zbMATH — the first resource for mathematics

One approach to construction of effective algorithms for recognizing completeness in multivalued logics. (English. Russian original) Zbl 0615.03005
Math. Notes 39, 418-423 (1986); translation from Mat. Zametki 39, No. 5, 766-775 (1986).
Let $$E_ k$$ be the set $$\{$$ 0,1,...,k-1$$\}$$ and $$P_ k$$ be the set of all functions $$f(\bar x^ n):E^ n_ k\to E_ k$$ depending on an arbitrary number n of variables. Let $$S=\{f_ 1(\bar x^ n),...,f_ t(\bar x^ n)\}$$ be a system of functions in $$P_ k$$. The problem is to determine the completeness of S (or, in other words, whether an arbitrary function from $$P_ k$$ can be expressed in terms of the functions from S by means of the composition operation). Functions are defined by tables in which tuples of values of variables are ordered lexicographically, and numbers appearing in the tables are represented by their binary expansions. A function $$f_ i(\bar x^ n)$$ is defined by a table whose cardinality is equal to $$k^{n_ i}\cdot (n_ i+1)\cdot \log_ 2k$$ and, therefore, the cardinality of the entire input information of the problem of the completeness of system S is equal to $$\bar N=\sum^{t}_{i=1}k^ n\cdot (n_ i+1)\cdot \log_ 2k$$. To describe the algorithms, the author uses a model of computation with arbitrary access to the memory. By a step of an algorithm the author means logical operations on bit information, and time complexity of an algorithm is the dependence of the number of steps used by the algorithm to solve the completeness problem on the cardinality of input information. The author constructs algorithms with time complexity $$O(\bar N)$$ for $$k=2$$, 3, 4 and with time complexity $$O(\bar N\cdot \log \bar N)$$ for $$k=5$$, 6.
Reviewer: V.V.Gorlov
MSC:
 03B50 Many-valued logic
Full Text:
References:
 [1] A. Aho, J. Hopcroft, and J. Ulman, Construction and Analysis of Computing Algorithms [Russian translation], Mir, Moscow (1979). [2] L. Rosenberg, ?La structure des fonctions de plusieurs variables sur un ensemble fini,? C. R. Acad. Sci.,260, No. 14, 3817-3819 (1965). · Zbl 0144.01002 [3] S. V. Yablonskii, Introduction into Discrete Mathematics [in Russian], Nauka, Moscow (1979). [4] V. B. Alekseev and N. R. Emel’yanov, ?A method of construction of fast algorithms in the k-valued logic,? Mat. Zametki,38, No. 1, 148-156 (1985).
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.