AvoidingPatternsUnderInvolution < CoWiki

Patterns can be generalized by adding functional dependencies between variables.  Here, we consider involutions &thetasym;, that is, &thetasym;(&thetasym;(_a_))&nbsp;=&nbsp;<i>a</i> for all letters _a_, and their morphic/antimorphic extensions on words, that is, &thetasym;(_uv_)&nbsp;=&nbsp;&thetasym;(_u_)&thetasym;(_v_) for the morphic and &thetasym;(_uv_)&nbsp;=&nbsp;&thetasym;(_v_)&thetasym;(_u_) for the antimorphic case. A pattern _p_ in this setting consists now of (word) variables and function variables and it is avoided in some infinite word *w* if there exists no substitution of (word) variables by words and function variables by involutions for _p_ such that the result is a factor of *w*. The morphic and antimorphic cases are usually considered separately.

The avoidance indices of all unary patterns under involution are known. See
<div style="padding-left: 30px;">B. Bischoff, J. Currie, D. Nowotka, _Unary Patterns With Involution_, (reference to be completed).</div>

Let _p_ be a pattern consisting of only one (word) variable and at most one function variable. Then for both the morphic and antimorphic case _p_ is
   * avoidable over three letters, if _p_ is of length 3 and not in {&alpha;&alpha;&alpha;, &thetasym;(&alpha;)&thetasym;(&alpha;)&thetasym;(&alpha;)},
   * unavoidable, if _p_ is in {&alpha;, &thetasym;(&alpha;), &alpha;&thetasym;(&alpha;), &thetasym;(&alpha;)&alpha;}, and
   * avoidable over two letters otherwise.


-- Main.DirkNowotka - 12 Mar 2012
This topic: CoWiki > WebHome > Avoidance > AvoidingPatternsUnderInvolution
Topic revision: r1 - 2012-03-12 - DirkNowotka