Cargando…
On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations
We consider general expressions, which are trees whose nodes are labeled with operators, that represent syntactic descriptions of formulas. We assume that there is an operator that has an absorbing pattern and prove that if we use this property to simplify a uniform random expression with n nodes, t...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
2020
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7247884/ http://dx.doi.org/10.1007/978-3-030-48516-0_13 |
_version_ | 1783538256039641088 |
---|---|
author | Koechlin, Florent Nicaud, Cyril Rotondo, Pablo |
author_facet | Koechlin, Florent Nicaud, Cyril Rotondo, Pablo |
author_sort | Koechlin, Florent |
collection | PubMed |
description | We consider general expressions, which are trees whose nodes are labeled with operators, that represent syntactic descriptions of formulas. We assume that there is an operator that has an absorbing pattern and prove that if we use this property to simplify a uniform random expression with n nodes, then the expected size of the result is bounded by a constant. In our framework, expressions are defined using a combinatorial system, which describes how they are built: one can ensure, for instance, that there are no two consecutive stars in regular expressions. This generalizes a former result where only one equation was allowed, confirming the lack of expressivity of uniform random expressions. |
format | Online Article Text |
id | pubmed-7247884 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2020 |
record_format | MEDLINE/PubMed |
spelling | pubmed-72478842020-05-26 On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations Koechlin, Florent Nicaud, Cyril Rotondo, Pablo Developments in Language Theory Article We consider general expressions, which are trees whose nodes are labeled with operators, that represent syntactic descriptions of formulas. We assume that there is an operator that has an absorbing pattern and prove that if we use this property to simplify a uniform random expression with n nodes, then the expected size of the result is bounded by a constant. In our framework, expressions are defined using a combinatorial system, which describes how they are built: one can ensure, for instance, that there are no two consecutive stars in regular expressions. This generalizes a former result where only one equation was allowed, confirming the lack of expressivity of uniform random expressions. 2020-05-26 /pmc/articles/PMC7247884/ http://dx.doi.org/10.1007/978-3-030-48516-0_13 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 Koechlin, Florent Nicaud, Cyril Rotondo, Pablo On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations |
title | On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations |
title_full | On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations |
title_fullStr | On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations |
title_full_unstemmed | On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations |
title_short | On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations |
title_sort | on the degeneracy of random expressions specified by systems of combinatorial equations |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7247884/ http://dx.doi.org/10.1007/978-3-030-48516-0_13 |
work_keys_str_mv | AT koechlinflorent onthedegeneracyofrandomexpressionsspecifiedbysystemsofcombinatorialequations AT nicaudcyril onthedegeneracyofrandomexpressionsspecifiedbysystemsofcombinatorialequations AT rotondopablo onthedegeneracyofrandomexpressionsspecifiedbysystemsofcombinatorialequations |