Push complexity: optimal bounds and decidability

DOI10.1016/J.TCS.2026.115839MaRDI QIDQ6837841zbMATH OpenFDO

Authors Giovanni Pighizzini

Publication date 26 March 2026

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

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115839

zbMATH Keywords

context-free languagesdescriptional complexitypushdown automataspace complexityunary languages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Generalization of Ogden's Lemma
• An optimal lower bound for nonregular languages
• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 3917711 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1390066 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• New results on the minimum amount of useful space
• On the degrees of non-regularity and non-context-freeness
• Optimal simulations between unary automata
• Push complexity: optimal bounds and unary inputs
• Pushdown and one-counter automata: constant and non-constant memory usage
• Pushdown automata and constant height: decidability and bounds
• Pushdown automata and constant height: decidability and bounds
• Some Results on Tape-Bounded Turing Machines
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
• Two Families of Languages Related to ALGOL
• Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.

This page was built for publication: Push complexity: optimal bounds and decidability

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