10 citations · 16 across the 4 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…
Weakly and Strongly Irreversible Regular Languages
Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero
Finite automata whose computations can be reversed, at any point, by knowing the last k symbols read from the input, for a fixed k, are considered. These devices and their accepted…