Synchronizing and Collapsing Words

A word w over a finite alphabet Σ is called k-collapsing if for each finite deterministic automaton the inequality holds provided that for some word , depending on . A word over the alphabet Σ is called k-synchronizing if it is a reset word for all synchronizing automata with k + 1 states and input alphabet Σ. The aim of this work is to give the motivations of the interest in these words and to provide an overview of some results in this area. Received: May 2007