Single use transducers over infinite alphabets

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.