Image reducing words and subgroups of fr
β
D.S. Ananichev; A. Cherubini; M.V. Volkov
π
Article
π
2003
π
Elsevier Science
π
English
β 253 KB
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 ev