The world is increasingly populated with interactive agents distributed in space, real or abstract. These agents can be artificial, as in computing systems that manage and monitor traffic or health; or they can be natural, e.g. communicating humans, or biological cells. It is important to be able to model networks of agents in order to understand and optimize their behavior. Robin Milner describes in this book just such a model, by presenting a unified and rigorous structural theory, based on bigraphs, for systems of interacting agents. This theory is a bridge between the existing theories of concurrent processes and the aspirations for ubiquitous systems, whose enormous size challenges our understanding. The book is self-contained mathematically and is designed to be learned from: examples and exercises abound, solutions for the latter are provided.
Author(s): Robin Milner
Edition: 1
Publisher: Cambridge University Press
Year: 2009
Language: English
Pages: 215
Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
The informatic challenge......Page 11
Space......Page 13
Motion......Page 14
Generality......Page 16
Rigour......Page 18
Outline of the book......Page 19
Acknowledgements......Page 23
Part I: Space......Page 25
1 The idea of bigraphs......Page 27
2.1 Bigraphs and their assembly......Page 38
2.2 Mathematical framework......Page 42
2.3 Bigraphical categories......Page 49
3.1 Elementary bigraphs and normal forms......Page 52
3.2 Derived operations......Page 57
4 Relative and minimal bounds......Page 63
5.1 RPOs for bigraphs......Page 70
5.2 IPOs in bigraphs......Page 76
5.3 Abstract bigraphs lack RPOs......Page 81
6.1 Place sorting and CCS......Page 83
6.2 Link sorting, arithmetic nets and Petri nets......Page 88
6.3 The impact of sorting......Page 93
Part II: Motion......Page 95
7 Reactions and transitions......Page 97
7.1 Reactive systems......Page 98
7.2 Transition systems......Page 101
7.3 Sub transition systems......Page 108
7.4 Abstract transition systems......Page 109
8 Bigraphical reactive systems......Page 112
8.1 Dynamics for a BRS......Page 113
8.2 Dynamics for a nice BRS......Page 118
9.1 Arithmetic nets......Page 124
9.2 Condition–event nets......Page 127
10.1 Syntax and reactions for CCS in bigraphs......Page 134
10.2 Transitions for CCS in bigraphs......Page 138
Part III: Development......Page 145
11.1 Tracking......Page 147
11.2 Growth......Page 149
11.3 Binding......Page 154
11.4 Stochastics......Page 161
12 Background, development and related work......Page 163
Appendices......Page 170
A.1 Support translation......Page 171
A.2 Public versus private names......Page 172
A.3 RPOs for link graphs......Page 173
A.4 Quotient of a transition system......Page 175
A.5 Unambiguity of labels......Page 176
A.6 Faithfulness of engaged transitions......Page 177
A.7 Recovering bisimilarity for CCS......Page 183
Solutions for Chapter 1......Page 186
Solutions for Chapter 3......Page 188
Solutions for Chapter 4......Page 190
Solutions for Chapter 5......Page 191
Solutions for Chapter 6......Page 192
Solutions for Chapter 7......Page 194
Solutions for Chapter 11......Page 196
Glossary of terms and symbols......Page 201
References......Page 204
Index......Page 209
