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\cdot\sigma_2\cdot\sigma_3\dots$$ $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}? Are 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 assumption 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}). 4 deleted 401 characters in body 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\cdot\sigma_2\cdot\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}? Are there special assumption 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. It seems that 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). 3 added 416 characters in body 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\cdot\sigma_2\cdot\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}?$Are there special assumption 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. We may also 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.$It seems that 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)\$.