Author(s): P.-L. Curien (ed.)
Series: Theoretical Computer Science 281 1-2
Language: English
Pages: 615
An even shorter biography......Page 2
Scientific works......Page 3
Années d'apprentissage......Page 6
A la rencontre de Schützenberger......Page 8
IRIA......Page 10
La création du LITP......Page 11
L'informatique théorique européenne......Page 13
Théorie des langages......Page 14
De la sémantique algébrique à celle du parallélisme......Page 15
Travaux d'Hercule......Page 16
Tomographie discrète......Page 17
Un homme de conviction......Page 18
References......Page 20
ICALP......Page 23
EATCS......Page 25
Nivat's processes and their synchronization......Page 29
References......Page 34
Basic analytic combinatorics ofdirected lattice paths......Page 35
Lattice paths and generating functions......Page 38
Algebraic structures and the kernel method......Page 40
Walks and bridges......Page 43
Meanders and excursions......Page 46
Computational aspects......Page 54
Singular structures......Page 56
Bridges and excursions......Page 59
Paths and meanders......Page 63
Periodicities......Page 66
Basic parameters and limit laws......Page 67
Arches and contacts......Page 68
Final altitude of a meander......Page 69
Directed two-dimensional models......Page 73
Conclusion......Page 74
References......Page 75
Introduction......Page 79
Preliminaries......Page 80
Directed tiling with boundary a closed curve C......Page 82
Relations between tilings, balance, and the word problem......Page 83
The 3-hexes group Gh......Page 88
Generalization: the group Gp......Page 90
References......Page 95
Introduction......Page 96
Notation......Page 98
Circular order......Page 99
Intersection......Page 100
Main result......Page 103
References......Page 104
Introduction......Page 105
The language and type system......Page 108
Properties of typed programs......Page 111
Scheduling sequential programs......Page 118
Conclusion and related work......Page 123
References......Page 125
Introduction......Page 127
An algebra of connectors......Page 129
A two-dimensional logic......Page 131
An example from basic process algebras......Page 133
Normal forms for algebras of connectors......Page 134
Tile logic......Page 139
A digression on symmetric monoidal double categories and PMEqtl......Page 143
Auxiliary connectors as tiles......Page 144
Connectors for concurrency......Page 148
Tile bisimilarity and causal weak bisimilarity......Page 161
Related work......Page 166
Acknowledgements......Page 168
References......Page 169
The evaluation of first-order substitutionis monadic second-order compatible......Page 173
Introduction......Page 174
Structures and monadic second-order logic......Page 175
MS-transductions with parameters......Page 176
Finite and infinite terms......Page 177
Graphs......Page 179
Terms and rooted graphs......Page 180
Operations on graphs......Page 181
Interpretations......Page 184
Coverings and unfoldings......Page 185
The evaluation of first-order substitutions......Page 186
First-order substitutions......Page 187
Evaluating substitutions......Page 188
Regular, algebraic and hyperalgebraic trees......Page 192
Regular trees......Page 193
Second-order substitution......Page 194
Algebraic trees......Page 195
Damm's hierarchy......Page 198
References......Page 201
Introduction......Page 203
Design problems......Page 204
Basic modules and functors for tilings......Page 206
Group representation......Page 207
Mappings......Page 208
Geometries......Page 211
Conclusion......Page 212
References......Page 213
Introduction......Page 214
Fidélité et morphismes......Page 216
Non-linéarité et reconnaissabilité......Page 219
Preuve de la Proposition 2......Page 220
Bimorphismes......Page 226
Rèfèrences......Page 227
Introduction......Page 229
The planar case......Page 231
The cylindrical case......Page 232
The reconstruction problem......Page 236
Conjecture for CDSSPM on the class of (0,1)-matrices......Page 241
References......Page 242
Problématique......Page 244
Pourquoi ces fils......Page 245
Définitions......Page 246
Définition et représentation graphique......Page 249
Temps réel sur le fil d'Archimède......Page 250
Langages rationnels sur le fil d'Archimède......Page 251
Définition et représentation graphique......Page 253
Une propriété du fil de Hilbert......Page 254
Temps réel sur le fil de Hilbert......Page 257
Remarques générales......Page 260
Algorithme pour l'extérieur d'une boule B(0, 0)(t)......Page 262
Algorithme pour l'intérieur d'une boule B(0,0)(t)......Page 268
Obtention du temps réel......Page 274
Le calcul sur la feuille F-anticipation......Page 276
Un exemple d'obtention du temps réel1......Page 278
Conclusion......Page 280
References......Page 281
Introduction......Page 283
Definitions and basic results......Page 286
An algorithm for counting the number of H-colorings......Page 287
The #VEH-coloring......Page 291
The #EH-coloring......Page 293
The directed case......Page 295
Coloring problems......Page 296
Problems on cores......Page 298
Remarks and open problems......Page 299
References......Page 300
Plan......Page 302
Quelques définitions......Page 303
Un peu de topologie......Page 305
Topologie et quasipériodicité......Page 306
Le problème......Page 308
Pavages et indécidabilité......Page 310
Une palette apériodique......Page 311
Pavages complexes......Page 313
References......Page 315
Introduction......Page 316
Graphs with labels and colours......Page 320
Alternating trails......Page 323
Pairing functions of even graphs......Page 325
Folding a graph......Page 326
Unfolding paired graphs......Page 328
Assembled graphs of genomes......Page 330
Intracyclic unfolding......Page 332
References......Page 339
Introduction......Page 341
Finite succession rules......Page 344
Rule operators......Page 346
Sum of rule operators......Page 348
Product of succession rules......Page 349
The star of a rule operator......Page 350
Partial sum of a succession rule......Page 352
Open problems......Page 354
A conjecture......Page 356
References......Page 357
A truly concurrent semantics for a process algebra using resource pomsets......Page 358
Introduction......Page 359
Resource pomsets......Page 361
The language, its resources and its operational semantics......Page 370
Operational semantics......Page 371
Examples......Page 372
Denotational semantics......Page 374
Strict sequential composition......Page 376
Weak sequential composition......Page 378
Parallel composition......Page 382
Hiding......Page 387
Recursion......Page 389
Summary......Page 392
Examples......Page 394
Two crucial results......Page 397
The rank function......Page 401
Adequacy and the congruence theorem......Page 404
Full abstraction......Page 406
Summary......Page 408
Acknowledgements......Page 409
References......Page 410
Modelization of deterministic rational relations......Page 411
Rational relations defined via set theoretical operations......Page 412
Multitape automata......Page 413
Normalizing automata......Page 414
Read-only One-way Turing Machines......Page 416
Tally rational relations......Page 419
Unambiguous automata and relations......Page 421
Decidability of ambiguity for automata......Page 422
Unambiguous multimorphisms......Page 424
Modelization of deterministic rational relations......Page 426
End-markers and super-deterministic automata......Page 427
What is a deterministic automaton?......Page 428
Strongly deterministic and n-deterministic automata......Page 430
Deterministic automata compute what is expected......Page 433
Decidability of determinism for automata......Page 435
Deterministic multimorphisms......Page 439
Acknowledgements......Page 440
References......Page 441
Introduction......Page 442
Definitions, preliminaries and main results......Page 443
Intractability results......Page 449
Tractability results......Page 454
References......Page 456
Introduction......Page 457
First and higher order intuitionistic phase space......Page 459
Phase models......Page 461
The uniform cut-elimination and (phase-semantic) completeness proof for first-order logics......Page 466
The uniform cut-elimination and (phase-semantic non-standard) completeness proof for higher order logics......Page 471
Inference rules for intuitionistic linear logic......Page 477
Classical linear logic......Page 479
Substructural systems......Page 481
References......Page 482
A unified language processing methodology......Page 485
Introduction......Page 486
Language as a communication tool......Page 488
Macro-operations......Page 489
Communicators, languages, and language systems......Page 490
Language use......Page 492
Meaning of word-expressions......Page 494
Galois connection as a criterion for consistent language usage......Page 495
Example language structures......Page 496
Natural language......Page 497
Logical language......Page 498
Programming language......Page 500
Structural properties of a specification schema......Page 504
Universal tools for language processing......Page 506
Properties of languages specified by a schema......Page 509
Consistency criterion for language usage......Page 514
Algebraic model of language translation......Page 515
Examples of algebraic translations......Page 517
Correctness of an algebraic translator......Page 519
References......Page 520
Uni-transitional Watson--Crick D0L systems......Page 523
Introduction......Page 524
Watson--Crick D0L systems......Page 526
Uni-transitional mode......Page 528
Regular triggers......Page 532
Decision problems for standard systems......Page 534
Computing functions......Page 538
References......Page 539
Result......Page 540
Contents......Page 541
Pushdown automata......Page 542
Free monoids acting on semi-rings......Page 543
Definitions......Page 546
Residuals......Page 547
Operations on row-vectors......Page 549
Strict-deterministic grammars......Page 550
Linear independence......Page 557
Derivations......Page 558
General formal systems......Page 560
Strategies......Page 562
System D0......Page 563
Triangulations......Page 567
Constants......Page 575
Strategies for D0......Page 577
Tree analysis......Page 579
Depth and weight......Page 580
B-stacking sequences......Page 581
Completeness of D0......Page 591
Elimination......Page 592
References......Page 593
Introduction......Page 594
A more rigorous geometric analysis......Page 595
Æsthetic feedback......Page 597
Bibliographic search......Page 598
A sacred symbol of Devi......Page 600
Analysing the three basic symbols......Page 601
An outside-in walk......Page 603
Yantra as an instrument of worship......Page 605
Mantras......Page 606
Conclusion......Page 607
References......Page 612
