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

¿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 there are several selfish players competing for a set of resources, and each resource incurs a certain latency, expressed by a congestion-dependent function, to the players using it. Each player has a certain weight and an available set of strategies, where each strategy is a non-empty subset of resources, and aims at choosing a strategy minimizing her personal cost, which is defined as the sum of the latencies experienced on all the selected resources. The impact of selfish behavior in congestion games generally deteriorates the social welfare, thus reducing their performance. This deterioration is generally estimated by the price of anarchy, a metric that compares the worst Nash equilibrium configuration with the optimal social welfare, so that the larger the price of anarchy for a game, the higher the impact of selfish behavior. The book derives from the first author's thesis, which won the Best Italian PhD Thesis in Theoretical Computer Science in 2019, awarded by the Italian chapter of the EATCS. The book will be revised for broader audience, and the thesis supervisor is joining as coauthor following the suggestion of the series. The authors will introduce examples for initial definitions with detailed explanations, and expand the scope to the broader results in the area rather than their specific work.

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.

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

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.

Timing issues are of growing importance for the conceptualization and design of computer-based systems. Even if timing is not essential for the correct behaviour of a system, there may be good reasons to introduce it in such a way that suitable timing becomes relevant for the correct behaviour of a complex system.

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.

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.

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.

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.

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.

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.

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.

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.

A comprehensive introduction to interval logic and duration calculus for modelling, analysing and verifying real-time systems. The Duration Calculus (DC) represents a logical approach to formal design of real-time systems. The duration of a state in a time interval is the accumulated presence time of the state in the interval.

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.

There has been much 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. This comprehensive reference volume collects the main results in the field.

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.

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.

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.

The theory of parsing is an important application area of the theory of formal languages and automata. Context-free grammars were soon found to be the most convenient formalism for describing the syntax of programming languages, and accordingly methods for parsing context-free languages were devel oped.

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.

This book examines approaches to fault-tolerance in the context of algorithmic search theory. It details the application of fault-tolerant search procedures to specific problems in distributed computing, bioinformatics and computational learning.

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.

In this book the authors introduce unfoldings, an approach to model checking which alleviates the state explosion problem by means of concurrency theory.

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.

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.

The aim of this book is to present fundamentals of algebraicspecifications with respect to the following three aspects:fundamentals in the sense of a carefully motivatedintroduction to algebraic specifications, which is easy tounderstand for computer scientists and mathematicians;