On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations
| Autor: | Pablo Rotondo, Cyril Nicaud, Florent Koechlin |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), The third author was funded by the Projet RIN Alenor (Regional Project from French Normandy), Nataša Jonoska, Dmytro Savchuk |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
050101 languages & linguistics 05 social sciences 02 engineering and technology 16. Peace & justice Article Expression (mathematics) Operator (computer programming) [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Bounded function [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Regular expression Degeneracy (mathematics) Mathematics |
| Zdroj: | Lecture Notes in Computer Science International Conference on Developments in Language Theory (DLT 2020) International Conference on Developments in Language Theory (DLT 2020), May 2020, Tampa, United States. pp.164-177, ⟨10.1007/978-3-030-48516-0_13⟩ Developments in Language Theory ISBN: 9783030485153 DLT Developments in Language Theory |
| DOI: | 10.1007/978-3-030-48516-0_13⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|