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

DOI10.1016/0022-0000(92)90045-KzbMath0769.68019OpenAlexW2079856360WikidataQ123298544 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 monoidsdeterministic two-way finite automatonalternating one-tape linear-time Turing machinesalternating two-way finite automatanon-deterministic two-way finite automatonone-pebble automata

Mathematics Subject Classification ID

Related Items (5)

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

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations