Recent results on syntactic groups of prefix codes. (Q444391): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:16, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Recent results on syntactic groups of prefix codes. |
scientific article |
Statements
Recent results on syntactic groups of prefix codes. (English)
0 references
14 August 2012
0 references
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.
0 references
free semigroups
0 references
finite automata
0 references
syntactic groups
0 references
prefix codes
0 references
finite transformation monoids
0 references
maximal subgroups
0 references