Unary Patterns of Size Four with Morphic Permutations

2019/02/05 by Reshadi, Kamellia
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1902.02333

Abstract

We investigate the avoidability of unary patterns of size of four with morphic permutations. More precisely, we show that, for the positive integers i,j,k, the sizes of the alphabets over which a pattern x π^ i (x) π^j(x) π^k(x) is avoidable are an interval of the integers (where x is a word variable and π is a function variable with values in the set of all morphic permutations of the respective alphabets). We also show how to compute a good approximation of this interval. This continues the work of [Manea et al., 2015], where a complete characterisation of the avoidability of cubic patterns with permutations was given.

Related

• Further applications of a power series method for pattern avoidance
• Doubled patterns are 3-avoidable
• On the Best Upper Bound for Permutations Avoiding A Pattern of a Given Length
• Application of entropy compression in pattern avoidance
• Avoidability of formulas with two variables