zbMATH — the first resource for mathematics

Algorithms for tractable compliance problems. (English) Zbl 1403.68077
Summary: 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.
68Q25 Analysis of algorithms and problem complexity
68W40 Analysis of algorithms
90B70 Theory of organizations, manpower planning in operations research
Full Text: DOI
[1] Kharbili, M., Business process regulatory compliance management solution frameworks: a comparative evaluation, 23-32, (2012)
[2] Sadiq, S.; Governatori, G., Managing regulatory compliance in business processes, 159-175, (2010)
[3] Governatori, G.; Sadiq, S.; Cardoso, J. (ed.); Aalst v. d, W. (ed.), The journey to business process compliance, 426-454, (2009)
[4] Governatori, G.; Milosevic, Z.; Sadiq, S., Compliance checking between business processes and business contracts, 221-232, (2006)
[5] Roman, D.; Kifer, M., Reasoning about the behaviour of semantic web services with concurrent transaction logic, 627-638, (2007)
[6] Ghose, A.; Koliadis, G., Auditing Business Process Compliance, 169-180, (2007)
[7] Colombo Tosatto, S.; Governatori, G.; Kelsen, P., Business process regulatory compliance is hard, IEEE Transactions on Service Computing, 99, 1, (2014)
[8] Prakken, H.; Sergot, M., Dyadic deontic logic and contrary-to-duty obligations, Defeasible Deontic Logic, 263, 223-262, (1997) · Zbl 0913.03009
[9] Jones, A.; Carmo, J.; Gabbay, D. (ed.); Guenthner, F. (ed.), Deontic logic and contrary-to-duties, 265-343, (2002)
[10] Kiepuszewski, B.; Hofstede, A. H M.; Bussler, C. J., On structured work-flow modelling, 431-445, (2000)
[11] Polyvyanyy, A.; García-Bañuelos, L.; Dumas, M., Structuring acyclic process models, Information Systems, 37, 518-538, (2012)
[12] Keller, G.; Teufel, T., SAP R/3 Process Oriented Implementation: Iterative Process Prototyping, (1998)
[13] Governatori, G.; Hoffmann, J.; Sadiq, S. W.; Weber, I.; Ardagna, D. (ed.); Mecella, M. (ed.); Yang, J. (ed.), Detecting regulatory compliance for business process models through semantic annotations, 5-17, (2008)
[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, 50, 510-530, (1985) · Zbl 0578.03011
[15] Governatori, G.; Rotolo, A., Norm compliance in business process modeling, 194-209, (2010)
[16] Aalst, WMP; Pesic, M.; Schonenberg, H., Declarative workflows: balancing between flexibility and support, Computer Science-Research and Development, 23, 99-113, (2009)
[17] Awad, A.; Decker, G.; Weske, M., Efficient compliance checking using bpmn-q and temporal logic, Lecture Notes in Computer Science, 5240, 326-341, (2008)
[18] Hoffmann, J.; Weber, I.; Governatori, G., On compliance checking for clausal constraints in annotated process models, Information Systems Frontiers, 14, 155-177, (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.