Wilf classes of non-symmetric operads
arXiv:2105.08880 · doi:10.1145/3452143.3465555
Abstract
Two operads are said to belong to the same Wilf class if they have the same generating series. We discuss possible Wilf classifications of non-symmetric operads with monomial relations. As a corollary, this would give the same classification for the operads with a finite Groebner basis. Generally, there is no algorithm to decide whether two finitely presented operads belong to the same Wilf class. Still, we show that if an operad has a finite Groebner basis, then the monomial basis of the operad forms an unambiguous context-free language. Moreover, we discuss the deterministic grammar which defines the language. The generating series of the operad can be obtained as a result of an algorithmic elimination of variables from the algebraic system of equations defined by the Chomsky--Schutzenberger enumeration theorem. We then focus on the case of binary operads with a single relation. The approach is based on the results by Rowland on pattern avoidance in binary trees. We improve and refine Rowland's calculations and empirically confirm his conjecture. Here we use both the algebraic elimination and the direct calculation of formal power series from algebraic systems of equations. Finally, we discuss the connection of Wilf classes with algorithms for the Quillen homology of operads calculation.
arXiv comment8 pages
References in corpus (9)
- Gröbner bases for operads
- Pattern avoidance in binary trees
- Quillen homology for operads via Gröbner bases
- Shuffle algebras, homology, and consecutive pattern avoidance
- On generating series of finitely presented operads
- Pattern avoidance in labelled trees
- Tree series and pattern avoidance in syntax trees
- Growth in varieties of multioperator algebras and Groebner bases in operads
- Inversion of integral series enumerating planar trees