2
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ I'm not sure what your question is. Are you looking for an efficient algorithm that, given the update rules, computes the time to cycle? Are you looking for a mathematical upper bound on the time to cycle as a function of $n$, that will hold for all update rules? Something else? Can you edit your question to clarify? $\endgroup$
    – D.W.
    Mar 24 at 18:01
  • $\begingroup$ Can you define more precisely what it means to "reach a cycle"? If you are already "in" a cycle of length $\ell$, does it take $\ell$ time to reach a cycle, or 0? $\endgroup$
    – D.W.
    Mar 24 at 18:02
  • $\begingroup$ I'm searching for theoretical bounds that hold for all $k$, i.e., whether it's worst case polynomial or exponential. For your second question: It takes $l$ time, so essentially I'm asking when you'll encounter a vector $v_i$ that you've already seen. $\endgroup$
    – PattuX
    Mar 24 at 18:20
  • $\begingroup$ That still doesn't answer my questions about what it means to reach a cycle. Let me propose some definitions. If $x$ is a state (boolean vector), let $f(x)$ denote the next step according to the update rules, and let $f^{(n)}(x)$ denote the result of applying $f$ $n$ times. We could define that $x$ is in a cycle if there exists $n>0$ such that $f^{(n)}(x)=x$, that the period of the cycle is the smallest such $n$, that the time it takes for $x$ to reach a cycle is the smallest $n$ such that $f^{(n)}$ is in a cycle, and that the cycle time of $x$ is the smallest $n>0$ such that $f^{(n)}(x)=x$. $\endgroup$
    – D.W.
    Mar 24 at 18:36
  • $\begingroup$ If you accept those definitions, are you asking for an upper bound on the period of any cycle? on the time it takes to reach a cycle? the cycle time of any state? Please edit the question to define all concepts precisely and be precise about what you want answered. $\endgroup$
    – D.W.
    Mar 24 at 18:37
2
$\begingroup$

This can take exponentially many steps, as Laakeri explained.

You can build a system that cycles with period $p$. In particular, the update rule is $x_i = x_{i-1 \bmod p}$ for all $i$, with variables $x_0,\dots,x_{p-1}$.

Let $p_1,\dots,p_k$ be the first $k$ primes. Concatenate $k$ disjoint systems, each of which cycles with period $p_i$. Then the period of the entire system is the product $p_1 \cdots p_k$. The system involves $p_1+\dots+p_k$ variables.

If you have $n$ variables, then we can take $k$ to be approximately $\sqrt{4n/\log n}$. Now the product of the first $k$ primes is roughly $e^{k \log k}$, or in other words, $e^{\Theta(\sqrt{n/\log n})}$, which is exponential in $n$.

This shows that the period of a system, and thus the time to reach a cycle (by your definition), can be exponential in the number of variables.

$\endgroup$
3
  • $\begingroup$ Can you specify what you mean by "concatenate"? Adding one transition from a cycle induced by $p_i$ to the cycle of length $p_{i+1}$? If yes, this does not hold, as I said in response to Laakeri's comment. For $k=2$ we have some constant $t$ as the maximum number of steps required for $(x_1,\dots,x_5)$ to cycle. within that vector cycle we must have $x_3=x_4=x_5=\text{true}$. As I outlined in my comment, from there on adding a $p_k$ cycle results in $p_k$ more steps until you $\underline{v}$ reaches a cycle. This means in your construction the bound is $t+\sum_{i=2}^k p_k$, i.e., linear. $\endgroup$
    – PattuX
    Mar 25 at 8:01
  • $\begingroup$ @PattuX, no, each system is disjoint. Variables $x_0,\dots,x_{p_1-1}$ are in the first system, $x_{p_1},\dots,x_{p_1+p_2-1}$ are in the second system, and so on. Each update rule only mentions variables within the system, there is no propagation between systems. Each system evolves independently, in parallel. I'm proposing something different than you proposed, so your response to Laakeri is irrelevant (I suspect you misunderstood what Laakeri had in mind too). $\endgroup$
    – D.W.
    Mar 25 at 8:03
  • $\begingroup$ Oh, now I see, thank you! $\endgroup$
    – PattuX
    Mar 25 at 8:19

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.