Sparse and slender subsets of monoids. (Q2480765)

There are generalized the notions of sparse and slender sets for arbitrary monoids and characterized the unambiguous rational sets which are sparse or slender. Let \(M\) be a free monoid. A language \(L\subseteq M\) is called sparse if there is a polynomial \(p(x)\) such that for all \(n\), \(L\) contains at most \(p(n)\) words of length \(n\). Further, \(L\) is called slender if there is a positive integer \(q\) such that for all \(n\), \(L\) contains at most \(q\) words of length \(n\) [see \textit{G. Păun} and \textit{A. Salomaa}, Discrete Appl. Math. 61, No. 3, 257-270 (1995; Zbl 0831.68057)]. Let \(M\) be a monoid. Instead of the length there is considered an arbitrary morphism \(\varphi\colon M\to\mathbb{N}^k\), where \(\mathbb{N}^k\) is the additive monoid of \(k\)-tuples of nonnegative integers. A subset \(S\subseteq M\) is called \(\varphi\)-sparse if there is a polynomial \(p(x_1,\dots,x_k)\) such that for all \((a_1,\dots,a_k)\in\mathbb{N}^k\) the number of elements \(s\in S\) with \(\varphi(s)=(a_1,\dots,a_k)\) is less than \(p(a_1,\dots,a_k)\). Similarly, a subset \(S\subseteq M\) is called \(\varphi\)-slender if there is a positive integer \(q\) such that for all \((a_1,\dots,a_k)\in\mathbb{N}^k\) the number of elements \(s\in S\) with \(\varphi(s)=(a_1,\dots,a_k)\) is at most \(q\). A subset \(S\subseteq M\) is called an `unambiguous multiple loop set', if there exist \(u_1,v_1,\dots,u_n,v_n,u_{n+1}\in M\) such that \(S=u_1v^*_1\cdots u_nv^*_nu_{n+1}\) and, furthermore, \(u_1v^{i_1}_1\cdots u_nv^{i_n}_nu_{n+1}\neq u_1v^{j_1}_1\cdots u_nv^{j_n}_nu_{n+1}\) whenever \((i_1,\dots,i_n)\neq(j_1,\dots,j_n)\). The families of unambiguous rational subsets of \(M\) were defined by \textit{S. Eilenberg} [Automata, languages, and machines, Vol. A, Pure Appl. Math. 58. New York-London: Academic Press (1974; Zbl 0317.94045)]. The main result is the following Theorem. Let \(M\) be a monoid and \(\varphi\colon M\to\mathbb{N}^k\) be a monoid morphism. Let \(S\) be an unambiguous rational set of \(M\). Then \(S\) is \(\varphi\)-sparse if and only if \(S\) is a finite disjoint union of unambiguous multiple loop sets of finite degrees.