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.

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