Context-dependent nondeterminism for pushdown automata
From MaRDI portal
Publication:880177
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
context-free languagesdeterministic pushdown automatacomputational capacityclosures of languagestime-efficient recognizers
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