New Developments in Formal Languages and Applications

1. Front Matter

   Pages i-vii

   PDF

2. Basic Notation and Terminology

   Pages 1-9

3. Open Problems on Partial Words

   • Francine Blanchet-Sadri

   Pages 11-58

4. Alignments and Approximate String Matching

   • Maxime Crochemore, Thierry Lecroq

   Pages 59-93

5. An Introductory Course on Communication Complexity

   • Carsten Damm

   Pages 95-123

6. Formal Languages and Concurrent Behaviours

   • Jetty Kleijn, Maciej Koutny

   Pages 125-182

7. Cellular Automata – A Computational Point of View

   • Martin Kutrib

   Pages 183-227

8. Probabilistic Parsing

   • Mark-Jan Nederhof, Giorgio Satta

   Pages 229-258

9. DNA-Based Memories: A Survey

   • Andrew J. Neel, Max H. Garzon

   Pages 259-275

The theory of formal languages is widely recognized as the backbone of theoretical computer science, originating from mathematics and generative linguistics, among others. As a foundational discipline, formal language theory concepts and techniques are present in a variety of theoretical and applied fields of contemporary research which are concerned with symbol manipulation: discrete mathematics, bioinformatics, natural language processing, pattern recognition, text retrieval, learning, cryptography, compression, etc. This volume presents the main results of some recent, quickly developing subfields of formal language theory in an easily accessible way and provides the reader with extensive bibliographical references to go deeper. Open problems are formulated too. The intended audience consists of undergraduates and graduates in computer science or mathematics. Graduates in other disciplines (linguistics, electrical engineering, molecular biology, logic) with some basic level of mathematical maturity may find the volume appealing and useful too. The book represents 'a gate to formal language theory and its applications' and a source of information in computation theory in general. This volume is complementary of the volumes in the Springer series Studies in Fuzziness and Soft Computing, number 148, and Studies in Computational Intelligence, 25.

• Parsing
• Problem solving
• artificial life
• automata
• communication
• complexity
• computational intelligence
• computer graphics
• formal language
• formal languages
• fuzziness
• intelligence
• linguistics
• mathematical logic
• mathematics

• Research Group on Mathematical Linguistics, Rovira i Virgili University, Spain

  Gemma Bel-Enguix, M. Dolores Jiménez-López, Carlos Martín-Vide

Policies and ethics