If the special characters on this page do not load properly, please use Mozilla's Firefox browser to view this page.

Back to the Implementation Page

Let *X, Y *⊂ *W(A)*. The following operations preserve avoidability:

- Factoring − if there exist
*v,w∈ X*and*v'∈ F(v)*such that*w*⊂*v'*, then*Y = X*\ {*v*}. - Prefix-Suffix − if there exists
*w = xa∈ X*with*a∈A*such that for every*b∈ A*there exists a factorization of*x, x = yz*, and a word*v∈ X*with*v*⊂*zb*, then*Y = (X*\ {*w*}) ∪ {*x*}. - Hole Truncation − if there exists
*w∈ X*such that*w = x◊*for some^{n}*x ∈ W(A)*, then*Y = (X*\ {*w*}) ∪ {*x*}. - Expansion −
*Y = (X*\ {*w*}*)*∪ {*w*} where {_{1},w_{2}, . . . ,w_{n}*w*} is a partial expansion of_{1},w_{2}, . . . ,w_{n}*w ∈ X*. For the purposes of implementation, we only perform expansions if there exists*w = xa∈ X*with*a∈A*such that for every*b ∈ A*there is some factorization of*x, x = yz*, and a word*v ∈ X*where*zb ↑ v*, and choose the positions to expand such that a prefix-suffix operation might become valid.

Our algorithm takes a given set of partial words *X*, and performs these operations until none are valid. If *X* has been reduced to the set {*ε*}, then *X* is unavoidable, else it is avoidable.