A basic issue in computer science is the complexity of problems. Computational complexity measures how much time or memory is needed as a function of the input problem size. Descriptive complexity is concerned with problems which may be described in first-order logic. By virtue of the close relationship between logic and relational databses, it turns out that this subject has important applications to databases such as analysing the queries computable in polynomial time, analysing the parallel time needed to compute a query, and the analysis of nondeterministic classes. This book is written as a graduate text and so aims to provide a reasonably self-contained introduction to this subject. The author has provided numerous examples and exercises to further illustrate the ideas presented.
In Think Complexity, you´ll use graphs, cellular automata, and agent-based models to study topics in physics, biology, and economics. Whether you´re an intermediate-level Python programmer or a student of computational modeling, you´ll delve into examples of complex systems through a series of worked examples, exercises and case studies.
The study of the connections between mathematical automata and for mal logic is as old as theoretical computer science itself. In the founding paper of the subject, published in 1936, Turing showed how to describe the behavior of a universal computing machine with a formula of first order predicate logic, and thereby concluded that there is no algorithm for deciding the validity of sentences in this logic. Research on the log ical aspects of the theory of finite-state automata, which is the subject of this book, began in the early 1960´s with the work of J. Richard Biichi on monadic second-order logic. Biichi´s investigations were extended in several directions. One of these, explored by McNaughton and Papert in their 1971 monograph Counter-free Automata, was the characterization of automata that admit first-order behavioral descriptions, in terms of the semigroup theoretic approach to automata that had recently been developed in the work of Krohn and Rhodes and of Schiitzenberger. In the more than twenty years that have passed since the appearance of McNaughton and Papert´s book, the underlying semigroup theory has grown enor mously, permitting a considerable extension of their results. During the same period, however, fundamental investigations in the theory of finite automata by and large fell out of fashion in the theoretical com puter science community, which moved to other concerns.
Computer systems are simply one type of electrical systems. Using the concept of ´´abstraction´´, this book attempts to unify electrical engineering and computer science as the art of creating and exploiting successive abstractions to manage the complexity of building useful electrical systems.
This textbook presents a survey of research on boolean functions, circuits, parallel computation models, function algebras, and proof systems. Its main aim is to elucidate the structure of ´´fast´´ parallel computation. The complexity of parallel computation is emphasized through a variety of techniques ranging from finite combinatorics, probability theory and finite group theory to finite model theory and proof theory. Nonuniform computation models are studied in the form of boolean circuits; uniform ones in a variety of forms. Steps in the investigation of non-deterministic polynomial time are surveyed as is the complexity of various proof systems. The book will benefit advanced undergraduates and graduate students as well as researchers in the field of complexity theory.
This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with the increase of hands-on, practical applications. This new edition comes with Gradiance, an online assessment tool developed for computer science. Please note, Gradiance is no longer available with this book, as we no longer support this product.
In Distributed Algorithms , Nancy Lynch provides a blueprint for designing, implementing, and analyzing distributed algorithms. She directs her book at a wide audience, including students, programmers, system designers, and researchers. Distributed Algorithms contains the most significant algorithms and impossibility results in the area, all in a simple automata-theoretic setting. The algorithms are proved correct, and their complexity is analyzed according to precisely defined complexity measures. The problems covered include resource allocation, communication, consensus among distributed processes, data consistency, deadlock detection, leader election, global snapshots, and many others. The material is organized according to the system model-first by the timing model and then by the interprocess communication mechanism. The material on system models is isolated in separate chapters for easy reference. The presentation is completely rigorous, yet is intuitive enough for immediate comprehension. This book familiarizes readers with important problems, algorithms, and impossibility results in the area: readers can then recognize the problems when they arise in practice, apply the algorithms to solve them, and use the impossibility results to determine whether problems are unsolvable. The book also provides readers with the basic mathematical tools for designing new algorithms and proving new impossibility results. In addition, it teaches readers how to reason carefully about distributed algorithms-to model them formally, devise precise specifications for their required behavior, prove their correctness, and evaluate their performance with realistic measures.
Using the factor analysis of information risk (FAIR) methodology developed over ten years and adopted by corporations worldwide, Measuring and Managing Information Risk provides a proven and credible framework for understanding, measuring, and analyzing information risk of any size or complexity. Intended for organizations that need to either build a risk management program from the ground up or strengthen an existing one, this book provides a unique and fresh perspective on how to do a basic quantitative risk analysis. Covering such key areas as risk theory, risk calculation, scenario modeling, and communicating risk within the organization, Measuring and Managing Information Risk helps managers make better business decisions by understanding their organizational risk. Uses factor analysis of information risk (FAIR) as a methodology for measuring and managing risk in any organization. Carefully balances theory with practical applicability and relevant stories of successful implementation. Includes examples from a wide variety of businesses and situations presented in an accessible writing style.
In the era of ubiquitous computing, metadata has become infrastructural, like the electrical grid or the highway system. We interact with it or generate it every day. It is not, Pomerantz tell us, just ¿data about data.¿ It is a means by which the complexity of an object is represented in a simpler form. For example, the title, the author, and the cover art are metadata about a book. When metadata does its job well, it fades into the background; everyone (except perhaps the NSA) takes it for granted. Pomerantz explains what metadata is, and why it exists. He distinguishes among different types of metadata¿descriptive, administrative, structural, preservation, and use¿and examines different users and uses of each type. He discusses the technologies that make modern metadata possible, and he speculates about metadata¿s future. By the end of the book, readers will see metadata everywhere. Because, Pomerantz warns us, it¿s metadata¿s world, and we are just living in it.