Temporal Constraint Satisfaction Problems in Fixed-Point Logic
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
Finite-domain constraint satisfaction problems are either solvable by Datalog, or not even expressible in fixed-point logic with counting. The border between the two regimes can be described by a strong height-one Maltsev condition. For infinite-domain CSPs, the situation is more complicated even if the template structure of the CSP is model-theoretically tame. We prove that there is no Maltsev condition that characterizes Datalog already for the CSPs of first-order reducts of (Q; <); such CSPs are called temporal CSPs and are of fundamental importance in infinite-domain constraint satisfaction. Our main result is a complete classification of temporal CSPs that can be expressed in one of the following logical formalisms: Datalog, fixed-point logic (with or without counting), or fixed-point logic with the Boolean rank operator. The classification shows that many of the equivalent conditions in the finite fail to capture expressibility in Datalog or fixed-point logic already for temporal CSPs.
Details
Originalsprache | Englisch |
---|---|
Titel | Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 |
Herausgeber (Verlag) | Association for Computing Machinery (ACM), New York |
Seiten | 237-251 |
Seitenumfang | 15 |
ISBN (elektronisch) | 978-1-4503-7104-9 |
Publikationsstatus | Veröffentlicht - 8 Juli 2020 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | LICS: Logic in Computer Science |
---|---|
ISSN | 1043-6871 |
Konferenz
Titel | 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 |
---|---|
Dauer | 8 - 11 Juli 2020 |
Stadt | Saarbrucken |
Land | Deutschland |
Externe IDs
ORCID | /0000-0001-8228-3611/work/142241065 |
---|
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- fixed-point logic, Maltsev conditions, temporal constraint satisfaction problems