Single-use automata and transducers—current standpoint

Speaker(s)

Rafał Stefański

Affiliation

MIM UW

Date

March 2, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

Register automata (as defined by Kaminski and Francez) are an established tool for studying languages and transductions over infinite alphabets. They share many desired properties of finite automata, but they also miss a few key ones. For example, their definitions are unstable—one-way deterministic, two-way deterministic, one-way nondeterministic and two-way nondeterministic register automata all recognize different classes of languages. In a paper from 2020, Mikołaj Bojańczyk and I argued that register automata become more stable if we limit them, by stating that every read access to a register should have the side effect of destroying that register’s contents. For example, with this single-use restriction, one-way and two-way register automata become equivalent. Another result of applying the single-use restriction is a rather interesting theory of transducers. In this talk, I will summarize some of the results from this paper and some subsequent unpublished developments. In particular, I will define both the classical and the single-use register automata and transducers, and compare their properties. I will also present some ongoing research regarding abstract single-use functions and totally ordered atoms. Finally, I will present some open problems. The talk will be based on joint research with Mikołaj Bojańczyk and Nathan Lhote.

---