Descriptive complexity for neural networks via Boolean networks
We investigate the descriptive complexity of a class of neural networks with
unrestricted topologies and piecewise polynomial activation functions. We
consider the general scenario where the running time is unlimited and
floating-point numbers are used for simulating reals. We characterize these
neural networks with a rule-based logic for Boolean networks. In particular, we
show that the sizes of the neural networks and the corresponding Boolean rule
formulae are polynomially related. In fact, in the direction from Boolean rules
to neural networks, the blow-up is only linear. We also analyze the delays in
running times due to the translations. In the translation from neural networks
to Boolean rules, the time delay is polylogarithmic in the neural network size
and linear in time. In the converse translation, the time delay is linear in
both factors. We also obtain translations between the rule-based logic for
Boolean networks, the diamond-free fragment of modal substitution calculus and
a class of recursive Boolean circuits where the number of input and output
gates match.
Veeti Ahvonen, Damian Heiman, Antti Kuusisto
# Descriptive complexity for neural networks via Boolean networks

###### Abstract

We investigate the descriptive complexity of a class of neural networks with unrestricted topologies and piecewise polynomial activation functions. We consider the general scenario where the running time is unlimited and floating-point numbers are used for simulating reals. We characterize a class of these neural networks with a rule-based logic for Boolean networks. In particular, we show that the sizes of the neural networks and the corresponding Boolean rule formulae are polynomially related. In fact, in the direction from Boolean rules to neural networks, the blow-up is only linear. We also analyze the delays in running times due to the translations. In the translation from neural networks to Boolean rules, the time delay is polylogarithmic in the neural network size and linear in time. In the converse translation, the time delay is linear in both factors.

email: firstname.lastname@tuni.fi

## 1 Introduction

This article investigates the descriptive complexity of neural networks, giving a logical characterization for a class of general neural networks with unrestricted network topologies and unlimited running time. The characterization is based on _Boolean networks_[3, 11]. Boolean networks have a long history, originating from the work of Kauffman in the 1960s [8]. Current applications include a wide variety of research relating to topics varying from biology and medicine to telecommunications and beyond. For recent work, see, e.g., [13, 12].

Boolean networks are usually not defined via a logical syntax, but it is easy to give them one as follows. Consider the set \(\mathcal{T}=\{X_{1},\ldots,X_{k}\}\) of Boolean variables. A _Boolean rule_ over \(\mathcal{T}\) is an expression of the form \(X_{i}\colon-\varphi\) where \(X_{i}\in\mathcal{T}\) is a _head predicate_ and \(\varphi\) is a Boolean formula over the syntax \(\varphi::=\top\mid X_{j}\mid\neg\varphi\mid\varphi\land\varphi\), where \(X_{j}\in\mathcal{T}\). A _Boolean program_ over \(\mathcal{T}\) is then a set of Boolean rules (over \(\mathcal{T}\)), one rule for each \(X_{i}\). Given an input \(f:\mathcal{T}\to\{0,1\}\) and executing the rules in parallel, the program then produces a time-series of \(k\)-bit strings in a natural way (see the preliminaries section for the full details). An extended Boolean program over \(\mathcal{T}\) is a Boolean program over some \(\mathcal{S}\supseteq\mathcal{T}\) together with a _terminal clause_\(X_{j}(0)\colon-b\) for each \(X_{j}\in\mathcal{S}\setminus\mathcal{T}\), where \(b\in\{\top,\bot\}\). Extended programs produce time-series just like regular programs, but they also contain _auxiliary variables_\(X_{j}\in\mathcal{S}\setminus\mathcal{T}\) whose initial value is not part of the input but is instead given via a terminal clause (cf. the preliminaries section). The logic used in this paper, **Boolean network logic** BNL, consists of extended Boolean programs. It turns out that BNL is also closely related to the diamond-free fragment of _modal substitution calculus_ MSC used
in [9] to characterize distributed message passing automata. Calling that fragment SC (for _substitution calculus_), we prove that programs of SC and BNL can be translated to each other with only a linear increase in program size. Thereby our characterization via BNL can alternatively be obtained via SC.

The neural network (NN) model we consider is very general. We allow unrestricted topologies for the underlying directed graphs, including loops, thereby considering the recurrent setting. The reals are modeled via floating-point numbers and the running times are unlimited. We show that for each NN, there exists a corresponding program of BNL that simulates the time series of the NN for each input, and vice versa, BNL-programs can--likewise--be simulated by NNs. Furthermore, the sizes of the NNs and BNL-programs are shown to be polynomially related.

In a bit more detail, let \(S=(p,q,\beta)\) denote a floating-point system with _fraction precision_\(p\), _exponent precision_\(q\) and _base_\(\beta\) (see Section 3.2 for the definitions). Let \(N\) denote the number of nodes in an NN and \(\Delta\) the maximum degree of the underlying graph. Modeling activation functions via piecewise polynomial functions, let \(P\) denote the number of pieces required and \(\Omega\) the maximum order of the involved polynomials. Then the following holds.

**Theorem 4.1**.: _Given a general neural network \(\mathcal{N}\) for \(S=(p,q,\beta)\) with \(N\) nodes, degree \(\Delta\), piece-size \(P\) and order \(\Omega\), we can construct a BNL-program \(\Lambda\) such that \(\mathcal{N}\) and \(\Lambda\) are asynchronously equivalent in \(S\) where for \(r=\max\{p,q\}\),_

1. _the size of_ \(\Lambda\) _is_ \(\mathcal{O}(N(\Delta+P\Omega^{2})(r^{4}+r^{3}\beta^{2}+r\beta^{4}))\)_, and_
2. _the computation delay of_ \(\Lambda\) _is_ \(\mathcal{O}((\log(\Omega)+1)(\log(r)+\log(\beta))+\log(\Delta))\)_._

Here (and also in the below theorem) _asynchronous equivalence_ means that the modeled time series can be repeated but with a delay between _significant computation rounds_. The time delays in our results are not arbitrary but rather modest. For modeling Boolean network logic via a general neural network, let the depth of a program refer to the maximum nesting depth of Boolean formulas appearing in rules. Our result is for NNs that use the activation function \(\operatorname{ReLU}(x)=\max\{0,x\}\), but it can be generalized for other activation functions.

**Theorem 4.2**.: _Given a BNL-program \(\Lambda\) of size \(s\) and depth \(d\), we can construct a general neural network \(\mathcal{N}\) for any floating-point system \(S\) with at most \(s\) nodes, degree at most \(2\), \(\operatorname{ReLU}\) activation functions and computation delay \(\mathcal{O}(d)\) (or \(\mathcal{O}(s)\) since \(s>d\)) such that \(\Lambda\) and \(\mathcal{N}\) are asynchronously equivalent in binary._

It is worth noting that in our setting, while we allow for general topologies and unlimited running times, our systems have inherently finite input spaces. In the framework of NN models, this is a well-justified assumption for a wide variety of modeling purposes. Our results stress the close relations between the size and time resources of general NNs and BNL-programs. Furthermore, as outputs we consider time series rather than a single-output framework. Indeed, it is worth noting that trivially a single Boolean function suffices to model any NN with a finite input space when limiting to single outputs only and not caring about size and time blow-ups in translations.

**Related work.** The closely related topic of descriptive complexity of graph neural networks (or GNNs) has been studied by Barcelo et al. in [2], and by Grohe in [5], [4]. In [5], the GNNs operate via feedforward neural networks, and a natural connection between these models and the circuit complexity class \(\mathsf{TC}^{0}\) is established via logic. The feedforward model in [5] uses _rational piecewise linear approximable_ activation functions, meaning that the parameters of the linear representations of activation functions are finitely representable in
a binary floating-point system. In the current paper, we allow floating-point systems with an arbitrary base, which can be useful, as a change of base often allows inadmissible reals to become admissible. Moreover, our activation functions are piecewise polynomially definable, meaning that most of the widely used activation functions are directly representable in our framework, e.g., ReLU. Furthermore, practically all activation functions are reasonably approximable.

Neural networks are special kinds of distributed systems, and descriptive complexity of distributed computing was initiated in Hella et al. [6], Kuusisto [9] and Hella et al. [7] by relating distributed complexity classes to modal logics. While [6] and [7] gave characterizations to constant-time distributed complexity classes via modal logics, [9] lifted the work to general non-constant-time algorithms by characterizing finite distributed message passing automata via the modal substitution calculus MSC. This was recently lifted to circuit-based networks with identifiers in Ahvonen et al. [1], also utilizing modal substitution calculus. The logic MSC has been linked to a range of other logics. For example, in [9], it is shown to contain the \(\mu\)-fragment of the modal \(\mu\)-calculus, and it is easy to translate MSC into a fragment of partial fixed-point logic. Building on [9], Reiter shows in [10] that this fragment of the modal \(\mu\)-calculus captures finite message passing automata in the asynchronous setting. It is worth noting here that also [2] utilizes modal logic, establishing a match between aggregate-combine graph neural networks and graded modal logic. The logics BNL and SC used in this article are rule-based systems. Rule-based logics are used widely in various applications, involving systems such as Datalog, answer-set programming (ASP) formalisms, and many others.

## 2 Preliminaries

First we introduce some basic concepts. For any set \(S\), we let \(\wp(S)\) denote the power set of \(S\) and we let \(|S|\) denote the size (or cardinality) of \(S\). We let \(\mathbb{N}\) and \(\mathbb{Z}_{+}\) denote the sets of non-negative and positive integers respectively. For every \(n\in\mathbb{Z}_{+}\), we let \([n]=\{1,\dots,n\}\) and \([0;n]=\{0,\dots,n\}\). We let bold lower-case letters \(\mathbf{a},\mathbf{b},\mathbf{c},\dots\) denote strings. The letters of a string are written directly next to each other, i.e. \(abc\), or with dots in-between, i.e. \(a\cdot b\cdot c\), or a mix of both, i.e. \(abc\cdot def\). Omitted segments of strings are represented with three dots, i.e. \(abcd\cdots wxyz\). If \(\mathbf{s}=s_{0}\cdots s_{k-1}\) is a string of length \(k\), then for any \(j\in[0;k-1]\), we let \(\mathbf{s}(j)\) denote the letter \(s_{j}\). The alphabet for the strings will depend on the context. We let \(\mathrm{VAR}=\{\,V_{i}\mid i\in\mathbb{N}\,\}\) denote the (countably infinite) set of all **schema variables**. Mostly, we will use meta variables \(X\), \(Y\), \(Z\) and so on, to denote symbols in \(\mathrm{VAR}\). We assume a linear order \(<^{\mathrm{VAR}}\) over the set \(\mathrm{VAR}\). Moreover, for any set \(\mathcal{T}\subseteq\mathrm{VAR}\), a linear order \(<^{\mathcal{T}}\) is induced by \(<^{\mathrm{VAR}}\). We let \(\mathrm{PROP}=\{\,p_{i}\mid i\in\mathbb{N}\,\}\) denote the (countably infinite) set of **proposition symbols** that is associated with the linear order \(<^{\mathrm{PROP}}\), inducing a linear order \(<^{P}\) over any subset \(P\subseteq\mathrm{PROP}\). We let \(\Pi\subseteq\mathrm{PROP}\) denote a finite subset of proposition symbols.

### Discrete time series

Next we consider infinite sequences of bit strings, i.e., we consider _discrete time series_ of strings over the alphabet \(\{0,1\}\). To separate important strings from less important ones, we need to define when a time series produces an output; importantly, we allow an arbitrary number of outputs. We will define two separate general output conditions for time series. In the first approach, special bits indicate when to output. In the second approach the output rounds are fixed, and we do not include bits that indicate when to output.

The formal definition for the first approach is as follows. Let \(k\in\mathbb{Z}_{+}\) and let \(B\) denote
an infinite sequence \((\mathbf{b}_{j})_{j\in\mathbb{N}}\) of \(k\)-bit strings \(\mathbf{b}_{j}\in\{0,1\}^{k}\). Let \(A\subseteq[k]\) be subset, called **attention** bits and respectively \(P\subseteq[k]\), called **print** bits (or bit positions, strictly speaking). The sets \(A\) and \(P\) induces a corresponding subsequences \((\mathbf{a}_{j})_{j\in\mathbb{N}}\) and \((\mathbf{p}_{j})_{j\in\mathbb{N}}\) of the strings in \(B\). More formally, \((\mathbf{a}_{j})_{j\in\mathbb{N}}\) records the subsequences with positions in \(A\), and respectively \((\mathbf{p}_{j})_{j\in\mathbb{N}}\) records the subsequences with positions in \(P\). Next we define output conditions for \(B\) with respect to attention and print bits. If at least one bit in \(\mathbf{n}_{n}\) is \(1\) (for some \(n\in\mathbb{N}\)), then we say that \(B\)**outputs**\(\mathbf{p}_{n}\) in round \(n\) and that \(n\) is an **output round**. More precisely, \(B\)**outputs in round \(n\) with respect to \((k,A,P)\)**, and \(\mathbf{p}_{n}\) is the **output of \(S\) in round \(n\) with respect to \((k,A,P)\)**. Let \(O\subseteq\mathbb{N}\) be the set of output rounds; they induce a subsequence \((\mathbf{b}_{i})_{i\in O}\) of \(S\). We call the sequence \((\mathbf{p}_{i})_{i\in O}\) the **output sequence** of \(S\).

Next we define an output condition where output rounds are fixed by a set \(O\subseteq\mathbb{N}\) and attention bits are excluded. We say that \(S\)**outputs** in rounds \(O\) (and also, in any particular round \(n\in O\)). Outputs and output sequences w.r.t. \((k,O,P)\) are defined analogously.

We study the two approaches for the sake of generality. The difference between the two output frameworks is that the output rounds are induced internally from within the sequence in the first approach, while they are given externally from the outside in the second one. For instance, it is natural to indicate output conditions within a program if it is part of the program's design. Retroactively, it might be more natural to augment a program to draw attention to rounds the original design doesn't account for, and a different mechanism could be used to compute the output rounds, e.g., a Turing machine.

### Modal substitution calculus MSC and Boolean network logic BNL

We next define modal substitution calculus MSC introduced in [9]. Let \(\Pi\subseteq\) PROP be a finite set of proposition symbols and \(\mathcal{T}\subseteq\) VAR. A **terminal clause** (over \((\Pi,\mathcal{T})\)) is a string of the form \(V_{i}(0)\!:\!-\;\varphi\), where \(V_{i}\in\mathcal{T}\) and \(\varphi\) is defined over the language \(\varphi:=\top\mid p_{i}\mid\neg\varphi\mid\varphi\land\varphi\mid\lozenge\varphi\) where \(p_{i}\in\Pi\) (i.e., \(\varphi\) is a formula of modal logic over \(\Pi\)). An **iteration clause** (over \((\Pi,\mathcal{T})\)) is a string of the form \(V_{i}\!:\!-\;\psi\) where \(\psi\) is a \((\Pi,\mathcal{T})\)**-formula of modal substitution calculus** (or MSC) defined over the language \(\psi:\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! \!\!
conditions discussed for time series. We will later discuss how either can be used to determine a set of output rounds for the program. We use attention predicates by default, and only discuss the attention function when specified.

Usually, a run of a program of MSC is defined over a Kripke-model, but a \((\Pi,\mathcal{T})\)-program of SC is defined over a **model**\(M\) of propositional logic, i.e., \(M\) is a valuation \(\Pi\to\{0,1\}\) assigning a truth value to each proposition symbol in \(\Pi\). The semantics of formulae of propositional logic in model \(M\) are defined as follows: \(M\models p_{i}\) (read: \(p_{i}\) is true in \(M\)) iff the valuation of \(p\) is \(1\), and the semantics of \(\wedge\), \(\neg\) and \(\top\) is the usual one. If \(\Pi^{\prime}\subseteq\Pi\) is the set of proposition symbols that appear in the program, the linear order \(<^{\Pi^{\prime}}\) and the model \(M\) induce a binary string \(\mathbf{i}\in\{0,1\}^{|\Pi^{\prime}|}\) that serves as input, i.e., the \(i\)th bit of \(\mathbf{i}\) is \(1\) iff the valuation of the \(i\)th proposition in \(\Pi^{\prime}\) is \(1\). The truth of a \((\Pi,\mathcal{T})\)-formula \(\psi\) in round \(n\) (written \(M\models\psi^{n}\)) is defined as follows: \(\mathbf{1}\)) \(M\models\top^{n}\) always holds, \(\mathbf{2}\)) \(M\models p_{i}^{n}\) iff \(M\models p_{i}\) (where \(p_{i}\in\Pi\)), \(\mathbf{3}\)) if \(\psi=\neg\theta\), then \(M\models(\neg\theta)^{n}\) iff \(M\not\models\theta^{n}\), \(\mathbf{4}\)) if \(\psi=(\chi\wedge\theta)\), then \(M\models(\chi\wedge\theta)^{n}\) iff \(M\models\chi^{n}\) and \(M\models\theta^{n}\), and \(\mathbf{5}\)) the truth of a head predicate \(X_{i}\) is defined separately as follows. We define that \(M\models X_{i}^{0}\) if \(M\models\varphi_{i}\) where \(\varphi_{i}\) is the body of the terminal clause of \(X_{i}\). Assume we have defined the truth of all \(\mathcal{T}\)-formulae in round \(n\). We define that \(M\models X_{i}^{n+1}\) iff \(M\models\psi_{i}^{n}\) where \(\psi_{i}\) is the body of the iteration clause of \(X_{i}\).

We then define **Boolean network logic** (or BNL) which we will later show to be equivalent to the fragment SC. Boolean network logic gets its name from Boolean networks, which are discrete dynamical systems commonly used in various fields, e.g., biology, telecommunications and various others. For example, they are used to describe genetic regulatory networks (e.g., [8]). A Boolean network consists of a set of Boolean variables, i.e. variables that only get Boolean values \(0\) or \(1\). Each variable is given an initial Boolean value called the "seed". The Boolean values of all variables are updated in discrete steps starting with the seed. In each step, each variable updates its Boolean value using its own Boolean function. The updated value is determined from the Boolean values of all variables in the previous step. There is no general syntax for Boolean networks, but BNL will give us a suitable one.

Let \(\mathcal{T}\subseteq\mathrm{VAR}\). The \(\mathcal{T}\)**-formula of Boolean network logic** (or BNL) is defined over the language \(\psi\coloneqq\top\mid V_{i}\mid\neg\psi\mid\psi\wedge\psi\), where \(V_{i}\in\mathcal{T}\) (i.e. we do not include propositions). Assume now that \(\mathcal{T}\) is a finite and nonempty. There are three main differences between \(\mathcal{T}\)-programs of BNL and SC: \(\mathbf{1}\)) The terminal clauses of BNL are either of the form \(X(0)\!\mathrel{\mathop{:}}-\top\) or \(X(0)\!\mathrel{\mathop{:}}-\bot\). \(\mathbf{2}\)) The bodies of iteration clauses are \(\mathcal{T}\)-formulae of BNL. \(\mathbf{3}\)) Each schema variable in a BNL-program has exactly one iteration clause and either one or zero terminal clauses. We let \(\mathcal{I}\) denote the predicates that do not have terminal clauses, which we call **input predicates**. For example consider a BNL-program with a terminal clause \(X(0)\!\mathrel{\mathop{:}}-\top\) and with an iteration clauses \(Y\!\mathrel{\mathop{:}}-Y\wedge X\) and \(X\!\mathrel{\mathop{:}}-\neg X\). Here \(Y\) is the input predicate and \(X\) acts as an auxiliary predicate. Bodies and head predicates of clauses are defined analogously to SC (and MSC). A BNL-program also includes print predicates and either attention predicates or an attention function \(A\!\mathrel{\mathop{:}}\{0,1\}^{k}\to\wp(\mathbb{N})\), where \(k=|\mathcal{I}|\).

The run of a program of BNL is defined over a **model**\(\mathcal{M}\), i.e. \(\mathcal{M}\) is a valuation \(\mathcal{I}\to\{0,1\}\). Analogously to a model of SC, any model for BNL and the set \(\mathcal{I}\) induce a binary string \(\mathbf{i}\in\{0,1\}^{|\mathcal{I}|}\) that serves as input. (Note that vice versa each string \(\mathbf{i}\in\{0,1\}^{|\mathcal{I}|}\) induces a model with valuation \(\mathcal{I}\to\{0,1\}\) such that \(I_{j}\mapsto\mathbf{i}(j)\) if \(I_{0},\ldots,I_{|I|-1}\) enumerates the set \(\mathcal{I}\) in the order \(<^{\mathrm{VAR}}\).) The truth of a \(\mathcal{T}\)-formula is defined analogously to SC expect for the truth value of head predicates in round \(0\). If \(X\in\mathcal{I}\), we define that \(\mathcal{M}\models X^{0}\) if the valuation of \(X\) in \(\mathcal{M}\) is \(1\). If \(X\notin\mathcal{I}\), then \(\mathcal{M}\models X^{0}\) if the body of the terminal clause of \(X\) is \(\top\).

Let \(X_{1},\ldots,X_{n}\) enumerate the set \(\mathcal{T}\) of schema variables (in the order \(<^{\mathrm{VAR}}\)), \(\Lambda\) be a \(\mathcal{T}\)-program of SC (or BNL), and \(M\) a model for SC (or respectively \(\mathcal{M}\) for BNL) that induces
an input \(\mathbf{i}\in\{0,1\}^{k}\), where \(k\) is the number of proposition symbols (or resp. the number of input predicates). Each time step (or round) \(t\in\mathbb{N}\) defines a **global configuration**\(g_{t}\colon\mathcal{T}\to\{0,1\}\). The global configuration at time step \(t\) is induced by the values of head predicates, i.e., \(g_{t}(X_{i})=1\) iff \(M\models X_{i}^{t}\) (or resp. \(\mathcal{M}\models X_{i}^{t}\)), for each \(X_{i}\in\mathcal{T}\). Thus, an SC-program (or BNL-program) also induces an infinite sequence \((\mathbf{s}_{t})_{t\in\mathbb{N}}\) called the **global configuration sequence** (with input \(\mathbf{i}\)), where \(\mathbf{s}_{t}=g_{t}(X_{1})\cdots g_{t}(X_{n})\). The set of print bits is \(\{\,i\mid X_{i}\in\mathcal{P}\,\}\), where \(\mathcal{P}\) is the set of print predicates. If the program has attention predicates \(\mathcal{A}\), then the set of attention bits is \(\{\,i\mid X_{i}\in\mathcal{A}\,\}\). If the program has an attention function \(A\), then the output rounds are given by \(A(\mathbf{i})\). Therefore, a program of SC or BNL with an input \(\mathbf{i}\) also induces **output rounds** and an **output sequence** w.r.t. \((n,\mathcal{A},\mathcal{P})\) (or resp. w.r.t. \((n,\mathcal{A}(\mathbf{i}),\mathcal{P})\)).

We say that a \((\Pi,\mathcal{T})\)-program of SC and a \(\mathcal{T}^{\prime}\)-program of BNL (or likewise, two BNL-programs) are **asynchronously equivalent** if they have the same output sequences with every input. We say that they are **globally equivalent** if they _also_ have the same global configuration sequences and output rounds with each input (note that identical inputs require that \(|\Pi|=\mathcal{I}\), where \(\mathcal{I}\) is the set of input predicates of the BNL-program).

The **size** of a program of SC or BNL is defined as the number of appearances of \(\top\), proposition symbols \(p_{i}\), head predicates \(V_{i}\) and logical connectives \(\neg\) and \(\land\) in its terminal and iteration clauses. The **depth**\(d(\psi)\) of a BNL-formula or SC-formula is defined recursively such that \(d(p_{i})=d(\top)=d(X)=0\), where \(p_{i}\) is proposition symbol and \(X\) schema variable, \(d(\neg\psi)=d(\psi)+1\) and \(d(\psi\land\theta)=\max\{d(\psi),d(\theta)\}+1\). The **depth** of a BNL-program is the maximum depth of the bodies of iteration clauses.

BNL-programs inherit a number of properties from Boolean networks. Each reachable combination of truth values for the head predicates (i.e., each reachable global configuration) is called a **state** and together they form a **state space**. Note that certain global configurations may not be reachable, because neither they nor their preceding states are possible states at round \(0\) due to the terminal clauses of the BNL-program. Given that the number of states is finite, a BNL-program will eventually either reach a single stable state or begin looping through a sequence of states. A stable state is called a **point attractor**, a **fixed-point attractor** or simply a **fixed point**, whereas a looping sequence of multiple states is a **cycle attractor**. The smallest amount of time it takes to reach an attractor from a given state is called the **transient time** of that state. The **transient time** of a BNL-program is the maximum transient time of a state in its state space [3]. The concept of transient time is also applicable to SC, since it is also deterministic and eventually stabilizes with each input.

Consider the fragment BNL\({}_{0}\) where no head predicate of a program is allowed to have a terminal clause. The programs of this logic BNL\({}_{0}\) are an exact match with Boolean networks; each program encodes a Boolean network, and vice versa. The logic BNL extends this framework by allowing terminal clauses.

A BNL-program that only has fixed points (i.e., no input leads to a cycle attractor) and outputs precisely at fixed points, is called a **halting** BNL-**program**. For a halting BNL-program \(\Lambda\) with input predicates \(\mathcal{I}\) and print predicates \(\mathcal{P}\), each input \(\mathbf{i}\in\{0,1\}^{|\mathcal{I}|}\) results in a single (repeating) **output** denoted by \(\Lambda(\mathbf{i})\), which is the output string determined by the fixed-point values of the print predicates. In this sense, a halting BNL-program is like a function \(\Lambda\colon\{0,1\}^{|\mathcal{I}|}\to\{0,1\}^{|\mathcal{P}|}\). We say that \(\Lambda\)**specifies** a function \(f\colon\{0,1\}^{\ell}\to\{0,1\}^{k}\) if \(|\mathcal{I}|=\ell\), \(|\mathcal{P}|=k\) and \(\Lambda(\mathbf{i})=f(\mathbf{i})\) for all \(\mathbf{i}\in\{0,1\}^{\ell}\). The **computation time** of a halting BNL-program is its transient time.

We introduce two useful tools that are used when constructing BNL-programs (these tools are also definable via MSC or SC). Flagging is one of the most useful tools similar to adding "if-else" conditions in programming. Given two formulae \(\varphi\) and \(\chi\), and a rule \(X:\neg\,\psi\)
**flagging**\(X\) (w.r.t. \(\varphi\) and \(\chi\)) means rewriting the rule \(X\!:\!-\)\(\psi\) as \(X\!:\!-\)\((\varphi\wedge\psi)\vee(\neg\varphi\wedge\chi)\). Now, if \(\varphi\) is true then the truth value of \(X\) depends on the truth value of \(\psi\), and if \(\varphi\) is false then the truth value of \(X\) depends on the truth value of \(\chi\). We call \(\varphi\) the **flag** and \(\chi\) the **backup**. Often \(\chi\) is \(X\) itself meaning that the truth value of \(X\) does not change if \(\varphi\) is false.

A **one-hot counter** is defined as a sequence of schema variables \(T_{0},T_{1},\ldots,T_{n}\) with the terminal clauses \(T_{0}(0)\!:\!-\)\(\top\) and \(T_{i}(0)\!:\!-\)\(\bot\) for all \(i\geq 1\), and iteration clauses \(T_{0}\!:\!-\)\(T_{n}\) and \(T_{i}\!:\!-\)\(T_{i-1}\) for all \(i\geq 1\). Exactly one of these schema variables is true in any one time step, and they turn on in a looping sequence from left to right. \(T_{t}\) is true in round \(t\) for all \(t\leq n\). In round \(n+1\), \(T_{0}\) is true again and the cycle continues. This is ideal for flagging: \(T_{n}\) can be used as a flag for attention predicates to trigger an output round once every \(n\) time steps.

We are ready to prove that BNL is equivalent to SC; for the full proof, see the appendix.

**Theorem 2.1**.: _Each SC-program has an asynchronously equivalent BNL-program of linear size and transient time, and each BNL-program has a globally equivalent SC-program of linear size._

Proof.: (Sketch) From SC to BNL, we create a BNL-program that uses one time step to compute the terminal clauses of the SC-program; the terminal clauses of the SC-program are embedded into the iteration clauses of the BNL-program using a flag. From BNL to SC, we amend the BNL-program with the missing terminal clauses using proposition symbols. 

## 3 Arithmetic with BNL

In this section we first show how to carry out integer addition and multiplication in Boolean network logic in parallel. We then extend this demonstration to floating-point arithmetic, including floating-point polynomials and piecewise polynomial functions.

The algorithms we use for integers are mostly well known and thus some of the formal details are in the appendix. Informally, the idea is to split both addition and multiplication into simple steps that are executed in parallel. We will show that we can simulate integer arithmetic (respectively, floating-point arithmetic) by programs whose size is polynomial in the size of the integers (resp., respectively in the size of the floating-point system). We also analyze the time delays of the constructed programs. The time delay is polylogarithmic in the size of the integers (and resp. in the size of the floating-point system) and sometimes even a constant. Ultimately, the same applies to floating-point polynomials and piecewise polynomial functions.

### Integer arithmetic

We next define how a _halting_ BNL-program simulates integer functions in an arbitrary base \(\beta\in\mathbb{Z}\), \(\beta\geq 2\). Informally, we represent integers with bit strings that are split into substrings of length \(\beta\), where exactly one bit in each substring is \(1\) and the others are \(0\). Formally, let \(\mathbf{s}_{1},\ldots,\mathbf{s}_{k}\in\{0,1\}^{\beta}\) be **one-hots**, i.e. bit strings with exactly one \(1\). We say that \(\mathbf{s}=\mathbf{s}_{1}\cdots\mathbf{s}_{k}\)**corresponds** to \(b_{1}\cdots b_{k}\in[0;\beta-1]^{k}\) if for every \(b_{i}\), we have \(\mathbf{s}_{i}(b_{i})=1\) (and other values in \(\mathbf{s}_{i}\) are zero). For example, if \(\beta=5\), then \(00100\cdot 01000\cdot 00001\in\{0,1\}^{\beta.3}\) corresponds to \(2\cdot 1\cdot 4\in[0;4]^{3}\). We say that \(\mathbf{s}\) is a **one-hot representation** of \(b_{1}\cdots b_{k}\).

Using the binary one-hot representations, we can present integers in BNL by assigning each bit with a head predicate that is true if and only if the bit is \(1\). The sign (\(+\) or \(-\)) of a number can likewise be handled with a single bit that is true iff the sign is positive.
**Definition 3.1**.: Let \(\beta\in\mathbb{Z}\), \(\beta\geq 2\) be a base. We say that a halting BNL-program \(\Lambda\)**simulates** (or computes) a function \(f\colon\left[0;\beta-1\right]^{\ell}\to\left[0;\beta-1\right]^{k}\) if for each input string \(\mathbf{i}\in\{0,1\}^{\ell\beta}\) that corresponds to \(\mathbf{b}\in\left[0;\beta-1\right]^{\ell}\), the output \(\Lambda(\mathbf{i})\) also corresponds to \(f(\mathbf{b})\).

#### Parallel addition

In this section we construct a parallel integer addition algorithm via BNL-programs. The algorithm is mostly well known and is based on how integer addition is computed in Nick's class \(\mathsf{NC}^{1}\) (sometimes called the carry-lookahead method), i.e., we parallelize the textbook method (sometimes called the long addition algorithm). Here the main difference to integer addition in Nick's class is that we generalize the algorithm for arbitrary bases.

**Lemma 3.2**.: _Given a base \(\beta\in\mathbb{Z}\), \(\beta\geq 2\) and \(p\in\mathbb{Z}_{+}\), adding two numbers in \([0;\beta-1]^{p}\) can be simulated with a (halting) \(\mathrm{BNL}\)-program of size \(\mathcal{O}(p^{3}+p\beta^{2})\) and computation time \(\mathcal{O}(1)\)._

Proof.: (Sketch) The full formal program and more rigorous explanations are in the appendix. Informally, the textbook method of adding integers (in arbitrary base \(\beta\)) is done by aligning the digits vertically and adding the single digits one-by-one from right to left. If the sum of digits exceeds \(\beta-1\), then \(1\) is _carried_ to the next addition on the left, i.e, \(1\) is a _carry_. The main difference to parallel integer addition is that the addition is done simultaneously and the hard part is to compute carries in parallel. In order to compute a carry, we have to check if the other additions to the right lead to a carry. It is straightforward to write a BNL-program that computes carries in \(\mathcal{O}(p^{3}+p\beta^{2})\) space and \(\mathcal{O}(1)\) time steps. 

#### Parallel multiplication

In this section we introduce a parallel multiplication algorithm. The parallelization method is mostly well known and is based on "cutting" multiplication to simple addition tasks.

**Lemma 3.3**.: _Given a base \(\beta\in\mathbb{Z}\), \(\beta\geq 2\), multiplication of any two numbers in \([0;\beta-1]^{p}\) can be simulated with a (halting) \(\mathrm{BNL}\)-program of size \(\mathcal{O}(p^{4}+p^{3}\beta^{2}+p\beta^{4})\) and computation time \(\mathcal{O}(\log(p)+\log(\beta))\)._

Proof.: (Sketch) The formal explanations and examples are in the appendix. Assume that we have two \(p\)-digit integers (we allow leading zeros) a multiplicand \(\mathbf{x}\) and a multiplier \(\mathbf{y}=y_{p}\cdots y_{1}\) in an arbitrary base \(\beta\in\mathbb{Z}\), \(\beta\geq 2\). The parallel multiplication algorithm computes in the following two steps. **(1)** We run \(p\) different multiplications in parallel where the multiplicand \(\mathbf{x}\) is multiplied by \(y_{l}0\cdots 0\) with \(i-1\) zeros on the right (for each \(i\in[p]\) in base \(\beta\)). Each multiplication is actually also computed in parallel by using the parallel addition algorithm to obtain relatively small space and time complexities. As a result we obtain \(p\) different numbers of length \(2p\). **(2)** We add the numbers obtained in the first step together in parallel using the parallel addition algorithm. 

### Floating-point arithmetic

In this section we consider floating-point arithmetic, including polynomials and piecewise polynomial functions. We show that BNL-programs can simulate these in polynomial space and in polylogarithmic time, and some simple arithmetic operations even in constant time.
### Floating-point system

A **floating-point number** in a system \(S=(p,q,\beta)\) (where \(p,q,\beta\in\mathbb{Z}_{+}\), \(\beta\geq 2\)) is a number that can be represented in the form

\[\pm\underbrace{0.d_{1}d_{2}\cdots d_{p}}_{=f}\times\beta^{\pm e_{1}\cdots e_{ q}},\]

where \(d_{i},e_{i}\in[0;\beta-1]\). For such a number in system \(S\), we call \(f\) the **fraction**, the dot between \(0\) and \(d_{1}\) the **radix point**, \(p\) the **precision**, \(e=\pm e_{1}\cdots e_{q}\) the **exponent**, \(q\) the **exponent precision** and \(\beta\) the **base** (or **radix**).

A floating-point number in a system \(S\) may have many different representations such as \(0.10\times 10^{1}\) and \(0.01\times 10^{2}\) which are both representations of the number \(1\). To ensure that our calculations are well defined, we desire a single form for all non-zero numbers. We say that a floating-point number (or more specifically, a floating-point representation) is **normalized**, if \(d_{1}\neq 0\), or if \(f=0\), \(e\) is the smallest possible value and the sign of the fraction is \(+\).

For a floating-point system \(S=(p,q,\beta)\), we define an extended system of **raw floating-point numbers**\(S^{+}(p^{\prime},q^{\prime})\) (where \(p^{\prime}\geq p\) and \(q^{\prime}\geq q\)) that possess a representation of the form \(\pm d_{0}.d_{1}d_{2}\cdots d_{p^{\prime}}\times\beta^{\pm e_{1}\ldots e_{q^{ \prime}}}.\) When performing floating-point arithmetic, the precise outcomes of the calculations may be raw numbers, i.e., no longer in the same system as the operands strictly speaking. Therefore, in practical scenarios, we have \(p^{\prime}=\mathcal{O}(p)\) and \(q^{\prime}=\mathcal{O}(q)\). Consider, e.g., the numbers \(99\) and \(2\) which are both in the system \(S=(2,1,10)\), but their sum \(101\) is not, because \(3\) digits are required to represent the fraction precisely. For this purpose, we must round numbers. The easiest way to round a number is **truncation**, where the least significant digits of the number are simply omitted, rounding the number toward zero. The most common method is to round to the nearest floating-point number, with ties rounding to the number with an even least significant digit. This is called **round-to-nearest ties-to-even**. Truncation can be performed in BNL with constant space and time, but the latter rounding method requires \(\mathcal{O}(p^{2}\beta^{2})\) space and \(\mathcal{O}(1)\) time steps. It is trivial to construct a BNL-program that computes rounding, so we do not go into detail.

### Representing floating-point numbers in binary

Our way of representing floating-points of arbitrary base in binary is based on international standards (e.g. IEEE 754). Informally, if \(\mathbf{b}\) represents a floating-point number in a system \(S=(p,q,\beta)\), then the first two bits encode the signs of the exponent and fraction. The next \(q\beta\) bits encode the exponent in base \(\beta\), and the last \(p\beta\) bits encode the fraction in base \(\beta\).

Before we go into the details, we have to define simulation of functions that compute with floating-point numbers in a system \(S=(p,q,\beta)\). Let \(F=\pm f\times\beta^{\pm e}\) be a floating-point number in system \(S\). Let \(\mathbf{p}_{1},\mathbf{p}_{2}\in\{0,1\}\) and \(\mathbf{s}_{1},\ldots,\mathbf{s}_{q},\mathbf{s}_{1}^{\prime},\ldots,\mathbf{s}_ {p}^{\prime}\in\{0,1\}^{\beta}\). We say that \(\mathbf{s}=\mathbf{p}_{1}\mathbf{p}_{2}\mathbf{s}_{1}\cdots\mathbf{s}_{q} \mathbf{s}_{1}^{\prime}\cdots\mathbf{s}_{p}^{\prime}\)**corresponds** to \(F\) (or \(\mathbf{s}\) is a **one-hot representation** of \(F\)) if **(1)**\(\mathbf{p}_{1}=1\) iff the sign of the exponent is \(+\), **(2)**\(\mathbf{p}_{2}=1\) iff the sign of the fraction is \(+\), **(3)**\(\mathbf{s}_{1}\cdots\mathbf{s}_{q}\) corresponds to \(e=e_{1}\cdots e_{q}\), and **(4)**\(\mathbf{s}_{1}^{\prime}\cdots\mathbf{s}_{p}^{\prime}\) corresponds to \(f=0.d_{1}d_{2}\cdots d_{p}\) (or, more precisely, to \(d_{1}\cdots d_{p}\)). Likewise, we say that a bit string \(\mathbf{s}\)**corresponds** to a sequence \((F_{1},\ldots,F_{k})\) of floating-point numbers if \(\mathbf{s}\) is the concatenation of the bit strings that correspond to \(F_{1},\ldots,F_{k}\) from left to right. For example, in the system \(S=(4,3,3)\) the number \(-0.2001\times 3^{+120}\) has the corresponding string \(\underbrace{1}_{\mathbf{p}_{1}}\cdot\underbrace{0}_{\mathbf{p}_{2}}\cdot \underbrace{010\cdot 001\cdot 100}_{\mathbf{s}_{1}\mathbf{s}_{2}\mathbf{s}_{3}}\cdot \underbrace{001\cdot 100\cdot 100\cdot 010}_{\mathbf{s}_{1}^{\prime}\mathbf{s}_{ 1}^{\prime}\mathbf{s}_{s}^{\prime}\mathbf{s}_{s}^{\prime}\mathbf{s}_{s}^{ \prime}\mathbf{s}_{4}^{\prime}}\)
**Definition 3.4**.: Let \(S=(p,q,\beta)\) be a floating-point system. We say that a halting BNL-program \(\Lambda\)**simulates** a function \(f\colon S^{\ell}\to S^{k}\), if the output \(\Lambda(\mathbf{i}_{1}\cdots\mathbf{i}_{\ell})\) corresponds to \(f(F_{1},\ldots,F_{\ell})\) for any \(F_{1},\ldots,F_{\ell}\in S\) and the corresponding inputs \(\mathbf{i}_{1},\ldots,\mathbf{i}_{\ell}\in\{0,1\}^{2+\beta(p+q)}\).

Later when we construct programs for the floating-point operations e.g. normalization, we will use a tool called **shifting**, which means moving each digit of a fraction to the left or right by one (e.g. shifting a fraction \(0.012\) once to the left leads to \(0.120\))

#### Normalizing a floating-point number

We informally describe how the normalization of raw floating-point numbers can be done. By normalization we mean that a raw floating-point number is normalized as described above.

**Lemma 3.5**.: _Let \(S=(p,q,\beta)\) be a floating-point system. Normalization of a raw floating-point number in \(S^{+}(p^{\prime},q^{\prime})\) to the floating-point system \(S\), where \(p^{\prime}=\mathcal{O}(p)\) and \(q^{\prime}=\mathcal{O}(q)\), can be simulated with a (halting) \(\mathrm{BNL}\)-program of size \(\mathcal{O}(r^{3}+r^{2}\beta^{2})\) and computation time \(\mathcal{O}(1)\), where \(r=\max\{p,q\}\)._

Proof.: The full formal explanations and details are in the appendix. Let \(S=(p,q,\beta)\) be a floating-point system. The normalization of a raw floating-point number \(f\times\beta^{e}\) (we do not write down the signs here) in system \(S^{+}(p^{\prime},q^{\prime})\) to the system \(S\), where \(p^{\prime}=\mathcal{O}(p)\) and \(q^{\prime}=\mathcal{O}(q)\) can be split into the following cases.

1. If \(f=0\), we only set \(e\) to the smallest possible value and the sign of the fraction to \(+\).
2. If \(|f|<1\), then we can calculate in a few steps how much we have to shift the fraction to the left (and increase the exponent).
3. If \(|f|\geq 1\), we shift the fraction to the right by one (and decrease the exponent by one) and, after that, round the number to match precision \(p\). The rounding might lead to a non-normalized floating-point number, but we only have to shift the number to the right again at most once (because after rounding, \(|f|\leq\beta-1\)).

The hard part is to keep the time complexity as low as possible. We do not go into the details here (full proofs are in the appendix), but the main idea is to apply parallel integer addition specified in Section 3.1. 

#### Addition of floating-point numbers

In this section we show that we can simulate floating-point addition via BNL-programs, which can be done even in constant time.

**Lemma 3.6**.: _Addition of two (normalized) floating-point numbers in \(S=(p,q,\beta)\) can be simulated with a (halting) \(\mathrm{BNL}\)-program of size \(\mathcal{O}(r^{3}+r^{2}\beta^{2})\) and computation time \(\mathcal{O}(1)\), where \(r=\max\{p,q\}\)._

Proof.: (Sketch) We then very roughly sketch how the addition of two normalized floating-point numbers can be done; the full explanations are in the appendix. The parts where we add or normalize numbers, we apply the results obtained in earlier sections. The addition is done in the following steps. **(1)** We compare which of the exponents is greater and store it. **(2)** We determine the difference \(d\) between the exponents. If \(d\) is greater than the length of the fractions, we are done and output the number with the greater exponent. If \(d\) is
smaller than the length of the fractions, then we shift the fraction of the number with the smaller exponent to the right \(d\) times. We then perform integer addition on the fractions and store the result. **(3)** We obtain a number whose exponent was obtained in the first step and whose fraction was obtained in the second step. We normalize this number. 

#### Multiplication of floating-point numbers

In this section we show how to simulate floating-point multiplication via BNL-programs. The multiplication takes logarithmic time, since the proof applies integer multiplication results obtained in Lemma 3.1.

**Lemma 3.7**.: _Multiplication of two (normalized) floating-point numbers in \(S=(p,q,\beta)\) can be simulated with a (halting) BNL-program of size \(\mathcal{O}(r^{4}+r^{3}\beta^{2}+r\beta^{4})\) and computation time \(\mathcal{O}(\log(r)+\log(\beta))\), where \(r=\max\{p,q\}\)._

Proof.: (Sketch) We roughly sketch how the multiplication of two (normalized) floating-point numbers is done; the full explanations are in the appendix. Informally, we do the following.

1. We add the exponents together by using the parallel (integer) addition algorithm and store the result. If the result is less than the maximum exponent, we move to the next step. Otherwise, we are done and output the largest possible number, i.e. the number with the highest possible fraction and exponent in the system.
2. We multiply the fractions using the integer multiplication algorithm and store the product.
3. We obtain a number whose exponent was obtained in the first step and whose fraction was obtained in the second step. We normalize this number.

Applying the results of parallel (integer) addition, parallel (integer) multiplication, and normalization described in the previous sections, we obtain the wanted results. 

#### Floating-point polynomials and piecewise polynomial functions

Next we consider floating-point polynomials and activation functions that are piecewise polynomial. A **piecewise polynomial** function (with a single variable) is defined as separate polynomials over certain intervals of real numbers. For instance, the function "\(f(x)=x^{2}\) when \(x\geq 0\) and \(f(x)=-x\) when \(x<0\)" is piecewise polynomial; the intervals are the sets of non-negative and negative numbers and the attached polynomials are \(x^{2}\) and \(-x\). In a floating-point system, a piecewise polynomial function is an approximation, much like addition and multiplication. We perform approximations after each addition and multiplication; as a result, the calculations must be performed in some canonical order because the order of approximations will influence the result. By the number of pieces, we refer to the number of intervals that the piecewise polynomial function is defined over; our example above has 2 pieces. We obtain the following theorem.

**Theorem 3.8**.: _Assume we have a piecewise polynomial function \(\alpha\colon S\to S\), where each polynomial is of the form \(a_{n}x^{n}+\cdots+a_{1}x+a_{0}\) where \(n\in\mathbb{N}\), \(a_{i}\in S=(p,q,\beta)\) for each \(0\leq i\leq n\) and \(r=\max\{p,q\}\) (addition and multiplication approximated in \(S\)). Let \(\Omega\) be the highest order of the polynomials (or \(1\) if the highest order is \(0\)) and let \(P\in\mathbb{Z}_{+}\) be the number of pieces. We can construct a BNL-program \(\Lambda\) that simulates \(\alpha(x)\) such that_

1. _the size of_ \(\Lambda\) _is_ \(\mathcal{O}(P\Omega^{2}(r^{4}+r^{3}\beta^{2}+r\beta^{4}))\)_, and_
2. _the computation time of_ \(\Lambda\) _is_ \(\mathcal{O}((\log(\Omega)+1)(\log(r)+\log(\beta)))\)_._

Proof.: (Sketch) We only roughly sketch the proof. The full proof can be found in the appendix. We obtain BNL-programs that simulate these functions in polynomial space and polylogarithmic time. When calculating a floating-point polynomial \(a_{n}x^{n}+\cdots+a_{1}x+a_{0}\), the order of calculations is as follows: Multiplications are handled first. When carrying out the multiplication \(x_{1}\cdot x_{2}\cdot\ldots\cdot x_{k}\), we simultaneously calculate the products \(y_{1}=x_{1}\cdot x_{2}\), \(y_{2}=x_{3}\cdot x_{4}\), etc. (If \(k\) is an odd number, the multiplicand \(x_{k}\) has no pair. In this case we define \(y_{(k+1)/2}=x_{k}\).) Then, in similar fashion we calculate the products \(z_{1}=y_{1}\cdot y_{2}\), \(z_{2}=y_{3}\cdot y_{4}\), etc. We continue this until we have calculated the whole product. After multiplications, we handle the sums in identical fashion. We obtain the wanted results by simulating the additions and multiplications of each polynomial as described in Lemmas 3.6 and 3.7. 

## 4 Descriptive complexity for general neural networks

In this section, we establish connections between Boolean network logic and neural networks. Informally, we define a general neural network as a weighted directed graph (with any topology) operating on floating-point numbers in some system \(S\). Each node receives either a fixed initial value or an input as its first activation value. In each communication round a node sends its activation value to its neighbours and calculates a new activation value as follows. Each node multiplies the activation values of its neighbours with associated weights, adds them together with a node-specific bias and feeds the result into a node-specific activation function. Note that floating-point systems are bounded, and the input-space of a neural network is thus finite.

Next we define neural networks formally. A **(directed) graph** is a tuple \((V,E)\), where \(V\) is a finite set of **nodes** and \(E\subseteq V\times V\) is a set of **edges**. Note that we allow self-loops on graphs, i.e. edges \((v,v)\in E\). A **general neural network**\(\mathcal{N}\) (for floating-point system \(S\)) is defined as a tuple \((G,\mathfrak{a},\mathfrak{b},\mathfrak{w},\pi)\), where \(G=(V,E,<^{V})\) is a directed graph associated with a linear order \(<^{V}\) for nodes in \(V\). The network \(\mathcal{N}\) contains sets \(I,O\subseteq V\) of **input** and **output** nodes respectively, and a set \(H=V\setminus(I\cup O)\) of **hidden nodes**. The tuples \(\mathfrak{a}=(\alpha_{v})_{v\in V}\) and \(\mathfrak{b}=(b_{v})_{v\in V}\) are assignments of a piecewise polynomial **activation function**\(\alpha_{v}\colon S\to S\) and a **bias**\(b_{v}\in S\) for each node. Likewise, \(\mathfrak{w}=(w_{e})_{e\in E}\) is an assignment of a **weight**\(w_{e}\in S\) for each edge. The function \(\pi\colon(V\setminus I)\to S\) assigns an initial value to each non-input node.

The computation of a general neural network is defined with a given input function \(i\colon I\to S\). Similarly to BNL-programs, an input function \(i\) also induces a floating-point string \(\mathbf{i}\in S^{|I|}\), and respectively a floating-point string induces an input function. **The state of the network at time \(t\)** is a function \(g_{t}\colon V\to S\), which is defined recursively as follows. For \(t=0\), we have \(g_{0}(v)=i(v)\) for input nodes and \(g_{0}(v)=\pi(v)\) for non-input nodes. Now assume we have defined the state at time \(t\). The state at time \(t+1\) is defined as follows:

\[g_{t+1}(v)=\alpha_{v}\Big{(}b_{v}+\sum_{(u,v)\in E}\big{(}g_{t}(u)\cdot w_{(u, v)}\big{)}\,\Big{)}.\]

More specifically, the sum is unfolded from left to right according to the order \(<^{V}\) of the nodes \(u\in V\). For each piece of an activation function, we assume a normal form \(a_{n}x^{n}+\cdots+a_{1}x+a_{0}\), which designates the order of operations. If we designate that \(u_{1},\ldots,u_{k}\) enumerate the set \(O\) of output nodes in the order \(<^{V}\), then the state of the system induces an output tuple \(o_{t}=(g_{t}(u_{1}),\ldots,g_{t}(u_{k}))\) at time \(t\) for all \(t\geq 0\).
We once again define two frameworks for picking out important output rounds, one machine-internal and one machine-external framework. In the first framework, the set \(V\) contains a set \(A\) of attention nodes \(u\), each of which is associated with a _threshold_\(s\in S\). If the activation value \(u\) of one of the attention nodes exceeds its threshold in some round \(t\), i.e., \(g_{t}(u)\geq s\), then \(t\) is an output round. In the second framework, we instead have an attention function of type \(a\colon S^{|I|}\to\wp(\mathbb{N})\) that assigns a set of output rounds for each input of the network; in this framework, there are no attention nodes. Analogously to BNL-programs, a neural network with \(n\) nodes, input \(\mathbf{i}\in S^{|I|}\) and either attention bits (or respectively an attention function), induces an **output sequence** and **output rounds** w.r.t. \((n,A,O)\) (or, respectively, w.r.t. \((n,a(\mathbf{i}),O)\)).

We then define some parameters that will be important when describing how neural networks and BNL-programs are related in terms of space and time complexity. The in-degree of a node \(v\) is the number of nodes \(u\) such that there is an edge \((u,v)\in E\); we say that \(u\) is a **neighbour** of \(v\). Note that we allow reflexive loops so a node might be its own "neighbour". The **degree** of a general neural network \(\mathcal{N}\) is the maximum in-degree of the underlying graph. The **piece-size** of \(\mathcal{N}\) is the maximum number of "pieces" across all its piecewise polynomial activation functions. The **order** of \(\mathcal{N}\) is the highest order of a "piece" of its piecewise polynomial activation functions.

A general neural network can easily emulate typical _feedforward neural networks_. This requires that the graph of the general neural network is connected and acyclic, the sets \(I\), \(O\) and \(H\) are chosen correctly and the graph topology is as required, with all paths from an input node to an output node being of the same length. Unlike in a classical feedforward neural network, the hidden and output nodes of a general neural network have an initial value, but they are erased as the calculations flow through the network, so this is an inconsequential, essentially syntactic phenomenon. The inputs are also erased in the same way, likewise an inconsequential syntactic phenomenon. Finally, there is a round \(t\) where the general neural network outputs the same values as a corresponding feedforward network would.

In general, our neural network models are _recurrent_ in the sense that they allow loops. They are _one-to-many_ networks, in other words, they can map each input to a sequence of outputs unlike feedforward neural networks which always map each input to a single output.

In order to translate neural networks to BNL-programs and vice versa, we define time series problems for both floating-point numbers and binary numbers, and two types of corresponding equivalence relations. The reason for this is obvious, as BNL-programs operate with binary numbers and neural networks with floating-point numbers. Informally, in the below asynchronous equivalence means that the modeled time series can be repeated but with a delay between output rounds. The time delays in our results are not arbitrary but rather modest. Moreover, we do not fix the attention mechanism for the programs or neural networks, and our definitions work in both cases.

First we define notions for floating-points. Let \(k,\ell\in\mathbb{N}\), \(P\subseteq[k]\) and let \(S=(p,q,\beta)\) be a floating-point system. We let \(\mathcal{F}(k,P,S)\) denote the family of sequences \(F=(\mathbf{f}_{n})_{n\in\mathbb{N}}\) of \(k\)-strings \(\mathbf{f}_{n}\in S^{k}\) of numbers in \(S\) with print position set \(P\). A **(floating-point) time series problem \(\mathfrak{P}\) for \((\ell,k,P)\) in \(S\)** is a function \(\mathfrak{P}\colon S^{\ell}\to\mathcal{F}(k,P,S)\times\wp(\mathbb{N})\). With a given input \((F_{1},\ldots,F_{\ell})\in S^{\ell}\), \(\mathfrak{P}\) gives a sequence \((\mathbf{f}_{n})_{n\in\mathbb{N}}\in\mathcal{F}(k,P,S)\) and a subset \(O\subseteq\mathbb{N}\) and therefore \(\mathfrak{P}\) induces the output sequences of \((\mathbf{f}_{n})_{n\in\mathbb{N}}\) w.r.t. \((k,O,P)\). Let \(\Lambda\) be a BNL-program with \((\beta(p+q)+2)|P|\) print predicates and \((\beta(p+q)+2)\ell\) input predicates. We say that \(\Lambda\)**simulates a solution** for time series problem \(\mathfrak{P}\) if for every input \(\mathbf{i}\in\{0,1\}^{(\beta(p+q)+2)\ell}\) corresponding to \((F_{1},\ldots,F_{\ell})\in S^{\ell}\), the output sequence of \(\Lambda\) with input \(\mathbf{i}\) corresponds to the output sequence induced by \(\mathfrak{P}(F_{1},\ldots,F_{\ell})\), i.e., the output
strings of \(\Lambda\) correspond to the output strings of \(\mathfrak{P}\). A neural network \(\mathcal{N}\) with \(\ell\) input nodes and \(|P|\) print nodes **solves**\(\mathfrak{P}\) if the output sequence of \(\mathcal{N}\) with input \((F_{1},\dots,F_{\ell})\) is the output sequence of \(\mathfrak{P}(F_{1},\dots,F_{\ell})\). We say that a BNL-program \(\Lambda\) and a neural network \(\mathcal{N}\) (for \(S\)) are **asynchronously equivalent in \(S\)** if the time series problems in \(S\) simulated by \(\Lambda\) are exactly the ones solved by \(\mathcal{N}\).

We define notions for binaries in similar fashion. Recall that \(k,\ell\in\mathbb{N}\), \(P\subseteq[k]\). Similarly, let \(\mathcal{S}(k,P)\) denote the family of \(k\)-bit strings sequences \(B=(\mathbf{b}_{n})_{n\in\mathbb{N}}\) with print bit set \(P\). A **(binary) time series problem \(\mathfrak{P}\) for \((\ell,k,P)\)** is a function \(\mathfrak{P}\colon\{0,1\}^{\ell}\to\mathcal{S}(k,P)\times\wp(\mathbb{N})\) that assigns a \(k\)-bit string sequence and a set \(O\in\wp(\mathbb{N})\) of output rounds to every input \(\mathbf{i}\in\{0,1\}^{\ell}\); together they induce an output sequence w.r.t. \((k,O,P)\). We say that a BNL-program (or neural network) \(x\) with \(\ell\) input predicates (resp., input nodes) and \(|P|\) print predicates (resp., print nodes) **solves**\(\mathfrak{P}\) if the output sequence of \(x\) with any input \(\mathbf{i}\in\{0,1\}^{\ell}\) is the output sequence of \(\mathfrak{P}(\mathbf{i})\). Note that actually, a neural network handles \(0\) and \(1\) in floating-point representation. We say that a BNL-program and a general neural network are **asynchronously equivalent in binary** if they solve the same binary time series problems.

We define the delay between two asynchronously equivalent objects \(x\) and \(y\). Let \(x_{1},x_{2},\dots\) and \(y_{1},y_{2},\dots\) enumerate their (possibly infinite) sets of output rounds in ascending order. Assume that the cardinality of the sets of output rounds is the same and \(x_{n}\geq y_{n}\) for every \(n\in\mathbb{N}\). If \(T\) is the smallest amount of time steps such that \(T\cdot y_{n}\geq x_{n}\) for every \(n\in\mathbb{N}\), then we say that the **computation delay** of \(x\) is \(T\). The case for \(y_{n}\geq x_{n}\) is analogous.

### From NN to BNL

We provide a translation from general neural networks to Boolean network logic. The proof is based on the results obtained for floating-point arithmetic in the previous section.

**Theorem 4.1**.: _Given a general neural network \(\mathcal{N}\) for \(S=(p,q,\beta)\) with \(N\) nodes, degree \(\Delta\), piece-size \(P\) and order \(\Omega\) (or \(1\) if the highest order is \(0\)), we can construct a BNL-program \(\Lambda\) such that \(\mathcal{N}\) and \(\Lambda\) are asynchronously equivalent in \(S\) where for \(r=\max\{p,q\}\),_

1. _the size of_ \(\Lambda\) _is_ \(\mathcal{O}(N(\Delta+P\Omega^{2})(r^{4}+r^{3}\beta^{2}+r\beta^{4}))\)_, and_
2. _the computation delay of_ \(\Lambda\) _is_ \(\mathcal{O}((\log(\Omega)+1)(\log(r)+\log(\beta))+\log(\Delta))\)_._

Proof.: First we consider the framework where output rounds are defined by attention nodes and attention predicates. We consider the setting where output rounds are fixed as a corollary.

We use separate head predicates \(S_{u,e}\), \(S_{u,f}\), \(E_{u,i,b}\), and \(F_{u,j,b}\) (\(i\in[q]\), \(j\in[p]\), \(b\in[0;\beta-1]\)) for each node \(u\) of \(\mathcal{N}\). Together, they encode the **1)** exponent sign, **2)** fraction sign, **3)** exponent and **4)** fraction of the activation values of \(u\) in one-hot representation as described in Section 3.2. These calculations are done using the arithmetic algorithms from the same section. The program can not calculate a new activation value in one step like a neural network does, as each arithmetic operation takes some time to compute. The input of a single node is a floating-point number with \(q\) digits for the exponent, \(p\) digits for the fraction, and a sign for both. Its one-hot representation therefore has \((p+q)\beta+2\) bits; exactly the number of head predicates assigned for each node. Each of these nodes receives a corresponding bit as input. For instance, if the input floating-point number of \(u\) is \(-0.314\times 10^{+01}\), then the head predicates \(S_{u,e}\), \(E_{u,1,0}\), \(E_{u,2,1}\), \(F_{u,1,3}\), \(F_{u,2,1}\) and \(F_{u,3,4}\) get the input \(1\) while all the other head predicates for \(u\) get the input \(0\).
After receiving these inputs, the rest of the program is built by applying the programs for floating-point addition and multiplication constructed in Section 3.2 to the aggregations and activation functions of each node in the established canonical order of operations. The calculations are timed with a one-hot counter, i.e., predicates \(T_{0},\ldots,T_{n}\) as described in Section 2.2. Here \(n\) is the worst-case number of rounds required for the algorithms to calculate an activation value for a node in the network (based on the number of neighbours, as well as the order and number of pieces of the activation function). The predicates in this counter are used to stall the head predicates for each node such that they receive the bits corresponding to the new activation values at the same time (this includes the output predicates, which are all the predicates corresponding to output nodes). The attention nodes have additional predicates that correspond to the threshold values; during rounds where the activation values have been calculated, an attention predicate turns true if this value is exceeded.

We compute additions and multiplications for each node in the network; this can be done simultaneously for each node. Each node requires at most \(\Delta\) multiplications and additions in the aggregation before the use of the activation function. Multiplications can be done simultaneously and sums in parallel as described in section 3. These steps require size \(\mathcal{O}(N\Delta(r^{4}+r^{3}\beta^{2}+r\beta^{4}))\) (each of the \(N\) nodes performs \(\mathcal{O}(\Delta)\) multiplications/additions; the size of the multiplication is \(\mathcal{O}(r^{4}+r^{3}\beta^{2}+r\beta^{4})\) which dwarfs the addition size \(\mathcal{O}(r^{3}+r^{2}\beta^{2}))\) and the overall time required is \(\mathcal{O}(\log(r)+\log(\beta))+\mathcal{O}(\log(\Delta))\) (multiplication + addition).

After the aggregation come the activation functions. Since they are piecewise polynomial, we may apply Theorem 3.8, using the piece-size and order of the network. If \(\Omega=0\) we are done, so assume that \(\Omega\in\mathbb{Z}_{+}\). Each of the \(N\) nodes calculates at most \(P\) polynomial pieces of order at most \(\Omega\), which gives us a size of \(\mathcal{O}(NP\Omega^{2}(r^{4}+r^{3}\beta^{2}+r\beta^{4}))\). This requires only \(\mathcal{O}((\log(\Omega)+1)(\log(r)+\log(\beta)))\) time. The same predicates are used for the calculation of each subsequent global configuration of the network. Timing the calculations does not increase the size and time complexity. Adding the sizes and times together, the size of the program is \(\mathcal{O}(N(\Delta+P\Omega^{2})(r^{4}+r^{3}\beta^{2}+r\beta^{4}))\) and computing each global configuration of \(\mathcal{N}\) requires time \(\mathcal{O}(\log(r)+\log(\beta))+\mathcal{O}(\log(\Delta))+\mathcal{O}((\log( \Omega)+1)(\log(r)+\log(\beta)))=\mathcal{O}((\log(\Omega)+1)(\log(r)+\log( \beta))+\log(\Delta))\); the first \(\mathcal{O}(\log(r)+\log(\beta))\) is not dwarfed if \(\Omega=1\).

The case for the second framework, where output rounds are given from the outside, is obtained as a corollary. We simply take the worst case time complexity for calculating a new activation value with the aggregations and piecewise polynomial functions in BNL; let's say the worst case is \(T\) rounds. If \(R\) is the set of output rounds of \(\mathcal{N}\), the output rounds of \(\Lambda\) are simply \(TR\). In other words, we spend \(T\) rounds in \(\Lambda\) to simulate a single round of \(\mathcal{N}\). 

### From BNL to NN

Before the formal translation from BNL-programs to general neural networks, we introduce two typical piecewise polynomial activation functions with just two pieces and order at most \(1\). These are the well-known rectified linear unit and the Heaviside step function. Recall that an activation function is a function \(S\to S\), where \(S\) is a floating-point system. The **rectified linear unit** ReLU is defined by \(\operatorname{ReLU}(x)=\max\{0,x\}\) and the **Heaviside step function**\(H\) is defined by \(H(x)=1\) if \(x>0\), and \(H(x)=0\), otherwise. We obtain the following Theorem, where for a given BNL-program we construct a general neural network model that uses ReLU (or Heaviside) activation functions. It is easy to generalize our results for other activation functions, which we plan to do in the full version of this paper.
**Theorem 4.2**.: _Given a BNL-program \(\Lambda\) of size \(s\) and depth \(d\), we can construct a general neural network \(\mathcal{N}\) for any floating-point system \(S\) with at most \(s\) nodes, degree at most \(2\), ReLU (or Heaviside) activation functions and computation delay \(\mathcal{O}(d)\) (or \(\mathcal{O}(s)\) since \(s>d\)) such that \(\Lambda\) and \(\mathcal{N}\) are asynchronously equivalent in binary._

Proof.: (Sketch) The full proof can be found in the appendix. The aggregation each node performs on the activation values of its neighbours weakens neural networks in the sense that much of the information related to specific neighbours is lost. Due to this, a single node of a neural network can't imitate an arbitrary iteration clause where each predicate has a precise role. Instead, the program \(\Lambda\) is first turned into an asynchronously equivalent "fully-open" program \(\Lambda^{\prime}\) that is described in the appendix. Informally, that means each body of the iteration clauses of \(\Lambda^{\prime}\) includes at most one logical connective. This is turned into a neural network by creating a node for each predicate of \(\Lambda^{\prime}\). The network only uses the floating-point numbers \(-1,0,1,2\), and the iteration clauses can all be calculated with ReLU or Heaviside by choosing the weights and biases appropriately. 

## 5 Conclusion

We have shown a strong equivalence between a general class of one-to-many neural networks and Boolean network logic in terms of discrete time series. The translations are simple in both directions, with reasonable time and size blow-ups. We receive similar results for the logic SC due to Theorem 2.1. Interesting future directions involve investigating extensions with randomization as well as studying the effects of using alternatives to floating-point numbers, such as, for example, fixed-point arithmetic.
