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}).$



Breaking efficiently a binary sequence into given strings
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


