第1卷第2期 智能系统学报 Vol.1№2 2006年10月 CAAI Transactions on Intelligent Systems 0ct.2006 基于有限状态自动机的服务组合模型 蒋运承12，汤庸2，邓培民 (1.广西师范大学计算机科学与信息工程学院，广西桂林541004：2.中山大学计算机科学系，广东广州510275) 摘要：分析了目前服务计算的研究现状和存在的问题，在D Berardi和A Wombacher的基础上提出了一种带条件 的有限状态自动机模型cFSA(Finite State Automata with condition),并给出了基于cFSA的服务理论模型.在该服 务理论模型的基础上提出了一种基于有限状态自动机的服务组合形式化模型，并给出了该模型的代数性质和实现 方法 关键词：有限状态自动机：带条件的有限状态自动机：服务计算：服务组合 中图分类号：TP18文献标识码：A文章编号：1673-4785(2006)02-004810 A service composition model based on finite state automata JIANG Yumcheng'2,TANG Yong?,DENG Pei-min' (1.College of Computer Sciences and Information Engineering,Guangxi Normal University,Guilin 541004,China;2.De- partment of Computer Sciences,Sun Yasen University,Guangzhou 510275,China) Abstract:The existing conditions and problems of service computing are analyzed,and based on the work of D Berardi and A Wombacher,a kind of finite state automata with condition cFSA(Finite State Automata with condition)is presented,and the service theory model based on cFSA is presented too.Based on this model,the formal theory model of service composition based on finite state automata with condition cFSA is studied.The algebraic property and implementing method of the service composition model are studied. Key words :finite state automata;finite state automata with condition;service computing;service composition 面向服务的计算山(service-oriented compu- Microsoft将WSFL和LANG结合起来提出了服 ting)是一种新的分布式计算范型，它以服务作为开 务组合语言BPEL4WSo1,蒋运承研究了面向服务 发应用或提供问题解决方案的基本元素.而服务是 质量的服务匹配算法山等. 一种自描述的、平台无关的计算元素，它支持分布式 但是，目前e-Service的研究中，主要将服务看 应用的快速和低价组合.例如，目前的Web服务2)、 成是一个无状态的动作，事实上这是不充分的，服务 语义Web服务)或基于主体的服务4等都是面向应该是一个有状态的动作序列1)，这方面已有研 服务的计算范型，文中统称为服务或e-Service. 究.例如，D.Berardi用有限状态自动机来建立Web 目前国内外对e-Service进行了深入研究，W3C 服务的理论模型，但D.Berardi的工作只研究了服 提出了Web服务描述语言WSDL I5I,D Martin基 务描述与有限状态自动机的转换问题，没有研究基 于OWL提出了语义Web服务本体OWL-s),史 于有限状态自动机的服务匹配和组合问题】.A 忠植利用描述逻辑理论来描述主体服务)，蒋运承 Wombacher研究了基于有限状态自动机的Web服 提出了主体服务描述语言SDL SINI4,并且这些服 务商业过程的匹配问题，但A Wombacher也没有 务描述语言都有相应的服务匹配算法.BM根据工 研究基于有限状态自动机的服务组合问题).本文 作流的思想提出了Web服务流语言WSFLI81,Mi 进一步研究了基于有限状态自动机的服务组合问 crosoft提出了服务组合语言LANG),BM和 题 收稿日期：200602-23. 1 服务理论模型 基金项目：国家自然科学基金资助项目(60373081)；广东省自然科 学重点基金资助项目(04105503) 为了用有限状态自动机来描述服务，下面先给 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 1 卷第 2 期 智 能 系 统 学 报 Vol. 1 №. 2 2006 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2006 基于有限状态自动机的服务组合模型 蒋运承1 ,2 ,汤 庸2 ,邓培民1 (1. 广西师范大学 计算机科学与信息工程学院 ,广西 桂林 541004 ; 2. 中山大学 计算机科学系 ,广东 广州 510275) 摘 要 :分析了目前服务计算的研究现状和存在的问题 ,在 D Berardi 和 A Wombacher 的基础上提出了一种带条件 的有限状态自动机模型 cFSA ( Finite State Automata with condition) ,并给出了基于 cFSA 的服务理论模型. 在该服 务理论模型的基础上提出了一种基于有限状态自动机的服务组合形式化模型 ,并给出了该模型的代数性质和实现 方法. 关键词 :有限状态自动机 ;带条件的有限状态自动机 ;服务计算 ;服务组合 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2006) 0220048210 A service composition model based on finite state automata J IAN G Yun2cheng 1 ,2 , TAN G Yong 2 , DEN G Pei2min 1 (1. College of Computer Sciences and Information Engineering , Guangxi Normal University , Guilin 541004 , China ; 2. De2 partment of Computer Sciences , Sun Ya2sen University , Guangzhou 510275 , China) Abstract :The existing conditions and problems of service comp uting are analyzed , and based on t he work of D Berardi and A Wombacher , a kind of finite state automata with condition cFSA (Finite State Automata with condition) is presented , and t he service theory model based on cFSA is presented too. Based on this model , t he formal theory model of service compo sition based on finite state automata with condition cFSA is st udied. The algebraic property and implementing met hod of t he service composition model are studied. Keywords :finite state automata ; finite state automata with condition ; service computing ; service composition 收稿日期 :2006202223. 基金项目 :国家自然科学基金资助项目(60373081) ; 广东省自然科 学重点基金资助项目(04105503) . 面向服务的计算[1 ] ( service2oriented comp u2 ting) 是一种新的分布式计算范型 ,它以服务作为开 发应用或提供问题解决方案的基本元素. 而服务是 一种自描述的、平台无关的计算元素 ,它支持分布式 应用的快速和低价组合. 例如 ,目前的 Web 服务[2 ] 、 语义 Web 服务[3 ] 或基于主体的服务[4 ] 等都是面向 服务的计算范型 ,文中统称为服务或 e2Service. 目前国内外对 e2Service 进行了深入研究 ,W3C 提出了 Web 服务描述语言 WSDL [5 ] ,D Martin 基 于 OWL 提出了语义 Web 服务本体 OWL2S [6 ] ,史 忠植利用描述逻辑理论来描述主体服务[7 ] ,蒋运承 提出了主体服务描述语言 SDLSIN [4 ] ,并且这些服 务描述语言都有相应的服务匹配算法. IBM 根据工 作流的思想提出了 Web 服务流语言 WSFL [ 8 ] ,Mi2 cro soft 提出了服务组合语言 XLAN G [9 ] , IBM 和 Microsoft 将 WSFL 和 XLAN G结合起来提出了服 务组合语言 BPEL4WS [10 ] ,蒋运承研究了面向服务 质量的服务匹配算法[11 ]等. 但是 ,目前 e2Service 的研究中 ,主要将服务看 成是一个无状态的动作 ,事实上这是不充分的 ,服务 应该是一个有状态的动作序列[12213 ] ,这方面已有研 究. 例如 ,D. Berardi 用有限状态自动机来建立 Web 服务的理论模型 ,但 D. Berardi 的工作只研究了服 务描述与有限状态自动机的转换问题 ,没有研究基 于有限状态自动机的服务匹配和组合问题[12 ] . A Wombacher 研究了基于有限状态自动机的 Web 服 务商业过程的匹配问题 ,但 A Wombacher 也没有 研究基于有限状态自动机的服务组合问题[13 ] . 本文 进一步研究了基于有限状态自动机的服务组合问 题. 1 服务理论模型 为了用有限状态自动机来描述服务 ,下面先给