|
|
 |
|
Mardi 8 Octobre
| Heure: |
14:00 - 17:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Normalité et automates |
| Description: |
Olivier Carton We strengthen the theorem that establishes that deterministic finitetransducers can not compress normal infinite words. We prove that, indeed,non-deterministic finite transducers, even augmented with a fixed number ofcounters, can not compress normal infinite words. However, there arepush-down non-deterministic transducers that can compress normal infinitewords. We also obtain new results on the preservation of normality withautomata selectors. Complementing Agafonov's theorem for prefix selectors,we show that suffix selectors also preserve normality. However, there aresimple two-sided selectors that do not preserve normality. |
Vendredi 11 Octobre
| Heure: |
10:00 - 12:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Intensionnalité vs. extensionnalité : où est-elle la frontière ? (2e partie) |
| Description: |
Jean-Yves Moyen Au cours de ces trois séances de groupe de travail, je ferai le
"débriefing" de mon CRCT et je vous présenterai les résultats obtenus à
Nancy en collaboration avec Guillaume Bonfante et Pierre, ou à
Copenhague en collaboration avec James Avery et Jakob Simonsen (qui sera
par ailleurs prof invité chez nous en février).
Au gré de vos interruptions et de nos discussions, nous parlerons
sans doute de Rice et de Gödel, de cardinaux et de grands ordinaux,
d'ordre supérieur et de non déterminisme, de treillis, de partitions,
peut-être de topologie. Les catégoriciens pourront s'exercer à faire
commuter des diagrammes. Ne reniant pas mes origines, tout cela sera
enrobé dans une couche de complexité implicite.
Le point de départ est une relecture du théorème de Rice entamée
avec Pierre il y a quelques années. Au lieu de parler de "propriétés
extensionnelles", le résultat est vu comme parlant de l'équivalence
extensionnelle (p et q sont équivalents si ils calculent la même
fonction). Autrement dit, on quotiente l'ensemble des programmes par
leur extension.
Cette vision fait de Rice une équivalence parmi d'autres et on peut
chercher d'autres équivalences "intéressantes" entre programmes.
Notamment, l'ensemble des équivalences formant un treillis complet, on
peut étudier ce treillis. |
|
|
