Automata on algebraic structures

V. V. Skobelev

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 13 (2013) no. 2, pp. 58-66.

Résumé

A survey of results obtained in investigations of automata determined over finite algebraic structures. The objects of research are automata over some finite ring, automata determined in terms of ideals, automata over varieties, and families of hash-functions determined by automata without output function. Computational security, complexity of simulation and homomorphisms of investigated automata are characterized.

Bibliographie

[1] Gill A., Linear sequential machines, Nauka, Moscow, 1974, 298 pp. | MR | Zbl

[2] Faradgev R. G., Linear sequential machines, Sovetskoje Radio, Moscow, 1975, 248 pp.

[3] Agibalov G. P., “Recognition of operators realized by linear autonomous automata”, Izv. AN USSR. Tech. Cybernetika, 1970, no. 3, 99–108 | MR | Zbl

[4] Agibalov G. P., Jufit Ya. G., “On simple experiments for linear initial automata”, Avtomatica i vychisliteljnaja technika, 1972, no. 2, 17–19 | MR | Zbl

[5] Speranskij D. V., Experiments with linear and bi-linear finite automata, Saratov. Univ. Press, Saratov, 2004, 144 pp.

[6] Kurosh A. G., Lectures in general algebra, Nauka, Moscow, 1973, 400 pp.

[7] Skobelev V. V., Skobelev V. G., Analysis of ciphersystems, IAMM NASU, Donetsk, 2009, 479 pp.

[8] Skobelev V. V., Glazunov N. M., Skobelev V. G., Varieties over rings. Theory and applications, IAMM NASU, Donetsk, 2011, 323 pp.

[9] Skobelev V. V., Skobelev V. G., “Analysis of non-linear automata with lag 2 over finite ring”, Prikladnaja discretnaja matematika, 2010, no. 1, 68–85

[10] Skobelev V. V., “Complexity of identification of non-linear 1-dimensional automata with lag 2 over finite ring”, Computernaja mathematika, 2 (2011), 81–89

[11] Kuznetsov S. P., Dynamical chaos, Fizmatlit, Moscow, 2001, 296 pp.

[12] Skobelev V. V., Skobelev V. G., “On the complexity of analysis of automata over a finite ring”, Cybernet. Systems Anal., 46:4 (2010), 533–545 | DOI | MR | Zbl

[13] Skobelev V. V., “On systems of polynomial equations over finite rings”, Naukovi zapiski NaU-KMA. Ser. Komp'yuterni nauki, 138 (2012), 15–19

[14] Skobelev V. V., “On subsets of automata over finite ring determined via terms of ideals”, Visn., Ser. Fiz.-Mat. Nauky, Kyïv. Univ. Im. Tarasa Shevchenka, 2011, no. 3, 212–218 (in Ukrainian)

[15] Skobelev V. V., “Simulation of automata over a finite ring by the automata with finite memory”, J. of Automation and Information Sci., 44:5 (2012), 57–66 | DOI

[16] Skobelev V. V., “Analysis of the problem of recognition of automaton over some ring”, Dopov. Nats. Akad. Nauk Ukr., Mat., Pryr., Tekh. Nauky, 2012, no. 9, 29–35 | Zbl

[17] Skobelev V. V., “On automata determined over varieties over some ring”, Tr. Inst. Prikl. Mat. Mekh., 24, 2012, 190–201

[18] Skobelev V. V., “Automata over vatieties with some algebra”, Visn., Ser. Fiz.-Mat. Nauky, Kyïv. Univ. Im. Tarasa Shevchenka, 2012, no. 2, 234–238 (in Ukrainian) | Zbl

[19] Skobelev V. V., “Analysis of automata determined over parametric varieties over an associative ring”, Visnik Kiïvskogo universitetu. Ser.: fiz.-mat. nauki, 2012, no. 3, 239–244 | Zbl

[20] Skobelev V. V., “On automata determined over polynomially parametric varieties over some finite ring”, Tr. Inst. Prikl. Mat. Mekh., 25, 2012, 185–195

[21] Skobelev V. V., “On homomorphisms of automata over varieties over some ring”, Dopov. Nats. Akad. Nauk Ukr., Mat., Pryr., Tekh. Nauky, 2013, no. 1, 42–46 | Zbl

[22] Skobelev V. V., “Analysis of automata determined over elliptic curves”, Visn., Ser. Fiz.-Mat. Nauky, Kyïv. Univ. Im. Tarasa Shevchenka, 2012, no. 1, 223–230 (in Ukrainian) | Zbl

[23] Skobelev V. V., “Analysis of families of hash functions defined by automata over a finite ring”, Cybernet. Systems Anal., 49:2 (2013), 209–216 | DOI