The completeness criterion for systems containing all one-place bounded-determinate functions

We consider the completeness problem for the functional system $\mathrm P$ whose elements are finite-automaton functions (f.-a. functions) and the only operations are the operations of superposition. It is known that $\mathrm 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 $\mathrm P(1)$ of all one-place f.-a. functions forms a complete system in $\mathrm P$. In this paper, the completeness criterion of systems of f.-a. functions which contain $\mathrm P(1)$ is given. It allows us to construct nontrivial examples of complete systems.
The research was supported by the Russian Foundation for Basic Research, grant 00–01–00374.