One-Time Nondeterministic Computations

DOI10.1142/S012905411940029XzbMath1427.68145OpenAlexW3021003646WikidataQ127227448 ScholiaQ127227448MaRDI QIDQ5205043

Markus Holzer, Martin Kutrib

Publication date: 10 December 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905411940029x

zbMATH Keywords

limited nondeterminismdescriptional complexitynondeterministic finite automatanondeterministic pushdown automatarecursive and nonrecursive trade-offs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Goedel speed-up and succinctness of language representations
• Context-dependent nondeterminism for pushdown automata
• Classical finite transformation semigroups. An introduction.
• The state complexities of some basic operations on regular languages
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Automata, logics, and infinite games. A guide to current research
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata

This page was built for publication: One-Time Nondeterministic Computations