Zobrazeno 1 - 10
of 75
pro vyhledávání: '"Olaf Beyersdorff"'
Autor:
Olaf Beyersdorff, Benjamin Böhm
Publikováno v:
Logical Methods in Computer Science, Vol Volume 19, Issue 2 (2023)
QBF solvers implementing the QCDCL paradigm are powerful algorithms that successfully tackle many computationally complex applications. However, our theoretical understanding of the strength and limitations of these QCDCL solvers is very limited. In
Externí odkaz:
https://doaj.org/article/088c96270fef4608aae2d40380ec8160
Publikováno v:
Logical Methods in Computer Science, Vol Volume 15, Issue 1 (2019)
As a natural extension of the SAT problem, an array of proof systems for quantified Boolean formulas (QBF) have been proposed, many of which extend a propositional proof system to handle universal quantification. By formalising the construction of th
Externí odkaz:
https://doaj.org/article/67f81314a6e343eca53ee1195a891e86
Publikováno v:
Logical Methods in Computer Science, Vol Volume 13, Issue 2 (2017)
In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. In this paper we establish the feasible interpolation technique for all resolution-based QBF systems, whether modelling CDCL or ex
Externí odkaz:
https://doaj.org/article/e9413774f0d3414c8d02560c9ead25ef
Autor:
Olaf Beyersdorff, Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Heribert Vollmer
Publikováno v:
Logical Methods in Computer Science, Vol Volume 7, Issue 2 (2011)
The model checking problem for CTL is known to be P-complete (Clarke, Emerson, and Sistla (1986), see Schnoebelen (2002)). We consider fragments of CTL obtained by restricting the use of temporal modalities or the use of negations---restrictions alre
Externí odkaz:
https://doaj.org/article/d77ddb64fd9249a888fce26fc6b626e8
Publikováno v:
Mathematics for Computation (M4C). :i-xiii
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5ce89ee3e8427239e8da8b2c19bea961
https://doi.org/10.1142/9789811245220_fmatter
https://doi.org/10.1142/9789811245220_fmatter
Autor:
Olaf Beyersdorff
Publikováno v:
Mathematics for Computation (M4C) ISBN: 9789811245213
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::98cd558a30fac3c422910e2378800f13
https://doi.org/10.1142/9789811245220_0015
https://doi.org/10.1142/9789811245220_0015
Publikováno v:
Mathematics for Computation (M4C). :461-462
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::28a360b362c9c0f552c390b9adffbfdd
https://doi.org/10.1142/9789811245220_bmatter
https://doi.org/10.1142/9789811245220_bmatter
Autor:
Sarah Sigley, Olaf Beyersdorff
Publikováno v:
Journal of Automated Reasoning
We investigate the proof complexity of modal resolution systems developed by Nalon and Dixon (J Algorithms 62(3–4):117–134, 2007) and Nalon et al. (in: Automated reasoning with analytic Tableaux and related methods—24th international conference
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3450f70fe44312da739a4dacf6ba6fab
https://doi.org/10.1007/s10817-021-09609-9
https://doi.org/10.1007/s10817-021-09609-9
Autor:
Benjamin Böhm, Olaf Beyersdorff
QCDCL is one of the main algorithmic paradigms for solving quantified Boolean formulas (QBF). We design a new technique to show lower bounds for the running time in QCDCL algorithms. For this we model QCDCL by concisely defined proof systems and iden
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::16659f8bd391601663227f98760bf480
https://doi.org/10.21203/rs.3.rs-1796853/v1
https://doi.org/10.21203/rs.3.rs-1796853/v1
Publikováno v:
UPCommons. Portal del coneixement obert de la UPC
Universitat Politècnica de Catalunya (UPC)
Universitat Politècnica de Catalunya (UPC)
We define and investigate Frege systems for quantified Boolean formulas (QBF). For these new proof systems, we develop a lower bound technique that directly lifts circuit lower bounds for a circuit class C to the QBF Frege system operating with lines
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b1a71059526abcfaa4d32b866518de6d
https://doi.org/10.1145/3381881
https://doi.org/10.1145/3381881