History log of /seL4-l4v-10.1.1/HOL4/src/integer/OmegaShell.sml
Revision Date Author Comments
# 67274ad0 07-Oct-2003 Joe Hurd <joe@gilith.com>

Added a few newlines at end of files to suppress warnings from my
Mosml -> MLton preprocessor.


# e234dcdc 23-Mar-2003 Michael Norrish <Michael.Norrish@nicta.com.au>

Got rid of QConv, and made all conversions do the "raise exception to
indicate reflexivity" thing. (Also fixed bug in new implementation
of ABS_CONV that attempted renaming on failure of conv, and not just
failure of ABS.)

Next step will be to rework the simplifier's implementation so that
it also uses Conv.UNCHANGED, rather than in its own internal version
of the same. This will let the simplifier play efficiently with
others.

May also assess making ABS_CONV not do renaming, and give the rewriter
its own special traverser. This might make some things more efficient.


# 5b7b7cf1 06-Mar-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

Omega now passes all of its tests, and I claim it's probably now a reasonable
approximation of a complete procedure for doing Preburger arithmetic.
Aggressive preprocessing attempts to minimise DNF blowup, but the fact
that EXISTS_OR_CONV can still consume over 10% of the procedure's running
time basically sucks.


# f32f2816 04-Mar-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

Omega now works on all of the test case, bar KXSDIV1, on which it
blows up. Some investigation suggests that this is "just" an efficiency
issue and not one of code correctness. With luck, I'll check in some
efficiency changes tomorrow, and then I'll be done.


# 00262dd0 01-Mar-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

OMEGA_CONV is now "almost complete". There are just bugs to be ironed out.
Changes are too many to document extensively. Some though:
* OmegaMath has got a lot bigger, with OmegaEq being merged into it and
also gaining some divisibility normalisation code.
* couple of new test cases
* decided against prenexing mixed quantifier problems.


# fffdfcea 18-Feb-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

Moved very useful leaf_normalise function into the OmegaMath "library".


# 42463560 18-Feb-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

Correctly implementing the second optimisation from Friday carves 50s
off the running time for the evil SUNRISE1 test case. (Every test
suite should have such horrors.)


# d85ab97f 15-Feb-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

Implemented two more optimisations for "simple Omega". One made
the noxious SUNRISE example go twice as fast. (It's still almost three
times faster if you use Cooper though.)

The first optimisation made the contextual simplification smarter, while the
second took the opportunity to do single-point elimination before converting
to DNF where possible.


# 5769e500 08-Feb-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

Improvements to the decision procedures. Omega is now somewhat smarter
about doing useful work before throwing itself into DNF-ication.
I think there are probably one or two more optimisations to be done
along these lines.


# 86209dd7 23-Jan-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

Revisions to the code that DNF-ifies the problem set, including a phase
of "congruential simplification". On those problems that Omega can get
it seems quicker than Cooper in almost all case. One very notable
exception suggests that there is still work to be done though.


# 4a27629a 21-Jan-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

Tests revealed that it was much better to let the Canon functions remove
implications and bi-implications themselves rather than doing this first.
Also publish the useful dealwith_nats function from IntDP_Munge.


# fe1bec3d 17-Jan-2002 Michael Norrish <Michael.Norrish@nicta.com.au>

Progress with Omega. Also refactored code for handling natural numbers
and generalising over non-presburger sub-terms so that both Omega and
Cooper can use it.