Reasoning about Partially Ordered Web Service Activities in PSL

摘要

Many tasks within semantic web service discovery can be formalized as reasoning problems related to the partial ordering of sub-activity occurrences in a complex activity. We show how the first-order ontology of the Process Specification Language (PSL) can be used to represent both the queries and the process descriptions that constitute the underlying theory for the reasoning problems. We also identify extensions of the PSL Ontology for which these problems are NP-complete and then explicitly axiomatize classes of activities for which the various reasoning problems are tractable.