Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
From MaRDI portal
Publication:1201150
DOI10.1016/0022-0000(92)90045-KzbMath0769.68019WikidataQ123298544 ScholiaQ123298544MaRDI QIDQ1201150
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
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
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