Uniform simulations of nondeterministic real time multitape turing machines

DOI10.1007/BF01704917zbMath0633.68036OpenAlexW2012951761MaRDI QIDQ3771615

Andreas Brandstädt, Klaus W. Wagner, Franz-Josef Brandenburg

Publication date: 1987

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01704917

zbMATH Keywords

simulationsreal timefamilies of languageshierarchieslinear timenondeterministic multitape Turing machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items

A note on: `Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages' (by K. Ayers)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reset machines
• Multiple equality sets and Post machines
• Reversal-bounded multipushdown machines
• One way finite visit automata
• Remarks on blind and partially blind one-way multicounter machines
• A relation between space, return and dual return complexities
• Checking automata and one-way stack languages
• Equality Sets and Complexity Classes
• Reversal-Bounded Acceptors and Intersections of Linear Languages
• Simple Representations of Certain Classes of Languages
• Linear Languages and the Intersection Closures of Classes of Languages
• Visits, crosses, and reversals for nondeterministic off-line machines
• Counter machines and counter languages
• One-way stack automata
• Quasi-realtime languages
• One-way nondeterministic real-time list-storage languages
• Real-Time Simulation of Multihead Tape Units