Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   

Поиск по указателям

Rozenberg G., Salomaa A. — The mathematical theory of L systems
Rozenberg G., Salomaa A. — The mathematical theory of L systems

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: The mathematical theory of L systems

Авторы: Rozenberg G., Salomaa A.


Formal language theory is by its very essence an interdisciplinary area of science: the need for a formal grammatical or machine description of specific languages arises in various scientific disciplines. Therefore, influences from outside the mathematical theory itself have often enriched the theory of formal languages.
Perhaps the most prominent example of such an outside stimulation is provided by the theory of L systems. L systems were originated by Aristid Lindenmayer in connection with biological considerations in 1968. Two main novel features brought about by the theory of L systems from its very beginning are (i)parallelism in the rewriting process-due originally to the fact that languages were applied to model biological development in which parts of the developing organism change simultaneously, and (ii) the notion of a grammar conceived as a description of a dynamic process (taking place in time), rather than a static one. The latter feature initiated an intensive study of sequences (in contrast to sets) of words, as well as of grammars without nonterminal letters. The results obtained in the very vigorous initial period-up to 1974-were covered in the monograph "Developmental Systems and Languages" by G. Herman and G. Rozenberg (North-Holland, 1975).
Since this initial period, research in the area of L systems has continued to be very active. Indeed, the theory of L systems constitutes today a considerable body of mathematical knowledge. The purpose of this monograph is to present in a systematic way the essentials of the mathematical theory of L systems. The material common to the present monograph and that of Herman and Rozenberg quoted above consists only of a few basic notions and results. This is an indication of the dynamic growth in this research area, as well as of the fact that the present monograph focuses attention on systems without interactions, i.e., context-independent rewriting.
The organization of this book corresponds to the systematic and mathematically very natural structure behind L systems: the main part of the book (the first five chapters) deals with one or several iterated morphisms and one or several iterated finite substitutions. The last chapter, written in an overview style, gives a brief survey of the most important areas within L systems not directly falling within the basic framework discussed in detail in the first five chapters.
Today, L systems constitute a theory rich in original results and novel techniques, and yet expressible within a very basic mathematical framework. It has not only enriched the theory of formal languages but has also been able to put the latter theory in a totally new perspective. This is a point we especially hope to convince the reader of. It is our firm opinion that nowadays a formal language theory course that does not present L systems misses some of the very essential points in the area. Indeed, a course in formal language theory can be based on the mathematical framework presented in this book because the traditional areas of the theory, such as context-free languages, have their natural counterparts within this framework. On the other hand, there is no way of presenting iterated morphisms or parallel rewriting in a natural way within the framework of sequential rewriting.
No previous knowledge of the subject is required on the part of the reader, and the book is largely self-contained. However, familiarity with the basics of automata and formal language theory will be helpful. The results needed from these areas will be summarized in the introduction. Our level of presentation corresponds to that of graduate or advanced undergraduate work.
Although the book is intended primarily for computer scientists and mathematicians, students and researchers in other areas applying formal language theory should find it useful. In particular, theoretical biologists should find it interesting because a number of the basic notions were originally based on ideas in developmental biology or can be interpreted in terms of developmental biology. However, more detailed discussion of the biological aspects lies outside the scope of this book. The interested reader will find some references in connection with the bibliographical remarks in this book.
The discussion of the four areas within the basic framework studied in this book (single or several iterated morphisms or finite substitutions) builds up the theory starting from the simple and proceeding to more complicated objects. However, the material is organized in such a way that each of the four areas can also be studied independently of the others, with the possible exception of a few results needed in some proofs. In particular. a mathematically minded reader might find the study of single iterated morphisms (Chapters 1 and 111) a very interesting topic in its own right. It is an area where very intriguing and mathematically significant problems can be stated briefly ab ova.
Exercises form an important part of the book. Many of them survey topics not included in the text itself. Because some exercises are rather difficult, the reader may wish to consult the reference works cited. Many open research problems are also mentioned throughout the text. Finally, the book contains references to the existing literature both at the end and scattered elsewhere. These references are intended to aid the reader rather than to credit each result to some specific author(s).

Read more at http://ebookee.org/Grzegorz-Rozenberg-The-Mathematical-Theory-of-L-Systems_622209.html#Uxf6QhFklpuBFloE.99

Язык: en

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1980

Количество страниц: 369

Добавлена в каталог: 09.12.2014

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
Предметный указатель
$\Theta$-determined language      84
Active normal form      262
Adult alphabet      72
Adult language      71
AFL      7
AFL, full      7
Alphabet      1
Ambiguity      60
Anti-AFL      7
Antiarithmetic family of languages      258
Automaton      5
Automaton, auxiliary pushdown      311
Automaton, cs-pd      301
Automaton, deterministic cs-pd      303
Automaton, finite deterministic      5
Automaton, finite nondeterministie      6
Automaton, pac      308
Automaton, pap      305
Balance of homomorphisms      122
Balance of homomorphisms, bounded      123
Balanced decomposition      90
Binary propagating map OL system      332
Catenation      2
Catenation closure      2
CGP system      325
Chomsky hierarchy      4
CLUSTERED      98 248
Code      129
Code with bounded delay      130
Coding      2
COL system      62
Compatible homomorphisms      122
Complete EOL form      113
Complete twin shuffle      151
complexity      310
Cone      7
Control word      190
Covered      22
cross      2
Cut      14
Decomposition of FPOL system      93
Decomposition of FPOL system, well-sliced      93
Decomposition of sequences      17 155
density      223
Dependence graph      28
Derivation      45 190 233
dfl-substitution      105
dgsm mapping      145
dgsm mapping, reverse      145
dgsm mapping, symmetric      145
DOL equivalence problem      12
DOL form      177
DOL form, form equivalence      177
DOL form, sequence equivalence      177
DOL system      10
DOL system, conservative      17
DOL system, everywhere growing      213
DOL system, injective      24
DOL system, reduced      16
DOL system, uniformly growing      213
DTOL function      215
DTOL function, communative      218
DTOL system      188
EDTOL system      191
EIL form      289
Elementary homomorphism      17
Empty word      1
Endomorphism      2
EOL form      107
EOL form, bad      115
EOL form, complete      113
EOL form, good      115
EOL form, good relative to      116
EOL form, mutually good      116
EOL form, synchronized      111
EOL form, vomplete      115
EOL system      54
Equal homomorphisms      122
Equal homomorphisms, ultimately equal      122
Equality language      122 144
ETOL system      235
ETOL system of finite index      263
ETOL system of finite tree rank      279
ETOL system of uncontrolled finite index      263
ETOL system with rank      278
ETOL system, synchronized      239
Exhaustive language      253
Existential spectrum      52 66
Finite index normal form      267
Fixed point language      144
Form equivalence      107 289
Form equivalence, strict      107
Fragmentation      78
Generalized sequential machine      7
Generating function      33
Grammar      3
Grammar, context-free      4
Grammar, context-sensitive      4
Grammar, finite index      205
Grammar, Indian parallel      192
Grammar, iteration      293
Grammar, linear      4
grammar, regular      4
Grammar, type i      4
Growth equivalence      35 216
Growth function      30 289
Growth order      161
Growth relation      90
Growth relation, deterministic      90
Growth relation, exponential      90
Growth relation, limited      90
Growth relation, polynomial type      90
gsm mapping      7
Height of derivation      45 190
Hilbert's tenth problem      8
Homomorphism      2
Homomorphism, $\Lambda$-free      2
Homomorphism, elementary      17
Homomorphism, inverse      2
Homomorphism, nonerasing      2
Homomorphism, simplifiable      17
Homomorphism, type of      253
Hyper-AFL      296
Hyper-AFL, full      296
Hyperalgebraic extension      294
Hypersentential extension      298
IL system      281
Improductive occurrence      46
Interpretation      107 177
Interpretation, uniform      117
Isomorphic sequences      178
Isomorphic sequences, ultimately isomorphic      178
Iteration grammar      293
Iteration grammar, deterministic      299
Iteration grammar, m-restricted      293
Iteration grammar, morphic      293
Iteration grammar, propagating      293
Iteration grammar, sentential      293
k-equivalent      249
Kleene plus      2
Kleene star      2
Language      2
Language, arithmetic      258
Language, bounded      205
Language, context-free      4
Language, context-sensitive      4
Language, DOL      11
Language, DTOL      188
Language, EDTOL      191
Language, EIL      285
Language, elementary      127
Language, EOL      54
Language, ETOL      235
Language, IL      281
Language, linear      4
Language, OL      44
Language, PDOL      11
Language, prefix-free      143
Language, recursively enumerable      4
Language, regular      4
Language, TOL      231
LBA problem      6
Length density      223
Length of derivation      45 190
Length of word      1
Length set      4
letter      1
Letter, bad      184
Letter, good      184
Linear set      5
Locally catenative      14
Locally catenative of some depth      24
Locally catenative of some width      27
Locally catenative, DOL system      14
Loose COL system      69
Macro system      61
Matrix of trees      194
Matrix of trees, well-formed      195
Merging of sequences      17 155
Mirror image      3
Morphism      see "Homomorphism"
N-rational      32 215
Neat subderivation      193
Neatly synchronized      85
Nonterminal      3 54
NP-complete      310
Occurrence of letter, big      193
Occurrence of letter, expansive      203
Occurrence of letter, multiple      193
Occurrence of letter, nonrecursive      193
Occurrence of letter, recursive      193
Occurrence of letter, small      193
Occurrence of letter, unique      193
OL system      43
OL system with finite axiom set      70
Parikh mapping      5
Parikh set      5
Parikh vector      5
PDOL form      177
PDOL system      11
Polynomially bounded      39 227
Post Correspondence Problem      8
Pre-quasoid      294
Prefix      2 207
Prefix balance      146
Production      3
Productive occurrence      46
propagating      11 44
Propagating graph OL system      317
Quasiquotiem      167
Quasoid      294
Rational transduction      7
Recurrence system      61
Regular expression      5
Regular operation      5
Rewriting form      105
Rewriting system      3
Semihomogeneous      312
Semilinear set      5
Sentential form      4
Sequential transducer      6
Shift of functions      163 167
Shift of sequence      26
Shuffle      249
Slicing      51
Slow function      197
Speed-up of EOL system      59
Strictly growing PDOL form      179
Subderivation      190
Subderivation, neat      193
Substitution      2
Substitution, $\Lambda$-free      2
Substitution, arithmetic      258
Substitution, dfl      105
Substitution, finite      2
Subword      1
Subword, final      2
Subword, initial      2
Suffix      2 207
Symmetric pair      145
Synchronization symbol      57 239
Synchronized      56 111 239
t-counting language      93
t-disjoint decomposition      90
table      188 231
Terminal      3
Tight COL system      69
TOL system      231
Trace of derivation      45 190 233
Turing machine      6
Ultimately exponential      39
Unary OL system      59
Universal spectrum      52
Vomplete EOL form      115
Word      1
Word, f-random      197
Yield relation      3
Z-rational      32 215
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2022
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте