Geodesic
Completeness problem for the class of linear automata functions
Diskretnaya Matematika, Tome 27 (2015) no. 2, pp. 134-151.

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

We consider the classes of linear automata functions over finite fields with composition (superposition and feedback) operation and describe an algorithm that decides whether a finite set of functions from such class is complete. Thus we generalize the result that was known for the case of linear automata functions over prime finite fields.
Keywords: finite automaton, linear automata function, composition operation, superposition operation, feedback, completeness problem, completeness criterion, precomplete classes, adder, delay. 
@article{DM_2015_27_2_a8,
     author = {Anatoliy A. Chasovskikh},
     title = {Completeness problem for the class of linear automata functions},
     journal = {Diskretnaya Matematika},
     pages = {134--151},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2015_27_2_a8/}
}
TY  - JOUR
AU  - Anatoliy A. Chasovskikh
TI  - Completeness problem for the class of linear automata functions
JO  - Diskretnaya Matematika
PY  - 2015
SP  - 134
EP  - 151
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2015_27_2_a8/
LA  - ru
ID  - DM_2015_27_2_a8
ER  - 
%0 Journal Article
%A Anatoliy A. Chasovskikh
%T Completeness problem for the class of linear automata functions
%J Diskretnaya Matematika
%D 2015
%P 134-151
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2015_27_2_a8/
%G ru
%F DM_2015_27_2_a8
Anatoliy A. Chasovskikh. Completeness problem for the class of linear automata functions. Diskretnaya Matematika, Tome 27 (2015) no. 2, pp. 134-151. http://geodesic.mathdoc.fr/item/DM_2015_27_2_a8/

[1] Van der Varden B. L., Algebra, per. s nem., Nauka, Moskva, 1976, 648 pp.

[2] Gill A., Lineinye posledovatelnostnye mashiny, per. s angl., Nauka, Moskva, 1974, 288 pp.

[3] Zarisskii O., Samyuel P., Kommutativnaya algebra, per. s angl., IL, Moskva, 1963, 373 pp.

[4] Kudryavtsev V. B., Aleshin S. V., Podkolzin A. S., Vvedenie v teoriyu avtomatov, Nauka, Moskva, 1985, 320 pp.

[5] Leng S., Algebra, per. s angl., Mir, Moskva, 1968, 564 pp.

[6] Lidl R., Niderraiter G., Konechnye polya., per. s angl., 1, Mir, Moskva, 1988, 430 pp.

[7] Chasovskikh A. A., “Usloviya polnoty lineino-p-avtomatnykh funktsii”, Intellektualnye sistemy, 18:3 (2014), 203–252

[8] Lau D., Function Algebras on Finite Sets. A Basic Course on Many-Valued Logic and Clone Theory, Springer, Rostok, 2006, 668 pp.

[9] Szendrei Á., “On closed classes of quasilinear functions”, Chechoslovak Math. J., 30:3 (1980), 498–509