Tight bounds for reachability problems on one-counter and pushdown systems
From MaRDI portal
Publication:2032173
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
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