Speaker
Rafał Stefański, University College London
Title
Single-use Restriction vs. Associativity
Abstract
The context of this talk is regular languages over infinite alphabets. In a recent paper (ICALP 2020) together with Bojańczyk, we studied a version of automata constrained by a single-use restriction which limits their data access. We showed that single-use one-way automata and single-use two-way automata are equivalent. Moreover both of those models are equivalent to monoids, which is quite mysterious, as monoids are not explicitly constrained by the single-use restriction. Instead, the restriction seems to be implicitly enforced by the associativity of monoids. In this talk, I am going to discuss this phenomenon for transducers (focusing mainly on Mealy machines).
