Package de.upb.swt.epctools.simulator.explicit

This package implements an algorithm for explicitly calculating the semantics of EPCs and some analysis algorithms.

See:
Description

Class Summary

AndJoinConnector_DS	Implements an AND-join connector of the EPC data structure.
AndSplitConnector_DS	Implements an AND-split connector of the EPC data structure.
Arc_DS	Implements an arc of the EPC data structure.
EPC_DS	Implements the data structure for an EPC model.
EventFunction_DS	Implements an Event or Function node of an EPC model.
JoinConnector_DS	Implements a join connector of the EPC data structure.
Node_DS	Implements a node of the EPC data structure.
OrJoinConnector_DS	Implements an OR-join connector of the EPC data structure.
OrSplitConnector_DS	Implements an OR-split connector of the EPC data structure.
SplitConnector_DS	Implements a split connector of the EPC data structure.
State	Implements the state of a transition system of an EPC.
Transition	Implements a transition of the transition system.
TransitionSystem	Implements a data structure and algorithms for calculating and accessing the semantics of an EPC.
XorJoinConnector_DS	Implements an XOR-join connector of the EPC data structure.
XorSplitConnector_DS	Implements an XOR-split connector of the EPC data structure.

Exception Summary

EPCSyntaxError

Exception raised when the internal data structure of the EPC is built.

Package de.upb.swt.epctools.simulator.explicit Description

This package implements an algorithm for explicitly calculating the semantics of EPCs and some analysis algorithms. The transition system is explicitly constructed and the non-local conditions are considered by nesting the forward construction of the transition system with a backward marking algorithms for every non-local connector. The analysis algorithms check the soundness of the EPC, i.e. whether from all reachable states an end state is reachable, where an end state is a state that has process folders only on the input arcs of end events.

If no conflict between the additional conditions of a non-local connector with a already constructed transition are encountered during the construction. The transition system refelcts the ideal semantics of the EPC (restricted to its reachable states). If such a conflict is encountered, the transition system does not properly reflect the semantics of the the EPC (it is close to the pessimistic semantics, but it is not necessarily identical to it).

Note that there are examples of EPCs that have an ideal semantics, for which this algorithms is not able to propely calculate the semantics; it could encounter a conflict mentioned above and, therefore, marked unclean. If the constructed transition system, however, is clean, the it reflects the ideal semantics of the EPC.

The algorithm is implementated in such a way that for a constructed transition system for some EPC, we can easily add a new state and start the construction algorithm; this will save some time because the old parts will not be constructed again. If the transition system was unclean, it is better to start the calculation from scratch because a unclean transition system will never become clean again (even when the new state alon would result in a clean transition system).

Note that this is the first prototype of the algorithm! It is neither properly tested, nor is it the most elgant or most efficient implementation. There are many ideas on how to improve the implemantation. Once this implementation is tested and some of the improvements have been made, it will be included into EPCTools.

Here are some optimizations that could be implemented:

• Currently, the complete transition system is constructed in order to calculate which non-local connectors are enabled in the current state. Actually, this is not always necessary. In some states we know that no folders can be added to the input arcs of a non-local connector anymore (for purely syntactic reasons). We could stop the forward construction in such states.

Release notes

• July 30, 2005: Initial version not yet fully tested and not cleaned up.
• August 2, 2005 : Inspected and cleaned up code; completed comments and java docs. Made some test, but not yet fully tested.
• October 2, 2005: Added an algorithm for calculating levels, which define the order in which the non-local connectors are considered. In many examples, this will make sure that the resulting transition system is clean.
• October 20, 2005: Now, the algorithm checks whether there were contact situations during the construction of the transition system. This is important for a reduction of the EPC called chain elimination.
• October 20, 2005: Implemented a method for aborting the calculation of the transition system (and for resuming it again).
• October 28, 2005: Implemented termination of the calculation if there is not enough memory left; the calculation method will throw a Runtime Exception.
• November 28, 2005: Implemented procedures for calculating the soundness and weak soundness of the EPC. Corrected a flaw in the calculation of the transition system.

Version:

0.1.1

Author:

Ekkart Kindler