Pushdown reachability with constant treewidth
DOI10.1016/j.ipl.2017.02.003zbMath1422.68184OpenAlexW2591236525MaRDI QIDQ1675921
Georg Osang, Krishnendu Chatterjee
Publication date: 3 November 2017
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2017.02.003
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. III. Planar tree-width
- Matrix multiplication via arithmetic progressions
- Efficient algorithms for clique problems
- General context-free recognition in less than cubic time
- S-functions for graphs
- Complete problems for deterministic polynomial time
- All structured programs have small tree width and good register allocation
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth
- Algorithms for algebraic path properties in concurrent systems of constant treewidth components
- Subcubic algorithms for recursive state machines
- Fast context-free grammar parsing requires fast boolean matrix multiplication
- If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
- Regularity Lemmas and Combinatorial Algorithms
- SOFSEM 2005: Theory and Practice of Computer Science
- Computer Aided Verification
This page was built for publication: Pushdown reachability with constant treewidth
