Context-dependent nondeterminism for pushdown automata

DOI10.1016/J.TCS.2007.01.015MaRDI QIDQ880177zbMATH OpenOpenAlexFDO

Authors 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

deterministic pushdown automatacontext-free languagescomputational capacityclosures of languagestime-efficient recognizers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Context-Dependent Nondeterminism for Pushdown Automata
• Regulated Nondeterminism in Pushdown Automata
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Regulated 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 1995125 (Why is no real title available?)
• scientific article; zbMATH DE number 2068877 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Amounts of nondeterminism in finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• Finite turns and the regular closure of linear context-free languages
• Measures of nondeterminism for pushdown automata
• Measuring nondeterminism in pushdown automata
• On measuring nondeterminism in regular languages
• On the Amount of Nondeterminism and the Power of Verifying
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Real-time computations with restricted nondeterminism
• Regular Closure of Deterministic Languages

Cited in

(13)

• scientific article; zbMATH DE number 2150277 (Why is no real title available?)
• Context-Dependent Nondeterminism for Pushdown Automata
• A pumping lemma for regular closure of prefix-free languages
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Regulated nondeterminism in pushdown automata
• scientific article; zbMATH DE number 2040920 (Why is no real title available?)
• Regulated Nondeterminism in Pushdown Automata
• Regulated nondeterminism in pushdown automata: the non-regular case
• Syntax checking either way
• Syntax checking either way
• Automata that may change their mind
• One-time nondeterministic computations
• scientific article; zbMATH DE number 3883637 (Why is no real title available?)

This page was built for publication: Context-dependent nondeterminism for pushdown automata

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