Abstract
DecSerFlow is a declarative language to specify business processes. It consists of a set of temporal predicates that can be translated into LTL but limited to finite sequences. This paper focuses on the “conformance problem”: Given a set of DecSerFlow constraints, is there an execution sequence that satisfies all given constraints? This paper provides syntactic characterizations of conformance for several subclasses of DecSerFlow constraints. These characterizations directly lead to efficient (polynomial time) conformance testing. Furthermore, algorithms are developed to generate conforming strings if the set of constraints is conformable. A conformance analyzer is developed based on the syntactic characterizations and the string generating algorithms. Experiments reveal several interesting factors concerning performance and scalability.
Supported in part by a grant from Bosch.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
van der Aalst, W.M.P.: Business process management demystified: A tutorial on models, systems and standards for workflow management. In: Desel, J., Reisig, W., Rozenberg, G. (eds.) Lectures on Concurrency and Petri Nets. LNCS, vol. 3098, pp. 1–65. Springer, Heidelberg (2004)
van der Aalst, W.M.P., Pesic, M.: DecSerFlow: Towards a Truly Declarative Service Flow Language. In: Bravetti, M., Núñez, M., Zavattaro, G. (eds.) WS-FM 2006. LNCS, vol. 4184, pp. 1–23. Springer, Heidelberg (2006)
Artale, A., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M.: The complexity of clausal fragments of LTL. In: McMillan, K., Middeldorp, A., Voronkov, A. (eds.) LPAR-19 2013. LNCS, vol. 8312, pp. 35–52. Springer, Heidelberg (2013)
Bauland, M., Schneider, T., Schnoor, H., Schnoor, I., Vollmer, H.: The complexity of generalized satisfiability for linear temporal logic. In: Seidl, H. (ed.) FOSSACS 2007. LNCS, vol. 4423, pp. 48–62. Springer, Heidelberg (2007)
Chen, C.C., Lin, I.P.: The computational complexity of satisfiability of temporal horn formulas in propositional linear-time temporal logic. Inf. Proc. Lett. 45(3), 131–136 (1993)
Demri, S., Schnoebelen, P., Demri, S.E.: The complexity of propositional linear temporal logics in simple cases. Information and Computation 174, 61–72 (1998)
Dixon, C., Fisher, M., Konev, B.: Tractable temporal reasoning. In: Proc. International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press (2007)
Eisner, C., Fisman, D., Havlicek, J., Lustig, Y., McIsaac, A., Van Campenhout, D.: Reasoning with temporal logic on truncated paths. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 27–39. Springer, Heidelberg (2003)
Hull, R., Su, J., Vaculín, R.: Data management perspectives on business process management: tutorial overview. In: SIGMOD Conference, pp. 943–948 (2013)
Lichtenstein, O., Pnueli, A.: Checking that finite state concurrent programs satisfy their linear specification. In: POPL, pp. 97–107 (1985)
Pesic, M., Schonenberg, H., van der Aalst, W.M.P.: Declare: Full support for loosely-structured processes. In: EDOC, pp. 287–300 (2007)
Pichler, P., Weber, B., Zugal, S., Pinggera, J., Mendling, J., Reijers, H.A.: Imperative versus declarative process modeling languages: An empirical investigation. In: Daniel, F., Barkaoui, K., Dustdar, S. (eds.) BPM Workshops 2011, Part I. LNBIP, vol. 99, pp. 383–394. Springer, Heidelberg (2012)
Pnueli, A.: The temporal logic of programs. In: FOCS, pp. 46–57 (1977)
Silva, N.C., de Carvalho, R.M., Oliveira, C.A.L., Lima, R.M.F.: REFlex: An efficient web service orchestrator for declarative business processes. In: Basu, S., Pautasso, C., Zhang, L., Fu, X. (eds.) ICSOC 2013. LNCS, vol. 8274, pp. 222–236. Springer, Heidelberg (2013)
Sistla, A.P., Clarke, E.M.: The complexity of propositional linear temporal logics. J. ACM 32(3), 733–749 (1985)
Sun, Y., Xu, W., Su, J.: Declarative choreographies for artifacts. In: Liu, C., Ludwig, H., Toumani, F., Yu, Q. (eds.) Service Oriented Computing. LNCS, vol. 7636, pp. 420–434. Springer, Heidelberg (2012)
Vardi, M.Y., Wolper, P.: An automata-theoretic approach to automatic program verification (preliminary report). In: LICS, pp. 332–344 (1986)
Xu, W., Su, J., Yan, Z., Yang, J., Zhang, L.: An Artifact-Centric Approach to Dynamic Modification of Workflow Execution. In: Meersman, R., Dillon, T., Herrero, P., Kumar, A., Reichert, M., Qing, L., Ooi, B.-C., Damiani, E., Schmidt, D.C., White, J., Hauswirth, M., Hitzler, P., Mohania, M. (eds.) OTM 2011, Part I. LNCS, vol. 7044, pp. 256–273. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sun, Y., Su, J. (2014). Conformance for DecSerFlow Constraints. In: Franch, X., Ghose, A.K., Lewis, G.A., Bhiri, S. (eds) Service-Oriented Computing. ICSOC 2014. Lecture Notes in Computer Science, vol 8831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45391-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-662-45391-9_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45390-2
Online ISBN: 978-3-662-45391-9
eBook Packages: Computer ScienceComputer Science (R0)