KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №13, Moscow, 2004
Authors: Safin R.F.
On the Relation Between Depth and Complexity of Formulas in Precomplete Classes of k-Valued Logic.
Abstract:
In this paper we consider the relation between depth and complexity of formulas in precomplete classes of k-valued logic. For all precomplete classes of types E, B, L, P and some precomplete classes of types O and C in Pk, k ≥ 3, we show that any finite system of functions A generating any of these classes satisfies the following condition: there exist constants c and d such that for any function f from [A] the depth D(f) and the complexity L(f) of function f in the class of formulas over A satisfy the relation D(f) ≤ c log2 L(f) + d. We also show the existence of finite generating systems satisfying this condition for all precomplete classes in Pk, 2 ≤ k ≤ 7, and for all precomplete classes of type C in Pk, k ≥ 2.
Keywords:
precomplete classes of k-valued logic, depth and complexity of formulas
Publication language: russian,  страниц: 56 (p. 223-278)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text: