The Disjunctive Temporal Problem (DTP) consists of a finite set of time points and a finite set of constraints, each composed of alternative disjuncts modeling delays and deadlines for possibly different pairs of time points. An instance of DTP is consistent if there exists an assignment of real values to the time points such that all constraints are satisfied. Here we focus on DTPs with at most k >= 2 disjuncts per constraint. We define a few polynomial-time encoders to reduce the number of disjuncts to at most k', with 2 <= k' <= k, preserving (in)consistency of the original instance. These results generalize previous work in the literature. Anyway, we provide a methodology not related to any specific technology that sticks to DTP.
Reducing the Number of Disjuncts in DTPs
Zavatteri, Matteo
Membro del Collaboration Group
2023
Abstract
The Disjunctive Temporal Problem (DTP) consists of a finite set of time points and a finite set of constraints, each composed of alternative disjuncts modeling delays and deadlines for possibly different pairs of time points. An instance of DTP is consistent if there exists an assignment of real values to the time points such that all constraints are satisfied. Here we focus on DTPs with at most k >= 2 disjuncts per constraint. We define a few polynomial-time encoders to reduce the number of disjuncts to at most k', with 2 <= k' <= k, preserving (in)consistency of the original instance. These results generalize previous work in the literature. Anyway, we provide a methodology not related to any specific technology that sticks to DTP.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
