Geodesic
About some properties of Horn and anti-Horn functions
Prikladnaâ diskretnaâ matematika, no. 2 (2013), pp. 5-13.

Voir la notice de l'article provenant de la source Math-Net.Ru

Some properties of weakly positive (anti-Horn) and weakly-negative (Horn) Boolean functions are investigated. Particularly, estimates are given for the complexity of constructing reduced form and for the possible lengths of expressions of considered functions, and it is shown that there are no limits for the weight of such functions.
Keywords: weakly positive (anti-Horn) Boolean function, weakly negative (Horn) Boolean function, computing complexity. 
@article{PDM_2013_2_a0,
     author = {S. P. Gorshkov},
     title = {About some properties of {Horn} and {anti-Horn} functions},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {5--13},
     publisher = {mathdoc},
     number = {2},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_2_a0/}
}
TY  - JOUR
AU  - S. P. Gorshkov
TI  - About some properties of Horn and anti-Horn functions
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 5
EP  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_2_a0/
LA  - ru
ID  - PDM_2013_2_a0
ER  - 
%0 Journal Article
%A S. P. Gorshkov
%T About some properties of Horn and anti-Horn functions
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 5-13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_2_a0/
%G ru
%F PDM_2013_2_a0
S. P. Gorshkov. About some properties of Horn and anti-Horn functions. Prikladnaâ diskretnaâ matematika, no. 2 (2013), pp. 5-13. http://geodesic.mathdoc.fr/item/PDM_2013_2_a0/

[1] Gorshkov S. P., “O slozhnosti nakhozhdeniya privedënnykh predstavlenii slabo polozhitelnykh i slabo otritsatelnykh bulevykh funktsii”, Prikladnaya diskretnaya matematika, 2008, no. 1, 7–9

[2] Gizunov S. A., Nosov V. A., “O klassifikatsii vsekh bulevykh funktsii chetyrëkh peremennykh po klassam Sheffera”, Obozrenie prikladnoi promyshlennoi matematiki. Ser. diskretnoi matematiki, 2:3 (1995), 440–467

[3] Grettser G., Obschaya teoriya reshëtok, Mir, M., 1982, 456 pp. | MR

[4] Alekseev V. B., “O chisle semeistv podmnozhestv, zamknutykh otnositelno peresecheniya”, Diskretnaya matematika, 1:2 (1989), 129–136 | MR | Zbl

[5] Korshunov A. D., “O chisle monotonnykh bulevykh funktsii”, Problemy kibernetiki, 38, Nauka, M., 1981, 5–108 | MR

[6] Gorshkov S. P., “O slozhnosti raspoznavaniya multiaffinnosti, biyunktivnosti, slaboi polozhitelnosti i slaboi otritsatelnosti bulevykh funktsii”, Obozrenie prikladnoi promyshlennoi matematiki. Ser. diskretnoi matematiki, 4:2 (1997), 440–467

[7] Gorshkov S. P., “Primenenie teorii NP-polnykh zadach dlya otsenki slozhnosti resheniya sistem bulevykh uravnenii”, Obozrenie prikladnoi promyshlennoi matematiki. Ser. diskretnoi matematiki, 2:3 (1995), 325–398

[8] Gorshkov S. P., Tarasov A. V., “O maksimalnykh gruppakh invariantnykh preobrazovanii multiaffinnykh, biyunktivnykh, slabo polozhitelnykh i slabo otritsatelnykh bulevykh funktsii”, Diskretnaya matematika, 21:2 (2009), 94–101 | DOI | MR | Zbl

[9] Schaefer T., “Complexity of satisfiability problems”, Proc. 10 Annual ACM Symposium on Theory of Computing Machinery, ACM, New York, NY, USA, 1978, 216–226 | MR

[10] Tarasov A. V., “O svoistvakh funktsii, predstavimykh v vide 2-KNF”, Diskretnaya matematika, 13:4 (2001), 99–115 | DOI | MR | Zbl

[11] Gorshkov S. P., “O peresechenii klassov multiaffinnykh, biyunktivnykh, slabo polozhitelnykh i slabo otritsatelnykh bulevykh funktsii”, Obozrenie prikladnoi promyshlennoi matematiki. Ser. diskretnoi matematiki, 4:2 (1997), 238–259