Compact Representations and Efficient Algorithms for Operating Guidelines

• Autorzy: Lohmann N. , Wolf K.
• Języki publikacji: EN

Abstrakty

EN

Operating guidelines characterize correct interaction (e. g., deadlock freedom) with a service. They can be stored in a service registry. They are typically represented as an annotated transition system where the annotations are Boolean formulae attached to the states. The core result of this article is to propose an alternative representation of operating guidelines where, instead of a Boolean formula, only a few bits need to be stored with a state. This way, we safe one order of magnitude in the space complexity of the representation. Moreover, we demonstrate that the new representation yields efficiency gains in several algorithms which involve operating guidelines. Finally we show that the new representation permits the translation of the transition system representing the operating guidelines into a Petri net which typically yields further gains concerning the space for storing operating guidelines.

Słowa kluczowe

EN

operating guidelines; service automaton; Implicit representation of formulae; matching with new representation; substitutability; minimization; Petri net

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 108, nr 1/2
• Strony: 43--62
• Opis fizyczny: Bibliogr. 27 poz., tab., wykr.

Twórcy

autor

Lohmann N.

autor

Wolf K.

• Universität Rostock, Institut für Informatik, 18051 Rostock, Germany,

Bibliografia

• [1] Aalst, W. M. P. v. d., Dongen, B. v., Herbst, J., Maruster, L., Schimm, G., Weijters, A. J. M. M.: Workflow mining: A survey of issues and approaches, Data Knowl. Eng., 47(2), 2003, 237-267.
• [2] Aalst, W. M. P. v. d., Lohmann, N., Massuthe, P., Stahl, C., Wolf, K.: Multiparty Contracts: Agreeing and Implementing Interorganizational Processes, Comput. J., 2009, (In press).
• [3] Alves, A., et al.: Web Services Business Process Execution Language Version 2.0, OASIS Standard, OASIS, 2007.
• [4] Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial Algorithms for the Synthesis of Bounded Nets, TAPSOFT 1995, 915, Springer, 1995.
• [5] Brand, D., Zafiropulo, P.: On Communicating Finite-State Machines, J. ACM, 30(2), 1983, 323-342.
• [6] Brookes, S. D., Hoare, C. A. R., Roscoe, A. W.: A Theory of Communicating Sequential Processes, J. ACM, 31(3), 1984, 560-599.
• [7] Bryant, R. E.: Graph-Based Algorithms for Boolean Function Manipulation, IEEE Trans. Computers, C-35(8), 1986, 677-691.
• [8] Carmona, J., Cortadella, J., Kishinevsky, M.: A Region-Based Algorithm for Discovering Petri Nets from Event Logs, BPM 2008, 5240, Springer, 2008.
• [9] Cortadella, J., Kishinevsky, M., Kondratyev, A., Lavagno, L., Yakovlev, A.: Petrify: A Tool for Manipulating Concurrent Specifications and Synthesis of Asynchronous Controllers, Trans. Inf. and Syst., E80-D(3), 1997, 315-325.
• [10] Cortadella, J., Kishinevsky, M., Lavagno, L., Yakovlev, A.: Deriving Petri nets from finite transition systems, IEEE Trans. Computers, 47(8), 1998, 859-882.
• [11] Ehrenfeucht, A., Rozenberg, G.: Partial (Set) 2-Structures. Part I, II, Acta Inf., 27(4), 1989, 315-368.
• [12] Gottschalk, K.: Web Services Architecture Overview, IBM whitepaper, IBM developerWorks, 2000, http://ibm.com/developerWorks/web/library/w-ovr.
• [13] Hopcroft, J.: An n log n algorithm for minimizing states in a finite automaton, Technical Report STAN-CS-71-190, Stanford University, 1971.
• [14] Kaschner, K., Lohmann, N.: Automatic Test Case Generation for Interacting Services, ICSOC 2008 Workshops, 5472, Springer, 2009.
• [15] Kaschner, K., Massuthe, P., Wolf, K.: Symbolic Representation of Operating Guidelines for Services, Petri Net Newsletter, 72, 2007, 21-28.
• [16] Lohmann, N.: Correcting Deadlocking Service Choreographies Using a Simulation-Based Graph Edit Distance, BPM 2008, 5240, Springer, 2008.
• [17] Lohmann, N.: A Feature-Complete Petri Net Semantics for WS-BPEL 2.0, WS-FM 2007, 4937, Springer, 2008.
• [18] Lohmann, N., Kleine, J.: Fully-automatic Translation of Open Workflow Net Models into Simple Abstract BPEL Processes, Modellierung 2008, P-127, GI, 2008.
• [19] Lohmann, N., Massuthe, P., Wolf, K.: Operating Guidelines for Finite-State Services, PETRI NETS 2007, 4546, Springer, 2007.
• [20] Lynch, N. A.: Distributed Algorithms, Morgan Kaufmann, 1996.
• [21] Massuthe, P.: Operating Guidelines for Services, Dissertation, Humboldt-Universit¨at zu Berlin, Mathematisch-Naturwissenschaftliche Fakult¨at II, Berlin, Germany; Eindhoven University of Technology, Eindhoven, The Netherlands, 2009.
• [22] OMG: Business Process Modeling Notation (BPMN) Version 1.0, OMG Final Adopted Specification, OMG, 2006.
• [23] OMG: Unified Modeling Language (UML), Version 2.1.2, OMG, 2007.
• [24] Stahl, C., Massuthe, P., Bretschneider, J.: Deciding Substitutability of Services with Operating Guidelines, LNCS Transactions on Petri Nets and Other Models of Concurrency, II(5460), 2009, 172-191.
• [25] Tinder, R. F.: Engineering Digital Design, Revised second edition, Academic Press, 2000.
• [26] Valmari, A.: Stubborn sets for reduced state space generation, PETRI NETS 1989, 483, Springer, 1989.
• [27] Wombacher, A., Fankhauser, P., Mahleko, B., Neuhold, E. J.: Matchmaking for Business Processes Based on Choreographies, Int. J. Web Service Res., 1(4), 2004, 14-32