Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Cause-effect structures (1st ed.): An Algebra of Nets with Examples of Applications
Czaja L., Springer Publishing Company, Incorporated, 2019. 160 pp. Type: Book (978-3-030204-60-0)
Date Reviewed: Apr 12 2022

Most systems in the real world--for example, computational, physical, or biologicalones--consist of multiple components that on the one hand operateconcurrently, but on the other hand may also interact with each other. Sinceat any time many interactions are possible but not guaranteed, thesesystems exhibit nondeterministic behavior, which makes it challenging topredict in which states the systems may be. Only by modeling suchconcurrent systems in a suitable formal framework and applying rigorousmathematical/logical techniques does an adequate analysis and verificationbecome possible. This book presents such a formal framework, that of cause-effect (c-e)structures, which has been mainly developed by the author himself.

The basic idea is to represent a network of interacting components by thealgebraic structure of a quasi-semiring whose elements are the components.Two algebraic expressions are associated to each element: a “cause”expression describes which combinations of messages sent by othercomponents may trigger the activation of the component; an “effect”expression describes which combination of messages the activated componentmay send to other components. These expressions take the form of formalpolynomials where addition represents nondeterministic “choice” andmultiplication represents “simultaneity.” The core topic of the book is todevelop the corresponding algebraic theory and demonstrate its applicationto concrete examples.

In fact, the interpretation of c-estructures coincides very much with the behavior ofPetri nets, another well-known model with which c-estructures share a lot ofsimilarities, in particular an intuitive graphic presentation. However,while Petri nets are described by bipartite graphs consisting of two kindsof nodes, “places” and “transitions,” c-e graphs have only one kindof node labeled by the “cause” and “effect” polynomials. Indeed,these polynomials alone define the dynamic behavior of the system, while theedges of the graph only describe its static structure. This representationof c-e structures yields a very elegant algebraic theory where a system can bedescribed by an algebraic expression and its evolution is shown byrewriting the expression according to the axioms of the quasi-semiring.

The first two chapters introduce the basic ideas in aprecise but illustrative way. In particular, chapter 1 gives the motivationfor the theory, its origins and history, and then presents a very usefulhigh-level survey over the main topics of the remaining chapters. It alsodemonstrates a software tool for developing c-e structures in a graphical wayand having their execution animated. Chapter 2 describes the basic theory ofelementary c-e structures, introduces various equivalent representation forms (aspolynomial-annotated nodes, as graphs, and as linear “arrow-expressions”),and discusses the relationship of c-e structures to Petri nets. Furthermore, it givesvarious concrete application examples of systems modeled as c-e structures.

After these must-read chapters, the book pursues different directions,each of which is covered by a sequence of short chapters. Chapters 3 to 5discuss various extensions of elementary c-e structures by nodes that inhibitparticular transitions, by multiple models of “time,” and by abstractions ofc-e structures to “rough” c-e structures. Chapters 7 and 8 further develop the basic theory byanalyzing the syntactical properties of c-e structures (structural decomposition) aswell as semantic properties (verification of safety and liveness). Chapter 9provides an in-depth discussion of the actual relation of c-e structures to Petri nets, andchapters 10 through 12 discuss the properties of “processes” that describe theevolution of c-e activities. Chapter 13 returns to the topic of practicalapplication by modeling various concurrent systems, mostly describingfundamental synchronization and coordination problems in concurrency theoryas well as problems arising in traffic and systems control.

The book is very well written and structured, with information presented in avery compact form. Readers interested in a general overview of thetheory and its potential to applications will be mostly satisfied withchapters 1, 2, and 13; the remaining chapters provide more in-depth informationthat can be read according to one’s interests. The many examples provide good illustrations of the varioustheoretical concepts introduced throughout the book.

As for the potential of the theory itself, the book mainly shines whenillustrating the modeling of concurrent systems. However, actually analyzing such systems with respect to properties of interest isnot given the same depth. Furthermore, while the theory has drawn much inspiration from Petri nets,the resulting algebraic structure has much more in common with processcalculi such as Milner’s calculus of communicating systems (CSS) or thepi-calculus; a comparative evaluation would have been of interest.

Despite these minor misgivings, the book is highly recommended. It presentsan interesting alternative to the well-known theory of Petri nets, withmuch potential that deserves a wider audience.

Reviewer:  Wolfgang Schreiner Review #: CR147429 (2207-0091)
Bookmark and Share
  Featured Reviewer  
Symbolic and Algebraic Manipulation (I.1 )
Petri Nets (D.2.2 ... )
Organization And Design (D.4.7 )
General (I.0 )
Would you recommend this review?
Other reviews under "Symbolic and Algebraic Manipulation": Date
Data structure properties for scientific computing: an algebraic topology library
Heinzl R.  POOSC 2009 (Proceedings of the 8th Workshop on Parallel/High-Performance Object-Oriented Scientific Computing, Genova, Italy, Jul 7, 2009)1-6, 2009. Type: Proceedings
Oct 27 2009
Mathematics, computer science and logic - a never ending story: the Bruno Buchberger Festschrift
Paule P., Springer Publishing Company, Incorporated, New York, NY, 2013.  120, Type: Book (978-3-319009-65-0)
Jan 27 2014
Estimating the number of tetrahedra determined by volume, circumradius and four face areas using Groebner basis
Tsai Y. Journal of Symbolic Computation 77162-174, 2016. Type: Article
Feb 22 2017

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy