Recent results on syntactic groups of prefix codes. (Q444391): Difference between revisions

This important and nice expository paper with many examples illustrating the results, is about the non trivial problem of computing the maximal groups contained in finite transformation monoids, where a transformation monoid on a finite set \(Q\) is a monoid of all partial maps from \(Q\) to \(Q\) with composition of functions as product and the identity map on \(Q\) as a neutral element. The transformation monoids considered here arise as the transition monoid \(M\) of the minimal automaton recognizing the free monoid generated by a prefix code \(X\). The maximal groups contained in \(M\) are called the syntactic groups of \(X\). Based upon the notion of holonomy groups of a finite transformation monoid \(M\), which are shown to be isomorphic with the maximal groups contained in \(M\), the authors give two alternative methods for computing the set of generators of these groups. The first one is to use the Schützenberger representation of a finite transformation monoid and the second is using the notion of fundamental groups of graph. Using these technical methods, the authors give a description of two recent results on syntactic groups of prefix codes. The first new result, which is an improvement of several previous ones due to Schützenberger and to part of the authors of this paper, states that any transitive permutation group \(G\) of degree \(d\) and rank \(k\) is a syntactic group of a bifix code with \((k-1)d+1\) elements. The second result describes a class of prefix codes such that all their syntactic groups are cyclic.