Using Decomposition-Parameters for QBF: Mind the Prefix!

D 2016

Using Decomposition-Parameters for QBF: Mind the Prefix!

GANIAN, Robert, Sebastian ORDYNIAK a Eduard EIBEN

Základní údaje

Originální název

Using Decomposition-Parameters for QBF: Mind the Prefix!

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), Sebastian ORDYNIAK (276 Německo) a Eduard EIBEN (703 Slovensko)

Vydání

USA, Proceedings of the Thirtieth {AAAI} Conference on Artificial Intelligence, od s. 964-970, 7 s. 2016

Nakladatel

AAAI Press

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/16:00093941

Organizační jednotka

Fakulta informatiky

ISBN

978-1-57735-760-5

Klíčová slova anglicky

QBF; treewidth

Štítky

core_A, firank_1

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 12. 5. 2020 19:47, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Similar to the satisfiability (SAT) problem, which can be seen to be the archetypical problem for NP, the quantified Boolean formula problem (QBF) is the archetypical problem for PSPACE. Recently, Atserias and Oliva (2014) showed that, unlike for SAT, many of the well-known decompositional parameters (such as treewidth and pathwidth) do not allow efficient algorithms for QBF. The main reason for this seems to be the lack of awareness of these parameters towards the dependencies between variables of a QBF formula. In this paper we extend the ordinary pathwidth to the QBF-setting by introducing prefix pathwidth, which takes into account the dependencies between variables in a QBF, and show that it leads to an efficient algorithm for QBF. We hope that our approach will help to initiate the study of novel tailor-made decompositional parameters for QBF and thereby help to lift the success of these decompositional parameters from SAT to QBF.

Citovat

GANIAN, Robert, Sebastian ORDYNIAK a Eduard EIBEN. Using Decomposition-Parameters for QBF: Mind the Prefix!. Online. In Dale Schuurmans, Michael P. Wellman. Proceedings of the Thirtieth {AAAI} Conference on Artificial Intelligence. USA: AAAI Press, 2016, s. 964-970. ISBN 978-1-57735-760-5.

@inproceedings{1376008,
   author = {Ganian, Robert and Ordyniak, Sebastian and Eiben, Eduard},
   address = {USA},
   booktitle = {Proceedings of the Thirtieth {AAAI} Conference on Artificial Intelligence},
   editor = {Dale Schuurmans, Michael P. Wellman},
   keywords = {QBF; treewidth},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {USA},
   isbn = {978-1-57735-760-5},
   pages = {964-970},
   publisher = {AAAI Press},
   title = {Using Decomposition-Parameters for QBF: Mind the Prefix!},
   url = {https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12420},
   year = {2016}
}

TY  - JOUR
ID  - 1376008
AU  - Ganian, Robert - Ordyniak, Sebastian - Eiben, Eduard
PY  - 2016
TI  - Using Decomposition-Parameters for QBF: Mind the Prefix!
PB  - AAAI Press
CY  - USA
SN  - 9781577357605
KW  - QBF
KW  - treewidth
UR  - https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12420
N2  - Similar to the satisfiability (SAT) problem, which can be seen to be the archetypical problem for NP, the quantified Boolean formula problem (QBF) is the archetypical problem for PSPACE. Recently, Atserias and Oliva (2014) showed that, unlike for SAT, many of the well-known decompositional parameters (such as treewidth and pathwidth) do not allow efficient algorithms for QBF. The main reason for this seems to be the lack of awareness of these parameters towards the dependencies between variables of a QBF formula. In this paper we extend the ordinary pathwidth to the QBF-setting by introducing prefix pathwidth, which takes into account the dependencies between variables in a QBF, and show that it leads to an efficient algorithm for QBF. We hope that our approach will help to initiate the study of novel tailor-made decompositional parameters for QBF and thereby help to lift the success of these decompositional parameters from SAT to QBF.
ER  -

GANIAN, Robert, Sebastian ORDYNIAK a Eduard EIBEN. Using Decomposition-Parameters for QBF: Mind the Prefix!. Online. In Dale Schuurmans, Michael P. Wellman. \textit{Proceedings of the Thirtieth $\{$AAAI$\}$ Conference on Artificial Intelligence}. USA: AAAI Press, 2016, s.~964-970. ISBN~978-1-57735-760-5.

Podrobný výpis o publikaci