Difference between pages "D45 Model Checking" and "Membership in Goal"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Leuschel
 
imported>Billaude
 
Line 1: Line 1:
= Overview =
+
= Objective =
{{TODO}} An overview of the work done about model checking.
 
  
== State Space Reduction, Compression and Hashing ==
+
This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.<br>
 +
This reasoner discharges sequent whose goal denotes a membership which can be inferred from hypotheses. Here an basic example of what it discharges :<br>
 +
<math>H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash x\in U</math>
  
Driven by a case study from the space sector (a protocol modeled by SSF), where memory consumption was an issue, we have investigated ways to reduce ProB's memory consumption.
+
= Analysis =
A first step was to implement a first version of state compression, whereby we simplify stored states so that they require less memory. This was achieved without compromising speed and is now always activated.
 
Furthermore, if the preference <tt>COMPRESSION</tt> is set to true, then ProB will also detect common (sub-)expressions in states and store the common expressions only once.
 
E.g., when several states have the same same value for a given variable <tt>x</tt> then its value will only be stored just once. This is particularly useful when complicated variables only change infrequently.
 
  
Related to this aspect, the hashing of ProB states was improved on 64-bit architectures, which is also important in the context of detecting common subexpressions for sharing (common subexpressions are detected by hashing).
+
Such sequent are proved by PP and ML. But, these provers have both drawbacks :
We have also implemented a cryptographic SHA1 hashing function for Prolog terms, but it is not yet used in the production version of ProB.
+
*All the visible are added as needed hypotheses, which is most of the time not the case.
 +
*They take quite consequent time to prove it (even with the basic example given here above, the difference in time execution is noticeable).
 +
*If there are too many hypotheses, or if the expression of the <math>x</math> is too complicated, they may not prove it.
 +
This is particularly true when in the list of inclusion expressions of each side of the relation are not equal. For example : <math>H,\quad a\in S,\quad S\subset T_1\cap T_2,\quad T_1\cup T_3\subseteq  U\quad\vdash a\in U</math>
 +
<p>
 +
Such a reasoner contributes to prove more Proof Obligations automatically, faster and with fewer needed hypotheses which makes proof rule more legible and proof replay less sensitive to modifications.
  
Finally, the most useful symmetry reduction technique of ProB is the so-called "hash marker" method.
+
= Design Decision =
Here, we have also improved the computation of the hash symmetry markers, both achieving a reduction in size and runtime.
 
  
In addition, many improvements in constraint solving kernel were implemented.
+
== Tactic ==
  
== Constraint-Based Checking ==
+
This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.
 +
=== Goal ===
 +
The tactic (as the reasoner) should works only on goals such as :
 +
*<math>\cdots~\in~\cdots</math>
 +
For examples :
 +
*<math>f(x)\in g\otimes h</math>
 +
*<math>x\in A\cprod\left(B\cup C\right)</math>
 +
*<math>x\mapsto y\in A\cprod B</math>
 +
In the latter case, the reasoner won't try to prove that ''x'' belongs to ''A'' and ''y'' belongs to ''B'', but that the mapplet belong to the Cartesian product.
 +
=== Hypotheses ===
 +
Now we have to find hypotheses leading to discharge the sequent. To do so, the tactic recovers two kinds of hypotheses :
 +
#the ones related to the left member of the goal <math>\left( x\in S\right)</math> (this is the start point):
 +
#*<math>x\in \cdots</math>
 +
#*<math>\cdots\mapsto x\mapsto\cdots\in\cdots</math>
 +
#*<math>\left\{\cdots, x,\cdots\right\}=\cdots</math>
 +
#*<math>\left\{\cdots, \cdots\mapsto x\mapsto\cdots,\cdots\right\}=\cdots</math>
 +
#the ones denoting inclusion (all but the ones matching the description of the first point) :
 +
#*<math>\cdots\subset\cdots</math>
 +
#*<math>\cdots\subseteq\cdots</math>
 +
#*<math>\cdots=\cdots</math>
 +
Then, it will search a link between those hypotheses so that the sequent can be discharged.
 +
=== Find a path ===
 +
Now that we recovered all the hypotheses that could be useful for the reasoner, it remains to find a path among the hypotheses leading to discharge the sequent. Depending on the relations on each side of the inclusion, we will act differently. <math>f</math> always represent an expression (may be a domain, a range, etc.).
 +
#The following sequent is provable because <math>f\subseteq \varphi (f)</math>.
 +
#*<math>x\in f,\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g</math>
 +
#*<math>\varphi (f) = f\quad\mid\quad f\cup h \quad\mid\quad h\cup f \quad\mid\quad h\ovl f</math>
 +
#The following sequent is provable because <math>\psi (f)\subseteq f</math>.
 +
#*<math>x\in \psi (f),\quad f\subseteq g\quad\vdash\quad x\in g</math>
 +
#*<math>\psi (f) = f\quad\mid\quad f\cap h \quad\mid\quad h\cap f \quad\mid\quad f\setminus h \quad\mid\quad f\ransub A \quad\mid\quad f\ranres A \quad\mid\quad A\domsub f \quad\mid\quad A\domres f</math>
 +
#We can generalized the first two points. This is the Russian dolls system. We can easily prove a sequent with multiple inclusions by going from hypothesis to hypothesis.
 +
#*<math>x\in \psi (f),\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g</math>
 +
#For some relations, [[#positions|positions]] are needed to be known to continue to find hypotheses, but it is not always necessary.
 +
#*<math>x\mapsto y\in f,\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
 +
#*<math>x\in dom(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in A</math>
 +
#*<math>x\in ran(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in B</math>
  
Improved Constraint-based checking for deadlocks, invariants and event sequences (used in MBT).
+
By using these inclusion and rewrites, it tries to find a path among the recovered hypotheses. Every one of those should only be used once, avoiding possible infinite loop <math>\left(A\subseteq B,\quad B\subseteq A\right)</math>. Among all paths that lead to discharge the sequent, the tactic give the first it finds. Moreover, so that the reasoner does not do the same work as the tactic of writing new hypothesis, it gives all needed hypotheses and added hypotheses in the input.
  
 +
== Reasoner ==
  
== New Features ==
+
The way the reasoner must work is still in discussion.
=== Experiments with Theory Plugin ===
 
  
=== Support of finite operator===  
+
= Implementation =  
  
=== Improved detection of infinite functions, and improved support for them===
+
This section explain how the tactic has bee implemented.
  
=== Detection when infinite sets had to be approximated===
+
=== Positions ===
 +
As it was said, we may sometimes need the position. It is represented by an array of integer. Here are the possible values the array contains (atomic positions) :
 +
* '''''kdom''''' : it corresponds to the domain.
 +
**<math>\left[A\cprod B\right]_{pos\;=\;kdom} = A</math>
 +
**<math>\left[x\mapsto y\right]_{pos\;=\;kdom} = x</math>
 +
**<math>\left[g\right]_{pos\;=\;kdom} = dom(g)</math>
 +
* '''''kran''''' : it corresponds to the domain.
 +
**<math>\left[A\cprod B\right]_{pos\;=\;kran} = B</math>
 +
**<math>\left[x\mapsto y\right]_{pos\;=\;kran} = y</math>
 +
**<math>\left[g\right]_{pos\;=\;kran} = ran(g)</math>
 +
* '''''leftDProd''''' : it corresponds to the left member of a direct product.
 +
**<math>\left[f\otimes g\right]_{pos\;=\;leftDProd} = f</math>
 +
**<math>\left[A\cprod \left(B\cprod C\right)\right]_{pos\;=\;leftDProd} = A\cprod B</math>
 +
* '''''rightDProd''''' : it corresponds to the right member of a direct product
 +
**<math>\left[f\otimes g\right]_{pos\;=\;rightDProd} = g</math>
 +
**<math>\left[A\cprod\left(B\cprod C\right)\right]_{pos\;=\;rightDProd} = A\cprod C</math>
 +
* '''''leftPProd''''' : it corresponds to the left member of a parallel product
 +
**<math>\left[f\parallel g\right]_{pos\;=\;leftPProd} = f</math>
 +
**<math>\left[\left(A\cprod B\right)\cprod\left(C\cprod D\right)\right]_{pos\;=\;leftPProd} = A\cprod C</math>
 +
* '''''rightPProd''''' : it corresponds to the right member of a parallel product
 +
**<math>\left[f\parallel g\right]_{pos\;=\;rightPProd} = g</math>
 +
**<math>\left[\left(A\cprod B\right)\cprod\left(C\cprod D\right)\right]_{pos\;=\;rightPProd} = B\cprod D</math>
 +
* '''''converse''''' : it corresponds to the child of an inverse
 +
**<math>\left[f^{-1}\right]_{pos\;=\;converse}=f</math>
 +
**<math>\left[A\cprod B\right]_{pos\;=\;converse} = B\cprod A</math>
 +
For example, the following expressions at the given positions are equivalent.
 +
:<math>\left[f\otimes\left(\left(A\cprod dom(g)\right)\parallel g\right)\right]_{pos\;=\;\left[rightDProd,\;leftPProd,\;kran\right]} = \left[\left(A\cprod dom(g)\right)\parallel g\right]_{pos\;=\;\left[leftPProd,\;kran\right]} = \left[A\cprod dom(g)\right]_{pos\;=\;\left[kran\right]} = \left[dom(g)\right]_{pos\;=\;\left[~\right]} = \left[g\right]_{pos\;=\;\left[kdom\right]}</math>
  
== Experiments ==
+
Some combinations of atomic positions are equivalent. In order to simplify comparison between positions, they are normalized :
Conducted comparison with TLA+ model checker TLC
+
*<math>ran(f^{-1}) = dom(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kran\right]} = \left[f\right]_{pos\;=\;\left[kdom\right]}</math>
 +
*<math>dom(f^{-1}) = ran(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kdom\right]} = \left[f\right]_{pos\;=\;\left[kran\right]}</math>
 +
*<math>\left(f^{-1}\right)^{-1} = f\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~converse\right]} = \left[f\right]_{pos\;=\;\left[~\right]}</math>
  
= Motivations =
+
=== Goal ===
{{TODO}} To be completed.
 
The motivations for the state space compression arose from experiments in WP3 (space), and from applications of ProB outside of Deploy.
 
  
= Choices / Decisions =
+
As explained in the design decision part, goal is checked. If it matches the description here above <math>\left(x\in S\right)</math> then ''x'' is stored in an attribute. Moreover, from the set ''S'', we compute every pair ''expression'' & ''position'' equivalent to it. For example, from the set <math>dom(ran(ran(g)))</math>, the map will be computed :
{{TODO}} To be completed.
+
*<math>dom(ran(ran(g)))\;\mapsto\;[\;]</math>
 +
*<math>ran(ran(g))\;\mapsto\;[0]</math>
 +
*<math>ran(g)\;\mapsto\;[1,~0]</math>
 +
*<math>g\;\mapsto\;[1,~1,~0]</math>
 +
Only ''range'', ''domain'' and ''converse'' can be taken into account to get all the possibles goals.
  
Aggressive compression can also induce a performance penalty.
+
A pair (expression ; position) is said equal to the goal if and only if there exists a pair equivalent to the goal (GoalExp ; GoalPos) and a pair equivalent to the given pair (Exp ; Pos) such as ''Pos = GoalPos'' and ''Exp'' is contained in ''GoalExp''.
The new default mode was chosen such that there should be no performance penalty, with reduced memory usage.
 
(Indeed, the time for compression is regained by reduced time to store and retrieve the states.)
 
  
A more aggressive setting can be forced by <tt>-p COMPRESSION TRUE</tt>. This will further reduce memory consumption, but may increase runtime (although quite often it does not).
+
=== Hypotheses ===
  
= Available Documentation =
+
As explained in the design decision part, there are two kinds of hypotheses which are recovered. But when hypotheses related to the left member of the goal <math>\left(x\in S\right)</math> are stored, the position of ''x'' is also record. Then, if there is an hypothesis such as <math>\left\{\cdots\;,\;y\mapsto x\mapsto z\;,\;m\mapsto x\;,\;\cdots\right\} = A</math>, then this hypothesis is mapped to the positions <math>\left\{\left[0,~1\right],~\left[1\right]\right\}</math>.
{{TODO}} To be completed.
 
  
* [http://www.stups.uni-duesseldorf.de/ProB/index.php5/Using_the_Command-Line_Version_of_ProB Command-Line Version of ProB]
+
=== Find a path ===
* [http://www.stups.uni-duesseldorf.de/w/Special:Publication/HaLe2011 Constraint-Based Deadlock Checking of High-Level Specifications. In Proceedings ICLP'2011 (to appear), Cambridge University Press, 2011.]
 
* [http://www.stups.uni-duesseldorf.de/w/Special:Publication/HansenLeuschelTLA2012 Translating TLA+ to B and experiments with TLC]
 
  
= Status =
+
Let's considered the sequent with the following goal : <math>x\in V</math>.
{{TODO}} To be completed.
+
We start with the hypotheses which have a connection with the goal's member. Such a hypothesis gives two informations : the position <math>pos</math> and the set <math>S</math> as explained in [[#Hypotheses|hypotheses]]. Then, for each equivalent pair to these one <math>\left(S', pos'\right)</math>, we compute set containing <math>S'</math> ([[#Design Decision#Tactic#Find a path| Find a path 2.]]). For every new pair, we test if it is contained in the goal.
  
The improved hashing and light-weight state compression is available in the current release of ProB.
+
To be continued.
The SHA1 hash technique is not available in the current release.
 
The research on further compression technique is ongoing and will be continued within the project ADVANCE.
 
  
 +
= Untreated cases =
  
[[Category:D45 Deliverable]]
+
Some cases are not treated. Further enhancement may be provided for some.
 +
*<math>x\in A\cup B,\quad A\cup B\cup C\subseteq D\quad\vdash\quad x\in D</math>
 +
*<math>x\in f,\quad f\in A\;op\;B\quad\vdash\quad x\in A\cprod B</math>
 +
*<math>f\ovl \left\{x\mapsto y\right\}\subseteq A\cprod B\quad\vdash\quad x\in A</math>
 +
*<math>x\in f\otimes g,\quad f\subseteq A\cprod B,\quad g\subseteq C\cprod D\quad\vdash\quad x\in (A\cprod C)\cprod(B\cprod D)</math>
 +
*<math>x\in f\otimes g,\quad f\subseteq h\quad\vdash\quad x\in h\otimes g</math>
 +
*<math>x\in \left\{a,~b,~c\right\},\quad\left\{a,~b,~c,~d,~e,~f\right\}\subseteq D\quad\vdash\quad x\in D</math>
 +
*<math>x\in A\cprod B,\quad A\subseteq C\quad\vdash\quad x\in C\cprod B</math>
 +
*<math>x\in dom(f)\cap A\quad\vdash\quad x\in dom(A\domres f)</math>
 +
*<math>x\in ran(f)\cap A\quad\vdash\quad x\in ran(f\ranres A)</math>
 +
*<math>x\in \quad\vdash\quad</math>
 +
*<math>\quad\vdash\quad</math>
 +
*<math>\quad\vdash\quad</math>
 +
*<math>\quad\vdash\quad</math>
 +
*:<math>\bigl(</math> where <math>op_1</math> and <math>op_2</math> are ones of :<math>\quad\rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij\bigr)</math>
 +
 
 +
[[Category:Design proposal]]

Revision as of 13:28, 9 August 2011

Objective

This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.
This reasoner discharges sequent whose goal denotes a membership which can be inferred from hypotheses. Here an basic example of what it discharges :
H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash x\in U

Analysis

Such sequent are proved by PP and ML. But, these provers have both drawbacks :

  • All the visible are added as needed hypotheses, which is most of the time not the case.
  • They take quite consequent time to prove it (even with the basic example given here above, the difference in time execution is noticeable).
  • If there are too many hypotheses, or if the expression of the x is too complicated, they may not prove it.

This is particularly true when in the list of inclusion expressions of each side of the relation are not equal. For example : H,\quad a\in S,\quad S\subset T_1\cap T_2,\quad T_1\cup T_3\subseteq  U\quad\vdash a\in U

Such a reasoner contributes to prove more Proof Obligations automatically, faster and with fewer needed hypotheses which makes proof rule more legible and proof replay less sensitive to modifications.

Design Decision

Tactic

This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.

Goal

The tactic (as the reasoner) should works only on goals such as :

  • \cdots~\in~\cdots

For examples :

  • f(x)\in g\otimes h
  • x\in A\cprod\left(B\cup C\right)
  • x\mapsto y\in A\cprod B

In the latter case, the reasoner won't try to prove that x belongs to A and y belongs to B, but that the mapplet belong to the Cartesian product.

Hypotheses

Now we have to find hypotheses leading to discharge the sequent. To do so, the tactic recovers two kinds of hypotheses :

  1. the ones related to the left member of the goal \left( x\in S\right) (this is the start point):
    • x\in \cdots
    • \cdots\mapsto x\mapsto\cdots\in\cdots
    • \left\{\cdots, x,\cdots\right\}=\cdots
    • \left\{\cdots, \cdots\mapsto x\mapsto\cdots,\cdots\right\}=\cdots
  2. the ones denoting inclusion (all but the ones matching the description of the first point) :
    • \cdots\subset\cdots
    • \cdots\subseteq\cdots
    • \cdots=\cdots

Then, it will search a link between those hypotheses so that the sequent can be discharged.

Find a path

Now that we recovered all the hypotheses that could be useful for the reasoner, it remains to find a path among the hypotheses leading to discharge the sequent. Depending on the relations on each side of the inclusion, we will act differently. f always represent an expression (may be a domain, a range, etc.).

  1. The following sequent is provable because f\subseteq \varphi (f).
    • x\in f,\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g
    • \varphi (f) = f\quad\mid\quad f\cup h \quad\mid\quad h\cup f \quad\mid\quad h\ovl f
  2. The following sequent is provable because \psi (f)\subseteq f.
    • x\in \psi (f),\quad f\subseteq g\quad\vdash\quad x\in g
    • \psi (f) = f\quad\mid\quad f\cap h \quad\mid\quad h\cap f \quad\mid\quad f\setminus h \quad\mid\quad f\ransub A \quad\mid\quad f\ranres A \quad\mid\quad A\domsub f \quad\mid\quad A\domres f
  3. We can generalized the first two points. This is the Russian dolls system. We can easily prove a sequent with multiple inclusions by going from hypothesis to hypothesis.
    • x\in \psi (f),\quad \varphi (f)\subseteq g\quad\vdash\quad x\in g
  4. For some relations, positions are needed to be known to continue to find hypotheses, but it is not always necessary.
    • x\mapsto y\in f,\quad f\subseteq A\cprod B\quad\vdash\quad x\in A
    • x\in dom(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in A
    • x\in ran(f),\quad f\subseteq A\cprod B\quad\vdash\quad x\in B

By using these inclusion and rewrites, it tries to find a path among the recovered hypotheses. Every one of those should only be used once, avoiding possible infinite loop \left(A\subseteq B,\quad B\subseteq A\right). Among all paths that lead to discharge the sequent, the tactic give the first it finds. Moreover, so that the reasoner does not do the same work as the tactic of writing new hypothesis, it gives all needed hypotheses and added hypotheses in the input.

Reasoner

The way the reasoner must work is still in discussion.

Implementation

This section explain how the tactic has bee implemented.

Positions

As it was said, we may sometimes need the position. It is represented by an array of integer. Here are the possible values the array contains (atomic positions) :

  • kdom : it corresponds to the domain.
    • \left[A\cprod B\right]_{pos\;=\;kdom} = A
    • \left[x\mapsto y\right]_{pos\;=\;kdom} = x
    • \left[g\right]_{pos\;=\;kdom} = dom(g)
  • kran : it corresponds to the domain.
    • \left[A\cprod B\right]_{pos\;=\;kran} = B
    • \left[x\mapsto y\right]_{pos\;=\;kran} = y
    • \left[g\right]_{pos\;=\;kran} = ran(g)
  • leftDProd : it corresponds to the left member of a direct product.
    • \left[f\otimes g\right]_{pos\;=\;leftDProd} = f
    • \left[A\cprod \left(B\cprod C\right)\right]_{pos\;=\;leftDProd} = A\cprod B
  • rightDProd : it corresponds to the right member of a direct product
    • \left[f\otimes g\right]_{pos\;=\;rightDProd} = g
    • \left[A\cprod\left(B\cprod C\right)\right]_{pos\;=\;rightDProd} = A\cprod C
  • leftPProd : it corresponds to the left member of a parallel product
    • \left[f\parallel g\right]_{pos\;=\;leftPProd} = f
    • \left[\left(A\cprod B\right)\cprod\left(C\cprod D\right)\right]_{pos\;=\;leftPProd} = A\cprod C
  • rightPProd : it corresponds to the right member of a parallel product
    • \left[f\parallel g\right]_{pos\;=\;rightPProd} = g
    • \left[\left(A\cprod B\right)\cprod\left(C\cprod D\right)\right]_{pos\;=\;rightPProd} = B\cprod D
  • converse : it corresponds to the child of an inverse
    • \left[f^{-1}\right]_{pos\;=\;converse}=f
    • \left[A\cprod B\right]_{pos\;=\;converse} = B\cprod A

For example, the following expressions at the given positions are equivalent.

\left[f\otimes\left(\left(A\cprod dom(g)\right)\parallel g\right)\right]_{pos\;=\;\left[rightDProd,\;leftPProd,\;kran\right]} = \left[\left(A\cprod dom(g)\right)\parallel g\right]_{pos\;=\;\left[leftPProd,\;kran\right]} = \left[A\cprod dom(g)\right]_{pos\;=\;\left[kran\right]} = \left[dom(g)\right]_{pos\;=\;\left[~\right]} = \left[g\right]_{pos\;=\;\left[kdom\right]}

Some combinations of atomic positions are equivalent. In order to simplify comparison between positions, they are normalized :

  • ran(f^{-1}) = dom(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kran\right]} = \left[f\right]_{pos\;=\;\left[kdom\right]}
  • dom(f^{-1}) = ran(f)\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~kdom\right]} = \left[f\right]_{pos\;=\;\left[kran\right]}
  • \left(f^{-1}\right)^{-1} = f\quad\limp\quad \left[f\right]_{pos \;=\; \left[converse,~converse\right]} = \left[f\right]_{pos\;=\;\left[~\right]}

Goal

As explained in the design decision part, goal is checked. If it matches the description here above \left(x\in S\right) then x is stored in an attribute. Moreover, from the set S, we compute every pair expression & position equivalent to it. For example, from the set dom(ran(ran(g))), the map will be computed :

  • dom(ran(ran(g)))\;\mapsto\;[\;]
  • ran(ran(g))\;\mapsto\;[0]
  • ran(g)\;\mapsto\;[1,~0]
  • g\;\mapsto\;[1,~1,~0]

Only range, domain and converse can be taken into account to get all the possibles goals.

A pair (expression ; position) is said equal to the goal if and only if there exists a pair equivalent to the goal (GoalExp ; GoalPos) and a pair equivalent to the given pair (Exp ; Pos) such as Pos = GoalPos and Exp is contained in GoalExp.

Hypotheses

As explained in the design decision part, there are two kinds of hypotheses which are recovered. But when hypotheses related to the left member of the goal \left(x\in S\right) are stored, the position of x is also record. Then, if there is an hypothesis such as \left\{\cdots\;,\;y\mapsto x\mapsto z\;,\;m\mapsto x\;,\;\cdots\right\} = A, then this hypothesis is mapped to the positions \left\{\left[0,~1\right],~\left[1\right]\right\}.

Find a path

Let's considered the sequent with the following goal : x\in V. We start with the hypotheses which have a connection with the goal's member. Such a hypothesis gives two informations : the position pos and the set S as explained in hypotheses. Then, for each equivalent pair to these one \left(S', pos'\right), we compute set containing S' ( Find a path 2.). For every new pair, we test if it is contained in the goal.

To be continued.

Untreated cases

Some cases are not treated. Further enhancement may be provided for some.

  • x\in A\cup B,\quad A\cup B\cup C\subseteq D\quad\vdash\quad x\in D
  • x\in f,\quad f\in A\;op\;B\quad\vdash\quad x\in A\cprod B
  • f\ovl \left\{x\mapsto y\right\}\subseteq A\cprod B\quad\vdash\quad x\in A
  • x\in f\otimes g,\quad f\subseteq A\cprod B,\quad g\subseteq C\cprod D\quad\vdash\quad x\in (A\cprod C)\cprod(B\cprod D)
  • x\in f\otimes g,\quad f\subseteq h\quad\vdash\quad x\in h\otimes g
  • x\in \left\{a,~b,~c\right\},\quad\left\{a,~b,~c,~d,~e,~f\right\}\subseteq D\quad\vdash\quad x\in D
  • x\in A\cprod B,\quad A\subseteq C\quad\vdash\quad x\in C\cprod B
  • x\in dom(f)\cap A\quad\vdash\quad x\in dom(A\domres f)
  • x\in ran(f)\cap A\quad\vdash\quad x\in ran(f\ranres A)
  • x\in \quad\vdash\quad
  • \quad\vdash\quad
  • \quad\vdash\quad
  • \quad\vdash\quad
    \bigl( where op_1 and op_2 are ones of :\quad\rel, \trel, \srel, \strel, \pfun, \tfun, \pinj, \tinj, \psur, \tsur, \tbij\bigr)