Tight bounds for reachability problems on one-counter and pushdown systems

DOI10.1016/j.ipl.2021.106135OpenAlexW3158908103MaRDI QIDQ2032173

Adam Husted Kjelstrøm, Andreas Pavlogiannis, Jakob Cetti Hansen

Publication date: 16 June 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106135

zbMATH Keywords

formal languagespushdown systemsone-counter systemsDyck reachability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• All structured programs have small tree width and good register allocation
• Pushdown reachability with constant treewidth
• Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth
• Faster Algorithms for Weighted Recursive State Machines
• Subcubic algorithms for recursive state machines
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Reachability analysis of pushdown automata: Application to model-checking