×

Maximal bifix codes of degree 3. (English) Zbl 1415.94395

Summary: The construction of thin maximal bifix codes of degree 1 or 2 is clear and simple. In this paper, a class of thin maximal bifix codes of degree 3 which contains all finite maximal bifix codes of degree 3 is investigated. The construction of such codes is determined. It is well known that for any positive integers \(d\) and \(k\), there are finitely many finite maximal bifix codes of degree \(d\) over a \(k\)-letter alphabet. But the enumeration problem is unsolved in general. In this paper, we show that for any positive integer \(k\), there is a bijection from the set of all finite maximal bifix codes of degree 3 over a \(k\)-letter alphabet onto the set of all directed acyclic graphs with \(k\) vertices, and then, the enumeration problem of finite maximal bifix codes of degree 3 is solved.

MSC:

94A45 Prefix, length-variable, comma-free codes
68Q70 Algebraic theory of languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Cambridge University Press, Cambridge (2010) · Zbl 1187.94001
[2] Gilbert, EN; Moore, EF, Variable length binary encodings, Bell Syst. Tech. J., 38, 933-967, (1959)
[3] Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory Languages and Computation, 2nd edn. Addison-Wesley, Reading (2001) · Zbl 0980.68066
[4] Léonard, M, A property of biprefix codes RAIRO inform, Théor. Appl., 22, 311-318, (1988) · Zbl 0648.68080
[5] Liu, Y, Compositions of maximal codes, Theor. Comput. Sci., 411, 228-238, (2010) · Zbl 1187.68297
[6] Liu, Y, Completely simple codes, Semigroup Forum, 85, 417-438, (2012) · Zbl 1259.94039
[7] Liu, Y, Groups and decompositions of codes, Theor. Comput. Sci., 443, 70-81, (2012) · Zbl 1279.68239
[8] Robinson, RW; Harary, F (ed.), Counting labeled acyclic digraphs, 239-273, (1973), New York
[9] Schützenberger, M.-P.:On an Application of semigroup methods to some problems in coding. In: IRE Transactions on Information Theory, IT-2, pp. 47-60 (1956)
[10] Schützenberger, M-P, On a family of submonoids, Publ. Math. Inst. Hungar. Acad. Sci. Ser. A, VI, 381-391, (1961) · Zbl 0125.28502
[11] Schützenberger, M-P, On a special class of recurrent events, Ann. Math. Stat., 32, 1201-1213, (1961) · Zbl 0243.60049
[12] West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)
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.