More details:

Structural Polynomial ≠ 0
© 2001, 2001 Programming in Mathematica by Ville Mattila

Firstly, we form all possible differences of Parikh-vectors of consecutive subwords  u  and  v.
Secondly, we multiply the differences with each other.
If the product is not zero, the word is a-2-free.



We can include one or more variables in the word.
Then we form the product as explained above.
The values of the variables are limited to the current alphabet.
All the values of the variables for which the product is not zero form an a-2-free word.

We can define a function findSuffixStructure that works as follows:

findSuffixStructure["abcd"]         

{-"c"+"d", -"a"-"b"+"c"+"d"}

Let X be a letter variable.
The following shows that the only possibility for "abacabaX"  in  {a,b,c,d}*  
to be a-2-free is that  X"→"d.

struct =
findSuffixStructure["abacabaX"]

{-"a"+"X", -"b"+"X", -"a"+"b"-"c"+"X", -"c"+"X"}

polyn = Times @@ struct

(-"a"+"X") (-"b"+"X") (-"c"+"X") (-"a"+"b"-"c"+"X")

If[(polyn /. "X"→#) =!= 0, "X"→#, {}]& /@ {"a","b","c","d"}//Flatten

{"X"→"d"}

By using findSuffixStructure in a quite obvious way, one can define
findStructure to create the structure of the whole word, or of the
necessary part of it.

Created by Mathematica  (November 2, 2003)