Pushdown automata and constant height: decidability and bounds

DOI10.1007/978-3-030-23247-4_20MaRDI QIDQ2179342zbMATHOpenAlexFDO

Authors Giovanni Pighizzini, Luca Prigioniero

Publication date 12 May 2020

Full work available at URL https://hal.inria.fr/hal-02387302

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Height-Deterministic Pushdown Automata
• Removing nondeterminism in constant height pushdown automata
• Removing nondeterminism in constant height pushdown automata
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Descriptional complexity of pushdown store languages

Cited in

(9)

• Space Complexity of Stack Automata Models
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• Pushdown automata and constant height: decidability and bounds
• scientific article; zbMATH DE number 826075 (Why is no real title available?)
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• On the degrees of non-regularity and non-context-freeness
• Space complexity of stack automata models
• Variations on pushdown machines (Detailed Abstract)
• Height-Deterministic Pushdown Automata

This page was built for publication: Pushdown automata and constant height: decidability and bounds

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