# Questions tagged [combinatorics-on-words]

A branch of combinatorics that focuses on the study of words and formal languages

95 questions
Filter by
Sorted by
Tagged with
1 vote
96 views

### Is there an efficient generalized algorithm to generate a set of binary words satisfying a particular cross-correlation property?

In this question, the term “word” implies a binary word, i.e. a sequence of bits. Let $W(w)$ denote the number of non-zero bits in a word $w$. Assuming that $l \geq 2$ is even, an $l$-bit word $w$ is ...
248 views

### Is there an efficient generalized algorithm to find at least one binary word with the maximum rotational imbalance and the full $\{0, 1\}$-balance?

Assuming that $x$ is a sequence of $l$ bits (i.e. a binary word of length $l$) and $0 \le m < l$, let $R(x, m)$ denote the result of the left bitwise rotation (i.e. the left circular shift) of $x$ ...
236 views

### Words with critical exponent $< \frac 73$

In a comment made by Gjergji Zaimi to this older question, it is conjectured that $\frac 73$ is the threshold separating countability and uncountability of the sets of infinite binary words having a ...
68 views

### Algorithms to factorize words into product of powers

I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references. Let $A$ be a finite set of symbols, are there ...
The Oldenburger-Kolakoski sequence, $OK$, is the unique sequence of $1$s and $2$s that starts with $1$ and is its own runlength sequence: $$OK = (1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,\ldots).... 5 votes 0 answers 106 views ### Computability of the "free envelope rank" of an endomorphism of a free group Let F be a free group freely generated by the finite set S and \sigma\colon F\to F be a group morphism. We define the free envelope rank of \sigma, written r(\sigma), as the smallest k for ... 2 votes 1 answer 320 views ### Is the number of words finite, when you don't know how to count? This question is inspired by this one: Can you do math without knowing how to count? Let M_2 be the set of words constructed by concatenation of the letters a_1 and a_2, with : (*) : for any x ... 1 vote 0 answers 98 views ### Hausdorff dimension and critical exponent of words What is the Hausdorff dimension of the subset S_c \subset [0,1] of points such that the critical exponent of their binary expansion is c? It's clear that \dim_H S_{\infty}=1, but what can be ... 2 votes 1 answer 98 views ### What is the cardinality of the set of Dyck natural numbers of semilength k? In arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I show that there is a 1:1 correspondence between \mathbb{N} = \{0,1,2,3,4,\ldots\} and \mathcal{D}_{r_{\... -1 votes 1 answer 117 views ### Prove using Dyck naturals: for n \in \mathbb{N}_{+} and big enough k \in \mathbb{N}_{+}, p_{k-1} < \cdots < np_{k-a_{n}} (a is A073093) While conducting research in connection with arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I noticed certain interesting patterns, one of which inspired the ... 1 vote 0 answers 64 views ### Words with finite critical exponent Let \mathcal{A} be a finite set. Is there a nice characterization of the subset of S\subset \mathcal{A}^\omega such that every w\in S has finite critical exponent? Of course S has measure zero ... 12 votes 1 answer 364 views ### Subwords of the infinite Fibonacci word Let W = 01001010010010 \ldots be the infinite Fibonacci word, A003849 in the OEIS. Let B(m) be the set of m+1 subwords of W that have length m, and for each such subword u, let p(u) be ... 2 votes 1 answer 110 views ### Binary words starting with arbitrarily long squares What is the measure of the following set of infinite binary words? S=\{w\in\{0,1\}^\omega\ \text{such that},\ \text{for every}\ N\in\mathbb{N},\, w\ \text{has a prefix of the form}\ pp\ \text{with}\ ... 32 votes 0 answers 2k views ### The easily bored sequence If we want to compare the repetitiveness of two finite words, it looks reasonable, first of all, to consider more repetitive the word repeating more times one of its factors, and secondarily to ... 2 votes 3 answers 613 views ### The critical exponent function It is a known fact  that, for every c\in (1,\infty], it is possible to find a finite alphabet \mathcal{A} and a word w\in \mathcal{A}^\omega such that w has critical exponent c. It looks ... 3 votes 2 answers 232 views ### Binary words that are nonconstant on long arithmetic progressions Let w=x_0 x_1 x_2 \ldots be an infinite word, where each x_i\in \{0,1\}. For each positive integer k (thought of as the jump size of an arithmetic progression) and each residue 0\leq a \leq k-... 10 votes 0 answers 281 views ### Measuring the randomness of texts The question concerns statistic properties of random words in a finite alphabet A. By A^{<\omega} we denote the set of all words in the alphabet A, i.e. finite sequences of elements of A. ... 4 votes 0 answers 114 views ### Words that give rise to an enumeration of elements of the symmetric group Let \mathbb{S}_m be the symmetric group on m letters. Let n=m-1. Let \mathbf{w}=a_1\cdots a_r be a word on the alphabet \{1,\ldots,n\}. We say that \mathbf{w} gives rise to an enumeration ... 2 votes 0 answers 177 views ### V-like actions of V This continues my question about prefix-continuous bijections (since the answer was "yes"). Notation and conventions: Let A be a finite alphabet and L \subset A^* a language. Let G be a group. ... 6 votes 1 answer 174 views ### Is there a prefix-continuous bijection between finite words and eventually zero words? Let$$ X = \{x \in \{0,1\}^{\omega} \;|\; \exists m: \forall i \geq m: x_i = 0\} $$(one-way infinite eventually zero words). Let \{0,1\}^* denote the finite (not necessarily nonempty) words over \{... 9 votes 2 answers 359 views ### A cubefree-preserving morphism from 5 to 2? A word is cubefree if it cannot be written as xyyyz where y has positive length. Let h be the morphism from \{0,1,2,3,4\}^* to \{0,1\}^* given for words of length 1 as follows (a\to h(a)):... 1 vote 1 answer 95 views ### Cliques in overlap graphs for words Let \Sigma be a finite alphabet, and consider the free monoid \Sigma^*. Given w, w' \in \Sigma^* we say that w overlaps w' if there exist non-empty words u, v, u' such that w = uv and w'... 10 votes 0 answers 386 views ### Words and ranks Let me state two problems that look very much alike. The first one can be solved putting together answers that different people have given to some questions I asked here a few weeks ago. The second ... 6 votes 2 answers 286 views ### Uniqueness of "Limit" of Cyclic Binary Strings Set-up: By abuse, let \sigma represent both the left shift operator on infinite bi-infinite strings and the cyclic left shift operator on finite strings. (Thus, for example, \sigma(...01\bar{0}10...... 4 votes 1 answer 219 views ### Conjecture about infinite word Let w=a_1a_2a_3... be an infinite word over a finite alphabet and \epsilon>0. Do there exist integers n,k such that \frac{d(a_1a_2...a_n,a_{k+1}a_{k+2}...a_{k+n})}{n}<\epsilon ? (d(u,v)... 7 votes 1 answer 193 views ### Is the density of 1's in the Fibonacci word uniform? The Fibonacci word is the limit of the sequence of words starting with 0 and satisfying rules 0 \to 01, 1 \to 0. Equivalently, it is obtained from the recursion S_n= S_{n-1}S_{n-2} under ... 8 votes 1 answer 184 views ### Minimum number of permutations of \{1,\ldots, n\} that together contain every k-subpermutation Define a k-permutation of \{1,\ldots, n\} to be a word \tau_1 \ldots \tau_k such that \{\tau_1,\ldots,\tau_k\} is a k-subset of \{1,\ldots, n\}. Thus an n-permutation of \{1,\ldots, n\}... 19 votes 3 answers 1k views ### What is the fairest order for stage-striking (and is it the Thue-Morse sequence)? Here's a fair-sequencing problem that doesn't quite match the usual fair-division problems. I think that, like those, the answer should also be the Thue-Morse sequence ("balanced alternation"), ... 3 votes 1 answer 118 views ### Partition theorems for located words In this paper Bergelson, Blass, and Hindman prove the following Theorem 1.2 Let W(\Sigma; v) be colored with finitely may colors and let \bar s be an infinite sequence from W(\Sigma; v). ... 2 votes 1 answer 201 views ### Unique(ish) infinite string avoiding a set of patterns Let \Sigma be a finite alphabet of size at least 2. A (possibly infinite) string s over alphabet \Sigma encounters a pattern p \in \mathbb{N}^* iff there is a non-erasing morphism f: \mathbb{... 4 votes 1 answer 135 views ### Subshifts with a free semigroup Let X be a subshift on a finite alphabet. I'm interested in the following property: there exist words s,t\in\mathcal L(X) (the language of X) such that \{s,t\}^*\subset \mathcal L(X). That is, ... 1 vote 0 answers 37 views ### Latent Dirichlet Allocation on Contrived Data I am doing a project that seems like it might be susceptible to Latent Dirichlet Allocation. However, my data is highly contrived (both in test cases and use cases) and my "words" don't come close to ... 12 votes 1 answer 351 views ### "Bisecting" a free subgroup with respect to word length My broad question is regarding the lengths of (reduced) words in a subgroup of a free group. As motivation, consider the free group Gp(S) where |S|=n, that is, a free group of rank n. Let S=\{... 11 votes 1 answer 312 views ### Unique words in dihedral groups Suppose x is a word over the alphabet \{0,1\}. Let a, b be elements of the group Dih_k for some k. Let \varphi=\varphi_{a,b,k} be the map from words over \{0,1\} to elements of the ... 3 votes 0 answers 258 views ### Cayley Graphs and Cyclically reduced words [closed] Let G be a finite group and S be a symmetric generating set for G. (EDIT: Assume S does not contain involutions!) Cyclically reduced words can be thought of as minimal length representatives ... 4 votes 1 answer 157 views ### Covering sequences of words (If anyone has a better title please change it!) Given two finite words v,w in the alphabet \{a,b\}, define the v-proportion of w to be the largest number of letters in w which can be ... 0 votes 1 answer 154 views ### How many words are there such that some word X is subsequence of them? Let's define subsequence of the word as part of the word created by deleting some of its letters, for example aetics is a subsequence of mathematics. QUESTION. Given a 3-letter word (let's call it ... 5 votes 0 answers 934 views ### The functional equation f(x) = qx + qxf(x) - f(x^2) A word (i.e., ordered string of letters) is bifix-free provided it has no proper initial string and terminal string that are identical. For example, the word ingratiating has bifix ing, but the ... 17 votes 0 answers 514 views ### Question about combinatorics on words Let \{a_1,a_2,...,a_n\} be an alphabet and let \{u_1,...,u_n\} be words in this alphabet, and a_i\mapsto u_i be a substitution \phi. Question: Is there an algorithm to check if for some m,k... 5 votes 1 answer 328 views ### Number of Lyndon words of given weight Consider the alphabet consisting of two letters a and b, and put the lexicographic order in which a<b. We say that a non-empty word w in this alphabet is a Lyndon word if, for any non-... 3 votes 1 answer 249 views ### Longest runs and concentration of measure Consider the longest runs \ell_\sigma(x) of the pattern \sigma for \sigma\in \{0, 1, 01, 10, 001,\dots\} etc. in a binary sequence x=x_1\dots x_n. For example, \ell_{001}(0001110010011001)=2... 0 votes 0 answers 178 views ### Sum of unit vectors always has a binary span after constrained permutations Conjecture: Let e_1 = (1,0,\ldots,0), \ldots , e_{m_1+m_2} = (0,\ldots,0,1) be the unit vectors of the standard basis E of \mathbb{R}^{m_1+m_2}. An enumeration  E \cup -E = \{f_1, \ldots, ... 1 vote 1 answer 101 views ### Weighted counting of circular codes Given a circular code X (for example: X=\{ w,b \}) with generating function u(z)=\sum\limits_{k=0}^{\infty}{u_k z^k} (in this example : u(z)=2z), the generating function p(z)=\sum\limits_{k=0}... 4 votes 2 answers 131 views ### Sturmian subword whose reverse is not a subword Let {\cal L}_n be the set of all subwords of length n of a biinfinite Sturmian sequence, induced by a rotation coding with irrational angle \theta. Take a word w \in {\cal L}_{2^n} and write ... 1 vote 1 answer 182 views ### Building the string on \{0,1\} alphabet with \Omega(n^{2}) different substrings [closed] As we know the number of different substrings has the upper bound O(n^{2}). Consider the strings on \{0,1\} alphabet. Can I build a string with \Omega(n^{2}) different substrings? Actually I ... 4 votes 1 answer 401 views ### Periodic strings I wish to ask a problem in periodic strings, it might be well-known but I am a beginner in this subject, so I am very glad if someones can show me. My problem is that can we add some string to the end ... 3 votes 0 answers 204 views ### Repartition of 1's in the "Chacon word" Consider the "Chacon words": B_0=0 and B_{n+1} = B_nB_n1B_n. The word B_n has \ell_n := \frac{3^{n+1}-1}{2} digits and the number of 1's in B_n is \ell_n - 3^n = \ell_{n-1} \sim \ell_n/3... 2 votes 0 answers 112 views ### Zero-one links: how many, and how to produce? For m \geq 1, define a link to be a zero-one word w=d_0d_1 \ldots d_k, where d_0=0 and k=2^m-1 , such that the words$$ w_0=0^{m-1}d_0, w_1=w_0d_1, w_2=w_1d_2, \ldots, w_k = w_{k-1}d_k $$... 4 votes 1 answer 150 views ### Existence of an infinite word with a predetermined asymptotic for the word complexity Let w be an infinite binary word, for example:$$1010100001 0010011000 0001001110 0101011011 \dots Let $N_w(k)$ be the set of distinct subwords of $w$ of length $k$, and $n_w(k)$ the cardinal of ...
Cyclic sequence is equivalence class of cyclic shift action. If $a = (a_1, ... , a_i)_c$ is cyclic sequence then \$(a_1, a_2, \ldots a_{i-1}, a_i)_c = (a_2, a_3, \ldots, a_i, a_1)_c = \ldots = (a_i, ...