Logo - springer
Slogan - springer

Mathematics - Computational Science & Engineering | Network Algebra

Network Algebra

Stefanescu, Gheorghe

Softcover reprint of the original 1st ed. 2000, XVI, 400 pp.

Available Formats:

Springer eBooks may be purchased by end-customers only and are sold without copy protection (DRM free). Instead, all eBooks include personalized watermarks. This means you can read the Springer eBooks across numerous devices such as Laptops, eReaders, and tablets.

You can pay for Springer eBooks with Visa, Mastercard, American Express or Paypal.

After the purchase you can directly download the eBook file or read it online in our Springer eBook Reader. Furthermore your eBook will be stored in your MySpringer account. So you can always re-download your eBooks.


(net) price for USA

ISBN 978-1-4471-0479-7

digitally watermarked, no DRM

Included Format: PDF

download immediately after purchase

learn more about Springer eBooks

add to marked items


Softcover (also known as softback) version.

You can pay for Springer Books with Visa, Mastercard, American Express or Paypal.

Standard shipping is free of charge for individual customers.


(net) price for USA

ISBN 978-1-85233-195-5

free shipping for individuals worldwide

usually dispatched within 3 to 5 business days

add to marked items

  • About this textbook

Network Algebra considers the algebraic study of networks and their behaviour. It contains general results on the algebraic theory of networks, recent results on the algebraic theory of models for parallel programs, as well as results on the algebraic theory of classical control structures. The results are presented in a unified framework of the calculus of flownomials, leading to a sound understanding of the algebraic fundamentals of the network theory. The term 'network' is used in a broad sense within this book, as consisting of a collection of interconnecting cells, and two radically different specific interpretations of this notion of networks are studied. One interpretation is additive, when only one cell is active at a given time - this covers the classical models of control specified by finite automata or flowchart schemes. The second interpretation is multiplicative, where each cell is always active, covering models for parallel computation such as Petri nets or dataflow networks. More advanced settings, mixing the two interpretations are included as well. Network Algebra will be of interest to anyone interested in network theory or its applications and provides them with the results needed to put their work on a firm basis. Graduate students will also find the material within this book useful for their studies.

Content Level » Professional/practitioner

Keywords » Concurrency and Control - Feedback - Network Algebra - algebra - calculus - parallel computation

Related subjects » Communication Networks - Computational Science & Engineering - Signals & Communication

Table of contents 

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.

Popular Content within this publication 



Read this Book on Springerlink

Services for this book

New Book Alert

Get alerted on new Springer publications in the subject area of Algorithms.