Interval Temporal Logics: a Journey
In the framework of the "Milan Seminar on Automata and Formal Languages" initiative, which provides monthly seminars at UniversitÓ di Milano, UniversitÓ di Milano-Bicocca and Politecnico di Milano, on Thursday, March 22nd, 2012 , at Dipartimento di Elettronica e Informazione in via Ponzio 34/5, Milano, PT1 room, Angelo Montanari will speak about "Interval Temporal Logics: a Journey".
In this talk, I describe a family of modal logics for reasoning about relational structures of intervals over (usually) linear orders, with modal operators associated with the various binary relations between such intervals, known as Allen's interval relations. The formulae of these logics are evaluated at intervals rather than points and the main effect of that semantic feature is substantially higher expressiveness and computational complexity of the interval logics as compared to point-based ones. Without purporting to provide a comprehensive survey of the field, I take the audience to a journey through the main developments in it over the past 10 years and outline some landmark results on expressiveness and (un)decidability of the satisfiability problem for the family of interval logics.