LINQ-Specification Template Extension for Add-on

Question

There are many implementations based on the LINQ composite specification template. I have not seen using Subsumption.

Are there any examples that have been documented (blogs, etc.) or published as open source? I have an idea and proof of concept for how this might work if ExpressionVisitor translates each specification into canonical logical form (CNF / DNF), but I am worried that it is too complicated. Is there a better way?

Answer 1

I am concerned that this is too complicated. Is there a better way?

Short answer: "No, does not exist" ¹

Long answer: “Too complicated” captures the essence of the problem: it is NP-hard. Here is a short, unofficial proof that the feasibility problem is :

• Suppose you have two Boolean formulas, A and B
• You need to check if A B ¬A | B or equivalently ¬A | B ¬A | B for all variable assignments that A and B depend on. In other words, you need proof that F = ¬A | B F = ¬A | B is a tautology.
• Suppose a tautology test can be completed in polynomial time
• Consider ¬F inverse to F F is feasible if and only if ¬F not a tautology
• Use a hypothetical polynomial algorithm to check ¬F for being a tautology
• The answer to “ F doable” is the opposite of “ ¬F tautology”
• Consequently, the existence of a polynomial tautology checker will mean that the feasibility problem is in P and that P=NP .

Of course, the fact that the NP-hard problem does not mean that there will be no solutions for practical cases: in fact, your approach to canonical conversion can lead to OK results in many real-life situations. However, the absence of the well-known “good” algorithm often hinders the active development of practical solutions ² .

<h / "> ¹ With the obligatory" exception P=NP "disclaimer.

² If there is no “reasonably good” solution, which may well be in the case of your problem, if you allow “false negatives”.