Service-oriented computing (SOC) has emerged as the eminent market environment for sharing and reusing service-centric capabilities. The underpinning for an organization's use of SOC techniques is the ability to discover and compose Web services. In this paper we present a generalized semantics-based technique for automatic service composition that combines the rigor of process-oriented composition with the descriptiveness of semantics. Our generalized approach extends the common practice of linearly linked services by introducing the use of a conditional directed acyclic graph (DAG) where complex interactions, containing control flow, information flow and pre/post conditions, are effectively represented.