Expressiveness and complexity of graph logic

DOI10.1016/J.IC.2006.10.006MaRDI QIDQ870359zbMATH OpenOpenAlexWikidataFDO

Authors Anuj Dawar, Philippa Gardner, G. Ghelli

Publication date 12 March 2007

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2006.10.006

zbMATH Keywords

graphscomplexityspatial logics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Logic in computer science (03B70)

Recommendations

• On the Expressive Power of Graph Logic
• L-recursion and a new logic for logarithmic space
• Expressive power of monadic logics on words, trees, pictures, and graphs
• L-recursion and a new logic for logarithmic space
• scientific article; zbMATH DE number 2086655

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 2081098 (Why is no real title available?)
• scientific article; zbMATH DE number 1747449 (Why is no real title available?)
• scientific article; zbMATH DE number 2163033 (Why is no real title available?)
• scientific article; zbMATH DE number 2086655 (Why is no real title available?)
• scientific article; zbMATH DE number 1841809 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• A logic you can count on
• A note on model checking the modal \(\nu\)-calculus
• Adjuncts elimination in the static ambient logic
• Alternating finite automata and star-free languages
• Anytime, anywhere: modal logics for mobile ambients
• Deciding validity in a spatial logic for trees
• Expressiveness and complexity of graph logic
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Foundations of Software Science and Computation Structures
• Model checking mobile ambients
• TQL: a query language for semistructured data based on the ambient logic
• The directed subgraph homeomorphism problem
• The polynomial-time hierarchy
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(25)

• Semantics for existential graphs
• A presheaf semantics for quantified temporal logics
• A term-graph clausal logic: completeness and incompleteness results ★
• Deciding safety properties in infinite-state pi-calculus via behavioural types
• On the almighty wand
• Separation logics and modalities: a survey
• scientific article; zbMATH DE number 2086655 (Why is no real title available?)
• L-recursion and a new logic for logarithmic space
• L-recursion and a new logic for logarithmic space
• Expressiveness and complexity of graph logic
• scientific article; zbMATH DE number 6739879 (Why is no real title available?)
• On temporal and separation logics
• The expressibility of fragments of hybrid graph logic on finite digraphs
• Expressive completeness of separation logic with two variables and no separating conjunction
• Graph logics with rational relations
• Two-Variable Separation Logic and Its Inner Circle
• On expressiveness of the chain graph interpretations
• Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree
• On the Expressive Power of Graph Logic
• Separation logic with one quantified variable
• On Composing Finite Forests with Modal Logics
• A Spatial Equational Logic for the Applied π-Calculus
• On the Almighty Wand
• Separating Graph Logic from MSO
• Specification and verification of a linear-time temporal logic for graph transformation

This page was built for publication: Expressiveness and complexity of graph logic

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