Avoidability of formulas with two variables
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.
- A generator of morphisms for infinite words
- Avoidability of circular formulas
- Avoidable patterns in strings of symbols
- Binary words avoiding the pattern AABBCABBA
- BLOCKING SETS OF TERMS
- Characterization of some binary words with few squares
- Doubled patterns are 3-avoidable
- Growth problems for avoidable words
- scientific article; zbMATH DE number 1737190 (Why is no real title available?)
- On some interesting ternary formulas
This page was built for publication: Avoidability of formulas with two variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1676792)
