14 citations · 15 across the 6 of their papers we have counts for
7 papers
Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata
Bruno Guillon, Luca Prigioniero, Javad Taheri
We prove that, paying a polynomial increase in size only, every unrestricted two-way nondeterministic finite automaton (2NFA) can be complemented by a 1-limited automaton (1-LA), a…
Nondeterminism makes unary 1-limited automata concise
Bruno Guillon, Luca Prigioniero, Javad Taheri
We investigate the descriptional complexity of different variants of 1-limited automata (1-las), an extension of two-way finite automata (2nfas) characterizing regular languages. I…
Weight-Reducing Turing Machines
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero +1
It is well-known that one-tape Turing machines working in linear time are no more powerful than finite automata, namely they recognize exactly the class of regular languages. We pr…
Converting Nondeterministic Two-Way Automata into Small Deterministic Linear-Time Machines
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero +1
In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and one-way nondeterministic automata into equivale…
Undecidability of a weak version of MSO+U
Mikołaj Bojańczyk, Laure Daviaud, Bruno Guillon +2
We prove the undecidability of MSO on -words extended with the second-order predicate which says that the distance between consecutive positions in a set $X \subseteq \…
Counter Machines and Distributed Automata: A Story about Exchanging Space and Time
Olivier Carton, Bruno Guillon, Fabian Reiter
We prove the equivalence of two classes of counter machines and one class of distributed automata. Our counter machines operate on finite words, which they read from left to right…
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…