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., ω-regular) languages in the interval logic ABB ̄ of Allen’s relations meets, begun by, and begins over finite linear orders (resp., N). Then, we lift such a correspondence to ωB-regular languages by substituting ABB ̄A ̄ for ABB ̄ (ABB ̄A ̄ is obtained from ABB ̄ by adding a modality for Allen’s relation met by). In addition, we show that new classes of extended (ω-)regular languages can be naturally defined in ABB ̄A ̄.
Interval Logics and ωB-Regular Languages
SALA, Pietro
2013-01-01
Abstract
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., ω-regular) languages in the interval logic ABB ̄ of Allen’s relations meets, begun by, and begins over finite linear orders (resp., N). Then, we lift such a correspondence to ωB-regular languages by substituting ABB ̄A ̄ for ABB ̄ (ABB ̄A ̄ is obtained from ABB ̄ by adding a modality for Allen’s relation met by). In addition, we show that new classes of extended (ω-)regular languages can be naturally defined in ABB ̄A ̄.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
