In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word.

If we are given an ordered triple of words $(a,b,c)$, an operation on that tuple consists of replacing one of the $x\in\{a,b,c\}$ by $x0,\ x1,$ or $y$ such that $x\neq y\in\{a,b,c\}$, e.g: $$(\epsilon,\epsilon,\epsilon)\xrightarrow{b:=b1}(\epsilon,1,\epsilon)\xrightarrow{b:=b0}(\epsilon,10,\epsilon)\xrightarrow{c:=c1}(\epsilon,10,1)\xrightarrow{a:=b}(10,10,1) $$ Given a non-negative integer $h$, we say that $(a,b,c)$ is $h$-complete if the length of each of $a,b,c$ is $h$, that is $|a|=|b|=|c|=h$. We say that a series of operations is healthy if and only any tuple $(a,b,c)$ appears at most once. For example, the sequence $$(\epsilon,\epsilon,\epsilon)\xrightarrow{b:=b0}(\epsilon,1,\epsilon)\xrightarrow{ b:=c}(\epsilon,\epsilon,\epsilon)$$ is not healthy because $(\epsilon,\epsilon,\epsilon)$ appears twice.

The length of a tuple $(a,b,c)$ is defined as $|(a,b,c)|=\max(|a|,|b|,|c|)$

My question:

What is the maximum number of healthy operations in a sequence which can transform $(\epsilon,\epsilon,\epsilon)$ into an $h$-complete tuple with all the intermediate tuples have length less than or equal to $h$

The minimum number of operations is $h+2$, but I'm interested in the worst case, and my problem consists of a generalization for $n$ words and not just $3$.

If you know any references for such problems, or have any idea about this problem, it will be appreciated!

Edit: the answer for couples is $f_2(h)=\frac{(h+2)(h+1)}{2}-1$ when we are taking pairs $(x,y)$ instead of $3$-tuples $(a,b,c)$

  1. If $h=1$ there is only two operations which can transform $(\epsilon,\epsilon)$ to $(0,0),(0,1),(1,0),(1,1)$ so: $$f_2(1)=2 $$
  2. Suppose that there is only that the result is true for $h$ given two words of lenght $|x|=|y|=h+1$ my idea is described by the following process: $$(\epsilon,\epsilon)\underbrace{-------\rightarrow}_{m(h) \text{ operations}} \begin{Bmatrix} (0,0)\\ (0,1)\\ (1,0)\\ (0,0) \\ (w,w') \big/ |w|\text{or }|w'|>1 \end{Bmatrix}\underbrace{-------\rightarrow}_{x(h) \text{ operations}} (x,y)$$ the added intermediate step is necessary (we can not complete the process without passing throught it) and one can prove that : $m(h)\leq h+2$ and clearly $x(h)\leq f_2(h)$ so: $$f_2(h+1)\leq f_2(h)+h+2$$ to complete the proof we have to construct a process with $f_2(h+1)=h+2+f_2(h)$ which can be done using the schema
  • $\begingroup$ I'm not sure about the tags and the title any suggestion is wolcome $\endgroup$
    – Elaqqad
    Mar 28, 2015 at 23:35
  • $\begingroup$ How the worst case for couples is $\frac{h(h+1)}{2}-1$? $h=1$ gives 0 $\endgroup$
    – LoMaPh
    Apr 1, 2015 at 4:01
  • $\begingroup$ Also please explain length of a tuple: "... with all the intermediate tuples have length less then h". $\endgroup$
    – LoMaPh
    Apr 1, 2015 at 4:31
  • $\begingroup$ The way you defined the "length of a tuple", I don't see how we can have an $h$-complete tuple while all the intermediate tuples have length less then h. The operations you defined only change one word at a time. If we want to have an $h$-complete tuple, at least two of previous tuples in the sequence must have the same length as $h$. Did you mean less than or equal? $\endgroup$
    – LoMaPh
    Apr 1, 2015 at 8:42
  • $\begingroup$ It might be worth looking at this analogous problem on the language $\{0\}^*$. That might give useful insight. (One might also, resolving that, try $\{0\}^*\cup \{1\}^*$ to get a feel for how having multiple words of equal length works) $\endgroup$ Apr 6, 2015 at 2:24

1 Answer 1


(I wouldn't claim my answer to be complete, but it is too long for a comment.)

There can be exponentially many steps, as I show below. And an obvious upper bound is $2^{3(h + 1)}$.

Now let consider following series of steps ($x \leftarrow y$ means that $x$ takes value $y$).

$$(\epsilon, \epsilon, \epsilon) \xrightarrow{a \leftarrow a0} (0, \epsilon, \epsilon) \xrightarrow{a \leftarrow a0} \cdots \xrightarrow{a \leftarrow a0} (\underbrace{0\ldots0}_{h}, \epsilon, \epsilon) \\ = (\underbrace{0\ldots0}_{h}, \epsilon, \epsilon) \xrightarrow{b \leftarrow b0} (\underbrace{0\ldots0}_{h}, 0, \epsilon) \xrightarrow{b \leftarrow b0} \cdots \xrightarrow{b \leftarrow b0} (\underbrace{0\ldots0}_{h}, \underbrace{0\ldots0}_{h}, \epsilon) \\ \xrightarrow{a \leftarrow c} (\epsilon, \underbrace{0\ldots0}_{h}, \epsilon) \xrightarrow{a \leftarrow a0} (0, \underbrace{0\ldots0}_{h}, \epsilon) \xrightarrow{a \leftarrow a0} \cdots \xrightarrow{a \leftarrow a0} (\underbrace{0\ldots0}_{h - 1}, \underbrace{0\ldots0}_{h}, \epsilon) \xrightarrow{a \leftarrow a1} (\underbrace{0\ldots0}_{h - 1}1, \underbrace{0\ldots0}_{h}, \epsilon) \\ \xrightarrow{b \leftarrow c} (\underbrace{0\ldots0}_{h - 1}1, \epsilon, \epsilon) \xrightarrow{b \leftarrow b0} (\underbrace{0\ldots0}_{h - 1}1, 0, \epsilon) \xrightarrow{b \leftarrow b0} \cdots \xrightarrow{b \leftarrow b0} (\underbrace{0\ldots0}_{h - 1}1, \underbrace{0\ldots0}_{h - 1}, \epsilon) \xrightarrow{a \leftarrow a1} (\underbrace{0\ldots0}_{h - 1}1, \underbrace{0\ldots0}_{h - 1}1, \epsilon) \xrightarrow{a \leftarrow c}\\ \vdots\\ \rightarrow(\underbrace{1\ldots1}_{h}, \underbrace{1\ldots1}_{h}, \epsilon)\rightarrow\ldots$$

In other words after some preparation $(a, b, c)$ runs through $2^{h + 1} \cdot (h + 1)$ possible values of form $(x, \mathrm{prefix}(x), \epsilon)$ or $(\mathrm{prefix}(x + 1), x, \epsilon)$ for $2h + 2$ steps between $(x, x, \epsilon)$ and $(x + 1, x + 1, \epsilon)$, where $x$ is a number written in binary with exactly $h$ digits (leading zeros are allowed), for all $2^h$ possible values of $x$. So all polynomial upper bounds are wrong.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.