Convex and Reverse Convex Prequadratics Constraints for Decidable Logics of Relations with Cardinalities
ACM Transactions on Computational Logic · 31.10.2026 · 27 (4) · 1-19
DOI: 10.1145/3820035 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computational Logic, online erschienen am 15.07.2026. Verfasst von Rodrigo Raya und 2 weiteren Autor:innen. Die Arbeit nennt 78 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung Project.
Abstract (Originalsprache)
We investigate decision procedures for quantifier-free fragments of set theory extended with relational and cardinality constraints. While the satisfiability problem for the general fragment is undecidable due to the existence of reductions from Hilbert’s 10th problem, in this article we show that extensions of existential Presburger arithmetic with atoms of the form \(x\leq y^{d}\) or of the form \(y^{d}\leq x\) , where \(d\in\mathbb{N}\) , are decidable in non-deterministic polynomial time. We apply these results to fragments of quantifier-free relational logic. Our methods rely on a normal form for linear constraints, which may be of independent interest.
Förderung
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung Project
Zitieren
APA
Raya, R., Hamza, J., & Kunčak, V. (2026). Convex and Reverse Convex Prequadratics Constraints for Decidable Logics of Relations with Cardinalities. ACM Transactions on Computational Logic, 27(4), 1-19. https://doi.org/10.1145/3820035
Vancouver
Raya R, Hamza J, Kunčak V. Convex and Reverse Convex Prequadratics Constraints for Decidable Logics of Relations with Cardinalities. ACM Transactions on Computational Logic. 2026;27(4):1-19. doi:10.1145/3820035
BibTeX
@article{Raya2026,
author = {Raya, Rodrigo and Hamza, Jad and Kunčak, Viktor},
title = {Convex and Reverse Convex Prequadratics Constraints for Decidable Logics of Relations with Cardinalities},
journal = {ACM Transactions on Computational Logic},
year = {2026},
volume = {27},
number = {4},
pages = {1--19},
doi = {10.1145/3820035}
}
EUVIMED