Network algebra considers the algebraic study of networks and their behavior. It approaches the models in a sharp and simple manner. This book takes an integrated view of a broad range of applications, varying from concrete hardware-oriented models to high-level software-oriented models.

Inhalt

I. An introduction to Network Algebra.- Brief overview of the key results.- Regular expressions.- Iteration theories.- Flownomials.- Basic results.- Mixed calculi.- Structure of the book.- Acknowledgments.- 1. Network Algebra and its applications.- 1.1 Algebra of finite relations.- 1.2 Basic Network Algebra, BNA.- 1.3 Flownomial expressions.- 1.4 Concrete vs. abstract networks.- 1.5 Network algebra, NA.- 1.6 Control, space, time: 3 faces of NA models.- 1.7 Feedback, iteration, and repetition.- 1.8 Network behaviours as xy-flows.- 1.9 Mixed Network Algebra, MixNA.- Comments, problems, bibliographic remarks.- II. Relations, flownomials, and abstract networks.- 2. Networks modulo graph isomorphism.- 2.1 Symocats.- 2.2 Bijections in symocats.- 2.3 Bijections in BNAs.- 2.4 Semantic models: I. BNA structure.- 2.5 Other presentations of BNAs.- 2.6 Network representation; model [X,T]a?.- 2.7 Working with flownomials.- 2.8 BNA soundness.- 2.9 BNA completeness.- 2.10 Networks as a?-flownomials.- Comments, problems, bibliographic remarks.- 3. Algebraic models for branching constants.- 3.1 xy-symocats (xy-weak rules).- 3.2 Angelic vs. demonic operators.- 3.3 Semantic models: II. NA structure.- 3.4 Normal form for relations.- 3.5 Axioms for relations.- 3.6 Simplification.- 3.7 Relations in xy-symocats.- 3.8 Relations in xy-symocats with feedback.- 3.9 Networks with branching constants.- Comments, problems, bibliographic remarks.- 4. Network behaviour.- 4.1 Strong xy-symocats (xy-strong rules).- 4.2 Algebraic theories.- 4.3 Matrix theories.- 4.4 Enzymatic rule (xy-enzymatic rules).- 4.5 Strong axioms: from cells to networks.- 4.6 xy-flows.- 4.7 Semantic models: III. xy-flow structure.- 4.8 Simulation.- 4.9 Enzymatic rule: from connections to networks.- 4.10 Duality: I. Reversing arrows.- Comments, problems, bibliographic remarks.- 5. Elgot theories.- 5.1 Input behaviour; regular trees.- 5.2 Elgot theories (a?-flows).- 5.3 Structural Theorem, case a?.- 5.4 Soundness for a?-flow.- 5.5 Completeness for a?-flow.- 5.6 Working with a?-flownomials.- 5.7 Output behaviour.- 5.8 Bisimulation: two-way simulation.- 5.9 Milner theories.- Comments, problems, bibliographic remarks.- 6. Kleene theories.- 6.1 IO behaviour, deterministic case.- 6.2 Park theories (b?-flow).- 6.3 Structural Theorem, case b?.- 6.4 Soundness for b? -flow.- 6.5 Completeness for b?-flow.- 6.6 Working with b?-flownomials.- 6.7 IO behaviour, nondeterministic case.- 6.8 Kleene theories (d?-flow).- 6.9 Structural Theorem, case d?.- 6.10 Soundness for d?-flow.- 6.11 Completeness for d?-flow.- 6.12 Working with d?-flownomials.- Comments, problems, bibliographic remarks.- III. Algebraic theory of special networks.- 7. Flowchart schemes.- 7.1 Structural programs.- 7.2 Flowchart representation.- 7.3 Floyd-Hoare logic.- 7.4 Soundness of Floyd-Hoare logic.- 7.5 Completeness of Floyd-Hoare logic.- 7.6 Duality: II. Control-Space.- 7.7 Iteration and feedback in (co)algebraic theories.- Comments, problems, bibliographic remarks.- 8. Automata.- 8.1 Finite automata.- 8.2 Simulation.- 8.3 From nondeterministic to deterministic automata.- 8.4 Minimization: I. Accessibility.- 8.5 Minimization: II. Reduction.- 8.6 Minimization: III. Deterministic automata.- 8.7 Regular expressions and Kleene algebras.- 8.8 Kleene Theorem: I. From automata to regular expressions.- 8.9 Kleene Theorem: II. From regular expressions to automata.- 8.10 Axiomatization, regular expressions.- 8.11 Repetition, iteration, and feedback in matrix theories.- Comments, problems, bibliographic remarks.- 9. Process algebra.- 9.1 An overview on parallel processes.- 9.2 Transition systems.- 9.3 Nondeterministic sequential processes; BPA plus recursion.- 9.4 Coloured traces.- 9.5 Communicating processes; ACP.- 9.6 Soundness and completeness of ACP.- 9.7 Abstraction.- 9.8 A case study: Alternating Bit Protocol.- Comments, problems, bibliographic remarks.- 10. Data-flow networks.- 10.1 Data-flow networks; general presentation.- 10.2 Synchronous networks.- 10.3 Asynchronous networks.- 10.4 Axiomatization: asynchronous, deterministic case.- 10.5 Time anomaly for nondeterministic networks.- 10.6 Axiomatization: asynchronous, nondeterministic case.- 10.7 Fully abstract models.- 10.8 Network algebra on top of process algebra.- Comments, problems, bibliographic remarks.- 11. Petri nets.- 11.1 Introducing the model.- 11.2 Concurrent regular expressions (CRegExp).- 11.3 Decomposed Petri nets.- 11.4 From Petri net languages to CRegExp.- 11.5 From CRegExp to Petri net languages.- 11.6 Equivalence of CRegExp and Petri net languages.- Comments, problems, bibliographic remarks.- IV. Towards an algebraic theory for software components.- 12. Mixed Network Algebra.- 12.1 Why mixed network algebra models?.- 12.2 Mixing control, space, and time.- 12.3 Acyclic models.- 12.3.1 Sysecats.- 12.3.2 Mixed relations.- 12.3.3 Distributive categories (discats).- 12.3.4 Mixalgebras.- 12.3.5 Plans.- 12.4 Compilers, code generation.- 12.5 Duality: III. Space-time.- 12.6 Object-oriented programs/software components.- Comments, problems, bibliographic remarks.- Related calculi, closing remarks.- Appendix B: Lifting BNA from connections to networks.- Appendix C: Demonic relation operators.- Appendix D. Generating congruences.- Appendix E: Automata, complements.- Appendix F: Data-flow networks; checking NA axioms.- Appendix G: Axiomatizing mixed relations.- Appendix H: Discats as sysecats.- Appendix I: Decomposing morphisms in discats.- Appendix J: Plans as free discats.- List of tables.- List of figures.