Zobrazeno 1 - 10
of 106
pro vyhledávání: '"H. Heule"'
Publikováno v:
Logical Methods in Computer Science, Vol Volume 18, Issue 2 (2022)
We introduce FRAT, a new proof format for unsatisfiable SAT problems, and its associated toolchain. Compared to DRAT, the FRAT format allows solvers to include more information in proofs to reduce the computational cost of subsequent elaboration to L
Externí odkaz:
https://doaj.org/article/39d6c5b18ead41d0b2179fd6251581da
Publikováno v:
International Journal on Software Tools for Technology Transfer. 25:167-184
Modern SAT solvers can emit independently-checkable proof certificates to validate their results. The state-of-the-art proof system that allows for compact proof certificates is propagation redundancy ($$\textsf{PR}$$ PR ). However, the only existing
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::aaec5812085e22ae2dd1b3ecf26d25c1
https://doi.org/10.1007/s10009-022-00690-y
https://doi.org/10.1007/s10009-022-00690-y
Publikováno v:
Tools and Algorithms for the Construction and Analysis of Systems ISBN: 9783031308222
Modern SAT solvers produce proofs of unsatisfiability to justify the correctness of their results. These proofs, which are usually represented in the well-known DRAT format, can often become huge, requiring multiple gigabytes of disk storage. We pres
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::43fa9cccf1101e56f6aa3c424339e035
https://doi.org/10.1007/978-3-031-30823-9_17
https://doi.org/10.1007/978-3-031-30823-9_17
Autor:
Dawn Michaelson, Dominik Schreiber, Marijn J. H. Heule, Benjamin Kiesl-Reiter, Michael W. Whalen
Publikováno v:
Tools and Algorithms for the Construction and Analysis of Systems ISBN: 9783031308222
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Tools and Algorithms for the Construction and Analysis of Systems
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Tools and Algorithms for the Construction and Analysis of Systems
Distributed clause-sharing SAT solvers can solve problems up to one hundred times faster than sequential SAT solvers by sharing derived information among multiple sequential solvers working on the same problem. Unlike sequential solvers, however, dis
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f9e4076eaebdc682eeec5ecb8d660d7f
https://doi.org/10.1007/978-3-031-30823-9_18
https://doi.org/10.1007/978-3-031-30823-9_18
Publikováno v:
Journal of Symbolic Computation. 104:899-916
It is known since the 1970s that no more than 23 multiplications are required for computing the product of two 3 × 3 -matrices. For non-commutative coefficient rings, it is not known whether it can also be done with fewer multiplications. However, t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::185c5945d1ba7597d64242b7638630ef
https://doi.org/10.1016/j.jsc.2020.10.003
https://doi.org/10.1016/j.jsc.2020.10.003
Autor:
Randal E. Bryant, Marijn J. H. Heule
Publikováno v:
Tools and Algorithms for the Construction and Analysis of Systems
In 2006, Biere, Jussila, and Sinz made the key observation that the underlying logic behind algorithms for constructing Reduced, Ordered Binary Decision Diagrams (BDDs) can be encoded as steps in a proof in the extended resolution logical framework.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0f7256e4da869591af0961bff3614358
http://europepmc.org/articles/PMC7979187
http://europepmc.org/articles/PMC7979187
Publikováno v:
Journal of Automated Reasoning. 64:1247-1267
Proof systems for propositional logic provide the basis for decision procedures that determine the satisfiability status of logical formulas. While the well-known proof system of extended resolution—introduced by Tseitin in the sixties—allows for
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0ecbe0932159fd9de74dfbfb392ac0f6
https://doi.org/10.1007/s10817-020-09554-z
https://doi.org/10.1007/s10817-020-09554-z
Autor:
Sean A. Weaver, Marijn J. H. Heule
Publikováno v:
AAAI
Minimal perfect hash functions (MPHFs) are used to provide efficient access to values of large dictionaries (sets of key-value pairs). Discovering new algorithms for building MPHFs is an area of active research, especially from the perspective of sto
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3d1309a1e0335053ec1766cfd6318c1e
https://doi.org/10.1609/aaai.v34i02.5529
https://doi.org/10.1609/aaai.v34i02.5529
Autor:
Marijn J. H. Heule
Publikováno v:
Mathematics in Computer Science. 13:533-548
Symmetry breaking is a crucial technique to solve many graph problems. However, current state-of-the-art techniques break graph symmetries only partially, causing search algorithms to unnecessarily explore many isomorphic parts of the search space. W
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4e03f1d05f02c2d70eee7d3c1864df3a
https://doi.org/10.1007/s11786-019-00397-5
https://doi.org/10.1007/s11786-019-00397-5
We explore the Collatz conjecture and its variants through the lens of termination of string rewriting. We construct a rewriting system that simulates the iterated application of the Collatz function on strings corresponding to mixed binary–ternary
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e254512d0c10791be52f68095ce1a447
http://arxiv.org/abs/2105.14697
http://arxiv.org/abs/2105.14697