+612 9045 4394
New Trends in Formal Languages : Control, Cooperation, and Combinatorics - Gheorghe Paun

New Trends in Formal Languages

Control, Cooperation, and Combinatorics

By: Gheorghe Paun (Editor), Arto Salomaa (Editor)

Paperback Published: 9th April 1997
ISBN: 9783540628446
Number Of Pages: 474

Share This Book:


or 4 easy payments of $39.60 with Learn more
Ships in 5 to 9 business days

This book presents a collection of refereed papers on formal language theory arranged for the occasion of the 50th birthday of Jurgen 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.

Regulated Rewritingp. 1
A Grammatical Approach to the LBA Problemp. 1
Conditional Context-Free Languages of Finite Indexp. 10
On the Number of Nonterminals in Matrix Grammars with Leftmost Derivationsp. 27
The Accepting Power of Finite Automata over Groupsp. 39
Controlled Fuzzy Parallel Rewritingp. 49
On Controlling Rewriting by Properties of Strings and Symbolsp. 71
Accepting Array Grammars with Control Mechanismsp. 95
On Restarting Automata with Rewritingp. 119
Cooperating Distributed Grammar Systemsp. 137
Deterministic Cooperating Distributed Grammar Systemsp. 137
Grammar Systems with Counting Derivation and Dynamical Prioritiesp. 150
Characterization of RE Using CD Grammar Systems with Two Registers and RL Rulesp. 167
On Cooperating Distributed Uniformly Limited 0L Systemsp. 178
Teams in Grammar Systems: Sub-Context-Free Casesp. 197
A Note on the Incomparability of the EOL Family with Certain Families of Languages Generated by Cooperating Grammar Systemsp. 217
Colonies as Models of Reactive Systemsp. 220
Grammatical Inference of Coloniesp. 236
Parallel Communicating Grammar Systemsp. 247
A Grammar Characterization of Logarithmic-Space Computationp. 247
On the Computational Complexity of Context-Free Parallel Communicating Grammar Systemsp. 256
Parallel Communicating Grammar Systems with Communication by Signalsp. 267
PC Grammar Systems Versus Some Non-Context-Free Constructions from Natural and Artificial Languagesp. 278
Grammar Systems for the Description of Certain Natural Language Factsp. 288
Networks of Parallel Language Processorsp. 299
Splicing Systemsp. 319
A Reduced Distributed Splicing System for RE Languagesp. 319
On the Generative Capacity of Splicing Grammar Systemsp. 330
Array Splicing Systemsp. 346
Infinite Wordsp. 366
Two Lower Bounds on Computational Complexity of Infinite Wordsp. 366
On [omega]-power Languagesp. 377
Shuffle-Like Operations on [omega]-wordsp. 395
Algebraic Approaches to Languagesp. 412
Generalized Lindenmayerian Algebraic Systemsp. 412
The Structure of the Basic Morphismsp. 422
On Mix Operationp. 430
On the Complexity of Iterated Insertionsp. 440
The Decidability of the Generalized Confluence Problem for Context-Free Languagesp. 454
Author Indexp. 465
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540628446
ISBN-10: 3540628444
Series: Lecture Notes in Computer Science,
Audience: General
Format: Paperback
Language: English
Number Of Pages: 474
Published: 9th April 1997
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 2.46
Weight (kg): 0.67