Monographs in Computer Science – serie

The core technologies underlying software configuration managementhave changed little in more than two decades. Developmentorganizations struggle to manage ever­ larger software systems with tools that were never designed to handle them. Their development processes are warped by the inadequacies of their building and version management tools. Developers must take time from writing and debugging code to cope with the operational problems thrust upon them by their build system's inade­ quate support of large-scale concurrent development. Vesta, a novel system for large-scale software configuration management, offers a better solution. Through a unique integration of building and version management facilities, Vestaconstructs software of any size repeatably, incrementally, and consis­ tently. Since modem software development occurs worldwide, Vesta supports con­ current, multi-site, distributed development. Vesta's core facilities are methodologi­ cally neutral, allowing development organizations a wide range of flexibility in the way they arrange their code repositories and structure the building of system com­ ponents. In short, Vesta advances the state of the art in configuration management.

Overview and Goals Data arriving in time order (a data stream) arises in fields ranging from physics to finance to medicine to music, just to name a few. Often the data comes from sensors (in physics and medicine for example) whose data rates continue to improve dramati­ cally as sensor technology improves. Further, the number of sensors is increasing, so correlating data between sensors becomes ever more critical in orderto distill knowl­ edge from the data. On-line response is desirable in many applications (e.g., to aim a telescope at a burst of activity in a galaxy or to perform magnetic resonance-based real-time surgery). These factors - data size, bursts, correlation, and fast response­ motivate this book. Our goal is to help you design fast, scalable algorithms for the analysis of single or multiple time series. Not only will you find useful techniques and systems built from simple primi­ tives, but creative readers will find many other applications of these primitives and may see how to create new ones of their own. Our goal, then, is to help research mathematicians and computer scientists find new algorithms and to help working scientists and financial mathematicians design better, faster software.

Parsing, also referred to as syntax analysis, has been and continues to be an essential part of computer science and linguistics. Today, parsing techniques are also implemented in a number of other disciplines, including but not limited to, document preparation and conversion, typesetting chemical formulae, and chromosome recognition.This second edition presents new developments and discoveries that have been made in the field. Parsing techniques have grown considerably in importance, both in computational linguistics where such parsers are the only option, and computer science, where advanced compilers often use general CF parsers. Parsing techniques provide a solid basis for compiler construction and contribute to all existing software: enabling Web browsers to analyze HTML pages and PostScript printers to analyze PostScript. Some of the more advanced techniques are used in code generation in compilers and in data compression.In linguistics, the importance of formal grammars was recognized early on, but only recently have the corresponding parsing techniques been applied. Also their importance as general pattern recognizers is slowly being acknowledged. This text Parsing Techniques explores new developments, such as generalized deterministic parsing, linear-time substring parsing, parallel parsing, parsing as intersection, non-canonical methods, and non-Chomsky systems.To provide readers with low-threshold access to the full field of parsing techniques, this new 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, and problems are presented at the conclusion of each chapter, allowing the reader to step outside the bounds of the covered material and explore parsing techniques at various levels. The reader is also provided with an extensive annotated bibliography as well as hints and partial solutions to a number of problems. In the bibliography, hundreds of realizations and improvements of parsing techniques are explained in a much terser, yet still informal, style, improving its readability and usability.The reader should have an understanding of algorithmic thinking, especially recursion; however, knowledge of any particular programming language is not required.

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.

This book integrates coverage of random/probabilistic algorithms, assertion-based program reasoning, and refinement programming models, providing a highly focused survey on probabilistic program semantics. It illustrates by example the typical steps necessary in computer science to build a mathematical model of any programming paradigm, addressing an 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.

Deformable objects are ubiquitous in the world surrounding us, on all levels from micro to macro. The need to study such shapes and model their behavior arises in a wide spectrum of applications, ranging from medicine to security. In recent years, non-rigid shapes have attracted growing interest, which has led to rapid development of the field, where state-of-the-art results from very different sciences - theoretical and numerical geometry, optimization, linear algebra, graph theory, machine learning and computer graphics, to mention several - are applied to find solutions.This book gives an overview of the current state of science in analysis and synthesis of non-rigid shapes. Everyday examples are used to explain concepts and to illustrate different techniques. The presentation unfolds systematically and numerous figures enrich the engaging exposition. Practice problems follow at the end of each chapter, with detailed solutions to selected problems in the appendix. A gallery of colored images enhances the text.This book will be of interest to graduate students, researchers and professionals in different fields of mathematics, computer science and engineering. It may be used for courses in computer vision, numerical geometry and geometric modeling and computer graphics or for self-study.

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.

There are several theories of programming. The first usable theory, often called "Hoare's Logic", is still probably the most widely known. In it, a specification is a pair of predicates: a precondition and postcondition (these and all technical terms will be defined in due course). Another popular and closely related theory by Dijkstra uses the weakest precondition predicate transformer, which is a function from programs and postconditions to preconditions. lones's Vienna Development Method has been used to advantage in some industries; in it, a specification is a pair of predicates (as in Hoare's Logic), but the second predicate is a relation. Temporal Logic is yet another formalism that introduces some special operators and quantifiers to describe some aspects of computation. The theory in this book is simpler than any of those just mentioned. In it, a specification is just a boolean expression. Refinement is just ordinary implication. This theory is also more general than those just mentioned, applying to both terminating and nonterminating computation, to both sequential and parallel computation, to both stand-alone and interactive computation. And it includes time bounds, both for algorithm classification and for tightly constrained real-time applications.

This text attempts to change the way we teach logic to beginning students. Instead of teaching logic as a subject in isolation, we regard it as a basic tool and show how to use it. We strive to give students a skill in the propo­ sitional and predicate calculi and then to exercise that skill thoroughly in applications that arise in computer science and discrete mathematics. We are not logicians, but programming methodologists, and this text reflects that perspective. We are among the first generation of scientists who are more interested in using logic than in studying it. With this text, we hope to empower further generations of computer scientists and math­ ematicians to become serious users of logic. Logic is the glue Logic is the glue that binds together methods of reasoning, in all domains. The traditional proof methods -for example, proof by assumption, con­ tradiction, mutual implication, and induction- have their basis in formal logic. Thus, whether proofs are to be presented formally or informally, a study of logic can provide understanding.

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.

This book presents a fundamental mathematical and logical approach to soft­ ware and systems engineering. Considering the large number of books de­ scribing mathematical approaches to program development, it is important to explain what we consider to be the specific contribution of our book, to identify our goals, and to characterize our intended target audience. Most books dealing with the mathematics and logics of programming and system development are mainly devoted to programming in the small. This is in contrast to our book where the emphasis is on modular system development with the help of component specifications with precisely identified interfaces and refinement concepts. Our book aims at systems development carried out in a systematic way, based on a clear mathematical theory. We do not claim that this book presents a full-blown engineering method. In fact, this is certainly not a book for the application-driven software engi­ neer looking for a practical method for system development in an industrial context. It is much rather a book for the computer scientist and the scientifi­ cally interested engineer who looks for basic principles of system development and, moreover, its mathematical foundations. It is also a book for method builders interested in a proper mathematical foundation on which they can build a practical development method and industrial-strength support tools.

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 second half of the twentieth century saw an astonishing increase in computing power; today computers are unbelievably faster than they used to be, they have more memory, they can communicate routinely with remote machines all over the world - and they can fit on a desktop. But, despite this remarkable progress, the voracity of modem applications and user expectations still pushes technology right to the limit. As hardware engineers build ever-more-powerful machines, so too must software become more sophisticated to keep up. Medium- to large-scale programming projects need teams of people to pull everything together in an acceptable timescale. The question of how pro gram­ mers understand their own tasks, and how they fit together with those of their colleagues to achieve the overall goal, is a major concern. Without that under­ standing it would be practically impossible to realise the commercial potential of our present-day computing hardware. That programming has been able to keep pace with the formidable advances in hardware is due to the similarly formidable advances in the principles for design, construction and organisation of programs. The efficacy of these methods and principles speaks for itself - computer technology is all-pervasive - but even more telling is that they are beginning to feed back and inftuence hardware design as weIl. The study of such methods is called programming methodology, whose topics range over system-and domain-modelling, concurrency, object orientation, program specification and validation. That is the theme of this collection.

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 implementation of language-based editing environments. The editor designer prepares a specification that includes rules defining a language's context-free abstract syn­ tax, context-sensitive relationships, display format, and concrete input syntax. From this specification, the Synthesizer Generator creates a display editor for manipulating objects according to these rules [Reps84]. This volume, The Synthesizer Generator Reference Manual, is intended as the defining document of the system. A companion volume, The Synthesizer Gen­ erator: A System for Constructing Language-Based Editors [Reps88], provides a more tutorial description of the system; it contains numerous examples that illustrate the specification and use of generated editors, as well as chapters that explain important algorithms of the implementation. The Synthesizer Generator is a generalization of our earlier system, the Cor­ nell Program Synthesizer [Teitelbaum81], which was a programming environ­ ment for a specific small dialect of PL/I. It featured a display-oriented, syntax­ directed editor, an incremental compiler, an execution supervisor supporting source-level debugging, and a file system containing syntactically typed pro­ gram fragments. Whereas PL/I was built into the Cornell Program Synthesizer, the Synthesizer Generator accepts a formal language definition as input. Although originally conceived as a tool for creating Synthesizer-like environments for arbitrary pro­ gramming languages, the Synthesizer Generator is more broadly useful. Any textual language with a hierarchical phrase structure grammar is a candidate. vi Preface Interactive theorem proving for formal mathematics and logic, for example, has emerged as a particularlysuitable application.

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!

These are my lecture notes from CS681: Design and Analysis of Algo­ rithms, a one-semester graduate course I taught at Cornell for three consec­ utive fall semesters from '88 to '90. The course serves a dual purpose: to cover core material in algorithms for graduate students in computer science preparing for their PhD qualifying exams, and to introduce theory students to some advanced topics in the design and analysis of algorithms. The material is thus a mixture of core and advanced topics. At first I meant these notes to supplement and not supplant a textbook, but over the three years they gradually took on a life of their own. In addition to the notes, I depended heavily on the texts • A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975. • M. R. Garey and D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness. w. H. Freeman, 1979. • R. E. Tarjan, Data Structures and Network Algorithms. SIAM Regional Conference Series in Applied Mathematics 44, 1983. and still recommend them as excellent references.

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.