Single use register automata for data words
- Speaker(s)
- Rafał Stefański (joint work with Mikołaj Bojańczyk)
- Affiliation
- Uniwersytet Warszawski
- Date
- Feb. 20, 2019, 2:15 p.m.
- Room
- room 5050
- Seminar
- Seminar Automata Theory
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:
one-way deterministic single use register automata;
two-way deterministic single use register automata;
languages recognised by orbit-finite semigroups.