|
Resumen:
|
In the last years, some extensions of ?-regular languages, namely, ?B-regular (?-regular languages extended with boundedness), ?S-regular (?-regular languages extended with strong unboundedness), and ?BS-regular languages (the combination of ?B- and ?S-regular ones), have been proposed in the literature. While the first two classes satisfy a generalized closure property, which states that the complement of an ?B-regular (resp., ?S-regular) language is an ?S-regular (resp., ?B-regular) one, the last class is not closed under complementation. The existence of non-?BS-regular languages that are the complements of some ?BS-regular ones and express fairly natural asymptotic behaviors motivates the search for other significant classes of extended ?-regular languages. In this paper, we present the class of ?T-regular languages, which includes meaningful languages that are not ?BS-regular. We define this new class of languages in terms of ?T-regular expressions. Then, we introduce a new class of automata (counter-check automata) and we prove that (i) their emptiness problem is decidable in PTIME, and (ii) they are expressive enough to capture ?T-regular languages. We also provide an encoding of ?T-regular expressions into S1S+U. Finally, we investigate a stronger variant of ?T-regular languages (-regular languages). We characterize the resulting class of languages in terms of -regular expressions, and we show how to map it into a suitable class of automata, called counter-queue automata. We conclude the paper with a comparison of the expressiveness of ?T- and -regular languages and of the corresponding automata.
|
