Geometrically Closed Positive Varieties of Star-Free Languages

A recently introduced operation of geometrical closure on formal languages is investigated. It is proved that the geometrical closure of a language from the positive variety [Formula: see text], the level 3/2 of the Straubing-Thérien hierarchy of star-free languages, always falls into the variety [F...

Descripción completa

Detalles Bibliográficos
Autores principales: Klíma, Ondřej, Kostolányi, Peter
Formato: Online Artículo Texto
Lenguaje:English
Publicado: 2020
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206645/
http://dx.doi.org/10.1007/978-3-030-40608-0_23
_version_ 1783530450416828416
author Klíma, Ondřej
Kostolányi, Peter
author_facet Klíma, Ondřej
Kostolányi, Peter
author_sort Klíma, Ondřej
collection PubMed
description A recently introduced operation of geometrical closure on formal languages is investigated. It is proved that the geometrical closure of a language from the positive variety [Formula: see text], the level 3/2 of the Straubing-Thérien hierarchy of star-free languages, always falls into the variety [Formula: see text], which is a new variety consisting of specific R-trivial languages. As a consequence, each class of regular languages lying between [Formula: see text] and [Formula: see text] is geometrically closed.
format Online
Article
Text
id pubmed-7206645
institution National Center for Biotechnology Information
language English
publishDate 2020
record_format MEDLINE/PubMed
spelling pubmed-72066452020-05-08 Geometrically Closed Positive Varieties of Star-Free Languages Klíma, Ondřej Kostolányi, Peter Language and Automata Theory and Applications Article A recently introduced operation of geometrical closure on formal languages is investigated. It is proved that the geometrical closure of a language from the positive variety [Formula: see text], the level 3/2 of the Straubing-Thérien hierarchy of star-free languages, always falls into the variety [Formula: see text], which is a new variety consisting of specific R-trivial languages. As a consequence, each class of regular languages lying between [Formula: see text] and [Formula: see text] is geometrically closed. 2020-01-07 /pmc/articles/PMC7206645/ http://dx.doi.org/10.1007/978-3-030-40608-0_23 Text en © Springer Nature Switzerland AG 2020 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle Article
Klíma, Ondřej
Kostolányi, Peter
Geometrically Closed Positive Varieties of Star-Free Languages
title Geometrically Closed Positive Varieties of Star-Free Languages
title_full Geometrically Closed Positive Varieties of Star-Free Languages
title_fullStr Geometrically Closed Positive Varieties of Star-Free Languages
title_full_unstemmed Geometrically Closed Positive Varieties of Star-Free Languages
title_short Geometrically Closed Positive Varieties of Star-Free Languages
title_sort geometrically closed positive varieties of star-free languages
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7206645/
http://dx.doi.org/10.1007/978-3-030-40608-0_23
work_keys_str_mv AT klimaondrej geometricallyclosedpositivevarietiesofstarfreelanguages
AT kostolanyipeter geometricallyclosedpositivevarietiesofstarfreelanguages

Ejemplares similares