Geodesic
Linearly realizable automata
Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 59-79
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper is devoted to the investigation of “linearly realizable” automata, i.e. automata that allow state encodings that lead to implementations with linear Boolean operators. We formulate the criterion of linear realizability and obtain upper and lower bounds on the number of linearly realizable automata.
Keywords: automata theory, semiautomata, transition systems, substitution function, assignment, state encoding, complexity.
Mots-clés : automata, permutation 
@article{DM_2017_29_1_a5,
     author = {S. B. Rodin},
     title = {Linearly realizable automata},
     journal = {Diskretnaya Matematika},
     pages = {59--79},
     year = {2017},
     volume = {29},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2017_29_1_a5/}
}
TY  - JOUR
AU  - S. B. Rodin
TI  - Linearly realizable automata
JO  - Diskretnaya Matematika
PY  - 2017
SP  - 59
EP  - 79
VL  - 29
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2017_29_1_a5/
LA  - ru
ID  - DM_2017_29_1_a5
ER  - 
%0 Journal Article
%A S. B. Rodin
%T Linearly realizable automata
%J Diskretnaya Matematika
%D 2017
%P 59-79
%V 29
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2017_29_1_a5/
%G ru
%F DM_2017_29_1_a5
S. B. Rodin. Linearly realizable automata. Diskretnaya Matematika, Tome 29 (2017) no. 1, pp. 59-79. http://geodesic.mathdoc.fr/item/DM_2017_29_1_a5/

[1] A. Gill, Lineinye posledovatelnostnye mashiny, Nauka, M., 1974, 288 pp.; Gill A., Linear Sequential Circuits. Analysis, Synthesis and Applications, McGraw-Hill, N. Y., 1966, 216 pp. | MR | Zbl

[2] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, M., 1984, 320 pp. | MR

[3] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, M., 1979, 272 pp. | MR

[4] Lidl R., Niderraiter G., Konechnye polya, per. s angl., Mir, M., 1988, 822 pp.; Lidl R., Niederreiter H., Finite fields, Encyclopedia of Mathematics and its Applications, 20, Addison-Wesley, 1987, 755 pp. | MR

[5] Kargapolov M. I., Merzlyakov Yu. I., Osnovy teorii grupp, 3-e izdanie, Nauka, M., 1982, 288 pp. | MR

[6] Arbib M. A., “Dekompozitsiya avtomatov i rasshirenie polugrupp”, Algebraicheskaya teoriya avtomatov, yazykov i polugrupp, Statistika, M., 1975, 46–64

[7] Klifford A., Preston G., Algebraicheskaya teoriya polugrupp, v. 1, Mir, M., 1972, 285 pp. ; Clifford A. H., Preston G. B., The algebraic theory of semigroups, AMS, 1964 | MR

[8] Hartmanis J., Walter H., “Group theoretic characterization of linear permutation automata”, J. Comput. Syst. Sci., 7:2 (1973), 168–188 | DOI | MR | Zbl

[9] Aleshin S. V., Algebraicheskie sistemy avtomatov, MAKS Press, M., 2016, 192 pp.