1 citations · 1 across the 4 of their papers we have counts for
5 papers
Unary Versus Binary Two-Way Automata
Viliam Geffert, Vincent Hlaváč, Rastislav Královič
If L is a unary language, then its binary coded version bin(L) is a binary language containing all binary strings representing any 0^x in L. It is known that if a unary language L…
Classical automata on promise problems
Viliam Geffert, Abuzer Yakaryilmaz
Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a f…
Two-Way Automata Making Choices Only at the Endmarkers
Viliam Geffert, Bruno Guillon, Giovanni Pighizzini
The question of the state-size cost for simulation of two-way nondeterministic automata (2NFAs) by two-way deterministic automata (2DFAs) was raised in 1978 and, despite many attem…
Translation from Classical Two-Way Automata to Pebble Two-Way Automata
Viliam Geffert, Lubomíra Ištoňová
We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata with an additional "pebble" movable along the input tape. Sim…
An In-Place Sorting with O(n log n) Comparisons and O(n) Moves
Gianni Franceschini, Viliam Geffert
We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This so…