Monographs in Computer Science – serie

This monograph, and accompanying open-source software Vesta, addresses two core problems in developing large software projects: 1) versioning and 2) building. In order to develop and sustain automated, scalable "software configuration management (SCM) systems," software systems engineers need to understand how large software code bases can be effectively managed and evolved. Using a well-known open-source software prototype system (Vesta developed at Digital and Compaq Systems Research Lab), the authors meticulously assess, develop, and demonstrate key concepts and methods to achieve such evolvable and scalable software systems. The concepts, lessons, and executable code allow researchers to develop a deeper understanding of the problems, and solution domains possible, for large-scale software construction practices.

Time-series data - data arriving in time order, or a data stream - can be found in fields such as physics, finance, music, networking, and medical instrumentation. Designing fast, scalable algorithms for analyzing single or multiple time series can yield scientific discoveries, medical diagnoses, and certainly profits.High Performance Discovery in Time Series presents rapid-discovery techniques for finding portions of time series with many events (i.e., gamma-ray scatterings) and finding closely related time series (i.e., highly correlated price histories, or musical melodies). Such real-time streaming data analysis is critical for complex real-world data in telecommunications, bioinformatics, and finance databases.This new monograph provides a technical survey of concepts and techniques for describing and analyzing large-scale time-series data streams. It offers essential coverage of the topic for database and online web services researchers and professionals, as well as an ideal resource for graduates.

Parsing--syntax analysis by computer--has been and continues to be an essential part of computer science. Parsing techniques have provided a solid basis for compiler construction since the mid-1960s, and continue to do so, thereby contributing to all existing software today. They enable Web browsers to analyze HTML pages, and PostScript printers to analyze PostScript, among other things; and some of the more advanced techniques are being used in code generation in compilers and in data compression. In linguistics, the importance of formal grammars was recognized early on, but only relatively recently have the corresponding parsing techniques been applied extensively; and their importance as general pattern recognizers is slowly being acknowledged. Today, with problems of speed and memory largely out of the way, these general techniques have grown considerably in importance, both in computer science, where advanced compilers now often use general CF parsers, and in computational linguistics, where such parsers are the only option.They are used in a variety of software products including web browsers, interpreters in computer devices, and data compression programs; and they are used extensively in linguistics. To provide readers with low-threshold access to the full field of parsing techniques, this second edition uses a two-tiered structure. The basic ideas behind the dozen or so existing parsing techniques are explained in an intuitive and narrative style, starting from first principles of data structures and algorithms; this provides breadth and accessibility. The hundreds of realizations and improvements of these techniques are then explained in a much terser, yet still informal, style in the summaries of more than 700 papers referenced in the book; this provides depth.

Geometric Fundamentals of Robotics provides an elegant introduction to the geometric concepts that are important to applications in robotics. This second edition is still unique in providing a deep understanding of the subject: rather than focusing on computational results in kinematics and robotics, it includes significant state-of-the-art material that reflects important advances in the field, connecting robotics back to mathematical fundamentals in group theory and geometry.Geometric Fundamentals of Robotics serves a wide audience of graduate students as well as researchers in a variety of areas, notably mechanical engineering, computer science, and applied mathematics. It is also an invaluable reference text.

Evolutionary computation is becoming increasingly important for computer vision and pattern recognition and provides a systematic way of synthesis and analysis of object detection and recognition systems. Incorporating "learning" into recognition systems will enable these systems to automatically generate new features on the fly and cleverly select a good subset of features according to the type of objects and images to which they are applied. This unique monograph investigates evolutionary computational techniques--such as genetic programming, linear genetic programming, coevolutionary genetic programming and genetic algorithms--to automate the synthesis and analysis of object detection and recognition systems. The purpose of incorporating learning into the system design is to avoid the time-consuming process of feature generation and selection and to reduce the cost of building object detection and recognition systems.Researchers, professionals, engineers, and students working in computer vision, pattern recognition, target recognition, machine learning, evolutionary learning, image processing, knowledge discovery and data mining, cybernetics, robotics, automation and psychology will find this well-developed and organized volume an invaluable resource.

This book ?nds new things to do with an old idea. The proofs-as-programs paradigm constitutes a set of approaches to developing programs from proofs in constructive logic. It has been over thirty years since the paradigm was ?rst conceived. At that time, there was a belief that proofs-as-programs had the - tential for practical application to semi-automated software development. I- tial applications were mostly concerned with ?ne-grain, mathematical program synthesis. For various reasons, research interest in the area eventually tended toward more theoretic issues of constructive logic and type theory. However, in recent years, the situation has become more balanced, and there is increasingly active research in applying constructive techniques to industrial-scale, complex software engineering problems. Thismonographdetailsseveralimportantadvancesinthisdirectionofpr- tical proofs-as-programs. One of the central themes of the book is a general, abstract framework for developing new systems of program synthesis by adapting proofs-as-programs to new contexts. Framework-oriented approaches that facilitate analogous - proaches to building systems for solving particular problems have been popular and successful. Thesemethodsarehelpful asthey providea formal toolbox that enablesa“roll-your-own”approachtodevelopingsolutions.Itishopedthatour framework will have a similar impact. The framework is demonstrated by example. We will give two novel - plications of proofs-as-programs to large-scale, coarse-grain software engine- ing problems: contractual imperative program synthesis and structured p- gram synthesis. These applications constitute an exemplary justi?cation of the framework. Also, in and of themselves, these approaches to synthesis should be interesting forresearchers working in the target problem domains.

The book is a focused survey on probabilistic program semantics, conceived to tell a coherent story with a uniform notation. It is grouped into three themes: Part I is for 'users' of the techniques who will be developing actual programs; Part II gives mathematical foundations intended for those studying exactly how it was done and how to build semantic structures/models in their own work; and Part III describes a very 'hot' research direction, temporal logic and model checking. Topics and features: - introduces readers to very up-to-date research in the mathematics of rigorous development of randomized (probabilistic) algorithms- illustrates by example the typical steps necessary in computer science to build a mathematical model of any programming paradigm- presents results of a large and integrated body of research in the area of 'quantitative' program logicsAn advanced research survey monograph, integrating three major topic areas: random/probabilistic algorithms, assertion-based program reasoning, and refinement programming models. Essential foundation topic for modern sequential programming methodology.

During maintenance of a software system, not all questions can be answered directly by resorting to otherwise reliable and accurate source code. Reverse engineering aims at extracting abstract, goal-oriented views of the system, able to summarize relevant properties of the program's computations. Reverse Engineering of Object-Oriented Code provides a comprehensive overview of several techniques that have been recently investigated in the field of reverse engineering. The book describes the algorithms involved in recovering UML diagrams from the code and the techniques that can be adopted for their visualization. This is important because the UML has become the standard for representing design diagrams in object-oriented development. A state-of-the-art exposition on how to design object-oriented code and accompanying algorithms that can be reverse engineered for greater flexibility in future code maintenance and alteration. Essential object-oriented concepts and programming methods for software engineers and researchers.

Algorithmic Algebra studies some of the main algorithmic tools of computer algebra, covering such topics as Gröbner bases, characteristic sets, resultants and semialgebraic sets. The main purpose of the book is to acquaint advanced undergraduate and graduate students in computer science, engineering and mathematics with the algorithmic ideas in computer algebra so that they could do research in computational algebra or understand the algorithms underlying many popular symbolic computational systems: Mathematica, Maple or Axiom, for instance. Also, researchers in robotics, solid modeling, computational geometry and automated theorem proving community may find it useful as symbolic algebraic techniques have begun to play an important role in these areas. The book, while being self-contained, is written at an advanced level and deals with the subject at an appropriate depth. The book is accessible to computer science students with no previous algebraic training. Some mathematical readers, on the other hand, may find it interesting to see how algorithmic constructions have been used to provide fresh proofs for some classical theorems. The book also contains a large number of exercises with solutions to selected exercises, thus making it ideal as a textbook or for self-study.

Understanding programming and programming languages requires knowledge of the underlying theoretical model. This book explores aspects of programming that are amenable to mathematical proof. The author describes a programming theory which is much simpler and more comprehensive than the current theories to date. In the theoretical model, a specification is just a boolean expression and refinement is just an ordinary implication. The author develops a practical and broad method for writing precise specifications and designing programs whose executions probably satisfy the specifications. Beginning with preparatory material in logic, numbers, sets, lists, functions and relations, the book advances further into program theory, the heart of the book. Subsequent chapters may be selected or omitted according to course emphasis. The text will be useful to students in courses on programming methodology or verification at the advanced undergraduate or beginning graduate level, as well as for software engineers in the field. All technical terms are explained and then demonstrated in the book wherever possible. No advanced mathematical knowledge or programming language is assumed.The book contains numerous exercises and worked-out solutions for specific exercises. Transparency masters and solutions for the remaining exercises are available from the author.

This text attempts to change the way logic and discrete math are taught in computer science and mathematics. While many books treat logic simply as another topic of study, this book's uniqueness is its willingness to take it one step further. In the book, logic is treated as a basic tool, to be applied in essentially every other area. "This is a rather extraordinary book, and deserves to be read by everyone involved in computer science and - perhaps more importantly - software engineering. I recommend it highly. The book will be of value not only to beginning students, but also to hardened programmers with many years of experience - in Fortran, Cobol, C, C++, or whatever. If the book is taken seriously, the rigor that it unfolds and the clarity of its concepts could have a significant impact on the way in which software is conceived and developed. " -Peter G. Neumann-

Although asynchronous circuits date back to the early 1950s most of the digital circuits in use today are synchronous because, traditionally, asynchronous circuits have been viewed as difficult to understand and design. In recent years, however, there has been a great surge of interest in asynchronous circuits, largely through the development of new asynchronous design methodologies. This book provides a comprehensive theory of asynchronous circuits, including modelling, analysis, simulation, specification, verification, and an introduction to their design. It is based on courses given to graduate students and will be suitable for computer scientists and engineers involved in the research and development of asynchronous designs.

Procedural languages are generally well understood and their formal foundations cast in the forms of various lambda-calculi. For object- oriented languages however the situation is not as clear-cut. In this book the authors propose and develop a different approach by developing object calculi in which objects are treated as primitives. Using object calculi,the authors are able to explain both the semantics of objects and their typing rules and demonstrate how to develop all of the most important concepts of object-oriented programming languages: self, dynamic dispatch, classes, inheritance, protected and private methods, prototyping, subtyping, covariance and contravariance, and method specialization. Many researchers and graduate students will find this an important development of the underpinnings of object-oriented programming.

The idea for this book was conceived over the second bottle of Villa Maria's Caber­ net Medot '89, at the dinner of the Australasian Combinatorics Conference held at Palmerston North, New Zealand in December 1990, where the authors first met and discovered they had a number of interests in common. Initially, we embarked on a small project to try to formulate reductions to address the apparent parame­ terized intractability of DOMINATING SET, and to introduce a structure in which to frame our answers. Having spent several months trying to get the definitions for the reductions right (they now seem so obvious), we turned to our tattered copies of Garey and Johnson's work [239]. We were stunned to find that virtually none of the classical reductions worked in the parameterized setting. We then wondered if we'd be able to find any interesting reductions. Several years, many more bottles, so many papers, and reductions later it [3] seemed that we had unwittingly stumbled upon what we believe is a truly central and new area of complexity theory. It seemed to us that the material would be of great interest to people working in areas where exact algorithms for a small range of parameters are natural and useful (e. g. , Molecular Biology, VLSI design). The tractability theory was rich with distinctive and powerful techniques. The intractability theory seemed to have a deep structure and techniques all of its own.

Today's distributed systems are characterized by interactions, often complex, between many different hardware/software components cooperating and exchanging information. To reduce the complexity of the development of interactive systems, experts employ descriptions, or specifications, of a given system's behavior and/or structure. This book provides a mathematical and logical foundation for the specification and development of interactive systems based on a model that describes systems in terms of their input/output behavior. Based on the model, the authors build a basic method, called FOCUS, that enables interactive systems to be described by characterizing their histories of message interaction. The book progresses from an introduction and guided tour of FOCUS through streams, specifications and their properties, and behavioral, interface, and conditional refinements.

This book features representative work in the design of panoramic image capturing systems, the theory involved in the imaging process, and applications that use panoramic images. The intended audience is anyone who wishes to become familiar with panoramic vision and its latest research work. The contents of this book allow the reader to understand the more technical aspects of panoramic vision, such as sensor design and imaging techniques. Researchers, instructors, and students will especially find this book useful.

Set Theory for Computing offers an up-to-date and comprehensive account of set-oriented symbolic manipulation and automated reasoning methods. Mastering today's variety of systems with crisp, formal tools is a prerequisite for a high degree of control over sets and aggregates. The many algorithmic methods and deductive techniques in this book offer readers a clear view of the use of set-theoretic notions in such critical areas as specification of problems, data types, and solution methods; algorithmic program verification; and automated deduction. The rigorous and largely self-contained style of presentation addresses readers wanting to complement their set intuition with the ability to exploit it in specification and verification and master it by symbolic, logically based techniques and methods. This book will be of interest to graduates and researchers in theoretical computer science and computational logic and automated reasoning.

In this book, a programming model is developed that addresses the fundamental issues of "large-scale programming," unifying several concepts from database theory, object-oriented programming and designs of reactive systems. The model and the associated theory have been christened "Seuss. " The major goal of Seuss is to simplify multiprogramming. To this end, we separate the concern of concurrent implementation from the core program design problem. A program execution is understood as a single thread of control - sequential executions of actions that are chosen according to some scheduling policy - yet program implementation permits concurrent executions of multiple threads. As a consequence, it is possible to reason about the properties of a program from its single execution thread, whereas an implementation may exploit the inherent concurrency for efficient execution.

The IFIP working group 2. 3 (Programming Methodology) is made up of internationally prominent computing academics and industrialists, and broadly its purpose is to invent, discuss and assess new and emerging techniques for improving the quality of software and systems. The group's membership has been influential in topics such as program correctness, object orientation, operating systems and distributed computing; indeed many thriving areas of research nowadays are based on ideas which were once scrutinized by the 2. 3 working committee. This is a volume of chapters written by the membership which will form a reference and guide to the front line of research activity in programming methodology. The range of subjects reflects the current interests of the members, and will offer insightful and controversial opinions on modern programming methods and practice. The material is arranged in thematic sections, each one introduced by a problem which epitomizes the spirit of that topic. The exemplary problem will encourage vigorous discussion and will form the basis for an introduction/tutorial for its section.

Super-Recursive Algorithms provides an accessible, focused examination of the theory of super-recursive algorithms and its ramifications for the computer industry, networks, artificial intelligence, embedded systems, and the Internet. The book demonstrates how these algorithms are more appropriate as mathematical models for modern computers, and how these algorithms present a better framework for computing methods in such areas as numerical analysis, array searching, and controlling and monitoring systems. In addition, a new practically-oriented perspective on the theory of algorithms, computation, and automata, as a whole, is developed. Problems of efficiency, software development, parallel and distributed processing, pervasive and emerging computation, computer architecture, machine learning, brain modeling, knowledge discovery, and intelligent systems are addressed. This clear exposition, motivated by numerous examples and illustrations, serves researchers and advanced students interested in theory of computation and algorithms.

From the reviews: "This book offers a coherent treatment, at the graduate textbook level, of the field that has come to be known in the last decade or so as computational geometry...The book is well organized and lucidly written; a timely contribution by two founders of the field. It clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics. It also points the way to the solution of the more challenging problems in dimensions higher than two." #Mathematical Reviews#1 "...This remarkable book is a comprehensive and systematic study on research results obtained especially in the last ten years. The very clear presentation concentrates on basic ideas, fundamental combinatorial structures, and crucial algorithmic techniques. The plenty of results is clever organized following these guidelines and within the framework of some detailed case studies. A large number of figures and examples also aid the understanding of the material.Therefore, it can be highly recommended as an early graduate text but it should prove also to be essential to researchers and professionals in applied fields of computer-aided design, computer graphics, and robotics." #Biometrical Journal#2

This book presents a unified collection of concepts, tools, and techniques that constitute the most important technology available today for the design and implementation of information systems. The framework adopted for this integration goal is the one offered by the relational model of data, its applica­ tions, and implementations in multiuser and distributed environments. The topics presented in the book include conceptual modeling of application environments using the relational model, formal properties of that model, and tools such as relational languages which go with it, techniques for the logical and physical design of relational database systems and their imple­ mentations. The book attempts to develop an integrated methodology for addressing all these issues on the basis of the relational approach and various research and practical developments related to that approach. This book is the only one available today that presents such an inte­ gration. The diversity of approaches to data models, to logical and physical database design, to database application programming, and to use and imple­ mentation of database systems calls for a common framework for all of them. It has become difficult to study modern database technology with­ out such a unified approach to a diversity of results developed during the vigorous growth of the database area in recent years, let alone to teach a course on the subject.

Describes basic programming principles and their step-by-step applications.Numerous examples are included.

The Synthesizer Generator is a system for automating the construction of customized editors for particular languages. The unique feature of the Synthesizer Generator is its use of an immediate-computation paradigm to perform analysis, translation, and error reporting while an object is being edited. With the Synthesizer Generator one can create programming language environments that incrementally parse, type-check, and compile a program as it is interactively developed. The use of the system is not restricted to programming languages; editors for logics, specification languages, and verification languages can be created as well. The specification language of the Synthesizer Generator is based on the attribute-grammar concept, which plays a major role in the way compiler construction is taught today. For this reason, the Synthesizer Generator is ideal for use in course projects and should be of particular interest to those involved in compiler construction. The Synthesizer Generator Reference Manual is the defining document of the Synthesizer Generator system.Written by the Synthesizer Generator's creators, this volume provides complete documentation on all aspects of specifying, generating, debugging, and running editors.

More than anything else, this book is a tribute to Edsger W. Dijkstra, on the occasion of his sixtieth birthday, by just a few of those fortunate enough to be influenced by him and his work and to be called his friend or relation, his master, colleague, or pupil. This book contains fifty-four technical contributions in different areas of endeavor, although many of them deal with an area of particular concern to Dijkstra: programming. Each contribution is relatively short and could be digested in one sitting. Together, they form a nice cross section of the discipline of programming at the beginning of the nineties. While many know of Dijkstra's technical contributions, they may not be aware of his ultimate goal, the mastery of complexity in mathematics and computing science. He has forcefully argued that beauty and elegance are essential to this mastery. The title of this book, chosen to reflect his ultimate goal, comes from a sentence in an article of his on some beautiful arguments using mathematical induction: "... when we recognize the battle against chaos, mess, and unmastered complexity as one of computing sci- ence's major callings, we must admit that 'Beauty Is Our Business'."

Programming is a fascinating and challenging subject. Unfortunately, it is rarely presented as such. Most often it is taught by "induction": features of some famous programming languages are given operational meaning (e.g. a loop "goes round and round"), a number of examples are shown, and by induction, we are asked to develop other programs, often radically different from the ones we've seen. Basically we are taught to guess our programs, and then to patch up our guesses. Our errors are given the cute name of "bugs". Fixing them becomes puzzle-solving, as does finding tricks that exploit or avoid poorly designed features of the programming language. The entire process is time-consuming and expensive. And even so, we are never quite sure if our programs really work in all cases. When approached in this way, programming is indeed a dull activity. There is, however, another approach to programming, an approach in which programs can be developed reliably, with attention to the real issues. It is a practical approach based on methodically developing programs from their specifications. Besides being practical, it is exciting. Many programs can be developed with relative ease. Problems which once were difficult can now be solved by beginners. Elegant solutions bring great satisfaction. This is our subject. We are interested in making programming an exciting topic!

The design and analysis of algorithms is one of the two essential cornerstone topics in computer science (the other being automata theory/theory of computation). Every computer scientist has a copy of Knuth's works on algorithms on his or her shelf. Dexter Kozen, a researcher and professor at Cornell University, has written a text for graduate study of algorithms. This will be an important reference book as well as being a useful graduate-level textbook.

Active rules provide a new and important method for designing databases and the subject is seeing an increasing amount of attention from commercial database companies. This book provides a timely survey of the field from the point of view of some of the subject's most active researchers. The book is divided into several parts, organized by theme: the first, Fundamentals covers the underlying methodology reagrding active rules, next comes a collection of chapters which cover formal specification, rule analysis, performance analysis, and support tools, the third part is devoted to a number of chapters covering the implementation of active rules in a number of commercial systems. Finally, come sections on applications and future directions that research may take. All researchers in databases will find this provides a valuable overview of this topic.

Among all the interests in parallelism, there is an essential and fundamental one that has remained largely unexplored, namely the question of how to design parallel programs from their specification. And that is what this book is about. It proposes a method for the formal development of parallel programs - multiprograms as we have preferred to call them -, and it does so with a minimum of formal gear, viz. with the predicate calculus and with the meanwhile well-established theory of Owicki and Gries. The fact that one can get away with just this theory will probably not convey anything to the uninitiated, but it may all the more come as a surprise to those who were exposed earlier to correctness of multiprograms. Contrary to common belief, the Owicki/Gries theory can indeed be effectively put to work for the formal development of multiprograms, regardless of whether these algorithms are distributed or not. That is what we intend to exemplify with this book.