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

Grange, Julien

doi:10.24963/ijcai.2021/649

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

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Sister Conferences Best Papers. Pages 4775-4779.

https://doi.org/10.24963/ijcai.2021/649

Keywords

Knowledge Representation and Reasoning: Logics for Knowledge Representation

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.

Julien Grange. 2021. Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract). In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4775–4779. https://doi.org/10.24963/ijcai.2021/649

@inproceedings{ijcai2021p649,
  title     = {Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)},
  author    = {Grange, Julien},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {4775--4779},
  year      = {2021},
  month     = {8},
  note      = {Sister Conferences Best Papers},
  doi       = {10.24963/ijcai.2021/649},
  url       = {https://doi.org/10.24963/ijcai.2021/649},
}

TY  - CPAPER
TI  - Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)
AU  - Grange, Julien
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4775
EP  - 4779
DO  - 10.24963/ijcai.2021/649
UR  - https://doi.org/10.24963/ijcai.2021/649
ER  -