Most service composition approaches rely on top down decomposition of a problem and AI-style planning to assemble services into a meaningful whole, impeding reuse and flexibility. In contrast, our approach starts from declarative knowledge about the semantics of individual services and constructs a full-blown orchestration process that supports sequence, choice and parallelism. The approach, which is able to generate OWL-S and WS-BPEL based description, is unique in producing complex compositions out of semantic links between services in a flexible way. It also allows reusing knowledge about semantic dependencies in the network to generate new compositions through new requests and modification of services at run-time. © 2012 IEEE.