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.
|
 |
Deterministic rational transducers and random sequences
| |
|
Deterministic rational transducers and random sequences
Sylvain Porrot1 , Max Dauchet2 , Bruno Durand3 and Nikolai K. Vereshchagin3, 4 
| (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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|