You are not logged in |
joint work with Rafał Stefański
- Speaker(s)
- Mikołaj Bojańczyk
- Affiliation
- Uniwersytet Warszawski
- Date
- April 29, 2020, 2:15 p.m.
- Information about the event
- Online seminar
- Title in Polish
- Single use transducers over infinite alphabets
- Seminar
- Seminar Automata Theory
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.
