  Machine clients are increasingly making use of the Web to perform tasks.
While Web services traditionally mimic remote procedure calling interfaces, a
new generation of so-called hypermedia APIs works through hyperlinks and forms,
in a way similar to how people browse the Web. This means that existing
composition techniques, which determine a procedural plan upfront, are not
sufficient to consume hypermedia APIs, which need to be navigated at runtime.
Clients instead need a more dynamic plan that allows them to follow hyperlinks
and use forms with a preset goal. Therefore, in this article, we show how
compositions of hypermedia APIs can be created by generic Semantic Web
reasoners. This is achieved through the generation of a proof based on semantic
descriptions of the APIs' functionality. To pragmatically verify the
applicability of compositions, we introduce the notion of pre-execution and
post-execution proofs. The runtime interaction between a client and a server is
guided by proofs but driven by hypermedia, allowing the client to react to the
application's actual state indicated by the server's response. We describe how
to generate compositions from descriptions, discuss a computer-assisted process
to generate descriptions, and verify reasoner performance on various
composition tasks using a benchmark suite. The experimental results lead to the
conclusion that proof-based consumption of hypermedia APIs is a feasible
strategy at Web scale.
