Digging input-driven pushdown automata

DOI10.1051/ITA/2021006MaRDI QIDQ5021110zbMATH OpenOpenAlexFDO

Authors Martin Kutrib, Andreas Malcher

Publication date 12 January 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

descriptional complexitydeterminizationclosure propertiesinput-driven pushdown automatacomputational capacitydecidability problemsempty pushdown behavior

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Tinput-Driven Pushdown Automata
• Tinput-driven pushdown, counter, and stack automata
• Input-driven double-head pushdown automata
• Further closure properties of input-driven pushdown automata
• Input-driven stack automata

Cites work

• scientific article; zbMATH DE number 3885334 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Adding nesting structure to words
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Input-Driven Pushdown Automata with Limited Nondeterminism
• Input-driven stack automata
• Jumping finite automata
• Minimizing Variants of Visibly Pushdown Automata
• On reducing the number of stack symbols in a PDA
• On reducing the number of states in a PDA
• Operator precedence and the visibly pushdown property
• Ordered multi-stack visibly pushdown automata
• P-hardness of the emptiness problem for visibly pushdown languages
• Scope-bounded pushdown languages
• Scope-bounded pushdown languages
• The tree width of auxiliary storage
• Tinput-driven pushdown, counter, and stack automata
• Visibly pushdown languages

Cited in

(9)

• Input-driven double-head pushdown automata
• On the power of pushing or stationary moves for input-driven pushdown automata
• Sweeping input-driven pushdown automata
• Input-driven stack automata
• Tinput-driven pushdown, counter, and stack automata
• Sweeping input-driven pushdown automata
• On the power of pushing or stationary moves for input-driven pushdown automata
• Tinput-Driven Pushdown Automata
• Input-Driven Double-Head Pushdown Automata

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

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