zbMATH — the first resource for mathematics

Superpositions of bounded-deterministic functions. (English. Russian original) Zbl 0795.68137
Math. Notes 47, No. 3, 231-235 (1990); translation from Mat. Zametki 47, No. 3, 3-10 (1990).
Summary: We consider the problem of completeness of systems of bounded- deterministic functions under superposition. It is known that finite complete systems of b-d. functions do not exist. The known complete systems contain functions with (jointly) unbounded number of variables. We show that any b.-d. function is representable as a superposition of b.-d. functions of two variables. More precisely, any b.-d. function is generated by one-place b.-d. functions and Boolean functions.

68Q45 Formal languages and automata
03D05 Automata and formal grammars in connection with logical questions
PDF BibTeX Cite
Full Text: DOI
[1] V. B. Kudryavtsev, S. V. Aleshin, and A. S. Podkolzin, An Introduction to Automata Theory [in Russian], Nauka, Moscow (1985), pp. 151-174. · Zbl 0604.68058
[2] S. S. Marchenkov, ?On one method of analysis of superpositions of continuous functions,? Probl. Kibern., No. 37, 5-17 (1980). · Zbl 0472.26006
[3] V. B. Kudryavtsev, ?On cardinality of sets of some function system associated with automata,? Probl. Kibern., No. 13, 45-57 (1965).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.