73 citations · 236 across the 29 of their papers we have counts for
19 papers · 1 filter
The Logic of Prefixes and Suffixes is Elementary under Homogeneity
Dario Della Monica, Angelo Montanari, Gabriele Puppis +1
In this paper, we study the finite satisfiability problem for the logic BE under the homogeneity assumption. BE is the cornerstone of Halpern and Shoham's interval temporal logic,…
Complexity of Safety and coSafety Fragments of Linear Temporal Logic
Alessandro Artale, Luca Geatti, Nicola Gigante +2
Linear Temporal Logic (LTL) is the de-facto standard temporal logic for system specification, whose foundational properties have been studied for over five decades. Safety and cosa…
The addition of temporal neighborhood makes the logic of prefixes and sub-intervals EXPSPACE-complete
L. Bozzelli, A. Montanari, A. Peron +1
A classic result by Stockmeyer gives a non-elementary lower bound to the emptiness problem for star-free generalized regular expressions. This result is intimately connected to the…
Adding the Relation Meets to the Temporal Logic of Prefixes and Infixes makes it EXPSPACE-Complete
Laura Bozzelli, Angelo Montanari, Adriano Peron +1
The choice of the right trade-off between expressiveness and complexity is the main issue in interval temporal logic. In their seminal paper, Halpern and Shoham showed that the sat…
Satisfiability and Model Checking for the Logic of Sub-Intervals under the Homogeneity Assumption
Laura Bozzelli, Alberto Molinari, Angelo Montanari +2
The expressive power of interval temporal logics (ITLs) makes them one of the most natural choices in a number of application domains, ranging from the specification and verificati…
Complexity of Timeline-Based Planning over Dense Temporal Domains: Exploring the Middle Ground
Laura Bozzelli, Alberto Molinari, Angelo Montanari +1
In this paper, we address complexity issues for timeline-based planning over dense temporal domains. The planning problem is modeled by means of a set of independent, but interacti…