Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 08 octobre 2013 à 14h00 en B107, Olivier Carton nous parlera de : Normalité et automates

Résumé : We strengthen the theorem that establishes that deterministic finite transducers can not compress normal infinite words. We prove that, indeed, non-deterministic finite transducers, even augmented with a fixed number of counters, can not compress normal infinite words. However, there are push-down non-deterministic transducers that can compress normal infinite words. We also obtain new results on the preservation of normality with automata selectors. Complementing Agafonov's theorem for prefix selectors, we show that suffix selectors also preserve normality. However, there are simple two-sided selectors that do not preserve normality.

 [Slides.pdf]


Dernière modification : Monday 27 May 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr