We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with nested pebbles. However,...
We consider conversions of regular expressions into -realtime
finite state automata, , automata in which the number of
consecutive uses of -transitions, along any computation path,
is bounded by a fixed constant . For -realtime automata,
, for automata that cannot change the state, without reading
an input symbol, more than two times in a row, we show that the
conversion of a regular expression into such an automaton produces
only states, log) -transitions, and
alphabet-transitions. We also show...
We study the relation between the standard two-way automata and
more powerful devices, namely, two-way finite automata equipped
with some additional “pebbles” that are movable along
the input tape, but their use is restricted (nested) in
a stack-like fashion. Similarly as in the case of the classical
two-way machines, it is not known whether there exists
a polynomial trade-off, in the number of states, between the
nondeterministic and deterministic two-way automata with
nested pebbles. However,...
Download Results (CSV)