Bøger i Monographs in Theoretical Computer Science. An EATCS Series serien

In this research monograph, the author constructs deterministic extractors for several types of sources, using a methodology of recycling randomness which enables increasing the output length of deterministic extractors to near optimal length.

This work presents a purely classical first-order logical approach to the field of study in theoretical computer science sometimes referred to as the theory of programs, or programming theory.

The OrIgIn of this monograph is a course entitled "Semantics directed Compiler Generation" which Professor Neil D. this led to a specification of a compiler generator which was bootstrapped on itself resulting in a machine-generated compiler generator.

The authors explore the properties of this generalized convexity in multidimensional Euclidean space, and describ restricted-orientation analogs of lines, hyperplanes, flats, halfspaces, and identify major properties of standard convex sets that also hold for restricted-orientation convexity.

They allow the modeller to investigate dynamic properties of CP-nets. The main ideas behind the analysis methods are described as well as the mathematics on which they are based and also how the methods are supported by computer tools.

This book provides a comprehensive study of complexity results and optimal and suboptimal algorithms concerning time-dependent scheduling in single-, parallel- and dedicated-machine environments. This is the first monograph on time-dependent scheduling.

This monograph presents a systematic, exhaustive and up-to-date overview of formal methods and theories for data analysis and inference inspired by the concept of rough set. The formalisms developed are non-invasive in that only the actual information that is needed in the process of analysis without external sources of information being required.

Local search has been applied successfully to a diverse collection of optimization problems. It provides the reader with a coherent overview of the achievements obtained so far, and serves as a source of inspiration for the development of novel results in the challenging field of local search.

The reason is that many commonly occurring phenomena and computer applications are highly con current : typical examples include control systems, computer networks, digital hardware, business computing, and multimedia systems.

The primary goal of this book is unifying and making more widely accessible the vibrant stream of research - spanning more than two decades - on the theory of semi-feasible algorithms. In doing so it demonstrates the richness inherent in central notions of complexity: running time, nonuniform complexity, lowness, and NP-hardness.

This book presents a coherent description of the theoretical and practical aspects of Coloured Petri Nets (CP-nets or CPN).

Combining coalgebraic reasoning, stochastic systems and logic, this volume presents the principles of coalgebraic logic from a categorical perspective. Modal logics are also discussed, including probabilistic interpretations and an analysis of Kripke models.

Wireless ad hoc sensor networks has recently become a very active research subject. The intended audience includes researchers and graduate students working on sensor networks, and the broader areas of wireless networking and distributed computing, as well as practitioners in the relevant application areas.

In the theory of automata this observation has led to the concepts of pro ducts and complete systems of automata. In the general form of the products of automata all the component automata are fed back to one another. , all component automata steer all those automata which follow them in the product.

The purpose of this Handbook is to highlight both theory and applications of weighted automata. Weighted finite automata are classical nondeterministic finite automata in which the transitions carry weights.

A new model-theoretic approach to universal algebra is offered in this book. The book concerns the algebraic characterization of axiomatic classes of algebras (equational, implicational, and universal Horn classes) by closure operators generalizing the famous Birkhoff Variety Theorem, and the algebraic characterization of the related theories.

Relational methods can be found at various places incomputer science, notably in data base theory, relationalsemantics of concurrency, relationaltype theory, analysisof rewriting systems, and modern programming languagedesign. Itexplains how to use relational and graph-theoretic methodssystematically in computer science.

The mathematical theory of computation has given rise to two important ap proaches to the informal notion of "complexity": Kolmogorov complexity, usu ally a complexity measure for a single object such as a string, a sequence etc., measures the amount of information necessary to describe the object.

This is a motivated presentation of recent results on tree transducers, applied to studying the general properties of formal models and for providing semantics to context-free languages. The authors consider top-down tree transducers, macro tree transducers, attributed tree transducers, and macro attributed tree transducers.

Net theory is a theory of systems organization which had its origins, about 20 years ago, in the dissertation of C. The main concern of this book is the presentation of those parts of net theory which can serve as a basis for practical application. By generali zation of these notions a part of the theory of nets is presented.

Indeed, automata theory and the closely related theory of formal languages form nowadays such a highly developed and diversified body of knowledge that even an exposition of "reasonably important" results is not possible within one volume.

Concurrent systems abound in human experience but theirfully adequate conceptualization as yet eludes our most ablethinkers. The COSY (ConcurrentSystem) notation and theorywas developed in the last decade as one of a number ofmathematical approaches for conceptualizing and analyzingconcurrent and reactive systems.

This is the second volume of a two volume collection on Structural Complexity. This volume assumes as a prerequisite knowledge about the topics treated in Volume I, but the present volume itself is nearly self-contained.

To our families The formal language theory was born in the middle of our century as a tool for modelling and investigating the syntax of natural languages, and it has been developed mainly in connection with programming language handling.

The volume presents the most important ideas and experiences from the projects, in a way which is useful also for readers who do not yet have personal experience with the construction and analysis of large CPN models. The presentation of the projects is based upon material provided by the per sons who have accomplished the individual projects.

For the first time in book form, original results from the last ten years are presented, some previously unpublished, using combinatorial and algebraic methods. Researchers will find important new results on semigroups and formal languages, as well as various applications for these methods.

We show the need to go beyond the view of logic as a geometry of static truths, and to see logic, both at the proof-theoretic and at the model-theoretic level, as a dynamics of processes. We see the dynamics of logic processes bear with classical logic, the same relation as the one existing between classical mechanics and Euclidean geometry.

Iteration plays a fundamental role in the theory of computation: for example, in the theory of automata, in formal language theory, in the study of formal power series, in the semantics of flowchart algorithms and programming languages, and in circular data type definitions.

This book presents comprehensive studies on nine specification languages and their logics of reasoning. In a unique feature, the book closes with short commentaries on the specification languages written by researchers closely associated with their original development.