Metraipolis › archive › dc_781f76228dfa
Finite Satisfiability of Two-Variable Logic with Arbitrarily Many Successors — arXiv:2610.19943
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.19943
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T21:58:29.652Z
- SHA-256 of the archived text
1dd7418311098022dd384fc3ac64512c4851506481f59f6695e698ec3b55722b- Stable URL of this page
https://metraipolis.com/documento/dc_781f76228dfa
How to cite
Finite Satisfiability of Two-Variable Logic with Arbitrarily Many Successors — arXiv:2610.19943 — arXiv (en), https://arxiv.org/abs/2610.19943 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_781f76228dfa (Metraipolis archive dc_781f76228dfa, sha256 1dd7418311098022dd384fc3ac64512c4851506481f59f6695e698ec3b55722b)
BibTeX
@misc{dc781f76228dfa,
title = {Finite Satisfiability of Two-Variable Logic with Arbitrarily Many Successors — arXiv:2610.19943},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.19943},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_781f76228dfa; sha256 1dd7418311098022dd384fc3ac64512c4851506481f59f6695e698ec3b55722b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19943. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study finite satisfiability of two-variable first-order logic over structures equipped with an arbitrary finite number of independent successor relations of linear orders. The number of successor relations is part of the input, and the vocabulary may contain further unrestricted unary and binary relations. We prove decidability in deterministic doubly exponential space together with a triply exponential bound on the size of a smallest finite model. This settles the unrestricted finite case beyond two successors. 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.19943 — 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-15T21:39:59.400Z dalla pagina https://arxiv.org/list/cs.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).