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 wv', 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 vzb, then Y = (X \ {w}) ∪ {x}.
  3. Hole Truncation − if there exists w∈ X such that w = x◊n for some x ∈ W(A), then Y = (X \ {w}) ∪ {x}.
  4. Expansion − Y = (X \ {w}) ∪ {w1,w2, . . . ,wn} where {w1,w2, . . . ,wn} 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