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

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