Reasoning with incomplete, imperfect information is very common in human communication. Its modeling is a highly nontrivial task and remains an important issue in applications of artificial intelligence.
For many problems in this area, exact equality/equivalence is replaced by its approximation. Tolerance relations are a tool to express it, modeling the corresponding imprecise information. They are reflexive and symmetric but not necessarily transitive relations, expressing the idea of closeness or resemblance. The original idea goes back to Poincaré, who viewed tolerance as the notion of fundamental importance in distinguishing mathematics applied to the physical world from ideal mathematics.
In the original version, tolerance relations were crisp (e.g., two objects are either close to each other or not). Later, their graded counterparts appeared which led, among others, to tolerance relations in the fuzzy setting. Fuzzy tolerance is often called proximity, and its special case, fuzzy equivalence, is called similarity. The project concentrates on techniques to advance automated or semi-automated reasoning for these relations.
The techniques we plan to develop concern three major activities in mathematical reasoning: solving, computing, and proving. We develop solving algorithms (modulo proximity/similarity relations) for optimal unification problems and for constraints over fuzzy or crisp sets. These algorithms and some of the existing ones will be used to advance constrained rewriting and simplification techniques (the computing part) as well as approximate theorem proving techniques for selected fragments of logic over proximity/similarity relations (the proving part). Finally, we aim at combining computation and deduction in a single framework as it is done, e.g., in Rewriting Logic or ρLog, extending the power of such formalisms from exact to approximate setting modulo proximity and similarity.

Project members:

• Temur Kutsia (Principal Investigator)

• Mikheil Rukhaia (Coordinator)

• Mircea Marin (Key Personnel)