Monographs in Theoretical Computer Science. An EATCS Series

​Congestion games are a fundamental class of games widely considered and studied in non-cooperative game theory, introduced to model several realistic scenarios in which people share a limited quantity of goods or services. In congestion games …

In this book the author explains domain engineering and the underlying science, and he then shows how we can derive requirements prescriptions for computing systems from domain descriptions. A further motivation is to present domain descriptions …

This is a comprehensive study of various time-dependent scheduling problems in single-, parallel- and dedicated-machine environments. In addition to complexity issues and exact or heuristic algorithms which are typically presented in scheduling …

This book deals with the problem of finding suitable languages that can represent specific classes of Petri nets, the most studied and widely accepted model for distributed systems. Hence, the contribution of this book amounts to the …

This book describes reversible computing from the standpoint of the theory of automata and computing. It investigates how reversibility can be effectively utilized in computing. A reversible computing system is a “backward deterministic” system …

This is the first comprehensive introduction to the theory of word-representable graphs, a generalization of several classical classes of graphs, and a new topic in discrete mathematics.

After extensive introductory chapters that explain the

This book is a comprehensive explanation of graph and model transformation. It contains a detailed introduction, including basic results and applications of the algebraic theory of graph transformations, and references to the historical context. T

Why a book on fault-tolerant search algorithms? Searching is one of the fundamental problems in computer science. Time and again algorithmic and combinatorial issues originally studied in the context of search find application in the most diverse

This book provides foundations for software specification and formal software development from the perspective of work on algebraic specification, concentrating on developing basic concepts and studying their fundamental properties. These foundati

Models that include a notion of time are ubiquitous in disciplines such as the natural sciences, engineering, philosophy, and linguistics, but in computing the abstractions provided by the traditional models are problematic and the discipline has

Wireless ad hoc sensor networks has recently become a very active research subject. Achieving efficient, fault-tolerant realizations of very large, highly dynamic, complex, unconventional networks is a real challenge for abstract modelling, algorithm

A deterministic extractor is a function that extracts almost perfect random bits from a weak random source. In this research monograph the author constructs deterministic extractors for several types of sources. A basic theme in this work is a method

There has been considerable interest recently in the subject of patterns in permutations and words, a new branch of combinatorics with its roots in the works of Rotem, Rogers, and Knuth in the 1970s. Consideration of the patterns in question has b

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. These weights may model, e. g. , the cost

Coalgebraic logic is an important research topic in the areas of concurrency theory, semantics, transition systems and modal logics. It provides a general approach to modeling systems, allowing us to apply important results from coalgebras, univer

hebookpresentedtothereaderisdevotedtotime-dependentscheduling. TScheduling problems, in general, consist in the allocation of resources over time in order to perform a set of jobs. Any allocation that meets all requirements concerning the jobs and re

By a specification language we understand a formal system of syntax, semantics and proof rules. The syntax and semantics define a language; the proof rules define a proof system. Specifications are expressions in the language, and reasoning over p

Model checking is a prominent technique used in the hardware and software industries for automatic verification. While it is very successful in finding subtle bugs in distributed systems, it faces the state explosion problem - the number of reacha

Local search has been applied successfully to a diverse collection of optimization problems. It's appreciated for its basic conceptual foundation, its general applicability, and its power to serve as a source for new search paradigms. The typical

Graphs are widely used to represent structural information in the form of objects and connections between them. Graph transformation is the rule-based manipulation of graphs, an increasingly important concept in computer science and related fields