zbMATH — the first resource for mathematics

On noncounting regular classes. (English) Zbl 0780.68084
Summary: Let \(A^*\) be the free monoid of base \(A\) and \(n\) a fixed positive integer. For any word \(w\in A^*\) we consider the set \([w]_ n\) of all the words which are equivalent to \(w\) modulus the congruence \(\theta_ n\) generated by the relation \(x^ n\sim x^{n+1}\), where \(x\) is any word of \(A^*\). The main result of the paper is that if \(n>4\) then for any word \(w\in A^*\) the congruence class \([w]_ n\) is a regular language. We also prove that the word problem for the quotient monoid \(M_ n=A^*/\theta_ n\) is recursively solvable.

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
Full Text: DOI
[1] Book, R.V., Thue systems and the church-rosser property: replacement systems, specification of formal languages, and presentations of monoids, (), 1-38
[2] Brzozowski, J.; Culik, K.; Gabrielian, A., Classification of noncounting events, J. comput. system sci., 5, 41-53, (1971) · Zbl 0241.94050
[3] Brzozowski, J., Open problems about regular languages, (), 23-45
[4] Ehrenfeucht, A.; Rozenberg, G., On regularity of languages generated by copying systems, Discrete appl. math., 8, 313-317, (1984) · Zbl 0549.68075
[5] Eilenberg, S.; Eilenberg, S., Automata, languages and machines, Automata, languages and machines, vol B, (1976), Academic Press · Zbl 0359.94067
[6] Fine, N.J.; Wilf, M.S., Uniqueness theorem for periodic functions, Proc. amer. math. soc., 16, 109-114, (1965) · Zbl 0131.30203
[7] Green, J.A.; Rees, D., On semigroups in which xr=x, Proc. Cambridge philos. soc., 48, 35-40, (1952) · Zbl 0046.01903
[8] Hotzel, E., On finiteness conditions in semigroups, J. algebra, 60, 352-370, (1979) · Zbl 0421.20032
[9] Lallement, G., Semigroups and combinatorial applications, (1979), John Wiley New York · Zbl 0421.20025
[10] Lothaire, M., Combinatorics on words, (1983), Addison-Wesley Reading, MA · Zbl 0514.20045
[11] de Luca, A.; Varricchio, S., A finiteness condition for semigroups generalizing a theorem of hotzel, J. algebra, 136, 60-72, (1991) · Zbl 0741.20038
[12] Theoret. Comput. Sci. to appear
[13] McNaughton, R.; Papert, S., Counter-free automata, (1971), The M.I.T. Press Cambridge, MA · Zbl 0232.94024
[14] Simon, I., Notes on noncounting languages of order, 2, (1970), manuscript
[15] Thue, A., Über die gegenseitige lage gleicher teile gewisser zeichenreihen, Videnskabsselskabets skrifter, 1, (1912), Mat.-Nat. K.1., Christiania · JFM 44.0462.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.