Geodesic
On the automaton determinization of sets of superworks
Diskretnaya Matematika, Tome 18 (2006) no. 2, pp. 84-97 
A. G. Verenkin; È. È. Gasanov. On the automaton determinization of sets of superworks. Diskretnaya Matematika, Tome 18 (2006) no. 2, pp. 84-97. http://geodesic.mathdoc.fr/item/DM_2006_18_2_a5/
@article{DM_2006_18_2_a5,
     author = {A. G. Verenkin and \`E. \`E. Gasanov},
     title = {On the automaton determinization of sets of superworks},
     journal = {Diskretnaya Matematika},
     pages = {84--97},
     year = {2006},
     volume = {18},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_2_a5/}
}
TY  - JOUR
AU  - A. G. Verenkin
AU  - È. È. Gasanov
TI  - On the automaton determinization of sets of superworks
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 84
EP  - 97
VL  - 18
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_2_a5/
LA  - ru
ID  - DM_2006_18_2_a5
ER  - 
%0 Journal Article
%A A. G. Verenkin
%A È. È. Gasanov
%T On the automaton determinization of sets of superworks
%J Diskretnaya Matematika
%D 2006
%P 84-97
%V 18
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2006_18_2_a5/
%G ru
%F DM_2006_18_2_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

We introduce the concept of a determinising automaton which, for every superword taken from a given set fed into its input, beginning with some step, at any time $t$ yields the value of the input word at time $t+1$, that is, predicts the input superword. We find a criterion whether a given set of superwords is determinisable, that is, whether for the set there exists a determinising automaton. We give the best (in some sense) method to design a determinising automaton for an arbitrary determinisable set of superwords. For some determinisable sets we present optimal and asymptotically optimal determinising automata.

[1] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, Moskva, 1985 | MR

[2] Trakhtenbrot B. A., Barzdin Ya. M., Konechnye avtomaty (povedenie i sintez), Nauka, Moskva, 1970 | MR

[3] Vinogradov I. M., Vvedenie v teoriyu chisel, Nauka, Moskva, 1981

[4] Kostrikin A. I., Osnovnye struktury algebry, Fizmatlit, Moskva, 2000