Simon Bliudze
email: simon.bliudze@imag.fr

Daniel Krob

Modelling of Complex Systems: Systems as dataflow machines

Keywords: Complex system, Hybrid system, Non-standard analysis, Physical system, Software system, System modelling, Temporized systems, Time scale, Turing machine

We develop a unified functional formalism for modelling complex systems, that is to say systems that are composed of a number of heterogeneous components, including typically software and physical devices. Our approach relies on non-standard analysis that allows us to model continuous time in a discrete way.

Systems are defined as generalized Turing machines with temporized input, internal and output mechanisms. Behaviors of systems are represented by transfer functions. A transfer function is said to be implementable if it is associated with a system. This notion leads us to define a new classwhich is natural in our framework -of computable functions on (usual) real numbers.

We show that our definitions are robust: on one hand, the class of implementable transfer functions is closed under composition; on the other hand, the class of computable functions in our meaning includes analytical functions whose coefficients are computable in the usual way, and is closed under addition, multiplication, differentiation and integration. Our class of computable functions also includes solutions of dynamical and Hamiltonian systems defined by computable functions. Hence, our notion of system appears to take suitably into account physical systems.

Introduction 1.Motivation

The notion of "system" is a typical generic -and unclear -concept which is used in many different contexts in totally different meanings. In "hard" sciences, one can find it for instance in mathematics, physics, electronics, control theory or computer science. Think for instance of dynamical, mechanical, Hamiltonian, hybrid, holonomic, embedded, concurrent or distributed systems (see [START_REF] Alur | The Algorithmic Analysis of Hybrid Systems[END_REF][START_REF] Bacon | Concurrent systems -An Integrated Approach to Operating Systems, Database, and Distributed Systems[END_REF][START_REF] Krob | Modelling of Complex Software Systems: A Reasoned Overview[END_REF][START_REF] Marwedel | Embedded System Design[END_REF][START_REF] Meyer | Introduction to Hamiltonian Dynamical Systems and the N-Body Problem[END_REF][START_REF] Robert | Les systèmes dynamiques discrets[END_REF][START_REF] Sontag | Mathematical Control Theory: Deterministic Finite Dimensional Systems[END_REF]). In industrial applications, one will also speak of transportation, electro-mechanical, software or information systems, just to give a limited number of other examples.

Due to this both really huge and quite vague perimeter, it is therefore rather difficult to give any precise mathematical definition of a system that would cover all aspects of this concept. It indeed appears that only a few number of authors tried to propose global frameworks for discussing systems. These formalisms can moreover be roughly divided into two main categories. On one hand, one can find several "physical-oriented" formalisms (see for instance -who proposed his classical theory of systems for the purpose of control theory, but also [START_REF] Cha | Fundamentals of Modeling and Analyzing Engineering Systems[END_REF][START_REF] Severance | System Modeling and Simulation: An Introduction[END_REF][START_REF] Zeigler | Theory of Modeling and Simulation -Integrating Discrete Event and Continuous Complex Dynamic Systems[END_REF] where other points of view of the same type are developed), even if they intend to cover both continuous and discrete aspects of systems; on the other hand, one will find more "logical-oriented" frameworks, well adapted for describing software systems (see typically -for such an approach where systems are defined through their capacity of being described in a given specification language; note of course that many other formalisms of the same kind can be found in the computer science literature, e.g. [START_REF] Börger | Abstract State Machines -A method for high-level system design and analysis[END_REF][START_REF] Marwedel | Embedded System Design[END_REF][START_REF] Schneider | Verification of reactive systems -Formal methods and algorithms[END_REF][START_REF] Zurawski | Embedded Systems Handbook[END_REF]).

In all these different approaches, continuous and discrete systems are however quite difficult to manage together due to the fact that continuous and discrete time modelings cannot be mixed so easily. Several attempts to get round this problem were done during the two last decades leading in particular to the theory of hybrid systems that was developed jointly in control theory (see [START_REF] Sontag | Mathematical Control Theory: Deterministic Finite Dimensional Systems[END_REF][START_REF] Zaytoun | Systèmes dynamiques hybrides[END_REF]) and in computer science (see [START_REF] Alur | The Algorithmic Analysis of Hybrid Systems[END_REF][START_REF] Alur | Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems[END_REF][START_REF] Lygeros | Lecture notes on hybrid systems[END_REF]). The main issue with this theory is however that the underlying formalism has some troubling properties -such as the Zeno effect which corresponds to the fact that an hybrid system can change of state an infinite number of times within a finite time -that one usually prefers to avoid in a robust modeling approach. Other interesting and slightly different attempts in the same direction can also be found in Rabinovitch and Trakhtenbrot (see [START_REF] Rabinovitch | Automata over Continuous Time[END_REF][START_REF] Trakhtenbrot | Understanding Basic Automata Theory in the Continuous Time Setting[END_REF]) who tried to reconstruct a finite automata theory on the basis of a real time framework.

Everybody would therefore probably agree that there does not exist any commonly and widely agreed framework that integrates smoothly continuous and discrete systems (see [START_REF] Bournez | A Survey on Continuous Time Computations[END_REF] for a wonderful and quite exhaustive survey of all the existing research on this topic), the key problem beeing that one is usually always obliged to choose -at one moment or another -between the two underlying ways of modeling time. Our paper intends hence to bring a new contribution to this challenging problem by adressing it from another point of view. To this aim, we propose to revisit the formalisms for dealing with systems with two key ingredients -one old, Turing machines, and one new, non-standard analysis, the novelty being of re-visiting the old topic with the new one -that we will now discuss more in details.

• Ingredient 1: we will place us here in the line of the algorithmic complexity theory (in the meaning of the classical textbook [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF] or more precisely in the continuation of the works described typically in [START_REF] Bournez | A Survey on Continuous Time Computations[END_REF]), systems being defined as a new kind of computing timed-machines. We shall indeed integrate in a common "machine" model the key features that can be found in quite all concrete "systems": first, the fact that systems are fundamentally characterized by a temporal behavior since they are always manipulating physical or data-flows (depending on their continuous or discrete structure) and, secondly, the fact that they always have an internal architecture since they are usually constructed by integrating (i.e. composing) other smaller sub-systems and abstracting the result of this composition process (this last notion being here taken in the meaning of abstract interpretation -see [START_REF] Cousot | Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints[END_REF]). Note that "complex" systems can then just be seen as systems obtained through a large number of integration/abstraction processes 1 .

• Ingredient 2: to obtain a formal definition of a system which captures in a common framework both continuous and discrete systems, our key idea is to use a (discrete) modelling of time based on a non-standard model of real numbers (in the meaning of non-standard analysis -see [START_REF] Cutland | Nonstandard Analysis and its Applications[END_REF][START_REF] Davis | Applied nonstandard analysis[END_REF][START_REF] Diener | Nonstandard Analysis in Practice[END_REF][START_REF] Diener | Nonstandard Analysis in Practice[END_REF][START_REF] Diener | Analyse non standard[END_REF][START_REF] Robinson | Non Standard Analysis[END_REF]). Making this quite strong step allows us indeed to take into account in the same way both physical and software systems, while keeping several natural system intuitions. Mixing this non-standard approach with the Turing-machine like ingredient which was described just above, leads us in particular to enlarge quite seriously the family of computable functions with respect to more classical approaches (see [START_REF] Blum | Complexity and Real Computation[END_REF][START_REF] Bournez | A Survey on Continuous Time Computations[END_REF][START_REF] Moore | Recursion theory on the reals and continuous-time computation[END_REF]): the analytical functions whose coefficients are Turingcomputable are for instance computable in our formalism, which is usually not the case in other real-oriented computability frameworks.

With these two ingredients, we shall therefore revisit in this paper -and try to mix -both classical control theory approaches to system theory (see for example [START_REF] Sontag | Mathematical Control Theory: Deterministic Finite Dimensional Systems[END_REF]) and complexity theory approaches (see for instance [START_REF] Bournez | A Survey on Continuous Time Computations[END_REF]) within a common non-standard point of view. This will lead us in particular to define a class of implementable transfer functions which enjoys several fundamental properties. First, it is closed under composition (cf. Theorem 3.5), which is a typical property required in the context of systems engineering. Moreover, its sub-class of computable functions is closed under addition, multiplication, differentiation and integration. These properties allow us to prove that solutions of dynamical and Hamiltonian systems defined using computable functions are themselves computable (in our meaning), which shows that our notion of system is suitable for taking into account physical systems.

Due to the fact that systems -as defined in our paper -are natural extensions of Turing machines, we obtained therefore a formal definition of systems where both software and physical systems can be modelled and described in a unified way. We believe that our formalism may be used as the basis of a complexity theory -still to be developed -for systems which appear now as a timed-extension (adding time) of Turing machines in the same way in some sense that Turing machines are themselves spaceextension (adding memory) of classical automata.

Let us finally add that this paper came out in part from S. Bliduze's dissertation (see [START_REF] Bliudze | A Framework for Studying Complex Industrial Systems: An Example Based on the UMTS Infrastructure[END_REF][START_REF] Bliudze | Modelling of Complex Systems I -A Functional Approach: Time, Data and Systems[END_REF]) in the line of previous works of the two authors (see [START_REF] Bliudze | Towards a Functional Formalism for Modelling Complex Industrial Systems, Com-PlexUs[END_REF][START_REF] Krob | Modelling of Complex Software Systems: A Reasoned Overview[END_REF]) on the same subject.

Non-Standard Analysis

To develop a global (discrete) unified framework for dealing both with continuous and discrete systems, let us first go back to the 18th century representation of real numbers (see the first annex of [START_REF] Lakatos | Preuves et réfutations[END_REF] for a very interesting reasoned introduction to the subject). In the 17th and 18th centuries, the common idea on real numbers was indeed quite different from the modern one. In differential calculus, reasonings were for instance typically carried out with the help of special quantities, called "infinitesimals", which had the strange property of "vanishing" when added with any usual real quantity (cf. the famous article of D'Alembert on the subject -see [START_REF] Le Rond | Article "Différentiel[END_REF] -published in the 1754 Diderot-D'Alembert encyclopedia) 2 . For instance, one obtained in this historical framework the derivative f (x) of a given function f (x) by considering the increment of the function given an infinitesimal increment dx of the variable x and applying directly (modulo infinitesimals) the following exact "computational" formula:

f (x) = f (x + dx) -f (x) dx .
For example, applying this mode of reasoning to f (x) = x 2 leads to the following computation

f (x) = (x + dx) 2 -x 2 dx = 2 x dx + (dx) 2 dx = 2x + dx ≈ 2x ,
where the last relation signifies that dx, being infinitesimal, vanishes in the final addition.

It took in fact around two centuries to be able to give a precise mathematical definition of the concept of infinitesimal which was only formalized by Robinson in the 60's (see [START_REF] Robinson | Non Standard Analysis[END_REF]). He indeed introduced the set * R of non-standard real numbers 3 , which is a real-closed field that contains all usual real numbers, but also infinitesimal real numbers, i.e. non-zero elements of * R that have their absolute value strictly less than any usual positive real number r ∈ R * + , and infinite real numbers, their inverses, i.e. those with an absolute value strictly greater than any usual real number r ∈ R (see Figure 1). 2 As Lakatos explains in [START_REF] Lakatos | Preuves et réfutations[END_REF], modern real analysis emerged largely in the 19th century -within Cauchy and Weierstrass works -from the difficulty of formalizing properly this not very rigorous (at this moment of history) notion. 3 A star on the left of a symbol -as in * R -stands always for "non-standard", whereas on the right, it just means that the single real number 0 is excluded from the considered set, as in R * or * R * (that are denoting respectively the usual and non-standard sets of real numbers which are different from zero).

To convince the reader that there is nothing mysterious behind non-standard real numbers, we will now make a brief introduction to the topic in order to be -as much as possible -self-contained in this paper. The reader willing to learn more about non-standard analysis may of course refer to the following classical textbooks [START_REF] Cutland | Nonstandard Analysis and its Applications[END_REF][START_REF] Davis | Applied nonstandard analysis[END_REF][START_REF] Diener | Nonstandard Analysis in Practice[END_REF][START_REF] Diener | Nonstandard Analysis in Practice[END_REF][START_REF] Diener | Analyse non standard[END_REF][START_REF] Kanovei | Nonstandard analysis, axiomatically[END_REF] and papers [START_REF] Delfini | The Vibrating String[END_REF][START_REF] Diener | Ducks and rivers: three existence results[END_REF][START_REF] Troesch | Analyse non standard et équations de Van der Pol. II. Perturbations singulières et analyse non standard[END_REF]. Let us thus introduce the adaptation, due to Lindstrøm (see [START_REF] Cutland | Nonstandard Analysis and its Applications[END_REF]), of the model-theoretical construction of * R (see [START_REF] Barwise | Handbook of Mathematical Logic[END_REF][START_REF] Jensen | Model Theoretical Algebra[END_REF]) which is probably the most intuitive for "standard" scientists. Using Zorn's Lemma, we should first consider an additive measure m on N -that we will fix throughout all this paper -with the following properties4 :

• Property 1: for all A ⊂ N, m(A) is defined and is either 0 or 1,

• Property 2: m(A) = 0 for every finite subset A of N,

• Property 3: m(N) = 1.
The set of non-standard real numbers * R is then defined as the quotient of the set R N of infinite sequences of usual real numbers by the equivalence relation ≡ m defined by setting:

(a n ) n≥0 ≡ m (b n ) n≥0 iff m({n ∈ N, a n = b n }) = 1 .
Using the properties of an additive measure, one can now equip the set * R with an addition, a product and an ordering by setting for every a = [(a n ) n≥0 ] and b = [(b n ) n≥0 ] (where [ ] denotes the class of a sequence of real numbers with respect to the equivalence relation ≡ m ):

• addition: a + b = [(a n + b n ) n≥0 ],
• product:

a b = [(a n b n ) n≥0 ],
• order:

a < b iff m({n ∈ N, a n < b n }) = 1.
The reader will indeed easily establish that these operations are independent of the representatives chosen for defining them. Moreover it is also quite easy to show that these operations give a structure of totally ordered field to * R. Let us for instance prove that each non-zero element of * R is invertible to give an example of the mode of reasoning to use. Let therefore a = [(a n ) n≥0 ] be an element of * R different from its obvious zero element 0 = [(0) n≥0 ]. Being different from 0 means by definition that the measure m(A) of the set A = {n ∈ N, a n = 0} is equal to 0 (which implies that m(N -A) = 1 according to the properties satisfied by m). Let us now consider the sequence (b n ) n≥0 of R N defined by setting:

b n = 1/a n for every n / ∈ A, b n = 0 for every n ∈ A.
It is therefore easy to see that one has {n ∈ N, a n b n = 1} = N -A, which immediately implies that the sequence (a n b n ) n≥0 is equivalent to the constant sequence (1) n≥0 due to the fact that m(N -A) = 1, which is obviously the neutral element 1 of the product of * R, i.e. that one has a b = 1.

The totally ordered field * R contains of course the usual real numbers of R that can be identified to the classes of the constant sequences. However it also contains new interesting types of elements:

• infinitesimal numbers, i.e. elements x ∈ * R such that -a < x < a for every real number a ∈ R,

• infinite numbers, i.e. elements x ∈ * R such that x > a or x < -a for every real number a ∈ R5 .

It is indeed easy to see that the equivalence class of any sequence of real numbers converging to 0 (resp. to ±∞) is infinitesimal (resp. infinite). To give more insight to the reader on the way to work with the above formalism, we shall now prove the following key property of non-standard real numbers.

Proposition 1.1. Any finite non-standard real number x ∈ * R can be uniquely decomposed as a sum x = a + where a is a usual real number of R and is infinitesimal.

Proof: The unicity of the claimed decomposition is obvious. If one would have a+ = b+η where a and b are two usual real numbers and and η two infinitesimals, one would indeed deduce that a -b = η -. But, since this quantity is both a usual real number and an infinitesimal, it must be equal to 0, which shows that one both has a = b and = η as expected.

On the other hand, let x = [(x n ) n≥0 ] be a finite non-standard real number. Let us then consider the subset B of R defined by setting B = {b ∈ R, b < x}. Due to the finiteness of x, it is easy to see that B is a bounded set of real numbers which hence has a supremum a within R. Let us then set = x -a and let us suppose that there exists a positive real number r ∈ R such that r < | |. If > 0, we would have r < x -a, i.e. a < a + r < x, in contradiction with the fact that a is the supremum of B (there would be a bigger real number a + r in B than a). On the other hand, if < 0, we would have r < a -x, hence x < a -r < a, again contradicting the fact that a is the supremum of B (a -r would be a small upper bound of B than a). Hence must be an infinitesimal, which ends our proof.

Let us now introduce some notations that will be useful in the sequel. Two non-standard real numbers x and y will first said to be infinitely close, which will be denoted by x ≈ y, if and only if x -y is infinitesimal. The previous result can therefore be restated as the fact that each finite non-standard real number is always infinitely close to a unique usual real number (which also implies that infinitesimal numbers are exactly the non-standard real numbers which are infinitely close to 0). Observe also that, among all non-standard real numbers, one can of course consider the set * Z of non-standard integers that, on top of usual integers, contains infinite ones, having absolute value greater than any n ∈ N.

We will finally end this introduction by giving (without any proof) some important model-theoretical properties of the set of non-standard real numbers (see [START_REF] Barwise | Handbook of Mathematical Logic[END_REF][START_REF] Diener | Nonstandard Analysis in Practice[END_REF][START_REF] Diener | Nonstandard Analysis in Practice[END_REF][START_REF] Diener | Analyse non standard[END_REF][START_REF] Jensen | Model Theoretical Algebra[END_REF] for more details). The first important property to know is the fact that the two totally ordered fields * R and R are elementarily equivalent, which means that the first order logical properties of R and * R (expressed in the logical theory of ordered fields) are exactly the same. This property is in fact a special case of the following more general result, called the transfer principle (see [START_REF] Cutland | Nonstandard Analysis and its Applications[END_REF] for a proof and a totally rigorous statement).

Transfer principle. Let F be a set-theoretical formula involving only usual real variables which does not have any free variable. Then F is true iff * F is true, where * F stands for the formula on non-standard real numbers obtained from F by transfer, i.e. by changing each usual standard set a involved in F by its non-standard version * a (that is to say the ≡ m -classes of the sequences of elements of a).

As one can immediately see, the transfer principle is a very strong property of non-standard real numbers since it claims basically that every usual property of standard real numbers holds for nonstandard real numbers up to replacing standard sets by their non-standard equivalents. It implies for instance that the recurrence principle can be immediately lifted to * R, up to working with * N instead of N. In the same way, the transfer principle shows that most of the classical properties (such as the existence of a non-standard integer part of any non-standard real number, of an upper bound for each bounded internal 6 non-standard subset of * R, etc.) of R still work for * R up to replacing usual standard involved sets by their non-standard equivalents.

Time Scales, Data Flows and Transfer Functions

We are now in position to introduce the bases of the framework that we will use to deal with systems in the sequel. Note that most of our formalism is fundamentally a non-standard revisiting of quite classical concepts that were for instance synthesized in Sontag's classical textbook (see [START_REF] Sontag | Mathematical Control Theory: Deterministic Finite Dimensional Systems[END_REF]) 7 . The new system properties brought by our non-standard approach will in fact mainly be seen in the last part of our paper.

Time Scales

The first key modification brought by non-standard analysis is of course related to the modelling of time. The conditions imposed on time references in Definition 2.1, ensures that the successor (resp. predecessor) of any t ∈ T -denoted by succ T (t) (resp. by pred T (t)) -can be uniquely defined. Observe also that time references are clearly closed under union (but not under intersection). Definition 2.2. Time scales -A non-empty subset T ⊂ * R + is said to be a time scale if and only if it is the non-negative part of a time reference that contains 0, i.e. iff there exists a time reference T that contains 0 (which will therefore be the minimal element of every time scale) such that T = T ∩ * R + . We shall use the term moment to denote the elements of a time scale. One important class of time scales consists of regular time scales, i.e. of the type T τ = * N τ where τ ∈ * R * + is a positive non-standard real number, called the step of its corresponding regular time scale. Such a time scale can be seen as a discrete series of clock ticks occurring at each time n•τ , where n ∈ * N describes all non-standard finite and infinite integers (see Figure 2).

The next definition introduces now the notion of continuous time scales that will allow us to mimic naturally -and discretely -continuous time in a non-standard framework as we will see below.

Definition 2.3. Continuous time scales -A time scale T is said to be continuous if for any non-negative standard real number r ∈ R + , there exists a moment t ∈ T such that t ≈ r.

We are now in position to show that we can recover usual continuous time by considering regular time scales with infinitesimal steps. This result is key since it means that we can model discretely continuous time in a non-standard framework, which is one of the core ideas on which this paper relies.

Proposition 2.1. A regular time scale with an infinitesimal step is continuous.

Proof: Let T be a regular time scale with an infinitesimal step τ ≈ 0 and let r ∈ R + be any nonnegative standard real. The non-standard version of Archimedes' property (use either the formalism of Section 1.2, either the transfer principle or look to Chapter A.6 of [START_REF] Barwise | Handbook of Mathematical Logic[END_REF]) implies that there exists always a non-standard integer N ∈ * N (here necessarily infinite) such that N < r/τ ≤ N + 1. We deduce therefore that N τ < r ≤ (N + 1)τ and 0 < r -N τ ≤ τ ≈ 0. Hence t ≈ r with t = N τ ∈ T as requested.

We will also use in the sequel the notion of time scale refinement that we finally quickly recall.

Dataflows

This new sub-section introduces the notion of dataflow, taken here again in a non-standard meaning, which will be another cornerstone of our system modelling approach due to the fact that we will consider here systems as dataflow transformers (and not as only data transformers as it is classically done). Definition 2.5. Dataflow -Let T be a time scale. A T-dataflow over an alphabet A is then just a mapping x : T → A. The set of all T-dataflows over A will be denoted by A T .

The next definition intends to capture the fact that a dataflow can be observed at any positive time although its value only changes at discrete moments specified by its underlying time scale. Definition 2.6. Snapshots -Let x be a T-dataflow over A and let t ∈ * R + be a positive non-standard real number. The snapshot of x at time t is then the element of A, denoted by x :: t, which is defined by:

x :: t = x(t ), where t = min{u ∈ T | t ≤ u} .
We can now introduce the following notion of product of dataflows that will be quite useful when we will consider multi-entry systems in the next section. The reader will easily check that the product of dataflows defined in this manner is an associative product. Definition 2.7. Let x ∈ A T 1 1 and y ∈ A T 2 2 be two dataflows and let T be the time scale T = T 1 ∪ T 2 resulting of the union of the two time scales of these two dataflows. The product of x and y, denoted by x ⊗ y, is then the T-dataflow over A 1 × A 2 defined, for any t ∈ T + , by setting:

(x ⊗ y)(t) def = (x :: t, y :: t) .
Let us finally introduce the following notion that we will use in the next section for discussing equivalence results between different systems definitions. Definition 2.8. Observational equivalence -Two dataflows n-uples x = (x i ) i=1...n and y = (y j ) j=1...n are said to be observationally equivalent -which will be denoted by x y -iff one has:

(x 1 ⊗ . . . ⊗ x n ) :: t = (y 1 ⊗ . . . ⊗ y n ) :: t for all t ∈ * R + .
Example 2.1. Let T τ be a regular time scale with step τ and let f be a T τ -dataflow over an alphabet A. Consider the regular time scale T τ /2 of step τ /2. It is then clear that the T τ /2 -dataflow f which repeats every value in f twice, is observationally equivalent to f .

Transfer Functions

Observable behavior of a system is described by its associated transfer function which can be seen as a real-time dataflow transformer satisfying the causality condition as given in the next definition. Note however that causality as defined below corresponds only to strong causality in a classical framework (see [START_REF] Sontag | Mathematical Control Theory: Deterministic Finite Dimensional Systems[END_REF]). In the nonstandard analysis framework we took here, the usual concepts of causality and strong causality 8 are indeed collapsing now into the unique concept of (strong) causality. This is due to the fact that strong and non strong causality differ in a classical framework since systems can work there in null time, i.e. spend no time to pass from their input to their output. In a nonstandard framework, no system can work in zero time: there will be always at least an infinitesimal moment (which may model the zero time behaviors of usual systems) between an input and the corresponding output of a system, which as a consequence leads us to define only the following (strong) causality property as the unique type of causality that we will consider in our framework. Definition 2.9. Transfer functions -Let In and Out be two alphabets and T i and T o be two time scales. Then a function F : In T i → Out T o is said to be a transfer function iff it is causal, i.e. iff one has:

∀ t ∈ * R + , ∀ x, y ∈ In T i , ∀ 0 ≤ t < t, x :: t = y :: t =⇒ F(x) :: t = F(y) :: t .
Observe that if F 1 and F 2 are two transfer functions such that the set of output dataflows of F 1 coincides with the set of input dataflows of F 2 , then the composition F 1 • F 2 is also a transfer function. More generally, transfer functions are "composed" through interfaces as defined in the next definition. Note that we will in fact speak in full generality of transfer function integration -rather than composition -due to the fact that our "composition" is a mixture between parallel and sequential compositions which models typically the possibility of redirecting dataflows from an output to an input of the two involved transfer functions. Integration of transfer functions is in fact only the transfer function counterpart of the system integration operator that plays a key role in systems modelling (cf. Section 3).

E E F In T i Out T o π i π o F 1 F 2 d d d B x 1 r j x 2 A F 1 (x 1 ) i F 2 (x 2 )
Figure 3. Two transfer functions F 1 and F 2 integration through an interface (In

T i , Out T o , π i , π o ).
Definition 2.10. Interfaces and integration of transfer functions -Let In 1,2 and Out 1,2 be four alphabets which are all products of other alphabets9 with two distinguished elements 1,2 in Out 1,2 , let

T i 1,2
and T o 1,2 be four time scales and let finally F 1 : In

T i 1 1 → Out T o 1 1 and F 2 : In T i 2 2 → Out T o 2
2 be two transfer functions. An interface for F 1 and F 2 is then a quadruple Π = (In T i , Out T o , π i , π o ) where:

• In and Out are two alphabets which are products of other alphabets in such a way that the alphabets In1 and In2 (resp. the alphabet Out) are products (resp. is a product) of some of the alphabets involved in the alphabet products defining In, Out 1 and Out 2 (resp. Out 1 and Out 2 ),

• T i and T o are any arbitrary time scales,

• π i = (π i 1 , π i 2 )
is a pair of componentwise projections10 between the following product sets:

π i 1 : In × Out 1 × Out 2 → In 1 , π i 2 : In × Out 1 × Out 2 → In 2 , • π o : Out 1 × Out 2 →
Out is a componentwise projection between the involved product sets.

The integration of F 1 and F 2 through Π is then the transfer function F :

In T i → Out T o , denoted by I Π (F 1 , F 2 )
, which is defined by setting for every x(t) ∈ In T i (see Figure 3):

F(x)(t) def = π o (F 1 (x 1 ) :: t, F 2 (x 2 ) :: t) for every t ∈ T o , (1)
where x 1 and x 2 are respectively the T i 1 and T i 2 -dataflows inductively 11 defined by setting:

• Initial conditions:

x 1 (0) = π i 1 (x :: 0, 1 , 2 ), x 2 (0) = π i 2 (x :: 0, 1 , 2 ), (2)
• Induction relations:

x 1 (t) = π i 1 (x :: t, F 1 (x 1 ) :: t, F 2 (x 2 ) :: t) for every t ∈ T i 1 -{0} , x 2 (t) = π i 2 (x :: t, F 1 (x 1 ) :: t, F 2 (x 2 ) :: t) for every t ∈ T i 2 -{0} .
(

) 3
The next result shows that Definition 2.10 is consistent which needs both to ensure the consistency of the above definition and the fact that it defines really a transfer function.

Proposition 2.2. For any transfer functions F 1 , F 2 and any interface Π as in Definition 2.10, the integration I Π (F 1 , F 2 ) of F 1 and F 2 is always a well-defined transfer function.

Proof: We will take here all notations of Definition 2.10. The reader will then first easily check that Equations ( 2) and (3) define well inductively the two dataflows x 1 and x 2 due to the fact that F 1 and F 2 are transfer functions (write x 1 and x 2 as sequences of unknown variables over In 1 and In 2 and look at the equations involving these variables given by Equations ( 2) and ( 3)). The only thing to prove now is then that the integration of two transfer functions is itself a transfer function. Going back to the defining Equation (1) and using the fact that F 1 and F 2 are causal functions, this last property results then immediately of the fact that for every t ∈ R + , one has x 1 (t) = x 1 (t) and x 2 (t) = x 2 (t) as soon as x(t ) = x (t ) for every t < t (with obvious notations), as one may easily check.

As the reader may easily check, the notions of interfaces and integration can be extended without difficulties to any finite number of transfer functions. This generalization will in particular be used in the next example that we will now explore in order to illustrate all previous concepts. Example 2.2. Water Tank -We shall revisit in our nonstandard framework a well known example of the hybrid systems and control theory literature. Let us hence fix first some regular continuous time scale T with infinitesimal time step ε that will be used to define all the transfer functions of our example.

We shall therefore consider the system consisting of a water tank where water arrives at a variable rate w i (t) ≥ 0 (with t ∈ T) through one single pipe. The water leaves through another (output) pipe at rate w o (t) (with t ∈ T) controlled by a valve (see Figure 4-a) whose position will be given by v(t) ∈ [0, 1] (with t ∈ T), 0 and 1 modelling respectively here the fact that the valve is closed or open. The initial position at time t = 0 of the valve is equal to some constant v(0) = V 0 . The maximal throughput capacity of the output pipe is C, thus its actual throughput at each moment t ∈ T is C v(t). The valve is controlled by a sensor measuring the level l(t) of water in the tank, which aims at keeping this level in a given interval [L 1 , L 2 ] (the initial water tank level L 0 belongs therefore to this interval). For simplicity, we assume that there is always enough water in the tank to saturate the output pipe and that the incoming flow does not exceed the output pipe's capacity, i.e. that one has always max(w The transfer function of the complete water tank system has the input space In = [0, C] (incoming flow rate) and the output space Out = [0, C] × [L 1 , L 2 ] (output flow rate and current water level in the tank). It can be modelled as an integration of the three following transfer functions (see Figure 4-b):

i (t), t ∈ T) ≤ C. L 1 L 2 ' c sensor h h h ¤ ¤ ¤ E w i E w o Valve Sensor Tank E w i E w o ' E l E v ' dv (a) (b)
1. The tank transfer function, T , taking on input the current values of the incoming water flow w i (t)

and the position v(t) of the valve and sending on its output the corresponding output water flow w o (t) and water level l(t) according to the following equations:

w o (0) = C V 0 , w o (t + ) = C v(t) for every t ∈ T * , l(0) = L 0 , l(t + ) = l(t) + (w i (t) -w o (t)) for every t ∈ T * .
The input and output spaces of T are then

In T = [0, C] × [0, 1] and Out T = [0, C] × [L 1 , L 2 ].
2. The sensor transfer function, S, taking on input the water level l(t) and sending on its output a valve position adjustment dv(t) defined from some given equation as follows 12 :

dv(0) = 0, dv(t + ) = sign l(t) - L 1 + L 2 2 for every t ∈ T * .
The input and output spaces of S are then In S = [L 1 , L 2 ] and Out S = {-, 0, }.

3. The valve transfer function, V , taking on input the adjustment dv(t) and providing on its output v(0) = V 0 at time t = 0 and the value v(t) given by the following formula:

v(t + ) = v(t) + dv(t) if v(t) + dv(t) ∈ [0, 1] , v(t) if (v(t) = 0 ∧ dv(t) = -) or (v(t) = 1 ∧ dv(t) = ) ,
for t ∈ T * . The input and output spaces of V are then In V = {-, 0, } and Out V = [0, 1].

We will not enter at this point in the consistency of our model, i.e. on the fact that all the limits of the input and output spaces of our transfer functions are well defined 13 since we only wanted to illustrate the transfer function integration mechanism. As one can see on Figure 4-b, the transfer function of the full tank water system is indeed given by the integration of the transfer functions T , S and V through the interface Π = (In T , Out T , π i , π o ) with componentwise projections

π i : In × Out T × Out S × Out V -→ In T × In S × In V (w i ; w o , l; dv; v) -→ (w i , v; l; dv) and π o : Out T × Out S × Out V -→ Out (w o , l; dv; v) -→ (w o , l) .

Systems

We shall now revisit classical system theory in the framework of non standard analysis. This will lead us to redefine the notion of system and the associated transfer function and integration operator concepts.

Notation 3.1. For any alphabet A, we will denote in the sequel by A the completion of A by a blank symbol , that is to say

A def = A ∪ { }.

Definition

We are now in position to introduce our "mechanical" system model in the line of the usual Turing machine mechanism which is essentially enhanced by adding to it input/output mechanisms and temporisation (though input, output and internal time scales) within a non-standard analysis approach which allows to work with continuous values14 .

Definition 3.1. Systems -A system S is defined as the union of the following elements (see Figure 5):

• an input/output mechanism that consists respectively of:

-an input channel x capable of receiving -only at moments that belong to a given time scale T i called the input time scale -elements that belong to a given alphabet In, called the input domain of S (which will also be denoted by In(S)),

-an output channel y capable of emitting -only at moments that belong to a given time scale T o called the output time scale -elements that belong to a given alphabet Out, called the output domain of S (which will also be denoted by Out(S)), each of these channels is represented by a single memory cell containing the last received value and overwritten at each moment on the corresponding time scale;

• an internal memory composed of -a memory tape indexed by the set * N of non-standard positive integers containing symbols from a given alphabet M (also denoted by M (S)) called the memory domain of S, with a size being bounded by a (possibly infinite) non-standard integer N ∈ * N, -a read/write head current position indicator p ∈ * N (with p < N );

• a control mechanism defined by -an internal time scale T s , -an internal state set which is just an arbitrary standard finite set Q (also denoted State(S)),

-a transition function δ : Q × M × In → Q × M × {-1, 0, +1} ×
Out, that allows to update at each moment on the internal time scale the system's current state, the element of the internal memory at the current head position, the head position itself and the system's output (the output value computed by δ can be blank when t ∈ T s \ T o , i.e. at the moments on the internal time scale that do not belong to the output time scale);

• a set of initial values to which the concerned above components are assigned at their respectively associated initial moments.

E E

x

T i
In

' E m ∈M N c T y T o Out $ c q ∈Q k Q T T s δ Figure 5. Graphical representation of a system.
Let us now consider the dynamics of a system in this model. Observe first that the internal configuration of a system is described at each moment of time by the system's state, the contents of its memory tape, and the position of its read/write head. The following definition introduces this idea formally. Definition 3.2. Instantaneous description of a system -Let S be a system. An instantaneous description of S at a given moment t ∈ T s on its internal time scale is a quadruple d = (q, m, p, ỹ) of Q × M N × * N × Out, where q, m, p, and ỹ represent respectively the internal state, the full contents of the memory tape, the position of the read/write head and the symbol to be emitted on the output of S at the moment t (equal to blank if it does not exist).

We can now introduce the dynamics of a system (in the meaning of Definition 3.1) defined as a coherent sequence of instantaneous descriptions indexed by moments on its internal time scale. Definition 3.3. Execution of a system -Let S be a system. An execution of S for a given input flow x is then the T s -dataflow d = (q(t), m(t), p(t), ỹ(t)) t∈T s over Q × M N × * N × Out which is defined inductively (in the non-standard meaning) as follows:

• the initial value of d at time 0, i.e. the 4-uple (q(0), m(0), p(0), ỹ(0)), is equal to the initial internal state, memory content, read/write head position and output value of S,

• let now t ∈ T s and suppose that the 4-uple d(t) = (q(t), m(t), p(t), ỹ(t)) is defined; we can then define d(t ) for t = succ T s (t) by setting:

d(t ) = (q(t ), m(t ), p(t ), ỹ(t )) def = (q , m , p(t) + ∆, ỹ ), (4)
where one has first (q , m , ∆, ỹ ) = δ(q(t), m(t) p(t) , x :: t), with m(t) p(t) and x :: t respectively being the values of the memory tape cell pointed by the read/write head and the snapshot of the input flow x at moment t, and secondly m" j equal to m(t) j for j = p(t) and to m j for j = p(t).

Taking all the notations introduced in the previous definition 3.3, the output flow y ∈ Out T o of a system S which is generated by a given input flow x ∈ In T i can now be defined by setting:

∀t ∈ T o , y(t) def = ỹ :: t . Note 3.2.
As at some moments on the internal time scale -those that do not belong to T i -no new data is available on the input channel, one applies then the transition function δ to the snapshot of the input flow, i.e. the latest received value.

In [START_REF] Bliudze | Modelling of Complex Systems I -A Functional Approach: Time, Data and Systems[END_REF], we showed that our notion of system can be naturally generalized to include systems with multiple input/output channels and memory tapes which are called multi-systems. We will need to work with such multi-systems in the next example that shows how a classical physical system can be modelled by a system in our meaning. Note however that this generalization does not increase the expressive power of our model as stated by Theorem 3.4 in the next sub-section.

Example 3.1. Simple pendulum -Consider a pendulum consisting of a point mass m hanging on a rigid string of negligible mass and of length L (see Figure 6-a) 15 . The motion of such a pendulum is described by the usual standard differential equation

θ = - g L sin θ , ( 5
)
where θ is the angle formed by the string and the y axis. By integrating (5) and multiplying by mL 2 , we obtain then immediately the following energy preservation equation:

1 2 m(L θ) 2 + mgL(1 -cos θ) = C , (6)
where the first and the second summand in the left hand side represent respectively the kinetic, E K , and the potential, E P , energies of the system. The following relation can then easily be obtained from [START_REF] Bliudze | A Framework for Studying Complex Industrial Systems: An Example Based on the UMTS Infrastructure[END_REF]: A system modelling such a pendulum is shown in Figure 6-b. It has two tapes K and P , each of them containing a (non-standard) finite number of infinitesimal quanta of energy. The two tapes together always contain the same infinitely great number N ∈ * N of energy quanta (in such a way that the total energy contained in the two tapes is a constant equal to C). The system's behaviour consists then essentially in taking at each moment of time -on a given continuous time scale T -the number of quanta defined by [START_REF] Bliudze | Towards a Functional Formalism for Modelling Complex Industrial Systems, Com-PlexUs[END_REF] (which can be simulated -using a finer time scale than T -within our system model due to the results of Section 4.1) from one tape and putting it on the other one, until the working tape is empty, at which moment the two tapes exchange their roles.

d E K dt = d E P dt = 2 E K E P L 2g - E P mL . ( 7
) E x T y L ¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡¡ c g t θ ••• P ••••• K ↑ ¥ § T c δ E E E P E K ¤ ¥ ¢ £ E E output (a) (b)

Equivalence of Systems

According to Definition 3.3, every system S with input flows in In T i and output flows in Out T o can be equipped with its transfer function F(S) :

In T i → Out T o ,
which is the mapping that associates to any input flow x ∈ In T i the output flow y ∈ Out T o generated by S. Conversely we shall call any transfer function that can be associated to a system implementable.

Definition 3.4. Implementable transfer functions -We say that a transfer function F is implementable if there exists a system S such that F = F(S).

The notion of the transfer function associated with a system allows us to introduce the following key equivalence relation for systems in our meaning. Definition 3.5. Weak system equivalence -Two systems S 1 and S 2 are said to be weakly equivalent if and only if the following characterizing properties hold simultaneously:

• In(S 1 ) = In(S 2 ) and Out(S 1 ) = Out(S 2 ),

• for any two input flows x 1 and x 2 over In(S 1 ), one has:

(x 1 x 2 ) =⇒ (F S 1 (x 1 ) F S 2 (x 2 ))
where F S 1 (x 1 ) and F S 2 (x 2 ) stand for the corresponding output flows provided respectively by the systems S 1 and S 2 .

Note 3.3. The notion of weak equivalence can be obviously lifted to implementable transfer functions and will be used in this meaning in the sequel (cf. Theorem 3.5).

We are now in position to give the following result which states that the computational power of systems do not increase if we allow several memory tapes for a system. Theorem 3.4. Each multi-tape system is weakly equivalent to some mono-tape system.

Proof: The complete proof is presented in [START_REF] Bliudze | Modelling of Complex Systems I -A Functional Approach: Time, Data and Systems[END_REF]. Here we only present the main idea. We proceed in a manner similar to that used by Hopcroft and Ullman in [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF] for the proof of the analog result for multitape Turing machines. The main additional difficulty of the proof resides in the constraint imposed by the input and output time scales. This is resolved by considering the internal time scale refining that of the original multi-system by dividing each step into A × N equal parts, where N is the upper bound (that can be an infinite integer of * N) of the memory size and A is a suitable (finite) integer constant (several sweeps of the memory tape can be required to simulate one step of the multi-system).

The following theorem is also key since it is the implementable transfer functions trace of the fact that systems are closed under an operator -called integration -which is underlying in its proof. Theorem 3.5. Up to weak equivalence, implementable transfer functions are closed under integration. Proof: Let F 1 : In

T i 1 1 → Out T o 1 1 and F 2 : In T i 2 2 → Out T o 2
2 be two implementable transfer functions associated with the systems S 1 and S 2 and let Π = (In T i , Out T o , π i , π o ) be an interface for F 1 and F 2 . Consider then the multi-system S defined by the following elements:

• its input and output channels are respectively equal to In T i and Out T o ,

• its internal memory consist in four distinct memory tapes: the two first tapes have respectively the same characteristics than the two memory tapes of S 1 and S 2 (that they simulate) when each of the two other tapes has only one single cell respectively with symbol in In 1 × In 2 and Out 1 × Out 2 ,

• its control mechanism works in an internal time refining sufficiently the internal times of S 1 and S 2 to allow the below simulations, has an internal state set equal to the product of the state sets of S 1 and S 2 by the special states product set {in 0 , in 1 , in 2 } × {out 0 , out 1 , out 2 } and consists in simulating in parallel the behavior of S 1 and S 2 (the special states being then equal to (in 0 , out 0 )) when storing or extracting π i (x :: t, F 1 (x 1 ) :: t, F 2 (x 2 ) :: t) and π o (F 1 (x 1 ) :: t, F 2 (x 2 ) :: t) respectively on the third and fourth memory tapes when necessary (the special states being then respectively equal to (in 1,2 , out 0 ) and (in 0 , out 1,2 ) before going back to their nominal value (in 0 , out 0 )).

It is then easy to see that the transfer function of system S is observationally equivalent to the integration of the transfer functions of S 1 and S 2 , as requested.

Note 3.6. The notions of interface and integration can be generalised to multi-systems. It is clear that the above theorem also holds for this generalisation.

A Notion of Computability on Reals

One of the main difference between the non standard approach and the classical approach reflects in the fact that the computable functions that we can define in our framework are much richer that in the usual classical frameworks for computability on real numbers (see [START_REF] Bournez | A Survey on Continuous Time Computations[END_REF]).

Computable Real Functions

We shall now introduce a special case of implementable transfer functions, that is to say the class of computable functions on reals. To this aim, fix now ε ∈ * R + and observe first that any non-standard real number can be approximated by a flow of quanta up to ε. Given a non-standard time scale T, we can indeed encode each x ∈ * R as a flow x ∈ {+, -, 1, } T defined as follows:

• x begins by a sign equal to '+' (when x ≥ 0) or '-' (when x < 0),

• x is followed by a contiguous sequence of N times the symbol 1 where N is the unique (due to Archimedes's principle already used in the proof of Proposition 2.1) non-standard integer of * N such that N ε ≤ |x| < (N + 1) ε,

• all the remaining symbols of x are equal to .

Let E(±, 1, ) denote the image of all non-standard real numbers through this encoding, i.e. the set of all T-dataflows on {+, -, 1, } that consist of a {+, -} symbol, followed by an arbitrary number of 1's and finishing by an infinite sequence of symbols. Any transfer function F : {+, -, 1, } T → E(±, 1, ) induces then a function F ε : * R → * R, as a composition of the above encoding, the transfer function F and the corresponding decoding. Notice that the previous encoding is injective on R when ε ≈ 0. In the following, we shall therefore fix ε = 1/E where E ∈ * N is some infinite positive integer.

Definition 4.1. Computable functions -A function f : R → R is computable if there exists an implementable transfer function F : {+, -, 1} T → E(±, 1, ), such that one has f (x) ≈ F ε (x) for every x ∈ R. Moreover a computable function f is said to be computable with bounded error if there exists an error bound B ∈ * N with Bε ≈ 0 such that the following property holds for any N ∈ * Z:

N ε is finite =⇒ |F ε (N ε) - * f (N ε)| < Bε , (8)
where * f stands for the non-standard version of f16 .

Note 4.1. Observe that sequences of real numbers are functions with support N. Hence computable sequences constitute a special case of computable functions.

The following result shows now that non-standard modelling gives raise to the same kind of computable functions than in most of the usual real-oriented computability frameworks (see [START_REF] Bournez | A Survey on Continuous Time Computations[END_REF]).

Theorem 4.2. The set of bounded error computable functions is closed under addition, multiplication, and integration. Moreover addition and multiplication preserves the order of the error bound.

Proof: 1. Closure under addition and preservation of the error bound order results immediately from the construction (let to the reader) of a two memory tapes system that computes the sum (N + M ) ε of two non-standard real numbers N ε and M ε with N, M ∈ * Z (each of them being initially put on one of the system's tapes according to the above encoding).

2. Closure under multiplication will result immediately of the construction of a two memory tapes system that computes up to ε the product (N ε) × (M ε) of two non-standard positive real numbers N ε and M ε with N, M ∈ * N. Using the Euclidian division algorithm (that can be easily simulated by a system), one can compute two unique non-standard integers Q and R such that M N = QE + R and 0 ≤ R < E (where E is the infinite non-standard integer such that ε = 1/E). Since one clearly has

(M/E) (N/E) = (Q/E) + (R/E 2 ) =⇒ Q ε ≤ M N ε 2 < Q ε + ε ,
it happened that the positive non-standard real number Qε is hence a relevant approximation -up to εof the product (N ε) × (M ε) that can be system-computed as expected. Proof of the error bound order preservation is straightforward.

3. Let [a, b] ⊂ R be a usual interval and let f : R → R be a continuous standard function computable with some error bound B ∈ * N. For any infinite non-standard integer N ∈ * N, we then have

b a f (x)dx ≈ 1 N N i=0 * f a + i b -a N .
Taking N = E/B and applying Euclidean division algorithm as above, it is easy to verify that the right-hand side of this equation can be implemented, given an implementation of the integration of f . The two next results are now concentrating the main differences between our non-standard computability model and the usual real-oriented computability models. Theorem 4.3. Let f : R → R be a uniformly continuous differentiable function, computable with error bound B ∈ * N. Then its derivative f is also computable with bounded error.

Proof: Let F be an implementable transfer function such that f (x) ≈ F ε (x) for every x ∈ R (with associated error bound B). Recall first that the derivative f (x) can be approximated for any x ∈ R by the formula f (x) ≈ ( * f (x + δ) - * f (x)) /δ where δ stands for any infinitesimal. Let us now consider a real number x ∈ R and let M ∈ * Z be the unique infinite non-standard integer such that 0 ≤ x-M ε < ε. Then one has for any non-standard positive integer N ∈ * N such that δ = N ε remains infinitesimal:

* f (M ε + N ε) - * f (M ε) δ - F ε (M ε + N ε) -F ε (M ε) δ < 2 Bε/δ . ( 9
)
Consider N = √ EB . We then have both δ = N ε ≈ 0 and (Bε)/δ = B/N ≈ √ Bε ≈ 0. Therefore f (x) can be always approximated by (E/N ) F ε (x + N ε) -F ε (x) . Using this last formula in connection with Equation 9, it is now immediate to show that f is computable with bounded error.

Arguing as in the third point of Theorem 4.2, we can state the following remarkable computability result which is totally specific to the non-standard modelling we used here. Theorem 4.4. Let (a n ) n∈N be a sequence of real numbers computable with bounded error and such that the function f (x) = n∈N a n x n is analytical. Then f is computable with bounded error.

Dynamical and Hamiltonian Systems

A dynamical system x : t ∈ R -→ x(t) ∈ R n is defined by a differential equation of the type:

x(t 0 ) = x 0 ∈ R n and ẋ(t) = f (t, x(t)) for every t ∈ R . ( 10
) If f : [0, 1] × R n → R n
is a continuous bounded function, then Equation 10 admits a unique solution called the trajectory of the corresponding dynamical system (see [START_REF] Severance | System Modeling and Simulation: An Introduction[END_REF]). The following theorem extends then the results of the previous sub-section to computability of dynamical systems.

Theorem 4.5. Let S be a dynamical system defined by a bounded continuous function f . If f is computable with bounded error, then the unique trajectory of S is also computable with bounded error.

Proof: The proof of this theorem is based on the non-standard proof of Peano theorem (see [START_REF] Bliudze | A Framework for Studying Complex Industrial Systems: An Example Based on the UMTS Infrastructure[END_REF]Secn. A.4.2] or [START_REF] Cutland | Nonstandard Analysis and its Applications[END_REF]) and techniques similar to those applied in the previous section. Let N ∈ * N be a nonstandard infinite integer. The key point is to express the solution of a dynamical system using the formalism of non-standard analysis. It appears that Equation (10) admits a solution X : [0, 1] → * R defined inductively (in the non-standard meaning) by setting for every non-standard integer 0 ≤ k ≤ N :

X(k/N ) = x 0 + 1 N k-1 i=0 f (i/N, X(i/N )) . ( 11
)
Using Equation [START_REF] Bournez | A Survey on Continuous Time Computations[END_REF], we can build a system that computes X. This system takes analog encodings of real numbers of [0, 1] on its input that are encoded using the infinitesimal ε = 1/N and is designed in such a way that when it reads the k th -1, it stores the value X(k/N ) on its memory tape. To achieve this, the system simply adds to the non-standard integer value representing X(k -1/N ) already stored on its memory tape the non-standard integer f ((k -1)/N, X(k -1/N )) . Since f is computable, this algorithm is easy to implement using techniques already used in the previous sub-section.

An important special case of dynamical systems is constituted by the closed Hamiltonian systems, defined by a system of differential equations of the form: p(t 0 ) = p 0 , ṗ = -∂H ∂q q(t 0 ) = q 0 , q = ∂H ∂p , [START_REF] Cha | Fundamentals of Modeling and Analyzing Engineering Systems[END_REF] where H(p, q) is an Hamiltonian, modelling the total energy of the system. As an immediate consequence of the previous result, we get the following corollary which shows that most of the classical physical systems can be modelled by systems in our meaning. Note also that this result shows the key difference between our model and the classical ones since one can prove that solutions of Hamiltonian systems cannot be algorithmically computed in a usual computable framework (see [START_REF] Costa | Undecidability and incompleteness in classical mechanics[END_REF][START_REF] Pour-El | A computable ordinary differential equation which possesses no computable solution[END_REF][START_REF] Richardson | Some undecidable problems involving elementary functions of a real variable[END_REF]).

Corollary 4.1. Let S be a closed Hamiltonian system such that both ∂H/∂p and ∂H/∂q are bounded continuous functions that are computable with bounded error. Then the unique trajectory of S is also computable with bounded error.

The discussion above allows us to reconsider the simple pendulum example (Example 3.1) by decomposing it into simpler components. with H(ϕ, θ) = ϕ 2 2 -g L cos θ. Thus, another model of such a pendulum can be obtained by considering a system with two tapes storing respectively the values of the angle θ and angular speed ϕ. This system will use two "sub-systems" computing respectively the Hamiltonian H(θ, ϕ) and the trajectories that it defines, these components consisting themselves of other "sub-systems" (the system computing H(θ, ϕ) use for instance a sub-system to compute the cosine function).

Conclusion

In this paper, we presented a new family of timed systems encompassing classical approaches based on continuous and discrete time models. The key idea of our approach is to use a non-standard framework where continuous time is modelled discretely through continuous time scales. This change of modelling paradigm, joined with the fact that non-standard analysis allows to refine time scales without difficulties, allowed us to enlarge the perimeter of usual real-oriented computability frameworks. It indeed happens that a natural class of computable real functions in our formalism is closed under operations such as derivation and integration (which is usually not the case) and contains interesting functions such as most of the classical analytical functions. As a special case, trajectories of Hamiltonian and dynamical systems are computable under assumption of computability of their parameters. This shows that a large class of physical systems can be modelled in this framework. Defining a system as a natural extension of a Turing machine mechanism, lead us therefore to a formal definition of systems, where both software and physical systems can be modelled and described in a unified way. To the best of our knowledge, few models have so far been developed that combine all the above mentioned characteristics. We believe therefore that our model provides an elegant and powerful mathematical framework for modelling complex systems and hope that it will give new intuitions for further researches.

Figure 1 .

 1 Figure 1. Graphical representation of the set * R of non-standard real numbers.

Definition 2 . 1 .

 21 Time references -A non-empty subset T ⊂ * R is called a time reference if and only if, for any t ∈ * R, the two sets T t-= {t ∈ T | t < t} and T t+ = {t ∈ T | t > t} have respectively always a maximum and a minimum.

Figure 2 .

 2 Figure 2. Graphical representation of a (non-standard) regular time scale.

Definition 2 . 4 .

 24 A time scale T refines another time scale T -denoted by T T -iff T ⊆ T.

Figure 4 .

 4 Figure 4. The Water Tank (a) and an associated simplified systemic model (b).

Figure 6 .

 6 Figure 6. Simple pendulum: mechanical (a) and systemic (b) representations.

Example 4 . 1 .

 41 Simple pendulum revisited -Let us first recall that the motion of the simple pendulum as described in Example 3.1 is modelled by the differential equation[START_REF] Barwise | Handbook of Mathematical Logic[END_REF]. Denoting ϕ = θ the angular speed of the pendulum, this equation defines the following Hamiltonian system: ϕ(0) = 0, φ = -∂H ∂θ and θ(0) = θ 0 , θ = ∂H ∂ϕ

Note that the concept of "complex system" has presently two main meanings supported by two quite different communities. First, in the computer science sphere, it now refers more or less commonly to a type of system whose behavior can be obtained by a set of general rules that do not apply to any of his components (see for instance[START_REF] Nicolis | Foundations of Complex Systems[END_REF] for an introduction to the topic). This point of view leads in particular to difficult behavioral questions such as the problem of combining the behavior of different components to achieve the global behavior of a system in a given algebraic or logical framework (which is typically not addressed in our paper). Secondly, in systems engineering (see[START_REF] Kossiakoff | Systems Engineering -Principles and practice[END_REF][START_REF] Sage | Introduction to systems engineering[END_REF][START_REF] Turner | Introduction to industrial systems and systems engineering[END_REF] for good introductory textbooks to this quite old subject which can be traced back to the early 50's), which is rather the academic and technical discipline to which we are naturally connected in this paper, complex systems refer to heterogeneous (i.e. mixing hardware, software and humanware) technical systems obtained through industrial design and integration processes. In this other direction, the key questions to solve are rather of architectural matter, that is to say how to design the more efficiently possible a system through an usually top-down approach (which is the systemic analysis point of view underlying our own approach). Our paper should therefore only be seen as a modest attempt to give sound mathematical bases to this last systems engineering tradition.

In other words, m is a measure that separates between each subset of N and its complement, one and only one of these two sets being always of measure 1, when the other is then of measure 0.

An element of * R which is not infinite is called finite.

A subset * A of * R is said to be internal if and only if there exist a sequence (A n ) n≥0 of usual subsets of R such that x ∈ * A iff x = [(an) n≥0 ] with an ∈ An for every n ≥ 0.

Many authors -such as typicallyRabinovitch ([36]) who also re-visited the same concepts when introducing real-time aspects in finite automata theory -are working exactly in the same way.

Recall that a usual transfer function x(t) -→ F (x(t); t) is causal (resp. strongly causal) if and only if for every t ∈ R, one has ∀ t ≤ t, (resp. t < t), x(t ) = y(t ) =⇒ F (x(t); t) = F (y(t); t). A strongly causal transfer function is of course always causal, but the converse does not hold.

In other words, all these alphabets are therefore equal to some product A 1 × . . . A n of other alphabets (A i ) i=1...n .

A componentwise projection is any surjective mapping π from a product set A 1 × • • • × A n onto one of its "partial-product" sets Ai 1 × • • • × Ai k such that one has π(a1, . . . , an) = (ai 1 , . . . , ai k ) for every n-uple (a1, . . . , an) ∈ A1 × • • • × An.

Where sign denotes the function from R into {-1, 0, 1} defined by setting sign (0) = 0, sign (x) = 1 for every x > 0 and sign (x) = -1 for every x < 0.

The only thing to check is in fact that one always has l(t) ∈ [L1, L2] which can be proved by supposing that the property is not respected and considering the first moment where one of the L 1 or L 2 limit is broken in order to get a contradiction.

Even if our system mechanism can be seen as an extension of the usual Turing machine mechanism, it should not considered as a full generalization. In the classical framework, S. Akl (see for instance[START_REF] Akl | Three counterexamples to dispel the myth of the universal computer[END_REF]) showed indeed that standard physical real time destroys universality, a key classical property of Turing machines. This last result shows therefore that it is not totally obvious to see whether our own system formalism preserves universality, which is an important problem that we will hence let open (the most probable result in this way being however probably negative).

Other interesting examples of non-standard revisits of classical physical problems can be found in[START_REF] Delfini | The Vibrating String[END_REF][START_REF] Diener | Nonstandard Analysis in Practice[END_REF][START_REF] Diener | Ducks and rivers: three existence results[END_REF][START_REF] Troesch | Analyse non standard et équations de Van der Pol. II. Perturbations singulières et analyse non standard[END_REF].

I.e. the function * f defined by setting * f ([(xn) n≥0 ]) = [(f (xn)) n≥0 ], going back to the formalism of Section 1.2.

Acknowledgements

The authors would like to thank the anonymous referees for many valuable remarks that helped to seriously improve the first version of the present paper.


Abdelkrim Doufene
email: doufene@mit.edu

Daniel Krob

Pareto Optimality and Nash Equilibrium for Building Stable Systems

Keywords: Architectural equilibrium, Nash equilibrium, Stable systems. I

This paper introduces a design approach based on system analysis and game theory for the identification of architectural equilibrium which guarantees the stability of the system being designed and its environment after the integration. We introduce multi-objective optimization and game theory, and their links with systems engineering through mathematical models. While Pareto optimality is used to select best architectures and to support independent decisions, Nash equilibrium is used to find out architectural equilibrium and to support interdependent decisions. This approach was illustrated previously in a case study.

INTRODUCTION

The integration of a new system in an environment can disrupt the stability of this environment and trigger adverse or unexpected events, which in turn can affect the success of this integration. This integration becomes more complex due to the complexity of the system of interest (SOI) and its environment.

To address this problem, we propose in this paper a design approach based on system analysis and game theory for the identification of architectural equilibrium which guarantees the stability of the SOI and its environment after the integration. We have demonstrated this assertion using a practical example related to electric vehicles [START_REF] Doufene | Sharing the Total Cost of Ownership of Electric Vehicles: A Study on the Application of Game Theory[END_REF] [START_REF] Abdelkrim | Architecture des systèmes complexes et Optimisation[END_REF]. We rely on a system analysis to understanding the system environment and the stakeholders involved during the SOI`s life cycle. The objective is to find global balances between external systems (stakeholders) that would meet their needs (would satisfy their strategies), taking into account feasibility constraints (economic, technological, regulatory, societal, etc.) This balance (equilibrium) guarantees a better integration of the SOI and the stability of its environment. In order to find this equilibrium, we create a game model as defined in game theory. Solving this game and finding equilibrium allow to anticipate changes in an uncertain environment (departure or arrival of a stakeholder, new or changing needs or constraints, etc.)

A game as defined in game theory is a mathematical function which matches for each possible combination of strategies played by N players, an outcome of the game. This outcome is often represented -especially in numerical examples -by the gain of each player [START_REF] Guerrien | La Théorie des jeux, Livre aux éditions Economica, Collection "poches[END_REF].

II. BACKGROUND

Games could be used to solve many multi-objective optimization (MOO) problems. MOO in the context of engineering and design of complex systems is very useful to support tradeoff analysis and decision making. It allows considering multidisciplinary objectives such as performance, cost, schedule and risk (cf. Maier and Rechtin, 2000 [4]). A quick overview of MOO and the most popular methods are presented in [4].

A MOO problem can be formalized mathematically as follows [5]:

We look at Minimizing F(x)=[F 1 (x), F 2 (x)] T while g j and h i
where k is the number of objective functions m is the number of inequality constraints e is the number of equality constraints x E n is the vector of design variables, where n is the number of independent variables x i F(x) E k is the vector of objective functions F i (x) : E n E 1 F i (x). x i * is the point minimizing the objective function F i (x)

The feasible decision space X is defined as a set {x|g j ; and h i The feasible objective space Z is defined as a set {F(x)|x X}.

The notion of preference of decision-makers and priority between optimization objectives influence the choice of methods for solving an MOO problem. The author [4], for example, class examples into two categories: methods with expression of preferences in advance (a priori preferences) and the Pareto methods (a posteriori preferences). The reader may refer to the studies on MOO methods in [START_REF] Doufene | Complex Systems Architecture Framework. Extension to Multi-Objective Optimization[END_REF], [START_REF] Balesdent | A survey of multidisciplinary design optimization methods in launch vehicle design[END_REF] and [START_REF] Coello Coello | Multiobjective Optimization Website and Archive[END_REF] for further references. Indeed, in an MOO problem, there is no single and unique global solution, it is often necessary to identify a set of optimal points. The predominant concept in defining an optimal point is Pareto optimality [5]. This is the mathematical definition of a Pareto point:

A point x* X is a Pareto optimum if, and only if, there is not another point x X such as F(x*) and F i (x)<F i (x*) for at least one function. The Pareto optimal points represent the boundary of the space of feasible objectives Z which is called the Pareto frontier.

The solutions which are not Pareto optimal while they meet other constraints are called Weakly Pareto Optimal. A point x* X is a Weakly Pareto optimum if, and only if, there is not another point x X such as .

In other words, a point is a Weakly Pareto Optimal if there is not another point that enhances all objective functions simultaneously. A point is a Pareto optimum if there is not another point that improves at least one objective function at the expense of another function.

However, the preferences of decision makers are difficult to quantify and depend on several parameters within the organizations. Some decision problems in the systems engineering can be seen as decision problems of a single agent (one independent decision maker), but, in many interdependent stakeholders around the SOI (architects, engineers, managers, project managers, program managers. etc.) may have different preferences difficult to quantify and often difficult to converge [START_REF] Lawson | Group decision making in a prototype engineering system : the Federal Open Market Committee[END_REF]. In addition, when designing a system where many external stakeholders are involved, and are expecting some added value, the decisions become interdependent. Thus, we discuss in the following paragraphs the contribution of game theory and Nash equilibrium in addressing such problems.

III. WHY GAME THEORY

Game theory is a rational decision theory of strategically interdependent agents, that is to say, which influence each other and are aware of these reciprocal influences. The games are interactive decision situations in which utility (welfare) of each individual depends on the decisions of other individuals [START_REF] Koessler | Théorie des jeux, support de formation[END_REF].

A. Definitions

Some definitions in this section are adapted from [START_REF] Guerrien | La Théorie des jeux, Livre aux éditions Economica, Collection "poches[END_REF]. The ingredients of a game are a list of n individuals called players, aiming to maximize an objective function or quantified gains, given the information they have (rationality conditions of the players, a rational player is the one who wants maximum gains). We then have n sets, one set by a player, whose elements are called strategies. In addition, we have a mathematical function which matches to each of the possible combinations of strategies available to N players an outcome of the game. This outcome is often represented -especially in the numerical examples by the gain of each player. Indeed, a solution of the game is a combination of strategies, and the associated gains for each player accordingly.

Formally, we have a game with n players. Each player i has a set S i of strategies. s=(s 1 n ) is a combination of strategic choices of n players where s 1 is the strategic choice of the player 1, s 2 is the strategic choice of the player 2 and so on. is the gain of the player i when s is selected, where i can be any player .

The strategies can be pure strategies (no probability) or mixed strategies (for a given pure strategy s 1 , we associate a probability p 1 ). The solution of the game with mixed strategies may not be in the real world, we can imagine a real number (float) to quantify the gain (even if it does not exist in reality). The criterion for comparing the gains in the various possible alternatives is that of expected utility, which is to take the expected gains of pure-strategies obtained by weighting them by the probabilities chosen by the players (their mixed strategies).

We can have a complete information game (each player knows all the possible outcomes of the game and the strategies of the other players) and an incomplete information game (players assign a priori probabilities on the outcomes of the game and the strategies of the other players). The game can be zero-sum when the sum of gains of all players is zero. A nonzero sum game can be reduced to a zero-sum game by creating a fictitious player.

Unlike a non-cooperative game, in a cooperative game the players can create coalitions (agreements on the choice of strategies to play.) A dominant strategy of a player exists if he has a strategy that gives him the maximum gains whatever the strategies of the other players.

Finally, we talk about an equilibrium (a point of rest, which may be the end point of a process) when the players announce their choices and no one regrets his choice given the choices of the other players. The Nash equilibrium is an example. If all strategies is finite (bounded) and the game can include mixed strategies, then the game has at least one Nash equilibrium solution.

B. Nash Equilibrium

Nash equilibrium is a very important concept in game theory (name of John F. Nash, Nobel Prize in Economics in 1994. He introduced the concept of equilibrium in 1951). Nash equilibrium describes an outcome of the game in which no player has an incentive to change his strategy given the strategies of the other players. The formal description of Nash equilibrium can be given as follows [11]:

Let`s define a no-cooperative game with n player and s * =(s *1 *n ) a combination of strategic choices of these n players where s *1 is the strategic choice of the player 1, s *2 is the strategic choice of the player 2 and so on. In addition, let i (s *1 *n ) the gain of the player i when s * is selected, where i can be any player .

Nash Equilibrium is formally defined as follows:

A combination of strategic choices

s * =(s *1 *n ) is a Nash equilibrium if i (s *1 *i i (s *1 i
) for each s i in S i and each player i. S i is the set of strategies of the player i. In summary, s *i is the best strategy of player i when all the other players choose their strategies s * .

In this work, we are interested in studying non-cooperative games (the players cannot talk to each other and sign preferential contracts (particularly because of anti-trust laws prohibiting businesses to communicate with each other to enter into agreements, etc. [11] ))

C. Link with systems engineering

As explained previously, one of the first stages of a systems engineering approach is the modeling of the SOI`s environment. The purpose of this step is to define the interactions between the SOI with the external systems with which it interacts in order to anticipate the evolution of an external system (or several) that could affect other systems. This step clarifies the external interfaces of the SOI before diving its internal architectures. Note that the environment modeling phase is critical. Forgetting an external system could jeopardize the design of the SOI. Indeed, each external system has its own expectations, needs or constraints, throughout the life cycle of the system, the designer should anticipate and satisfy. However, these needs are often interrelated and sometimes antagonistic. In order to maximize the profits related to the SOI, each stakeholder has strategies. Thus, we arrive at a situation where the designer must look for equilibrium for the purpose of stability. This architectural equilibrium should more or less satisfy all these stakeholders and ensure a stable environment throughout the SOI's life cycle.

By taking the vocabulary of the systems engineering and game theory, we assume that each stakeholder can be considered as a player around the SOI and he is rational. Each player has his own strategies to maximize his gains, which account for the satisfaction of his own needs. However, the designer must try to best satisfy the stakeholders (players). At the same time, the designer should find out an architectural equilibrium, meaning that it guarantees the stability of the environment throughout the cycle life of the SOI and the life cycles of all the stakeholders. Finally, we can say that the predesign of this architectural equilibrium is a solution of a game where the stakeholders are the players. If we consider that the stakeholders can build coalitions in the sense that they combine their choice of strategies, it is called cooperative game. Otherwise, it is in a non-cooperative game.

The use of game theory in the context of systems engineering and its relation to design architectural frameworks is mentioned in [START_REF] Bartolomei | Engineering Systems Multiple-Domain Matrix: An Organizing Framework for Modeling Large-Scale Complex Systems[END_REF]. Indeed, the authors propose a framework called Engineering Systems Multiple-Domain Matrix (ES-MDM). The framework is based on the use of several different areas (environmental, social, functional, technical, process) and matrices (designer / decision maker, stakeholder, objectives, functions, objects, activities). Then the authors propose to cross the matrices together and in different areas, for example, the stakeholder matrix about a SOI representing the social field, Stakeholders are human entities that contribute to the objectives of the system and control system components. The extent of their control system defines the scope of the system. For the identification of stakeholders in a given system, it is useful to ask the following questions (cf. Rechtin and Maier (2000) in [START_REF] Bartolomei | Engineering Systems Multiple-Domain Matrix: An Organizing Framework for Modeling Large-Scale Complex Systems[END_REF]): Who benefits? Who pays? Who supplies? And who loses? Then, the authors propose a combination of matrices, such as that of stakeholders with those goals. Each stakeholder has his own objectives, and other stakeholders can declare their support, opposition or indifference. This is used to store information about the positions of the various stakeholders that can be used in a game model to analyze strategies and to align their interests (cf. Dixit and Skeath (2003) in [START_REF] Bartolomei | Engineering Systems Multiple-Domain Matrix: An Organizing Framework for Modeling Large-Scale Complex Systems[END_REF]) on a tutorial on game theory and applications in the real world.)

D. Proposed approach

In our approach, we propose the following interdependence analysis process to identify an architectural equilibrium:

IV. DISCUSSION

One difficulty in finding an architectural equilibrium is that it is not easy to empirically observe the emergence of behavior consistent with a mixed strategy. Indeed, in that case, there is no strict incentive that an actor plays the equilibrium strategy, the use of random strategies implies the use of assumptions on the expected utility and assumptions of risk [START_REF] Koessler | Théorie des jeux, support de formation[END_REF]. Another difficulty in solving games is related to the fact that the information can be complete or incomplete. It is not easy for a player to know all the strategies of other players without contracts for cooperation. In addition, sometimes, it is very difficult to formalize gains functions (we can even be in front of non-formalized gains, such as brand image where the notion of perception is important, etc.) We can also consider the emergence of new issues that brings us clearly in decisions in uncertain situations. However, building such models helps greatly in finding architectural equilibriums, or at least approaching them. The example we presented in [START_REF] Doufene | Sharing the Total Cost of Ownership of Electric Vehicles: A Study on the Application of Game Theory[END_REF] related to electric vehicles is instructive. Indeed, to designing complex industrial system, we believe that two types of optimization models are complementary and necessary. These models take into account the types of decisions that come into play in the choice of solutions.

areto Optimality for finding the best architectural solutions of an SOI given the needs and constraints of the stakeholders / external systems. These solutions correspond to different options or alternatives of the system architectures. Pareto Optimality is useful for "independent" decisions in the sense that these decisions depend only on the choices (or preferences) as defined by the SOI designer. The decision space related to these decisions is a set of endogenous factors.

Nash equilibrium for finding the best equilibrium between the stakeholders surrounding the SOI. The results correspond to different architectural equilibrium. The equilibrium models are useful for "interdependent" decisions, where the decision space contains endogenous and exogenous factors, which depend not only on the SOI designer, but also on other stakeholders.

Finally, we can consider that architectural equilibrium of a given system has an impact on the design, therefore on the independent decisions. The architectural equilibrium gives the first orientations that are made during the design process. Some preliminary design constraints result from the choice of the architectural equilibrium.

V. CONCLUSION

In this paper, we present the contribution of game theory in finding architectural equilibrium, in the context of complex systems engineering. Indeed, for interdependent decisions of different stakeholders involved during the lifecycle of a given system, the concept of equilibrium is important. An architectural equilibrium of the SOI guarantees a better integration, stability of its environment and the satisfaction of all the stakeholders. This assertion is shown by a practical example related to the market of electric vehicles in [START_REF] Doufene | Sharing the Total Cost of Ownership of Electric Vehicles: A Study on the Application of Game Theory[END_REF] [START_REF] Abdelkrim | Architecture des systèmes complexes et Optimisation[END_REF]. Many factors may contribute to the success of electric vehicles, which do not necessarily depend on the car manufacturers but also on other stakeholders such as energy suppliers, local authorities, governments, etc.

1 n)

 1 is the result of the game where i (s 1 n )

1 .

 1 Analysis and modeling of the SOI`s environment 2. Stakeholders identification 3. Macro-needs analysis and identification of strategies (for each stakeholder) 4. Identification of the interdependence between strategies, so between stakeholders 5. SOI Total Cost of Ownership calculation and life-cycle assessment 6. Realization of a distribution matrix -normal or extensive form of the game according to the combination of strategies 7. Setting examples of distribution scenarios 8. Equilibrium calculation 9. If cooperation is possible, create coalitions of stakeholders, and go to 7 10. Emphasize the equilibrium solutions.