Single use register automata for data words

We introduce a new automaton model for data words, called single use register automata. These are like register automata for data words (introduced by Kaminski and Francez), with the restriction that every read access to a register destroys the register contents. We prove that the following models are equivalent: (a) one-way deterministic single use register automata; (b) two-way deterministic single use register automata; (c) languages recognised by orbit-finite semigroups.

Authors

• Rafał Stefański.

Keywords

No keywords are indexed for this paper.