Article ID Journal Published Year Pages File Type
6875514 Theoretical Computer Science 2018 4 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,