# How to maximize the number of operations in process

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
• I'm not sure about the tags and the title any suggestion is wolcome Mar 28, 2015 at 23:35
• How the worst case for couples is $\frac{h(h+1)}{2}-1$? $h=1$ gives 0 Apr 1, 2015 at 4:01
• Also please explain length of a tuple: "... with all the intermediate tuples have length less then h". Apr 1, 2015 at 4:31
• 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? Apr 1, 2015 at 8:42
• 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) Apr 6, 2015 at 2:24

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.