Document Open Access Logo

Uniform Random Expressions Lack Expressivity

Authors Florent Koechlin, Cyril Nicaud, Pablo Rotondo

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.51.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Florent Koechlin
  • Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE, UPEM, France
Cyril Nicaud
  • Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE, UPEM, France
Pablo Rotondo
  • Université Paris-Est, LIGM (UMR 8049), CNRS, ENPC, ESIEE, UPEM, France

Cite AsGet BibTex

Florent Koechlin, Cyril Nicaud, and Pablo Rotondo. Uniform Random Expressions Lack Expressivity. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.MFCS.2019.51

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
Keywords
  • Random expressions
  • simplification algorithms
  • analytic combinatorics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jason P. Bell, Stanley Burris, and Karen A. Yeats. Characteristic Points of Recursive Systems. Electr. J. Comb., 17(1), 2010. Google Scholar
  2. Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. Average Size of Automata Constructions from Regular Expressions. Bulletin of the EATCS, 116, 2015. Google Scholar
  3. Nicolas Broutin and Cécile Mailler. And/or trees: A local limit point of view. Random Struct. Algorithms, 53(1):15-58, 2018. URL: https://doi.org/10.1002/rsa.20758.
  4. Brigitte Chauvin, Danièle Gardy, and Cécile Mailler. A sprouting tree model for random boolean functions. Random Struct. Algorithms, 47(4):635-662, 2015. URL: https://doi.org/10.1002/rsa.20567.
  5. Michael Drmota. Systems of functional equations. Random Struct. Algorithms, 10(1-2):103-124, 1997. Google Scholar
  6. Michael Drmota. Random Trees: An Interplay Between Combinatorics and Probability. Springer Publishing Company, Incorporated, 1st edition, 2009. Google Scholar
  7. Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. Boltzmann Samplers for the Random Generation of Combinatorial Structures. Combinatorics, Probability & Computing, 13(4-5):577-625, 2004. Google Scholar
  8. Philippe Flajolet and Andrew M. Odlyzko. The Average Height of Binary Trees and Other Simple Trees. J. Comput. Syst. Sci., 25(2):171-213, 1982. URL: https://doi.org/10.1016/0022-0000(82)90004-6.
  9. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. URL: http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=9780521898065.
  10. Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert. Analytic Variations on the Common Subexpression Problem. In Mike Paterson, editor, Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16-20, 1990, Proceedings, volume 443 of Lecture Notes in Computer Science, pages 220-234. Springer, 1990. URL: https://doi.org/10.1007/BFb0032034.
  11. Philippe Flajolet and Jean-Marc Steyaert. A Complexity Calculus for Recursive Tree Algorithms. Mathematical Systems Theory, 19(4):301-331, 1987. URL: https://doi.org/10.1007/BF01704918.
  12. Danièle Gardy. Random Boolean expressions. In David, René, Gardy, Danièle, Lescanne, Pierre, Zaionc, and Marek, editors, Computational Logic and Applications, CLA '05, volume DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05) of DMTCS Proceedings, pages 1-36, Chambéry, France, 2005. Discrete Mathematics and Theoretical Computer Science. URL: https://hal.inria.fr/hal-01183339.
  13. Antoine Genitrini and Bernhard Gittenberger. No Shannon effect on probability distributions on Boolean functions induced by random expressions. In Discrete Mathematics and Theoretical Computer Science, pages 303-316. Discrete Mathematics and Theoretical Computer Science, 2010. Google Scholar
  14. Antoine Genitrini, Bernhard Gittenberger, and Cécile Mailler. No Shannon effect induced by And/Or trees. In 25th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, pages 109-120, 2014. Google Scholar
  15. A Meir and J.W Moon. On an asymptotic method in enumeration. Journal of Combinatorial Theory, Series A, 51(1):77-89, 1989. URL: https://doi.org/10.1016/0097-3165(89)90078-2.
  16. Michel Nguyên-Thê. Distribution of Valuations on Trees. Theses, Ecole Polytechnique X, February 2004. URL: https://pastel.archives-ouvertes.fr/pastel-00000839.
  17. Cyril Nicaud. On the Average Size of Glushkov’s Automata. In Adrian-Horia Dediu, Armand-Mihai Ionescu, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings, volume 5457 of Lecture Notes in Computer Science, pages 626-637. Springer, 2009. Google Scholar
  18. Cyril Nicaud, Carine Pivoteau, and Benoît Razet. Average Analysis of Glushkov Automata under a BST-Like Model. In Kamal Lodaya and Meena Mahajan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, volume 8 of LIPIcs, pages 388-399. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010. Google Scholar
  19. Albert Nijenhuis and Herbert S Wilf. Combinatorial algorithms for computers and calculators. Computer Science and Applied Mathematics, New York: Academic Press, 1978, 2nd ed., 1978. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact