Search

• We prove that the restriction to future semantics does not recover decidability of timeline based planning over dense time. • We introduce two semantic variants (weak and strong minimal) of timeline based planning expressing meaningful properties. • The problem is undecidable for the strong minimal semantics and PSPACE-complete for the weak minimal one. • Membership in PSPACE is determined by introducing an original strictly more expressive extension of Event-Clock Automata. The problem of timeline-based planning (TP) over dense temporal domains is known to be undecidable in the general case. We first prove that the restriction to the future semantics does not suffice to recover decidability. Then, we introduce two semantic variants of TP, called strong minimal and weak minimal semantics, and show that they allow one to express meaningful properties. Both semantics are based on the minimality in the time distances of the existentially-quantified time events from the universally-quantified reference one, but the weak minimal variant distinguishes minimality in the past from minimality in the future. Surprisingly, we show that, despite the (apparently) small differences between the two semantics, the TP problem is still undecidable for the strong minimal one, while it is PSPACE -complete for the weak minimal one. Membership in PSPACE is determined by exploiting a strictly more expressive extension (ECA +) of the well-known robust class of Event-Clock Automata (ECA), that allows us to encode the weak minimal TP problem and to reduce it to non-emptiness of Timed Automata (TA). Finally, an extension of ECA +(ECA ++) is considered, proving that its non-emptiness problem is undecidable. We believe that the two extensions of ECA (ECA + and ECA ++), introduced for technical reasons, are actually valuable per sé in the field of TA.1 [ABSTRACT FROM AUTHOR]

Cost-parity games are a fundamental tool in system design for the analysis of reactive and distributed systems that recently have received a lot of attention from the formal methods research community. They allow to reason about the time delay on the requests granted by systems, with a bounded consumption of resources, in their executions. In this paper, we contribute to research on cost-parity games by combining them with hierarchical systems , a successful method for the succinct representation of models. We show that determining the winner of a Hierarchical Cost-parity Game is Pspace -complete, thus matching the complexity of the proper special case of Hierarchical Parity Games. This shows that reasoning about temporal delay can be addressed at a free cost in terms of complexity. [ABSTRACT FROM AUTHOR]

Planning is one of the most studied problems in computer science. In this paper, we focus on the timeline-based approach, where the domain is modeled by a set of independent, but interacting, components, each one represented by a number of state variables, whose behavior over time (timelines) is governed by a set of temporal constraints (transition functions and synchronization rules). Whereas the time domain is usually assumed to be discrete, here we address decidability and complexity issues for timeline-based planning (TP) over dense time. We first prove that dense TP is undecidable in the general case; then, we show that decidability can be recovered by restricting to synchronization rules with a suitable future semantics. More "tractable" settings can be obtained by additionally constraining the form of intervals used in rules: EXPSPACE -completeness is obtained by avoiding singular intervals, and PSPACE -completeness by admitting only intervals of the forms [ 0 , a ] and [ b , + ∞ [. Finally, NP -completeness can be proved for dense TP with purely existential rules only. [ABSTRACT FROM AUTHOR]

We investigate the succinctness gap between two known equally-expressive and different linear-past extensions of standard ATL ⁎ . We establish by formal non-trivial arguments that the 'memoryful' linear-past extension (the history leading to the current state is taken into account) can be exponentially more succinct than the standard 'local' linear-past extension (the history leading to the current state is forgotten). As a second contribution, we consider the ATL -like fragment, denoted ATL l p , of the known 'memoryful' linear-past extension of ATL ⁎ . We show that ATL l p is strictly more expressive than ATL , and interestingly, it can be exponentially more succinct than the more expressive logic ATL ⁎. Moreover, we prove that both satisfiability and model-checking for the logic ATL l p are Exptime -complete. [ABSTRACT FROM AUTHOR]

Abstract Since the 80s, model checking (MC) has been applied to the automatic verification of hardware/software systems. Point-based temporal logics, such as LTL , CTL , CTL ⁎ , and the like, are commonly used in MC as the specification language; however, there are some inherently interval-based properties of computations, e.g., temporal aggregations and durations, that cannot be properly dealt with by these logics, as they model a state-by-state evolution of systems. Recently, an MC framework for the verification of interval-based properties of computations, based on Halpern and Shoham's interval temporal logic (HS , for short) and its fragments, has been proposed and systematically investigated. In this paper, we focus on the boundaries that separate tractable and intractable HS fragments in MC. We first prove that MC for the logic BE of Allen's relations started-by and finished-by is provably intractable, being Expspace -hard. Such a lower bound immediately propagates to full HS. Then, in contrast, we show that other noteworthy HS fragments, i.e., the logic A A ‾ B B ‾ (resp., A A ‾ E E ‾) of Allen's relations meets , met-by , starts (resp., finishes), and started-by (resp., finished-by), are well-behaved, and turn out to have the same complexity as LTL (Pspace -complete). Halfway are the fragments A A ‾ B B ‾ E ‾ and A A ‾ E B ‾ E ‾ , whose Expspace membership and Pspace hardness are already known. Here, we give an original proof of Expspace membership, that substantially simplifies the complexity of the constructions previously used for such a result. Contraction techniques—suitably tailored to each HS fragment—are at the heart of our results, enabling us to prove a pair of remarkable small-model properties. [ABSTRACT FROM AUTHOR]