Avoidability of formulas with two variables
type: Item
instance of: scholarly article
title: Avoidability of formulas with two variables
zbMATH Open document ID: 1374.68359
author: Pascal Ochem
author: Matthieu Rosenfeld
published in: The Electronic Journal of Combinatorics
publication date: 2017-11-10T00:00:00Z
full work available at URL: v24i4p30
review text: Summary: In combinatorics on words, a word \(w\) over an alphabet \(\Sigma\) is said to avoid a pattern \(p\) over an alphabet \(\Delta\) of variables if there is no factor \(f\) of \(w\) such that \(f=h(p)\) where \(h:\Delta^\ast\rightarrow\Sigma^\ast\) is a non-erasing morphism. A pattern \(p\) is said to be \(k\)-avoidable if there exists an infinite word over a \(k\)-letter alphabet that avoids \(p\). We consider the patterns such that at most two variables appear at least twice, or equivalently, the formulas with at most two variables. For each such formula, we determine whether it is \(2\)-avoidable, and if it is \(2\)-avoidable, we determine whether it is avoided by exponentially many binary words.
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6805095
zbMATH Keywords: word
zbMATH Keywords: pattern avoidance
MaRDI profile type: Publication
cites work: Characterization of some binary words with few squares
cites work: Growth problems for avoidable words
cites work: Avoidable patterns in strings of symbols
cites work: Avoidability of circular formulas
cites work: A generalization of repetition threshold
cites work: Q4529547
cites work: A generator of morphisms for infinite words
cites work: Binary words avoiding the pattern AABBCABBA
cites work: Doubled patterns are 3-avoidable
cites work: On some interesting ternary formulas
cites work: BLOCKING SETS OF TERMS
description: scientific article; zbMATH DE number 6805095