Geodesic
On Full Checking Tests under Local Glueings of Variables in Boolean Functions
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. 90-97
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A local $k$-fold glueing of variables in Boolean function $f(\widetilde x^n)$ is a function obtained as a result of substitution instead of some $k$ successive variables an arbitrary Boolean function depending on these variables ($2\le k\le n$). Full checking tests under local $k$-fold glueings of variables in Boolean functions $f(\widetilde x^n)$ are studied in this paper. It is established that if $n\to\infty$, $(n-k)\to\infty$, $k\to\infty$, then an asymptotics of Shannon function of the test length is $2^{k-1}(n-k+2)$. Furthermore, let $n\to\infty$, $(n-k)\to\infty$, $\gamma(n,k)\to\infty$, $\gamma(n,k)=o(\log_2(n-k))$, therefore, a set of $n$-tuples exists which is full checking test under local $k$-fold glueings of variables in almost all Boolean functions $f(\widetilde x^n)$ and whose power is not greater than $\lceil\log_{4/3}(n-k+1)+\gamma(n,k)\rceil$. At last, under conditions $n\to\infty$, $2\le k\le n$, $(n-k)\to\infty$, a length of minimal full checking test under local $k$-fold glueings of variables is not greater than 3 for almost all Boolean functions $f(\widetilde x^n)$.
Keywords: Boolean function, test for inputs of circuits, local glueing of variables. 
@article{UZKU_2009_151_2_a10,
     author = {I. A. Kuzhetsov and D. S. Romanov},
     title = {On {Full} {Checking} {Tests} under {Local} {Glueings} of {Variables} in {Boolean} {Functions}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {90--97},
     year = {2009},
     volume = {151},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a10/}
}
TY  - JOUR
AU  - I. A. Kuzhetsov
AU  - D. S. Romanov
TI  - On Full Checking Tests under Local Glueings of Variables in Boolean Functions
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2009
SP  - 90
EP  - 97
VL  - 151
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a10/
LA  - ru
ID  - UZKU_2009_151_2_a10
ER  - 
%0 Journal Article
%A I. A. Kuzhetsov
%A D. S. Romanov
%T On Full Checking Tests under Local Glueings of Variables in Boolean Functions
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2009
%P 90-97
%V 151
%N 2
%U http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a10/
%G ru
%F UZKU_2009_151_2_a10
I. A. Kuzhetsov; D. S. Romanov. On Full Checking Tests under Local Glueings of Variables in Boolean Functions. 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. 90-97. http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a10/

[1] Noskov V. N., “Diagnosticheskie testy dlya vkhodov logicheskikh ustroistv”, Diskretnyi analiz, 26, IM SO AN SSSR, Novosibirsk, 1974, 72–83 | MR

[2] Noskov V. N., “O slozhnosti testov, kontroliruyuschikh rabotu vkhodov logicheskikh skhem”, Diskretnyi analiz, 27, IM SO AN SSSR, Novosibirsk, 1975, 23–51 | MR

[3] Noskov V. N., “O dlinakh minimalnykh edinichnykh diagnosticheskikh testov, kontroliruyuschikh rabotu vkhodov logicheskikh skhem”, Metody diskretnogo analiza v sinteze upravlyayuschikh sistem, Diskretnyi analiz, 32, IM SO AN SSSR, Novosibirsk, 1978, 40–51 | MR

[4] Noskov V. N., “Ob universalnykh testakh dlya diagnostiki odnogo klassa neispravnostei kombinatsionnykh skhem”, Metody diskretnogo analiza v reshenii ekstremalnykh zadach, Diskretnyi analiz, 33, IM SO AN SSSR, Novosibirsk, 1979, 41–52 | MR

[5] Nurmeev N. N., “Ob universalnykh diagnosticheskikh testakh dlya odnogo klassa neispravnostei kombinatsionnykh skhem”, Veroyatnostnye metody i kibernetika, 18, Izd-vo Kazan. un-ta, Kazan, 1982, 73–76

[6] Pogosyan G. R., O proveryayuschikh testakh dlya logicheskikh skhem, VTs AN SSSR, M., 1982, 57 pp.