Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Deterministic rational transducers and random sequences

Sylvain PorrotContact Information, Max DauchetContact Information, Bruno DurandContact Information and Nikolai K. Vereshchagin3, 4 Contact Information

(1)  LAIL, URA CNRS 1440, Université des Sciences et Technologies de Lille, Bâtiment P2, 59655 Villeneuve d'Ascq Cedex, France
(2)  LIFL, URA CNRS 369, Université des Sciences et Technologies de Lille, Bâtiment M3, 59655 Villeneuve d'Ascq Cedex, France
(3)  LIP, ENS-Lyon CNRS, 46 Allée d'Italie, 69634 Lyon Cedex 07, France
(4)  Dept. of Mathematical Logic and Theory of Algorithms, Moscow State University, Vorobjevy Gory, Moscow, Russia
Abstract
This paper presents some results about transformations of infinite random sequences by letter to letter rational transducers. We show that it is possible by observing initial segments of a given random sequence to decide whether two given letter to letter rational transducers have the same output on that sequence. We use the characterization of random sequences by Kolmogorov Complexity. We also prove that the image of a random sequence is either random, or non-random and non-recursive, or periodic, depending on some transducer's structural properties that we give.

Contact Information Sylvain Porrot
Email: porrot@lifl.fr
Fax: (33) 03 20 43 47 43

Contact Information Max Dauchet
Email: dauchet@lifl.fr

Contact Information Bruno Durand
Email: Bruno.Durand@ens-lyon.fr

Contact Information Nikolai K. Vereshchagin
Email: ver@mech.math.msu.su
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: MPWEB26
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)