On Models of a Nondeterministic Computation

DOI10.1007/978-3-642-03351-3_31zbMath1248.68198OpenAlexW1709153679MaRDI QIDQ3392968

Mikhail N. Vyalyi

Publication date: 18 August 2009

Published in: Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_31

zbMATH Keywords

nondeterminismautomatoncomplexity class

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On regular realizability problems ⋮ Orbits of Linear Maps and Regular Languages ⋮ On the decidability of finding a positive ILP-instance in a regular set of ILP-instances ⋮ On Models of a Nondeterministic Computation ⋮ From decidability to undecidability by considering regular sets of instances ⋮ Automata equipped with auxiliary data structures and regular realizability problems

Cites Work

• Unnamed Item
• Unnamed Item
• Finite model theory and its applications.
• On the power of synchronization in parallel computations
• A communication hierarchy of parallel computations
• Alternating and empty alternating auxiliary stack automata.
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Undecidability on quantum finite automata
• Theory of Formal Systems. (AM-47)
• On Models of a Nondeterministic Computation
• Tree-Walking Automata
• Alternation
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers