Digging input-driven pushdown automata

DOI10.1051/ITA/2021006OpenAlexW3186999106MaRDI QIDQ5021110

Andreas Malcher, Martin Kutrib

Publication date: 12 January 2022

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2021006

zbMATH Keywords

closure propertiesdescriptional complexitydeterminizationinput-driven pushdown automatacomputational capacitydecidability problemsempty pushdown behavior

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

On the power of pushing or stationary moves for input-driven pushdown automata ⋮ Sweeping input-driven pushdown automata ⋮ On the power of pushing or stationary moves for input-driven pushdown automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ordered multi-stack visibly pushdown automata
• Operator precedence and the visibly pushdown property
• P-hardness of the emptiness problem for visibly pushdown languages
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Input-Driven Stack Automata
• Input-Driven Pushdown Automata with Limited Nondeterminism
• On reducing the number of stack symbols in a PDA
• Adding nesting structure to words
• Minimizing Variants of Visibly Pushdown Automata
• Visibly pushdown languages
• On reducing the number of states in a PDA
• Tinput-Driven Pushdown, Counter, and Stack Automata
• JUMPING FINITE AUTOMATA
• The tree width of auxiliary storage
• Scope-Bounded Pushdown Languages
• Scope-Bounded Pushdown Languages

This page was built for publication: Digging input-driven pushdown automata