The Boolean functions may be iterated either asynchronously, when their coordinates are computed independently of each other, or synchronously, when their coordinates are computed at the same time. In Boolean Systems: Topics in Asynchronicity, a book addressed to mathematicians and computer scientists interested in Boolean systems and their use in modelling, author Serban E. Vlad presents a consistent and original mathematical theory of the discrete-time Boolean asynchronous systems. The purpose of the book is to set forth the concepts of such a theory, resulting from the synchronous Boolean system theory and mostly from the synchronous real system theory, by analogy, and to indicate the way in which known synchronous deterministic concepts generate new asynchronous nondeterministic concepts. The reader will be introduced to the dependence on the initial conditions, periodicity, path-connectedness, topological transitivity, and chaos. A property of major importance is invariance, which is present in five versions. In relation to it, the reader will study the maximal invariant subsets, the minimal invariant supersets, the minimal invariant subsets, connectedness, separation, the basins of attraction, and attractors. The stability of the systems and their time-reversal symmetry end the topics that refer to the systems without input. The rest of the book is concerned with input systems. The most consistent chapters of this part of the book refer to the fundamental operating mode and to the combinational systems (systems without feedback). The chapter Wires, Gates, and Flip-Flops presents a variety of applications. The first appendix addresses the issue of continuous time, and the second one sketches the important theory of Daizhan Cheng, which is put in relation to asynchronicity. The third appendix is a bridge between asynchronicity and the symbolic dynamics of Douglas Lind and Brian Marcus.
Author(s): Serban E. Vlad
Publisher: Academic Press
Year: 2023
Language: English
Pages: 437
City: London
Contents
Preface
1 Boolean functions
1.1 The binary Boole algebra
1.2 Affine spaces defined by two points
1.3 Boolean functions
1.4 Duality
1.5 Iterates
1.6 Cartesian product of functions
1.7 Successors and predecessors
1.8 Functions that are compatible with the affine structure of Bn
1.9 The Hamming distance. Lipschitz functions
2 Morphisms of generator functions
2.1 Definition
2.2 Examples of morphisms
2.3 Composition
2.4 Isomorphisms
2.5 Synonymous functions
2.6 Symmetry relative to translations
2.7 Morphisms vs. duality
2.8 Morphisms vs. iterates
2.9 Morphisms vs. Cartesian product of functions
2.10 Morphisms vs. successors and predecessors
2.11 Morphisms vs. fixed points
3 State portraits
3.1 Preliminaries
3.2 State portraits
3.3 State portraits vs. generator functions
3.4 Examples
3.5 State subportrait
3.6 Isomorphisms. Duality
3.7 Indegree, outdegree, balanced state portraits
3.8 Path, path-connectedness
3.9 Hamiltonian path, Eulerian path
4 Signals
4.1 Definition
4.2 Initial value and final value, initial time and final time
4.3 Duality
4.4 Monotonicity
4.5 Orbit, orbital equivalence
4.6 Omega-limit set, omega-limit equivalence
4.7 The forgetful function
4.8 The image of a signal via a function
4.9 Periodicity
5 Computation functions. Progressiveness
5.1 Main definitions
5.2 Morphisms of progressive computation functions
5.3 Special cases of progressive computation functions
6 Flows and equations of evolution
6.1 Flows
6.2 Reachability
6.3 Examples
6.4 Consistency, causality and composition
6.5 Equations of evolution
6.6 Flows with constant generator functions
7 Systems
7.1 Several equivalent perspectives
7.2 Definition
7.3 Subsystem
7.4 Cartesian product
8 Morphisms of flows
8.1 Definition
8.2 Induced morphisms
8.3 Morphisms of generator functions vs. morphisms of flows
8.4 Composition
8.5 Isomorphisms
8.6 Symmetry relative to translations
8.7 Morphisms compatible with the subsystems
8.8 Morphisms vs. duality
8.9 Morphisms vs. orbits and omega-limit sets
8.10 Morphisms vs. Cartesian products
8.11 Morphisms vs. successors and predecessors
8.12 Morphisms vs. limits
8.13 Morphisms vs. orbital and omega-limit equivalence
8.14 Pseudo-morphisms
9 Nullclines
9.1 Definition
9.2 Examples
9.3 Properties
9.4 Special case: NCi=Bn
10 Fixed points
10.1 Definition
10.2 Fixed points vs. final values. Rest position
10.3 Morphisms vs. fixed points
11 Sources, isolated fixed points, transient points, sinks
11.1 Definition
11.2 Morphisms
11.3 Other properties
12 Sets of reachable states
12.1 Convergent sequences of sets
12.2 Sets of reachable states
12.3 Example
12.4 Isomorphisms
13 Dependence on the initial conditions
13.1 Definition
13.2 Examples
13.3 Subsystem
13.4 Cartesian product
13.5 Isomorphisms
13.6 Versions of dependence on the initial conditions
14 Periodicity
14.1 Eventual periodicity and double eventual periodicity
14.2 Main theorems
14.3 Morphisms vs. periodicity
14.4 Other definitions of periodicity
15 Path-connectedness and topological transitivity
15.1 Path-connectedness
15.2 Topological transitivity
15.3 Examples
15.4 Some properties
15.5 Morphisms
15.6 Cartesian products
15.7 Path-connected components
16 Chaos
16.1 Definition
16.2 Examples
16.3 Morphisms
17 Nonwandering points and Poisson stability
17.1 Nonwandering points
17.2 Poisson stability
17.3 Properties
17.4 Morphisms
18 Invariance
18.1 Definition
18.2 Examples
18.3 Invariant subset
18.4 Properties
18.5 Morphisms
18.6 Symmetry relative to translations
18.7 Subsystems
18.8 Cartesian products
18.9 Invariance and path-connectedness vs. topological transitivity
18.10 A Lyapunov-Lagrange type invariance theorem
18.11 Other possibilities of defining invariance
19 Relatively isolated sets, isolated set
19.1 Definition
19.2 Examples
19.3 Properties
19.4 When the orbits included in invariant sets are nullclines
19.5 Isomorphisms
19.6 Subsystem
20 Maximal invariant subset
20.1 Definition
20.2 Examples
20.3 Main properties
20.4 Maximality vs. nullclines
20.5 Isomorphisms
20.6 Subsystems
20.7 Cartesian products
21 Minimal invariant superset
21.1 Definition
21.2 Examples
21.3 Properties
21.4 Minimality vs. nullclines
21.5 Isomorphisms
21.6 Subsystems
21.7 Cartesian products
22 Minimal invariant subset
22.1 Definition
22.2 Examples
22.3 Properties
22.4 Minimality vs. nullclines
22.5 Isomorphisms
22.6 Cartesian products
23 Connectedness and separation
23.1 Connectedness
23.2 Separation
23.3 Examples
23.4 Properties
23.5 Connectedness vs. topological transitivity
23.6 Connectedness vs. path-connectedness
23.7 Connected components
23.8 Isomorphisms
24 Basins of attraction
24.1 Definition
24.2 Examples
24.3 Properties
24.4 The basin of attraction of the fixed points
24.5 The basin of attraction of the periodic points
24.6 Isomorphisms
25 Basins of attraction of the states
25.1 Definition
25.2 Examples
25.3 Properties
25.4 Isomorphisms
26 Local basins of attraction
26.1 Definition
26.2 Properties
26.3 Isomorphisms
27 Local basins of attraction of the states
27.1 Definition
27.2 Properties
27.3 Isomorphisms
28 Attractors
28.1 Definition
28.2 Examples
28.3 Properties
28.4 Topological transitivity
28.5 Path-connectedness
28.6 Isomorphisms
28.7 Attractors as omega-limit sets
28.8 Cartesian products
28.9 Chaos
28.10 Repellers
28.11 Weak attractors
29 Stability
29.1 Definition
29.2 Examples
29.3 Stability vs. the basins of attraction of the fixed points
29.4 Morphisms
29.5 Subsystems
29.6 (In)dependence on the initial conditions
30 Time-reversal symmetry
30.1 Definition
30.2 Examples
30.3 The uniqueness of the symmetrical function
30.4 Properties
30.5 Morphisms vs. time-reversal symmetry
30.6 Cartesian product
31 Generator functions with one parameter
31.1 Generator functions with one parameter
31.2 Iterates
31.3 Cartesian product of functions
31.4 Successors and predecessors
31.5 State portrait families
31.6 Bifurcations
31.7 Morphisms
32 Input flows and equations of evolution
32.1 Input flows
32.2 Causality and composition
32.3 Equations of evolution
32.4 Morphisms
33 Input systems
33.1 Several equivalent perspectives
33.2 Definition
33.3 Subsystem
33.4 State space decomposition
33.5 Cartesian product
33.6 Autonomy
34 The fundamental (operating) mode
34.1 An introductory remark
34.2 Looking for common sense requests
34.3 The fundamental (operating) mode
35 Combinational systems with one level
35.1 Definition
35.2 Examples
35.3 Stability
35.4 Cartesian product
35.5 Predecessors and successors
35.6 Isomorphisms
35.7 Symmetry relative to translations
35.8 Invariance
35.9 Subsystem
36 Combinational systems
36.1 Definition
36.2 Levels
36.3 Example
36.4 The input-output function. Stability
36.5 Hazards
36.6 Cartesian product
36.7 Predecessors and successors
36.8 Isomorphisms
36.9 Symmetry relative to translations
36.10 Invariance
36.11 Basins of attraction, attractors
36.12 Subsystem
36.13 The fundamental operating mode
37 Wires, gates, and flip flops
37.1 Circuits
37.2 The wire
37.3 The delay element
37.3.1 The delay element
37.3.2 Circuit with a delay element and feedback
37.3.3 Circuit with two delay elements
37.3.4 Circuit with two delay elements and feedback
37.4 Gates
37.4.1 Gates
37.4.2 The NOT gate
37.4.3 Circuit with a Not gate and feedback
37.4.4 Circuit with two NOT gates
37.4.5 Circuit with two NOT gates and feedback
37.4.6 Circuit with a delay element and a NOT gate and feedback
37.4.7 The NAND gate
37.5 The SR latch
37.6 The gated SR flip flop
37.7 The D type flip flop
A Continuous time
A.1 Limits, signals, and computation functions
A.2 Systems, several perspectives
B Theory of Cheng
B.1 Semi-tensor product
B.2 Replacement of B with D
B.3 Structure matrix
B.4 Equations of evolution
B.5 Example
C Symbolic dynamics
C.1 Blocks
C.2 Shift spaces
C.3 Languages
C.4 The timeless model of computation
C.5 The unbounded delay model of computation
C.6 The bounded delay model of computation
Notations
Bibliography
Index
