The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
76 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 ...
9
votes
0answers
111 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 ...
4
votes
2answers
100 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 ...
36
votes
1answer
886 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 ...
7
votes
1answer
206 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
1answer
287 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 ...
3
votes
0answers
46 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$. ...
16
votes
0answers
384 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$, ...
3
votes
1answer
134 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 ...
4
votes
1answer
115 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
1answer
110 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) = ...
15
votes
7answers
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 ...
5
votes
1answer
117 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
2answers
174 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?
20
votes
2answers
564 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
1answer
222 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$, ...
4
votes
4answers
474 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
0answers
154 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 ...
10
votes
1answer
453 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 ...
15
votes
0answers
423 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
1answer
370 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 ...
3
votes
0answers
330 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 ...
21
votes
3answers
709 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 ...
8
votes
2answers
617 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 ...
2
votes
1answer
149 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 ...
20
votes
5answers
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 ...
11
votes
3answers
1k 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 ...
14
votes
5answers
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 ...
3
votes
2answers
243 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 ...
3
votes
5answers
344 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 ...