This book introduces the concept of Event Mining for building explanatory models from analyses of correlated data. Such a model may be used as the basis for predictions and corrective actions. The idea is to create, via an iterative process, a model that explains causal relationships in the form of structural and temporal patterns in the data. The first phase is the data-driven process of hypothesis formation, requiring the analysis of large amounts of data to find strong candidate hypotheses. The second phase is hypothesis testing, wherein a domain expert’s knowledge and judgment is used to test and modify the candidate hypotheses. The book is intended as a primer on Event Mining for data-enthusiasts and information professionals interested in employing these event-based data analysis techniques in diverse applications. The reader is introduced to frameworks for temporal knowledge representation and reasoning, as well as temporal data mining and pattern discovery. Also discussed are the design principles of event mining systems. The approach is reified by the presentation of an event mining system called EventMiner, a computational framework for building explanatory models. The book contains case studies of using EventMiner in asthma risk management and an architecture for the objective self. The text can be used by researchers interested in harnessing the value of heterogeneous big data for designing explanatory event-based models in diverse application areas such as healthcare, biological data analytics, predictive maintenance of systems, computer networks, and business intelligence.

This book introduces the concept of Event Mining for building explanatory models from analyses of correlated data. Such a model may be used as the basis for predictions and corrective actions. The idea is to create, via an iterative process, a model that explains causal relationships in the form of structural and temporal patterns in the data. The first phase is the data-driven process of hypothesis formation, requiring the analysis of large amounts of data to find strong candidate hypotheses. The second phase is hypothesis testing, wherein a domain expert's knowledge and judgment is used to test and modify the candidate hypotheses. The book is intended as a primer on Event Mining for data-enthusiasts and information professionals interested in employing these event-based data analysis techniques in diverse applications. The reader is introduced to frameworks for temporal knowledge representation and reasoning, as well as temporal data mining and pattern discovery. Also discussed are the design principles of event mining systems. The approach is reified by the presentation of an event mining system called EventMiner, a computational framework for building explanatory models. The book contains case studies of using EventMiner in asthma risk management and an architecture for the objective self. The text can be used by researchers interested in harnessing the value of heterogeneous big data for designing explanatory event-based models in diverse application areas such as healthcare, biological data analytics, predictive maintenance of systems, computer networks, and business intelligence.

Edsger Wybe Dijkstra (1930–2002) was one of the most influential researchers in the history of computer science, making fundamental contributions to both the theory and practice of computing. Early in his career, he proposed the single-source shortest path algorithm, now commonly referred to as Dijkstra’s algorithm. He wrote (with Jaap Zonneveld) the first ALGOL 60 compiler, and designed and implemented with his colleagues the influential THE operating system. Dijkstra invented the field of concurrent algorithms, with concepts such as mutual exclusion, deadlock detection, and synchronization. A prolific writer and forceful proponent of the concept of structured programming, he convincingly argued against the use of the Go To statement. In 1972 he was awarded the ACM Turing Award for “fundamental contributions to programming as a high, intellectual challenge; for eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness; for illuminating perception of problems at the foundations of program design.” Subsequently he invented the concept of self-stabilization relevant to fault-tolerant computing. He also devised an elegant language for nondeterministic programming and its weakest precondition semantics, featured in his influential 1976 book A Discipline of Programming in which he advocated the development of programs in concert with their correctness proofs. In the later stages of his life, he devoted much attention to the development and presentation of mathematical proofs, providing further support to his long-held view that the programming process should be viewed as a mathematical activity. In this unique new book, 31 computer scientists, including five recipients of the Turing Award, present and discuss Dijkstra’s numerous contributions to computing science and assess their impact. Several authors knew Dijkstra as a friend, teacher, lecturer, or colleague. Their biographical essays and tributes provide a fascinating multi-author picture of Dijkstra, from the early days of his career up to the end of his life.

Software history has a deep impact on current software designers, computer scientists, and technologists. System constraints imposed in the past and the designs that responded to them are often unknown or poorly understood by students and practitioners, yet modern software systems often include “old” software and “historical” programming techniques. This work looks at software history through specific software areas to develop student-consumable practices, design principles, lessons learned, and trends useful in current and future software design. It also exposes key areas that are widely used in modern software, yet infrequently taught in computing programs. Written as a textbook, this book uses specific cases from the past and present to explore the impact of software trends and techniques. Building on concepts from the history of science and technology, software history examines such areas as fundamentals, operating systems, programming languages, programming environments, networking, and databases. These topics are covered from their earliest beginnings to their modern variants. There are focused case studies on UNIX, APL, SAGE, GNU Emacs, Autoflow, internet protocols, System R, and others. Extensive problems and suggested projects enable readers to deeply delve into the history of software in areas that interest them most.

This book discusses two questions in Complexity Theory: the Monotonicity Testing problem and the 2-to-2 Games Conjecture. Monotonicity testing is a problem from the field of property testing, first considered by Goldreich et al. in 2000. The input of the algorithm is a function, and the goal is to design a tester that makes as few queries to the function as possible, accepts monotone functions and rejects far-from monotone functions with a probability close to 1. The first result of this book is an essentially optimal algorithm for this problem. The analysis of the algorithm heavily relies on a novel, directed, and robust analogue of a Boolean isoperimetric inequality of Talagrand from 1993. The probabilistically checkable proofs (PCP) theorem is one of the cornerstones of modern theoretical computer science. One area in which PCPs are essential is the area of hardness of approximation. Therein, the goal is to prove that some optimization problems are hard to solve, even approximately. Many hardness of approximation results were proved using the PCP theorem; however, for some problems optimal results were not obtained. This book touches on some of these problems, and in particular the 2-to-2 games problem and the vertex cover problem. The second result of this book is a proof of the 2-to-2 games conjecture (with imperfect completeness), which implies new hardness of approximation results for problems such as vertex cover and independent set. It also serves as strong evidence towards the unique games conjecture, a notorious related open problem in theoretical computer science. At the core of the proof is a characterization of small sets of vertices in Grassmann graphs whose edge expansion is bounded away from 1.

This book investigates multiple facets of the emerging discipline of Tangible, Embodied, and Embedded Interaction (TEI). This is a story of atoms and bits. We explore the interweaving of the physical and digital, toward understanding some of their wildly varying hybrid forms and behaviors. Spanning conceptual, philosophical, cognitive, design, and technical aspects of interaction, this book charts both history and aspirations for the future of TEI. We examine and celebrate diverse trailblazing works, and provide wide-ranging conceptual and pragmatic tools toward weaving the animating fires of computation and technology into evocative tangible forms. We also chart a path forward for TEI engagement with broader societal and sustainability challenges that will profoundly (re)shape our children’s and grandchildren’s futures. We invite you all to join this quest.

Professor Stephen A. Cook is a pioneer of the theory of computational complexity. His work on NP-completeness and the P vs. NP problem remains a central focus of this field. Cook won the 1982 Turing Award for “his advancement of our understanding of the complexity of computation in a significant and profound way.” This volume includes a selection of seminal papers embodying the work that led to this award, exemplifying Cook’s synthesis of ideas and techniques from logic and the theory of computation including NP-completeness, proof complexity, bounded arithmetic, and parallel and space-bounded computation. These papers are accompanied by contributed articles by leading researchers in these areas, which convey to a general reader the importance of Cook’s ideas and their enduring impact on the research community. The book also contains biographical material, Cook’s Turing Award lecture, and an interview. Together these provide a portrait of Cook as a recognized leader and innovator in mathematics and computer science, as well as a gentle mentor and colleague.