2026-07-25T03:04:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18173 2024-03-06T11:01:13Z ddc:004 open_access

Deterministic Regular Functions of Infinite Words Carton, Olivier Douéneau-Tabot, Gaëtan Filiot, Emmanuel Winter, Sarah infinite words streaming string transducers two-way transducers monadic second-order logic look-aheads factorization forests Regular functions of infinite words are (partial) functions realized by deterministic two-way transducers with infinite look-ahead. Equivalently, Alur et. al. have shown that they correspond to functions realized by deterministic Muller streaming string transducers, and to functions defined by MSO-transductions. Regular functions are however not computable in general (for a classical extension of Turing computability to infinite inputs), and we consider in this paper the class of deterministic regular functions of infinite words, realized by deterministic two-way transducers without look-ahead. We prove that it is a well-behaved class of functions: they are computable, closed under composition, characterized by the guarded fragment of MSO-transductions, by deterministic Büchi streaming string transducers, by deterministic two-way transducers with finite look-ahead, and by finite compositions of sequential functions and one fixed basic function called map-copy-reverse. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Olivier Carton and Gaëtan Douéneau-Tabot and Emmanuel Filiot and Sarah Winter 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.121 urn:nbn:de:0030-drops-181733 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.121 eng https://creativecommons.org/licenses/by/4.0/legalcode