Deterministic pushdown automata with translucent input letters

DOI10.1016/J.IC.2026.105403MaRDI QIDQ6865533zbMATH OpenFDO

Authors Martin Kutrib, Andreas Malcher, Carlo Mereghetti, Beatrice Palano, Priscilla Raucci, Matthias Wendlandt

Publication date 2 February 2026

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2026.105403

zbMATH Keywords

closure propertiescomputational capacitydeterministic pushdown automatareturning and non-returning computationstranslucent input letters

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A survey on automata with translucent letters
• CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store
• Church-Rosser Thue systems and formal languages
• Deterministic context free languages
• Deterministic pushdown automata with translucent input letters
• Deterministic pushdown-CD-systems of stateless deterministic R(1)-automata
• Growing context-sensitive languages and Church-Rosser languages
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3230262 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• Jump complexity of finite automata with translucent letters
• Jumping finite automata
• Membership for growing context-sensitive grammars is polynomial
• Non-returning deterministic and nondeterministic finite automata with translucent letters
• Nondeterministic right one-way jumping finite automata
• On CD-systems of stateless deterministic R-automata with window size one
• On growing context-sensitive languages
• On input-revolving deterministic and nondeterministic finite automata
• One-way jumping finite automata
• Restarting automata
• Restarting automata. The standard type of restarting automaton and its variants
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• The effect of jumping modes on various automata models

This page was built for publication: Deterministic pushdown automata with translucent input letters

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