In this paper, we introduce a new class of automata over infinite words (counter-queue automata) and we prove the decidability of their emptiness problem. Then, we define an original extension of ω-regular languages, called ωT-regular languages, that captures meaningful languages that neither belong to the class of ω-regular languages nor to other extensions of it proposed in the literature, and we show that counter-queue automata are expressive enough to encode them.
Counter-queue automata with an application to a meaningful extension of ω-regular languages
A. Montanari;P. Sala
2017-01-01
Abstract
In this paper, we introduce a new class of automata over infinite words (counter-queue automata) and we prove the decidability of their emptiness problem. Then, we define an original extension of ω-regular languages, called ωT-regular languages, that captures meaningful languages that neither belong to the class of ω-regular languages nor to other extensions of it proposed in the literature, and we show that counter-queue automata are expressive enough to encode them.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
