文章基本信息

标题：Uniform Random Expressions Lack Expressivity
本地全文：下载
作者：Florent Koechlin ; Cyril Nicaud ; Pablo Rotondo 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：138
页码：1-14
DOI：10.4230/LIPIcs.MFCS.2019.51
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Random expressions; simplification algorithms; analytic combinatorics