|
|
Algorithms for tractable compliance problems |
Silvano COLOMBO TOSATTO1,3,*( ),Pierre KELSEN1( ),Qin MA1,Marwane el KHARBILI1,Guido GOVERNATORI2( ),Leendert van der TORRE1( ) |
1. Computer Science and Communication Unit, University of Luxembourg, Luxembourg L-1359, Luxembourg 2. NICTA, Brisbane QLD 4001, Australia 3. Dipartment di Informatica, Università di Torino, Torino 10149, Italy |
|
|
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
|
Corresponding Author(s):
Silvano COLOMBO TOSATTO
|
Issue Date: 09 February 2015
|
|
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
https://doi.org/10.1007/978-94-015-8851-5_10
|
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
https://doi.org/10.1007/3-540-45140-4_29
|
11 |
Polyvyanyy A, García-Ba?uelos L, Dumas M. Structuring acyclic process models. Information Systems, 2012, 37(6): 518-538
https://doi.org/10.1016/j.is.2011.10.005
|
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
https://doi.org/10.2307/2274239
|
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
https://doi.org/10.1007/s00450-009-0057-9
|
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
https://doi.org/10.1007/978-3-540-85758-7_24
|
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
https://doi.org/10.1007/s10796-009-9179-7
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|