Some extensions of w-regular languages have been proposed in the literature to express asymptotic properties of w-words which are not captured by w-regular languages. They include wB-regular languages, that extend w-regular languages with boundedness, wS- regular languages, that enrich w-regular ones with strong unboundedness, wBS-regular languages, that combine wB- and wS-regular ones, and wff-regular languages, that include meaningful languages which are not wBS-regular. Formal definitions of extended w-regular languages have been given in terms of both suitable classes of automata and extended w -regular expressions, while satisfactory temporal logic counterparts are still missing. In this paper, we give a characterization of them in terms of interval temporal logics by providing an explicit encoding of expressions into formulas.(c) 2023 Elsevier B.V. All rights reserved.
An interval temporal logic characterization of extended w-regular languages
Sala, P
2023-01-01
Abstract
Some extensions of w-regular languages have been proposed in the literature to express asymptotic properties of w-words which are not captured by w-regular languages. They include wB-regular languages, that extend w-regular languages with boundedness, wS- regular languages, that enrich w-regular ones with strong unboundedness, wBS-regular languages, that combine wB- and wS-regular ones, and wff-regular languages, that include meaningful languages which are not wBS-regular. Formal definitions of extended w-regular languages have been given in terms of both suitable classes of automata and extended w -regular expressions, while satisfactory temporal logic counterparts are still missing. In this paper, we give a characterization of them in terms of interval temporal logics by providing an explicit encoding of expressions into formulas.(c) 2023 Elsevier B.V. All rights reserved.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
