Other formats:
BibTeX
LaTeX
RIS
@article{1840697,
author = {Klíma, Ondřej and Kostolányi, Peter},
article_number = {October},
doi = {http://dx.doi.org/10.1016/j.ic.2021.104709},
keywords = {Geometrical closure; Commutative closure; Variety of languages; Star-free language},
language = {eng},
issn = {0890-5401},
journal = {Information and Computation},
title = {Geometrically closed positive varieties of languages},
url = {https://www.sciencedirect.com/science/article/pii/S0890540121000249#!},
volume = {288},
year = {2022}
}
TY - JOUR
ID - 1840697
AU - Klíma, Ondřej - Kostolányi, Peter
PY - 2022
TI - Geometrically closed positive varieties of languages
JF - Information and Computation
VL - 288
IS - October
SP - 1-17
EP - 1-17
PB - Elsevier
SN - 08905401
KW - Geometrical closure
KW - Commutative closure
KW - Variety of languages
KW - Star-free language
UR - https://www.sciencedirect.com/science/article/pii/S0890540121000249#!
N2 - 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.
ER -
KLÍMA, Ondřej and Peter KOSTOLÁNYI. Geometrically closed positive varieties of languages. \textit{Information and Computation}. Elsevier, 2022, vol.~288, October, p.~1-17. ISSN~0890-5401. Available from: https://dx.doi.org/10.1016/j.ic.2021.104709.
|
