Pushdown automata with bounded nondeterminism and bounded ambiguity

DOI10.1016/S0304-3975(96)00267-8MaRDI QIDQ1391304zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

• scientific article; zbMATH DE number 3839323 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1346507 (Why is no real title available?)
• scientific article; zbMATH DE number 1995125 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A note on the succinctness of descriptions of deterministic languages
• Amounts of nondeterminism in finite automata
• On measuring nondeterminism in regular languages
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Refining nondeterminism in context-free languages
• Succinctness of Descriptions of Unambiguous Context-Free Languages

Cited in

(32)

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

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)