Reachability on prefix-recognizable graphs

DOI10.1016/j.ipl.2008.04.008zbMath1191.68467OpenAlexW2108144184MaRDI QIDQ975403

Stefan Göller

Publication date: 9 June 2010

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

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

zbMATH Keywords

computational complexityreachabilityalternationprefix-recognizable graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Finite presentations of infinite structures: Automata and interpretations
• On infinite transition graphs having a decidable monadic theory
• A note on emptiness for alternating finite automata with a one-letter alphabet
• Reachability problems on regular ground tree rewriting graphs
• Efficient Algorithms for Alternating Pushdown Systems with an Application to the Computation of Certificate Chains
• Alternation
• Prefix-Recognizable Graphs and Monadic Logic
• First-order and counting theories ofω-automatic structures
• Symbolic Backwards-Reachability Analysis for Higher-Order Pushdown Systems
• Foundations of Software Science and Computation Structures
• Reachability analysis of pushdown automata: Application to model-checking