114,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
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.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 183
Veröffentlichungsjahr: 2019
Ähnliche
Table of Contents
Cover
Preface
1 Boolean Functions
1.1 The Binary Boole Algebra
1.2 Definition of the Boolean Functions. Examples. Duality
1.3 Iterates
1.4 State Portraits. Stable and Unstable Coordinates
1.5 Modeling the Asynchronous Circuits
1.6 Sequences of Sets
1.7 Predecessors and Successors
1.8 Source, Isolated Fixed Point, Transient Point, Sink
1.9 Translations
2 Affine Spaces Defined by Two Points
2.1 Definition
2.2 Properties
2.3 Functions that Are Compatible with the Affine Structure of
2.4 The Hamming Distance. Lipschitz Functions
2.5 Affine Spaces of Successors
3 Morphisms
3.1 Definition
3.2 Examples
3.3 The Composition
3.4 A Fixed Point Property
3.5 Symmetrical Functions Relative to Translations. Examples
3.6 The Dual Functions Revisited
3.7 Morphisms vs. Predecessors and Successors
4 Antimorphisms
4.1 Definition
4.2 Examples
4.3 The Composition
4.4 A Fixed Point Property
4.5 Antisymmetrical Functions Relative to Translations. Examples
4.6 Antimorphisms vs Predecessors and Successors
5 Invariant Sets
5.1 Definition
5.2 Examples
5.3 Properties
5.4 Homomorphic Functions vs Invariant Sets
5.5 Special Case of Homomorphic Functions vs Invariant Sets
5.6 Symmetry Relative to Translations vs Invariant Sets
5.7 Antihomomorphic Functions vs Invariant Sets
5.8 Special Case of Antihomomorphic Functions vs Invariant Sets
5.9 Antisymmetry Relative to Translations vs Invariant Sets
5.10 Relatively Isolated Sets, Isolated Set
5.11 Isomorphic Functions vs Relatively Isolated Sets
5.12 Antiisomorphic Functions vs Relatively Isolated Sets
6 Invariant Subsets
6.1 Definition
6.2 Examples
6.3 Maximal Invariant Subset
6.4 Minimal Invariant Subset
6.5 Connected Components
6.6 Disconnected Set
7 Path Connected Set
7.1 Definition
7.2 Examples
7.3 Properties
7.4 Path Connected Components
7.5 Morphisms vs Path Connectedness
7.6 Antimorphisms vs Path Connectedness
8 Attractors
8.1 Preliminaries
8.2 Definition
8.3 Properties
8.4 Morphisms vs Attractors
8.5 Antimorphisms vs Attractors
9 The Technical Condition of Proper Operation
9.1 Definition
9.2 Examples
9.3 Iterates
9.4 The Sets of Predecessors and Successors
9.5 Source, Isolated Fixed Point, Transient Point, Sink
9.6 Isomorphisms vs tcpo
9.7 Antiisomorphisms vs tcpo
10 The Strong Technical Condition of Proper Operation
10.1 Definition
10.2 Examples
10.3 Iterates
10.4 The Sets of Predecessors and Successors
10.5 Source, Isolated Fixed Point, Transient Point, Sink
10.6 Isomorphisms vs Strong tcpo
10.7 Antiisomorphisms vs Strong tcpo
11 The Generalized Technical Condition of Proper Operation
11.1 Definition
11.2 Examples
11.3 Iterates
11.4 The Sets of Predecessors and Successors
11.5 Source, Isolated Fixed Point, Transient Point, Sink
11.6 Isomorphisms vs the Generalized tcpo
11.7 Antiisomorphisms vs the Generalized tcpo
11.8 Other Properties
12 The Strong Generalized Technical Condition of Proper Operation
12.1 Definition
12.2 Examples
12.3 Iterates
12.4 Source, Isolated Fixed Point, Transient Point, Sink
12.5 Asynchronous and Synchronous Transient Points
12.6 The Sets of Predecessors and Successors
12.7 Isomorphisms vs the Strong Generalized tcpo
12.8 Antiisomorphisms vs the Strong Generalized tcpo
13 Time‐Reversal Symmetry
13.1 Definition
13.2 Examples
13.3 The Uniqueness of the Symmetrical Function
13.4 Isomorphisms and Antiisomorphisms vs Time‐Reversal Symmetry
13.5 Other Properties
14 Time‐Reversal Symmetry vs tcpo
14.1 Time‐Reversal Symmetry vs tcpo
14.2 Time‐Reversal Symmetry vs the Strong tcpo
14.3 Examples
15 Time‐Reversal Symmetry vs the Generalized tcpo
15.1 Time‐Reversal Symmetry vs the Generalized tcpo
15.2 Examples
Appendix A: The Category As
Appendix B: Notations
Bibliography
Index
End User License Agreement
List of Tables
4
Table 1 An example.
List of Illustrations
Chapter 1
Figure 1.1 The state portrait of
.
Figure 1.2 The state portrait of
.
Figure 1.3 The state portrait of
.
Figure 1.4 The state portrait of
.
Figure 1.5 The state portrait of
.
Figure 1.6 Circuit with three logical gates.
Figure 1.7 The state portrait of
.
Figure 1.8 Example of sources, isolated fixed points, transient points, and sin...
Chapter 2
Figure 2.1
contains three fixed points of
and
.
Chapter 3
Figure 3.1 The function
.
Figure 3.2 The function
.
Figure 3.3 The function
.
Figure 3.4 The function
.
Figure 3.5 The function
.
Figure 3.6 The function
.
Chapter 4
Figure 4.1 The function
.
Figure 4.2 Function
which is antiisomorphic with the function
.
Figure 4.3 The function
.
Figure 4.4 The function
.
Chapter 5
Figure 5.1
is (5.1)‐invariant.
Figure 5.2 The sets
are (5.1)‐invariant and (5.2)‐invariant;
are (5.1...
Figure 5.3 The sets
and
are (5.1)‐invariant and (5.2)‐invariant.
Figure 5.4 The function
.
Figure 5.5 The function
.
Chapter 6
Figure 6.1 The sets
and
are the
‐connected components of
.
Figure 6.2 The sets
and
are the ( 6.2 )‐connected components of
.
Chapter 7
Figure 7.1 The nonempty subsets
are path connected.
Figure 7.2 The nonempty subsets
and
are path connected.
Figure 7.3 The nonempty subsets
are path connected.
Figure 7.4 The nonempty subsets
are path connected.
Figure 7.5 The sets
are path connected components of
.
Chapter 8
Figure 8.1 The set
is an attractor.
Chapter 9
Figure 9.1
fulfills tcpo.
Figure 9.2
fulfills tcpo.
Chapter 10
Figure 10.1
fulfills the strong tcpo.
Figure 10.2
fulfills the strong tcpo.
Figure 10.3
fulfills tcpo but it does not fulfill the strong tcpo.
Chapter 11
Figure 11.1
fulfills the generalized tcpo.
Figure 11.2
fulfills the generalized tcpo.
Figure 11.3
fulfills the generalized tcpo.
Figure 11.4 Function
that fulfills the generalized tcpo.
Figure 11.5 Function
that fulfills the generalized tcpo.
Chapter 13
Figure 13.1 The time‐reversal symmetry of two constant functions.
Figure 13.2 The function
.
Figure 13.3 The function
.
Chapter 14
Figure 14.1 Function
that fulfills tcpo; the time‐reversal symmetry of
and...
Figure 14.2 The function
which is the time‐reversed symmetrical of the functi...
Figure 14.3 The function
.
Figure 14.4 The function
.
Figure 14.5
at (a) and
at (b)
Figure 14.6
at (a) and
at (b).
Chapter 15
Figure 15.1
at (a) and
at (b).
Figure 15.2
at (a) and
at (b).
Guide
Cover
Table of Contents
Begin Reading
Pages
iii
xi
xii
xiii
xiv
xv
xvi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Boolean Functions: Topics in Asynchronicity
First Edition
Serban E. Vlad
Oradea, Romania
Copyright
This edition first published 2019
© 2019 John Wiley & Sons, inc
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.
The right of Serban E. Vlad to be identified as the author of this work has been asserted in accordance with law.
Registered Office
John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA
Editorial Office
111 River Street, Hoboken, NJ 07030, USA
For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.
Wiley also publishes its books in a variety of electronic formats and by print‐on‐demand. Some content that appears in standard print versions of this book may not be available in other formats.
Limit of Liability/Disclaimer of Warranty
While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
Library of Congress Cataloging‐in‐Publication Data
Names: Vlad, Serban E., 1959- author.
Title: Boolean functions : topics in asynchronicity / Serban E. Vlad.
Description: First edition. | Hoboken, NJ : John Wiley & Sons, 2018. |
Includes bibliographical references and index. |
Identifiers: LCCN 2018034871 (print) | LCCN 2018057135 (ebook) | ISBN
9781119517498 (Adobe PDF) | ISBN 9781119517511 (ePub) | ISBN 9781119517474
(hardcover) | ISBN 9781119517498 (ePDF)
Subjects: LCSH: Algebra, Boolean.
Classification: LCC QA10.3 (ebook) | LCC QA10.3 .V533 2018 (print) | DDC
511.3/24--dc23
LC record available at https://lccn.loc.gov/2018034871
ISBN 978‐1‐119‐51747‐4 (Hardback)
ISBN 978‐1‐119‐51749‐8 (ePDF)
ISBN 978‐1‐119‐51751‐1 (epub)
Cover Design: Wiley
Cover Image: Courtesy of Serban E. Vlad
Dedication
To Ciupi and Puiu Mic
Preface
In this framework, by asynchronicity we mean that the coordinate functions of a function are computed independently on each other, asynchronously. Synchronicity is that special case of asynchronicity when are computed at the same time, synchronously. It is of special interest to study the iterations of which can be asynchronous or synchronous.
Our project “Topics in asynchronicity” has been thought of having two parts, part I: Boolean functions and part II: Boolean systems. While working we took the decision to split it in two books.
The source of inspiration is represented by the asynchronous circuits from electronics that can be modeled by Boolean functions iterating their coordinates in arbitrary time, independently on each other, i.e. asynchronously. The uncertainties related with the behavior of the circuits and their models are generated by technology and also by temperature variations and voltage supply variations.
In order to understand the dynamics of these systems, we give the example of the function from Table 1, whose state portrait was drawn in Figure 1 (we have adopted the terminology of state portrait, by analogy with the phase portraits of the dynamical systems theory; such drawings might be called in engineering and elsewhere state transition graphs or state transition diagrams).
Table 1 An example.
In Figure 1, the arrows show the increase of time. We have underlined in the tuples these coordinates, called unstable (or excited, or enabled), for which these are the coordinates that are about to switch, but the time instant and the order in which these switches happen are not known. In this model, each present value of the state may be followed by several possible values in the future, giving nondeterminism and also branching time in the future.
Figure 1 Dependence on the order in which are computed.
is an isolated fixed point of (a fixed point is also called equilibrium point, or rest position, or final state), where the system stays indefinitely long; it has no underlined coordinates. Unlike it, is a fixed point that is not isolated, since a transfer to it exists, from
The transition consists in the computation of even if we do not know when it happens, we know that it happens and the system, if it is in surely gets to sometime. And the transitions are similar.
The interesting behavior is in if is computed first, or if are computed simultaneously, the system gets to sometime, with a possible intermediate state; but if is computed first, then the state is reached and, as it is a fixed point of (no coordinate is underlined) the system rests there indefinitely long.
In the previous discussion:
(a) a system is identified with a function in the sense that contains all the information that gives the behavior of the system. This justifies our definitions of the Boolean functions via state portraits and, in fact, this is the motivation situated behind writing this book;
(b) the system that we refer to is Boolean (this vaguely refers at ), universal (the state space is all of ), regular (a generator function exists), asynchronous ( are not computed at the same time, but the fact that these coordinates are computed independently on each other also shows that the structure of the system is variable), nondeterministic ( have unknown durations of computation), autonomous (no input), noninitialized;
(c) the durations of computation of are subject to no restriction (this is the unbounded delay model of computation of the Boolean functions);
(d) time is discrete or continuous.
The topics that are common for the Boolean functions and the Boolean systems include morphisms and antimorphisms, invariant sets, the conditions of proper operation (race‐freedom) and time‐reversal, with the symmetry that it generates.
The concept of isomorphism is easily understood by looking at Figure 2, where the state portrait of a function which is isomorphic with the function from Figure 1 was drawn. To each point from Figure 1, the vector was added modulo 2 coordinatewise and the result expressed by Figure 2 is that the transitions from the first case become transitions translated with in the second case. Note the arrows and the underlined coordinates of the two functions: the behavior is the same. The morphisms present under a more general form this transfer of properties from a function to another one and this is observed by taking a look at Figure 3, representing a function that accepts a morphism from it to both functions, from Figures 1 and 2. The morphism of this example forgets the computations of .
Figure 2 This function is isomorphic with the function from Figure 1.
Figure 3 A morphism exists from this function to the functions from Figure 1 and Figure 2: the computation of is forgotten.
A nonempty set is invariant ( is kept in mind) if, whenever a computation starts in it ends in some point and two types of invariance are situated behind this intuition. We can think, looking at Figure 2, that the fixed points give the invariant sets (where the computation starts in and ends in etc.). But the set is also invariant. From the previous sets, are attractors.
The functions from Figures 1 and 2 suggest the problem of finding sets of Boolean functions where, even if we do not know the time instants and the order in which their coordinates are computed, we know that for any the values are computed sometime, in this order. Thus, the behavior of the (asynchronous) systems that we are looking for reproduces in a certain way the behavior of the (synchronous, usual) dynamical systems in their Boolean version, and this is considered to be “nice”, in a context with many unknown parameters. We get the “proper operation” properties of the Boolean functions/systems. The functions from Figures 1 and 2 do not fulfill such a property, for example in Figure 2 it is not sure that is really computed, since the computation of first produces the transfer of the system from to where it rests indefinitely long. The functions from Figures 3 and 4 fulfill the proper operation property.
Figure 4 Function that accepts time reversal.
Time reversal means, roughly speaking, reversing the arrows of a state portrait. The function from Figure 2 does not accept this, since reversing the arrows that point to to arrows that start from is impossible, but the function from Figure 4 does accept. We have inserted an arrow from
