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

DOI10.1016/J.TCS.2024.114503MaRDI QIDQ6131193zbMATH OpenOpenAlexFDO

Authors Martin Kutrib, Andreas Malcher, Matthias Wendlandt

Publication date 4 April 2024

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

deterministic pushdown automatainput-driven pushdown automatacomputational capacitydecidability questionsrepresentation by inverse homomorphism

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Tinput-Driven Pushdown Automata
• Tinput-driven pushdown, counter, and stack automata
• Digging input-driven pushdown automata
• Input-driven stack automata
• Further closure properties of input-driven pushdown 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?)
• Adding nesting structure to words
• Digging input-driven pushdown automata
• Minimizing Variants of Visibly Pushdown Automata
• On the power of pushing or stationary moves for input-driven pushdown automata
• Operator precedence and the visibly pushdown property
• Synchronization of Pushdown Automata
• Tinput-driven pushdown, counter, and stack automata
• Visibly pushdown languages

Cited in

(1)

• Input-Driven Double-Head Pushdown Automata

This page was built for publication: On the power of pushing or stationary moves for input-driven pushdown automata

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