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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3478529
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact