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. стр. 92-101 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 8974).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Emelyanov, P & Ponomaryov, D 2015, On tractability of disjoint AND-decomposition of boolean formulas. в 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), Том. 8974, Springer-Verlag GmbH and Co. KG, стр. 92-101, 9th International Ershov Informatics Conference on Perspectives of System Informatics, PSI 2014, St. Petersburg, Российская Федерация, 24.06.2014. https://doi.org/10.1007/978-3-662-46823-4_8

APA

Emelyanov, P., & Ponomaryov, D. (2015). On tractability of disjoint AND-decomposition of boolean formulas. в Perspectives of System Informatics - 9th International Ershov Informatics Conference, PSI 2014, Revised Selected Papers (стр. 92-101). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 8974). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-662-46823-4_8

Vancouver

Emelyanov P, Ponomaryov D. 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. стр. 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. стр. 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 -

ID: 14280239