Visits, crosses, and reversals for nondeterministic off-line machines

DOI10.1016/S0019-9958(78)90289-9zbMath0375.02027OpenAlexW1994749191MaRDI QIDQ4154851

Sheila A. Greibach

Publication date: 1978

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(78)90289-9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10)

Related Items

Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ On the power of alternation on reversal-bounded alternating Turing machines with a restriction ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals ⋮ Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines ⋮ Iterated stack automata and complexity classes ⋮ The power of two-way deterministic checking stack automata ⋮ The ancestor width of grammars and languages