Buevich, V. A. 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. Cited in 1 Document MSC: 68Q45 Formal languages and automata 03B50 Many-valued logic PDF BibTeX XML Cite \textit{V. A. Buevich}, Discrete Math. Appl. 10, No. 6, 613--634 (2000; Zbl 1088.68631); translation from Diskretn. Mat. 12, No. 4, 138--158 (2000) Full Text: DOI