I have a vector of boolean variables $v=(x_1,\dots,x_k)$. In each step each variable is updated according to a positive disjunction like so:
- $x_1 \leftarrow x_i \vee \dots \vee x_j$
- $\dots$
- $x_k \leftarrow x_m \vee \dots \vee x_n$
This produces a sequence of vectors $\underline{v} = v_1,v_2\dots$. My question is, how long does it take for $\underline{v}$ to reach a cycle, in terms of $k$, for arbitrary $v_1$, that is:
Let $v$ be a $k$-ary boolean vector. Then $f(v)$ denotes the update function for according to those rules. We say $v'$ is in a cycle from $v$ if there is an $n>0$ and $m \geq 0$ such that $f^{(m)}=f^{(m+n)}$. We define the smallest time to reach a cycle as the smallest sum $m+n$ for which the equality holds.
The question is: What is an upper bound for the smallest time to reach a cycle in terms of $k$ that holds for all possible starting vectors $v_1$ and all possible update functions $f$.
My idea was to represent the update rules as a dependency graph and look at cycles to form rules such as if $x_i$ is true in $v_y$ and is in a cycle of length $n$, then it will also be true in $v_{y+n}$.
But the best lower bound I could do so far is to construct an example where for even $k=2l$ I construct two cycles of length $l$ and $l+1$ with one common node and start with $v_1$ having exactly one true node. The common node is true every $l$ or $l+1$ steps (depending on in which cycle the first true node was). Since $gcd(l,l+1)=1$, eventually all nodes in the other cycle will be true as well. For this, the common nude must be true $l+1$ or $l$ times, respectively. This yields $O(k^2)$ steps until all nodes are true (and then $\underline{v}$ is trivially cyclic).
Unfortunately, I did not get any upper bound except for the obvious $2^k+1$ since each $v_i$ can only assume one of $2^k$ values.
I am not necessarily looking for an exact upper bound if that turns out to be hard, it'd also be sufficient for me to give the upper bound in $O$-notation, or even just show whether the upper bound is polynomial or exponential.
Further, I'm also interested in and extension to the 3-valued case (with 3-valued Kleene disjunction).