Skip to Main content Skip to Navigation
Conference papers

Uniform Random Expressions Lack Expressivity

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-03145930
Contributor : Admin Upem Connect in order to contact the contributor
Submitted on : Thursday, February 18, 2021 - 4:54:36 PM
Last modification on : Tuesday, October 19, 2021 - 11:26:22 AM
Long-term archiving on: : Wednesday, May 19, 2021 - 7:30:33 PM

File

MFCS19.pdf
Publisher files allowed on an open archive

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

`

Citation

Florent Koechlin, Cyril Nicaud, Pablo Rotondo. Uniform Random Expressions Lack Expressivity. MFCS 2019, Aug 2019, Aachen, Germany. pp.51:1-51:14, ⟨10.4230/LIPIcs.MFCS.2019.51⟩. ⟨hal-03145930⟩

Share

Metrics

Record views

32

Files downloads

28