License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2019.51
URN: urn:nbn:de:0030-drops-109957
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10995/
Go to the corresponding LIPIcs Volume Portal

Koechlin, Florent ; Nicaud, Cyril ; Rotondo, Pablo

Uniform Random Expressions Lack Expressivity

pdf-format:
LIPIcs-MFCS-2019-51.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{koechlin_et_al:LIPIcs:2019:10995,
  author =	{Florent Koechlin and Cyril Nicaud and Pablo Rotondo},
  title =	{{Uniform Random Expressions Lack Expressivity}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Peter Rossmanith and Pinar Heggernes and Joost-Pieter Katoen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10995},
  URN =		{urn:nbn:de:0030-drops-109957},
  doi =		{10.4230/LIPIcs.MFCS.2019.51},
  annote =	{Keywords: Random expressions, simplification algorithms, analytic combinatorics}
}

Keywords: Random expressions, simplification algorithms, analytic combinatorics
Collection: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI