Pushdown automata with bounded nondeterminism and bounded ambiguity

DOI10.1016/S0304-3975(96)00267-8zbMATH Open0901.68132OpenAlexW2632078856MaRDI QIDQ1391304FDOQ1391304

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

Recommendations

• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Context-dependent nondeterminism for pushdown automata
• Context-Dependent Nondeterminism for Pushdown Automata
• Pushdown automata free of explicit nondeterminism and an infinite hierarchy of context-free languages
• Measuring nondeterminism in pushdown automata

zbMATH Keywords

pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Title not available (Why is that?)
• Amounts of nondeterminism in finite automata
• Title not available (Why is that?)
• A note on the succinctness of descriptions of deterministic languages
• Succinctness of Descriptions of Unambiguous Context-Free Languages
• On measuring nondeterminism in regular languages
• Title not available (Why is that?)
• Title not available (Why is that?)
• Refining nondeterminism in context-free languages
• Title not available (Why is that?)

Cited In (33)

• Computation with multiple CTCs of fixed length and width
• Deciding path size of nondeterministic (and input-driven) pushdown automata
• Context-Dependent Nondeterminism for Pushdown Automata
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Self-verifying pushdown and queue automata
• Regulated nondeterminism in pushdown automata
• Context-dependent nondeterminism for pushdown automata
• Input-Driven Pushdown Automata with Limited Nondeterminism
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Title not available (Why is that?)
• Regulated Nondeterminism in Pushdown Automata
• Pushdown automata free of explicit nondeterminism and an infinite hierarchy of context-free languages
• Bounded Parikh automata
• Measuring nondeterminism in pushdown automata
• In memoriam Chandra Kintala
• Title not available (Why is that?)
• Non-recursive trade-offs between two-dimensional automata and grammars
• Title not available (Why is that?)
• Descriptional complexity of pushdown store languages
• Descriptional complexity of pushdown store languages
• Title not available (Why is that?)
• Automata that may change their mind
• McNaughton families of languages.
• One-time nondeterministic computations
• A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
• Limited nondeterminism of input-driven pushdown automata: decidability and complexity
• Title not available (Why is that?)
• Pushdown automata and constant height: decidability and bounds
• A Note on Pushdown Automata Systems
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
• Ambiguity in omega context free languages

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

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