Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875514 | Theoretical Computer Science | 2018 | 4 Pages |
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 Ci of circular formulas is such that C1=AA, C2=ABA.BAB, C3=ABCA.BCAB.CABC and so on. For every i⩽n, the n-avoidance basis contains Ci. 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Guilhem Gamard, Pascal Ochem, Gwenaël Richomme, Patrice Séébold,