All Questions
7 questions
2
votes
0
answers
101
views
Combinatorics on non-associative words
In my P.h.d research, I deal (among other things) with non-associative words, which we call monomials, and we need to consider two types of operations with these monomials.
The first one is simply ...
6
votes
1
answer
280
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 ...
- 6,652
15
votes
1
answer
558
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.1k
4
votes
1
answer
245
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,621
1
vote
1
answer
105
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}...
- 26.5k
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-...
- 1,329
24
votes
3
answers
865
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 ...
- 30.1k