
doi: 10.1007/bf02573122
Let X be a finite alphabet, \(| X| \geq 2\). A word w over X is said to be primitive if \(w=u\) n implies \(u=w\) and \(n=1\). In this paper, properties of sets of primitive words accepted by finite automata are studied. If a given n-state automaton accepts a primitive word at all it accepts a primitive word whose length does not exceed 3(n-1). On the other hand, it accepts infinitely many primitive words if and only if it accepts at least one primitive word whose length is no less than n. In particular, it follows that for a given automaton the questions of whether it accepts any primitive words and whether it accepts infinitely many primitive words are decidable. In the final section of the paper, the authors focus on the following problem: Among those automata with n states accepting only finitely many primitive words, what is the maximal number \(\vartheta_ n\) of primitive words accepted and what is the maximal number \(\eta_ n\) of primitive words which are roots of accepted words. The surprising result is \[ \vartheta_ n = \eta_ n = \begin{cases} 0, & \text{ if \(n=1,\)} \\ 1, & \text{ if \(n=2,\)} \\ | \{x|\quad | x| \leq n-2, x \text{ is primitive}\}|, & \text{ if \(n\geq 3\).}\end{cases} \]
510.mathematics, primitive words, Free semigroups, generators and relations, word problems, Semigroups in automata theory, linguistics, etc., finite alphabet, Formal languages and automata, finite automata, Article
510.mathematics, primitive words, Free semigroups, generators and relations, word problems, Semigroups in automata theory, linguistics, etc., finite alphabet, Formal languages and automata, finite automata, Article
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
