14 citations · 15 across the 6 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
cs.FL2021★ 1 cited
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…
cs.FL2021
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…