On Models of a Nondeterministic Computation

DOI10.1007/978-3-642-03351-3_31MaRDI QIDQ3392968zbMATH OpenOpenAlexFDO

Authors Mikhail 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

automatonnondeterminismcomplexity 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)

Recommendations

• On multi-head automata with restricted nondeterminism
• On non-determinism in machines and languages
• Nondeterminism within $P^ * $
• scientific article; zbMATH DE number 176517
• Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• A communication hierarchy of parallel computations
• Alternating and empty alternating auxiliary stack automata.
• Alternation
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Finite model theory and its applications.
• On Models of a Nondeterministic Computation
• On the power of synchronization in parallel computations
• Theory of Formal Systems. (AM-47)
• Tree-Walking Automata
• Undecidability on quantum finite automata

Cited in

(18)

• On regular realizability problems
• Orbits of linear maps and regular languages
• Non-deterministic data types: Models and implementations
• Computational complexity in non-Turing models of computation: the what, the why and the how
• Nondeterministic polynomial-time computations and models of arithmetic
• scientific article; zbMATH DE number 4128803 (Why is no real title available?)
• Natural computation and non-Turing models of computation
• On Models of a Nondeterministic Computation
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
• From decidability to undecidability by considering regular sets of instances
• scientific article; zbMATH DE number 1231470 (Why is no real title available?)
• On the Herbrand-Kleene universe for nondeterministic computations
• Computability and universal determinability of negatively representable models
• A nondeterministic extension over finitely recursive process model
• On universality of regular realizability problems
• Modelling higher-order dual nondeterminacy
• scientific article; zbMATH DE number 3903969 (Why is no real title available?)
• Automata equipped with auxiliary data structures and regular realizability problems

This page was built for publication: On Models of a Nondeterministic Computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392968)