Each regular code is included in a maximal regular code. (English) Zbl 0609.68053

It is proved here that each regular code is included in a maximal regular code. Other concepts of codes related to maximality are involved. The main result solves a long standing open problem in the theory of formal languages and combinatorial semigroup theory.
Reviewer: T.Harju


68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
Full Text: DOI EuDML


[1] J. BERSTEL, D. PERRIN and M. P. SCHUTZENBERGER, The Theory of Codes(to appear).
[2] S. EILENBERG, Automata, Languages and Machines, Vol. A, 1974, Academic Press, New York and London. Zbl0317.94045 MR530382 · Zbl 0317.94045
[3] W. FELLER, An Introduction to Probability Theory and its Applications, Vol. 1, 1950, J. Wiley. Zbl0039.13201 MR38583 · Zbl 0039.13201
[4] D. Ed.PERRIN, Theorie des codes, L.I.T.P. Publication, Paris, 1979. Zbl0628.94001 · Zbl 0628.94001
[5] D. PERRIN, Completing Biprefix Codes, Lecture Notes in Computer Science, Vol. 140, 1982, pp. 397-406. Zbl0485.68075 MR675474 · Zbl 0485.68075
[6] D. PERRIN, Séries formelles et combinatoire du monoide libre, in J. Berstel Ed., Series Formelles, L.I.T.P., Paris, 1977.
[7] A. RESTIVO, On Codes Having no Finite Completions, in Automata, Languages and Programming, S. MICHAELSON Ed., Edinburgh University Press, 1976, pp. 38-44. MR498922
[8] A. SALOMAA, Formal Languages, Academic Press, London, New York, 1973. Zbl0262.68025 MR438755 · Zbl 0262.68025
[9] M. P. SCHUTZENBERGER, Une théorie algébrique du codage, Seminaire Dubreuil-Pisot, année 55-56, exp. No. 15, Inst. Henri-Poincaré, Paris, 1956. MR75169
[10] M. P. SCHUTZENBERGER and R. S. MARCUS, Full Decodable Code Word Sets, I.R.E. Trans on Inf. Theroy, Vol. 5, 1959, pp. 13-15. MR130045
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.