Where Mathematics, Computer Science, Linguistics and Biology Meet

by Martin-Vide, Carlos; Mitrana, Victor; Paun, Gheorghe

• ISBN13: 9780792366935
• ISBN10: 079236693X
• Format: Hardcover
• Copyright: 2000-12-01
• Publisher: Kluwer Academic Pub

Summary

There are not many interdisciplinary scientific fields as formal language theory. In this volume, it is presented as the very intersection point between Mathematics, Computer Science, Linguistics and Biology. The book is a collection of papers going deep into classical topics in computer science inspired formal languages, as well as other ones showing new concepts and problems motivated in linguistics and biology. The papers are organized in four sections: Grammars and Grammar Systems, Automata, Languages and Combinatorics, and Models of Molecular Computing. They clearly prove the power, wealth and vitality of the theory nowadays and sketch some trends for its future development. The volume is intended for an audience of computer scientists, computational linguists, theoretical biologists and any other people interested in dealing with the problems and challenges of interdisciplinarity.

Table of Contents

Preface	ix
Contributing Authors	xiii
The Games of His Life	1	(12)
Solomon Marcus
Part I GRAMMARS AND GRAMMAR SYSTEMS
Deterministic Stream X-Machines Based on Grammar Systems	13	(12)
Tudor Balanescu
Marian Gheorghe
Mike Holcombe
Some Ghosts that Arise in a Spliced Linguistic String: Evidence From Catalan	25	(12)
Gamma Bel-Enguix
On Size Complexity of Context-Free Returning Parallel Communicating Grammar Systems	37	(14)
Erzsebet Csuhaj-Varju
Subregularly Controlled Derivations: Restrictions by Syntactic Parameters	51	(12)
Jurgen Dassow
Neo-Modularity and Colonies	63	(12)
Jozef Kelemen
Alica Kelemenova
Victor Mitrana
Sewing Contexts and Mildly Context-Sensitive Languages	75	(10)
Carlos Martin-Vide
Alexandru Mateescu
Arto Salomaa
Towards Grammars of Decision Algorithms	85	(14)
Lech Polkowski
Andrzej Skowron
Part II AUTOMATA
Computational Complementarity for Probabilistic Automata	99	(16)
Cristian S. Calude
Elena Calude
Karl Svozil
Acceptance of w-Languages by Communicating Deterministic Turing Machines	115	(12)
Rudolf Freund
Ludwig Staiger
Counter Machines and the Safety and Disjointness Problems for Database Queries with Linear Constraints	127	(12)
Oscar H. Ibarra
Jianwen Su
Constantinos Bartzis
Automata Arrays and Context-Free Languages	139	(10)
Martin Kutrib
On Special Forms of Restarting Automata	149	(12)
Frantisek Mraz
Martin Platek
Martin Prochazka
The Time Dimension of Computation Models	161	(14)
Sheng Yu
Part III LANGUAGES AND COMBINATORICS
An Infinite Sequence of Full AFL-Structures, Each of Which Possesses an Infinite Hierarchy	175	(12)
Peter R. J. Asveld
Trellis Languages	187	(12)
Adrian Atanasiu
Pictures, Layers, Double Stranded Molecules: On Multi-Dimensional Sentences	199	(12)
Paolo Bottoni
Transduction in Polypodes	211	(8)
Symeon Bozapalidis
Some Algebraic Properties of Contexts and Their Applications to Contextual Languages	219	(8)
Rodica Ceterchi
On Fatou Properties of Rational Languages	227	(10)
Christian Choffrut
Juhani Karhumaki
Multiple Keyword Patterns in Context-Free Languages	237	(6)
Pal Domosi
Masami Ito
Reading Words in Graphs Generated by Hyperedge Replacement	243	(10)
Frank Drewes
Hans-Jorg Kreowski
Regularly Controlled Formal Power Series	253	(14)
Henning Fernau
Werner Kuich
Forbidden Subsequences and Permutations Sortable on Two Parallel Stacks	267	(10)
Tero Harju
Lucian Ilie
Approximate Identification and Finite Elasticity	277	(10)
Satoshi Kobayashi
Yasubumi Sakakibara
Takashi Yokomori
Insertion of Languages and Differential Semirings	287	(12)
Gabriel Thierrin
Part IV MODELS OF MOLECULAR COMPUTING
Molecular Structures	299	(20)
Gabriel Ciobanu
A Characterization of Non-Iterated Splicing with Regular Rules	319	(10)
Ray Dassen
Hendrik Jan Hoogeboom
Nike van Vugt
Universal and Simple Operations for Gene Assembly in Ciliates	329	(14)
Andrzej Ehrenfeucht
Ion Petre
David M. Prescott
Grzegorz Rozenberg
Semi-Simple Splicing Systems	343	(10)
Elizabeth Goode
Dennis Pixton
Writing By Methylation Proposed for Aqueous Computing	353	(8)
Tom Head
Context-Free Recombinations	361	(16)
Jarkko Kari
Lila Kari
Simplified Simple H Systems	377	(10)
Kamala Krithivasan
Arvind Arasu
On Some Forms of Splicing	387	(12)
Vincenzo Manca
Time-Varying Distributed H-Systems of Degree 2 Generate All Recursively Enumerable Languages	399	(10)
Maurice Margenstern
Yurii Rogozhin
On Membrane Computing Based on Splicing	409	(14)
Andrei Paun
Mihaela Paun
Is Evolutionary Computation Using DNA Strands Feasible?	423	(12)
Jose Rodrigo
Juan Castellanos
Fernando Arroyo
Luis Fernando Mingo
Splicing Systems Using Merge and Separate Operations	435
Claudio Zandron
Giancarlo Mauri
Claudio Ferretti
Paola Bonizzoni