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

Our Algorithm

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

1. Factoring − if there exist v,w∈ X and v'∈ F(v) such that w⊂ v', then Y = X \ {v}.
2. 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}.
3. Hole Truncation − if there exists w∈ X such that w = x◊ⁿ for some x ∈ W(A), then Y = (X \ {w}) ∪ {x}.
4. Expansion − Y = (X \ {w}) ∪ {w₁,w₂, . . . ,w_n} where {w₁,w₂, . . . ,w_n} is a partial expansion of 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.

Back to the Implementation Page