Concatenation of inputs in a two-way automaton

DOI10.1016/0304-3975(89)90075-3zbMath0664.68081OpenAlexW1985201105MaRDI QIDQ1115636

Jean-Camille Birget

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90075-3

zbMATH Keywords

subset constructioncrossing sequenceBirget semigroupconcatenation of inputsglobal transition mapstwo-way automatontwo-way transformation semigroups

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (9)

A linear-time simulation of deterministic \(d\)-limited automata ⋮ State-complexity of finite-state devices, state compressibility and incompressibility ⋮ Two-way automaton computations ⋮ Two-way representations and weighted automata ⋮ Sur les codes zigzag et leur décidabilité. (Zigzag codes and their decidability) ⋮ Two-way automata and length-preserving homomorphisms ⋮ Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations ⋮ The zig-zag power series: A two-way version of the \({}^*\) operator. ⋮ Regular transducer expressions for regular transformations

Cites Work

• Two-way automaton computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Concatenation of inputs in a two-way automaton