Difference between pages "D32 General Platform Maintenance" and "Membership in Goal"

From Event-B
(Difference between pages)
Jump to navigationJump to search
imported>Pascal
 
imported>Billaude
 
Line 1: Line 1:
= Overview =
+
= Objective =
The main goal of the platform corrective and evolutive maintenance is to fix the listed known bugs, and implement some new requested features. As in the previous years of Deploy, these bugs and features are reported either by mail or through dedicated SourceForge trackers.
 
  
The terse list below gives an overwiew of the noteworthy features added in the main platform during the past year:
+
This page describes the design of the reasoner MembershipGoal and its associated tactic MembershipGoalTac.<br>
* Proof replay on undischarged POs (releases 1.3 and upper)
+
This reasoner discharges sequent whose goal denotes a membership which can be inferred from hypotheses. Here an basic example of what it discharges :<br>
: It often happens, while modifying a model, that a set of previously manually discharged POs are slightly changed and need to be discharged again. However, replaying the proof for those POs could most of the time be enough to discharge it. Hence, a command was added to manually try replaying the proofs for a set of undischarged POs. This request was expressed by [https://sourceforge.net/tracker/?func=detail&aid=2949606&group_id=108850&atid=651672 end users]. See [http://wiki.event-b.org/index.php/Proof_Obligation_Commands].
+
<math>H,\quad x\in S,\quad S\subset T,\quad T\subseteq U \quad\vdash x\in U</math>
* Rule Details View (releases 2.0 and upper)
 
: When doing an interactive proof, one is guided by the proof tree appearing on the proof tree view. However, it is sometimes needed to get more informations about the rules being involved in a proof, such as instantiation details, hidden hypotheses, etc. The [http://wiki.event-b.org/index.php/Rodin_Proving_Perspective#Rule_Details_View Rule Details View] displaying such details has been added.
 
* Refactoring plug-in (releases 1.2 and upper)
 
: ---
 
* Documentation
 
: Plug-in developers expressed their need to get a detailed documentation about Rodin extension ability. A dedicated [http://wiki.event-b.org/index.php/Plug-in_Tutorial tutorial][http://wiki.event-b.org/index.php/D23_General_Platform_Maintenance#Available_Documentation] has been written accordingly, and was the support of a training session given at the [http://www.event-b.org/rodin10.html Rodin User and Developer Workshop] in Düsseldorf this year.
 
  
See the [http://wiki.event-b.org/index.php/D23_General_Platform_Maintenance#Available_Documentation Release Notes] and the [http://wiki.event-b.org/index.php/D23_General_Platform_Maintenance#Available_Documentation SourceForge] databases (bugs and feature requests) for details about the previous and upcoming releases of the Rodin platform.
+
= Analysis =
  
= Motivations =
+
Such sequent are proved by PP and ML. But, these provers have both drawbacks :
The evolutive maintenance (resp. corrective maintenance) has its origin in the Deploy project's description of work, and the various requests (resp. bug reports) listed by WP1-4 partners, developers and users. Since the Deploy project's birth, various streams can be used to express feature requests or track an encountered bug :
+
*All the visible are added as needed hypotheses, which is most of the time not the case.
: - [http://wiki.event-b.org/index.php/D23_General_Platform_Maintenance#Available_Documentation dedicated trackers],
+
*They take quite consequent time to prove it (even with the basic example given here above, the difference in time execution is noticeable).
: - DEPLOY mailing lists.
+
*If there are too many hypotheses, or if the expression of the <math>x</math> is too complicated, they may not prove it.
Maintenance tasks to perform are collected from the aforementioned streams and scheduled during WP9 meetings. These tasks are processed in the same way as the task planned in the description of work.
+
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.
  
The following table describes the main tasks performed or scheduled tasks motivating the evolutive maintenance :
+
= Design Decision =
  
{{SimpleHeader}}
+
== Tactic ==
|-
 
! scope=col | Origin || Maintenance Task || Done in 2010 || Scheduled in 2011
 
|-
 
| WP1-4 partners|| Updating fields of records || x ||
 
|-
 
| WP1-4 partners|| Team work || x ||
 
|-
 
| WP1-4 partners|| Increase platform performances ||  || x
 
|-
 
| WP1-4 partners|| Search in goal window ||  || x
 
|-
 
| WP1-4 partners|| Preferences for the automatic tactics ||  || x
 
|-
 
| Plug-in developers|| API to extend the Pretty Printer view || x ||
 
|-
 
| Plug-in developers|| View the error log || x ||
 
|-
 
| End Users|| Adding a replay proof command in the Event-B explorer || x ||
 
|-
 
| End Users|| Having auto-completion in proof control || x ||
 
|- 
 
| End Users|| Displaying instantiated hypotheses || x ||
 
|- 
 
| End Users || Displaying the inherited elements || || x
 
|}
 
  
= Choices / Decisions =
+
This part explains how the tactic (MembershipGoalTac) associated to the reasoner MembershipGoal is working.
* Task priority
+
=== Goal ===
: Listed tasks are being given a priority during WP9 bi-weekly meetings, and then assigned to partners in charge of their processing. It has been decided to give a higher priority to WP1-4 partner's requests.
+
The tactic (as the reasoner) should works only on goals such as :
* 64-bit release of Rodin for Mac platforms
+
*<math>\cdots~\in~\cdots</math>
: A major UI bug, due to some incompatibilities between Eclipse 3.5 and Java 1.6 on Mac platforms motivated the migration to the Eclipse 3.6 as basis for the Rodin 2.0 platform. In the meantime, as the 32-bit Java Virtual Machine is no longer supported on Mac platforms, Rodin migrated to Java 1.6, so that the release 2.0 of Rodin became a 64-bit Mac platform only.
+
For examples :
: The Rodin platforms family is then composed of three executables : 32-bit platforms for Linux and Windows environments and a 64-bit platform for Mac computers.
+
*<math>f(x)\in g\otimes h</math>
* Rodin sources
+
*<math>x\in A\cprod\left(B\cup C\right)</math>
: The sources of Rodin releases are now packed with the platform. It has been decided to ship the sources in every platform release. It is, for developers, a convenient alternative to the available sources on SourceForge (See [http://wiki.event-b.org/index.php/Using_Rodin_as_Target_Platform]).
+
*<math>x\mapsto y\in A\cprod B</math>
* Release notes
+
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.
: The release notes contain information about the released plug-ins and centralise the requirements or existing issues which could not be stated at the main platform release date. Thus, since Rodin 2.0 release, it has been chosen to link the contents of the release notes text file included in Rodin releases, with the contents of the dedicated Wiki page.
+
=== 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>
  
= Available Documentation =
+
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.
As in the previous D23 delivrable, the following pages give useful information about the Rodin platform releases:
 
* Release notes.
 
: See [http://wiki.event-b.org/index.php/Rodin_Platform_Releases Rodin Platform Releases].
 
* Bugs.
 
: See [http://sourceforge.net/tracker/?atid=651669&group_id=108850].
 
* Feature requests.
 
: See [http://sourceforge.net/tracker/?group_id=108850&atid=651672].
 
  
The user manual, user tutorial and other developer documentation on the [http://wiki.event-b.org wiki] are continuously, and collaboratively updated and enhanced. A major update (see [http://wiki.event-b.org/index.php?title=D32_General_Platform_Maintenance#Overview]) to the developer documentation about Rodin extension ability has been done.
+
== Reasoner ==
  
= Planning =
+
The way the reasoner must work is still in discussion.
During the coming year, special efforts will be made on the following topics, which where pointed out at the last plenary meeting by the WP1-WP4 and encompass industrial end user requests:
 
* Platform stability
 
: Currently, users struggle through performance flows in the Rodin platform while editing or proving a model. Solving these issues represents a real challenge for the coming year and will be mandatory for the industrial adoption of Rodin and Event-B.
 
* Prover integrity
 
: Reaching a state where POs are hundred percent automatically proved is the wager that Rodin developers aim. Getting close to this ideal will increase the satisfaction of industrial users and decrease costs. Enhancing prover facilities are as well, one significant help given to the person in charge of the proving. Enhancing prover is then a continuous task that will be performed until the Deploy project's end. However, such automatic or manual pieces of program are main points of integrity concerns. Ensuring their correctness and getting more confidence into them, will thus be a task conducted during the coming year.
 
* Plug-in incompatibilities
 
: The problem occurs when several plug-ins are installed and conflicts exist between them. The cumbersome behaviour often spawned by such incompatibilities leads to user's disappointment, or even to the impossility to use the platform. Particular efforts will be lead to identify the sources of incompatibilities amongs plug-in and coordinate the assignment and processing of the necessary corrective maintenance tasks.
 
  
[[Category:D32 Deliverable]]
+
= 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.
 +
**<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>
 +
 
 +
Some combinations of atomic positions are equivalent. In order to simplify comparison between positions, they are normalized :
 +
*<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>
 +
 
 +
=== Goal ===
 +
 
 +
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 :
 +
*<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.
 +
 
 +
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 <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>.
 +
 
 +
=== Find a path ===
 +
 
 +
Let's considered the sequent with the following goal : <math>x\in V</math>.
 +
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.
 +
 
 +
To be continued.
 +
 
 +
= Untreated cases =
 +
 
 +
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)