Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth

DOI10.1145/2676726.2676979zbMath1346.68047arXiv1410.7724OpenAlexW2074131210MaRDI QIDQ2819794

Krishnendu Chatterjee, Prateesh Goyal, Rasmus Ibsen-Jensen, Andreas Pavlogiannis

Publication date: 29 September 2016

Published in: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.7724

zbMATH Keywords

interprocedural analysisdataflow analysisconstant treewidth graphsreachability and shortest path

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Theory of programming languages (68N15)

Related Items (6)

Graph Games and Reactive Synthesis ⋮ Pushdown reachability with constant treewidth ⋮ Faster Algorithms for Weighted Recursive State Machines ⋮ What’s Decidable About Program Verification Modulo Axioms? ⋮ Tight bounds for reachability problems on one-counter and pushdown systems ⋮ Faster algorithms for quantitative verification in bounded treewidth graphs

This page was built for publication: Faster Algorithms for Algebraic Path Properties in Recursive State Machines with Constant Treewidth