2026-07-23T00:23:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6847 2024-03-06T10:39:01Z ddc:004 open_access

FO-Definable Transformations of Infinite Strings Dave, Vrunda Krishna, Shankara Narayanan Trivedi, Ashutosh Transducers FO-definability Infinite Strings The theory of regular and aperiodic transformations of finite strings has recently received a lot of interest. These classes can be equivalently defined using logic (Monadic second-order logic and first-order logic), two-way machines (regular two-way and aperiodic two-way transducers), and one-way register machines (regular streaming string and aperiodic streaming string transducers). These classes are known to be closed under operations such as sequential composition and regular (star-free) choice; and problems such as functional equivalence and type checking, are decidable for these classes. On the other hand, for infinite strings these results are only known for regular transformations: Alur, Filiot, and Trivedi studied transformations of infinite strings and introduced an extension of streaming string transducers over infinte strings and showed that they capture monadic second-order definable transformations for infinite strings. In this paper we extend their work to recover connection for infinite strings among first-order logic definable transformations, aperiodic two-way transducers, and aperiodic streaming string transducers. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vrunda Dave and Shankara Narayanan Krishna and Ashutosh Trivedi 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.12 urn:nbn:de:0030-drops-68476 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.12 eng https://creativecommons.org/licenses/by/3.0/legalcode