Factorization forests of finite height. (English) Zbl 0693.68044

We introduce factorization forests. It is shown that the vertex set of a dense factorization forest of finite height satisfies a bounded gap Ramsey-type property of words. The main result is that every morphism from a free semigroup to a finite semigroup S admits a Ramseyan factorization forest of height at most \(9| S|\). Technique for constructing factorization forests are developed.
Reviewer: Imre Simon


68Q45 Formal languages and automata
05A10 Factorials, binomial coefficients, combinatorial functions
68R99 Discrete mathematics in relation to computer science
Full Text: DOI


[1] Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 1022.94506
[2] Brown, T. C., Van der Waerden’s theorem on arithmetic progressions, Notices Amer. Math. Soc., 16, 245 (1969)
[3] Brown, T. C., An interesting combinatorial method in the theory of locally finite semigroups, Pacific J. Math., 36, 285-289 (1971) · Zbl 0211.33504
[4] Furstenberg, H., Recurrence in Ergodic Theory and Combinatorial Number Theory (1981), Princeton University Press: Princeton University Press Princeton · Zbl 0459.28023
[5] Hashiguchi, K., Limitedness theorem on finite automata with distance functions, J. Comput. System Sci., 24, 233-244 (1982) · Zbl 0513.68051
[6] Hashiguchi, K., Improved limitedness theorems on finite automata with distance functions (1986), manuscript
[7] Howie, J. M., An Introduction to Semigroup Theory (1976), Academic Press: Academic Press London · Zbl 0355.20056
[8] Jacob, G., Un théorème de factorisation des produits d’endomorphismes de \(K^N\), J. Algebra, 63, 389-412 (1980) · Zbl 0441.16002
[9] Justin, J., Généralisation du théorème de van der Waerden sur les semi-groupes répétitifs, J. Combin. Theory Ser. A, 12, 357-367 (1972) · Zbl 0248.05003
[10] Justin, J.; Pirillo, G., Two combinatorial properties of partitions of the free semigroup into finitely many parts, Discrete Math., 52, 299-303 (1984) · Zbl 0555.05005
[11] Justin, J.; Pirillo, G., On a natural extension of Jacob’s ranks, J. Combin. Theory Ser. A, 43, 205-218 (1986) · Zbl 0659.06015
[12] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[13] Simon, I., Word Ramsey theorems, (Bollobás, B., Graph Theory and Combinatorics (1984), Academic Press: Academic Press London) · Zbl 0548.20043
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.