You are not logged in | Log in

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.