Complexity of synthesis of composite service with correctness guarantee

• Published in: Science China. Information sciences 2012-03, Vol.55 (3), p.638-649
• Main Authors: Deng, Ting, Huai, JinPeng, Wo, TianYu
• Format: Article
• Language: English
• Subjects: China; Complexity; Computer Science; Construction specifications; CTL; Design engineering; Guarantees; Information Systems and Communication Service; Program verification (computers); Research Paper; Software development; Synthesis; Temporal logic; Web services; Web服务; 合成; 复合; 复杂性; 时序逻辑; 煤制油; 软件开发
• ISSN: 1674-733X; 1869-1919
• DOI: 10.1007/s11432-011-4460-z

How to compose existing web services automatically and to guarantee the correctness of the design （e.g. temporal constraints specified by temporal logic LTL, CTL or CTL＊） is an important and challenging problem in web services. Most existing approaches use the process in conventional software development of design, verification, analysis and correction to guarantee the correctness of composite services, which makes the composition process both complex and time-consuming. In this paper, we focus on the synthesis problem of composite service; that is, for a given set of services and correctness constraint specified by CTL or CWL＊ formula, a composite service is automatically constructed which guarantees that the correctness is ensured. We prove that the synthesis problem for CTL and CTL＊ are complete for EXPTIME and 2EXPTIME, respectively. Moreover, for the case of synthesis failure, we discuss the problem of how to disable outputs of environment （i.e. users or services） reasonably to make synthesis successful, which are also proved complete for EXPTIME and 2EXPTIME for CTL and CTL＊, respectively.