Abstract We present an implemented reasoner for fuzzy order-sorted feature (OSF) logic, supporting fuzzy unification and normalization of OSF terms modulo a sort theory. Fuzzy OSF logic is a knowledge representation and reasoning language based on feature symbols, denoting functions, and sort symbols, denoting fuzzy sets. Sort symbols are organized in a fuzzy subsumption relation that extends to OSF terms, record-like structures representing classes of entities. The unification algorithm for these structures provides a calculus of fuzzy type subsumption. We demonstrate the system’s behavior on representative examples, such as computing the membership degree of an instance to a sort, and computing subsumption degrees between sorts and OSF terms. We also report a comparison with a resolution-based fuzzy logic programming system.

Order-Sorted Feature (OSF) logic is a knowledge representation and reasoning language based on function-denoting feature symbols and set-denoting sort symbols ordered in a subsumption lattice. OSF logic allows the construction of record-like terms that represent classes of entities and that are themselves ordered in a subsumption relation. The unification algorithm for such structures provides an efficient calculus of type subsumption, which has been applied in computational linguistics and implemented in constraint logic programming languages such as LOGIN and LIFE and automated reasoners such as CEDAR. This work generalizes OSF logic to a fuzzy setting. We give a flexible definition of a fuzzy subsumption relation which generalizes Zadeh's inclusion between fuzzy sets. Based on this definition we define a fuzzy semantics of OSF logic where sort symbols and OSF terms denote fuzzy sets. We extend the subsumption relation to OSF terms and prove that it constitutes a fuzzy partial order with the property that two OSF terms are subsumed by one another in the crisp sense if and only if their subsumption degree is greater than 0. We show how to find the greatest lower bound of two OSF terms by unifying them and how to compute the subsumption degree between two OSF terms, and we provide the complexity of these operations.

Order-Sorted Feature (OSF) logic is a knowledge representation and reasoning language based on sorts – symbols that denote concepts ordered in a subsumption relation – and features – symbols that denote functional attributes. Reasoning with OSF logic is based on the unification of OSF terms, recordlike structures that denote classes of objects and that are themselves ordered in a subsumption relation. OSF term unification aims to combine the constraints expressed by two terms in a consistent way, and it takes into account the subsumption relation between sort symbols, providing an efficient calculus of type subsumption. This paper presents an approach to define approximate reasoning with OSF logic by extending its language with a similarity relation on sorts. In order for the OSF term unification algorithm to take into account this similarity and its interaction with the subsumption relation, we propose to combine the two relations into a single fuzzy subsumption relation. The advantage is that the same unification rules of OSF logic can then be applied to this fuzzy setting. We conclude by discussing potential applications of OSF logic extended with a sort similarity relation.

Taxonomies are frequently used to represent knowledge; a taxonomy is a set of concepts partially ordered by a subsumption (is-a) relation. Recently, the CEDAR project has proposed a CEDAR Semantic Web reasoner based on OSF logic, which has shown very promising results with respect to both efficiency and scalability. Indeed, the basic operations behind the reasoning mechanism of CEDAR amount to answering Boolean queries on a taxonomy. For instance, CEDAR answers a conjunctive query on a taxonomy by computing the greatest lower bound of a subset of its elements. This paper proposes a generalization of this operation to the setting where the taxonomy is regarded as a fuzzy partially ordered set and an answer to a conjunctive query is associated with a satisfaction (approximation) degree. A conjunctive query on the fuzzy taxonomy can be answered by applying the same encoding technique of the CEDAR reasoner, while the approximation degree of an answer can be computed by adapting shortest path algorithms for directed acyclic graphs that can be further optimized thanks to the information provided by the encoding.