Tolerance-Based Techniques for Approximate
Reasoning
Temur Kutsia1 , Mircea Marin2 , Mikheil Rukhaia3
1RISC, Johannes Kepler University Linz,
2
West University of Timişoara,
3I.Vekua Institute of Applied Mathematics, I.Javakhishvili Tbilisi State University

Introduction

Tolerance Relation• Reasoning with incomplete, imperfect information isvery common in human communication.
• Its modeling is a highly nontrivial task, and remains
an important issue in applications of artificial intelligence.
• Various notions are associated to such information:
uncertainty, imprecision, vagueness, fuzziness.
• Different methodologies have been proposed to deal
with them: default logic, probability, fuzzysets, etc.

• In the original version, tolerance relations were crisp: 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.
• For a set S, a mapping R from S × S to the real interval [0, 1] is called a binary fuzzy relation on S.
• By fixing a number λ, 0 ≤ λ ≤ 1, we can define a crisp counterpart of R, named the λ-cut of R on S, asRλ := {(s1 , s2 ) | R(s1 , s2 ) ≥ λ}.
• A fuzzy relation R on a set S is called a proximity relation (also known as a fuzzy tolerance relation) on S
iff it is reflexive and symmetric in the following sense:
Reflexivity: R(s, s) = 1 for all s ∈ S;
Symmetry: R(s1 , s2 ) = R(s2 , s1 ) for all s1 , s2 ∈ S.

• For many problems in this area, exact equality isreplaced by its approximation.

• A λ-cut of a proximity relation is a crisp tolerance relation.

• Idea by Poincaré: in physical world, accumulationof measurement errors lead to the violation of transitivity of equality (in contrast to the ideal mathematical world).

• A proximity relation (on S) is called a similarity relation (also known as a fuzzy equivalence relation) (onS) iff it is transitive in the following sense:• Example: experiment with small weights inmeasuring the differential sensitivity (Fechner’sweight-lifting experiment)• A λ-cut of a similarity relation is a crisp equivalence relation.

• A T-norm ∧ is an associative, commutative, non-decreasing binary operation on [0, 1] with 1 as the unit element.

Transitivity: R(s1 , s2 ) ≥ R(s1 , s) ∧ R(s, s2 ) for any s1 , s2 , s ∈ S.

crisp tolerance

proximity (fuzzy tolerance)

crisp equivalencesimilarity (fuzzy equivalence)

11g
==10g

6=

12g

Objectives
Problem Statement

Develop algorithms to solve a proximity and similaritybased (crisp or fuzzy) set unification problems.
Investigate the algorithms, analyze
them, and prove their properties.

The project addresses the problem of developing novelsymbolic techniques for supporting automated or semiautomated reasoning activities in theories modulo proximity and similarity relations.

Aims
We aim at designing, analyzing, and implementing specific algorithms and procedures for each of the major reasoning activities in theories with proximity and similarity
relations.

Develop an algorithm to solve a proximity andsimilarity-based optimal unification problem.

Solving
unification and constraint solving

Develop approximate inference methods with proximity and similarity
relations, involving set constraints.

ComputingConstrained rewriting, simplification

Extend Rewriting Logic by techniques
for proximity and similarity relations.

Computation and deduction
Programming in logic withconstrained transformation rules• New algorithms and techniques for unification,
matching, rewriting, and inference in fuzzy tolerance
and fuzzy equivalence settings.
• These algorithms will be usually applicable to (orhave analogs for) their crisp counterparts.
• Implementation of all these algorithms will befreely accessible from the project web page.
• Increase the international visibility of the project
team members.

Extend proximity and similarity-based
constrained rewriting with fuzzy regulartree language membership constraints.

Incorporate proximity and similaritybased constraints into the SMTbased theorem proving technique formulti-valued logics introduced in [1].

Proving
Formalisms for approximate reasoning

Expected Results

Develop constrained rewriting techniques
for proximity and similarity relations.

References[1] Carlos Ansótegui, Miquel Bofill, Felip Manyà, and Mateu Villaret. Automated theorem provers for multiple-valued logics with satisfiability
modulo theory solvers. Fuzzy Sets Syst., 292:32–48, 2016.
[2] Erik Christopher Zeeman. The topology of the brain and visual perception. In The Topology of 3-Manifolds, pages 240–248. Prentice
Hall, Englewood, N.J., 1962.
[3] Alexei B. Sossinsky. Tolerance space theory and some applications. Acta Applicandae Mathematicae, 5:137–167, 1986.
[4] Alexei B. Sossinsky. Tolerance spaces revisited I: Almost solutions. Mathematical Notes, 106(3):439–445, 2019.
[5] Hassan Aït-Kaci and Gabriella Pasi. Fuzzy lattice operations on first-order terms over signatures with similar constructors: A constraintbased approach. Fuzzy Sets Syst., 391:1–46, 2020.
[6] Giorgio Bacci, Radu Mardare, Prakash Panangaden, and Gordon Plotkin. Quantitative equational reasoning. In Gilles Barthe, JoostPieter Katoen, and Alexandra Silva, editors, Foundations of Probabilistic Programming, pages 333–360. Cambridge University Press,2021.

Contact
Acknowledgements• Email: mrukhaia@logic.at
This project was supported by Shota Rustaveli National Science Foundation ofGeorgia under the grant №FR-21-16725.

• Web: https://www.viam.science.tsu.ge/new/index.php?lang=eng&page=projects&
subpage=1