Synopses & Reviews
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.
Synopsis
The theory of formal languages is widely accepted as the backbone of t- oretical computer science. It mainly originated from mathematics (com- natorics, algebra, mathematical logic) and generative linguistics. Later, new specializations emerged from areas ofeither computer science(concurrent and distributed systems, computer graphics, arti?cial life), biology (plant devel- ment, molecular genetics), linguistics (parsing, text searching), or mathem- ics (cryptography). All human problem solving capabilities can be considered, in a certain sense, as a manipulation of symbols and structures composed by symbols, which is actually the stem of formal language theory. Language - in its two basic forms, natural and arti?cial - is a particular case of a symbol system. This wide range of motivations and inspirations explains the diverse - plicability of formal language theory ? and all these together explain the very large number of monographs and collective volumes dealing with formal language theory. In 2004 Springer-Verlag published the volume Formal Languages and - plications, edited by C. Martin-Vide, V. Mitrana and G. P?un in the series Studies in Fuzziness and Soft Computing 148, which was aimed at serving as an overall course-aid and self-study material especially for PhD students in formal language theory and applications. Actually, the volume emerged in such a context: it contains the core information from many of the lectures - livered to the students of the International PhD School in Formal Languages and Applications organized since 2002 by the Research Group on Mathem- ical Linguistics from Rovira i Virgili University, Tarragona, Spain.
Table of Contents
Basic Notation and Terminology.- Open Problems on Partial Words.- Alignments and Approximate String Matching.- An Introductory Course on Communication Complexity.- Formal Languages and Concurrent Behaviours.- Cellular Automata - A Computational Point of View.- Probabilistic Parsing.- DNA-Based Memories: A Survey.