Researchers in mathematics and computer science; This is an excellent collection of papers dealing with combinatorics on words, codes, semigroups, automata, languages, molecular computing, transducers, logics, etc., related to the impressive work of Gabriel Thierrin. This volume is in honor of Professor Thierrin on the occasion of his 80th birthday.
Author(s): Masami Ito, Gheorghe Paun, Sheng Yu
Edition: 1st
Year: 2002
Language: English
Pages: 455
Preface......Page 8
Contents......Page 10
1 Introduction......Page 13
2 Monoids Generated By Algebraic Closure Operators......Page 14
3 Some Simple Families of Fuzzy Languages......Page 16
4 A Technical Lemma......Page 18
5 The Main Results......Page 19
6 Concluding Remarks......Page 22
1 Preliminary concepts: linguistic units......Page 27
2 Theoretical basis of mixed links......Page 30
4 Features of mixed links......Page 31
5 Application of the link of level to basic ULPS......Page 32
6 Analysis of results......Page 33
7 Systematization of results......Page 35
8 Analysis of mixed links depending on the syntactic result of the rules......Page 36
9 Generative power of mixed systems......Page 41
2 Liar's Paradox......Page 45
3 Three Graphical Techniques: Web Cantor and Dragon......Page 47
4 Liar as a Demon......Page 48
5 Contrapositive Half and Minimalist Liars......Page 49
6 Unidirectional Time-Dependent Liar......Page 53
7 Bidirectional Time-Dependent Liar......Page 54
8 Codes......Page 55
1 Introduction......Page 59
2 Definitions and Basic Properties......Page 60
3 Hairpin and Loop Excision......Page 64
4 Further Work......Page 68
1 Introduction......Page 71
2 Definitions......Page 72
3 Restrictions by the Number of Nonterminals......Page 74
4 Restrictions by the Number of Productions......Page 75
1 Introduction and Basic Notions......Page 81
2 Penultimately Permutation Complete Digraphs......Page 83
3 Complete Classes of Directed Graphs......Page 88
4 Summary and Further Problems......Page 89
Circularity and Other Invariants of Gene Assembly in Ciliates......Page 93
1 Introduction......Page 94
2 DNA Molecules......Page 95
3 Gene Assembly in Ciliates......Page 96
4 Examples......Page 102
5 The Circularity Problem......Page 105
1 Introduction......Page 111
2 Conway semialgebras......Page 112
3 The main result......Page 120
4 Determinization......Page 121
5 Minimization......Page 122
6 Proof of the main result......Page 124
1 Introduction......Page 127
2 Forest Languages Related to Catenation Closed Pair......Page 128
3 Free Properties of Catenation Closed Pairs......Page 132
4 Forest Languages Related to Regular and Disjunctive Properties......Page 136
5 Some Well-Known Forest Languages......Page 138
1 Introduction......Page 141
2 Preliminaries......Page 142
3 Results......Page 144
4 Conclusion......Page 151
1 Introduction......Page 153
2 Preliminaries......Page 154
3 Isomorphic Completeness for MR......Page 156
4 Isomorhic Representation of n.d. Tree Automata......Page 160
1 Introduction......Page 167
2 General Preliminaries......Page 168
3 DR Tree Recognizers......Page 170
4 Path Languages and Path Closures......Page 171
5 Nerode Path Congruences......Page 172
6 Syntactic Path Monoids......Page 175
1 Introduction......Page 181
2 The Spectral Partition of A+ Induced by a Language L......Page 182
4 Languages on a Half Plane......Page 183
5 The Sketch Parameters of a Language......Page 187
6 Sketches of Regular Languages......Page 188
1 Introduction......Page 193
2 Definitions and Results......Page 194
3 Proofs......Page 196
1 Introduction......Page 201
2 Slenderness......Page 202
3 Dyck Loops......Page 204
5 Characterization of Parikh fc-Poly-Slenderness......Page 205
6 Decidability......Page 211
7 Further Generalization......Page 212
1 Introduction......Page 215
2 Prehomomorphisms......Page 218
1 Introduction......Page 223
2 Finite state machine concepts......Page 226
3 X-machine concepts......Page 228
4 The breakpoint test set of X-machines......Page 231
5 The extended test set of X-machines......Page 236
6 Conclusions......Page 238
Some Fundamental Theorems on BCK......Page 243
1 Introduction......Page 251
2 P Systems with Membrane Creation......Page 253
3 Some Preliminary Remarks......Page 256
4 Characterizing PsETOL......Page 257
5 Final Remarks......Page 264
1 Introduction......Page 267
2 Basic Notions and Notation......Page 268
3 Algebras and Pointed Algebras......Page 269
4 Pointed Monoids and Pointed Semigroups......Page 273
5 Automata......Page 275
6 Disjunctive Sets and Languages......Page 277
7 Disjunctive w-Languages......Page 278
8 Disjunctive Elements......Page 279
10 Variants of Disjunctivity......Page 281
11 Questions......Page 282
2 Language Theory Prerequisites......Page 287
3 The Balanced Cut Operation......Page 289
4 Related Operations......Page 296
1 Introduction......Page 301
2 Basic Notions and Preliminary Results......Page 302
3 Preliminary Results......Page 305
4 The Construction of Grammars Generating Kn......Page 307
1 Introduction......Page 315
2 Preliminaries......Page 316
3 Parsing Morphism Languages by UPPGs......Page 319
4 Concluding Remarks......Page 325
1 Introduction......Page 327
2 Iterated Finite State Sequential Transducers......Page 328
3 Iterated Transducers and Turing Machines......Page 329
4 Open Problems......Page 338
1 Introduction......Page 341
2 Basic Definitions......Page 342
3 The Main Result......Page 343
4 Definition of T......Page 344
5 Checking the Simulation......Page 347
1 Introduction......Page 353
2 The RRWW-Automaton......Page 355
3 Some Additional Examples of Languages That Are Accepted by RRWW-Automata......Page 356
4 Conclusion......Page 365
1 Introduction......Page 369
2 Preliminaries......Page 370
3 Parikh Controlled Grammars......Page 371
4 Bounded and Terminal Independent PcCFG's and PcRG's......Page 373
5 Conclusion......Page 378
Personal reminiscences about Gabriel Thierrin......Page 381
1 Introduction......Page 382
2 A Bijection......Page 383
3 Average Degree of the Root......Page 385
5 Average Number of Paths......Page 386
7 Number of Descendants......Page 387
9 Average Height of Elenas......Page 389
10 Conclusion......Page 390
2 Semilattice Amalgamation......Page 393
3 Symmetry and the Semidirect Product......Page 398
1 Introduction......Page 407
2 Preliminaries......Page 408
3 Main Results......Page 409
1 Introduction......Page 417
2 Basics About Watson-Crick DOL Systems......Page 419
3 DNA Systems......Page 421
4 Stability......Page 422
5 Equivalence Problems......Page 427
6 Weird Growth......Page 428
7 Conclusion......Page 431
1 Notation......Page 433
2 Preliminary Considerations......Page 434
3 The w-Language of Disjunctive Sequences......Page 435
4 The Topology of Forbidden Words......Page 437
5 A Metric Related to Languages......Page 439
The Publications of Gabriel Thierrin......Page 443
