|
|
 |
|
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. |
|
|
