×

Network algebra. (English) Zbl 0956.68002

Discrete Mathematics and Theoretical Computer Science. London: Springer. xvi, 400 p. (2000).
This book is structured in 4 Parts,12 chapters. Part I is an introduction to Network Algebra and is formed by an overview of the key results and by the Chapter 1, ”Network Algebra and its applications”. This chapter is an introduction to the calculus of flownomials. The most important parts of this book are Part II (Chapters 2-6) which contains results on general, abstract networks, and Part III (Chapter 7-11) dedicated to particular networks. In Chapter 2 is introduced the BNA structure (or aá-flow) and is proved the soundness and correctness of BNA axioms for networks modulo graph isomorphism. Chapter 3 presents algebraic models for branching constants to the BNA signature and corresponding weak axioms. Also the main results of Chapter 2 are extended to networks with branching constants. The network behavior is the subject of the Chapter 4. So the strong and enzymatic axioms for branching constants are introduced, which it allows to duplicate or remove network cells. In Chapters 5 and 6 are presented Elgot theories, Milner theories, Kleene theories and Park theories. For this theories some structural theorems are presented. Part II ends with a table containing the basic axioms used in the calculus of flownomials. Part III presents the algebraic theory of special networks. Flow-chart scheme is the subject of the Chapter 7. The main result here is the soundness and completeness of Floyd-Hoare logic, when it is interpreted in Cazanescu - Ungureanu theories. Also a few interesting duality results between flow-chart and circuit are presented. The fundamental results on finite automata are presented in the Chapter 8. So the connections between nondeterministic and deterministic automata, minimization and relation to regular expressions are presented. The subject of the Chapter 9 is a short presentation of process algebra, in its ACP versions. Chapter 10 is dedicated to data-flow network. Are presented synchronous and asynchronous networks, axiomation asynchronous deterministic and nondeterministic networks. The Chapter 11 is a brief presentation of Petri nets and the connection between Perti net languages and concurrent regular expressions. The Part IV is formed by a single chapter, Chapter 12, which describes the mixed network algebra models, obtained mixing network algebra models for control space and time. In the end there is an Appendix containing technical proofs. Interesting exercises and problems accompany most of sections. Also some open questions related to this subject are present.

MSC:

68M10 Network design and communication in computer systems
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q45 Formal languages and automata
68-02 Research exposition (monographs, survey articles) pertaining to computer science

Software:

CafeOBJ