Avoidability of circular formulas

Guilhem Gamard; Pascal Ochem; Gwenaël Richomme; Patrice Séébold

paper

Avoidability of circular formulas

arXiv:1610.04439

Abstract

Clark has defined the notion of $n$ -avoidance basis which contains the avoidable formulas with at most $n$ variables that are closest to be unavoidable in some sense. The family $C_{i}$ of circular formulas is such that $C_{1} = AA$ , $C_{2} = A B A . B A B$ , $C_{3} = A B C A . B C A B . C A B C$ and so on. For every $i \leq n$ , the $n$ -avoidance basis contains $C_{i}$ . Clark showed that the avoidability index of every circular formula and of every formula in the $3$ -avoidance basis (and thus of every avoidable formula containing at most 3 variables) is at most 4. We determine exactly the avoidability index of these formulas.

References in corpus (1)

Avoidability of formulas with two variables