The amount of digital systems supporting our daily life is increasing continuously. Improved technical facilities for their production have led to growing challenges for engineers and scientists working in the Boolean domain. A Boolean variable can only carry two different Boolean values: FALSE or TRUE (0 or 1), and has the best interference resistance in technical systems. However, a Boolean function exponentially depends on the number of its variables. This exponential complexity is the reason for major problems in the process of design and realization of circuits. According to Moore’s Law, the complexity of digital systems approximately doubles every 18 months. This requires comprehensive knowledge and techniques to solve very complex Boolean problems. This volume represents the third book in a series that provides further insights into the Boolean domain. Part 1 explores powerful models, methods and techniques which improve the efficiency in solving Boolean problems of extreme complexity. The universality of Boolean equations as a model to solve Non-deterministic Polynomial-time (NP) hard problems, as well as special properties of index generation functions, spectral techniques, or relational approaches, is discussed here. Both hardware devices, such as Field Programmable Gate Arrays (FPGAs) or Graphics Processing Units (GPUs), and optimized algorithms realized in software contribute to the acceleration of Boolean calculations. Part 2 contributes to the synthesis and visualization of digital circuits, and provides interesting new solutions for several types of circuits. A comprehensive collection of benchmarks supports the evolution of both existing and new synthesis approaches. The continuous reduction of the size of the transistors increases the challenges with regard to the reliability of the circuits. Part 3 describes several new approaches for the synthesis of reversible circuits. These approaches, as well as a classification of reversible functions, extend the basis of future quantum computers.

This book gathers together the results of research on the Boolean domain related to important real-life applications that will support the reader in solving their scientific and practical tasks. It highlights that ongoing digitalization leads to increasing amounts of complex applications, the digits of which are usually encoded by Boolean variables due to their simplicity as only two values are used. However, as shown here, an exponentially growing number of vectors of Boolean variables can negate this simplicity, which leads to challenges in advancing progress in the Boolean domain and supporting a wide range of applications.

This book describes recent findings in the domain of Boolean logic and Boolean algebra, covering application domains in circuit and system design, but also basic research in mathematics and theoretical computer science. Content includes invited chapters and a selection of the best papers presented at the 15th annual International Workshop on Boolean Problems.

The Internet of Things is a great new challenge for the development of digital systems. In addition to the increasing number of classical unconnected digital systems, more people are regularly using new electronic devices and software that are controllable and usable by means of the internet. All such systems utilize the elementariness of Boolean values. A Boolean variable can carry only two different Boolean values: FALSE or TRUE (0 or 1), and has the best interference resistance in technical systems. However, a Boolean function exponentially depends on the number of its variables. This exponential complexity is the cause of major problems in the process of design and realization of circuits. According to Moore’s Law, the complexity of digital systems approximately doubles every 18 months. This requires comprehensive knowledge and techniques to solve complex Boolean problems. This book summarizes both new problems and solutions in the Boolean domain in solving such issues. Part 1 describes powerful new approaches in solving exceptionally complex Boolean problems. Efficient methods contribute to solving problems of extreme complexity. New algorithms and programs utilize the huge number of computing cores of the Graphical Processing Unit and improve the performance of calculations by several orders of magnitude. Part 2 represents several applications of digital systems. Due to the crucial role of the internet, both solutions and open problems regarding the security of these systems are discussed. The exploration of certain properties of such systems leads to a number of efficient solutions, which can be reused in a wide field of applications. Part 3 discusses the scientific basis of future circuit technologies, investigating the need for completely new design methods for the atomic level of quantum computers. This part also concerns itself with reversible circuits as the basis for quantum circuits and specifies important issues regarding future improvements.

This open access State-of-the-Art Survey presents the main recent scientific outcomes in the area of reversible computation, focusing on those that have emerged during COST Action IC1405 "Reversible Computation - Extending Horizons of Computing", a European research network that operated from May 2015 to April 2019. Reversible computation is a new paradigm that extends the traditional forwards-only mode of computation with the ability to execute in reverse, so that computation can run backwards as easily and naturally as forwards. It aims to deliver novel computing devices and software, and to enhance existing systems by equipping them with reversibility. There are many potential applications of reversible computation, including languages and software tools for reliable and recovery-oriented distributed systems and revolutionary reversible logic gates and circuits, but they can only be realized and have lasting effect if conceptual and firm theoretical foundations are established first.

The greatly expanded and updated 3rd edition of this textbook offers the reader a comprehensive introduction to the concepts of logic functions and equations and their applications across computer science and engineering. The authors’ approach emphasizes a thorough understanding of the fundamental principles as well as numerical and computer-based solution methods. The book provides insight into applications across propositional logic, binary arithmetic, coding, cryptography, complexity, logic design, and artificial intelligence. Updated throughout, some major additions for the 3rd edition include: a new chapter about the concepts contributing to the power of XBOOLE; a new chapter that introduces into the application of the XBOOLE-Monitor XBM 2; many tasks that support the readers in amplifying the learned content at the end of the chapters; solutions of a large subset of these tasks to confirm learning success; challenging tasks that need the power of the XBOOLE software for their solution. The XBOOLE-monitor XBM 2 software is used to solve the exercises; in this way the time-consuming and error-prone manipulation on the bit level is moved to an ordinary PC, more realistic tasks can be solved, and the challenges of thinking about algorithms leads to a higher level of education.

Index generation functions are binary-input integer valued functions. They represent functions of content addressable memories (CAMs). Applications include: IP address tables; terminal controllers; URL lists; computer virus scanning circuits; memory patch circuits; list of English words; code converters; and pattern matching circuits. This book shows memory-based realization of index generation functions. It shows: 1. methods to implement index generation functions by look-up table (LUT) cascades and index generation units (IGU), 2. methods to reduce the number of variables using linear transformations, and 3. methods to estimate the sizes of memories, with many illustrations, tables, examples, exercises, and their solutions.

We are invited to deal with mathematical activity in a sys tematic way [ ... ] one does expect and look for pleasant surprises in this requirement of a novel combination of psy chology, logic, mathematics and technology. Hao Wang, 1970, quoted from(Wang, 1970). The field of mathematics has been a key application area for automated theorem proving from the start, in fact the very first automatically found the orem was that the sum of two even numbers is even (Davis, 1983). The field of automated deduction has witnessed considerable progress and in the last decade, automated deduction methods have made their way into many areas of research and product development in computer science. For instance, deduction systems are increasingly used in software and hardware verification to ensure the correctness of computer hardware and computer programs with respect to a given specification. Logic programming, while still falling somewhat short of its expectations, is now widely used, deduc tive databases are well-developed and logic-based description and analysis of hard-and software is commonplace today.

The expanded and updated 2nd edition of this classic text offers the reader a comprehensive introduction to the concepts of logic functions and equations and their applications across computer science. The approach emphasizes a thorough understanding of the fundamental principles as well as numerical and computer-based solution methods. Updated throughout, some major additions for the 2nd edition include: - an expanded introductory section on logic equations; - a new chapter on sets, lattices, and classes of logic functions; - a new chapter about SAT-problems; - a new chapter about methods to solve extremely complex problems; and - an expanded section with new decomposition methods utilizing the Boolean Differential Calculus extended to lattices of logic functions. The book provides insight into applications across binary arithmetic, coding, complexity, logic design, programming, computer architecture, and artificial intelligence. Based on the extensive teaching experience of the authors, Logic Functions and Equations is highly recommended for a one- or two-semester course in computer science and related programs. It provides straightforward high-level access to these methods and enables sophisticated applications, elegantly bridging the gap between mathematics and the theoretical foundations of computer science.

This book is Open Access under a CC BY licence. The LNCS 10805 and 10806 proceedings set constitutes the proceedings of the 24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2018, which took place in Thessaloniki, Greece, in April 2018, held as part of the European Joint Conference on Theory and Practice of Software, ETAPS 2018. The total of 43 full and 11 short papers presented in these volumes was carefully reviewed and selected from 154submissions. The papers are organized in topical sections as follows: Part I: theorem proving; SAT and SMT I; deductive verification; software verification and optimization; model checking; and machine learning. Part II: concurrent and distributed systems; SAT and SMT II; security and reactive systems; static and dynamic program analysis; hybrid and stochastic systems; temporal logic and mu-calculus; 7th Competition on Software Verification – SV-COMP.