ML Anthology

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

Julien Grange
IJCAI 2021 pp. 4775-4779
doi:10.24963/IJCAI.2021/649 /ijcai/2021/grange2021ijcai-successor/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Grange. "Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/649

Markdown

[Grange. "Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/grange2021ijcai-successor/) doi:10.24963/IJCAI.2021/649

BibTeX

@inproceedings{grange2021ijcai-successor,
  title     = {{Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)}},
  author    = {Grange, Julien},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {4775-4779},
  doi       = {10.24963/IJCAI.2021/649},
  url       = {https://mlanthology.org/ijcai/2021/grange2021ijcai-successor/}
}