Abstract: “This paper presents an improvement of requirement-oriented compliance checking algorithm to support trust-based decision making in service workflow environments. The proposed algorithm is based on our previous progressive works on (1) Service Workflow Specification language (SWSpec) serving as a formal and uniformed representation of requirements, and (2) the algorithm based on Constrained Truth Table (CTT), specifically developed for compliance checking for the Composite class of SWSpec. However, CTT algorithmpractically suffers from high complexitywhich is O(|S||V|2|V|), where |V| is the number of services presented in a workflow, and |S| is the size of a SWSpec formula to be checked. In this paper, we improve algorithm CTT by using Exclusive Disjunctive Normal Form (EDNF) as a new data structure that reduces the time complexity in the average case to O(|S||V|2). Finally, the performance comparison between these two approaches is conducted”

Keywords: Service, Workflow, Compliance Checking