2026-07-21T14:08:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10995 2024-03-06T10:47:00Z ddc:004 open_access

Uniform Random Expressions Lack Expressivity Koechlin, Florent Nicaud, Cyril Rotondo, Pablo Random expressions simplification algorithms analytic combinatorics In this article, we question the relevance of uniform random models for algorithms that use expressions as inputs. Using a general framework to describe expressions, we prove that if there is a subexpression that is absorbing for a given operator, then, after repeatedly applying the induced simplification to a uniform random expression of size n, we obtain an equivalent expression of constant expected size. This proves that uniform random expressions lack expressivity, as soon as there is an absorbing pattern. For instance, (a+b)^* is absorbing for the union for regular expressions on {a,b}, hence random regular expressions can be drastically reduced using the induced simplification. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florent Koechlin and Cyril Nicaud and Pablo Rotondo 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.51 urn:nbn:de:0030-drops-109957 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.51 eng https://creativecommons.org/licenses/by/3.0/legalcode