Formal Languages and Applications

✍ Scribed by Dr. Carlos Martín-Vide, Dr. Victor Mitrana (auth.), Dr. Carlos Martín-Vide, Dr. Victor Mitrana, Dr. Gheorghe Păun (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2004
• Tongue: English
• Leaves: 611
• Series: Studies in Fuzziness and Soft Computing 148
• Edition: 1
• Category: Library

✦ Synopsis

"Formal Languages and Applications" provides an overall course-aid and self-study material for graduates students and researchers in formal language theory and its applications. The main results and techniques are presented in an easily accessible way accompanied with many references and directions for further research. This carefully edited monograph is intended to be the gate to formal language theory and its applications and is very useful as a general source of information in formal language theory.

✦ Table of Contents

Front Matter....Pages i-viii
Basic Notation and Terminology....Pages 1-9
Formal Languages: Foundations, Prehistory, Sources, and Applications....Pages 11-54
Finite Automata....Pages 55-85
Regular Grammars and Languages....Pages 87-96
Context-Free Languages....Pages 97-116
Pushdown Automata....Pages 117-138
On Context-Sensitive Grammars....Pages 139-161
Mildly Context-Sensitive Grammars....Pages 163-173
Parallel Grammars: A Short Phenomenology....Pages 175-182
Equational Axioms for a Theory of Automata....Pages 183-196
Turing Machines: Universality and Limits of Computational Power....Pages 197-225
Computational Complexity....Pages 227-247
Grammars With Regulated Rewriting....Pages 249-273
Grammar Systems....Pages 275-310
Eco-Grammar Systems....Pages 311-322
Miracles, Colonies, and Emergence....Pages 323-333
Marcus Contextual Grammars....Pages 335-366
Patterns....Pages 367-379
Combinatorics on Words....Pages 381-392
Combinatorics on Infinite Words....Pages 393-410
Finite Tree Automata and Regular Tree Languages. An Introduction....Pages 411-425
Two-Dimensional Languages....Pages 427-437
String Models and String Theories....Pages 439-456
Developmental Languages Versus DNA Computing....Pages 457-469
Membrane Computing....Pages 471-491
Dialogues on Quantum Computing....Pages 493-505
Grammatical Inference and Learning....Pages 507-528
Tabular Parsing....Pages 529-549
Weighted Finite-State Transducer Algorithms. An Overview....Pages 551-563
Text Searching: Theory and Practice....Pages 565-597
Cryptography: Basic Theory and Practice....Pages 599-620

✦ Subjects

Appl.Mathematics/Computational Methods of Engineering; Artificial Intelligence (incl. Robotics); Language Translation and Linguistics; Mathematical Logic and Foundations