# On the Limits of Decision: the Adjacent Fragment of First-Order Logic

From International Center for Computational Logic

# On the Limits of Decision: the Adjacent Fragment of First-Order Logic

##### Bartosz BednarczykBartosz Bednarczyk, Daumantas KojelisDaumantas Kojelis, Ian Pratt-HartmannIan Pratt-Hartmann

Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann

In Kousha Etessami, Uriel Feige, and Gabriele Puppis, eds.,

**On the Limits of Decision: the Adjacent Fragment of First-Order Logic**In Kousha Etessami, Uriel Feige, and Gabriele Puppis, eds.,

*Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming, ICALP 2023*, volume 261 of Leibniz International Proceedings in Informatics, 114:1--114:20, to appear. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik**Kurzfassung****Abstract**

We define the adjacent fragment AF of first-order logic, obtained by restricting the sequences of variables occurring as arguments in atomic formulas. The adjacent fragment generalizes (after a routine renaming) two-variable logic as well as the fluted fragment. We show that the adjacent fragment has the finite model property, and that its satisfiability problem is no harder than for the fluted fragment (and hence is Tower-complete). We further show that any relaxation of the adjacency condition on the allowed order of variables in argument sequences yields a logic whose satisfiability and finite satisfiability problems are undecidable. Finally, we study the effect of the adjacency requirement on the well-known guarded fragment (GF) of first-order logic. We show that the satisfiability problem for the guarded adjacent fragment (GA) remains 2ExpTime-hard, thus strengthening the known lower bound for GF.**Projekt:****Project:**DeciGUT**Forschungsgruppe:****Research Group:**Computational LogicComputational Logic

```
@inproceedings{BKP2023,
author = {Bartosz Bednarczyk and Daumantas Kojelis and Ian Pratt-Hartmann},
title = {On the Limits of Decision: the Adjacent Fragment of First-Order
Logic},
editor = {Kousha Etessami and Uriel Feige and and Gabriele Puppis},
booktitle = {Proceedings of the 50th {EATCS} International Colloquium on
Automata, Languages and Programming, {ICALP} 2023},
series = {Leibniz International Proceedings in Informatics},
volume = {261},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik},
year = {2023},
month = {July},
pages = {114:1--114:20}
}
```