Towards a characterization of order-invariant queries over tame graphs

DOI10.2178/JSL/1231082307MaRDI QIDQ3616348zbMATH OpenOpenAlexFDO

Authors Michael Benedikt, Luc Segoufin

Publication date 25 March 2009

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2178/jsl/1231082307

zbMATH Keywords

collapsefinite model theorydefinabilityGaifman graphexpressive power of logics on finite graphs

Mathematics Subject Classification ID

Model theory of finite structures (03C13)

Recommendations

• Computer Science Logic
• Order invariance on decomposable structures
• Expressivity and succinctness of order-invariant logics on depth-bounded structures
• Lower bounds for invariant queries in logics with counting.
• Succinctness of Order-Invariant Logics on Depth-Bounded Structures

Cites work

• scientific article; zbMATH DE number 605773 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• Epsilon-logic is more expressive than first-order logic over finite structures
• Graph minors. III. Planar tree-width
• Locality of order-invariant first-order formulas
• On the strength of the interpretation method
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. X: Linear orderings

Cited in

(12)

• On the expressive power of logics with invariant uses of arithmetic predicates
• Computing possible and certain answers over order-incomplete data
• Order-invariant MSO is stronger than counting MSO in the finite
• Order-invariant types and their applications
• Locality of order-invariant first-order formulas
• On the locality of arb-invariant first-order formulas with modulo counting quantifiers
• Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
• Computer Science Logic
• On the ordered conjecture
• Order invariance on decomposable structures
• A short tutorial on order-invariant first-order logic
• Expressivity and succinctness of order-invariant logics on depth-bounded structures

This page was built for publication: Towards a characterization of order-invariant queries over tame graphs

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