Pushdown automata with bounded nondeterminism and bounded ambiguity

DOI10.1016/S0304-3975(96)00267-8zbMath0901.68132OpenAlexW2632078856MaRDI QIDQ1391304

Christian Herzog

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00267-8

zbMATH Keywords

pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (16)

Regulated nondeterminism in pushdown automata ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ Context-dependent nondeterminism for pushdown automata ⋮ Unnamed Item ⋮ Pushdown automata with bounded nondeterminism and bounded ambiguity ⋮ Regulated Nondeterminism in Pushdown Automata ⋮ Non-recursive trade-offs between two-dimensional automata and grammars ⋮ Ambiguity in omega context free languages ⋮ McNaughton families of languages. ⋮ A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ Self-Verifying Pushdown and Queue Automata ⋮ One-Time Nondeterministic Computations ⋮ Measuring nondeterminism in pushdown automata ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Computation with multiple CTCs of fixed length and width

Cites Work

• On measuring nondeterminism in regular languages
• Amounts of nondeterminism in finite automata
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• A note on the succinctness of descriptions of deterministic languages
• Succinctness of Descriptions of Unambiguous Context-Free Languages
• Refining nondeterminism in context-free languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Pushdown automata with bounded nondeterminism and bounded ambiguity