On depth and complexity of formulas in some classes of \(k\)-valued logic (Q5960278): Difference between revisions

Let \(\mathcal A\) be a finite system of functions from \(P_k\), \( k\geq 2\). It is known [see \textit{V.~R.~Pratt}, 16th Ann. Symp. Found. Comput. Sci., Berkeley, Calif. 1975, 119-121 (1975; Zbl 0469.94017)] that every finite system of functions complete in \(P_2\) is uniform. For some precomplete classes of the \(k\)-valued logic, the author proves an analytical result. For every finite system of functions \(\mathcal A\) generating one of these classes, constants \(c\) and \(d\) are found such that, for every function \(f\) from \([\mathcal A]\), the depth \(D(f)\) and the complexity \(L(f)\) of the function \(f\) in the class of formulas over \(\mathcal A\) are correlated as \[ D(f)\leq c\log_2 L(f)+d. \]