Laida Kushnareva, Daniil Cherniavskii, Vladislav Mikhailov, Ekaterina Artemova, Serguei Barannikov, Alexander Bernstein, Irina Piontkovskaya, Dmitri Piontkovski, Evgeny Burnaev. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. 2021.

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.

We consider varieties of linear multioperator algebras, that is, classes of algebras with several multilinear operations satisfying certain identities. To each such a variety one can assign a numerical sequence called a sequence of codimensions. The n-th codimension is equal to the dimension of the vector space of all n-linear operations in the free algebra of the variety. In recent decades, a new approach to such a sequence has appeared based on the fact that the union of the above vector spaces carries the structure of algebraic operad, so that the generating function of the codimension sequence is equal to the generating series of the operad. We show that in general there does not exist an algorithm to decide whether the growth exponent of the codimension sequence of the variety defined by given finite sets of operations and identities is equal to a given rational number. In particular, we solve negatively a recent conjecture by Bremner and Dotsenko by showing that the set of codimension sequences of varieties defined by a bounded number and degrees of operations and identities is infinite. Then we discuss algorithms which in many cases calculate the generating functions of the codimension series in the form of a defining algebraic or differential equation. For a more general class of varieties, these algorithms give upper and lower bounds for the codimensions in terms of generating functions. The upper bound is just a formal power series satisfying an algebraic equation defined effectively by the generators and the identities of the variety. The first stage of an algorithm for the lower bound is the construction of a Groebner basis of the operad. If the Groebner basis happens to be finite and satisfies mild restrictions, a recent theorem by the author and Anton Khoroshkin guarantees that the desired generating function is either algebraic or differential algebraic. We describe algorithms producing such equations. In the case of infinite Groebner basis, these algorithms applied to its finite subsets give lower bounds for the generating function of the codimension sequence.