Successor-Invariant First-Order Logic on Classes of Bounded Degree

DOI10.1145/3373718.3394767zbMATH Open1498.03069arXiv2009.11758OpenAlexW3032610015WikidataQ130826261 ScholiaQ130826261MaRDI QIDQ5145657FDOQ5145657

Julien Grange

Publication date: 21 January 2021

Published in: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: We study the expressive power of successor-invariant first-order logic, which is an extension of first-order logic where the usage of an additional successor relation on the structure is allowed, as long as the validity of formulas is independent of the choice of a particular successor on finite structures. We show that when the degree is bounded, successor-invariant first-order logic is no more expressive than first-order logic.

Full work available at URL: https://arxiv.org/abs/2009.11758

zbMATH Keywords

finite model theoryfirst-order logicsuccessor-invariance

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Classical first-order logic (03B10) Descriptive complexity and finite models (68Q19) Interpolation, preservation, definability (03C40)

Cites Work

• Title not available (Why is that?)
• Elements of finite model theory.
• Deciding First-Order Properties of Nowhere Dense Graphs
• On monadic NP vs monadic co-NP
• Locality of order-invariant first-order formulas
• Title not available (Why is that?)
• Towards a characterization of order-invariant queries over tame graphs
• Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures
• Successor-invariant first-order logic on finite structures
• Order-Invariant First-Order Logic over Hollow Trees
• Order Invariance on Decomposable Structures

Cited In (4)

• Feferman-vaught decompositions for prefix classes of first order logic
• Spectra and satisfiability for logics with successor and a unary function
• Succinctness of Order-Invariant Logics on Depth-Bounded Structures
• Title not available (Why is that?)

This page was built for publication: Successor-Invariant First-Order Logic on Classes of Bounded Degree

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