Abstract Compositional Analysis of Iterated Relations

A Structural Approach to Complex State Transition Systems

Frederic Geurts (Autor)

Buch | Softcover

XII, 280 Seiten

1998 | 1998
Springer Berlin (Verlag)
978-3-540-65506-0 (ISBN)

Artikel merken

State-transition systems model machines, programs, and speci?cations [20, 23,284,329],butalsothegrowthanddeclineofantpopulations,?nancial markets, diseases and crystals [22, 35, 178, 209, 279]. In the last decade, thegrowinguseofdigitalcontrollersinvariousenvironmentshasentailed theconvergenceofcontroltheoryandreal-timesystemstowardhybrids- tems [16] by combining both discrete-event facets of reality with Nature s continuous-time aspects. The computing scientist and the mathematician have re-discovered each other. Indeed, in the late sixties, the programming language Simula, father of modern object-oriented languages, had already been speci?cally designed to model dynamical systems [76]. Today,theimportanceofcomputer-basedsystemsinbanks,telecom- nication systems, TVs, planes and cars results in larger and increasingly complex models. Two techniques had to be developed and are now fruitfully used to keep analytic and synthetic processes feasible: composition and - straction.Acompositionalapproachbuildssystemsbycomposingsubsystems that are smaller and more easily understood or built. Abstraction simpli?es unimportantmattersandputstheemphasisoncrucialparametersofsystems. Inordertodealwiththecomplexityofsomestate-transitionsystemsand tobetterunderstandcomplexorchaoticphenomenaemergingoutofthe behaviorofsomedynamicalsystems,theaimofthismonographistopresent ?rststepstowardtheintegratedstudyofcompositionandabstractionin dynamical systems de?ned by iterated relations. Themaininsightsandresultsofthisworkconcernastructuralorm f of complexityobtainedbycompositionofsimpleinteractingsystemspresenting opposedattractingbehaviors.Thiscomplexityexpressesitselfintheevo- tionofcomposedsystems,i.e.,theirdynamics,andintherelationsbetween their initial and ?nal states, i.e., the computations they realize. The theor- ical results presented in the monograph are then validated by the analysis ofdynamicalandcomputationalpropertiesoflow-dimensionalprototypesof chaotic systems (e.g. Smale horseshoe map, Cantor relation, logistic map), high-dimensional spatiotemporally complex systems (e.g. cellular automata), and formal systems (e.g. paperfoldings, Turing machines). Acknowledgements. ThismonographisarevisionofmyPhDthesiswhichwas completed at the Universit e catholique de Louvain (Belgium) in March 96. VIII Preface The results presented here have been in?uenced by many people and I would like to take this opportunity to thank them all.

Prologue: Aims, Themes, and Motivations.- Prologue: Aims, Themes, and Motivations.- Mathematical Framework: Iterated Relations and Composition.- Dynamics of Relations.- Dynamics of Composed Relations.- Abstract Complexity: Abstraction, Invariance, Attraction.- Abstract Observation of Dynamics.- Invariance, Attraction, Complexity.- Abstract Compositional Analysis of Systems: Dynamics and Computations.- Compositional Analysis of Dynamical Properties.- Case Studies: Compositional Analysis of Dynamics.- Experimental Compositional Analysis of Cellular Automata.- Compositional Analysis of Computational Properties.- Epilogue: Conclusions and Directions for Future Work.

Erscheint lt. Verlag	18.12.1998
Reihe/Serie	Lecture Notes in Computer Science
Zusatzinfo	XII, 280 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	390 g
Themenwelt	Informatik ► Software Entwicklung ► User Interfaces (HCI)
Themenwelt	Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
Schlagworte	Complexity • compositional analysis • Dynamical Systems • Dynamisches System • Dynamische Systeme • Iterated Relations • Mathematische Logik • program analysis • Software Engineering / Softwareentwicklung • Softwareentwicklung • State Transitions Systems
ISBN-10	3-540-65506-9 / 3540655069
ISBN-13	978-3-540-65506-0 / 9783540655060
Zustand	Neuware