Silent Transitions in Automata with Storage

The authors consider the problem of removing silent transitions from one-way automata with various kinds of storage. Specifically, they ask for which kinds of storage the real-time and the general version have equal computational power. They consider the computational power of silent transitions in one-way automata with storage. Specifically, they ask which storage mechanisms admit a transformation of a given automaton into one that accepts the same language and reads at least one input symbol in each step. They study this question using the model of valence automata. Here, a finite automaton is equipped with a storage mechanism that is given by a monoid.

Resource Details

Provided by:
Cornell University