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

reachability logicPDL\(\text{CTL}^\star\)complexity of model checkinggraph query languages

Mathematics Subject Classification ID

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

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)

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

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)