Informace o publikaci
Geometrically closed positive varieties of languages
| Autoři | |
|---|---|
| Rok publikování | 2022 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Information and Computation |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://www.sciencedirect.com/science/article/pii/S0890540121000249#! |
| Doi | http://dx.doi.org/10.1016/j.ic.2021.104709 |
| Klíčová slova | Geometrical closure; Commutative closure; Variety of languages; Star-free language |
| Popis | A recently introduced operation of geometrical closure on formal languages is investigated from the viewpoint of algebraic language theory. Positive varieties V containing exclusively languages with regular geometrical closure are fully characterised by inclusion of V in W, a known positive variety arising in the study of the commutative closure. It is proved that the geometrical closure of a language from the intersection of W with the variety of all star-free languages SF always falls into RLT, which is introduced as a subvariety of R, the variety of languages recognised by R-trivial monoids. All classes between RLT and W?SF are thus geometrically closed: for instance, the level 3/2 of the Straubing-Thérien hierarchy, the DA-recognisable languages, or the variety R. It is also shown that W?SF is the largest geometrically closed positive variety of star-free languages, while there is no largest geometrically closed positive variety of regular languages. |
| Související projekty: |