AvoidingPatternsUnderInvolution < CoWiki

CoWiki Web>Avoidance>AvoidingPatternsUnderInvolution (2012-03-12, DirkNowotka) (raw view)

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

Topic revision: r1 - 2012-03-12 - DirkNowotka

CoWiki

CoWiki Web
CoWiki Web Home
Changes
Index
Search

Webs
- AIMAS
- CERAS
- CF
- CoWiki
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW

My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu Main.HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images

Edit