New Trends in Formal Languages: Control, Cooperation, and Combinatorics

Henning Bordihn (auth.), Gheorghe Păun, Arto Salomaa (eds.)3540628444, 9783540628446

This book presents a collection of refereed papers on formal language theory arranged for the occasion of the 50th birthday of Jürgen Dassow, who has made a significant contribution to the areas of regulated rewriting and grammar systems.
The volume comprises 33 revised full papers organized in sections on regulated rewriting, cooperating distributed grammar systems, parallel communicating grammar systems, splicing systems, infinite words, and algebraic approaches to languages.

---

Table of contents :
A grammatical approach to the LBA problem….Pages 1-9
Conditional context-free languages of finite index….Pages 10-26
On the number of nonterminals in matrix grammars with leftmost derivations….Pages 27-38
The accepting power of finite automata over groups….Pages 39-48
Controlled fuzzy parallel rewriting….Pages 49-70
On controlling rewriting by properties of strings and symbols….Pages 71-94
Accepting array grammars with control mechanisms….Pages 95-118
On restarting automata with rewriting….Pages 119-136
Deterministic cooperating distributed grammar systems….Pages 137-149
Grammar systems with counting derivation and dynamical priorities….Pages 150-166
Characterization of RE using CD grammar systems with two registers and RL rules….Pages 167-177
On cooperating distributed uniformly limited 0L systems….Pages 178-196
Teams in grammar systems: Sub-context-free cases….Pages 197-216
A note on the incomparability of the E0L family with certain families of languages generated by cooperating grammar systems….Pages 217-219
Colonies as models of reactive systems….Pages 220-235
Grammatical inference of colonies….Pages 236-246
A grammar characterization of logarithmic-space computation….Pages 247-255
On the computational complexity of context-free Parallel Communicating Grammar Systems….Pages 256-266
Parallel communicating grammar systems with communication by signals….Pages 267-277
PC grammar systems versus some non-context-free constructions from natural and artificial languages….Pages 278-287
Grammar systems for the description of certain natural language facts….Pages 288-298
Networks of parallel language processors….Pages 299-318
A reduced distributed splicing system for RE languages….Pages 319-329
On the generative capacity of splicing grammar systems….Pages 330-345
Array splicing systems….Pages 346-365
Two lower bounds on computational complexity of infinite words….Pages 366-376
On ω-power languages….Pages 377-394
Shuffle-like operations on ω-words….Pages 395-411
Generalized Lindenmayerian algebraic systems….Pages 412-421
The structure of the basic morphisms….Pages 422-429
On mix operation….Pages 430-439
On the complexity of iterated insertions….Pages 440-453
The decidability of the generalized confluence problem for context-free languages….Pages 454-464