Input- or output-unary sweeping transducers are weaker than their 2-way counterparts

DOI10.1051/ITA/2016028MaRDI QIDQ2969980zbMATH OpenOpenAlexFDO

Authors Bruno Guillon

Publication date 24 March 2017

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/c863bc2c17ae51e0a82623274973b71df5525cee

zbMATH Keywords

Hadamard relationssweeping transducerstwo-wayunary alphabets

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Recommendations

• An algebraic characterization of unary two-way transducers
• One-way definability of sweeping transducer
• Untwisting two-way transducers in elementary time
• scientific article; zbMATH DE number 7003194
• Converting two-way nondeterministic unary automata into simpler automata.

Cites work

• An algebraic characterization of unary two-way transducers
• Elements of automata theory. Translated from the French by Reuben Thomas
• From two-way to one-way finite state transducers
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 177806 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• scientific article; zbMATH DE number 3254906 (Why is no real title available?)
• MSO definable string transductions and two-way finite-state transducers
• One-way definability of sweeping transducer
• Rational sets in commutative monoids
• Sequences of words defined by two-way transducers
• Tropical Two-Way Automata
• Two Families of Languages Related to ALGOL
• Uniformisation of two-way transducers

Cited in

(4)

• An algebraic characterization of unary two-way transducers
• On Hadamard series and rotating \(\mathbb{Q}\)-automata
• One-way definability of sweeping transducer
• Comparison-free polyregular functions

This page was built for publication: Input- or output-unary sweeping transducers are weaker than their 2-way counterparts

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