Reachability on prefix-recognizable graphs

DOI10.1016/J.IPL.2008.04.008MaRDI QIDQ975403zbMATH OpenOpenAlexFDO

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

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

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)