Simplifications of Uniform Expressions Specified by Systems

Autor:	Florent Koechlin, Cyril Nicaud, Pablo Rotondo
Rok vydání:	2021
Předmět:	Reduction (complexity) Algebra Operator (computer programming) Simple (abstract algebra) Computer Science (miscellaneous) Analytic combinatorics Mathematics
Zdroj:	International Journal of Foundations of Computer Science. 32:733-760
ISSN:	1793-6373 0129-0541
DOI:	10.1142/s0129054121420065
Popis:	In this article, we study the impact of applying simple reduction rules to random syntactic formulas encoded as trees. We assume that there is an operator that has an absorbing pattern and prove that if we use this property to simplify a uniform random expression with [Formula: see text] nodes, then the expected size of the result is bounded by a constant. The same holds for higher moments, establishing the lack of expressivity of uniform random expressions. Our framework is quite general as we consider expressions defined by systems of combinatorial equations. For our proofs, we rely on Drmota’s multidimensional theorem for systems of generating functions.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b276ed31cd4f4c368669b76752b52d36 https://doi.org/10.1142/s0129054121420065 Zobrazit plný text záznamu