Standard

Algorithmic issues of AND-decomposition of boolean formulas. / Emelyanov, P. G.; Ponomaryov, D. K.

In: Programming and Computer Software, Vol. 41, No. 3, 01.05.2015, p. 162-169.

Research output: Contribution to journal › Article › peer-review

Harvard

Emelyanov, PG & Ponomaryov, DK 2015, 'Algorithmic issues of AND-decomposition of boolean formulas', Programming and Computer Software, vol. 41, no. 3, pp. 162-169. https://doi.org/10.1134/S0361768815030032

APA

Emelyanov, P. G., & Ponomaryov, D. K. (2015). Algorithmic issues of AND-decomposition of boolean formulas. Programming and Computer Software, 41(3), 162-169. https://doi.org/10.1134/S0361768815030032

Vancouver

Emelyanov PG, Ponomaryov DK. Algorithmic issues of AND-decomposition of boolean formulas. Programming and Computer Software. 2015 May 1;41(3):162-169. doi: 10.1134/S0361768815030032

Author

Emelyanov, P. G. ; Ponomaryov, D. K. / Algorithmic issues of AND-decomposition of boolean formulas. In: Programming and Computer Software. 2015 ; Vol. 41, No. 3. pp. 162-169.

BibTeX

@article{9407d319d9b24505bf8b705cd6f07937,
title = "Algorithmic issues of AND-decomposition of boolean formulas",
abstract = "AND-decomposition of a boolean formula means finding two (or several) formulas such that their conjunction is equivalent to the given one. Decomposition is called disjoint if the component formulas do not have variables in common. In the paper, we show that deciding AND-decomposability is intractable for boolean formulas given in CNF or DNF and prove tractability of computing disjoint AND-decomposition components of boolean formulas given in positive DNF, Full DNF, and ANF. The latter result follows from tractability of multilinear polynomial factorization over the finite field of order 2, for which we provide a polytime factorization algorithm based on identity testing for partial derivatives of multilinear polynomials.",
author = "Emelyanov, {P. G.} and Ponomaryov, {D. K.}",
year = "2015",
month = may,
day = "1",
doi = "10.1134/S0361768815030032",
language = "English",
volume = "41",
pages = "162--169",
journal = "Programming and Computer Software",
issn = "0361-7688",
publisher = "Maik Nauka Publishing / Springer SBM",
number = "3",

}

RIS

TY - JOUR

T1 - Algorithmic issues of AND-decomposition of boolean formulas

AU - Emelyanov, P. G.

AU - Ponomaryov, D. K.

PY - 2015/5/1

Y1 - 2015/5/1

N2 - AND-decomposition of a boolean formula means finding two (or several) formulas such that their conjunction is equivalent to the given one. Decomposition is called disjoint if the component formulas do not have variables in common. In the paper, we show that deciding AND-decomposability is intractable for boolean formulas given in CNF or DNF and prove tractability of computing disjoint AND-decomposition components of boolean formulas given in positive DNF, Full DNF, and ANF. The latter result follows from tractability of multilinear polynomial factorization over the finite field of order 2, for which we provide a polytime factorization algorithm based on identity testing for partial derivatives of multilinear polynomials.

AB - AND-decomposition of a boolean formula means finding two (or several) formulas such that their conjunction is equivalent to the given one. Decomposition is called disjoint if the component formulas do not have variables in common. In the paper, we show that deciding AND-decomposability is intractable for boolean formulas given in CNF or DNF and prove tractability of computing disjoint AND-decomposition components of boolean formulas given in positive DNF, Full DNF, and ANF. The latter result follows from tractability of multilinear polynomial factorization over the finite field of order 2, for which we provide a polytime factorization algorithm based on identity testing for partial derivatives of multilinear polynomials.

UR - http://www.scopus.com/inward/record.url?scp=84930629674&partnerID=8YFLogxK

U2 - 10.1134/S0361768815030032

DO - 10.1134/S0361768815030032

M3 - Article

AN - SCOPUS:84930629674

VL - 41

SP - 162

EP - 169

JO - Programming and Computer Software

JF - Programming and Computer Software

SN - 0361-7688

IS - 3

ER -

ID: 14280283