Words, semigroups, transductions

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