A completeness criterion for nonhomogeneous functions with delays

N. V. Il'chenko

Diskretnaya Matematika, Tome 8 (1996) no. 1, pp. 86-98.

Résumé

We consider a functional system of non-homogeneous functions \[ f\colon \{0,1\}^{n}\to C,\qquad C\in \{\{0,1\},\{0,3\}\} \] with delays $t\in {\N}_{0}=\{0,1,2,\ldots \}$, i.e., the set of pairs $(f,t)$ with operations of synchronous superposition. For this system we give the description of all $\phi$-complete sets in terms of precomplete classes. A set is $\phi$-complete if using its elements and the operations mentioned above the pair $(f,t)$ for any function $f$ can be obtained. This description implies the algorithmic solvability of the $\phi$-completeness problem.