On factorization forests of finite height

✍ Scribed by Jérémie Chalopin; Hing Leung

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 319 KB
• Volume: 310
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00344-x

✦ Synopsis

Simon (Theoret. Comput. Sci. 72 (1990)

has proved that every morphism from a free semigroup to a ÿnite semigroup S admits a Ramseyan factorization forest of height at most 9|S|. In this paper, we prove the same result of Simon with an improved bound of 7|S|. We provide a simple algorithm for constructing a factorization forest. In addition, we show that the algorithm cannot be improved signiÿcantly. We give examples of semigroup morphism such that any Ramseyan factorization forest for the morphism would require a height not less than |S|.