Recent results on syntactic groups of prefix codes. (Q444391): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Douadi Mihoubi / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20M35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20M05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20M20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 20M30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q70 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6065703 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
free semigroups | |||
Property / zbMATH Keywords: free semigroups / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
finite automata | |||
Property / zbMATH Keywords: finite automata / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
syntactic groups | |||
Property / zbMATH Keywords: syntactic groups / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
prefix codes | |||
Property / zbMATH Keywords: prefix codes / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
finite transformation monoids | |||
Property / zbMATH Keywords: finite transformation monoids / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
maximal subgroups | |||
Property / zbMATH Keywords: maximal subgroups / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1993846758 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the groups of codes with empty kernel. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bifix codes and Sturmian words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3653240 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5509690 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Episturmian words and some constructions of de Luca and Rauzy / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4132170 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms for computing finite semigroups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Return words in Sturmian and episturmian words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3853827 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4341774 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4145882 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3951547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3667090 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On syntactic groups. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4200990 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of some problems from the theory of automata / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5387708 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 14:06, 5 July 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