Single use transducers over infinite alphabets

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

29 kwietnia 2020 14:15

Informacje na temat wydarzenia

Online seminar

Tytuł w języku angielskim

joint work with Rafał Stefański

Seminarium

Seminarium „Teoria automatów”

---

Automata for infinite alphabets, despite the undeniable appeal, are a bit of a theoretical mess. Almost all models are non-equivalent as language recognisers: deterministic/nondeterministic/alternating, one-way/two-way, etc. Also monoids give a different class of languages, and mso gives yet another.

 

In this talk, I will describe how the single-use restriction can bring some order into this zoo. The single-use restriction says that once an atom from a register is queried, then that atom disappears. The single-use restriction was already described in a previous talk by Rafał Stefański. In this talk, I present some of our follow-up results, which involve transducers.

 

Among our results: a Factorisation Forest Theorem, a Krohn-Rhodes decomposition, and a class of “regular” transducers which admits four equivalent characterisations.

---