State-freezing pushdown automata

DOI10.1007/978-3-032-02602-6_18MaRDI QIDQ6861675zbMATH OpenFDO

Authors Martin Kutrib, Andreas Malcher, Priscilla Raucci

Publication date 10 February 2026

Full work available at URL https://doi.org/10.1007/978-3-032-02602-6_18

zbMATH Keywords

closure propertiescomputational capacitydecidability problemsdeterministic counter automatadeterministic pushdown automataquasi-acyclic state graphsstate-freezing

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A pumping lemma for real-time deterministic context-free languages
• Cellular automata with sparse communication
• Counter machines and counter languages
• Counter machines and distributed automata -- a story about exchanging space and time
• 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 3718546 (Why is no real title available?)
• scientific article; zbMATH DE number 3532861 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Reversible pushdown automata
• Tinput-driven pushdown, counter, and stack automata
• Trace monoids with idempotent generators and measure-only quantum automata
• What makes some language theory problems undecidable

This page was built for publication: State-freezing pushdown automata

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