Standard
On tractability of disjoint AND-decomposition of boolean formulas. / Emelyanov, Pavel; Ponomaryov, Denis.
Perspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2015. p. 92-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8974).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Emelyanov, P & Ponomaryov, D 2015,
On tractability of disjoint AND-decomposition of boolean formulas. in
Perspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8974, Springer-Verlag GmbH and Co. KG, pp. 92-101, 9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014, St. Petersburg, Russian Federation,
24.06.2014.
https://doi.org/10.1007/978-3-662-46823-4_8
APA
Vancouver
Emelyanov P, Ponomaryov D.
On tractability of disjoint AND-decomposition of boolean formulas. In Perspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, Revised Selected Papers. Springer-Verlag GmbH and Co. KG. 2015. p. 92-101. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-46823-4_8
Author
Emelyanov, Pavel ; Ponomaryov, Denis. /
On tractability of disjoint AND-decomposition of boolean formulas. Perspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, Revised Selected Papers. Springer-Verlag GmbH and Co. KG, 2015. pp. 92-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{571c69bee8a54cf08f06bf93f67ecb42,
title = "On tractability of disjoint AND-decomposition of boolean formulas",
abstract = "Disjoint AND-decomposition of a boolean formula means its representation as a conjunction of two (or several) formulas having disjoint sets of variables. We show that deciding AND-decomposability is intractable in general for boolean formulas given in CNF or DNF and prove tractability of computing AND-decompositions of boolean formulas given in positive DNF, Full DNF, and ANF. The results follow 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 = "Pavel Emelyanov and Denis Ponomaryov",
year = "2015",
month = jan,
day = "1",
doi = "10.1007/978-3-662-46823-4_8",
language = "English",
isbn = "9783662468227",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "92--101",
booktitle = "Perspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, Revised Selected Papers",
address = "Germany",
note = "9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014 ; Conference date: 24-06-2014 Through 27-06-2014",
}
RIS
TY - GEN
T1 - On tractability of disjoint AND-decomposition of boolean formulas
AU - Emelyanov, Pavel
AU - Ponomaryov, Denis
PY - 2015/1/1
Y1 - 2015/1/1
N2 - Disjoint AND-decomposition of a boolean formula means its representation as a conjunction of two (or several) formulas having disjoint sets of variables. We show that deciding AND-decomposability is intractable in general for boolean formulas given in CNF or DNF and prove tractability of computing AND-decompositions of boolean formulas given in positive DNF, Full DNF, and ANF. The results follow 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 - Disjoint AND-decomposition of a boolean formula means its representation as a conjunction of two (or several) formulas having disjoint sets of variables. We show that deciding AND-decomposability is intractable in general for boolean formulas given in CNF or DNF and prove tractability of computing AND-decompositions of boolean formulas given in positive DNF, Full DNF, and ANF. The results follow 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=84942520073&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-46823-4_8
DO - 10.1007/978-3-662-46823-4_8
M3 - Conference contribution
AN - SCOPUS:84942520073
SN - 9783662468227
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 92
EP - 101
BT - Perspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, Revised Selected Papers
PB - Springer-Verlag GmbH and Co. KG
T2 - 9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014
Y2 - 24 June 2014 through 27 June 2014
ER -
