Metraipolis › archive › dc_f75f825bf50d
Automatic constraints with few subpowers and graphoid recognition — arXiv:2609.07891
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.07891
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T15:39:59.414Z
- SHA-256 of the archived text
11e0d9b49829d4bbe3a7e60a761975c19d6d92bd6a7e47660085c79072216736- Stable URL of this page
https://metraipolis.com/documento/dc_f75f825bf50d
How to cite
Automatic constraints with few subpowers and graphoid recognition — arXiv:2609.07891 — arXiv (en), https://arxiv.org/abs/2609.07891 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f75f825bf50d (Metraipolis archive dc_f75f825bf50d, sha256 11e0d9b49829d4bbe3a7e60a761975c19d6d92bd6a7e47660085c79072216736)
BibTeX
@misc{dcf75f825bf50d,
title = {Automatic constraints with few subpowers and graphoid recognition — arXiv:2609.07891},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.07891},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f75f825bf50d; sha256 11e0d9b49829d4bbe3a7e60a761975c19d6d92bd6a7e47660085c79072216736},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07891. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Finite automata can describe relations of unbounded arity that are exponentially larger than their descriptions. We prove that constraint satisfaction for such relations is solvable in polynomial time whenever their length slices are preserved by a common fixed edge operation on a finite domain. The algorithm computes compact representations of the complete solution relation and its projections. Its main ingredient is a polynomial-time compilation of nondeterministic finite automata into the fork witnesses and small projections required by the few-subpowers algorithm. In the Mal'tsev case, a direct proof is polynomial also when the domain and operation table are supplied as input, answering the Mal'tsev tractability question for automatic constraint satisfaction. We also characterize all invariant relations of a family of 3-edge algebras with neither Mal'tsev nor near-unanimity terms. Their normal forms combine Boolean activity constraints with affine value spaces and yield canonical quadratic-bit representations constructible from NFAs or arbitrary generators. For graphoid automata, these results give polynomial-time recognition without a graph-width restriction, effective boundary composition, and comparison of finite graph relations. The quadratic boundary bounds are optimal in the worst case. A fixed three-state example separates polynomial-time recognition from hard exact counting. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LO). Categorie arXiv: Logic in Computer Science (cs.LO) ; Formal Languages and Automata Theory (cs.FL). Pagina del lavoro: https://arxiv.org/abs/2609.07891 — 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-16T15:30:57.134Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).