Grammars and automata for string processing: from mathematics and computer science to biology, and back

Carlos Martin-Vide, Victor Mitrana9780415298858, 0415298857

The volume discusses issues at the crossroads of molecular biology, linguistics, computer science and mathematics. The first section contains papers related to one of the fundamental concepts of the theory of formal languages, namely that of grammar. Results are presented in ‘classical’ as well as new and modern areas of grammar theory. The automation concept of the theory of formal languages is discussed in the second section: different types of automata are investigated either in search of new theoretical properties or for potential applications in software engineering, linguistics and ecology. The third section discusses languages for picture descriptions, semilinear and DOL power series, relationships between different classes of languages and the languages associated with rewriting systems. The last section is devoted to computing with molecules, and both experiments and theoretical models are described. Operations inspired by gene recombination and DNA strand assembly are considered as formal operations on strings and languages.