1 citations · 1 across the 2 of their papers we have counts for
3 papers
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…
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…