Friday, 27 June 2014

First Order Lower Units

So today I finally got a first version of first order lower units working and compressing a proof (note that we have one less resolution in the second case):

1: { ⊢ (p X), (q X B)} : Axiom()[]
2: {(p A) ⊢ } : Axiom()[]
3: { ⊢ (q A B)} : UnifyingResolution(1, 2)[]
4: {(q X Y) ⊢ (p X)} : Axiom()[]
5: { ⊢ (p X)} : UnifyingResolution(3, 4)[]
6: { ⊢ } : UnifyingResolution(5, 2)[]

1: { ⊢ (p X), (q X B)} : Axiom()[]
2: {(q X Y) ⊢ (p X)} : Axiom()[]
3: { ⊢ (p X), (p X)} : UnifyingResolutionMRR(1, 2)[]
4: { ⊢ (p X)} : Contraction(3)[]
5: {(p A) ⊢ } : Axiom()[]
6: { ⊢ } : UnifyingResolution(4, 5)[]

It's obviously not much, but I'm testing it on larger and larger examples and the code seems to be holding up well. Further testing and possibly some optimization will take place tomorrow.

Wednesday, 25 June 2014

Ambiguous Resolution Concern

Today I was working on fixing the bug mentioned in the last post, and getting FO lower units to work. The latter is making progress, and I don't have any real concerns about it yet, because although its not yet working, I understand why it isn't. However, with respect to the first issue, I would like some clarification. At some point during one of the proofs that is serving as an example, we attempt to perform resolution on

 ⊢ (eq (f U) 0), (eq (f U) 1), (eq (f U) 2), (eq (f U) 3), (eq (f U) 4)
(eq (f (s U)) 0), (eq (f U) 0) ⊢ 

and we would get the following list of possible unifiable pairs:

((eq (f W) 0),(eq (f (s U)) 0)),
 ((eq (f W) 0),(eq (f U) 0))

(Does either of these look wrong? If so, the comments below might not be applicable)

And in the old method, which checked if the length of the list of pairs was > 0, would just take the first set, and that worked (though it's true that it might not have in general). But when we check if the list length == 1, this fails the test; and an exception is thrown; the parser fails to parse the proof. This is clearly undesirable, since the premises can be resolved against each other.

So to fix this, I think we can do one of two things: (A) what we were doing before -- see if there's a list, and just pick the head of the list. I'm not convinced this will always work. Or (B) SPASS proofs actually indicate which formula in each premise is being used for resolution, and we are parsing that information. So maybe instead of just picking the first one, we use this information, and continue as if there's only one unifiable pair (the one we were told to look for).

But then either of these cases would effectively remove the check for length > 1, and that 'resolution is ambiguous' error would never be thrown. So is that a concern?

(B) seems like the better option to me. Do you have any comments on this?

Thursday, 19 June 2014

Extending LowerUnits to First Order

Yesterday, I coded the first version of LowerUnits for first order logic proofs. It's based on the conjecture that was supplied in my notes, minus the requirement that the unit being lowered is the most general form. I was also going to write up a proof that the conjectured conditions for lowering units would always work, but I discovered an error in it and I haven't yet corrected it. Today I'll continue to develop the LU algorithm, and get this proof corrected & typed up.

I also cleaned up a few things in UnifyingResolution - so Bruno, if you want to look at how we could refactor that class so that I don't need to pass in an extra argument in the constructor, now you can.

Monday, 16 June 2014

Conditions for Lowering Units

So for the past week or so, I've been studying the theoretical concerns of generalizing the LowerUnits algorithm to first order logic proofs. As a result of that work, I've come up with what I think a good first conjecture might be for applicability: we can lower a unit as long as the clauses that are resolved with the unit are also pair-wise unifiable (so that when we lower the unit, the faster contraction rule that usually overrides a resolution rule can actually proceed, as many times as is necessary), and further, that the unit formula is the most general form (e.g., the unit is P(X,Y), and the clause resolving with it might have a variant P(a,Y), but not the other way around -- though in some cases, this does work; this restriction allows a greater number of proofs to succeed by preventing cases where we might get a resolvent containing a too specific variant of the unit that isn't covered by the already specific unit clause we're trying to lower -- see the first real example in section 3 of [1]).

I am concerned that this criteria is somewhat loose; that I could possibly find a better condition for when we can lower units, but finding counter-examples to such things is difficult. I'm also less concerned that it's wrong: but I don't think so--it seems to work always, though I haven't proved it. But if either is the case, I'm not sure I'm asking the right questions.

I have other concerns as well; aside from the concern of unifiability of unit formulas that we want to lower, is it possible that the position of where the unit clause first appears in the proof matters? I've spent considerable time looking at questions for this, but I don't think that's the case either; but again, no proof, only some examples where it seems okay (and many more not documented).

A last concern is that of how far to 'lower' the unit; I think this is solvable by just generalizing the algorithm though--once we know we can apply it, following it like in the propositional case will indicate when to re-insert the unit.


[1] https://github.com/jgorzny/Skeptik/blob/develop/documents/proofs-test.pdf

(As a final note -- for the proofs in the pictures proofs-6-7, proofs-8-9, the letters should be interpreted as first order predicates over unifiable variables, e.g. P(X); which were the easiest to consider at first. Since these proofs probably aren't too useful (but I may want to refer to them), they can probably even be ignored by now.)

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

Friday, 6 June 2014

Code Cleaning

Yesterday I had a Skype meeting with Bruno who suggested a number of ways to improve my code for Contraction and clean up some other things in my code, so today was largely spent refactoring code and implementing the changes he suggested (like not using my from scratch code for contraction, but rather using the MGU algorithm already implemented).

Contraction Rule

This week (Mon-Wed), I was working primarily on developing the Contraction rule class for Skeptik. The proof examples that were provided in SPASS often implicitly used this rule, which was causing a mismatch between computed resolvents and expected resolvents for my parser. This appears to be implemented, as I have created a few small test cases and the 'Con' lines in the example proofs match what I have been producing (up to formula ordering).