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. 
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/
@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},
     year = {2015},
     volume = {27},
     number = {2},
     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
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
%U http://geodesic.mathdoc.fr/item/DM_2015_27_2_a8/
%G ru
%F 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