Since the World Wide Web is enlarging its scale, users cannot find and utilize information easily. Hence problem-solving systems in the Web environment are required. The core of such systems is the Problem Solver Markup Language (PSML) and PSML-based distributed Web inference engines. In this paper, we demonstrate a possible implementation of certain distributed reasoning capablities as required in the future PSML. In particular, our proposed implementation, called β-PSML, is based on the combination of OWL (Web Ontology Language) with Horn clauses. From the viewpoint of expressive power, the proposed β-PSML can represent multi-argument relation that is an extension of the OWL capability, and models domains with a rich hierarchical structure for Horn clauses. Furthermore, we discuss how to extend the β-PSML for solving problems in a large-scale distributed Web environment.