Symbolic Techniques for Fuzzy Relations

by Ioana Cleopatra Pau, Research Institute for Symbolic Computation, Linz, Austria

Unification, matching and generalization problems play an important role in various areas of mathematics, computer science and artificial intelligence. Unification and matching are central computational mechanisms in automated reasoning, rewriting, declarative programming. 
Generalization is closely related to detecting similarities between  objects and to learning general structures from concrete instances. Anti-unification is a logic-based method for computing generalizations, with a wide range of applications. In the first-order syntactic case,  solutions of unification and matching problems make two given terms  identical, and in anti-unification, common parts of two terms should be exactly the same. While in many situations this is the desired outcome, there are cases when some tolerance with respect to the mismatches would offer a better result. The type of the accepted difference may vary, and many types of mismatches were explored in the fuzzy context.

In this tutorial we present algorithms for the above techniques by representing the imprecise information mainly by proximity relations. They are fuzzy counterparts of tolerance (reflexive, symmetric, but not necessarily transitive) relations and generalize similarity relations (fuzzy equivalences). The presented unification, matching and anti-unification algorithms operate in languages whose signatures tolerate mismatches in function symbol names, arity, and in the arguments order (so called full fuzzy signatures).

One of the challenges in these algorithms is the non-transitivity, that forces a very specific treatment of variable elimination in unification and matching, and working with symbol neighborhoods in anti-unification. Another challenge is the arity mismatch, which requires to explicitly specify the related argument pairs for proximal symbols. These relations between argument pairs affect the algorithms. In the tutorial, we discuss how these challenges can be addressed.

Short Bio:

Ioana Cleopatra Pau is working as a research assistant at the Research Institute for Symbolic Computation of the Johannes Kepler University Linz, Austria. Her area of interest is computational logic and natural-language generation. Her current research focuses on symbolic techniques for proximity and similarity relations, such as unification, matching, anti-unification and constraint solving.