Seminario Teoría de Grupos ICMAT-UAM

Viernes 10 de Mayo, 10:30, Aula Gris 1, ICMAT.

Ponente: Dmitri Piontkovski

Titulo: Algebras and formal languages

Resumen:

 Given an infinite algebraic system or a linear algebra, the set of all its elements or its linear basis is often in one-to-one correspondence with a formal language of well-known class. This gives a way to calculate the corresponding generating function (such as the Hilbert series of a graded of a filtered algebra). For example, a linear basis of an associative algebra defined by a finite number of monomial relations forms a regular language, as well as the set of nonzero words in a finitely presented monomial semigroup. It follows that the Hilbert series of such an algebra a rational function (Govorov's theorem). A natural more general class with rational Hilbert series  is the class of automaton algebras introduced by Ufnarovski. By definition, the  normal basis of such an algebra forms a regular language.

 In the first part of the talk the following question by Ufnarovski will be considered: are all finitely presented graded associative algebras of linear growth are automaton? We will see that this conjecture (as well as the analogues conjecture for finitely presented monoids) is closely connected with the structure of regular languages of linear growth (slender languages) as well as with the dynamical Mordell--Lang conjecture about orbits of automorphisms of algebraic varieties.

 In the second part, we will discuss examples of finitely presented associative algebras and monoids (discovered in co-operation with La Scala and Tiwari), for which the monomial bases of the ideals of relations form unambiguous context-free languages. Under mild restrictions, the Hilbert series occurs to be algebraic functions. We will discuss also possible obstructions for calculation of growth of such algebras.

 In the third part, we discuss more general (linear) algebras defined over non-symmetric operads with finite Groebner bases (such as the operad of associative algebras and its more general versions).  We show that a linear algebra defined by a finite set of monomial relations has a monomial basis which forms a deterministic context-free language. It follows that the generating function of this language is again an algebraic function.