Analog networks on function data streams

Abstract

Most of the physical processes arising in nature are modeled by differential equations, either ordinary (example: the spring/mass/damper system) or partial (example: heat diffusion). From the point of view of analog computability, the existence of an effective way to obtain solutions (either exact or approximate) of these systems is essential.

A pioneering model of analog computation is the General Purpose Analog Computer (GPAC), introduced by Shannon [Journal of Mathematical Physics 20 (1941), 337–354] as a model of the Differential Analyzer and improved by Pour-El [Transactions of the American Mathematical Society 199 (1974), 1–28], Lipshitz and Rubel [Proceedings of the American Mathematical Society 99(2) (1987)], Costa and Graça [Journal of Complexity 19(5) (2003), 644–664] and others. The GPAC is capable of manipulating real-valued data streams. Its power is known to be characterized by the class of differentially algebraic functions, which includes the solutions of initial value problems for ordinary differential equations.

We address one of the limitations of this model, which is its fundamental inability to reason about functions of more than one independent variable (the ‘time’ variable), as noted by Rubel [Advances in Applied Mathematics 14(1) (1993), 39–50]. In particular, the Shannon GPAC cannot be used to specify solutions of partial differential equations. We extend the class of data types using networks with channels which carry information on a general complete metric space X; here we take $X = C (R)$ , the class of continuous functions of one real (spatial) variable.

We consider the original modules in Shannon’s construction (constants, adders, multipliers, integrators) and we add a differential module which has one input and one output. For input u, it outputs the spatial derivative $v (t) = \partial_{x} u (t)$ .

We then define an X-GPAC to be a network built with X-stream channels and the above-mentioned modules. This leads us to a framework in which the specifications of such analog systems are given by fixed points of certain operators on continuous data streams. Such a framework was considered by Tucker and Zucker [Theoretical Computer Science 371 (2007), 115–146]. We study the properties of these analog systems and their associated operators, and present a characterization of the X-GPAC-generable functions which generalizes Shannon’s results.

Keywords

Analog computation computable analysis partial differential equations

1. Introduction

Analog computation, as conceived by Kelvin [30], Bush [2], and Hartree [10], is a form of experimental computation with physical systems called analog devices or analog computers. Historically, data are represented by measurable physical quantities, including lengths, shaft rotation, voltage, current, resistance, etc., and the analog devices that process these representations are made from mechanical, electromechanical or electronic components [11,13,29].

A general purpose analog computer (GPAC) was introduced by Shannon [28] as a model of Bush’s Differential Analyzer [2]. Shannon discovered that a function can be generated by a GPAC if, and only if, it is differentially algebraic, but his proof was incomplete. A basic study was made by Pour-El [24] who gave some good characterizations of the analog computable functions, focusing on the classic analog systems built from constants, adders, multipliers and integrators. This yielded a stronger model and a new proof of the Shannon’s equivalence (and some new gaps, corrected by Lipshitz and Rubel [18]). Using this characterization in terms of algebraic differential equations, Pour-El showed that not all computable functions on the reals (in the sense of computable analysis) can be obtained with these analog networks.

The theory of analog computing has also been developed by Moore with some very general mathematical models [20]. These models, using schemes rather like Kleene’s [14], but with primitive recursion replaced by integration and others added, define a hierarchy of functions on the reals, which contains the GPAC generable functions at its lowest level, and uncomputable functions (in the sense of computable analysis) at higher levels. Graça and Costa [6] have presented an improved model of the GPAC, and shown this to be equivalent to the lowest level subclass of Moore’s functions.

The contributions of Campagnolo [3] and Mycka [21] have also presented some fine results concerning analog complexity classes. Finally, Pouly [23] studied in his PhD thesis the GPAC (among other models of computation) from the point of view of complexity classes, and with Bournez and Graça [1] they have defined a multidimensional GPAC (however, their model can be formulated as working under a single, ‘implicit time’ variable, as will be discussed below).

The main objects of our study are analog networks or analog systems, [12,32–34], whose main components are described as follows: $\begin{matrix} Analog network = data + time + channels + modules . \end{matrix}$

We will model data as elements of a complete metric vector space X, such as a Banach or Fréchet space. We will use a bounded interval of the real numbers as a continuous model of time $T = [0, T]$ , where T denotes the final time. Each channel carries a continuously differentiable stream, represented as a function $u : T \to X$ (this space is denoted by $C^{1} (T, X)$ ). Each module M has zero, one or more input channels, and must have a single output channel; thus it can be specified by a (possibly partially defined) stream function $\begin{matrix} F_{M} : X^{k} \times C^{1} {(T, X)}^{ℓ} ⇀ C^{1} (T, X) . \end{matrix}$

In the case that $X = R$ , we obtain the Shannon GPAC. We can use four types of modules to describe this model, which are equivalent to the ones originally used by Shannon.

Definition 1.1 (Shannon modules).

The Shannon modules are defined as follows:

for each $c \in R$ , there is a constant module with zero inputs and one output v, given by $\begin{matrix} v (t) = c; \end{matrix}$

the adder module has two inputs u, v and one output w, given by $\begin{matrix} w (t) = u (t) + v (t); \end{matrix}$

the multiplier module has two inputs u, v and one output w, given by $\begin{matrix} w (t) = u (t) v (t); \end{matrix}$

the integrator module has an initial setting c, two inputs u, v and one output w, given by the Lebesgue-Stieltjes integral $\begin{matrix} w (t) = c + \int_{0}^{t} u (s) v^{'} (s) d s . \end{matrix}$

We can depict the four Shannon modules in box diagrams, as in Fig. 1. We also introduce the symbol ‘ ’ todenote the operator associated with the integrator module, in order to differentiate from the actual integral; we can then write .

Figure 1.

The four Shannon modules.

The continuous differentiability of the streams u, v ensures that the integrator module is well defined; indeed, the Lebesgue-Stieltjes integral is well defined for continuous integrand and continuously differentiable integrator. In other words, for any $u, v \in C^{1} ([0, T], R)$ , the formula $\int_{0}^{t} u (s) d v (s)$ defines a function in $C^{1} ([0, T], R)$ .

Definition 1.2 (Shannon GPAC).

A Shannon general purpose analog computer (GPAC) is a network built with the four Shannon modules (constants, adders, multipliers and integrators) and connections between their inputs and outputs, with the following restrictions:

the only connections allowed are between an output and an input;

each input may be connected to either zero or one output.

Example 1.3.
Of course, there can be cycles in a GPAC, for example, an output connected to an input of its own module. This is called feedback and it is fundamental to develop an interesting theory. A simple example of a Shannon GPAC can be seen in Fig. 2. It has only one module, which is an integrator module, and only one connection, between its output channel and one of its input channels.

In his paper Shannon sets out to characterize the class of functions which can be generated by a GPAC and in doing so he found an equivalence with the class of differentially algebraic functions.

Figure 2.
A GPAC for computing the exponential function.
Definition 1.4 (Differentially algebraic function).

A function $f : [0, T] \to R$ is said to be differentially algebraic if there exists $k \in N$ and a polynomial P in $k + 2$ variables (and real coefficients) such that $f \in C^{k} ([0, T])$ and $\begin{matrix} (1) & P (t, f (t), f^{'} (t), \dots, f^{(k)} (t)) = 0, for all t \in [0, T] . \end{matrix}$ An equation in the form (1) is called a differential algebraic equation.

Theorem 1 (GPAC characterization theorem).

Let $u \in C^{1} (T, R)$ . Then u is generable by a GPAC if and only if u is differentially algebraic.

The original proof of Theorem 1 can be found in [28], but that proof had flaws, which were corrected in the papers [6,18,24].

In this paper we present a generalization of the Shannon GPAC for channels whose values lie in a general complete metric vector space, i.e. a Banach or Fréchet space. This allows us to, for example, work with functions of more than one variable. Our goal is to obtain an equivalence result similar to Theorem 1, with a larger class of functions which include, in particular, solutions to well-known PDEs, such as the heat equation and wave equation.

The paper is organized as follows. In Section 2 we show some limitations to Shannon’s model and motivate our transition to function data spaces. In Section 3 we present our new model, the X-GPAC, and define its semantics. In Section 4 we introduce normal form systems which are used as an intermediate step towards the main result. In Section 5 we introduce partial differential algebraic systems and prove our main result: a characterization of X-GPAC-generable functions in terms of solutions to such systems. In Section 6 we summarize our findings and propose directions for further research.

2. Limitations of the Shannon GPAC

The Shannon GPAC is regarded as an important and powerful method of analog computation, thanks largely to Theorem 1. Despite this, many authors have pointed out some limitations to the model. For example, the gamma function $\begin{matrix} Γ (t) = \int_{0}^{\infty} x^{t - 1} e^{- x} d x \end{matrix}$ is not differentially algebraic, and so cannot be generated by a GPAC (this was noted by Shannon himself). However, one could expect that, in a ‘sensible’ model of computability on continuous data, this function would be computable. Indeed, the gamma function is effectively computable in the sense of computable analysis, a branch of analog computability studied by Pour-El, Richards [25], Weihrauch [35], Grzegorczyk [7,8], Lacombe [15–17], Tucker, Zucker [32], among others. Some authors have addressed this limitation, and Graça [5] showed that the gamma function can indeed be considered as GPAC computable if

…we redefine our notion of GPAC-computability in a manner that it matches more closely the philosophy underlying computable analysis….

There is, however, another limitation with the Shannon GPAC, that appears to have been overlooked by Shannon, Pour-El and others. It lies in the fact that the Shannon GPAC can fundamentally reason only about real-valued functions of one independent variable t. Ironically, it was stated in [28] and [24] that the generalization to more than one independent variable only requires an obvious modification, but this is by no means the case. In fact, it is hard to conceive a realistic physical interpretation for a formalism involving two (or more) independent “time” variables.

We briefly remark that this limitation was pointed out in [27]. Rubel says:

For one thing, the GPAC works in one (“time”) variable only, while the EAC [Extended Analog Computer] produces functions of any finite number of real variables.

To address this problem, Rubel defined what he called an Extended Analog Computer (EAC).1

¹
An implementation of the EAC (or at least, of some of its components) has been achieved with the work of Mills [19].

However, Rubel stressed that

…the EAC is a conceptual computer – the extent to which it can be realized by actual physical, chemical, or biological devices or systems remains to be investigated.

A different attempt to deal with this problem was recently proposed by Bournez, Graça and Pouly [1,23]. In their approach, channels can carry a n-variable real-valued data stream of type $R^{n} \to R$ . In this way, they were able to introduce functions with multiple variables by extending the input space; for example, replacing $C^{1} ([0, T], R)$ with $C^{1} ([0, X_{1}] \times \dots \times [0, X_{n}], R)$ . This seems to be a very natural way of generalizing the Shannon GPAC.

Despite the fact that [1, Definition 14] uses Jacobians (which imply independent variables), we would like to point out that their model can still be re-expressed in terms of only one (implicit “time”) variable. This idea is present in [1, Examples 12 and 13]. It also occurs in [1, Remark 15], where it is explained that the value of a generable function y at a given point x can be obtained by solving an initial value problem in one independent variable (this is done by introducing a smooth curve γ from $x_{0}$ , an initial point, to x).

In this paper we adopt an approach which in some way is orthogonal to the one in [1]; our idea is to extend the output space, that is, replacing $C^{1} ([0, T], R)$ with $C^{1} ([0, T], X)$ , where X is a metric vector space. For example, we can think of X as the space of continuous real-valued functions on a bounded domain $Ω \subset R^{n}$ , that is, $X = C (Ω, R)$ . In this way, our channels will now carry X-valued streams of data $u : [0, T] \to X$ , which correspond to functions of $n + 1$ real variables, under the uncurrying $\begin{matrix} [0, T] \to (Ω \to R) ≃ [0, T] \times Ω \to R . \end{matrix}$

It is evident that one of the variables, namely the “time” variable, plays a different role from the others. Our approach is, to some extent, motivated by the theory of Partial Differential Equations, in which some fundamental problems (such as the Heat Equation, Wave Equation and Schrödinger Equation) can be expressed as time evolution problems in a function space.

3. The X-GPAC

As discussed in the previous section we decide to change our data space X to become a function space. In this paper we shall thus take X to be the space of continuous real functions of a real variable, $\begin{matrix} X = C (R) . \end{matrix}$

We observe that X is a Fréchet space, with the family of pseudonorms $\begin{matrix} (2) & ‖ g ‖_{M} = sup_{| x | ⩽ M} | g (x) | . \end{matrix}$

We also consider the subspace $D = C^{1} (R)$ of continuously differentiable functions. This is also a Fréchet space, with the family of pseudonorms $\begin{matrix} (3) & ‖ g ‖_{M} = sup_{| x | ⩽ M} | g (x) | + sup_{| x | ⩽ M} | \partial_{x} g (x) | . \end{matrix}$

Note that D is a linear and dense (under the X-pseudonorms) subspace of X.

We can define a differential operator as $\begin{array}{l} (4) & \begin{matrix} \partial_{x} : & X ⇀ X \\ u (x) \mapsto \partial_{x} u (x) . \end{matrix} \end{array}$

We establish some important properties of the differential operator:

$\partial_{x}$ is a partial function from X to X, with domain $dom (\partial_{x}) = D$ ;

$\partial_{x}$ is linear, that is, for all $u, v \in D$ and $α, β \in R$ we have $\partial_{x} (α u + β v) = α \partial_{x} u + β \partial_{x} v$ ;

$\partial_{x}$ has dense domain, that is, D is dense in X (under the topology in X induced by its pseudonorms);

$\partial_{x}$ has a closed graph, that is, if $(u_{n})$ is a sequence in D with $u_{n} \to u$ and $\partial_{x} u_{n} \to v$ , then $u \in D$ and $\partial_{x} u = v$ .

We include here the definition of closed operator, which will play a role in our notion of well-posedness.

Definition 3.1 (Closed operator).

Let X and Y be metric spaces and $A : X ⇀ Y$ a partial function with domain $D (A)$ . We say that A is closed if its graph is a closed subset of $X \times Y$ ; in other words, if for all sequences $(x_{n})$ in X, $x \in X$ and $y \in Y$ we have $\begin{matrix} if \{\begin{matrix} x_{n} \to x & as n \to \infty, \\ x_{n} \in D (A) & for all n, \\ A x_{n} \to y & as n \to \infty, \end{matrix}\} then x \in D (A) and A x = y . \end{matrix}$

Hence $\partial_{x}$ is a closed operator on X. We remind the reader that closedness is, in general, a weaker property than continuity. We also remark that both are equivalent in the space of total linear operators between Banach spaces (this basic result is known as the Closed Graph Theorem).

Figure 3.

Plot of $a_{n} (x)$ (left) and $a_{n}^{'} (x)$ (right) for $n = 3$ (red, bold), $n = 5$ (green, dashed), $n = 10$ (blue, dotted).

Example 3.2.

Consider the sequence $a_{n} (x) = \frac{1}{n} sin (n^{2} x)$ , which converges in $X = C (R)$ (that is, in the pseudonorms of X) to 0; for any M, $‖ a_{n} ‖_{M} = \frac{1}{n} \to 0$ . Moreover, each $a_{n} \in D$ , and $\partial_{x} a_{n} (x) = n cos (n^{2} x)$ . Note that, for any M, $‖ a_{n}^{'} ‖_{M} = n$ , meaning that the suprema of $a_{n}^{'}$ grow without bounds. Thus $\partial_{x}$ is a discontinuous operator. See Fig. 3.

We consider X-streams as elements in the space $C^{1} ([0, T], X)$ of X-valued, continuously differentiable functions, for some $T > 0$ . By continuous differentiability we mean that, for $u \in C^{1} ([0, T], X)$ , the expression $\begin{matrix} v (t) = lim_{h \to 0} \frac{u (t + h) - u (t)}{h} \end{matrix}$ is well-defined for all $t \in [0, T]$ and v is a continuous function of time.

In this way, $C^{1} ([0, T], X)$ is a Fréchet space under the family of pseudonorms $\begin{matrix} ‖ u ‖_{T, M} = sup_{0 ⩽ t ⩽ T} {‖ u (t) ‖}_{M} + sup_{0 ⩽ t ⩽ T} {‖ u^{'} (t) ‖}_{M}; \end{matrix}$ note that in the right-hand side we consider pseudonorms of X.

The Shannon modules are easily defined in this new setting, and we introduce a new module based on the differential operator.

Definition 3.3.

The differential module (see Fig. 4) has one input u and one output v, given by $\begin{matrix} v (t) = \partial_{x} u (t) . \end{matrix}$

We remark that the differential module $\partial_{x} : C^{1} ([0, T], X) ⇀ C^{1} ([0, T], X)$ is partially defined and its domain is $C^{1} ([0, T], D)$ . As mentioned above, $\partial_{x}$ is a closed but discontinuous operator.

Figure 4.

The differential module.

With the above considerations in mind we can arrive at the desired generalization of the Shannon GPAC.

Definition 3.4 (X-GPAC).

An X-valued general purpose analog computer (X-GPAC) is a network built with the five X-modules (constants, adders, multipliers, integrators and differentials) and X-channels connecting their inputs and outputs, with the following restrictions:

the only connections allowed are between an output and an input;

each input may be connected to either zero or one output.

Our next goal is to assign semantics to an X-GPAC, that is, determine how to define generable functions. For that end, we introduce the notion of induced operator.

Definition 3.5 (X-GPAC induced operator).

Let $G$ be an X-GPAC;

the constant space of $G$ is the Cartesian product of the spaces associated with all the initial settings occuring in any integrator. The constant space can be written as $C = X^{p}$ , for some $p ⩾ 0$ ;

the proper input space of $G$ is the Cartesian product of the spaces associated with all the unconnected input channels. The input space can be written as $I = C^{1} {([0, T], X)}^{q}$ , for some $q ⩾ 0$ ;

the proper output space of $G$ is the Cartesian product of the spaces associated with all the unconnected output channels. The output space can be written as $O = C^{1} {([0, T], X)}^{m}$ , for some $m ⩾ 0$ ;

the mixed space of $G$ is the Cartesian product of the spaces associated with all the channels which connect some input with some output. The mixed space can be written as $M = C^{1} {([0, T], X)}^{r}$ , for some $r ⩾ 0$ ;

the induced operator of $G$ is the function $\begin{matrix} (5) & F : C \times I \times M ⇀ M \times O, F (g, u^{I}, u^{M}) = ({\tilde{u}}^{M}, u^{O}), \end{matrix}$ where g is an X-valued vector and each u is a vector of X-channels. Moreover, each of the components in the codomain of F is given by the module with which it is associated. In other words, for each $u_{i}$ component of either ${\tilde{u}}^{M}$ or $u^{O}$ ,

if $u_{i}$ is associated with the output channel of a constant, then $u_{i} = g$ , where g is the constant associated with that module;

if $u_{i}$ is associated with the output channel of an adder, then $u_{i} = + (v_{1}, v_{2})$ , where $v_{1}$ and $v_{2}$ are the components in $u^{I}$ or $u^{M}$ associated with the input channels of that module;

if $u_{i}$ is associated with the output channel of a multiplier, then $u_{i} = \times (v_{1}, v_{2})$ , where $v_{1}$ and $v_{2}$ are the components in $u^{I}$ or $u^{M}$ associated with the input channels of that module;

if $u_{i}$ is associated with the output channel of an integrator, then , where $v_{1}, v_{2}$ are the components in $u^{I}$ or $u^{M}$ associated with the input channels of that module, and g is the component in g associated with the initial setting of that module;

if $u_{i}$ is associated with the output channel of a differential, then $u_{i} = \partial_{x} (v)$ , where v is the component in $u^{I}$ or $u^{M}$ associated with the input channel of that module.

We remark that F may be partially defined; for each differential module occuring in $G$ , there is a component of $I \times M$ which is restricted to $C^{1} ([0, T], D)$ . Hence, to describe the domain of F we must take into special consideration those channels which are inputs of differential modules.

Example 3.6.
To achieve a better understanding of Definition 3.5 we provide an example in Fig. 5 of an X-GPAC with one constant and four X-channels.

Figure 5.
An X-GPAC implementing a transport equation.

In this example there is one constant (associated with the integrator module), one input channel (labeled $u_{1}$ ), two mixed channels (labeled $u_{2}$ and $u_{3}$ ) and one output channel (labeled $u_{4}$ ). The induced operator simply formalizes the input/output relation between these channels, $\begin{array}{l} C = X, I = C^{1} (T, X), M = C^{1} {(T, X)}^{2}, O = C^{1} (T, X); \\ F : C \times I \times M ⇀ M \times O \\ F (g, u_{1}, u_{2}, u_{3}) = (g + \int u_{3} d u_{1}, \partial_{x} u_{2}, \partial_{x} u_{3}) = (\tilde{u_{2}}, \tilde{u_{3}}, u_{4}) . \end{array}$

Definition 3.4 gives a lot of freedom in the construction of X-GPACs and it turns out that not all of the possible networks lead to ‘valid and interesting’ X-GPACs (similarly to the fact that not all ASCII expressions lead to ‘valid and interesting’ computer programs). Thus we present a well-posedness-like notion to restrict the space of X-GPACs that we wish to consider.
Definition 3.7 (Quasi-well-posedness of X-GPAC).

Let $G$ be an X-GPAC and $F : C \times I \times M ⇀ M \times O$ be its induced operator. Let $U \subseteq C \times I$ . We say that $G$ is quasi-well-posed on U if

(existence) for every $(g, u^{I}) \in U$ , there exists $(u^{M}, u^{O}) \in M \times O$ such that $\begin{matrix} (6) & F (g, u^{I}, u^{M}) = (u^{M}, u^{O}); \end{matrix}$

(uniqueness) for every $(g, u^{I}) \in U$ , the tuple $(u^{M}, u^{O})$ such that Eq. (6) holds is unique;

(closedness) the map $(g, u^{I}) \mapsto (u^{M}, u^{O})$ , with domain U and codomain $M \times O$ , given as the unique solution of Eq. (6), defines a closed operator.

We may refer to Eq. (6) as the fixed point equation; note that the mixed variables $u^{M}$ are the only ones that appear in both sides of the equation.

If we required continuity instead of closedness (that is, if we required U to be an open set, and the map $(g, u^{I}) \mapsto (u^{M}, u^{O})$ to be continuous), then our definition would match the three usual principles for well-posedness – existence, uniqueness, continuity of solutions – as presented by Hadamard [9] (see also [4]). Instead, we choose to use closedness (and a non-necessarily open domain U), which is a strictly weaker criterion, hence the term ‘quasi-well-posed’. The reason for choosing closedness is the presence of the differential module, which defines a closed function of type $X ⇀ X$ which is not continuous.

Admittedly, some could argue that a discontinuous operation is of little interest in the study of computable functions of continuous spaces. We must then make the important remark that continuity can be obtained from closedness (and thus well-posedness can be obtained by quasi-well-posedness) if we define a finer topology in the domain, induced by graph (pseudo)norms. To be precise, we recall the following basic result in functional analysis.

Proposition 3.8 ([26, p. 240, Exercise 8.7]).

Let $(X, ‖ \cdot ‖_{X})$ and $(Y, ‖ \cdot ‖_{Y})$ be Banach spaces and $A : X ⇀ Y$ a closed linear operator with domain $D (A)$ . Then

$(D (A), ‖ \cdot ‖_{G (A)})$ is a Banach space with the graph norm given by $\begin{matrix} ‖ x ‖_{G (A)} = ‖ x ‖_{X} + ‖ A x ‖_{Y}; \end{matrix}$

the restriction $A : D (A) \to Y$ is a continuous linear map between Banach spaces.

Proof.
We first prove that $‖ \cdot ‖_{G (A)}$ defines a norm:
if $x \in D (A)$ , then $‖ x ‖_{G (A)} = 0$ iff $‖ x ‖_{X} + ‖ A x ‖_{Y} = 0$ iff $‖ x ‖_{X} = 0$ iff $x = 0$ ;

if $x \in D (A)$ and $α \in R$ , then $‖ α x ‖_{G (A)} = ‖ α x ‖_{X} + ‖ A (α x) ‖_{Y} = | α | ‖ x ‖_{X} + | α | ‖ A x ‖_{Y} = | α | ‖ x ‖_{G (A)}$ ;

if $x, y \in D (A)$ , then $‖ x + y ‖_{G (A)} = ‖ x + y ‖_{X} + ‖ A (x + y) ‖_{Y} ⩽ ‖ x ‖_{X} + ‖ y ‖_{X} + ‖ A x ‖_{Y} + ‖ A y ‖_{Y} = ‖ x ‖_{G (A)} + ‖ y ‖_{G (A)}$ .

Next we prove that $D (A)$ is complete. Let ${x_{n}}_{n}$ be a Cauchy sequence in $D (A)$ , so that $‖ x_{N + k} - x_{N} ‖_{G (A)} = ‖ x_{N + k} - x_{N} ‖_{X} + ‖ A (x_{N + k} - x_{N}) ‖_{Y}$ vanishes (uniformly on k) as $N \to \infty$ . In particular, we must have that ${x_{n}}_{n}$ is a Cauchy sequence in X (under the X-norm) and ${A x_{n}}$ is a Cauchy sequence in Y. Since X and Y are Banach spaces it follows that there exist $x \in X$ and $y \in Y$ such that $x_{n} \to x$ and $A x_{n} \to y$ . By closedness of A we conclude that $x \in D (A)$ and $A x = y$ , so that $x_{n} \to x$ in $D (A)$ (under the graph norm). Thus $(D (A), ‖ \cdot ‖_{G (A)})$ is a Banach space.

Finally we prove that $A : D (A) \to Y$ is continuous. Let ${x_{n}}_{n}$ be a sequence in $D (A)$ and $x \in D (A)$ such that $x_{n} \to x$ in $D (A)$ . Then $‖ x_{n} - x ‖_{G (A)} \to 0$ , which implies $‖ x_{n} - x ‖_{X} \to 0$ and $‖ A (x_{n} - x) ‖_{Y} \to 0$ , so that, in particular, $A x_{n} \to A x$ in Y. □
Proposition 3.9.
Let X and Y be Fréchet spaces with families of pseudonorms ${‖ \cdot ‖_{X, n}}_{n}$ and ${‖ \cdot ‖_{Y, m}}_{m}$ and $A : X ⇀ Y$ a closed linear operator with domain $D (A)$ . Consider the Fréchet space $D (A)$ with graph pseudonorms given by $\begin{matrix} ‖ x ‖_{G (A), n, m} = ‖ x ‖_{X, n} + ‖ A x ‖_{Y, m} . \end{matrix}$

Then the restriction $A : D (A) \to Y$ is a continuous linear map between Fréchet spaces.
Proof.
The proof is similar to that of Proposition 3.8. □

This finer topology is usually equivalent to a topology of interest in the domain space. For example, consider the differential operator $\partial_{x} : C (R) ⇀ C (R)$ given by Eq. (4), which is closed but not continuous under the usual family of pseudonorms in $C (R)$ . However, it becomes a continuous operator if we restrict it to the space $C^{1} (R)$ and consider the graph pseudonorms $\begin{matrix} ‖ f ‖_{n, m} = ‖ f ‖_{n} + ‖ \partial_{x} f ‖_{m} = sup_{| x | ⩽ n} | f (x) | + sup_{| x | ⩽ m} | \partial_{x} f (x) |, \end{matrix}$ under whose topology $C^{1} (R)$ is a Fréchet space. Moreover, this family of pseudonorms can be seen to be equivalent to the usual family of pseudonorms in $C^{1} (R)$ given by Eq. (3).

We shall then adopt the notion of quasi-well-posedness in this paper, while reminding ourselves that, if needed, we can in principle express our results in terms of well-posed operators.

The final step in this section is to assign semantics to X-GPACs, that is, to define the notion of X-GPAC-generable functions.
Definition 3.10 (Semantics of X-GPAC).

Let $G$ be an X-GPAC and $F : C \times I \times M ⇀ M \times O$ be its induced operator. Let $U \subseteq C \times I$ such that $G$ is quasi-well-posed on U. We define the specification of $G$ as the (partial) function $\begin{array}{l} Φ : C \times I ⇀ M \times O; \\ Φ (g, u^{I}) = (u^{M}, u^{O}), \end{array}$ whose domain is U and where $(u^{M}, u^{O})$ is given by Eq. (6). We also say that $G$ generates Φ on $U = dom (Φ)$ .

A function $Φ : C \times I ⇀ M \times O$ is X-GPAC-generable if there exists an X-GPAC $G$ such that $G$ is quasi-well-posed on the domain of Φ and Φ is the specification of $G$ .

We remark that every integrator in an X-GPAC has an initial setting (which is one of the constants in the space $C$ ) and an output (which is one of the mixed/output channels in $M \times O$ ). Since we can define an injective map from the initial settings to the mixed/output channels, we have the following basic property.

Proposition 3.11.
If $Φ : C \times I ⇀ M \times O$ is X-GPAC-generable, then $dim (C) ⩽ dim (M) + dim (O)$ .
4. Normal form systems

We have defined in the previous section the class of X-GPAC-generable functions, which constitute our space of interest. We can state our objective as follows.

Problem.
Characterize the class of X-GPAC-generable functions in terms of a suitable generalization of the class of differential algebraic equations.

In the study of the GPAC, an intermediate step is usually taken in the transition from generable functions to differential algebraic equations. For example, in [28] a system of equations called a fundamental solvability condition was considered (Theorem I in that paper). Also in [24] a similar system of equations is used in the actual definition of GPAC generable functions (Definition 10 in that paper) instead of the usual definition involving analog networks. We shall generalize that notion into our framework, and refer to the resulting objects as normal form systems.
Definition 4.1 (Normal form equation).

Let $N \in N$ . A normal form equation on the N variables $y_{1}, \dots, y_{N}$ is an equation of the form $\begin{matrix} (7) & \sum_{i = 0}^{N} \sum_{j = 1}^{N} b_{i j} y_{i} y_{j}^{'} + \sum_{j = 1}^{N} c_{j} \partial_{x} y_{j}^{'} = 0, \end{matrix}$ under the conventions that $y_{0} \equiv 1$ and $b_{i j}$ , $c_{j}$ are real numbers.

We remark that $y_{0} \equiv 1$ is not a variable, just a notational convenience to obtain a more compact equation. We also note that index i starts at 0 whereas index j starts at 1; thus Eq. (7) will not include the term $y_{0}^{'}$ (which would be equal to 0, and therefore irrelevant).

We also alert the reader to our choice of terms of the form $\partial_{x} y_{j}^{'}$ in the second summation in Eq. (7), with derivatives both in time and space. One could think that a similar definition of normal form equations with terms of the form $\partial_{x} y_{j}$ would be more ‘natural’. In fact, both definitions would be equivalent, and we could move from the former to the latter by adding extra variables (namely, one would have to add the extra variable t that specifies “linear time”, $t (t, x) = t$ ). The main reason for choosing Eq. (7) as our template for normal form equations is of practicality, as it makes the proof of Lemma 4.7 (below) much simpler.

Here are some examples of normal form equations: $\begin{array}{l} y_{1}^{'} = y_{1} y_{2}^{'}; \\ y_{1}^{'} = y_{2}^{'} + y_{3}^{'}; \\ y_{1}^{'} = \partial_{x} y_{1}^{'} . \end{array}$

Definition 4.2 (Normal form system over X).

Let $K, L \in N$ and $N = K + L$ . A normal form system (NFS) on the N variables $y_{1}, \dots, y_{N}$ is a system of the form $\begin{matrix} (8) & \{\begin{matrix} \sum_{i = 0}^{N} \sum_{j = 1}^{N} b_{i j ℓ} y_{i} y_{j}^{'} + \sum_{j = 1}^{N} c_{j ℓ} \partial_{x} y_{j}^{'} = 0, & for ℓ = 1, \dots, L; \\ y_{K + ℓ} (0) = g_{ℓ}, & for ℓ = 1, \dots, L, \end{matrix} \end{matrix}$ under the conventions that $y_{0} \equiv 1$ , $b_{i j ℓ}$ , $c_{j ℓ}$ are real numbers and $g_{ℓ} \in X$ .

We say that $g_{1}, \dots, g_{L}$ are the (initial) constants, $y_{1}, \dots, y_{K}$ are the inputs or independent variables and $y_{K + 1} \dots, y_{K + L}$ are the outputs or dependent variables.

We briefly remark that, in a well-posed system of equations, the number of equations and the number of unknowns must be the same. In the previous definition, these correspond to the outputs $y_{K + 1}, \dots, y_{K + L}$ ; hence there must be L equations.

Definition 4.3 (Quasi-well-posedness of NFS).

Let $K, L \in N$ and $N = K + L$ . Let $N$ be an NFS given by Eq. (8) with K inputs and L outputs and consider the spaces $\begin{matrix} C = X^{L}, I = C^{1} {([0, T], X)}^{K}, O = C^{1} {([0, T], X)}^{L} . \end{matrix}$ Let $U \subseteq C \times I$ . We say that $N$ is quasi-well-posed on U if

(existence) for every $(g, y^{I}) \in U$ , there exists $y^{O} \in O$ such that Eq. (8) holds for $(g, y^{I}, y^{O})$ , where $g = (g_{1}, \dots, g_{L})$ , $y^{I} = (y_{1}, \dots, y_{K})$ , $y^{O} = (y_{K + 1}, \dots, y_{K + L})$ ;

(uniqueness) for every $(g, y^{I}) \in U$ , the tuple $y^{O}$ such that Eq. (8) holds is unique;

(closedness) the map $(g, y^{I}) \mapsto y^{O}$ , with domain U and codomain $O$ , given as the unique solution of Eq. (8), defines a closed operator.

Definition 4.4 (Semantics of NFS).

Let $K, L \in N$ and $N = K + L$ . Let $N$ be an NFS with K inputs and L outputs. Let $U \subseteq C \times I$ such that $N$ is quasi-well-posed on U. We define the solution of $N$ as the (partial) function $\begin{array}{l} Φ : C \times I ⇀ O; \\ Φ (g, y^{I}) = y^{O}, \end{array}$ whose domain is U and where $y^{O}$ is given by Eq. (8). We also say that $N$ generates Φ on $U = dom (Φ)$ .

A function $Φ : C \times I ⇀ O$ is NFS-generable if there exists an NFS $N$ such that $N$ is quasi-well-posed on the domain of Φ and Φ is the solution of $N$ .

We remark that in an NFS, there is a bijection between the initial conditions and the outputs; thus we have the following basic property (cf. Proposition 3.11).

Proposition 4.5.
If $Φ : C \times I ⇀ O$ is NFS-generable, then $dim (C) = dim (O)$ .

We have established semantics for NFS, and the next step is to show that every X-GPAC-generable function is a projection of an NFS-generable function, as in the following definition.
Definition 4.6 (Function projection).

Let $F : A ⇀ B$ and $F^{'} : A \times A^{'} ⇀ B \times B^{'}$ , and let $\begin{array}{l} G (F) = {(a, b) : a \in dom (F) and F (a) = b} \subseteq A \times B, \\ G (F^{'}) = {(a, a^{'}, b, b^{'}) : (a, a^{'}) \in dom (F^{'}) and F^{'} (a, a^{'}) = (b, b^{'})} \subseteq A \times A^{'} \times B \times B^{'} \end{array}$ be their graphs. We say that F is a projection of $F^{'}$ if for all $(a, b) \in A \times B$ ,

if $(a, b) \notin G (F)$ then for all $a^{'} \in A^{'}$ , $b^{'} \in B^{'}$ we have $(a, a^{'}, b, b^{'}) \notin G (F^{'})$ ;

if $(a, b) \in G (F)$ then there exist unique $a^{'} \in A^{'}$ and $b^{'} \in B^{'}$ such that $(a, a^{'}, b, b^{'}) \in G (F^{'})$ .

We briefly remark that the notion of projection induces a partial order in the class of functions. We have the following lemma.

Lemma 4.7 (X-GPAC-generable implies NFS-generable).

Let $Φ_{G} : C_{G} \times I_{G} ⇀ M_{G} \times O_{G}$ be X-GPAC-generable with domain $U_{G} \subseteq C_{G} \times I_{G}$ . Then there exists $Φ_{N} : C_{N} \times I_{N} ⇀ O_{N}$ which is NFS-generable with domain $U_{N} \subseteq C_{N} \times I_{N}$ with the following properties:

$dim (I_{N}) = dim (I_{G})$ and $dim (O_{N}) = dim (M_{G}) + dim (O_{G})$ ;

for every $(g, u^{I}) \in C_{G} \times I_{G}$ such that $(g, u^{I}) \notin U_{G}$ , we have $(g, g^{*}, u^{I}) \notin U_{N}$ for any X-vector $g^{*}$ ;

for every $(g, u^{I}) \in C_{G} \times I_{G}$ such that $(g, u^{I}) \in U_{G}$ , there exists a unique X-vector $g^{*}$ such that $(g, g^{*}, u^{I}) \in U_{N}$ ; moreover, we have $\begin{matrix} Φ_{G} (g, u^{I}) = Φ_{N} (g, g^{*}, u^{I}) . \end{matrix}$

In other words,

Φ_{G}

is a projection of

Φ_{N}

Proof.
Let $Φ_{G} : C_{G} \times I_{G} ⇀ M_{G} \times O_{G}$ be X-GPAC-generable with domain $U_{G} \subseteq C_{G} \times I_{G}$ . Denote by $G$ the X-GPAC that generates $Φ_{G}$ and $F : C_{G} \times I_{G} \times M_{G} ⇀ M_{G} \times O_{G}$ the induced operator.

The important idea of the proof is understanding how to write the equational specification of F as an NFS. We apply the following conversions, for every u appearing in $M_{G} \times O_{G}$ : $\begin{array}{l} u = g ⇝ \{\begin{matrix} u^{'} = 0 \\ u (0) = g \end{matrix} \\ u = v + w ⇝ \{\begin{matrix} u^{'} = v^{'} + w^{'} \\ u (0) = v (0) + w (0) \end{matrix} \\ u = v \cdot w ⇝ \{\begin{matrix} u^{'} = v w^{'} + w v^{'} \\ u (0) = v (0) \cdot w (0) \end{matrix} \\ u = g + \int v d w ⇝ \{\begin{matrix} u^{'} = v w^{'} \\ u (0) = g \end{matrix} \\ u = \partial_{x} v ⇝ \{\begin{matrix} u^{'} = \partial_{x} v^{'} \\ u (0) = \partial_{x} v (0) \end{matrix} \end{array}$

We observe that the input/output relation of each module of $G$ can be written as a normal form equation coupled with an initial condition. Therefore, we can construct an NFS, $N$ , from $G$ , including an initial condition for each channel.

However, the constant space $C_{G}$ appearing in the specification of $G$ only takes into account those constants appearing as initial settings of integrators. In order to define the solution mapping, $Φ_{N}$ , we need to extend the constant space to include the initial settings of the other types of operations, as they appear in the list of conversions above.

Let $I_{N} = C^{1} {([0, T], X)}^{K}$ and $O_{N} = C^{1} {([0, T], X)}^{L}$ , where K, L are the number of inputs, outputs of $N$ . By construction each input of $N$ corresponds to an input channel of $G$ and each output of $N$ corresponds to either a mixed or output channel of $G$ . Therefore, we have that $I_{N} = I_{G}$ and $O_{N} = M_{G} \times O_{G}$ , so that $dim (I_{N}) = dim (I_{G})$ and $dim (O_{N}) = dim (M_{G}) + dim (O_{G})$ , which proves the first bullet.

The next step is to find a suitable $U_{N}$ for the domain of $Φ_{N}$ . By quasi-well-posedness of $G$ on $U_{G}$ , we know that, for every $(g, u^{I}) \in U_{G}$ , there exists a unique $(u^{M}, u^{O}) \in M_{G} \times O_{G}$ such that $F (g, u^{I}, u^{M}) = (u^{M}, u^{O})$ . Thus, if we define $(g, g^{})$ as the vector of initial conditions2
²
Possibly after reordering the mixed and output channels; this can be done without loss of generality.

of $(u^{M}, u^{O})$ , we can infer that $g^{}$ depends uniquely on $(u^{M}, u^{O})$ , and thus it depends uniquely on $(g, u^{I})$ . With this in mind we define $\begin{array}{l} U_{N} = {(g, g^{}, u^{I}) : (g, u^{I}) \in U_{G} and (g, g^{}) = Φ_{G} (g, u^{I}) ⇂_{t = 0}}; \\ Φ_{N} (g, g^{}, u^{I}) = \{\begin{matrix} Φ_{G} (g, u^{I}) & if (g, g^{}, u^{I}) \in U_{N}; \\ undefined & otherwise . \end{matrix} \end{array}$

By the above construction, $U_{N}$ and $Φ_{N}$ satisfy the second and third bullets, and all is left is to show that $Φ_{N}$ is the solution of $N$ on $U_{N}$ . By quasi-well-posedness of $G$ on $U_{G}$ , it is clear that for $(g, g^{}, u^{I}) \in U_{N}$ , the tuple $(u^{M}, u^{O}) \in O_{N}$ that solves the NFS exists, is unique and given by $Φ_{G} (g, u^{I})$ .

To prove closedness of $Φ_{N}$ , consider a sequence $(g_{n}, g_{n}^{}, u_{n}^{I}) \in U_{N}$ such that $\begin{matrix} (g_{n}, g_{n}^{}, u_{n}^{I}) \to (g, g^{}, u^{I}) and Φ_{N} (g_{n}, g_{n}^{}, u_{n}^{I}) \to (u^{M}, u^{O}); \end{matrix}$ then we have $\begin{matrix} (g_{n}, u_{n}^{I}) \to (g, u^{I}) and Φ_{G} (g_{n}, u_{n}^{I}) = Φ_{N} (g_{n}, g_{n}^{}, u_{n}^{I}) \to (u^{M}, u^{O}) . \end{matrix}$

By closedness of $Φ_{G}$ , we have $\begin{matrix} (g, u^{I}) \in U_{N} and Φ_{G} (g, u^{I}) = (u^{M}, u^{O}); \end{matrix}$

Now define $(u_{n}^{M}, u_{n}^{O}) = Φ_{G} (g_{n}, u_{n}^{I})$ , so that $\begin{matrix} (g_{n}, g_{n}^{}) = Φ_{G} (g_{n}, u_{n}^{I}) ⇂_{t = 0} = (u_{n}^{M}, u_{n}^{O}) ⇂_{t = 0}; \end{matrix}$ by taking limits, we conclude that $(g, g^{}) = (u^{M}, u^{O}) ⇂_{t = 0}$ . Thus, $\begin{matrix} (g, g^{}, u^{I}) \in U_{N} and Φ_{N} (g, g^{}, u^{I}) = (u^{M}, u^{O}), \end{matrix}$ which concludes the proof. □
Example 4.8.
In order to better understand the construction in the proof of Lemma 4.7, we apply it to the X-GPAC seen on Example 3.6 (repeated in Fig. 6).

Figure 6.
An X-GPAC implementing a transport equation.

It can be checked that this X-GPAC is well-posed for $u_{1} \in C^{1} ([0, T], X)$ and $g \in C^{2} (R)$ . It generates the function $Φ_{G} : X^{1} \times C^{1} {([0, T], X)}^{1} ⇀ C^{1} {([0, T], X)}^{3}$ , given by $Φ_{G} (g, u_{1}) = (u_{2}, u_{3}, u_{4})$ , where $\begin{matrix} u_{2} (t, x) = g (x + u_{1} (t) - u_{1} (0)), u_{3} (t, x) = g^{'} (x + u_{1} (t) - u_{1} (0)), u_{4} (t, x) = g^{″} (x + u_{1} (t) - u_{1} (0)); \end{matrix}$ if $u_{1}$ is linear time, $u_{1} (t, x) = t$ , this has the simpler form $\begin{matrix} u_{2} (t, x) = g (x + t), u_{3} (t, x) = g^{'} (x + t), u_{4} (t, x) = g^{″} (x + t) . \end{matrix}$

Let us construct an NFS with solution $Φ_{N}$ such that $Φ_{G}$ is a projection of $Φ_{N}$ . The X-GPAC generates the equational relations $\begin{matrix} (9) & u_{2} = g + \int_{0}^{t} u_{3} d u_{1}, u_{3} = \partial_{x} u_{2}, u_{4} = \partial_{x} u_{3}; \end{matrix}$ which can be converted into an NFS with three constants, one input and three outputs, $\begin{matrix} (10) & \begin{matrix} u_{2}^{'} = u_{3} u_{1}^{'}, u_{3}^{'} = \partial_{x} u_{2}^{'}, u_{4}^{'} = \partial_{x} u_{3}^{'}, \\ u_{2} (0) = g, u_{3} (0) = g_{3}, u_{4} (0) = g_{4} . \end{matrix} \end{matrix}$

We can see that the constant space of the NFS has three parameters g, $g_{3}$ and $g_{4}$ , which is two more than in the constant space of the X-GPAC. Therefore any solution of the NFS must be of type $X^{3} \times C^{1} {([0, T], X)}^{1} ⇀ C^{1} {([0, T], X)}^{3}$ .

We also see that if $(g, u_{1}, u_{2}, u_{3}, u_{4})$ produces a specification of the X-GPAC, then $(u_{1}, u_{2}, u_{3}, u_{4})$ produces a solution of the NFS for the initial conditions g, $g_{3} = u_{3} (0)$ , $g_{4} = u_{4} (0)$ ; in other words, the NFS generates a function $Φ_{N}$ such that $\begin{matrix} if Φ_{G} (g, u_{1}) = (u_{2}, u_{3}, u_{4}), then Φ_{N} (g, u_{3} (0), u_{4} (0), u_{1}) = (u_{2}, u_{3}, u_{4}) . \end{matrix}$

Thus $Φ_{G}$ is a projection of $Φ_{N}$ , as expected.

5. Partial differential algebraic equations

In this section we will define partial differential algebraic systems, which will prove to be the correct generalization of differentially algebraic equations for our purposes, as will be made clear from our main result (Theorem 2).

Definition 5.1 (Partial differential algebraic equation).

Let $N \in N$ . A partial differential algebraic equation (PDAE) on the N variables $y_{1}, \dots, y_{N}$ is an equation of the form $\begin{matrix} (11) & P (t, y_{1}, \dots, y_{N}, \dots, \partial_{x}^{α_{1}} y_{1}^{(β_{1})}, \dots, \partial_{x}^{α_{N}} y_{N}^{(β_{N})}) = 0, \end{matrix}$ where P is a polynomial in $y_{1}, \dots, y_{N}$ and some of their derivatives, with real coefficients.

Definition 5.2 (System of PDAEs).

Let $K, L \in N$ and $N = K + L$ . A partial differential algebraic system (PDAS), also referred to as system of PDAEs, on the N variables $y_{1}, \dots, y_{N}$ is a system of the form $\begin{matrix} (12) & \{\begin{matrix} P_{ℓ} (t, y_{1}, \dots, y_{N}, \dots, \partial_{x}^{α_{1}} y_{1}^{(β_{1})}, \dots, \partial_{x}^{α_{N}} y_{N}^{(β_{N})}) = 0, & for 1 ⩽ ℓ ⩽ L; \\ y_{ℓ}^{(β)} (0) = g_{ℓ, β}, & for K + 1 ⩽ ℓ ⩽ K + L and 0 ⩽ β < β_{ℓ}, \end{matrix} \end{matrix}$ under the conventions that $P_{ℓ}$ are polynomials in $y_{1}, \dots, y_{N}$ and some of their derivatives, with real coefficients, and $g_{ℓ, β} \in X$ .

We say that $y_{1}, \dots, y_{K}$ are the inputs or independent variables and $y_{K + 1} \dots, y_{K + L}$ are the outputs or dependent variables.

We provide a short explanation on the notation in the previous definition. Each variable $y_{i}$ can appear in the polynomial expressions with space derivatives of order at most $α_{i}$ and time derivatives of order at most $β_{i}$ ; for each $y_{ℓ}$ which is an output, we need to provide $β_{ℓ}$ initial conditions; they correspond to the values of $y_{ℓ}$ and its space derivatives $y_{ℓ}^{(β)}$ of order up to $β_{ℓ} - 1$ at time $t = 0$ , $\begin{matrix} y_{ℓ} (0), y_{ℓ}^{'} (0), \dots, y_{ℓ}^{(β_{ℓ} - 1)} (0) . \end{matrix}$

This is a standard assumption in the theory of PDEs and is a necessary condition for well-posedness (with fewer initial conditions, the system is underdetermined; with more initial conditions, the system is overdetermined).

Definition 5.3 (Quasi-well-posedness of PDAS).

Let $L, K \in N$ and $N = L + K$ . Let $P$ be a PDAS given by Eq. (12) with K inputs, L outputs and J initial conditions and consider the spaces $\begin{matrix} C = X^{J}, I = C^{1} {([0, T], X)}^{K}, O = C^{1} {([0, T], X)}^{L} . \end{matrix}$ Let $U \subseteq C \times I$ . We say that $P$ is quasi-well-posed on U if

(existence) for every $(g, y^{I}) \in U$ , there exists $y^{O} \in O$ such that Eq. (12) holds for $(g, y^{I}, y^{O})$ , where g is the vector of initial conditions, $y^{I} = (y_{1}, \dots, y_{K})$ , $y^{O} = (y_{K + 1}, \dots, y_{K + L})$ ;

(uniqueness) for every $(g, y^{I}) \in U$ , the tuple $y^{O}$ such that Eq. (12) holds is unique;

(closedness) the map $(g, y^{I}) \mapsto y^{O}$ , with domain U and codomain $O$ , given as the unique solution of Eq. (12), defines a closed operator.

Definition 5.4 (Semantics of PDAS).

Let $K, L \in N$ and $N = K + L$ . Let $P$ be a PDAS with K inputs and L outputs. Let $U \subseteq C \times I$ such that $P$ is quasi-well-posed on U. We define the solution of $P$ as the (partial) function $\begin{array}{l} Φ : C \times I ⇀ O; \\ Φ (g, y^{I}) = y^{O}, \end{array}$ whose domain is U and where $y^{O}$ is given by Eq. (12). We also say that $P$ generates Φ on $U = dom (Φ)$ .

A function $Φ : C \times I ⇀ O$ is PDAS-generable if there exists a PDAS $P$ such that $P$ is quasi-well-posed on the domain of Φ and Φ is the solution of $P$ .

We remark that in a PDAS, there is a correspondence between the outputs and a subset of the initial conditions (namely, those for which $β = 0$ ), and so we have the following basic property (cf. Propositions 3.11 and 4.5).

Proposition 5.5.
If $Φ : C \times I ⇀ O$ is PDAS-generable, then $dim (O) ⩽ dim (C)$ .

Our next two results will complete the cycle in Fig. 7, showing that generable functions in each mode can be seen as projections of generable functions in the other modes.

Figure 7.
Main results.
Lemma 5.6 (NFS-generable implies PDAS-generable).

Any NFS-generable function is PDAS-generable.

Proof.
Any normal form equation is a partial differential algebraic equation where the variables occur with time (and space) derivatives of order at most 1; thus the initial conditions in an NFS are exactly those appearing as initial conditions in the corresponding PDAS; in other words, every NFS is a PDAS. □
Lemma 5.7 (PDAS-generable implies X-GPAC-generable).

Let $Φ_{P} : C_{P} \times I_{P} ⇀ O_{P}$ be PDAS-generable with domain $U_{P} \subseteq C_{P} \times I_{P}$ . Then there exists $Φ_{G} : C_{G} \times I_{G} ⇀ M_{G} \times O_{G}$ which is X-GPAC-generable with domain $U_{G} \subseteq C_{G} \times I_{G}$ with the following properties:

$dim (I_{G}) = dim (I_{P}) + 1$ and $dim (C_{G}) ⩾ dim (C_{P})$ ;

for every $(g, y^{I}) \in C_{P} \times I_{P}$ such that $(g, y^{I}) \notin U_{P}$ , we have $(g, g^{*}, y^{I}, y) \notin U_{G}$ for any X-vector $g^{*}$ and any X-stream y;

for every $(g, y^{I}) \in C_{P} \times I_{P}$ such that $(g, y^{I}) \in U_{P}$ , there exists a unique X-vector $g^{*}$ and X-stream y such that $(g, g^{*}, y^{I}, y) \in U_{G}$ ; moreover, there exists a unique X-stream vector $y^{*}$ such that $\begin{matrix} Φ_{G} (g, g^{*}, y^{I}, y) = (y^{*}, Φ_{P} (g, y^{I})) . \end{matrix}$

In other words,

Φ_{P}

is a projection of

Φ_{G}

The equality and inequality in the first bullet will be explained below.

Proof.
Let $Φ_{P} : C_{P} \times I_{P} ⇀ O_{P}$ be PDAS-generable with domain $U_{P} \subseteq C_{P} \times I_{P}$ . Denote by $P$ the PDAS that generates $Φ_{P}$ .

The important idea of the proof is understanding how to write partial differential algebraic equations with X-GPAC modules. We start with channels for all variables $y_{1}, \dots, y_{N}$ . To obtain derivatives in time, we include modules and connections as in Fig. 8.

Figure 8.
An X-GPAC for computing time derivatives.

Note that the channels on Fig. 8 must obey the system $\begin{matrix} \{\begin{matrix} v_{1} = y_{i} + v_{4}; \\ v_{2} = v_{1} + v_{2}; \\ v_{3} = g_{i, 0} + \int v_{2} d t; \\ v_{4} = - v_{3}; \\ y_{i} (0) = g_{i, 0} \end{matrix} \Rightarrow \{\begin{matrix} v_{1} = 0; \\ v_{2} = y_{i}^{'}; \\ v_{3} = y_{i}; \\ v_{4} = - y_{i}; \end{matrix} \end{matrix}$ so that we obtain $y_{i}^{'}$ in the channel labeled $v_{2}$ . Observe that we must include an initial setting (in the above case, the initial value $y_{i} (0)$ ) every time we need to take a time derivative. We also need to include the linear channel $t \in C^{1} ([0, T], X)$ given by the map $(t, x) \mapsto t$ . By composing several of these modules, we can get all time derivatives that appear in $P$ , that is, we obtain $y_{i}^{(β)}$ for $i = 1, \dots, N$ and $β = 0, \dots, β_{i} - 1$ .

Next, by successive applications of the differential module (see Fig. 9) we obtain all the partial derivatives appearing in $P$ , which are of the form $\partial_{x}^{α} y_{i}^{(β)}$ for $i = 1, \dots, N$ , $α = 0, \dots, α_{i}$ and $β = 0, \dots, β_{i} - 1$ .

Figure 9.
An X-GPAC for computing spatial derivatives.

Next, we compute the polynomial expressions $P_{ℓ}$ from the partial derivative terms using constants, multipliers and adders. Any term appearing in the polynomials $P_{ℓ}$ is of the form $a t_{1}^{d_{1}} \dots t_{n}^{d_{n}}$ , where $a \in R$ (obtainable from a constant module), each $t_{i}$ is either t (obtainable using the linear input t) or some $\partial_{x}^{α} y_{i}^{(β)}$ , and thus can be obtained by a constant module and a sequence of multipliers. Each polynomial $P_{ℓ}$ is a finite sum of such terms, and thus can be obtained by a sequence of adders.

Finally, to enforce the relation $P_{ℓ} (t, y_{1}, \dots, y_{N}, \dots, \partial_{x}^{α_{1}} y_{1}^{(β_{1})}, \dots, \partial_{x}^{α_{N}} y_{N}^{(β_{N})}) = 0$ , we add $y_{K + ℓ}$ to both sides of the equation and include an adder and feedback loop, as shown on Fig. 10. We can then loop the channel labeled $y_{K + ℓ}$ back to the start, enforcing it to be a mixed channel.

Figure 10.
Feedback loop implementing $P_{ℓ} = 0$ .

Figure 11 illustrates the several steps of our construction, which results in an X-GPAC $G$ . We must next address the underlying spaces of $G$ . The constant space is constructed with the initial settings of integrators, which only appear in the phase where we build time derivatives. For every original variable $y_{i}$ which appears in $P$ with time derivatives of order up to $β_{i}$ , we have included the $β_{i}$ initial settings $g_{i, β} = y_{i}^{(β)} (0)$ , $0 ⩽ β < β_{i}$ . Hence, the constant space of $G$ , denoted by $C_{G}$ , is an extension of $C_{P}$ , which only takes into account the initial settings associated with the output variables; therefore $dim (C_{G}) ⩾ dim (C_{P})$ .

Figure 11.
Construction of X-GPAC from a PDAS.

In regards to the input space, the original input variables $y_{i}$ , $i = 1, \dots, L$ appear in $G$ as proper input channels. The only other proper input channel is the linear input t, which can be seen as an ‘explicit time’ inserted into the system. In this way, $dim (I_{G}) = dim (I_{P}) + 1$ , which proves the first bullet.

Observe that the original output variables $y_{K + ℓ}$ , $ℓ = 1, \dots, L$ , all appear in $G$ as mixed channels because of the feedback loop that ensures $P_{ℓ} = 0$ . There are (potentially many) other mixed and proper output channels in $G$ , which carry the value of either partial derivatives $\partial_{x}^{α} y_{i}^{(β)}$ , multiplying terms $a t_{i}^{d_{i}} \dots t_{n}^{d_{n}}$ or sums of multiplying terms; hence $dim (M_{G} \times O_{G}) ⩾ dim (O_{P})$ .

The next step is to find a suitable $U_{G}$ for the domain of $Φ_{G}$ . By quasi-well-posedness of $P$ , we know that, for every $(g, y^{I}) \in U_{P}$ , there exists a unique $y^{O} \in O_{P}$ that solves $P$ . Thus, if we define $(g^{}, g)$ as the vector of initial conditions of all time derivatives of the input and output variables, which are of the form $y_{i}^{(β)} (0)$ for $i = 1, \dots, N$ and $β = 0, \dots, β_{i} - 1$ , we can infer that $g^{}$ depends uniquely on $(y^{I}, y^{O})$ , and thus it depends uniquely on $(g, y^{I})$ . With this in mind we define $\begin{array}{rcl} U_{G} & = & {(g^{}, g, y^{I}, t) : (g, y^{I}) \in U_{P} and (g^{}, g) = (y_{1}, \dots, y_{1}^{(β_{1} - 1)}, \dots, y_{N}, \dots, y_{N}^{(β_{N} - 1)}) ⇂_{t = 0}, \\ where (y_{1}, \dots, y_{K}) = y^{I} and (y_{K + 1}, \dots, y_{K + L}) = y^{O} = Φ_{P} (g, y^{I})} . \end{array}$

To define $Φ_{G}$ , we need to define the value of all the mixed and output channels appearing in $G$ . As described above, these are either the output variables $y_{K + 1}, \dots, y_{K + L}$ , or uniquely obtained from the tuple $(y^{I}, y^{O}, t) = (y_{1}, \dots, y_{K}, y_{K + 1}, \dots, y_{K + L}, t)$ via partial derivatives, products and sums. If we let $y^{}$ denote the value of all the mixed and output channels which are not the output variables, then $y^{}$ depends uniquely on $(y^{I}, y^{O}, t)$ and thus also on $(g, y^{I})$ , so that we can define $\begin{matrix} Φ_{G} (g^{}, g, y^{I}, t) = \{\begin{matrix} (y^{}, Φ_{P} (g, y^{I})) & if (g, g^{}, y^{I}, t) \in U_{G}; \\ undefined & otherwise . \end{matrix} \end{matrix}$

By this construction, $U_{G}$ and $Φ_{G}$ satisfy the second and third bullets, and all is left is to show that $Φ_{G}$ is the specification of $G$ on $U_{G}$ . By quasi-well-posedness of $P$ on $U_{P}$ and the above discussion, it is clear that for $(g^{}, g, y^{I}, t) \in U_{G}$ , the tuple $(y^{}, y^{O}) \in O_{G}$ that solves the equational specification of $G$ exists and is unique; that is to say, $y^{O}$ is given by $Φ_{P} (g, y^{I})$ and $y^{}$ is obtained from $(y^{I}, y^{O}, t)$ via partial derivatives, products and sums.

To prove closedness of $Φ_{G}$ , consider a sequence3
³
Since the last component of any tuple in $U_{G}$ must be the linear input t, we only need to consider sequences for the other three subtuples.

$(g_{n}^{}, g_{n}, y_{n}^{I}, t) \in U_{G}$ such that $\begin{matrix} (g_{n}^{}, g_{n}, y_{n}^{I}, t) \to (g^{}, g, y^{I}, t) and Φ_{G} (g_{n}^{}, g_{n}, y_{n}^{I}, t) \to (y^{}, y^{O}); \end{matrix}$ by defining $(y_{n}^{}, y_{n}^{O}) = Φ_{G} (g_{n}^{}, g_{n}, y_{n}^{I}, t)$ , we have $\begin{matrix} (g_{n}, y_{n}^{I}) \to (g, y^{I}) and Φ_{P} (g_{n}, y_{n}^{I}) = y_{n}^{O} \to y^{O} . \end{matrix}$

By closedness of $Φ_{P}$ , we have $\begin{matrix} (g, y^{I}) \in U_{P} and Φ_{P} (g, y^{I}) = y^{O} . \end{matrix}$

Now $(g_{n}^{}, g_{n})$ corresponds to the values of the variables in $(y_{n}^{I}, y_{n}^{O})$ and some of their derivatives at $t = 0$ . By closedness of the differential operator, we can take limits and conclude that $(g^{}, g)$ corresponds to the values of the variables in $(y^{I}, y^{O})$ and their derivatives at $t = 0$ ; thus, $(g^{}, g, y^{I}, t) \in U_{G}$ . Also, since partial derivatives, products and sums are closed operators, we infer that $(y_{n}^{}, y_{n}^{O}) \to Φ_{G} (g^{}, g, y^{I}, t)$ , so that $Φ_{G} (g^{}, g, y^{I}, t) = (y^{}, y^{O})$ , which concludes the proof. □
Example 5.8.
We provide an example of the construction in the previous Lemma by applying it to the one-dimensional heat equation, which can be written as the following PDAS, $\begin{matrix} u^{'} = \partial_{x}^{2} u, u (0) = x . \end{matrix}$

To produce a solution to the heat equation, we consider, for example, a square-integrable initial condition $g \in C (R) \cap L^{2} (R)$ , for which the solution can be obtained via the heat kernel, that is, $Φ_{P} : X ⇀ C^{1} ([0, T], X)$ is given by $Φ_{P} (g) = u$ , where $\begin{matrix} u (t, x) = \int_{R} K (t, x - y) g (y) d y, K (t, x) = \frac{1}{\sqrt{4 π t}} e^{- x^{2} / 4 t} . \end{matrix}$

Let us construct an X-GPAC with specification $Φ_{G}$ such that $Φ_{P}$ is a projection of $Φ_{G}$ . We start with a channel for the variable u. Using the constructions on Figs 8 and 9 we obtain channels with the derivatives $u^{'}$ , $\partial_{x} u$ and $\partial_{x}^{2} u$ . We can then construct the partial differential algebraic expression $P (u, u^{'}, \partial_{x} u, \partial_{x}^{2} u) = u^{'} - \partial_{x}^{2} u$ using one constant module, one multiplier module and one adder module. Finally, we include an adder and feedback loop as on Fig. 10 and loop the variable u to the beginning. The final X-GPAC can be seen on Fig. 12.

Figure 12.
Construction of X-GPAC from the heat equation.

We can see that the X-GPAC has one additional input t, which specifies linear time. It should also be noted that the heat equation has only one variable u, whereas the X-GPAC has a total of twelve channels and thus twelve variables (of course, most of those are redundant). Therefore, any specification of the X-GPAC must be of type $X^{1} \times C^{1} {([0, T], X)}^{1} ⇀ C^{1} {([0, T], X)}^{11}$ .

We can also see that if $Φ_{P} (g) = u$ produces a solution to the heat equation, then there is a unique tuple u of values that satisfy $F (g, t, u) = u$ , where F is the induced operator of the X-GPAC in Fig. 12, g is the initial condition of the integrator and t is the input channel (linear time). In other words, we can construct a specification $Φ_{G} (g, t) = u$ of the X-GPAC such that $Φ_{P}$ is a projection of $Φ_{G}$ , as expected.

Figure 13.
An X-GPAC that generates solutions to the heat equation.

It should be clear from this example that the construction in Lemma 5.7 is universal (in the sense that it works for any PDAS) but is not necessarily optimal (in the sense that it does not add a minimal number of new variables). In fact, one could construct a much simpler X-GPAC (with only three modules!) that generates solutions to the heat equation, as in Fig. 13. The reader can verify that $Φ_{P}$ is also a projection of the specification of this X-GPAC.

Finally we can state and prove our main result.
Theorem 2 (X-GPAC characterization theorem).

Let $Φ : X^{j} \times C^{1} {([0, T], X)}^{k} ⇀ C^{1} {([0, T], X)}^{ℓ}$ . Then the following are equivalent:

Φ is the projection of an X-GPAC-generable function;

Φ is the projection of an NFS-generable function;

Φ is the projection of a PDAS-generable function.

Proof.
We prove each implication:

(X-GPAC ⇒ NFS) Let Φ be the projection of an X-GPAC-generable function $Φ_{G}$ . By Lemma 4.7, $Φ_{G}$ is the projection of an NFS-generable function $Φ_{N}$ , and so Φ is a projection of $Φ_{N}$ .

(NFS ⇒ PDAS) Similar to the previous case, but use Lemma 5.6 instead.

(PDAS ⇒ X-GPAC) Similar to the previous case, but use Lemma 5.7 instead. □
6. Conclusion

In this paper we have seen a model of analog computation based on the Shannon GPAC. In this model we have taken streams whose value lie in a general function space X. Theorem 2 is evidence that our model of computation provides a suitable generalization of the original work on the GPAC. We can thus think of solutions to certain differential equations as outputs or fixed points of certain analog networks. We have also seen that (quasi)well-posedness conditions play an important role in this study.

We have only considered the case $X = C (R)$ . A possible direction for research would be considering other function spaces, such as $\begin{matrix} X = C^{p} (Ω) or X = H^{p} (Ω), \end{matrix}$ where Ω is, for example, a domain in $R^{n}$ , either unbounded (for example, $Ω = R^{n}$ ) or bounded (for example, $Ω = {[0, 1]}^{n}$ ), and $H^{p}$ denotes Sobolev spaces. In the case that Ω is bounded, we may further restrict our space X to functions with prescribed behaviour on the boundary, such as Dirichlet boundary conditions ( $f = 0$ on $\partial Ω$ ). We believe that such a direction could allow us to make interesting connections with the field of partial differential equations, where such spaces are ubiquitous.

Another possible direction would be to consider modules operating on multiple data types, which could be written as $\begin{matrix} F : τ_{1}^{ℓ_{1}} \times \dots \times τ_{n}^{ℓ_{n}} \to τ; \end{matrix}$ in this way we would have channels of different types and would be able to define a notion of many-typed analog networks. This direction will probably have a strongly technical aspect, but it could lead to a model of computation on many-sorted algebras as studied by Tucker and Zucker [31,32,34].

As an interesting question we may wonder whether our framework allows computability of functions which are known not to be Shannon GPAC-generable, such as the gamma function (as noted by Shannon) $\begin{matrix} Γ (t) = \int_{0}^{\infty} x^{t - 1} e^{- x} d x . \end{matrix}$

There are well-known differential equations in two variables related to the gamma function; for example (see [22, p. 174]), if we define the incomplete gamma functions $\begin{array}{l} γ (t, z) = \int_{0}^{z} x^{t - 1} e^{- x} d x; \\ Γ (t, z) = \int_{z}^{\infty} x^{t - 1} e^{- x} d x, \end{array}$ then both incomplete gamma functions satisfy the differential equation (for $w = w (t, z)$ ) $\begin{matrix} \frac{d^{2} w}{d z^{2}} + (1 + \frac{1 - t}{z}) \frac{d w}{d z} = 0 \end{matrix}$ and we have in addition $\begin{matrix} γ (t, z) + Γ (t, z) = Γ (t), γ (t, 0) = 0, Γ (t, \infty) = 0; \end{matrix}$ we may ask whether such relations could be implemented on a more general analog network.

Footnotes

Acknowledgements

The research of Diogo Poças and Jeffery Zucker was funded, respectively, by Fundação para a Ciência e Tecnologia (Doctoral Grant, Portugal) and the Natural Sciences and Engineering Research Council (Canada).

References

Bournez,

Graça and

Pouly, On the functions generated by the general purpose analog computer, 2016, submitted on 21 Jan 2016, arXiv:1602.00546.

Bush, The differential analyzer. A new machine for solving differential equations, Journal of the Franklin Institute 212(4) (1931), 447–488. doi:10.1016/S0016-0032(31)90616-9.

Campagnolo,

Moore and

J.F.

Costa, An analog characterization of the Grzegorczyk hierarchy, Journal of Complexity 18(4) (2002), 977–1000. doi:10.1006/jcom.2002.0655.

Courant and

Hilbert, Methods of Mathematical Physics, Vol. 2, Interscience Publishers, Inc., 1953.

Graça, Some recent developments on Shannon’s general purpose analog computer, Mathematical Logic Quarterly 50(4–5) (2004), 473–485.

Graça and

J.F.

Costa, Analog computers and recursive functions over the reals, Journal of Complexity 19(5) (2003), 644–664. doi:10.1016/S0885-064X(03)00034-7.

Grzegorczyk, Computable functions, Fundamenta Mathematicae 42 (1955), 168–202.

Grzegorczyk, On the definitions of computable real continuous functions, Fundamenta Mathematicae 44 (1957), 61–71.

Hadamard, Lectures on Cauchy’s Problem in Linear Partial Differential Equations, Dover, 1952.

10.

D.R.

Hartree, Calculating Instruments and Machines, Cambridge University Press, 1950.

11.

P.A.

Holst, Svein Rosseland and the Oslo Analyzer, IEEE Annals of the History of Computing 18(4) (1996), 16–26. doi:10.1109/85.539912.

12.

N.D.

James and

J.I.

Zucker, A class of contracting stream operators, The Computer Journal 56 (2013), 15–33. doi:10.1093/comjnl/bxs054.

13.

Johansson, Early analog computers in Sweden – With examples from Chalmers University of Technology and the Swedish aerospace industry, IEEE Annals of the History of Computing 18(4) (1996), 27–33. doi:10.1109/85.539913.

14.

Kleene, Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society 79 (1955), 312–340. doi:10.1090/S0002-9947-1955-0070594-4.

15.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles I, Comptes Rendus des Séances d l’Académie des Sciences, Paris 240 (1955), 2478–2480.

16.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles II, Comptes Rendus des Séances d l’Académie des Sciences, Paris 241 (1955), 13–14.

17.

Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles III, Comptes Rendus des Séances d l’Académie des Sciences, Paris 241 (1955), 151–153.

18.

Lipshitz and

Rubel, A differentially algebraic replacement theorem, Proceedings of the American Mathematical Society 99(2) (1987), 367–372. doi:10.1090/S0002-9939-1987-0870803-1.

19.

J.W.

Mills, The nature of the extended analog computer, Physica D: Nonlinear Phenomena 237(9) (2008), 1235–1256. doi:10.1016/j.physd.2008.03.041.

20.

Moore, Recursion theory on the reals and continuous-time computation, Theoretical Computer Science 162(1) (1996), 23–44. doi:10.1016/0304-3975(95)00248-0.

21.

Mycka and

J.F.

Costa, Real recursive functions and their hierarchy, Journal of Complexity 20(6) (2004), 835–857. doi:10.1016/j.jco.2004.06.001.

22.

F.W.J.

Olver,

D.W.

Lozier,

R.F.

Boisvert and

C.W.

Clark, NIST Handbook of Mathematical Functions, Cambridge University Press, 2010.

23.

Pouly, Continuous models of computation: from computability to complexity, PhD thesis, École Polytechnique and Universidade do Algarve, 2015.

24.

Pour-El, Abstract computability and its relations to the general purpose analog computer, Transactions of the American Mathematical Society 199 (1974), 1–28. doi:10.1090/S0002-9947-1974-0347575-8.

25.

Pour-El and

Richards, Computability in Analysis and Physics, Springer-Verlag, 1989. doi:10.1007/978-3-662-21717-7.

26.

Renardy and

R.C.

Rogers, An Introduction to Partial Differential Equations, Vol. 13, 2nd edn, Springer-Verlag, New York, 2006.

27.

L.A.

Rubel, The extended analog computer, Advances in Applied Mathematics 14(1) (1993), 39–50. doi:10.1006/aama.1993.1003.

28.

Shannon, Mathematical theory of the differential analyser, Journal Mathematical Physics 20 (1941), 337–354. doi:10.1002/sapm1941201337.

29.

J.S.

Small, General-purpose electronic analog computing: 1945–1965, IEEE Annals of the History of Computing 15(2) (1993), 8–18. doi:10.1109/85.207740.

30.

Thompson and

P.G.

Tait, Treatise on Natural Philosophy, Vol. 1, 2nd edn, Cambridge University Press, 1880, Part I.

31.

J.V.

Tucker and

J.I.

Zucker, Computable functions and semicomputable sets on many sorted algebras, in: Handbook of Logic for Computer Science,

Abramsky,

Gabbay and

Maibaum, eds, University Series in Mathematics, Vol. V, Oxford University Press, 2000, pp. 317–523.

32.

J.V.

Tucker and

J.I.

Zucker, Computability of analog networks, Theoretical Computer Science 371 (2007), 115–146. doi:10.1016/j.tcs.2006.10.018.

33.

J.V.

Tucker and

J.I.

Zucker, Continuity of operators on continuous and discrete time streams, Theoretical Computer Science 412 (2011), 3378–3403. doi:10.1016/j.tcs.2011.04.012.

34.

J.V.

Tucker and

J.I.

Zucker, Computability of operators on continuous and discrete time streams, Computability 3 (2014), 9–44.

35.

Weihrauch, Computable Analysis – An Introduction, Texts in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, 2000. doi:10.1007/978-3-642-56999-9.

Analog networks on function data streams

Abstract

Keywords

1. Introduction

Definition 1.1 (Shannon modules).

Theorem 1 (GPAC characterization theorem).

2. Limitations of the Shannon GPAC

1 An implementation of the EAC (or at least, of some of its components) has been achieved with the work of Mills [19].

Definition 3.1 (Closed operator).

Definition 3.5 (X-GPAC induced operator).

Proposition 3.8 ([26, p. 240, Exercise 8.7]).

Proposition 3.11. If Φ : C × I ⇀ M × O is X-GPAC-generable, then dim ( C ) ⩽ dim ( M ) + dim ( O ) . 4. Normal form systems

Definition 4.2 (Normal form system over X).

Definition 4.3 (Quasi-well-posedness of NFS).

Definition 4.4 (Semantics of NFS).

Lemma 4.7 (X-GPAC-generable implies NFS-generable).

Definition 5.1 (Partial differential algebraic equation).

Definition 5.2 (System of PDAEs).

Definition 5.3 (Quasi-well-posedness of PDAS).

Definition 5.4 (Semantics of PDAS).

Footnotes

Acknowledgements

References

¹
An implementation of the EAC (or at least, of some of its components) has been achieved with the work of Mills [19].

Proposition 3.11.
If $Φ : C \times I ⇀ M \times O$ is X-GPAC-generable, then $dim (C) ⩽ dim (M) + dim (O)$ .
4. Normal form systems