Words, languages and combinatorics 3: proceedings of international conference Kyoto 2000

Contributed Papers......Page 22
Preface......Page 6
Scientific Program......Page 8
List of Speakers......Page 16
1 Introduction......Page 26
2.1 Various operators on pseudovarieties......Page 27
2.2 Semidirect products with D......Page 29
2.3 Semidirect products - * H vs other operators......Page 31
2.4 (w - 1)-words......Page 32
2.5 Bases for semidirect products V * G......Page 35
3.1 Locally trivial solutions......Page 38
3.2 Some solutions in \'DS......Page 39
3.3 The case of DS......Page 40
3.4 The case of J......Page 41
References......Page 43
1 Introduction......Page 47
2 Definitions and examples......Page 49
3 The constant polynomial......Page 52
4 The linear polynomial......Page 56
5 The exponential case an......Page 60
References......Page 62
Appendix......Page 64
1 Introduction......Page 65
2 Groups......Page 66
3 The main result......Page 69
References......Page 75
1 Introduction......Page 76
2 Basic Notions......Page 77
3 High Arithmetical Complexity......Page 80
4 Low Arithmetical Complexity......Page 82
5 Concluding remark......Page 86
References......Page 87
1 Introduction......Page 88
2 Recursive and Recursively Enumerable Sets......Page 91
3 Algebraic Recursiveness......Page 93
References......Page 96
1 Introduction......Page 98
2 Model and Notions......Page 99
3 Guess Reduction......Page 102
4 Nondeterministic Hierarchy......Page 103
5 Closure Properties......Page 107
References......Page 111
1 Introduction......Page 113
2.1 Ordinals......Page 114
2.3 Rational expressions......Page 115
2.4 Automata......Page 116
2.5 w1 -semigroups......Page 117
3.1  -languages......Page 119
3.2 R-trivial languages......Page 122
References......Page 126
1 Introduction......Page 128
2.1 Ordinals......Page 129
2.2 Transfinite strings......Page 130
2.3 Continuous mappings......Page 131
3.1 Buchi automata on transfinite strings......Page 133
3.2 Choueka automata on transfinite strings......Page 134
3.3 Rational sets of transfinite strings......Page 135
3.4 Kleene type results......Page 136
4.2 Rational relations......Page 137
4.3 The first factorization theorem......Page 138
4.4 Rational Buchi transducers......Page 140
4.5 Eilenberg’s second factorization theorem: the case < w1......Page 141
Preliminary analysis......Page 143
Construction of the Buchi transducer......Page 144
4.6 Eilenberg\'s second factorization theorem: the case < wn+l......Page 145
4.7 Recognizable relations......Page 146
5 Uniformization......Page 147
5.1 The greedy ordering on Choueka-continuous sequences......Page 149
5.2 Two properties of the greedy ordering......Page 150
5.3 Uniformization of relations with domain bounded below ww......Page 152
5.4 From ww on......Page 153
References......Page 156
1 Introduction......Page 159
2 Preliminaries and basic notions......Page 161
3 Networks of Watson-Crick DOL systems......Page 163
4 Protocol (a) versus protocol (b)......Page 167
5 String population growth in NWDOL systems......Page 170
6 Remarks on black holes......Page 173
References......Page 174
1 Introduction and Definitions......Page 176
2 Deterministic Tabled Lindenmayer Systems......Page 177
3 Evolutionary Grammars......Page 180
4 Context-Free Grammars......Page 182
References......Page 185
1. Abstract......Page 187
2.2. Life......Page 188
3.2. Same dimensional viewing......Page 189
4.1. Input parameters......Page 190
4.2. Dashboard......Page 192
6. References......Page 193
1. Preliminaries.......Page 196
2. Supercodes.......Page 198
3. Maximal supercodes.......Page 199
4. Supercodes over two letter alphabets......Page 202
References......Page 207
A Parsing Problem for Context-Sensitive Languages P. Domosi (Debrecen, Hungary) and M. Ito (Kyoto, Japan)......Page 208
References......Page 209
1. Introduction......Page 210
2. Excluded Positions in Derivation Trees......Page 211
3. Context-Free Languages......Page 214
References......Page 215
1.1 Goals of the research......Page 217
2 Classical Reversible Finite Automata......Page 218
3.1 Quantum finite automata - a general scheme......Page 220
4 One-way quantum finite automata......Page 221
4.2 Example - hierarchies of languages......Page 222
4.3 Limitations on the probability acceptance......Page 223
4.5 Closure properties......Page 224
4.6 Succinctness results......Page 225
4.7 Lower bounds methods......Page 226
5 Two-way quantum finite automata......Page 228
5.1 Power of 2QFA......Page 229
5.3 Two-way classical/quantum finite automata......Page 231
6 Quantum almost finite automata......Page 232
1 Introduction......Page 237
2 Preliminaries......Page 238
3 Isomorphic representation......Page 240
4 Minimum-length directing words......Page 242
References......Page 246
2 The index of submonoids of monoids......Page 247
3 Presentations of right unitary submonoids of monoids......Page 248
4 Finitely presentability of right unitary submonoids of monoids......Page 250
References......Page 252
A Combinatorial Property of Languages and Monoids A. V. Kelarev (Hobart, Australia) and P. G. Trotter (Hobart, Australia)......Page 253
1. Introduction......Page 265
2. Basic Background......Page 267
3. Error Detection: Definitions, Examples and Basic Results......Page 269
4. Error-detecting Uniform, Solid, and Shuffle Codes......Page 273
References......Page 276
1 Introduction......Page 278
2 Definitions......Page 279
3 Review of the One-Variable Pattern-Finding Problem......Page 280
4 Finding Patterns from Positive and Negative Examples......Page 283
References......Page 289
On the Star Height of Rational Languages: A New Presentation for Two Old Results S. Lombardy (Paris, France) and J. Sakarovitch (Paris, France)......Page 291
1.1 Star height and loop complexity......Page 292
1.2 The state elimination algorithm......Page 295
1.3 The Eggan-Brzozowski index......Page 297
1.4 No rush to conclusion......Page 300
2 Conway’s universal automaton......Page 301
3 McNaughton’s Theorem......Page 303
3.1 Conformal morphisms......Page 306
3.2 Proof of Theorem 3......Page 307
Acknowledgements......Page 309
References......Page 310
I Preliminaries......Page 311
2 Normal Form......Page 313
3 Sheffer Hyperoperations......Page 315
3.1 Existence of Sheffer Hyperoperations......Page 316
3.2 Nonexistence of a Binary Sheffer Hyperoperation on {0,1}......Page 317
4 Rosenberg’s Problem......Page 318
References......Page 320
Words Guaranteeing Minimal Image S. W. Margolis (Ramat Gan, Israel), J.-E. Pin (Paris, France) and M. V. Volkov (Ekaterinburg, Russia)......Page 322
References......Page 334
1 Introduction......Page 336
2 Preliminaries......Page 337
3 Polynomials......Page 340
5 The Power Operator and Polynomial Closure......Page 341
6 Semigroups which are Locally Groups......Page 342
7 Locally Block Groups......Page 344
References......Page 346
1 Introduction......Page 348
2 Operations on routes and trajectories......Page 349
2.2 Some unary operations that are particular cases of splicing on routes......Page 351
3 Splicing on routes of regular and context-free languages......Page 352
4 Trajectories......Page 353
5.1 Completeness......Page 354
5.3 Commutativity......Page 355
5.5 Associativity......Page 356
6.1 Fairness......Page 360
6.2 On parallelization of languages using shuffle on trajectories......Page 361
7 Conclusion......Page 362
References......Page 363
$0. Commutative ring theory and commutative semigroups......Page 364
$1. Valuation semigroups and valuation domains......Page 365
$2. Valuation rings......Page 369
REFERENCES......Page 376
1 Introduction......Page 377
2 The restarting automaton and some of its variants......Page 378
3 A language-theoretical equivalent to the use of nonterminals......Page 381
4 Inclusions between the deterministic classes......Page 384
5 The Gladkij language is in L(RRWW)......Page 388
6 Restarting automata and prefix-rewriting systems......Page 392
References......Page 394
1 Introduction......Page 395
2.2 Local Function......Page 396
3.2 Ring &[X]......Page 397
5 Results We present several results which......Page 398
References......Page 399
Appendix 1. Polynomials over GF(3)......Page 401
Appendix 2. Simulation of CA[X] +......Page 402
1 Introduction and preliminaries......Page 403
2 Testing for generalized and local directability......Page 407
3 The least directing congruence......Page 410
4 The least generalized and locally directing congruences......Page 416
References......Page 418
Acts over Right, Left Regular Bands and Semilattices Types T. Saito (Innoshima, Japan)......Page 421
References......Page 427
Two Optimal Parallel Algorithms on the Commutation Class of a Word R. Schott (Nancy, France) and J.-C. Spehner (Mulhouse, France)......Page 428
1 Introduction......Page 429
2 The partial minimal automaton of the commutation class of a word......Page 430
3.1 The distribution of the states among the processors......Page 432
3.3 Construction of the partial automaton which recognizes the word w......Page 434
3.5 Permutation of two letters......Page 435
3.6 The treatment of the previous and the next states......Page 436
3.7 The treatment of the diagonal state......Page 437
4 Testing if a word belongs to a commutation class......Page 438
4.2 Letter occurrences in a word......Page 439
4.3 The first test......Page 440
4.5 Analysis of a word......Page 441
4.7 The second test......Page 442
Acknowledgments......Page 443
References......Page 444
1. INTRODUCTION AND PRELIMINARIES......Page 445
2. PROOF OF OKNIkSKI AND PUTCHA’S THEOREM......Page 446
REFERENCES......Page 452
1 Introduction......Page 453
2 Subdirect product of left groups......Page 454
3 Subdirect product of a left normal band and a group......Page 455
References......Page 458
1 Introduction......Page 459
2 Preliminaries......Page 460
3 Reducibility, left-linearity and regular tree languages......Page 462
4 Ground reducibility and universal closures......Page 463
5 Coping with nonlinearity......Page 464
6 Tree automata for AC-theories......Page 465
7 Descendants, normal forms and equivalence classes......Page 466
8 Congruential tree languages and ground term rewriting systems......Page 469
References......Page 470
1 Introduction......Page 475
2.1 Proposed protocol......Page 477
2.2 Security compared with the DiffieHellman protocol......Page 478
2.3 MDLOG......Page 479
3.1 Generic algorithms......Page 480
3.2 Main Theorem......Page 481
3.3 Proof of Theorem 3.1......Page 483
4 Example......Page 488
5 On the parameter condition......Page 489
References......Page 490
1 Introduction......Page 491
2 Rademacher functions and computability in a Banach space......Page 492
3 Computation within the  01-law of excluded middle......Page 494
4 Remarks......Page 498
References......Page 499
Authors Index......Page 502