Image reducing words and subgroups of free groups

✍ Scribed by D.S. Ananichev; A. Cherubini; M.V. Volkov

• Book ID: 104325785
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 253 KB
• Volume: 307
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00093-8

✦ Synopsis

A word w over a ÿnite alphabet is said to be n-collapsing if for an arbitrary ÿnite automaton A = Q; -•-, the inequality |Q • w| 6 |Q| -n holds provided that |Q • u| 6 |Q| -n for some word u (depending on A). We give an algorithm to test whether a word is 2-collapsing. To this aim we associate to every word w a ÿnite family of ÿnitely generated subgroups in ÿnitely generated free groups and prove that the property of being 2-collapsing re ects in the property that each of these subgroups has index at most 2 in the corresponding free group. We also ÿnd a similar characterization for the closely related class of so-called 2-synchronizing words.