On the degree of finite maximal biprefix codes (Q1322583): Difference between revisions

A biprefix code is a set of words \(X\) on an alphabet \(A\) such that for every pair \(x,x'\in X\), \(x\) is a prefix or a suffix of \(x'\) iff \(x= x'\). A code \(X\) is maximal if there is no code \(Y\) which contains strictly \(X\) [see, \textit{J. Berstel} and \textit{D. Perrin}, Theory of codes, Pure Appl. Math. 117 (1985; Zbl 0587.68066)]. The degree of a finite maximal biprefix code has several equivalent definitions. In this paper the author gives a method for the determination of the above degree, expressing it in the form of average length of words in a biprefix code. He shows that the degree which is also the number of encodings of a bi-infinite word using a finite maximal biprefix code does not depend on the word.