Matthieu Rosenfeld

Formulae calculator

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.

ABACBABDB

Removing any isolated letter and any empty fragment from ABACBABDB gives the formula : ABA.BAB.B
Removing any fragment that is a factor of another fragment from ABA.BAB.B gives the formula : ABA.BAB
The input formula is equivalent to F = ABA.BAB
The mirror of F is : ABA.BAB
The formula is on 2 variables. We will check if it divides the following Zimin word : ABA.
F is avoidable because the Zimin word does not contain any occurence of F.

F is divisible by ABA.BAB. The occurence is given by the morphism:
A -> B
B -> A

ABA.BAB is avoided by h(w) where w is the fixed point of a->ab, b->ac, c->dc, d->db and h(a)=aab, h(b)=bc, h(c)=ccb, h(d)=ba.
Thus the avoidability index of F is at most 3.

AAB.ABA.ABB.BBA.BAB.BAA is divisible by F. The occurence is given by the morphism:
A -> B
B -> A

AAB.ABA.ABB.BBA.BAB.BAA is not avoidable over the binary alphabet (the longest binary word avoiding this formula has length 23). [1]
Thus the avoidability index of F is at least 3.

λ(F) = 3

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={p1,p2,..., pn}, we often write F=p1.p2... .pn and we call the pi 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(pi) 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:

The algorithm

The algorithm that is applyed to a formula is the following:
  1. 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.
  2. Compare F to the Zimin word over the same number of variables to know if the formula is avoidable.
  3. Check if the formula contains a doubled pattern as a factor. If it is the case, the formula is 3-avoidable.
  4. 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.
  5. 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

  1. Avoidability of formulas with two variables, P. Ochem and M. Rosenfeld.
    In The Electronic Journal of Combinatorics (html)
  2. Doubled patterns are 3-avoidable. P. Ochem.
    Electron. J. Comb. 23(1) (2016), #P1.19.
  3. Avoidability of circular formulas. G. Gamard, P. Ochem, G. Richomme, and P. Seebold.
    Theoretical Computer Science. To appear.
  4. Growth problems for avoidable words.. K. A. Baker, G. F. McNulty, and W. Taylor.
    Theoretical Computer Science, 69(3):319–345, 1989.