Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.tcs.2017.11.014 | Theoretical Computer Science |
Keywords | DocType | Volume |
Words,Pattern avoidance | Journal | 726 |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.40 |
References | Authors | |
3 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guilhem Gamard | 1 | 8 | 4.03 |
| Pascal Ochem | 2 | 258 | 36.91 |
| Gwénaël Richomme | 3 | 136 | 18.10 |
| Patrice Séébold | 4 | 140 | 27.23 |