---
title: "Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)"
authors:
  - "Julien Grange"
doi: "10.24963/ijcai.2021/649"
url: "https://ijcai.org/proceedings/2021/649"
pdf: "https://ijcai.org/proceedings/2021/0649.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4775-4779"
track: "Sister Conferences Best Papers"
keywords:
  - "Knowledge Representation and Reasoning: Logics for Knowledge Representation"
---

# Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)

Julien Grange

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 4775-4779. DOI: [10.24963/ijcai.2021/649](https://doi.org/10.24963/ijcai.2021/649)

## Abstract

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