Sparse and slender subsets of monoids.

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic theory of languages and automata (68Q70)

Review text

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.

Recommendations

Cites work

Cited in

(2)

Describes a project that uses

Uses Software

ALGOL 60

This page was built for publication: Sparse and slender subsets of monoids.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2480765)