Finite automata and pattern avoidance in words

Petter Brändén, Toufik Mansour

We say that a word $w$ on a totally ordered alphabet avoids the word $v$ if there are no subsequences in $w$ order-equivalent to $v$. In this paper we suggest a new approach to the…