×

Some free submonoids of the free monoid of prefix codes. (English) Zbl 0299.94005

Summary: It is known that the class of all prefix codes \(P(X)\) over a finite alphabet \(X\) forms a free monoid. In this paper we show that the following eight subclasses of \(P(X)\) all form free submonolds of \(P(X)\): noncounting prefix codes, right noncounting prefix codes, biffix codes, finite prefix codes, maximal prefix codes, noncounting maximal prefix codes, right noncounting maximal prefix codes and regular prefix codes.

MSC:

94A45 Prefix, length-variable, comma-free codes
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] McNaughton, R. and S. Papert,Counter-Free Automata, MIT Press (1971).
[2] Perrin, D.,Le Langage Engendré par un Code Préfixe et son Monoie Syntaxique, Thèse (1970).
[3] Perrin, D.,Codes Conjugués, Information and Control 20 (1972), 222–231. · Zbl 0254.94015 · doi:10.1016/S0019-9958(72)90406-8
[4] Rabin, M. O. and D. Scott,Finite Automata and Their Decision Problems, IBM J. Res. Dev. 3, 2 (April 1959), 114–125. · Zbl 0158.25404 · doi:10.1147/rd.32.0114
[5] Shyr, H. J.,Codes and Factor Theorems for Subsets of a Free Monoid, Utilitas Mathematica 3 (1973), 153–159. · Zbl 0261.94010
[6] Shyr, H. J. and G. Thierrin,Left Noncounting Languages, To appear in International Journal of Computer and Information Sciences. · Zbl 0297.68060
[7] Schützenberger, M. P.,Une Théorie Algébrique du Codage, Séminare Dubreil-Pisot, 1955/1956
[8] Schützenberger, M. P.,Sur Certains Sousdemi-Groupes Qui Interviennent dans un Problème de Mathématiques Appliquées, Publ. Sci. Univ. d’Alger Ser. A6 (1959), 85–90.
[9] Schützenberger, M. P.,On Synchronizing Prefix Codes, Information and Control 11 (1967), 396–401. · Zbl 0157.25905 · doi:10.1016/S0019-9958(67)90620-1
[10] Tilson, B.,The Intersection of Free Monoids of a Free Monoid is Free, Semigroup Forum 4 (1972), 345–350. · Zbl 0261.20060 · doi:10.1007/BF02570808
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.