# zbMATH — the first resource for mathematics

The completeness criterion for systems which contain all one-place finite-automaton functions. (English. Russian original) Zbl 1088.68631
Discrete Math. Appl. 10, No. 6, 613-634 (2000); translation from Diskretn. Mat. 12, No. 4, 138-158 (2000).
Summary: We consider the completeness problem for the functional system $$P$$ whose elements are finite-automaton functions (f.-a. functions) and the only operations are the operations of superposition. It is known that $$P$$ does not contain finite complete systems. However, D. N. Babin constructed an example of a finite set of f.-a. functions which together with the set $$P(1)$$ of all one-place f.-a. functions forms a complete system in $$P$$. In this paper, the completeness criterion of systems of f.-a. functions which contain $$P(1)$$ is given. It allows us to construct nontrivial examples of complete systems.

##### MSC:
 68Q45 Formal languages and automata 03B50 Many-valued logic
Full Text: