Growth functions, rewriting systems, and the Euler characteristic (Q1922297): Difference between revisions

Let \(L\) be a language, i.e. a set of words in the finite alphabet \(X\). Suppose that every subword of any word from \(L\) also belongs \(L\). Then \(L\) is uniquely determined by the set \(U\) consisting of the set of words that do not belongs themselves to \(L\), but every their subwords belong \(L\). Namely, knowing \(U\), one can determine \(L\) as a basis for monomial algebra \(A=\langle X|U\rangle\). A standard formula for calculating the generating function \(H_L\) of the number of words in \(L\) (\(H_L=P_A(-1,t)\), where \(P_A\) is Poincaré series) is proved directly in terms of so-called \(n\)-chains (minimal words, that contains \(n\) consequently overlapping subwords from \(U\) such that only consequent subwords overlap). Several applications of this formula are shown: analogous of the Golod-Shafarevich inequality; test for checking that a term rewriting system is confluent; growth of semigroups, groups and graded algebras; topological entropy of symbolic systems and connection with the Euler characteristic.