Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Aperiodic String Transducers
verfasst von : Luc Dartois, Ismaël Jecker, Pierre-Alain Reynier
Erschienen in: Developments in Language Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Regular string-to-string functions enjoy a nice triple characterization through deterministic two-way transducers (\(\mathrm {2DFT}\)), streaming string transducers (\(\mathrm {SST}\)) and \(\mathrm {MSO}\) definable functions. This result has recently been lifted to \(\mathrm {FO}\) definable functions, with equivalent representations by means of aperiodic \(\mathrm {2DFT}\) and aperiodic 1-bounded \(\mathrm {SST}\), extending a well-known result on regular languages. In this paper, we give three direct transformations: (i) from 1-bounded \(\mathrm {SST}\) to \(\mathrm {2DFT}\), (ii) from \(\mathrm {2DFT}\) to copyless \(\mathrm {SST}\), and (iii) from k-bounded to 1-bounded \(\mathrm {SST}\). We give the complexity of each construction and also prove that they preserve the aperiodicity of transducers. As corollaries, we obtain that \(\mathrm {FO}\) definable string-to-string functions are equivalent to \(\mathrm {SST}\) whose transition monoid is finite and aperiodic, and to aperiodic copyless \(\mathrm {SST}\).