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

DOI10.1051/ITA/2016028zbMATH Open1362.68140OpenAlexW2575305094MaRDI QIDQ2969980FDOQ2969980

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

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.

zbMATH Keywords

two-wayHadamard relationssweeping transducersunary alphabets

Mathematics Subject Classification ID

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

Cites Work

• Elements of automata theory. Translated from the French by Reuben Thomas
• Title not available (Why is that?)
• Rational sets in commutative monoids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two Families of Languages Related to ALGOL
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Algebraic Characterization of Unary Two-Way Transducers
• MSO definable string transductions and two-way finite-state transducers
• Uniformisation of Two-Way Transducers
• Sequences of words defined by two-way transducers
• From Two-Way to One-Way Finite State Transducers
• One-way Definability of Sweeping Transducer.
• Tropical Two-Way Automata

Cited In (1)

• On Hadamard Series and Rotating Q-Automata

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)