Reachability logic: an efficient fragment of transitive closure logic

DOI10.1093/JIGPAL/8.3.325MaRDI QIDQ4487265zbMATH OpenOpenAlexFDO

Authors Natasha Alechina, Neil Immerman

Publication date 14 November 2000

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/9d7db8249836e0c61945b056873ab37edd8e0956

zbMATH Keywords

\(\text{CTL}^\star\)complexity of model checkinggraph query languagesPDLreachability logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Quantified computation tree logic
• Proving reachability-logic formulas incrementally
• scientific article; zbMATH DE number 2196601
• scientific article; zbMATH DE number 5148400
• Extended computation tree logic

Cited in

(9)

• Size-estimation framework with applications to transitive closure and reachability
• Quantified computation tree logic
• Space-efficient fragments of higher-order fixpoint logic
• Querying linguistic trees
• Proving reachability-logic formulas incrementally
• Existential Label Flow Inference Via CFL Reachability
• Foundations of RDF Databases
• PDL for ordered trees
• Comparing the succinctness of monadic query languages over finite trees

This page was built for publication: Reachability logic: an efficient fragment of transitive closure logic

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