Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 5

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote On Determining the AND-OR Hierarchy in Workflow Nets
EN
This paper presents a notion of reduction where a WF net is transformed into a smaller net by iteratively contracting certain well-formed subnets into single nodes until no more of such contractions are possible. This reduction can reveal the hierarchical structure of a WF net, and since it preserves certain semantic properties such as soundness, can help with analysing and understanding why a WF net is sound or not. The reduction can also be used to verify if a WF net is an AND-OR net. This class of WF nets was introduced in earlier work, and arguably describes nets that follow good hierarchical design principles. It is shown that the reduction is confluent up to isomorphism, which means that despite the inherent non-determinism that comes from the choice of subnets that are contracted, the final result of the reduction is always the same up to the choice of the identity of the nodes. Based on this result, a polynomial-time algorithm is presented that computes this unique result of the reduction. Finally, it is shown how this algorithm can be used to verify if a WF net is an AND-OR net.
2
Content available remote A Formal and Unified Description of XML Manipulation Languages
EN
We discuss three well-known languages for querying and manipulatingXML documents: XQuery, XPath and XSLT. They are considered to be the standard languages for processing XML documents. However, specifying their complete semantics in a formal way seems almost impossible. Indeed, an attempt by the W3C XML Query Working Group to do so for XQuery was ultimately abandoned. We introduce three sublanguages, called MiXPath, MiXQuery and MiXSLT, and describe their syntax and formal semantics. The syntax and semantics of these languages are chosen such that they are consistent with the ones given in the relatedW3C recommendations. As such this provides a practical foundation for research and teaching of XML languages. For this purpose the sublanguages are chosen such that they contain the most crucial features, constructs and expressions of each of these three languages.
EN
For designing and analyzing complex workflow nets the notion of hierarchical decomposition can be essential for keeping the structure of the workflow comprehensible. In this paper we study two classes of nets: hierarchical nets and extended hierarchical nets. The first have a simple hierarchical structure and can be defined in terms of five simple refinement rules. We show that for arbitrary nets it can be easily verified if they can be constructed this way, thus confirming their good design and the properties following from it. As we prove, this can be done by performing the refinements in reverse, i.e., by contracting subnets into single nodes. It is shown that the choice of the contracted subnet does not change the final result of the process, and therefore this procedure for checking the hierarchical structure requires no back-tracking. The second class, extended hierarchical nets, is an extension of the first class where two types of extra refinements are introduced that allow to indicate (1) the synchronization between two parallel running subworkflows or (2) the transfer of a thread from one subworkflow to another one. These refinements come with natural and necessary preconditions that ensure that result is still a sound workflow net. In case (1) where we want to synchronize two actions in two subworkflows, we should convince ourselves that the subworkflows represent parallel threads which always execute together, otherwise a deadlock could easily arise. Dually, in case (2), if after the moment that a choice was made between two subworkflows we at a later point in the workflow want to allow a transfer between them, this can be done safely provided that we did not enter any thread fork in the meantime. We show that the class of extended hierarchical nets, which is defined by adding these two additional types of refinement, is a proper superset of the hierarchical nets, but still all such nets exhibit the correctness property of *-soundness. We do this by showing that the class is a proper subset of the AND-OR nets which were in earlier work shown to have this property.
4
Content available remote Towards a Formal Semantics for the Process Model of the Taverna Workbench. Part I
EN
Workflow development and enactment workbenches are becoming a standard tool for conducting in silico experiments. Their main advantages are easy to operate user interfaces, specialized and expressive graphical workflow specification languages and integration with a huge number of bioinformatic services. A popular example of such a workbench is Taverna, which has many additional useful features like service discovery, storing intermediate results and tracking data provenance. We discuss a detailed formal semantics for Scufl - the workflow definition language of the Taverna workbench. It has several interesting features that are notmet in other models including dynamic and transparent type coercion and implicit iteration, control edges, failure mechanisms, and incominglinks strategies. We study these features and investigate their usefulness separately as well as in combination, and discuss alternatives. The formal definition of such a detailed semantics not only allows to exactly understand what is being done in a given experiment, but is also the first step toward automatic correctness verification and allows the creation of auxiliary tools that would detect potential errors and suggest possible solutions to workflow creators, the same way as Integrated Development Environments aid modern programmers. A formal semantics is also essential for work on enactment optimization and in designing the means to effectively query workflow repositories. This paper is the first of two. It defines, explains and discusses fundamental notions for describing Scufl graphs and their semantics. Then, in the second part, we use these notions to define the semantics and show that our definition can be used to prove properties of Scufl graphs.
5
Content available remote Towards a Formal Semantics for the Process Model of the Taverna Workbench. Part II
EN
Workflow development and enactment workbenches are becoming a standard tool for conducting in silico experiments. Their main advantages are easy to operate user interfaces, specialized and expressive graphical workflow specification languages and integration with a huge number of bioinformatic services. A popular example of such a workbench is Taverna, which has many additional useful features like service discovery, storing intermediate results and tracking data provenance. We discuss a detailed formal semantics for Scufl - the workflow definition language of the Taverna workbench. It has several interesting features that are notmet in other models including dynamic and transparent type coercion and implicit iteration, control edges, failure mechanisms, and incominglinks strategies. We study these features and investigate their usefulness separately as well as in combination, and discuss alternatives. The formal definition of such a detailed semantics not only allows to exactly understand what is being done in a given experiment, but is also the first step toward automatic correctness verification and allows the creation of auxiliary tools that would detect potential errors and suggest possible solutions to workflow creators, the same way as Integrated Development Environments aid modern programmers. A formal semantics is also essential for work on enactment optimization and in designing the means to effectively query workflow repositories. This paper is the second of two. In the first one [13] we have defined, explained and discussed fundamental notions for describing Scufl graphs and their semantics. Here, in the second part, we use these notions to define the semantics and show that our definition can be used to prove properties of Scufl graphs.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.