Formal and Natural Computing: Essays Dedicated to Grzegorz Rozenberg

ISBN-13: 9783540431909 / Angielski / Miękka / 2002 / 436 str.

Wilfried Brauer;Hartmut Ehrig;Juhani Karhumaki

Opis

Assessing the state of the art in some of the most active research areas in theoretical computer science, this book presents research papers and survey articles written on the occasion of Grzegorz Rozenberg's 60th birthday. The topics covered 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.

Spis treści

Words, Languages, Automata.- Balanced Grammars and Their Languages.- Safety and Liveness Properties for Real Traces and a Direct Translation from LTL to Monoids.- The Delta Operation: From Strings to Trees to Strings.- Infinite Solutions of Marked Post Correspondence Problem.- The Branching Point Approach to Conway’s Problem.- A Survey of Some Quantitative Approaches to the Notion of Information.- Nondeterministic Trajectories.- Binary Patterns in Infinite Binary Words.- Graph Transformations.- A Sight-seeing Tour of the Computational Landscape of Graph Transformation.- Local Action Systems and DPO Graph Transformation.- Bisimulation Equivalences for Graph Grammars.- Petri Nets.- High-Level Net Processes.- Petri Net Control for Grammar Systems.- Regular Event Structures and Finite Petri Nets: A Conjecture.- Concurrent Computing.- Towards Team-Automata-Driven Object-Oriented Collaborative Work.- Grammars as Processes.- Temporal Concurrent Constraint Programming: Applications and Behavior.- Molecular Computing.- Rewriting P Systems with Conditional Communication.- An Aqueous Algorithm for Finding the Bijections Contained in a Binary Relation.- Upper Bounds for Restricted Splicing.- Codes, Involutions, and DNA Encodings.- DNA Manipulations in Ciliates.- A Magic Pot : Self-assembly Computation Revisited.