This book presents state of the art research in theoretical computer science and related ?elds. In particular, the following areas are discussed: automata theory, formal languages and combinatorics of words, graph transformations, Petri nets, concurrency, as well as natural and molecular computing. The articles are written by leading researchers in these areas. The writers were originally invited to contribute to this book but then the normal refereeing procedure was applied as well. All of the articles deal with some issue that has been under vigorous study during recent years. Still, the topics range from very classical ones to issues raised only two or three years ago. Both survey articles and papers attacking speci?c research problems are included. The book highlights some key issues of theoretical computer science, as they seem to us now at the beginning of the new millennium. Being a comprehensive overview of some of the most active current research in theoretical computer science, it should be of de?nite interest for all researchers in the areas covered. The topics range from basic decidability and the notion of information to graph grammars and graph transformations, and from trees and traces to aqueous algorithms, DNA encoding and self-assembly. Special e?ort has been given to lucid presentation. Therefore, the book should be of interest also for advanced students.
Author(s): Jean Berstel, Luc Boasson (auth.), Wilfried Brauer, Hartmut Ehrig, Juhani Karhumäki, Arto Salomaa (eds.)
Series: Lecture Notes in Computer Science 2300
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2002
Language: English
Pages: 436
Tags: Computation by Abstract Devices; Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Data Structures; Discrete Mathematics in Computer Science; Mathematical Logic and Formal Languages
Balanced Grammars and Their Languages....Pages 3-25
Safety and Liveness Properties for Real Traces and a Direct Translation from LTL to Monoids....Pages 26-38
The Delta Operation: From Strings to Trees to Strings....Pages 39-56
Infinite Solutions of Marked Post Correspondence Problem....Pages 57-68
The Branching Point Approach to Conway’s Problem....Pages 69-76
A Survey of Some Quantitative Approaches to the Notion of Information....Pages 77-95
Nondeterministic Trajectories....Pages 96-106
Binary Patterns in Infinite Binary Words....Pages 107-116
A Sight-seeing Tour of the Computational Landscape of Graph Transformation....Pages 119-137
Local Action Systems and DPO Graph Transformation....Pages 138-157
Bisimulation Equivalences for Graph Grammars....Pages 158-187
High-Level Net Processes....Pages 191-219
Petri Net Control for Grammar Systems....Pages 220-243
Regular Event Structures and Finite Petri Nets: A Conjecture....Pages 244-253
Towards Team-Automata-Driven Object-Oriented Collaborative Work....Pages 257-276
Grammars as Processes....Pages 277-297
Temporal Concurrent Constraint Programming: Applications and Behavior....Pages 298-321
Rewriting P Systems with Conditional Communication....Pages 325-353
An Aqueous Algorithm for Finding the Bijections Contained in a Binary Relation....Pages 354-360
Upper Bounds for Restricted Splicing....Pages 361-375
Codes, Involutions, and DNA Encodings....Pages 376-393
DNA Manipulations in Ciliates....Pages 394-417
A Magic Pot : Self-assembly Computation Revisited....Pages 418-429