On Models of a Nondeterministic Computation
From MaRDI portal
Publication:3392968
DOI10.1007/978-3-642-03351-3_31zbMath1248.68198OpenAlexW1709153679MaRDI QIDQ3392968
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
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 (6)
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
This page was built for publication: On Models of a Nondeterministic Computation