Ebook: Where Mathematics, Computer Science, Linguistics and Biology Meet: Essays in honour of Gheorghe Păun

In the last years, it was observed an increasing interest of computer scientists in the structure of biological molecules and the way how they can be manipulated in vitro in order to define theoretical models of computation based on genetic engineering tools. Along the same lines, a parallel interest is growing regarding the process of evolution of living organisms. Much of the current data for genomes are expressed in the form of maps which are now becoming available and permit the study of the evolution of organisms at the scale of genome for the first time. On the other hand, there is an active trend nowadays throughout the field of computational biology toward abstracted, hierarchical views of biological sequences, which is very much in the spirit of computational linguistics. In the last decades, results and methods in the field of formal language theory that might be applied to the description of biological sequences were pointed out.

---

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.

---

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.
Content:
Front Matter....Pages i-xv
The Games of His Life....Pages 1-10
Front Matter....Pages 11-11
Deterministic Stream X-Machines Based on Grammar Systems....Pages 13-23
Some Ghosts that Arise in a Spliced Linguistic String: Evidence from Catalan....Pages 25-35
On Size Complexity of Context-Free Returning Parallel Communicating Grammar Systems....Pages 37-49
Subregularly Controlled Derivations: Restrictions by Syntactic Parameters....Pages 51-61
Neo-Modularity and Colonies....Pages 63-74
Sewing Contexts and Mildly Context-Sensitive Languages....Pages 75-84
Towards Grammars of Decision Algorithms....Pages 85-95
Front Matter....Pages 97-97
Computational Complementarity for Probabilistic Automata....Pages 99-113
Acceptance of ?-Languages by Communicating Deterministic Turing Machines....Pages 115-125
Counter Machines and the Safety and Disjointness Problems for Database Queries with Linear Constraints....Pages 127-137
Automata Arrays and Context-Free Languages....Pages 139-148
On Special Forms of Restarting Automata....Pages 149-160
The Time Dimension of Computation Models....Pages 161-172
Front Matter....Pages 173-173
An Infinite Sequence of Full AFL-Structures, Each of Which Possesses an Infinite Hierarchy....Pages 175-186
Trellis Languages....Pages 187-198
Pictures, Layers, Double Stranded Molecules: On Multi-Dimensional Sentences....Pages 199-209
Transduction in Polypodes....Pages 211-218
Some Algebraic Properties of Contexts and Their Applications to Contextual Languages....Pages 219-226
On Fatou Properties of Rational Languages....Pages 227-235
Front Matter....Pages 173-173
Multiple Keyword Patterns in Context-Free Languages....Pages 237-241
Reading Words in Graphs Generated by Hyperedge Replacement....Pages 243-252
Regularly Controlled Formal Power Series....Pages 253-265
Forbidden Subsequences and Permutations Sortable on Two Parallel Stacks....Pages 267-275
Approximate Identification and Finite Elasticity....Pages 277-286
Insertion of Languages and Differential Semirings....Pages 287-296
Front Matter....Pages 297-297
Molecular Structures....Pages 299-317
A Characterization of Non-Iterated Splicing with Regular Rules....Pages 319-327
Universal and Simple Operations for Gene Assembly in Ciliates....Pages 329-342
Semi-Simple Splicing Systems....Pages 343-352
Writing by Methylation Proposed for Aqueous Computing....Pages 353-360
Context-Free Recombinations....Pages 361-375
Simplified Simple H Systems....Pages 377-386
On Some Forms of Splicing....Pages 387-398
Time-Varying Distributed H-Systems of Degree 2 Generate All Recursively Enumerable Languages....Pages 399-407
On Membrane Computing Based on Splicing....Pages 409-422
Is Evolutionary Computation Using DNA Strands Feasible?....Pages 423-434
Splicing Systems Using Merge and Separate Operations....Pages 435-446

---

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.
Content:
Front Matter....Pages i-xv
The Games of His Life....Pages 1-10
Front Matter....Pages 11-11
Deterministic Stream X-Machines Based on Grammar Systems....Pages 13-23
Some Ghosts that Arise in a Spliced Linguistic String: Evidence from Catalan....Pages 25-35
On Size Complexity of Context-Free Returning Parallel Communicating Grammar Systems....Pages 37-49
Subregularly Controlled Derivations: Restrictions by Syntactic Parameters....Pages 51-61
Neo-Modularity and Colonies....Pages 63-74
Sewing Contexts and Mildly Context-Sensitive Languages....Pages 75-84
Towards Grammars of Decision Algorithms....Pages 85-95
Front Matter....Pages 97-97
Computational Complementarity for Probabilistic Automata....Pages 99-113
Acceptance of ?-Languages by Communicating Deterministic Turing Machines....Pages 115-125
Counter Machines and the Safety and Disjointness Problems for Database Queries with Linear Constraints....Pages 127-137
Automata Arrays and Context-Free Languages....Pages 139-148
On Special Forms of Restarting Automata....Pages 149-160
The Time Dimension of Computation Models....Pages 161-172
Front Matter....Pages 173-173
An Infinite Sequence of Full AFL-Structures, Each of Which Possesses an Infinite Hierarchy....Pages 175-186
Trellis Languages....Pages 187-198
Pictures, Layers, Double Stranded Molecules: On Multi-Dimensional Sentences....Pages 199-209
Transduction in Polypodes....Pages 211-218
Some Algebraic Properties of Contexts and Their Applications to Contextual Languages....Pages 219-226
On Fatou Properties of Rational Languages....Pages 227-235
Front Matter....Pages 173-173
Multiple Keyword Patterns in Context-Free Languages....Pages 237-241
Reading Words in Graphs Generated by Hyperedge Replacement....Pages 243-252
Regularly Controlled Formal Power Series....Pages 253-265
Forbidden Subsequences and Permutations Sortable on Two Parallel Stacks....Pages 267-275
Approximate Identification and Finite Elasticity....Pages 277-286
Insertion of Languages and Differential Semirings....Pages 287-296
Front Matter....Pages 297-297
Molecular Structures....Pages 299-317
A Characterization of Non-Iterated Splicing with Regular Rules....Pages 319-327
Universal and Simple Operations for Gene Assembly in Ciliates....Pages 329-342
Semi-Simple Splicing Systems....Pages 343-352
Writing by Methylation Proposed for Aqueous Computing....Pages 353-360
Context-Free Recombinations....Pages 361-375
Simplified Simple H Systems....Pages 377-386
On Some Forms of Splicing....Pages 387-398
Time-Varying Distributed H-Systems of Degree 2 Generate All Recursively Enumerable Languages....Pages 399-407
On Membrane Computing Based on Splicing....Pages 409-422
Is Evolutionary Computation Using DNA Strands Feasible?....Pages 423-434
Splicing Systems Using Merge and Separate Operations....Pages 435-446
....