Reachability on prefix-recognizable graphs

DOI10.1016/J.IPL.2008.04.008zbMATH Open1191.68467OpenAlexW2108144184MaRDI QIDQ975403FDOQ975403

Authors: 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

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

Cited In (2)

• Submarking reachability of marked graphs
• Reachability relations and the structure of transitive digraphs

This page was built for publication: Reachability on prefix-recognizable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q975403)