Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and back
This is a collection of 40 articles written in honour of Gheorghe Paun on the occasion of his 50th birthday. The first part (Grammars and grammar systems) treats contextual grammars, descriptional complexity, parsability approaches for contextual grammars and context-free grammars, and the power of limitation of regulated rewriting in image generation. The second part (Automata) is concerned with probabilistic cellular automata, directable automata, X-machines, finite automata and real-time automata. There are applications in software engineering, linguistics and ecology. The third part (Logics, languages and combinatorics) treats homomorphic characterisations of the language classes in the Chomsky hierarchy, languages for picture descriptions, semilinear power series and DOL power series, unary languages, relationships between different classes of languages, and the languages associated with rewriting systems. The last part (Models of molecular computing) presents models of metabolic reactions in bacteria, entropies of DNA-based computing models, Adelman’s model, splicing systems, and tiling shifts.