Grammars and Automata for String Processing

viii
Preface ix

Gheorghe P un and the Windmill Curiosity 1
Marloes Boon-van der Nat and Grzegorz Rozenberg

I. GRAMMARS AND GRAMMAR SYSTEMS

Animal Farm: An Eco-Grammar System 9
Maurice H.ter Beek
Towards a Brain Compatible Theory of Syntax Based on
Local Testability 17
Stefano Crespi Reghizzi and Valentino Braitenberg
The Power and Limitations of Random Context 33
Sigrid Ewert and Andries van der Walt
Parsing Contextual Grammars with Linear, Regular and
Context-Free Selectors 45
Karin Harbusch
Linguistic Grammar Systems: A Grammar Systems Approach
for Natural Language 55
M.Dolores Jiménez-López
Multi-Bracketed Contextual Rewriting Grammars with
Obligatory Rewriting 67
Martin Kappes
Semi-Top-Down Syntax Analysis 77
Jaroslav Král and Michal Žemlicka
Descriptional Complexity of Multi-Parallel Grammars
with Respect to the Number of Nonterminals 91
Alexander Meduna and Dušan Kolár
On the Generative Capacity of Parallel Communicating
Extended Lindenmayer Systems 99
György Vaszil
C
II. AUTOMATA

Cellular Automata and Probabilistic L Systems:
An Example in Ecology 111
Manuel Alfonseca, Alfonso Ortega and Alberto Suárez
On Iterated Sequential Transducers 121
Henning Bordihn, Henning Fernau and Markus Holzer
Distributed Real-Time Automata 131
Catalin Dima
On Commutative Directable Nondeterministic Automata 141
Balázs Imreh, Masami Ito and Magnus Steinby
Testing Non-Deterministic X-Machines 151
Florentin Ipate and Mike Holcombe
Note on Minimal Automata and Uniform Communication Protocols 163
Galina Jirásková
On Universal Finite Automata and a-Transducers 171
Manfred Kudlek
Electronic Dictionaries and Acyclic Finite-State Automata:
A State of the Art 177
Denis Maurel
A New Recursive Incremental Algorithm for Building Minimal
Acyclic Deterministic Finite Automata 189
Bruce W.Watson

III. LOGICS, LANGUAGES AND COMBINATORICS

Syntactic Calculus and Pregroups 203
Wojciech Buszkowski
Homomorphic Characterizations of Linear and Algebraic Languages 215
Virgil E.Cazanescu and Manfred Kudlek
Using Alternating Words to Describe Symbolic Pictures 225
Gennaro Costagliola, Vincenzo Deufemia, Filomena Ferrucci,
Carmine Gravino and Marianna Salurso
What Is the Abelian Analogue of Dejean’s Conjecture? 237
James D.Currie
Threshold Locally Testable Languages in Strict Sense 243
Pedro García and José Ruiz
Characterizations of Language Classes: Universal Grammars,
Dyck Reductions, and Homomorphisms 253
Sadaki Hirose and Satoshi Okawa
On D0L Power Series over Various Semirings 263
Juha Honkala
The World of Unary Languages: A Quick Tour 275
Carlo Mereghetti and Giovanni Pighizzini
A New Universal Logic Element for Reversible Computing 285
Kenichi Morita
Church-Rosser Languages and Their Relationship to Other
Language Classes 295
Gundula Niemann and Friedrich Otto
Hiding Regular Languages 305
Valtteri Niemi
On the Difference Problem for Semilinear Power Series 317
Ion Petre
On Spatial Reasoning via Rough Mereology 327
Languages and Problem Specification 337
Loutfi Soufi
The Identities of Local Threshold Testability 347
Avraam N.Trakhtman

IV. MODELS OF MOLECULAR COMPUTING

Soft Computing Modeling of Microbial Metabolism 359
Ruxandra Chiurtu, Alexandru Agapie, Manuela Buzoianu,
Florin Oltean, Marius Giuclea and Roxana Vasilco
DNA Hybridization, Shifts of Finite Type, and Tiling of the Integers 369
Ethan M.Coven and Nataša Jonoska
Generalized Homogeneous P-Systems 381
Rudolf Freund and Franziska Freund
Crossing-Over on Languages: A Formal Representation of
Chromosomes Recombination 391
Lucian Ilie and Victor Mitrana
Restricted Concatenation Inspired by DNA Strand Assembly 403
Carlos Martín-Vide and Alfonso Rodríguez-Patón
DNA Tree Structures 413
George Rahonis
Lech Polkowski

Another The Core of CS Books
Download