Metraipolis › archive › dc_f1922ebd33c8

Two Variables and Two-Dimensional Structures — arXiv:2610.20937

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.20937
License (as archived)
CC0-1.0
Archived
2026-10-16T10:40:27.764Z
SHA-256 of the archived text
c378b0acacb0f57be48d46c7c0e5b4fa7683e1a86ab4948df3b1737237171c59
Stable URL of this page
https://metraipolis.com/documento/dc_f1922ebd33c8

How to cite

Two Variables and Two-Dimensional Structures — arXiv:2610.20937 — arXiv (en), https://arxiv.org/abs/2610.20937 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f1922ebd33c8 (Metraipolis archive dc_f1922ebd33c8, sha256 c378b0acacb0f57be48d46c7c0e5b4fa7683e1a86ab4948df3b1737237171c59)
BibTeX
@misc{dcf1922ebd33c8,
  title = {Two Variables and Two-Dimensional Structures — arXiv:2610.20937},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.20937},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f1922ebd33c8; sha256 c378b0acacb0f57be48d46c7c0e5b4fa7683e1a86ab4948df3b1737237171c59},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20937. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the two-variable fragment FO^2 of first-order logic over two-dimensional structures. Formulae may employ two linear orders <=_1, <=_2, their successor relations S_1, S_2, and auxiliary predicates of any arity. Despite two decades of work, three cases of finite satisfiability in this setting were still open; we settle all three. First, finite satisfiability of FO^2 with one linear order and one successor relation, of the same or of a different order, is NExpTime-complete, even with arbitrary auxiliary predicates and constant symbols. This closes a gap left open by Manuel and Zeume (CSL 2013). As an application, a reduction based on swaps of adjacent elements shows that order-invariance and order-successor-invariance of FO^2 are coNExpTime-complete. This reproves the main result of Zeume and Harwath (LICS 2016) and settles their question on order-successor-invariance. Second, finite satisfiability of FO^2 with two linear orders is ExpSpace-hard, already without auxiliary non-unary predicates, matching the upper bound known since 2010. Our reduction combines Kieronski's encoding of alternating Turing machines with the classical fact that the pre-order and post-order traversals of a tree define its descendant relation. Third, with two linear orders and the successor of one of them, finite satisfiability is in ExpSpace even with arbitrary auxiliary predicates, improving the previous 2NExpTime bound and confirming a conjecture of Zeume and Harwath. Together with known results, our theorems show that in two dimensions, auxiliary (non-unary) predicates and constants come for free: with or without them, the complexities coincide. All our proofs are simple.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.LO, nuovi lavori del giorno).
Categorie arXiv: Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2610.20937 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:53:32.663Z dalla pagina https://arxiv.org/list/cs.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).