Patterns can be generalized by adding functional dependencies between variables. Here, we consider involutions ϑ, that is, ϑ(ϑ(a)) = a for all letters a, and their morphic/antimorphic extensions on words, that is, ϑ(uv) = ϑ(u)ϑ(v) for the morphic and ϑ(uv) = ϑ(v)ϑ(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

B. Bischoff, J. Currie, D. Nowotka, Unary Patterns With Involution, (reference to be completed).

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 {ααα, ϑ(α)ϑ(α)ϑ(α)},
  • unavoidable, if p is in {α, ϑ(α), αϑ(α), ϑ(α)α}, and
  • avoidable over two letters otherwise.

-- DirkNowotka - 12 Mar 2012

Topic revision: r1 - 2012-03-12 - DirkNowotka
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback