Please wait a minute...
Shopping Cart Email List Chinese
Advanced Search Fig/Tab
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Featured Articles  |  Most Downloaded  |  Most Reading
Online Submission Subscribe to Our RSS Content Feed
Front. Comput. Sci.    2015, Vol. 9 Issue (1) : 55-74    https://doi.org/10.1007/s11704-014-3239-y
RESEARCH ARTICLE
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
 Download: PDF(515 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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
 Cite this article:   
Silvano COLOMBO TOSATTO,Pierre KELSEN,Qin MA, et al. Algorithms for tractable compliance problems[J]. Front. Comput. Sci., 2015, 9(1): 55-74.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-014-3239-y
https://academic.hep.com.cn/fcs/EN/Y2015/V9/I1/55
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
[1] Shuaiqiang WANG, Yilong YIN. Polygene-based evolutionary algorithms with frequent pattern mining[J]. Front. Comput. Sci., 2018, 12(5): 950-965.
[2] Yong WANG, Zhi-Zhong LIU, Jianbin LI, Han-Xiong LI, Jiahai WANG. On the selection of solutions for mutation in differential evolution[J]. Front. Comput. Sci., 2018, 12(2): 297-315.
[3] Quanjun YIN, Long QIN, Yong PENG, Wei DUAN. Learning real-time search on c-space GVDs[J]. Front. Comput. Sci., 2017, 11(6): 1036-1049.
[4] Qingliang CHEN,Kaile SU,Abdul SATTAR,Xiangyu LUO,Aixiang CHEN. A first-order coalition logic for BDI-agents[J]. Front. Comput. Sci., 2016, 10(2): 233-245.
[5] Yingying ZHU,Cong YAO,Xiang BAI. Scene text detection and recognition: recent advances and future trends[J]. Front. Comput. Sci., 2016, 10(1): 19-36.
[6] Hebah ELGIBREEN,Mehmet Sabih AKSOY. RULES-IT: incremental transfer learning with RULES family[J]. Front. Comput. Sci., 2014, 8(4): 537-562.
[7] Chaoqun LI,Liangxiao JIANG,Hongwei LI. Naive Bayes for value difference metric[J]. Front. Comput. Sci., 2014, 8(2): 255-264.
[8] Dunwei GONG, Yan ZHANG. Generating test data for both path coverage and fault detection using genetic algorithms[J]. Front Comput Sci, 2013, 7(6): 822-837.
[9] Pablo RABANAL, Ismael RODRíGUEZ, Fernando RUBIO. An ACO-RFD hybrid method to solve NP-complete problems[J]. Front Comput Sci, 2013, 7(5): 729-744.
[10] Hongli YANG, Chao CAI, Liyang PENG, Xiangpeng ZHAO, Zongyan QIU, Shengchao QIN. Algorithms for checking channel passing in web service choreography[J]. Front Comput Sci, 2013, 7(5): 710-728.
[11] Yi WANG, Renfa LI. FPGA based unified architecture for public key and private key cryptosystems[J]. Front Comput Sci, 2013, 7(3): 307-316.
[12] Jie LUO. A general framework for computing maximal contractions[J]. Front Comput Sci, 2013, 7(1): 83-94.
[13] Bo YUAN, Wenhuang LIU. Measure oriented training: a targeted approach to imbalanced classification problems[J]. Front Comput Sci, 2012, 6(5): 489-497.
[14] Min XIE, Laks V. S. LAKSHMANAN, Peter T. WOOD. Composite recommendations: from items to packages[J]. Front Comput Sci, 2012, 6(3): 264-277.
[15] Fabian GIESEKE, Gabriel MORUZ, Jan VAHRENHOLD. Resilient k-d trees: k-means in space revisited[J]. Front Comput Sci, 2012, 6(2): 166-178.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed