zbMATH — the first resource for mathematics

A problem of completeness of S-sets of deterministic functions. (English. Russian original) Zbl 1304.68096
Mosc. Univ. Math. Bull. 63, No. 5, 211-213 (2008); translation from Vest. Mosk. Univ. Mat. Mekh. 63, No. 5, 57-59 (2008).
Summary: A problem of completeness of S-deterministic functions determined on words of length \(\tau\) is considered. The set of all precomplete classes forming the minimal criterial system for recognition of the completeness of arbitrary S-sets of deterministic functions is described in terms of preservation of relations (predicates).
68Q45 Formal languages and automata
08A40 Operations and polynomials in algebraic structures, primal algebras
Full Text: DOI
[1] V. B. Kudryavtsev, S. V. Aleshin, and A. S. Podkolzin, Introduction to the Theory of Automata (Nauka, Moscow, 1985) [in Russian].
[2] Y. Rosenberg, La structure des fonctions de plusieure variables sur un ensemble fini, C.r. Acad. sci. Paris, 3817 (1965). · Zbl 0144.01002
[3] V. B. Kudryavtsev, ”Properties of S-Systems of Functions in k-Valued Logic,” Elektronische Informationsverarbeitung und Kybernetik. 9(1–2), 8 (1973).
[4] V. A. Buevich and M. A. Podkolzina, ”Completeness Criterion of S-Completeness of Sets of Deterministic Functions,” in Matem. Voprosy Kibern. 16 (Nauka, Fizmatlit, Moscow, 2008), pp. 191–239. · Zbl 1202.03033
[5] V. A. Buevich, ”\(\tau\)-Completeness in the Class of Deterministic Functions,” Dokl. Russ. Akad. Nauk 326(3), 399 (1992). · Zbl 0921.03026
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.