Interval logics and omegaB-regular languages

In the recent years, interval temporal logics are emerging as a workable alternative to more standard point-based ones. In this paper, we establish an original connection between these logics and ωB-regular languages. First, we provide a logical characterization of regular (resp., omega-regular) languages in the interval logic ABBbar of Allen's relations meets, begun by, and begins over finite linear orders (resp., N). Then, we lift such a correspondence to omegaB-regular languages by substituting AAbarBBbar for ABBbar (AAbarBBbar is obtained from ABBbar by adding a modality for Allen's relation met by). In addition, we show that new classes of extended (omega-)regular languages can be naturally defined in AAbarBbar.