Aperiodic string transducers

DOI10.1007/978-3-662-53132-7_11MaRDI QIDQ2817381zbMATH OpenOpenAlexFDO

Authors Luc Dartois, Ismaël Jecker, Pierre-Alain Reynier

Publication date 30 August 2016

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.04059

zbMATH Keywords

aperiodic string transducerstreaming string transducerstring transducertransition monoidtwo-way transducer

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Abstract: Regular string-to-string functions enjoy a nice triple characterization through deterministic two-way transducers (2DFT), streaming string transducers (SST) and MSO definable functions. This result has recently been lifted to FO definable functions, with equivalent representations by means of aperiodic 2DFT and aperiodic 1-bounded SST, extending a well-known result on regular languages. In this paper, we give three direct transformations: i) from 1-bounded SST to 2DFT, ii) from 2DFT to copyless SST, and iii) from k-bounded to 1-bounded SST. We give the complexity of each construction and also prove that they preserve the aperiodicity of transducers. As corollaries, we obtain that FO definable string-to-string functions are equivalent to SST whose transition monoid is finite and aperiodic, and to aperiodic copyless SST.

Recommendations

• Aperiodic string transducers
• Aperiodic two-way transducers and FO-transductions
• FO-definable transformations of infinite strings
• MSO definable string transductions and two-way finite-state transducers

Cites work

• Aperiodic string transducers
• Aperiodic two-way transducers and FO-transductions
• Expressiveness of streaming string transducers
• First-order definable string transformations
• From monadic second-order definable string transformations to transducers
• From two-way to one-way finite state transducers
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Logic-automata connections for transformations
• MSO definable string transductions and two-way finite-state transducers
• On finite monoids having only trivial subgroups
• Regular transformations of infinite strings
• Uniformisation of two-way transducers

Cited in

(8)

• Copyful streaming string transducers
• Aperiodic string transducers
• First-order definable string transformations
• FO-definable transformations of infinite strings
• Aperiodic string transducers
• Copyful streaming string transducers
• Aperiodic two-way transducers and FO-transductions
• Reversible transducers over infinite words

This page was built for publication: Aperiodic string transducers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817381)