Modelling of Complex Systems: Systems as Dataflow Machines

• Autorzy: Bliudze S. , Krob D.
• Języki publikacji: EN

Abstrakty

EN

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 class - which 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.

Słowa kluczowe

EN

complex systems; hybrid system; non-standard analysis; physical system; software system; system modelling; temporized systems; time scale; Turing machine

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 2
• Strony: 251--274
• Opis fizyczny: bibliogr. 49 poz., wykr.

Twórcy

autor

Bliudze S.

autor

Krob D.

• LIX, CNRS & ´Ecole Polytechnique 91128 Palaiseau, France,

Bibliografia

• [1] Akl S., Three counterexamples to dispel the myth of the universal computer, Parallel Processing Letters, 16, (3), 381-403, 2006.
• [2] Alur R., Courcoubetis C., Halbwachs N., Henzinger T. A., Ho P. H., Nicollin X., Olivero A., Sifakis J., Yovine S., The Algorithmic Analysis of Hybrid Systems, Theor. Comp. Sci., 138 (1), 3-34, 1995.
• [3] Alur R., Courcoubetis C., Henzinger T.A., Ho P.H., Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems, Lect. Notes in Comp. Sci., 736, 209-229, Springer, 1993.
• [4] Bacon J., Concurrent systems - An Integrated Approach to Operating Systems, Database, and Distributed Systems, Addison Wesley, 1992.
• [5] Barwise J., Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, 90, North Holland, 1977.
• [6] Bliudze S., A Framework for Studying Complex Industrial Systems: An Example Based on the UMTS Infrastructure, Ph.D. Thesis, école Polytechnique, 2006, http://www-verimag.imag.fr/~bliudze.
• [7] Bliudze S., Krob D., Towards a Functional Formalism for Modelling Complex Industrial Systems, Com-PlexUs, in [Special Issue: Complex Systems - European Conference - November 2005 - Selected Papers - Part 1, Bourgine P., Képès F., SchoenauerM., Eds.], 2 (3-4), 163-176, 2004/2005.
• [8] Bliudze S., Krob D., Modelling of Complex Systems I - A Functional Approach: Time, Data and Systems, Technical report, LIX, école Polytechnique, 2007,
• [9] Blum L., Cucker F., Shub M., Smale S., Complexity and Real Computation, Springer, 1998.
• [10] Bőrger E., Stärk R., Abstract State Machines - A method for high-level system design and analysis, Springer, 1998.
• [11] Bournez O., Campagnolo M.L., A Survey on Continuous Time Computations, in ["New Computational Paradigms. Changing Conceptions of What is Computable", Cooper S.B., Lőwe B., Sorbi A., Eds.], 383-423, Springer, 2008.
• [12] Cha D., Rosenberg J., Dym C., Fundamentals of Modeling and Analyzing Engineering Systems, Cambridge University Press, 2000.
• [13] Cousot P., Cousot R., Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, in ["Conference Record of the Fourth Annual ACM Symposium on Principles of Programming Languages", Los Angeles, California], 238-252, ACM Press, 1977.
• [14] Cutland N., Nonstandard Analysis and its Applications, London Mathematical Society Student Texts, 10, Cambridge University Press, 1988.
• [15] Da Costa N., Doria F., Undecidability and incompleteness in classical mechanics, Int. Journal of Theor. Physics, 30, 1041-1073, 1991.
• [16] D'Alembert Le Rond, J. dit, Article "Différentiel", in [Encyclopédie ou Dictionnaire raisonné des sciences, des arts et des métiers, Diderot D., D'Alembert Le Rond J. dit, Eds.], 4, 985-989, Briasson, David, Le Breton et Durand, Paris, 1754.
• [17] Davis M. Applied nonstandard analysis, John Wiley, 1977.
• [18] Delfini P., Lobry C. The Vibrating String, in ["Nonstandard Analysis in Practice", Diener F., Diener M., Eds.], Springer, 1995.
• [19] Diener F., Diener M., Nonstandard Analysis in Practice, Springer, 1995.
• [20] Diener F., DienerM., Tutorial, in ["Nonstandard Analysis in Practice", Diener F., DienerM., Eds.], Springer, 1995.
• [21] Diener F., Diener M., Ducks and rivers: three existence results, in ["Nonstandard Analysis in Practice", Diener F., Diener M., Eds.], Springer, 1995.
• [22] Diener F., Reeb G., Analyse non standard, Hermann, 1989.
• [23] Hopcroft J. E., Ullman J. D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
• [24] Jensen C. U., Lenzing H., Model Theoretical Algebra, Gordon and Breach, 1989.
• [25] Kanovei V., Reeken M., Nonstandard analysis, axiomatically, Springer Verlag, 2004.
• [26] Kossiakoff A., Sweet W.N., Systems Engineering - Principles and practice, Wiley Series in Systems Engineering, 2003.
• [27] Krob D., Modelling of Complex Software Systems: A Reasoned Overview, in ["Formal Techniques for Networked and Distributed Systems" (FORTE'06), Najm E., Pradat-Peyre J.-F., Donzeau-Gouge V., Eds.], 4229, Springer, 2006.
• [28] Lakatos I., Preuves et réfutations, Hermann, 1984.
• [29] Lamport L., Specifying Systems - The TLA+ Language and Tools for Hardware and Software Engineers, Addison-Wesley, 2003.
• [30] Lygeros J., Lecture notes on hybrid systems, Notes for an ENSIETA Workshop, 2004.
• [31] Marwedel P., Embedded System Design, Kluwer, 2003.
• [32] Meyer K.R., Hall G.R., Introduction to Hamiltonian Dynamical Systems and the N-Body Problem, Applied Mathematical Sciences, 90, Springer, 1992.
• [33] Moore C., Recursion theory on the reals and continuous-time computation, Theor. Comp. Sci., 162 (1), 23-44, 1996.
• [34] Nicolis G., Nicolis C., Foundations of Complex Systems, World Scientific, 2007.
• [35] Pour-El M.B., Richards I., A computable ordinary differential equation which possesses no computable solution, Amer. Math. Logic, 17, 61-90, 1979.
• [36] Rabinovitch A., Automata over Continuous Time, Theor. Comput. Sci., 300, 331-363, 2003.
• [37] Richardson D., Some undecidable problems involving elementary functions of a real variable, The Journal of Symb. Logic, 33, (4), 514-520, 1968.
• [38] Robert F., Les systèmes dynamiques discrets, Mathématiques et Applications, 19, Springer, 1994.
• [39] Robinson A., Non Standard Analysis, North Holland, 1966.
• [40] Sage A.P., Armstrong J.E., Introduction to systems engineering,Wiley, 2000.
• [41] Severance F. L., System Modeling and Simulation: An Introduction, JohnWiley & Sons, 2001.
• [42] Schneider K., Verification of reactive systems - Formal methods and algorithms, Springer, 1998.
• [43] Sontag E., Mathematical Control Theory: Deterministic Finite Dimensional Systems, Textbooks in Applied Mathematics, 6, Springer, 1998.
• [44] Trakhtenbrot B.A., Understanding Basic Automata Theory in the Continuous Time Setting, Fundam. Inform., 62, (1), 69-121, 2004.
• [45] Troesch A., Urlacher E., I. Analyse non standard et équations de Van der Pol. II. Perturbations singulières et analyse non standard, Publications de l'IRMA, Strasbourg, 1977.
• [46] Turner W.C., Mize J.H., Case K.E., Nazemetz J.W., Introduction to industrial systems and systems engineering, Prentice Hall, 1993.
• [47] Zaytoun J., Systèmes dynamiques hybrides, Hermes, 2001.
• [48] Zeigler B. P., Praehofer H., Gon K. T., Theory of Modeling and Simulation- Integrating Discrete Event and Continuous Complex Dynamic Systems, Academic Press, 2000.
• [49] Zurawski R., Embedded Systems Handbook, CRC Press, 2006.