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 P_{k}, 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 log_{2} L(f) +
d. We
also show the existence of finite generating systems
satisfying this condition for all precomplete
classes in P_{k}, 2 ≤ k ≤ 7, and
for all
precomplete classes of type C in P_{k}, k
≥
2.

Keywords:

precomplete classes of k-valued logic, depth and
complexity of formulas