Interval-based Synthesis

In this paper, we introduce the synthesis problem for Halpern and Shoham’s interval temporal logic [5] extended with an equivalence relation ∼ over time points (HS ∼ for short). In analogy to the case of monadic second-order logic of one successor [2], given an HS ∼ formula φ and a finite set ΣT ofpropositionlettersandtemporalrequests,theproblemconsistsofestablishingwhetherornot, forallpossibleevaluationsofelementsinΣT ineveryintervalstructure,thereisanevaluationofthe remaining proposition letters and temporal requests such that the resulting structure is a model for φ. We focus our attention on the decidability of the synthesis problem for some meaningful fragments of HS ∼, whose modalities are drawn from {A (meets), A ̄ (met by), B (begun by), B ̄ (begins)}, interpreted over finite linear orders and natural numbers. We prove that the synthesis problem for ABB ∼ over finite linear orders is decidable (non-primitive recursive hard), while AA ̄BB ̄ turns out to be undecidable. In addition, we show that if we replace finite linear orders by natural numbers, then the problem becomes undecidable even for ABB ̄.