Algorithms for tractable compliance problems

Abstract

In general the problem of verifying whether a structured business process is compliant with a given set of regulations is NP-hard. The present paper focuses on identifying a tractable subset of this problem, namely verifying whether a structured business process is compliant with a single global obligation. Global obligations are those whose validity spans for the entire execution of a business process. We identify two types of obligations: achievement and maintenance.

In the present paper we firstly define an abstract framework capable to model the problem and secondly we define procedures and algorithms to deal with the compliance problem of checking the compliance of a structured business process with respect to a single global obligation. We show that the algorithms proposed in the paper run in polynomial time.

Keywords

compliance / business process models / algorithms / computational complexity

References

[1] Kharbili M. Business process regulatory compliance management solution frameworks: a comparative evaluation. In: Proceedings of AsiaPacific Conference on Conceptual Modelling. 2012, 23-32

[2] Sadiq S, Governatori G. Managing regulatory compliance in business processes. In: Proceedings of International Handbooks on Information Systems. 2010, 159-175

[3] Governatori G, Sadiq S. The journey to business process compliance. In: Cardoso J, Aalst v. d W, eds. Handbook of Research on BPM. 2009, 426-454

[4] Governatori G, Milosevic Z, Sadiq S. Compliance checking between business processes and business contracts. In: Proceedings of the 10th International Enterprise Distributed Object Computing Conference. 2006, 221-232

[5] Roman D, Kifer M. Reasoning about the behaviour of semantic web services with concurrent transaction logic. In: Proceedings of the 33rd International Conference on Very Large Data Bases. 2007, 627-638

[6] Ghose A, Koliadis G. Auditing Business Process Compliance. Springer Berlin Heidelberg. 2007, 169-180

[7] Colombo Tosatto S, Governatori G, Kelsen P. Business process regulatory compliance is hard. IEEE Transactions on Service Computing, 2014, (99): 1

[8] Prakken H, Sergot M. Dyadic deontic logic and contrary-to-duty obligations. Defeasible Deontic Logic, 1997, 263: 223-262

[9] Jones A, Carmo J. Deontic logic and contrary-to-duties. In: Gabbay D, Guenthner F, eds. Handbook of Philosophical Logic. 2002, 265-343

[10] Kiepuszewski B, Hofstede A H M, Bussler C J. On structured workflow modelling. In: Proceedings of the 12th International Conference on Advanced Information Systems Engineering. 2000, 431-445

[11] Polyvyanyy A, García-Bañuelos L, Dumas M. Structuring acyclic process models. Information Systems, 2012, 37(6): 518-538

[12] Keller G, Teufel T. SAP R/3 Process Oriented Implementation: Iterative Process Prototyping. Addison-Wesley, 1998

[13] Governatori G, Hoffmann J, Sadiq S W, Weber I. Detecting regulatory compliance for business process models through semantic annotations. In: Ardagna D, Mecella M, Yang J, eds. Business Process Management Workshops. 2008, 5-17

[14] Alchourrón C E, Gärdenfors P, Makinson D. On the logic of theory change: partial meet contraction and revision functions. Journal of Symbolic Logic, 1985, 50(2): 510-530

[15] Governatori G, Rotolo A. Norm compliance in business process modeling. In: Proceedings of the 4th International Web Rule Symposium: Research Based and Industry Focused. 2010, 194-209

[16] Aalst W M P, Pesic M, Schonenberg H. Declarative workflows: balancing between flexibility and support. Computer Science-Research and Development, 2009, 23(2): 99-113

[17] Awad A, Decker G, Weske M. Efficient compliance checking using bpmn-q and temporal logic. Lecture Notes in Computer Science, 2008, 5240, 326-341

[18] Hoffmann J, Weber I, Governatori G. On compliance checking for clausal constraints in annotated process models. Information Systems Frontiers, 2012, 14(2): 155-177

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg