13 citations · 65 across the 15 of their papers we have counts for
13 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,…
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…
Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison
Laura Bozzelli, Alberto Molinari, Angelo Montanari +2
In the last years, model checking with interval temporal logics is emerging as a viable alternative to model checking with standard point-based temporal logics, such as LTL, CTL, C…
Beyond BS-regular Languages: T-regular Expressions and Counter-Check Automata
Dario Della Monica, Angelo Montanari, Pietro Sala
In the last years, various extensions of ω-regular languages have been proposed in the literature, including ωB-regular (ω-regular languages extended with boundedness), ωS-regular…