+612 9045 4394
 
CHECKOUT
Abstract Compositional Analysis of Iterated Relations : A Structural Approach to Complex State Transition Systems : Lecture Notes in Computer Science, - Fraedaeric Geurts

Abstract Compositional Analysis of Iterated Relations : A Structural Approach to Complex State Transition Systems

Lecture Notes in Computer Science,

Paperback ISBN: 9783540655060
Number Of Pages: 280

Share This Book:

Paperback

$125.05
or 4 easy payments of $31.26 with Learn more
Ships in 5 to 9 business days

This self-contained monograph is an integrated study of generic systems defined by iterated relations using the two paradigms of abstraction and composition. This accommodates the complexity of some state-transition systems and improves understanding of complex or chaotic phenomena emerging in some dynamical systems. The main insights and results of this work concern a structural form of complexity obtained by composition of simple interacting systems representing opposed attracting behaviors. This complexity is expressed in the evolution of composed systems (their dynamics) and in the relations between their initial and final states (the computation they realize). The theoretical results are validated by analyzing dynamical and computational properties of low-dimensional prototypes of chaotic systems, high-dimensional spatiotemporally complex systems, and formal systems.

Forewordp. V
Prefacep. VII
Prologue: Aims, Themes, and Motivationsp. 1
Complex Relational Dynamical Systemsp. 2
The Context: A First Contact with Dynamical Systemsp. 2
Mutual Exclusionp. 4
Social Pressurep. 7
On the Chaotic Demography of Rabbitsp. 9
Tools and Motivationsp. 14
Overview of the Monographp. 16
Mathematical Framework: Iterated Relations and Composition
Dynamics of Relationsp. 21
Functional Discrete-Time Dynamical Systemsp. 22
Relational Dynamical Systemsp. 24
Point-Level Nondeterministic Dynamicsp. 25
Set-Level Deterministic Dynamicsp. 26
Comparisonp. 26
Preliminary Definitions and Propertiesp. 28
Basic Definitions About Relationsp. 28
Notions from Topologyp. 31
Monotonicity and General Junctivity Propertiesp. 33
Fixpoint Theoremsp. 37
Elementary Propertiesp. 39
Metric Propertiesp. 40
Transfinite Iterationsp. 44
Motivationp. 44
Transfinite Fixpoint Theoremp. 45
Transfinite Limits of Iterationsp. 47
Discussionp. 48
Relations vs Functionsp. 48
Set-Level Dynamics and Predicate-Transformersp. 49
Point-Level Dynamics and Trace Semanticsp. 50
Nondeterminism and Probabilistic Choicesp. 50
Transfinite Iterationsp. 51
Time Structurep. 51
Dynamics of Composed Relationsp. 53
Structural Compositionp. 53
Composition of Relationsp. 54
Unary Operatorsp. 55
N-Ary Operatorsp. 56
Composed Dynamical Systemsp. 59
Dynamics of Composed Relationsp. 62
One-Step Set-Level Evolution of Composed Relationsp. 62
Point-Level Dynamics of Composed Systemsp. 67
Algebraic Properties of Composition Operatorsp. 71
Composition of Unary Operatorsp. 72
Composition of Unary and N-Ary Operatorsp. 72
Composition of N-Ary Operatorsp. 73
Fixpoint Theory for the Compositionp. 75
Discussionp. 77
Composition Operatorsp. 77
Nondeterminism and Probabilities Revisitedp. 78
Fixpoint Operator and Compositionp. 79
Abstract Complexity: Abstraction, Invariance, Attraction
Abstract Observation of Dynamicsp. 83
Observation of Systemsp. 83
Trace-Based Dynamicsp. 85
Symbolic Observationp. 86
Abstraction of Systemsp. 88
Qualitative Abstract Verificationp. 89
Observation as Abstractionp. 91
Discussionp. 91
Observation and Abstraction: Related Workp. 92
Symbolic Dynamics vs Astract Observationp. 92
Qualitative Abstract Verificationp. 93
Invariance, Attraction, Complexityp. 95
Invariancep. 96
Forward and Backward Invariancep. 96
Global Invariancep. 100
Strong Invariancep. 100
Structure of Invariantsp. 102
Trace-Parametrized Invariantsp. 103
Fullness and Atomicityp. 104
Chaosp. 106
Fullness Implies Trace Chaosp. 108
Fullness and Atomicity Imply Knudsen Chaosp. 108
Devaney vs Trace vs Knudsen Chaosp. 109
Fullness and Atomicity Criteriap. 110
Criteriap. 110
Case Studies: Dyadic Map, Cantor Relation, Logistic Mapp. 113
Attractionp. 119
Intuition: From Reachability to Attractionp. 120
From Weak to Full Attractionp. 121
A Taxonomy of Attractionp. 123
Attraction Criteriap. 125
Attraction by Invariantsp. 126
Discussionp. 128
Invariance and Attraction: Related Notionsp. 128
Energy-Like Functionsp. 129
Dynamical Complexityp. 130
Abstract Compositional Analysis of Systems: Dynamics and Computations
Compositional Analysis of Dynamical Propertiesp. 135
Aims and Informal Resultsp. 135
Inversionp. 138
Restrictionsp. 140
Domain Restrictionp. 140
Range Restrictionp. 141
Negationp. 143
Sequential Compositionp. 144
Intersectionp. 146
Unionp. 147
Productsp. 154
Free Productp. 154
Connected Productp. 155
Combining Union with Free Productp. 156
Discussionp. 156
Compositionality: Summaryp. 157
Limitations and Open Problemsp. 157
Related Workp. 159
Emergence of Complexity by Structural Compositionp. 160
Case Studies: Compositional Analysis of Dynamicsp. 163
A Collection of Complex Behaviorsp. 163
Smale Horseshoe Mapp. 164
Cantor Relationp. 168
From Cantor Relation to Truncated Logistic Mapp. 169
Paperfoldingsp. 172
Introductionp. 172
Paperfolding Sequencesp. 173
Dynamical Complexity of Paperfoldingsp. 177
Partial Conclusionsp. 180
Discussion: Compositional Dynamical Complexityp. 180
Experimental Compositional Analysis of Cellular Automatap. 183
Aims and Motivations: Attraction-Based Classification and Compositionp. 184
Preliminary Notionsp. 186
Cellular Automatap. 186
Transfinite Attractionp. 188
Shifted Hamming Distancep. 188
Experimental Classificationp. 189
Formal Attraction-Based Classificationp. 191
Introductionp. 192
Type-<$>{\cal N}<$> Cellular Automatap. 193
Type-<$>{\cal F}<$> Cellular Automatap. 193
Type-<$>{\cal P}<$> Cellular Automatap. 194
Type-<$>{\cal S}<$> Cellular Automatap. 194
Type-<$>{\cal A}<$> Cellular Automatap. 195
Discussionp. 196
Structural Organizations of CA Classesp. 196
Motivation: Simulation vs Theoretical Resultsp. 196
Linear Periodicity Hierarchyp. 198
Periodicity Clusteringp. 199
Organization w.r.t. Shifted Hamming Distancep. 199
Dynamical Complexity in CAp. 201
Conjectures in CA Compositionp. 201
Complexity by Composition of Shiftsp. 203
Rules 2 and 16p. 203
Cantor Relationp. 204
Comparisonp. 206
A More Precise Conjecturep. 206
Qualitative Analysis and Complexity Measuresp. 206
Compositional Analysis of Complex CAp. 208
Local Disjunction, Local Union, and Global Unionp. 208
Comparison and Summary of Resultsp. 210
Discussionp. 211
Summary and Partial Conclusionp. 211
Open Questionsp. 212
Classification: State-of-the-Artp. 213
Aperiodicity in Cellular Automatap. 215
Related Work in Compositionp. 216
Compositional Analysis of Computational Propertiesp. 217
Automata as Dynamical Systemsp. 217
Comparing Dynamical Systemsp. 220
Extrinsic Methodp. 220
Intrinsic Methodp. 221
Our Comparisonp. 221
From Locality to Globalityp. 221
Turing Machinesp. 222
Cellular Automatap. 223
Continuous Functionsp. 224
General Modelp. 224
Comparison Through Simulationp. 227
Simulationp. 227
Choice of Codingp. 228
From TM to CAp. 228
From CA to CFp. 231
Weak Hierarchyp. 232
Topological and Metric Propertiesp. 232
Continuityp. 233
Shift-Invariancep. 233
Lipschitz Propertyp. 234
Shift-Vanishing Effectp. 235
Nondeterminismp. 235
Summaryp. 237
Computability of Initial Conditionsp. 238
Hierarchy of Systemsp. 239
Discussionp. 240
Composition and Computationp. 240
Further Workp. 240
Related Workp. 241
Epilogue: Conclusions and Directions for Future Workp. 243
Contributions and Related Workp. 244
Mathematical Frameworkp. 245
Compositional Analysisp. 246
Directions for Future Researchp. 247
A Patchwork of Open Technical Issuesp. 248
Fractal Image Compressionp. 248
Distributed Dynamical Optimizationp. 249
Distributed Systems and Self-Stabilizationp. 250
Probabilistic Systems and Measuresp. 250
Higher-Order Systems, Control, and Learningp. 251
Design of Attraction-Based Systemsp. 252
The Garden of Structural Similaritiesp. 253
Coda: Compositional Complexity Revisitedp. 255
Bibliographyp. 257
Glossary of Symbolsp. 273
Indexp. 277
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9783540655060
ISBN-10: 3540655069
Series: Lecture Notes in Computer Science,
Audience: General
Format: Paperback
Language: English
Number Of Pages: 280
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 1.55
Weight (kg): 0.41