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

**4**

votes

**2**answers

102 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

108 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 ...

**3**

votes

**1**answer

205 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

165 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 ...

**2**

votes

**0**answers

103 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

122 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 ...

**3**

votes

**1**answer

97 views

### Number and asymptotic for cyclic sequences

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, ...

**29**

votes

**1**answer

738 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$, ...

**2**

votes

**0**answers

168 views

### Words with Local plus Global Constraints

While doing estimates on the complexity of an algorithm I have run into a word-combinatorial problem with both a local and a global constraint.
This seems to be a rather general situation and I'm ...

**14**

votes

**3**answers

565 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 ...

**1**

vote

**1**answer

77 views

### Terminology for set of infinite strings with a certain prefix

Let $\mathcal{A}$ be a finite alphabet, and let $C$ be the Cantor space $\mathcal{A}^\omega$ under the product topology.
Given a finite string $s \in \mathcal{A}^*$, let $C(s)$ be the set of all ...

**11**

votes

**1**answer

377 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$ ...

**4**

votes

**1**answer

289 views

### Strings with no long runs from proper subalphabets

Let $R_{n,k,b}$ be the number of $b$-ary strings of length $n$ that contain some run of length at least $k$ from some $(b-1)$-ary subalphabet. Let $N_{n,k,b}=b^n-R_{n,k,b}$ be the size of the ...

**7**

votes

**0**answers

157 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 ...

**19**

votes

**5**answers

889 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 ...

**3**

votes

**1**answer

243 views

### Combinatorics problem involving counting the number of certain substrings

I'm not sure if this question is suited for MO, but it does seem quite challenging to me, and is required for a research problem in chemistry I'm working on. I did try getting help from elsewhere ...

**12**

votes

**0**answers

333 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 ...

**1**

vote

**1**answer

431 views

### Is it possible to create an infinite sequence in which no subsequence is repeated 3 times in a row?

In Chess, there is the Threefold Repetition rule where if a sequence of moves is repeated 3 times in a row, either player can claim a draw.
Say two players wanted to play a legal, infinite game of ...

**12**

votes

**0**answers

173 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 ...

**16**

votes

**4**answers

2k 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 ...

**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 ...

**28**

votes

**2**answers

1k 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 ...

**13**

votes

**3**answers

1k 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 ...

**17**

votes

**6**answers

2k 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 then recursion ...

**19**

votes

**0**answers

486 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 ...

**2**

votes

**0**answers

116 views

### Counting strings with alternating letters with generating functions

It is a classical problem that of finding the generating function (GF) of the number of strings with length $n$ having $m$ different letters (basically, the problem reduces to that of writing the ...

**4**

votes

**2**answers

124 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 ...

**37**

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 ...

**2**

votes

**1**answer

157 views

### Equivalent subshifts

Let $X$ be a finite set, $(X^{\mathbb Z}, T)$ is the shift, i.e. the Tikhonov topological space of all bi-infinite words in $X$, $T$ shifts the words one letter to the right. A subshift is a closed ...

**8**

votes

**1**answer

250 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 ...

**7**

votes

**1**answer

336 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 ...

**4**

votes

**0**answers

65 views

### Covariance matrix for number of powers in a word

A word over the alphabet $\{0,1\}$ of length $n$ may contain squares, cubes, and generally $k$th powers, where $2\le k\le n$. Let $O_k(w)$ denote the number of $k$th power occurrences in the word $w$.
...

**3**

votes

**1**answer

172 views

### Calculating the probability that all possible length $r$ subwords exists in a string, with or without overlaps allowed

Let $S$ be a length $L$ string, where each character in the string is chosen with uniform random probability over an alphabet with $q$ characters. For example, a binary string would imply $q = 2$, a ...

**20**

votes

**5**answers

1k 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 ...

**4**

votes

**1**answer

155 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 ...

**2**

votes

**1**answer

408 views

### Notation for ends of a string

I work now a lot with strings of characters and other finite sequences and found that I need many times a good notation for "cutting the end" a string. If $a$ is a finite sequence and $a'$ is its ...

**2**

votes

**1**answer

125 views

### Representability of sets of infinite sequences sharing common prefixes and factors (i.e. infixes)

Here we are concerned with the space $X^{\omega}$ of infinite sequences. Denote by $F_n(\xi)$
the set of factors (consecutive finite subsequences) of length $n$ and consider the set
$$
K_n(\xi) = ...

**5**

votes

**1**answer

167 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 ...

**5**

votes

**2**answers

193 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?

**3**

votes

**2**answers

265 views

### Maximal words (reloaded)

I have 3 more questions about maximal words (which are just another way of talking of necklaces).
Let W be a finite word on a two symbol alphabet {0,1}; let us say that W is maximal if it is the last ...

**20**

votes

**2**answers

622 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 ...

**3**

votes

**5**answers

363 views

### Strings and “co-subsequences”

Let $S$ be a string over some alphabet $\Sigma$. It is well known that a substring of $S$ is commonly defined as a sequence of contiguous elements from $S$, while a subsequence of $S$ is a sequence ...

**3**

votes

**1**answer

241 views

### A property of periodic words

Question is edited Perhaps this formulation is clearer.
It is well known that if a power of a primitive (i.e. not a proper power) word $u$ contains two different occurrences of a word $v$, ...

**10**

votes

**1**answer

519 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 ...

**9**

votes

**2**answers

724 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 ...

**4**

votes

**4**answers

534 views

### Subwords of cube-free binary words

I'm currently working on subwords of cube-free binary words.
A binary word is one composed of letters from a two-letter alphabet such as $\{0,1\}$. A word $y$ is a subword of $w$ if there exist ...

**3**

votes

**0**answers

162 views

### Generalised de Bruijn Graph

I have encountered sets of the following type, consisting of words over a finite aphabet $A$.
If $S$ is such a set, then
$S$ is finite,
No word in $S$ is part of another element of $S$, and
every ...

**3**

votes

**0**answers

350 views

### Software for Combinatorial Algebra sought

I am looking for software which helps me do straightforward tasks in combinatorial algebra. Let me give an example of what I mean by a straightforward task:
I have two graded (generally ...

**22**

votes

**3**answers

746 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 ...