Grammars and Automata for String Processing: From Mathematics and Computer Science to Biology, and Back Book

	Contributing Authors
	Preface
	Gheorghe Paun and the Windmill Curiosity	1
	Animal Farm: An Eco-Grammar System	9
	Towards a Brain Compatible Theory of Syntax Based on Local Testability	17
	The Power and Limitations of Random Context	33
	Parsing Contextual Grammars with Linear, Regular and Context-Free Selectors	45
	Linguistic Grammar Systems: A Grammar Systems Approach for Natural Languages	55
	Multi-Bracketed Contextual Rewriting Grammars with Obligatory Rewriting	67
	Semi-Top-Down Syntax Analysis	77
	Descriptional Complexity of Multi-Parallel Grammars with Respect to the Number of Nonterminals	91
	On the Generative Capacity of Parallel Communicating Extended Lindenmayer Systems	99
	Cellular Automata and Probabilistic L Systems: An Example in Ecology	111
	On Iterated Sequential Transducers	121
	Distributed Real-Time Automata	131
	On Commutative Directable Nondeterministic Automata	141
	Testing Non-Deterministic X-Machines	151
	Note on Minimal Automata and Uniform Communication Protocols	163
	On Universal Finite Automata and a-Transducers	171
	Electronic Dictionaries and Acyclic Finite-State Automata: A State of the Art	177
	A New Recursive Incremental Algorithm for Building Minimal Acyclic Deterministic Finite Automata	189
	Syntactic Calculus and Pregroups	203
	Homomorphic Characterizations of Linear and Algebraic Languages	215
	Using Alternating Words to Describe Symbolic Pictures	225
	What Is the Abelian Analogue of Dejean's Conjecture?	237
	Threshold Locally Testable Languages in Strict Sense	243
	Characterizations of Language Classes: Universal Grammars, Dyck Reductions, and Homomorphisms	253
	On DOL Power Series over Various Semirings	263
	The World of Unary Languages: A Quick Tour	275
	A New Universal Logic Element for Reversible Computing	285
	Church-Rosser Languages and Their Relationship to Other Language Classes	295
	Hiding Regular Languages	305
	On the Difference Problem for Semilinear Power Series	317
	On Spatial Reasoning via Rough Mereology	327
	Languages and Problem Specification	337
	The Identities of Local Threshold Testability	347
	Soft Computing Modeling of Microbial Metabolism	359
	DNA Hybridization, Shifts of Finite Type, and Tiling of the Integers	369
	Generalized Homogeneous P-Systems	381
	Crossing-Over on Languages: A Formal Representation of Chromosomes Recombination	391
	Restricted Concatenation Inspired by DNA Strand Assembly	403
	DNA Tree Structures	413