RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2015 Volume 27, Issue 2, Pages 134–151 (Mi dm1330)

This article is cited in 12 papers

Completeness problem for the class of linear automata functions

Anatoliy A. Chasovskikh

Lomonosov Moscow State University

Abstract: 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.

UDC: 519.716.3

Received: 17.03.2015

DOI: 10.4213/dm1330


 English version:
Discrete Mathematics and Applications, 2016, 26:2, 89–104

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025