ON REDUCED SCALAR EQUATIONS FOR SYNCHRONOUS BOOLEAN NETWORKS

Abstract

A total description of a synchronous Boolean network is typically achieved by a matrix recurrence relation. A simpler alternative is to use a scalar equation which is a possibly nonlinear equation that involves two or more instances of a single scalar variable and some Boolean operator(s). Further simplification is possible in terms of a linear reduced scalar equation which is the simplest two-term scalar equation that includes no Boolean operators and equates the value of a scalar variable at a latter instance t₂ to its value at an earlier instance t₁. This equation remains valid when the times t₁ and t₂ are both augmented by any integral multiple of the underlying time period. In other words, there are infinitely many versions of a reduced scalar equation, any of which is useful for deducing information about the cyclic behavior of the network. However, to obtain correct information about the transient behavior of the network, one must find the true reduced scalar equation for which instances t₁ and t₂ are minimal. This study investigates the nature, derivation and utilization of reduced scalar equations. It relies on Boolean-algebraic manipulations for the derivation of such equations and suggests that this derivation can be facilitated by seeking certain orthogonality relations among certain successive (albeit not necessarily consecutive) instances of the same scalar variable. We demonstrate, contrary to previously published assumptions or assertions, that there is typically no common reduced scalar equation for all the scalar variables. Each variable usually satisfies its own distinct reduced scalar equation. We also demonstrate that the derivation of a reduced scalar equation is achieved not only by proving it but also by disproving an immediately preceding version of it when such a version might exist. We also demonstrate that, despite the useful insight supplied by the reduced scalar equations, they do not provide a total solution like the one offered by matrix methods and therefore they need be supported by other techniques of mathematical reasoning. We present three classical examples to illustrate our techniques. Two examples are tutorials on the necessary Boolean-algebraic techniques. They present corrections of previously published results and refute purported claims of discrepancies between scalar and matrix methods. The third example illustrates how the reduced scalar equations can be supplemented by techniques of number theory, Diophantine equations and Boolean equations in making subtle inferences about Boolean networks. We achieved a better understanding of the nature of reduced scalar equations, demonstrated Boolean-algebraic techniques for deriving them, presented other mathematical tools for utilizing them and finally reconciled them with the more encompassing but more complex and less insightful matrix methods.