Web services are a new breed of Web application. They are self-contained, self-describing, modular applications that can be published, located, and invoked across the Web [154] Web services are a promising technology for ad hoc machine to machine interaction across application, enterprise and web boundaries. Self describing web services is a catchy phrase but it should mean more than having an interface description written in XML syntax. This research is motivated by the vision of web services in the future as loosely coupled applications operating on different platforms inter-operating without prior agreements in place and without direct human intervention at runtime. The main obstacle to advancing the vision of ad hoc runtime interaction is complexity. The complexity of ad hoc interaction for web services is related to 1) the information the service requires and provides and the nuances of the domain or context the service operates on and in. 2) The specific nature of the operations the service provides and the constraints related to those operations and 3) the necessary ordering of operations to achieve the desired result. There are three problems that must be addressed before the vision for web services can become a reality. These problems are aligned with the three aspects of service complexity identified above. The three inter-related elements of this research address each of these problems. The first part of the research deals with what web services "talk" about and how the data required or provided by services can be described to enable mutual understanding. An extension to traditional conceptual models, called outsourced type descriptions, allows the description of shared data in terms of publicly available information, including standards, specifications, ontologies and definitions from dictionaries and thesauri. The second part is concerned with describing why services interact and the capabilities (actions or information) services can provide. A structured format for the description, advertisement and discovery of services based on what they actually do is presented. The structured format is based on previous work in the description of actions and the context in which they are performed. The last part of the research addresses how previously unknown services can talk to one another to supply and use the advertised capabilities. Interaction is based on providers having "plans" for the delivery of capabilities. The flow of interaction is directed by the service providers' data requirements and is responsive to the resources of the client. A small language for information gathering based on well known interaction primitives is defined. An example implementation of a capability plan interpreter demonstrates how messages are generated, managed and interpreted at runtime in order to satisfy the client's goals.