Image reducing words and subgroups of free groups
A word w over a finite alphabet Sigma is said to be n-collapsing if for an arbitrary finite automaton A =   the inequality \Q . w\ less than or equal to \Q\ - n holds provided that \Q . u\ less than or equal to \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 finite family of finitely generated subgroups in finitely generated free groups and prove that the property of being 2-collapsing reflects in the property that each of these subgroups has index at most 2 in the corresponding free group. We also find a similar characterization for the closely related class of so-called 2-synchronizing words. (C) 2003 Elsevier B.V. All rights reserved.
free groups synchronizing automata compressible automata 2-collapsing words