Higher-Order Pattern Unification Modulo Similarity Relations
Besik Dundua, Temur Kutsia · 2025
Read Higher-Order Pattern Unification Modulo Similarity Relations by Besik Dundua, Temur Kutsia (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13208.txt.
Introduction
Besik Dundua and Temur Kutsia merged in 2025 two traditions that rarely meet: higher-order logic and fuzzy matching. Many decisions involve abstract functions where an exact match is too strict. Their approach pairs higher-order patterns, a well-behaved fragment of higher-order terms, with similarity relations drawn from fuzzy logic. Matching then succeeds by degree rather than by yes or no.
The pair present a unification algorithm for this combined setting. They prove it always terminates, that its answers are sound, and that it finds a unifier whenever one exists. Like the crisp version, the problem is unitary: one best answer exists. Their algorithm returns the most general unifier with the highest degree of approximation. The work targets reasoning systems that must stay efficient while tolerating near matches.
Catalog record
| CREATOR | Besik Dundua, Temur Kutsia |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-13208
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Higher-Order Pattern Unification Modulo Similarity Relations Besik Dundua, Temur Kutsia Abstract The combination of higher-order theories and fuzzy logic can be useful in decision-making tasks that involve reasoning across abstract functions and predicates, where exact matches are often rare or unnecessary. Developing efficient reasoning and computational techniques for such a combined formalism presents a significant challenge. In this paper, we adopt a more straightforward approach aiming at integrating two well-established and computationally well-behaved components: higher-order patterns on one side and fuzzy equivalences expressed through similarity relations based on minimum T-norm on the other. We propose a unification algorithm for higher-order patterns modulo these similarity relations and prove its termination, soundness, and completeness. This unification problem, like its crisp counterpart, is unitary. The algorithm computes a most general unifier with the highest degree of approximation when the given terms are unifiable. 1 Introduction Approximate reasoning involves making decisions or performing inferences based on vague or imprecise information, which is often modeled using fuzzy logic. Fuzzy similarity (and proximity) relations are key tools in this type of reasoning, allowing for working with uncertain or imprecise data. Fuzzy similarity refers to the degree to which two elements or objects are alike, using a value in the range of 0 to 1, where 0 represents no similarity and 1 represents complete similarity. These relations can be used to determine how similar a new situation is to past experiences or data. This is particularly useful in scenarios where precise comparisons are impossible or where “similar enough” is acceptable. (See, e.g., [ 23 , 31 , 28 , 18 , 8 , 13 , 30 , 20 ] in the context of using similarity relations in automated approximate reasoning.) Fuzzy similarity and proximity relations have been incorporated into knowledge representation and inference processes in the area of logic programming [ 9 , 31 , 15 , 7 , 12 , 17 , 11 ] , making it possible to reason or compute with vague concepts having imprecise boundaries. It helps to deal with the ambiguity inherent in real-world data, where exact matches are rare, and allows systems to make reasonable inferences even with imprecise or incomplete information. In order for this approach to work, one needs a fundamental computational mechanism such as unification to make an “approximate inference step”. Motivated by this application, first-order unification with fuzzy relations has been investigated both from theoretical and practical points of view, see, e.g., [ 29 , 31 , 18 , 22 , 1 , 10 , 8 , 32 , 33 , 19 , 16 , 14 , 28 , 5 ] . In [ 6 ] , this technique was studied in a more general setting where the quantitative approximate information is specified using quantales, having the fuzzy quantale as a special case. The cited works focus on fuzzy reasoning and computation within a first-order framework. However, decision-making often requires higher-order reasoning across abstract layers of functions and predicates, where exact matches are rare or even unnecessary. For instance, when two functions are not identical but exhibit a high degree of similarity in behavior or output, fuzzy similarity relations would enable the system to recognize this resemblance and apply approximate reasoning for inference or prediction. This can be especially useful in fields such as natural language processing, knowledge representation, and complex decision-making systems, where human-like reasoning and the handling of uncertainty are essential. This idea is a primary motivation for our work. It is important to note that the existing higher-order fuzzy logics (e.g., [ 21 , 27 ] ) are highly expressive formalisms, but because of this expressive power, developing efficient reasoning and computational techniques for them is a significant challenge. We adopt a more straightforward approach, concentrating on the integration of established and computationally well-behaved fragments: higher-order patterns on one hand, and fuzzy equivalences expressed through minimum-T-norm-based similarity relations on the other. The first step in supporting reasoning for this integration is the development of fundamental computational techniques, such as unification, which is the subject of this paper. Our contribution. We define the notion of similarity for simply-typed lambda terms and study the unification problem for higher-order patterns à la Miller [ 24 ] . In this framework, the equality relation modulo \alpha\beta\eta -equivalence is replaced by fuzzy similarity modulo \alpha\beta\eta with the minimum T-norm (Gödel T-norm). We develop a rule-based unification algorithm for such problems and prove its termination, soundness, and completeness. The unification problem, like its crisp counterpart, is unitary, that is, any unifiable problem has a single (modulo \alpha\beta\eta -equivalence) most general unifier (mgu) with respect to fuzzy similarity using minimum T-norm. The algorithm returns such an mgu for the given terms, along with an associated approximation degree, which indicates how similar the instances of the terms are under the unifier. Importantly, the computed unifier has the maximal possible approximation degree. This degree must meet or exceed a user-defined threshold (also known as a cut value). When the threshold is set to the maximal value 1 , the algorithm computes standard (i.e., crisp) unifiers. In this case, it can be viewed as a rule-based version of the standard higher-order pattern unification algorithm. Our presentation differs from traditional accounts of higher-order pattern unification and fuzzy unification by introducing a dedicated subalgorithm for variable elimination. This design has two main benefits. First, it simplifies the termination proof. Second, it enhances modularity, making it easier to integrate alternative T-norms: only the subalgorithm requires modification in such cases. Organization. Section 2 introduces the basic notions and establishes fundamental properties. The core of the paper is Section 3 , where we define the algorithm and prove its termination, soundness, and completeness. In Section 4 , we discuss two topics: (a) the crisp counterpart of our algorithm and its relation to existing higher-order pattern unification algorithms; and (b) possible extensions using T-norms other than the minimum (Gödel) T-norm employed in this work. Section 5 concludes the paper. 2 Preliminaries Term Language. Given a set of basic types, whose elements are denoted by \updelta , simple types are constructed using the grammar \uptau::=\updelta\mid\uptau\to\uptau , where \uptau is associative to the right. The alphabet of our language consists of the set \mathcal{V} of variables and \mathcal{F} of constants. They are disjoint and countably infinite and their elements have assigned types. It is assumed that for each basic type, there is at least one function symbol (types are not empty). Variables are typically denoted by F,G,H,X,Y,Z,x,y,z,\ldots and constants by f,g,a,b,c,\ldots . The set of terms over \mathcal{F} and \mathcal{V} , denoted by \mathcal{T}(\mathcal{F},\mathcal{V}) , is defined by the grammar t::=x\mid c\mid\lambda x.t\mid(t_{1}\,t_{2}), where \lambda x.t is called an abstraction and (t_{1}\,t_{2}) is called an application . We denote terms by t,s,r . The following standard abbreviations are used: (t_{1}\,t_{2}\,t_{3}\,\cdots\,t_{n}) , n\geq 3 , for (\cdots((t_{1}\,t_{2})\,t_{3})\,\cdots t_{n}) , and \lambda x_{1},\ldots,x_{n}.t , n\geq 2 , for \lambda x_{1}.(\lambda x_{2}.(\ldots(\lambda x_{n}.t))) . A term t is said to have the type \uptau if either • t is a constant or a variable of type \uptau , • t=\lambda x.s , the variable x has type \uprho , the term s has type \upphi , and \uptau=\uprho\rightarrow\upphi , • t=(s\,r) , where the term