Article collection "Mathematical Problems of Cybernetics" №16, Moscow, 2007

Authors:Buevich V.A., Podkolzina M.A.

A completeness criterion of S-sets of deterministic functions

Abstract:

The present paper considers functional completeness in a sequential functional system whose elements are deterministic funtions defined on words of length τ in the alphabet E_{k} ={0, 1, . . ., k−1}. The paper considers the problem of completeness for so-called S-sets, containing only S-functions, i.e. deterministic functions computed by finite automata, every state of which realizes a k-valued logic function taking all k values.