Questions tagged [combinatorics-on-words]

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

Filter by
Sorted by
Tagged with
40 votes
1 answer
1k views

Do runs of every length occur in this sequence?

This is a repost from user r.e.s's unsolved Math Stack Exchange question: Do runs of every length occur in this string? That question was derived from my original question on the subject: Does this ...
Calvin's Hobbies's user avatar
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 ...
Alessandro Della Corte's user avatar
31 votes
3 answers
2k views

"Nyldon words": understanding a class of words factorizing the free monoid increasingly

BACKGROUND. Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor Reiner'...
darij grinberg's user avatar
30 votes
1 answer
935 views

partition of infinite word onto permitted words

Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, $0<c&...
Fedor Petrov's user avatar
24 votes
3 answers
858 views

an operation on binary strings

Recently, as part of some joint research, Tom Roby was led to a curious operation on strings of L's and R's which he calls "bounce-reading": We start by reading the string at the left. When the ...
James Propp's user avatar
  • 19.4k
22 votes
6 answers
2k views

Are there uncountably many cube-free infinite binary words?

In Cube-free infinite binary words it was established that there are infinitely many cube-free infinite binary words (see the earlier question for definitions of terms). The construction given in ...
Gerry Myerson's user avatar
21 votes
0 answers
667 views

Avoidable words

Let $u(x_1,...,x_n)$ be a word, $k\in \mathbb{N}$. We say that $u$ is $k$-avoidable if there exists an infinite word in $k$ letters $\{a_1,...,a_k\}$ which does not contain values of $u$ (i.e. words ...
user avatar
20 votes
4 answers
3k views

Cube-free infinite binary words

A word $y$ is a subword of $w$ if there exist words $x$ and $z$ (possibly empty) such that $w=xyz$. Thus, $01$ is a subword of $0110$, but $00$ is not a subword of $0110$. I'm interested in right-...
JRN's user avatar
  • 1,329
20 votes
2 answers
723 views

congruence on words: having the same (scattered) subwords of length at most n

For a fixed finite alphabet $A=\{a,b,...\}$, write $x \sim_n y$ if the two words $x$ and $y$ have the same (scattered) subwords of length at most $n$. The relation $\sim_n$ is a congruence of finite ...
phs's user avatar
  • 371
19 votes
6 answers
3k views

Subwords of the Fibonacci word

The Fibonacci word is the limit of the sequence of words starting with "$0$" and satisfying rules $0 \to 01, 1 \to 0$. It's equivalent to have initial conditions $S_0 = 0, S_1 = 01$ and ...
john mangual's user avatar
  • 22.6k
19 votes
5 answers
1k views

Three-halves-free words (analogous to square-free)

A square-free word is a string of symbols (a "word") that avoids the pattern $XX$, where $X$ is any consecutive sequence of symbols in the string. For alphabets of two symbols, the longest square-free ...
Joseph O'Rourke's user avatar
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"), ...
Harry Altman's user avatar
  • 2,535
17 votes
3 answers
706 views

Probability that a word in the free group becomes (much) shorter?

Let $w$ be a word of length $2\ell$ chosen at random on the alphabet $\{x_1,x_1^{-1},x_2,x_2^{-1},\dotsc,x_k,x_k^{-1}\}$. By the reduction $\rho(w)$ I mean what you obtain by deleting substrings of ...
H A Helfgott's user avatar
  • 19.3k
17 votes
0 answers
530 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$...
user avatar
15 votes
7 answers
1k views

Two questions from combinatorics on words

Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...
Nikita Sidorov's user avatar
15 votes
1 answer
537 views

Combinatorics of palindromic decompositions

This is sort of a companion to my question Number of trivializations of a trivial word in the free group (which in turn is motivated by my earlier question here). It turns out that that question may ...
მამუკა ჯიბლაძე's user avatar
15 votes
0 answers
481 views

Word complexity of primes mod 4

For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
Igor Pak's user avatar
  • 16.3k
14 votes
3 answers
2k views

String of integers puzzle

I apologize for not have the math background to put this question in a more formal way. I'm looking to create a string of 796 letters (or integers) with certain properties. Basically, the string is ...
Erik's user avatar
  • 425
13 votes
1 answer
535 views

Is the set of cube-free binary sequences perfect?

This question is inspired by this one. In that thread, it's established that there are uncountably many cube-free infinite binary strings (where $x \in 2^{\omega}$ is cube-free iff $\forall \sigma \...
Amit Kumar Gupta's user avatar
13 votes
1 answer
524 views

Number of trivializations of a trivial word in the free group

Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ ...
მამუკა ჯიბლაძე's user avatar
13 votes
0 answers
287 views

Computing exact or asymptotics for number of strings over an alphabet of size $n$ that have no non-trivial substrings that appear more than once

I ran across a seemingly relatively simple combinatorics problem that appears open. For an alphabet of size $n$, let $A(n)$ be the number of strings over the alphabet that have no substring of length $...
user2566092's user avatar
12 votes
1 answer
414 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 ...
Clark Kimberling's user avatar
12 votes
1 answer
408 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=\{...
BharatRam's user avatar
  • 939
11 votes
1 answer
323 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 ...
Bjørn Kjos-Hanssen's user avatar
10 votes
2 answers
1k views

Ubiquitous Zimin words

Let $w$ be a word in letters $x_1,...,x_n$. A value of $w$ is any word of the form $w(u_1,...,u_n)$ where $u_1,...,u_n$ are words. For example, $abaaba$ is a value of $x^2$. A word $u$ is called ...
user avatar
10 votes
1 answer
435 views

Elegant proof for $xy < yx \Leftrightarrow x^\mathbb{N} < y^\mathbb{N}$

Let $x, y$ be finite words over totally ordered alphabet and $<$ denote the lexicographical order, i.e for two not necessarily finite words we say $x < y$ iff one of the following holds There ...
thematdev's user avatar
  • 163
10 votes
1 answer
674 views

Analogues of the Knuth and Forgotten equivalences on permutations: have they been studied?

Consider a totally ordered alphabet $A$ of $n$ letters. Let $W$ be the set of all words over $A$ which have no two letters equal. Then, for example, we can define the Knuth equivalence on $W$ as the ...
darij grinberg's user avatar
10 votes
0 answers
394 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 ...
H A Helfgott's user avatar
  • 19.3k
9 votes
2 answers
381 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)$):...
Bjørn Kjos-Hanssen's user avatar
9 votes
0 answers
443 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$. ...
Taras Banakh's user avatar
  • 40.8k
8 votes
1 answer
318 views

Über theorem on unavoidable patterns?

Let $A$ be an alphabet of $k$ symbols, and $p$ a pattern. An example of a pattern is $p=XX$, where $X$ is any finite string of symbols from $A^+$. Avoiding $p$ is avoiding any subword repeated twice ...
Joseph O'Rourke's user avatar
8 votes
1 answer
436 views

Is there a name for infinite words containing every finite words?

Apparently, the closest thing I've found would be normal number http://mathworld.wolfram.com/NormalNumber.html But requiring that every finite words occurs is weaker than this property. So I'm ...
Hermaion's user avatar
8 votes
1 answer
209 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\}$...
Mark Wildon's user avatar
  • 10.8k
7 votes
1 answer
235 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 ...
Darren Ong's user avatar
7 votes
2 answers
308 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$ ...
lyrically wicked's user avatar
6 votes
2 answers
164 views

Which criteria guarantee an orthogonal circuit in $\mathbb R^3$ to be rigid?

For $n\ge4$, define an orthogonal circuit or O-circuit as a closed circuit of $n$ unit segments in $\mathbb R^3$ such that any two neighboring segments form a right angle. (Physically this could be ...
Wolfgang's user avatar
  • 13.2k
6 votes
1 answer
257 views

A Sauer-Shelah-like lermma for prefix tree

I proved a variant of the Sauer-Shelah lemma and I was wondering if something like that is already known. Let $S \subseteq \{0,1\}^n $. We say that a set of coordinates $K \subseteq [n]$ is shattered ...
Or Meir's user avatar
  • 419
6 votes
1 answer
186 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 $\{...
Ville Salo's user avatar
  • 6,337
6 votes
2 answers
313 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......
Adam Quinn Jaffe's user avatar
5 votes
2 answers
378 views

Concatenation of strings [closed]

We have two strings (i. e., finite tuples) $A$ and $B$. We have to find if for some positive integers $n$ and $m$, the string $A$ concatenated $n$ times equals the string $B$ concatenated $m$ times or ...
user103260's user avatar
5 votes
2 answers
201 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 ...
Sebastien Palcoux's user avatar
5 votes
2 answers
241 views

Ordering on words

What are the known computation-friendly well-orderings on words from $A^*$, where $A$ is a finite alphabet, except the standard weightlex and syllable-order?
Victor's user avatar
  • 1,427
5 votes
1 answer
388 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-...
barry's user avatar
  • 51
5 votes
1 answer
119 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 ...
rtsss's user avatar
  • 477
5 votes
1 answer
217 views

Which automated theorem provers can address the combinatorics of periods in strings?

Five years ago, I made a conjecture on the number of correlation classes that are exhibited by pairs of words in an alphabet of a given size. I later speculated that the conjecture could be tackled ...
Penguian's user avatar
  • 129
5 votes
1 answer
285 views

In the Oldenburger-Kolakoski sequence, is #1s = #2s infinitely many times?

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).$...
Clark Kimberling's user avatar
5 votes
1 answer
431 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 ...
Cuong's user avatar
  • 51
5 votes
1 answer
333 views

What prefix and factors determine a ultimately periodic word uniquely

Let $\xi$ be an ultimately periodic sequence, i.e. there exists finite sequences $p, q \in X^*$ such that $\xi = pq^{\omega}$. Does there exists a $n > 0$ such that the prefix of length $n$ and all ...
StefanH's user avatar
  • 798
5 votes
0 answers
112 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 ...
user158448's user avatar
5 votes
0 answers
1k 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 ...
D. Ror.'s user avatar
  • 399