New Trends in Formal Languages

1. Front Matter

   PDF

2. A grammatical approach to the LBA problem

   • Henning Bordihn

   Pages 1-9

3. Conditional context-free languages of finite index

   • Henning Fernau, Markus Holzer

   Pages 10-26

4. On the number of nonterminals in matrix grammars with leftmost derivations

   • Alexander Meduna

   Pages 27-38

5. The accepting power of finite automata over groups

   • Victor Mitrana, Ralf Stiebe

   Pages 39-48

6. Controlled fuzzy parallel rewriting

   • Peter R. J. Asveld

   Pages 49-70

7. On controlling rewriting by properties of strings and symbols

   • Paolo Bottoni, Giancarlo Mauri, Piero Mussio

   Pages 71-94

8. Accepting array grammars with control mechanisms

   • Henning Fernau, Rudolf Freund

   Pages 95-118

9. On restarting automata with rewriting

   • Petr Jančar, František Mráz, Martin Plátek, Jörg Vogel

   Pages 119-136

10. Deterministic cooperating distributed grammar systems

    • Valeria Mihalache, Victor Mitrana

    Pages 137-149

11. Grammar systems with counting derivation and dynamical priorities

    • Tudor Bălănescu, Horia Georgescu, Marian Gheorghe

    Pages 150-166

12. Characterization of RE using CD grammar systems with two registers and RL rules

    • Sorina Dumitrescu

    Pages 167-177

13. On cooperating distributed uniformly limited 0L systems

    • Dietmar Wätjen

    Pages 178-196

14. Teams in grammar systems: Sub-context-free cases

    • Maurice H. ter Beek

    Pages 197-216

15. A note on the incomparability of the E0L family with certain families of languages generated by cooperating grammar systems

    • Mohamed Amin

    Pages 217-219

16. Colonies as models of reactive systems

    • Jozef Kelemen

    Pages 220-235

17. Grammatical inference of colonies

    • Petr Sosík, Leoš Štýbnar

    Pages 236-246

18. A grammar characterization of logarithmic-space computation

    • Karl Abrahamson, Liming Cai, Steve Gordon

    Pages 247-255

19. On the computational complexity of context-free Parallel Communicating Grammar Systems

    • Stefan Bruda

    Pages 256-266

20. Parallel communicating grammar systems with communication by signals

    • Daniel Popescu

    Pages 267-277

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.

• Formale Sprache
• Fuzzy
• Grammatik-Systeme
• Natural
• Regulierte Ersetzung
• Verteilte Grammatiken
• automata
• communication
• complexity
• distributed grammars
• formal language
• formal languages
• grammar systems
• regulated rewriting

Policies and ethics