Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations

DOI10.1016/0022-0000(92)90045-KzbMath0769.68019WikidataQ123298544 ScholiaQ123298544MaRDI QIDQ1201150

Jean-Camille Birget

Publication date: 17 January 1993

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90045-k

zbMATH Keywords

finite monoids; deterministic two-way finite automaton; alternating one-tape linear-time Turing machines; alternating two-way finite automata; non-deterministic two-way finite automaton; one-pebble automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

Two-way automata and length-preserving homomorphisms, The equivalence of pebbles and sensing heads for finite automata, State-complexity of finite-state devices, state compressibility and incompressibility, Alternation in two-way finite automata, Boolean language operations on nondeterministic automata with a pushdown of constant height

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On equations for regular languages, finite automata, and sequential networks
• Arbitrary vs. regular semigroups
• Concatenation of inputs in a two-way automaton
• Alternating Pushdown and Stack Automata
• Alternation
• Nondeterminism and the size of two way finite automata
• One-tape, off-line Turing machine computations