What is it about?
Temporal Constraint Satisfaction Problems (TCSPs) are derived from the basic task scheduling problem by allowing the use of Boolean combinations of precedence constraints. We present a complete classification of TCSPs with respect to their solvability in several standard logic programming languages such as Datalog. Our classification defies almost all expectations coming from the well-developed theory of constraint satisfaction problems with finite templates.
Featured Image
Photo by Michal Matlon on Unsplash
Why is it important?
Our work offers an in-depth analysis of the complexity of a particularly interesting family of infinite-domain constraint satisfaction problems from the perspective of logic programming using only basic tools of universal algebra. It is written in a down-to-earth format with the aim to be a solid entry-level article for any mathematician or computer scientist who might be interested in the topic. Simultaneously, it will be a valuable resource for the experts in the area who are typically interested in generalizing methods that work well in the finite-domain setting.
Perspectives
Read the Original
This page is a summary of: On the Descriptive Complexity of Temporal Constraint Satisfaction Problems, Journal of the ACM, December 2022, ACM (Association for Computing Machinery),
DOI: 10.1145/3566051.
You can read the full text:
Contributors
The following have contributed to this page