Single-use register automata and orbit-finite monoids for total-order atoms

Single-use register automata are a variant of register automata (in the style of Kaminski & Francez) in which every read access to register destroys its contents. Last year at Highlights, I discussed single-use register automata for atoms which can only be compared for equality. This year, I will discuss atoms with total orders. One notable difference between these two kinds of atoms is that with equality only, single-use automata recognise the same languages as orbit-finite semigroups, while in the presence of total order, single-use automata correspond to an interesting subclass of orbit-finite semigroups. This is based on joint work with Mikołaj Bojańczyk and Nathan Lhote.

Authors

• Rafał Stefański

Keywords

No keywords are indexed for this paper.