History log of /seL4-l4v-10.1.1/HOL4/src/HolQbf/QbfCertificate.sml
Revision Date Author Comments
# fda6dec3 20-Oct-2015 Michael Norrish <Michael.Norrish@nicta.com.au>

Clean src/ to remove Unicode (or to mark it as OK)

Marking Unicode as OK is done by putting the UOK tag on the same line of
the relevant file.


# 26e7e11f 02-Feb-2012 Ramana Kumar <ramana.kumar@gmail.com>

make HolQbfLib's sat solver customisable

crude method using a ref cell. if there's a standard better approach let
me know/fix it.


# 7398aea7 02-Feb-2012 Ramana Kumar <ramana.kumar@gmail.com>

remove calls to Profile.profile in QbfCertificate.sml

presumably only need to run profiling code when testing/improving the
library, not for normal use.


# b369148d 02-Sep-2011 Ramana Kumar <ramana.kumar@gmail.com>

Use CHOOSE+EXISTS instead of INST+PROVE_HYP in HolQbf

This change, suggested by Michael, showed a dramatic speed improvement
(looks like an order of magnitude) on the benchmarks (run by Tjark). It
is not obvious why.


# 19f7fca5 17-Feb-2011 Ramana Kumar <ramana.kumar@gmail.com>

Replace false comment in HolQbf valid certificate checker implementation


# a3f8f983 14-Feb-2011 Ramana Kumar <ramana.kumar@gmail.com>

Use new Redblackmap update function in HolQbf


# c091138f 13-Feb-2011 Ramana Kumar <ramana.kumar@gmail.com>

Improve HolQbf valid certificate validator

Time complexity should now be O(n*log(n)) where n is the total number of
variables (universal, existential, and extension) in the certificate,
whereas before it was more like O(n*n).


# e0c23413 16-Jan-2011 Ramana Kumar <ramana.kumar@gmail.com>

Remove an unused function in QbfCertificate.sml


# 97aa03ad 16-Jan-2011 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

Slightly improved final sanity checks.


# bfe8b4d3 15-Jan-2011 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

Added functions to prove/decide QBFs. Added profiling calls to QbfCertificate (for now).


# 1fb59e86 15-Jan-2011 Ramana Kumar <ramana.kumar@gmail.com>

QbfCertificate: use alternative method for discharging hypotheses

(To create the theorem for a valid certificate.)
This is hopefully faster than HO_MATCH_MP, although some evidence via
profiling would be nice.


# 6bd65fd4 14-Jan-2011 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

read_qdimacs_file now takes an additional argument, varfn, that translates
QDIMACS variable indices into HOL variable names.


# c753052a 21-Dec-2010 Ramana Kumar <ramana.kumar@gmail.com>

Rewrite of HolQbfLib's valid certificate validator

The new version:
- allows certificates that define extension variables in terms of
other extension variables (which squolem does generate)
- gives the witnesses as equality hypotheses rather than by actual
substitution, to reduce the size of the term passed to SAT_PROVE
- works on almost half of Tjark's tests (not included) in under 60
seconds each


# 5ff9a2e3 27-Nov-2010 Ramana Kumar <ramana.kumar@gmail.com>

Make dict argument to QbfCertificate.check optional

If SOME dict is passed, it should be a map from variables in the term to
literal indexes. If NONE is passed, assume the term was generated by
QDimacs.read_qdimacs_file, which preserves literal indexes in the
variable names.


# 14387f48 21-Nov-2010 Ramana Kumar <ramana.kumar@gmail.com>

Make HolQbfLib prove QBFs (validate Squolem validity certificates)

A sketch that uses SAT_PROVE on a qb formula after replacing the
existential variables with witnesses generated by Squolem.

It works on the simple tautologies in the selftest file.


# 4953551c 11-Nov-2010 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

Parsing of resolution steps more closely follows the grammar in "A File Format
for QBF Certificates".


# 1e80a48d 11-Nov-2010 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

HolQbfLib now supports Squolem2.


# b71cc562 28-Jul-2010 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

Typo fixed.


# 0b6302a2 05-Jun-2010 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

Made Moscow ML happy.


# 54e69795 15-Mar-2010 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

Unit tests, tracing, and various other additions.


# c135e30d 27-Jan-2010 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

Tuned.


# beca260e 25-Jan-2010 Tjark Weber <Tjark.Weber@cl.cam.ac.uk>

HolQbfLib: A new library for integrating Quantified Boolean Formulae (QBF)
solvers.

Features so far:

* Translation between (the QBF subset of) HOL and the QDIMACS format
* Checking of Q-resolution based certificates of invalidity, as generated
by the QBF solver Squolem