Geodesic
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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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},
     year = {2009},
     volume = {151},
     number = {2},
     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
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
%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/

[1] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, M., 1984, 136 pp.

[2] Shannon C. E., “The synthethis of two-terminal switching circuits”, Bell Syst. Techn. J., 28:1 (1949), 59–98 | DOI | MR

[3] Lozhkin S. A., Shupletsov M. S., “Asimptoticheskie otsenki vysokoi stepeni tochnosti dlya slozhnosti predikatnykh skhem iz odnogo klassa”, Materialy XVI Mezhdunar. shkoly-seminara “Sintez i slozhnost upravlyayuschikh sistem” (Sankt-Peterburg, 26–30 iyunya 2006 g.), Izd-vo mekh.-matem. fak-ta MGU, M., 2006, 72–77

[4] Shupletsov M. S., “Otsenki slozhnosti predikatnykh skhem v nekotorykh bazisakh”, Problemy teoreticheskoi kibernetiki, Tez. dokl. XV Mezhdunar. konf. (Kazan, 2–7 iyunya 2008 g.), ed. Yu. I. Zhuravlev, Otechestvo, Kazan, 2008, 134–135

[5] Lozhkin S. A., “Otsenki vysokoi stepeni tochnosti dlya slozhnosti upravlyayuschikh sistem iz nekotorykh klassov”, Matem. vopr. kibernetiki, 6, Nauka, M., 1996, 189–214 | MR

[6] Lozhkin S. A., Otsenki vysokoi stepeni tochnosti dlya slozhnosti upravlyayuschikh sistem iz nekotorykh klassov, Dis. $\dots$ d-ra fiz.-mat. nauk, M., 1997

[7] Bodnarchuk V. G., Kaluzhnin L. A., Kotov V. N., Romov B. A., “Teoriya Galua dlya algebr Posta”, Kibernetika, 1969, no. 3, 1–10 ; no. 5, 1–9 | Zbl | MR

[8] Kuznetsov A. V., “O sredstvakh dlya obnaruzheniya nevyvodimosti ili nevyrazimosti”, Logicheskii vyvod, Nauka, M., 1979, 5–33

[9] Kasim-Zade O. M., “O slozhnosti parametricheskikh predstavlenii bulevykh funktsii”, Matem. vopr. kibernetiki, 7, Nauka, M., 1998, 85–160 | MR