×

zbMATH — the first resource for mathematics

Recent results on syntactic groups of prefix codes. (English) Zbl 1272.20062
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.

MSC:
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
20M20 Semigroups of transformations, relations, partitions, etc.
20M30 Representation of semigroups; actions of semigroups on sets
68R15 Combinatorics on words
68Q70 Algebraic theory of languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berstel, Jean; De Felice, Clelia; Perrin, Dominique; Rindone, Giuseppina, On the groups of codes with empty kernel, Semigroup forum, 80, 3, 351-374, (2010) · Zbl 1202.20071
[2] Jean Berstel, Clelia De Felice, Dominique Perrin, Christophe Reutenauer, and Giuseppina Rindone, Bifix codes and Sturmian words, 2011. http://arXiv.org/abs/1011.5369. · Zbl 1263.68121
[3] Berstel, Jean; Perrin, Dominique; Reutenauer, Christophe, Codes and automata, (2009), Cambridge University Press · Zbl 1187.94001
[4] Černý, Ján, Poznámka \(k\) homogénnym experimentom \(s\) konečnými automatmi, Mat.-fyz. cas. SAV., 14, 208-215, (1964)
[5] Droubay, Xavier; Justin, Jacques; Pirillo, Giuseppe, Episturmian words and some constructions of de luca and Rauzy, Theoret. comput. sci., 255, 1-2, 539-553, (2001) · Zbl 0981.68126
[6] Eilenberg, Samuel, Automata, languages, and machines. vol. B, (1976), Academic Press New York, [Harcourt Brace Jovanovich Publishers] · Zbl 0359.94067
[7] Froidure, Véronique; Pin, Jean-Eric, Algorithms for computing finite semigroups, (), 112-126 · Zbl 0876.20034
[8] Justin, Jacques; Vuillon, Laurent, Return words in sturmian and Episturmian words, Theor. inform. appl., 34, 5, 343-356, (2000) · Zbl 0987.68055
[9] Lallement, Gérard, Semigroups and combinatorial applications, (1979), John Wiley & Sons New York, Chichester, Brisbane, Pure and Applied Mathematics, A Wiley-Interscience Publication · Zbl 0421.20025
[10] Lothaire, M., Combinatorics on words, (1997), Cambridge University Press, (First ed. 1983) · Zbl 0874.20040
[11] Lothaire, M., Algebraic combinatorics on words, (2002), Cambridge University Press · Zbl 1001.68093
[12] Lyndon, Roger C.; Schupp, Paul E., Combinatorial group theory, (1977), Springer-Verlag · Zbl 0368.20023
[13] Michael, W.; Holcombe, L., Algebraic automata theory, (1982), Cambridge University Press · Zbl 0489.68046
[14] Perrin, Dominique, Sur LES groupes dans LES monoïdes finis, (), 27-36 · Zbl 0518.20063
[15] Perrin, Dominique; Rindone, Giuseppina, On syntactic groups, Bull. belg. math. soc. Simon stevin, 10, suppl, 749-759, (2003) · Zbl 1069.20062
[16] Schützenberger, Marcel-Paul, A property of finitely generated submonoids of free monoids, (), 545-576
[17] Stern, Jacques, Complexity of some problems from the theory of automata, Inf. control, 66, 3, 163-176, (1985) · Zbl 0603.68059
[18] Trakhtman, Avraham, The černý conjecture for aperiodic automata, Discrete math. theor. comput. sci., 9, 2, (2007) · Zbl 1152.68461
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.