Context-dependent nondeterminism for pushdown automata

DOI10.1016/j.tcs.2007.01.015zbMath1111.68060OpenAlexW2004724199MaRDI QIDQ880177

Martin Kutrib, Andreas Malcher

Publication date: 11 May 2007

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.01.015

zbMATH Keywords

context-free languagesdeterministic pushdown automatacomputational capacityclosures of languagestime-efficient recognizers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Regulated nondeterminism in pushdown automata, Syntax checking either way, Unnamed Item, Regulated Nondeterminism in Pushdown Automata, Syntax checking either way, One-Time Nondeterministic Computations, A pumping lemma for regular closure of prefix-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On measuring nondeterminism in regular languages
• Amounts of nondeterminism in finite automata
• Measures of nondeterminism for pushdown automata
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Communication complexity method for measuring nondeterminism in finite automata
• Finite turns and the regular closure of linear context-free languages
• Measuring nondeterminism in pushdown automata
• Real-time computations with restricted nondeterminism
• Regular Closure of Deterministic Languages
• On the Amount of Nondeterminism and the Power of Verifying