scientific article; zbMATH DE number 7347653

zbMath1462.68105MaRDI QIDQ4988162

Martin Kutrib, Markus Holzer

Publication date: 12 May 2021

Full work available at URL: http://www.jalc.de/issues/2020/issue_25_2-3/jalc-2020-115-140.php

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• On Goedel speed-up and succinctness of language representations
• Context-dependent nondeterminism for pushdown automata
• The parallel complexity of finite-state automata problems
• Space-bounded reducibility among combinatorial problems
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Minimal NFA Problems are Hard
• One-Time Nondeterministic Computations
• On Computable Numbers, with an Application to the Entscheidungsproblem

This page was built for publication: