Indexing business processes based on annotated finite state automata

B. Mahleko, Andreas Wombacher

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

31 Citations (Scopus)
1 Downloads (Pure)


The existing service discovery infrastructure with UDDI as the de facto standard, is limited in that it does not support more complex searching based on matching business processes. Two business processes match if they agree on their simple services, their processing order as well as any mandatory or optional requirements for the service. This matching semantics can be formalized by modelling business processes as annotated finite state automata (aFSAs) and deciding emptiness of the intersection aFSA. Computing the intersection of aFSAs and deciding emptiness are computationally expensive, being more than quadratic on the number of states and transitions, thus does not scale for large service repositories. This paper presents an approach for indexing and matching business processes modeled as aFSAs, for the purpose of service discovery. Evaluation of this approach shows a performance gain of several orders of magnitude over sequential matching and a linear complexity with regard to the data set size.
Original languageUndefined
Title of host publicationIEEE International Conerence on Web Services, ICWS 2006
Place of PublicationLos Alamitos
Number of pages9
ISBN (Print)0 7695 2669 1
Publication statusPublished - Sept 2006
EventIEEE International Conerence on Web Services, ICWS 2006 - Chicago, USA
Duration: 18 Sept 200622 Sept 2006

Publication series

PublisherIEEE Computer Society Press


ConferenceIEEE International Conerence on Web Services, ICWS 2006
Other18-22 Sep 2006


  • EWI-6160
  • IR-63192
  • METIS-238092
  • IS-SETI: SEcurity and Trust in Inter-organizational workflow management

Cite this