## Breaking efficiently a binary sequence into given strings

Suppose we are given a finite collection of finite binary strings $\mathcal{S}$, of various lengths. Our task is to express any binary sequence $x\in 2^\mathbb{N}$ as juxtaposition of strings taken from $\mathcal{S}:$ $$x=\sigma_1\sigma_2\sigma_3\dots$$ For any such sequence of "bricks", $\sigma\in\mathcal{S}^\mathbb{N},$ we consider $$L^*(\sigma):=\limsup_{n\to\infty}\frac{1}{n}\sum_{k=1}^n\ \mathrm{length}(\sigma_k)$$ as a kind of parameter of quality of the factorization: we appreciate a factorization if the mean length of the composing pieces is frequently high.

Question:

Given the set $\mathcal{S},$ how to compute the best $L^*(\sigma)$ which is always attainable, whatever is $x\in 2^\mathbb{N}?$ That is, the quantity (depending on $\mathcal{S}$ only)

$$\lambda(\mathcal{S}):=\inf_{x\in2^\mathbb{N}}\ \max\ \{L^*(\sigma)\ :\ \sigma\in\mathcal{S}^\mathbb{N}, \ x=\sigma_1 \sigma_2 \sigma_3\dots \}.$$

Also, are there special assumptions on the collection $\mathcal{S}$ that may simplify the analysis?

Example. Let $\mathcal{S}:=\{ 0,\ 1,\ 00,\ 01,\ 11 \}.$ Then, any binary sequence $x$ can be broken into a sequence of strings in $\mathcal{S}$, with average length larger than or equal to $3/2$.

Remark. For my purposes, we can assume that the collection $\mathcal{S}$ always enjoys the property of being "stable for extraction of sub-strings", that is, if $\sigma=\epsilon_1 \epsilon_2 \dots \epsilon_n\in\mathcal{S}$, then also $\epsilon_p \epsilon_{p+1} \dots \epsilon_q\in\mathcal{S},$ for any $1\leq p < q\leq n.$ If I am not wrong, this allows quite a simple inductive procedure for a canonical optimal factorization $\sigma$ of a binary sequence $x$: having chosen $\sigma_1,\dots,\sigma_k,$ take $\sigma_{k+1}$ as the longest admissible element of $\mathcal{S}$: by the above property of $\mathcal{S}$ any other factorization $\tau$ of $x$ can be easily compared with $\sigma$, showing $L^ *(\sigma) \geq L^ *(\tau)$. So in this case I'd expect there is some hope of being able of computing the quantity $\lambda(\mathcal{S}).$

-
Just for context: en.wikipedia.org/wiki/Huffman_coding – Steve Huntsman Oct 6 2010 at 16:53
thanks a lot! (I came to this problem from a completely different origin so a context where to look is a very useful starting point). – Pietro Majer Oct 6 2010 at 17:45

## 1 Answer

Not an answer, but perhaps of some use:

It would help if S, the set of blocks, were finite. In any case, if S contains all words of length k, you know that for sufficiently long words L will have k as a lower bound. (Computing k for a given S closed under consecutive substrings is feasible, but may not be polynomial time in the length of a representation of S.) If S contains almost all words of length k, then the lower bound for L will still be k on those sigma which avoid the missing words, otherwise the lower bound for L will approach the lower bound for L of those missing words which occur more frequently as you read more of sigma. It may then make sense to compute L for short words not in S, or infinite repetitions of such short words, and use this in aiding the computation of L of sigma.

If S has infinitely many finite blocks (and the alphabet is still finite), then there is the potential for L to assume values of infinity. If you don't care about that or if you are focussing on the cases where L will be finite, then you have some mathematics which may touch upon descriptive set theory, and you may encounter a large cardinal or other surprising axiom to consider. S being closed under consecutive substrings will in many cases produce a larger k (k as in the above paragraph), and will have to be pretty special otherwise to avoid any finite substring. There may be other tools in mathematical logic (e.g. filters on finite subsets of the language) that might tell you what properties you want S to have.

Another poster referenced Huffman encoding. Outside of symbolic dynamics (and related fields of automata theory and semigroup theory), that and similar string-processing algorithms is a first choice of where to look for previous work. If you are considering extra-world (surreal? non-real?) applications using infinite S might you then turn to mathematical logic.

Gerhard "Ask Me About System Design" Paseman, 2010.10.07

-
 Thank you, that's of use indeed. Note that my S is a finite collection of strings of finite length. So, following somehow the hints in the first part of your answer I think I see how to compute that L(S), assuming the property I wrote in the remark. Let $A$ be a string in S of minimal length among those starting with $0,$ and such that $A0\notin S.$ Also, let $B,$ $C,$ $D$ defined analogously: $A$ and $B$ start with $0,$ $C$ and $D$ start with 1; $A0$ $B1$ $C0$ $D1$ are not in $S$. Then the constant L(S) is realized either by the sequence AAA.., or by DDD, or by BCBC... – Pietro Majer Oct 8 2010 at 17:23