High Accuracy Asymptotic Bounds for Predicate Circuits over a Class of Specific Predicate Bases
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 173-184
Voir la notice du chapitre de livre provenant de la source Math-Net.Ru
Synthesis problem for a specific class of control systems called predicate circuits is considered. This class generalizes most of well-known control-system classes (such as circuit of functional elements, contact circuits etc.). Predicate circuits are constructed with the use or predicate elements and therefore usually have no predefined direction of signal distribution. Asymptotic behavior of the Shannon's function $\mathcal L_\mathfrak B(n)$ is investigated for complexity of $n$-variable predicate implementation with the use of predicate circuits over basis $\mathfrak B$ of specific structure. The following high accuracy asymptotic bounds are acquired $$ \mathcal L_\mathfrak B(n)=\rho_\mathfrak B\frac{2^n}n\Biggl(1+\frac{\bigl(2+\frac1{k_\mathfrak B-1}\bigr)\log_2n\pm O(1)}n\Biggr), $$ where $\rho_\mathfrak B$ and $k_\mathfrak B$ are basis-dependent constants.
Keywords:
circuits of predicate elements, complexity, Shannon's function, high accuracy asymptotic bounds.
@article{UZKU_2009_151_2_a21,
author = {M. S. Shupletsov},
title = {High {Accuracy} {Asymptotic} {Bounds} for {Predicate} {Circuits} over {a~Class} of {Specific} {Predicate} {Bases}},
journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
pages = {173--184},
publisher = {mathdoc},
volume = {151},
number = {2},
year = {2009},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a21/}
}
TY - JOUR AU - M. S. Shupletsov TI - High Accuracy Asymptotic Bounds for Predicate Circuits over a Class of Specific Predicate Bases JO - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki PY - 2009 SP - 173 EP - 184 VL - 151 IS - 2 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a21/ LA - ru ID - UZKU_2009_151_2_a21 ER -
%0 Journal Article %A M. S. Shupletsov %T High Accuracy Asymptotic Bounds for Predicate Circuits over a Class of Specific Predicate Bases %J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki %D 2009 %P 173-184 %V 151 %N 2 %I mathdoc %U http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a21/ %G ru %F UZKU_2009_151_2_a21
M. S. Shupletsov. High Accuracy Asymptotic Bounds for Predicate Circuits over a Class of Specific Predicate Bases. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 173-184. http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a21/