2026-07-26T03:07:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12520 2024-03-06T10:50:21Z ddc:004 open_access

Single-Use Automata and Transducers for Infinite Alphabets Bojańczyk, Mikołaj Stefański, Rafał Automata semigroups data words orbit-finite sets Our starting point are register automata for data words, in the style of Kaminski and Francez. We study the effects of the single-use restriction, which says that a register is emptied immediately after being used. We show that under the single-use restriction, the theory of automata for data words becomes much more robust. The main results are: (a) five different machine models are equivalent as language acceptors, including one-way and two-way single-use register automata; (b) one can recover some of the algebraic theory of languages over finite alphabets, including a version of the Krohn-Rhodes Theorem; (c) there is also a robust theory of transducers, with four equivalent models, including two-way single use transducers and a variant of streaming string transducers for data words. These results are in contrast with automata for data words without the single-use restriction, where essentially all models are pairwise non-equivalent. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikołaj Bojańczyk and Rafał Stefański 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.113 urn:nbn:de:0030-drops-125200 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.113 eng https://creativecommons.org/licenses/by/3.0/legalcode