Tuesday, 10 June 2014

Generalizing Algorithms

Last Friday, as well as a little bit over the weekend, and today (Monday), I was working mostly on making sure that I understand the LowerUnits and RecyclePivots algorithms, in order to start generalizing them. The first step was looking at Example 2 in [1], which looks like it can immediately be made 'first order'; replace each literal with a predicate say, P(X), and proceed as before (at least manually); see [2] (which is also where I will write things up about these algorithms as I develop them). And I think that works out, and I think I understand how the algorithms work in that case at least.

At this point, I should ask for clarification/confirmation: a 'unit' clause would be one with exactly one formula? (That's how I was proceeding)

As a more general starting point, the document prepared by Postan was a good lead; it outlines local redundancy in first order proofs, and looks for units that can be unified in order to carry out the algorithm on; this was what I would implicitly do when solving the above example. However, this only works when L_1 = L_2\sigma for some sigma; namely if the unifier is applied to only one side; not both (which the next example in his document demonstrates).

So next question: is this what I should be looking for? If so, does it need to be proved that this will always reduce (or at least not expand) the proof? And can I start implementing using this technique if so?

And in order to convince myself that this is correct, I was attempting to compress (not necessarily using any algorithmic technique) the examples that are provided by hand--but they are large and this is long/hard/complicated, so this has been unsuccessful so far.

[1] Compression of Propositional Resolution Proofs by Lowering Subproofs
[2] https://github.com/jgorzny/Skeptik/blob/develop/documents/proofs-test.pdf

No comments:

Post a Comment