Computational geometry as an area of research in its own right emerged in the early seventies of this century. Right from the beginning, it was obvious that strong connections of various kinds exist to questions studied in the considerably older field of combinatorial geometry. For example, the combinatorial structure of a geometric problem usually decides which algorithmic method solves the problem most efficiently. Furthermore, the analysis of an algorithm often requires a great deal of combinatorial knowledge. As it turns out, however, the connection between the two research areas commonly...
Computational geometry as an area of research in its own right emerged in the early seventies of this century. Right from the beginning, it was obviou...
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 characteristics of combinatorial optimization problems to which local search can be applied, its relation to complexity theory, and the combination with randomized search features have led to a wealth of interesting theoretical results. However, these results are scattered throughout the literature.
This is the first book that presents a...
Local search has been applied successfully to a diverse collection of optimization problems. It's appreciated for its basic conceptual foundation, ...
The first book to integrate various model-based software specification approaches. The integration approach is based on a common semantic domain of abstract systems, their composition and development. Its applicability is shown through semantic interpretations and compositional comparisons of different specification approaches. These range from formal specification techniques like process calculi, Petri nets and rule-based formalisms to semiformal software modeling languages like those in the UML family.
The first book to integrate various model-based software specification approaches. The integration approach is based on a common semantic domain of...
This work is Volume II of a two-volume monograph on the theory of deterministic parsing of context-free grammars. Volume I, "Languages and Parsing" (Chapters 1 to 5), was an introduction to the basic concepts of formal language theory and context-free parsing. Volume II (Chapters 6 to 10) contains a thorough treat ment of the theory of the two most important deterministic parsing methods: LR(k) and LL(k) parsing. Volume II is a continuation of Volume I; together these two volumes form an integrated work, with chapters, theorems, lemmas, etc. numbered consecutively. Volume II begins with...
This work is Volume II of a two-volume monograph on the theory of deterministic parsing of context-free grammars. Volume I, "Languages and Parsing" (C...
Time-dependent scheduling involves problems in which the processing times of jobs depend on when those jobs are started. This book is a comprehensive study of complexity results and optimal and suboptimal algorithms concerning time-dependent scheduling in single-, parallel- and dedicated-machine environments. In addition to complexity issues and exact or heuristic algorithms which are typically presented in scheduling books, the author also includes more advanced topics such as matrix methods in time-dependent scheduling, and time-dependent scheduling with two criteria. The reader should...
Time-dependent scheduling involves problems in which the processing times of jobs depend on when those jobs are started. This book is a comprehensi...
Replacement systems, such as term rewriting systems, tree manipulat ing systems, and graph grammars, have been used in Computer Science in the context of theorem proving, program optimization, abstract data types, algebraic simplification, and symbolic comput ation. Replacement systems for strings arose about seventy years earlier in the area of combinatory logic and group theory. The most natural and appropriate formalism for dealing with string rewriting is the notion of a semi-Thue system and this monograph treats its central aspects. The reduction relation is here defined firstly by the...
Replacement systems, such as term rewriting systems, tree manipulat ing systems, and graph grammars, have been used in Computer Science in the context...
The purpose of this Handbook is to highlight both theory and applications of weighted automata. Weighted ?nite automata are classical nondeterministic ?nite automata in which the transitions carry weights. These weights may model, e. g., the cost involved when executing a transition, the amount of resources or time neededforthis, ortheprobabilityorreliabilityofitssuccessful execution. The behavior of weighted ?nite automata can then be considered as the function (suitably de?ned) associating with each word the weight of its execution. Clearly, weights can also be added to classical automata...
The purpose of this Handbook is to highlight both theory and applications of weighted automata. Weighted ?nite automata are classical nondeterministic...
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, universal algebra and category theory in novel ways. Stochastic systems provide important tools for systems modeling, and recent work shows that categorical reasoning may lead to new insights, previously not available in a purely probabilistic setting.
This book combines coalgebraic reasoning, stochastic systems and logics. It provides an insight...
Coalgebraic logic is an important research topic in the areas of concurrency theory, semantics, transition systems and modal logics. It provides a ...
