This is the formulae calculator. Give it a formula and it will tell you what it can about the avoidability index of this formula. Accepted formulae are formulas of length at most 25 on the alphabet {A, B, C, D, E, F}.

It should give you the avoidability index for any binary formula or ternary pattern. If you can give better bounds and have a reference you can let me know (the dictionnary is not exhaustive yet).

Enter a formula:You can try with: ABED.BEA.ABED.AEBD, ABACBABDB, AA or BAC.ABA.ACA.

## ABED.BEA.ABED.AEBD

Removing any fragment that is a factor of another fragment from ABED.BEA.ABED.AEBD gives the formula : BEA.ABED.AEBDThe input formula is equivalent to F = ABC.CABD.CBAD

The mirror of F is : ABC.DBCA.DCBA

The formula is on 4 variables. We will check if it divides the following Zimin word : ABACABADABACABA.

**F is avoidable**because the Zimin word does not contain any occurence of F.

F is divisible by AB.AC.BA.CA.CB. The occurence is given by the morphism:

A -> B

B -> A

C -> C

AB.AC.BA.CA.CB is 4 avoidable because it is "locked" [4].

**Thus the avoidability index of F is at most 4.**

ABCA.ACBA is divisible by F. The occurence is given by the morphism:

A -> C

B -> B

C -> A

D -> A

ABCA.ACBA is not avoidable over 3 letters. It can be showed by exhaustive search (it helps to use that a reccurent word avoiding this formula also avoids AA).

**Thus the avoidability index of F is at least 4.**

**λ(F) = 4**

## Definitions

### Words

An alphabet is a finite set. A word is a sequence over an alphabet. We denote by Σ^{*} the set of finite words over the alphabet Σ. A factor of a word is a contiguous subsequence of this word.

For two alphabet Σ and Σ_{2}, a function h: Σ^{*} -> Σ_{2}^{*} is a morphism if for any u,v from Σ^{*}, h(uv)=h(u)h(v).
Thus a morphism h is fully characterised by the images of the elements of Σ by h. For instance, let h:{a,b}^{*} ->{a,b}^{*} be the morphism such that h(a)=ab and h(b)=ba, then h(abba)=abbabaab

### Formula

A formula is a set of words over an alphabet of variables. For a formula F={p_{1},p_{2},..., p_{n}}, we often write F=p_{1}.p_{2}... .p_{n} and we call the p_{i} the fragment of F.
A word w over a second alphabet Σ contains an occurrence of F if there exists a non-erasing morphism h such that for all i, h(p_{i}) is a factor of w.
A word that does not contain any realization of F is said to avoid F.

### Avoidability

A formula F is avoidable (resp. k-avoidable) if there is an infinite word over a finite alphabet (resp. an alphabet of size k) that avoids F. The avoidability index of a formula F, denoted by λ(F), is the smallest integer k such that F is k-avoidable (or infinite if F is not avoidable).

### Divisibility

A formula F is divisible by another formula G if there is a non-erasing morphism h such that the image by h of any fragment of G is a factor of a fragment of F. It is not hard to show the two following properties:

- If F is divisible by G and G is divisible by H then F is divisible by H (that is, the relation "is divisible by" is transitive).
- If F is divisible by G, then any word that contains an occurrence of F contains an occurrence of G (which implies that the avoidability index of F is smaller than the avoidability index of G).

## The algorithm

The algorithm that is applyed to a formula is the following:- Get the formula in a form as simple as possible. This is done by removing any isolated letters and replacing it by a "." and removing any fragment that is factor of another fragment. If we reach the empty formula by this process, we know that the formula is not avoidable.
- Compare F to the Zimin word over the same number of variables to know if the formula is avoidable.
- Check if the formula contains a doubled pattern as a factor. If it is the case, the formula is 3-avoidable.
- Check if the the formula is divisbile by any formula that is known to be k-avoidable (for different k). If it is divisible by such a formula then it is itself k-avoidable for the same k.
- Check if any formula that is known to be k-unavoidable is divisibile by the the formula (for different k). If yes, it is itself k-unavoidable for the same k.

## References

**Avoidability of formulas with two variables**, P. Ochem and M. Rosenfeld.

In The Electronic Journal of Combinatorics (html)**Doubled patterns are 3-avoidable.**P. Ochem.

Electron. J. Comb. 23(1) (2016), #P1.19.**Avoidability of circular formulas.**G. Gamard, P. Ochem, G. Richomme, and P. Seebold.

Theoretical Computer Science. To appear.**Growth problems for avoidable words..**K. A. Baker, G. F. McNulty, and W. Taylor.

Theoretical Computer Science, 69(3):319–345, 1989.