As Web Services become more prevalent -- with the aim of achieving interoperability between heterogeneous, decentralized and distributed systems -- the problem of selecting and composing services to accomplish a given task becomes more important. Using Web ontologies to describe different properties of Web Services provided by separate developers facilitates their integration. Automating the composition of Web Services is essential for various different subjects ranging from ordinary users performing tasks on the Web, businesses carrying out complex transactions, and scientists collaborating with each other on the computational Grid.

In this thesis I present the HTN-DL formalism which combines Hierarchical Task Network (HTN) planning and Description Logics (DL) to automatically compose Web Services which are described with Web Ontology Language (OWL).

The main contributions of this thesis are as follows:

• The HTN-DL formalism, which couples Hierarchical Task Network (HTN) planning and Description Logics. HTN-DL combines the expressivity of Description Logics with the efficiency of HTN planning systems to solve Web Service composition problems.

• A translation algorithm from the Semantic Web Service language OWL-S to HTN-DL. This translation algorithm shows that the control constructs used to describe the control flow of a Web Service workflow can be encoded in an HTNDL domain. The translation also provides a semantics for OWL-S processes; and it is also shown that this semantics is compatible with the previously proposed Situation Calculus based semantics of OWL-S.

• Novel optimization techniques for DL reasoning which target nominals and large number of individuals. These optimization techniques allow the HTNDL planner to efficiently reason with OWL-DL ontologies during planning. Our empirical analysis shows that these optimizations dramatically improve consistency checking, classification, and realization tasks.

• Optimizations for conjunctive query answering w.r.t. DL knowledge bases. Inspired by some query optimization techniques used in relational databases, a cost-based model is presented to estimate the evaluation time of DL queries.

• An implementation of the HTN-DL planning system that interacts directly with Web Services. The components of the planning system, OWL-DL reasoner Pellet and API for OWL-S services, are also released as stand-alone tools and have been incorporated into many systems.