pith. sign in

arxiv: 1610.04439 · v1 · pith:QIE5ZM2Anew · submitted 2016-10-14 · 💻 cs.DM

Avoidability of circular formulas

classification 💻 cs.DM
keywords everyformulasavoidabilityavoidancebasiscircularformulaavoidable
0
0 comments X
read the original 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=ABA.BAB$, $C_3=ABCA.BCAB.CABC$ and so on. For every $i\le 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.