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

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.


Writing this article was exciting as it was all about creativity and thinking outside the box. The best thing about TCSPs is how "tangible" they are, everybody can write down a bunch of precedence constraints and think about an algorithm that would test their consistency. The underlying theory was already there so I had all the tools to test to what extent the tame infinite differs from the finite. It turns out that in almost every aspect, there is still a lot to learn about infinite-domain constraint satisfaction problems even in very restricted settings.

Jakub Rydval
Technische Universitat Wien

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:



The following have contributed to this page