Boolean Functions: Topics in Asynchronicity

### English

The essential guide showing how the unbounded delay model of computation of the Boolean functions may be used in the analysis of the Boolean networks

Boolean Functions: Topics in Asynchronicity contains the most current research in several issues of asynchronous Boolean systems. In this framework, asynchronicity means that the functions which model the digital circuits from electronics iterate their coordinates independently on each other and the author—a noted expert in the field—includes a formal mathematical description of these systems.

Filled with helpful definitions and illustrative examples, the book covers a range of topics such as morphisms, antimorphisms, invariant sets, path connected sets, attractors. Further, it studies race freedom, called here the technical condition of proper operation, together with some of its generalized and strengthened versions, and also time reversal, borrowed from physics and also from dynamical systems, together with the symmetry that it generates.

This book:

• Presents up-to-date research in the field of Boolean networks,
• Includes the information needed to understand the construction of an asynchronous Boolean systems theory and contains proofs,
• Employs use of the language of algebraic topology and homological algebra.

Written formathematicians and computer scientists interested in the theory and applications of Boolean functions, dynamical systems, and circuits, Boolean Functions: Topics in Asynchronicity is an authoritative guide indicating a way of using the unbounded delay model of computation of the Boolean functions in the analysis of the Boolean networks

### English

SERBAN E. VLAD is an Analyst Programmer at Oradea City Hall, Romania. He is a member of the Romanian and the German societies of industrial and applied mathematics, ROMAI and GAMM. He is the author of many papers and several books and book chapters.

### English

Preface xi

1 Boolean Functions 1

1.1 The Binary Boole Algebra 2

1.2 Definition of the Boolean Functions. Examples. Duality 4

1.3 Iterates 6

1.4 State Portraits. Stable and Unstable Coordinates 11

1.5 Modeling the Asynchronous Circuits 14

1.6 Sequences of Sets 14

1.7 Predecessors and Successors 15

1.8 Source, Isolated Fixed Point, Transient Point, Sink 18

1.9 Translations 19

2 Affine Spaces Defined by Two Points 21

2.1 Definition 21

2.2 Properties 23

2.3 Functions that Are Compatible with the Affine Structure of Bn 25

2.4 The Hamming Distance. Lipschitz Functions 28

2.5 Affine Spaces of Successors 31

3 Morphisms 35

3.1 Definition 35

3.2 Examples 36

3.3 The Composition 38

3.4 A Fixed Point Property 39

3.5 Symmetrical Functions Relative to Translations. Examples 39

3.6 The Dual Functions Revisited 41

3.7 Morphisms vs. Predecessors and Successors 42

4 Antimorphisms 45

4.1 Definition 45

4.2 Examples 46

4.3 The Composition 48

4.4 A Fixed Point Property 51

4.5 Antisymmetrical Functions Relative to Translations. Examples 51

4.6 Antimorphisms vs Predecessors and Successors 52

5 Invariant Sets 55

5.1 Definition 55

5.2 Examples 57

5.3 Properties 58

5.4 Homomorphic Functions vs Invariant Sets 60

5.5 Special Case of Homomorphic Functions vs Invariant Sets 62

5.6 Symmetry Relative to Translations vs Invariant Sets 63

5.7 Antihomomorphic Functions vs Invariant Sets 64

5.8 Special Case of Antihomomorphic Functions vs Invariant Sets 65

5.9 Antisymmetry Relative to Translations vs Invariant Sets 66

5.10 Relatively Isolated Sets, Isolated Set 67

5.11 Isomorphic Functions vs Relatively Isolated Sets 68

5.12 Antiisomorphic Functions vs Relatively Isolated Sets 69

6 Invariant Subsets 71

6.1 Definition 71

6.2 Examples 72

6.3 Maximal Invariant Subset 72

6.4 Minimal Invariant Subset 74

6.5 Connected Components 76

6.6 Disconnected Set 77

7 Path Connected Set 81

7.1 Definition 81

7.2 Examples 82

7.3 Properties 84

7.4 Path Connected Components 84

7.5 Morphisms vs Path Connectedness 85

7.6 Antimorphisms vs Path Connectedness 85

8 Attractors 87

8.1 Preliminaries 88

8.2 Definition 89

8.3 Properties 90

8.4 Morphisms vs Attractors 94

8.5 Antimorphisms vs Attractors 95

9 The Technical Condition of Proper Operation 97

9.1 Definition 97

9.2 Examples 100

9.3 Iterates 101

9.4 The Sets of Predecessors and Successors 101

9.5 Source, Isolated Fixed Point, Transient Point, Sink 103

9.6 Isomorphisms vs tcpo 104

9.7 Antiisomorphisms vs tcpo 105

10 The Strong Technical Condition of Proper Operation 107

10.1 Definition 107

10.2 Examples 109

10.3 Iterates 110

10.4 The Sets of Predecessors and Successors 110

10.5 Source, Isolated Fixed Point, Transient Point, Sink 111

10.6 Isomorphisms vs Strong tcpo 111

10.7 Antiisomorphisms vs Strong tcpo 112

11 The Generalized Technical Condition of Proper Operation 115

11.1 Definition 115

11.2 Examples 119

11.3 Iterates 120

11.4 The Sets of Predecessors and Successors 121

11.5 Source, Isolated Fixed Point, Transient Point, Sink 125

11.6 Isomorphisms vs the Generalized tcpo 126

11.7 Antiisomorphisms vs the Generalized tcpo 128

11.8 Other Properties 129

12 The Strong Generalized Technical Condition of Proper Operation 131

12.1 Definition 131

12.2 Examples 135

12.3 Iterates 136

12.4 Source, Isolated Fixed Point, Transient Point, Sink 137

12.5 Asynchronous and Synchronous Transient Points 141

12.6 The Sets of Predecessors and Successors 141

12.7 Isomorphisms vs the Strong Generalized tcpo 144

12.8 Antiisomorphisms vs the Strong Generalized tcpo 146

13 Time-Reversal Symmetry 147

13.1 Definition 148

13.2 Examples 150

13.3 The Uniqueness of the Symmetrical Function 151

13.4 Isomorphisms and Antiisomorphisms vs Time-Reversal Symmetry 151

13.5 Other Properties 152

14 Time-Reversal Symmetry vs tcpo 155

14.1 Time-Reversal Symmetry vs tcpo 155

14.2 Time-Reversal Symmetry vs the Strong tcpo 156

14.3 Examples 159

15 Time-Reversal Symmetry vs the Generalized tcpo 163

15.1 Time-Reversal Symmetry vs the Generalized tcpo 163

15.2 Examples 168

Appendix A The Category As 171

Appendix B Notations 175

Bibliography 177

Index 181