Minimal forbidden subwords
Motivated by a study of similar problems stated for factors of words, we study forbidden subwords of a language or a word. A procedure for obtaining the set of all words avoiding a given set of subwords is presented. On the other hand, an algorithm for computing the set of minimal forbidden subwords for a word is given. The case of a two-letter alphabet appears to be particularly interesting and it is considered separately. (C) 2004 Elsevier B.V. All rights reserved.
subwords automata formal languages combinatorics on words orders of words