This book focuses on numerous examples of tasks represented by c-e structure. Cause–effect (c-e) structures are dynamic objects devised for algebraic and graphic description of realistic tasks. They constitute a formal system providing means to specify or implement (depending on degree of description generality) the tasks. They can be transformed, thus come under simplification, in accordance with rules-axioms of their algebra. Also, their properties can be inferred from the axioms. One objective of this book is presentation, by many realistic examples, of computing capability of c-e structures, without entering into mathematical details of their algebra. In particular, how computing with natural numbers and in propositional calculus can be performed by c-e structures and how to specify behavior of data structures. But also demonstration of many other tasks taken from the area of parallel processing, specified as c-e structures. Another objective is modelling or simulation by means of c-e structures, of other descriptive systems, devised for tasks from various fields. Also without formalizing by usage of functions between the systems. This concerns formalisms such as reaction systems, rough sets, Petri nets and CSP-like languages. Also on such, where temporal interdependence between actions matters. The presentation of examples is prevalently graphic, in the form of peculiar nets, but accompanied by their algebraic and set-theoretic expressions. A fairly complete exposition of concepts and properties of the algebra of cause-effect structures is in the previous book appeared in the Lecture Notes in Networks and Systems series. But basic notions of c-e structures are here provided for understanding the examples.
Author(s): Ludwik Czaja
Series: Lecture Notes in Networks and Systems, 331
Publisher: Springer
Year: 2021
Language: English
Pages: 187
City: Cham
Preface
References
Acknowledgements
Contents
About the Author
1 About Content of the Book
References
2 Basic Concepts of Cause-Effect Structures
2.1 A Set-Theoretic Model of Axioms of the Quasi-semiring of Formal Polynomials
2.2 Selected Structural Properties
2.3 Selected Semantic Properties and Remarks
2.4 Drawing Conventions
2.5 Example of Constructing C-E Structure
References
3 Computing with Natural Numbers
3.1 The Addition (Iterated Adding of Unity)
3.2 The Restricted Subtraction (Iterated Subtracting of Unity)
3.3 The Multiplication (Iterated Adding a Number to Itself)
3.4 The Division with Neglected Remainder …
3.5 The Remainder
3.6 The Division with Remainder
3.7 The Exponentiation (Iterated Multiplication of a Number by Itself)
3.8 The Factorial (Iterated Multiplication with Successively Decreased Argument)
3.9 Summation of a Sequence of Numbers
3.10 Inner Product of Two Vectors, Sequential Computation
3.11 Inner Product of Two Vectors, Parallel Computation
3.12 Greatest Common Divisor
3.13 Lowest Common Multiple
3.14 The ``3k + 1'' Problem
3.15 Comparing Numbers: ``if Greater Than'' or ``if Less Than''
3.16 Comparing Numbers: ``if Greater Than'' or ``if Less Than'' or ``if Equals''
3.17 Integer Part of Square Root
References
4 Computing Logical (Boolean) Functions
4.1 One-Argument Logical Functions
4.1.1 Constant Functions
4.1.2 Negation and Identity
4.2 Two-Argument Logical Functions
4.2.1 Disjunction
4.2.2 Conjunction
4.2.3 Implication
4.2.4 Sheffer Function f(x,y)=(xwedgey) (Denoted Sometimes as underlinenand or x/y)
4.2.5 Exclusive Disjunction (xor)
4.2.6 f(x,y)=(xveey) (Negation of Disjunction Denoted Sometimes as underlinenor)
4.2.7 Example of Tautology f(x,y)=(xy)vee(yx)
4.3 Three-Argument Logical Functions
4.3.1 Frege Tautology ch4Fre1884 f(x,y,z)=[(x(yz)] [(xy)(xz)]
4.3.2 Threshold Function ch4SspsTspsHsps1965, ch4Lozspsetspsal2017 f(x,y,z)=(xwedgey)vee(xwedgez)vee(ywedgez)
References
5 Modelling Data Structures
5.1 Buffer
5.2 Stack Controller
5.3 Stack
5.4 FIFO Queue Controller
5.5 FIFO Queue
5.6 FIFO Ringqueue
5.7 Grid
5.8 Chess Knight
References
6 Relationship of Reaction Systems and Cause-Effect Structures
References
7 Rough Cause-Effect Structures
References
8 Relationship of C-E Structures to Petri Nets
8.1 Strong Equivalence - Elementary Case
8.2 Direct Conversions
8.3 Weak Equivalence
8.4 Procedure of Conversion of Elementary Petri Nets …
8.5 Strong Equivalence - Extended Case
8.6 Direct Conversions
8.7 Remarks on Weak Equivalence and Conversion of PTI Nets into Extended C-E Structures
8.8 Remarks on Another Version of PTI Nets and Their Relation to C-E Structures
References
9 Time in Cause-Effect Structures
9.1 Minimal Time Model for Elementary C-E Structures
9.1.1 Local Minimal Time
9.1.2 Global Minimal Time
9.2 Examples of Real Applications Inspired by Music Scores
9.2.1 Modelling Chords by Elementary C-E Structures
9.2.2 Modelling Sound Duration by Elementary C-E Structures; Repetition of Bars
9.3 Maximal Time Model for Elementary C-E Structures
9.4 Minimal Time Model for Extended C-E Structures
9.4.1 Example of Modelling Chords by Extended C-E Structures
References
10 Examples from Several Fields
10.1 Road Traffic
10.1.1 Roundabout
10.1.2 Bridge
10.1.3 Crossroad
10.1.4 Road Grid
10.2 Other Systems of Moving Objects
10.2.1 Lifts (Elevators)
10.2.2 Boatman—A Coordination Problem
10.3 Some Problems of Concurrency
10.3.1 Producers and Consumers
10.3.2 Deadlock-Free Dining Philosophers
10.3.3 Cigarette Smokers
10.3.4 Mutual Exclusion in Multiprocessors and Multicomputers
10.4 Problems with Simultaneity
10.4.1 Volley—Enforcement of Simultaneous Actions
10.4.2 Synchronous ``handshake'' Communication
10.4.3 More Concrete Example of Handshake Communication
10.5 Dispersal of Signals
10.5.1 Neurons
10.5.2 Balancer
References
Appendix Bibliographies
Index
