Standard
A polynomial time delta-decomposition algorithm for positive DNFs. / Ponomaryov, Denis.
Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. ed. / René van Bevern; Gregory Kucherov. Springer-Verlag GmbH and Co. KG, 2019. p. 325-336 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11532 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Ponomaryov, D 2019,
A polynomial time delta-decomposition algorithm for positive DNFs. in R van Bevern & G Kucherov (eds),
Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11532 LNCS, Springer-Verlag GmbH and Co. KG, pp. 325-336, 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russian Federation,
01.07.2019.
https://doi.org/10.1007/978-3-030-19955-5_28APA
Vancouver
Ponomaryov D.
A polynomial time delta-decomposition algorithm for positive DNFs. In van Bevern R, Kucherov G, editors, Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. Springer-Verlag GmbH and Co. KG. 2019. p. 325-336. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-19955-5_28
Author
Ponomaryov, Denis. /
A polynomial time delta-decomposition algorithm for positive DNFs. Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. editor / René van Bevern ; Gregory Kucherov. Springer-Verlag GmbH and Co. KG, 2019. pp. 325-336 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{4c0de38d4d974933941f01178685a2ef,
title = "A polynomial time delta-decomposition algorithm for positive DNFs",
abstract = "We consider the problem of decomposing a positive DNF into a conjunction of DNFs, which may share a (possibly empty) given set of variables Δ. This problem has interesting connections with traditional applications of positive DNFs, e.g., in game theory, and with the broad topic of minimization of boolean functions. We show that the finest Δ -decomposition components of a positive DNF can be computed in polynomial time and provide a decomposition algorithm based on factorization of multilinear boolean polynomials.",
author = "Denis Ponomaryov",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-19955-5_28",
language = "English",
isbn = "9783030199548",
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 = "325--336",
editor = "{van Bevern}, Ren{\'e} and Gregory Kucherov",
booktitle = "Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings",
address = "Germany",
note = "14th International Computer Science Symposium in Russia, CSR 2019 ; Conference date: 01-07-2019 Through 05-07-2019",
}
RIS
TY - GEN
T1 - A polynomial time delta-decomposition algorithm for positive DNFs
AU - Ponomaryov, Denis
PY - 2019/1/1
Y1 - 2019/1/1
N2 - We consider the problem of decomposing a positive DNF into a conjunction of DNFs, which may share a (possibly empty) given set of variables Δ. This problem has interesting connections with traditional applications of positive DNFs, e.g., in game theory, and with the broad topic of minimization of boolean functions. We show that the finest Δ -decomposition components of a positive DNF can be computed in polynomial time and provide a decomposition algorithm based on factorization of multilinear boolean polynomials.
AB - We consider the problem of decomposing a positive DNF into a conjunction of DNFs, which may share a (possibly empty) given set of variables Δ. This problem has interesting connections with traditional applications of positive DNFs, e.g., in game theory, and with the broad topic of minimization of boolean functions. We show that the finest Δ -decomposition components of a positive DNF can be computed in polynomial time and provide a decomposition algorithm based on factorization of multilinear boolean polynomials.
UR - http://www.scopus.com/inward/record.url?scp=85068608615&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-19955-5_28
DO - 10.1007/978-3-030-19955-5_28
M3 - Conference contribution
AN - SCOPUS:85068608615
SN - 9783030199548
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 325
EP - 336
BT - Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings
A2 - van Bevern, René
A2 - Kucherov, Gregory
PB - Springer-Verlag GmbH and Co. KG
T2 - 14th International Computer Science Symposium in Russia, CSR 2019
Y2 - 1 July 2019 through 5 July 2019
ER -
