Fuzzy Approximating Metrics, Approximating Parametrized Metrics and Their Relations with Fuzzy Partial Metrics

Abstract

We generalize the concept of a fuzzy metric by introducing its approximating counterpart in order to make it more appropriate for the study of some problems related to combinatorics on words. We establish close relations between fuzzy approximating metrics in the case of special t-norms and approximating parametrized metrics, discuss some relations between fuzzy approximating metrics and fuzzy partial metrics, as well as showing some possible applications of approximating parametrized metrics in the problems of combinatorics on words.

1. Introduction

Recently, some researchers have shown interest in the use of methods and tools of classical analysis, such as metrics and topologies, in “non-traditional” areas, such as theoretical computer science, combinatorics on words, data mining, etc. In particular, different metrics describing the distance between infinite words, limits of sequences of words, and topologies on the set of infinite words were studied (see, e.g., [1]). However, usually, there are not the classical metrics that provide effective tools for these studies, but more general structures. In particular, fuzzy metrics (see, e.g., [2]) have been used for pattern recognition (see, e.g., [3]), and partial metrics (see, e.g., [4]) have been used for some theoretical computer-science-related applications (see e.g., [5]). Fuzzy fragmentary metrics [6] and parametrized metrics [7,8] have been introduced in order to measure the distance between two infinite words in a more appropriate way than ordinary metrics. In this paper, we introduce yet another generalization of a fuzzy metric, called a fuzzy approximating metric (Section 3) and, closely related with them, the approximating version of parametrized metrics (Section 4). We study the properties of fuzzy approximating metrics and approximating parametrized metrics, discuss their relations with (fuzzy) partial metrics (Section 5) and consider the applicability of these concepts for the study of the problems related to combinatorics on words (Section 6). We conclude the paper with Section 7, where some ideas for the future work in this field are discussed.

2. Preliminaries: Fuzzy Metrics

In 1951, K. Menger [9] introduced the notion of a statistical metric. This concept was carefully studied and renamed the probabilistic metric in [10]. Later, basing on the definition of a probabilistic metric, I. Kramosil and J. Michalek [2] introduced the notion of a fuzzy metric. Based on the Kramosil–Michalek definition, A. George and P. Veeramani [11,12], after some, outwardly not very significant, modifications, introduced an alternative concept known now as a GV-fuzzy metric. The informal difference between the two definitions is that in the GV-definition, a greater role is given to the fuzzy component compared to the probabilistic component, the influence of which is more noticeable in the original definition of Kramosil–Michalek. In the sequel, when dealing with fuzzy metrics, we always mean the George–Veeramani version. An interested reader can easily find counterpart of the study provided in this work for the Kramosil–Michalek fuzzy metrics.

Both definitions of the fuzzy metric rely on the concept of a t-norm. The standard source for references on t-norms is the monograph [13]. However, for the readers convenience, we give basic information about t-norms that will be needed in our work.

Definition 1. 

A t-norm is a binary operation $\ast :[0,1]\times [0,1]\to [0,1]$ on the unit interval $[0,1]$ satisfying the following conditions for all $a,b,c$:

(1tn)

∗ is monotone: $a\le b\Rightarrow a\ast c\le b\ast c$;

(2tn)

∗ is commutative: $a\ast b=b\ast c$;

(3tn)

∗ is associative: $(a\ast b)\ast c=a\ast (b\ast c)$;

(4tn)

$a\ast 1=a$.

Example 1. 

Among the most important examples of t-norms are the following four (see, e.g., [10,13]):

• Define $a\ast b:=a\wedge b$ where ∧ denotes the operation of taking minimum in [0, 1]. It is called the minimum t-norm.
• Define $a\ast b:=a·b$ be the product. This is the so called product t-norm.
• Define $a{\ast }_{L}b:=max(a+b-1,0).$ This is the well-known Łukasiewicz t-norm.
• Define $a\ast b:=\frac{a·b}{a+b-a·b}$ This is known as the Hamacher t-norm.

Remark 1. 

It is known and can be easily seen that $a\wedge b\ge a\ast b$ for every t-norm ∗. Hence, ∧ is the largest t-norm.

Definition 2 

([11]). Let X be a set and $\ast :[0,1]\times [0,1]\to [0,1]$ a continuous t-norm. A fuzzy metric on a set X is a mapping $M:X\times X\times (0,\infty )\to (0,1]$ satisfying the following axioms:

(FM1)

$M(x,y,t)=1$ if and only if $x=y$;

(FM2)

$M(x,y,t)=M(y,x,t)\forall x,y\in X,\forall t\in (0,\infty )$;

(FM3)

$M(x,z,t+s)\ge M(x,y,t)\ast M(y,z,s)\forall x,y,z\in X,\forall s,t\in (0,\infty )$;

(FM4)

$M(x,y,-):(0,\infty )\to (0,1]$ is lower semi-continuous (In the original definition in [11] $M(x,y,-):(0,\infty )\to [0,1]$ was assumed to be continuous).

In order to specify the t-norm used in the definition of a fuzzy metric, we refer to a fuzzy metric as the pair $(M,\ast )$.

Note that from axioms (FM3) and (FM1), it follows that the mapping $M(x,y,-):(0,\infty )\to [0,1]$ is non-decreasing.

In our work, we apply also the following stronger version of a fuzzy metric first introduced in [14].

Definition 3. 

A fuzzy metric M on a set X is called strong if in addition to axioms (FM1) and (FM2), the following modifications of axioms (FM3) and (FM4) are satisfied:

(FKM3^s)

$M(x,z,t)\ge M(x,y,t)\ast M(y,z,t)$ for all $x,y,z\in X$ and for all $t\in (0,\infty )$.

(FKM4^s)

$M(x,y,-):(0,\infty )\to (0,1]$ is left continuous and non-decreasing, (that is $t<s⟹$ $M(x,y,t)\le M(x,y,s),\forall x,y\in X.$).

Remark 2. 

In case we just replace axiom (FM3) by axiom (FKM3${}^s$), the resulting concept may fail to be a fuzzy metric. The simplest example of such a situation was found by A. Sapenas and S. Morillas [14]. Therefore, in order to obtain a stronger version of a fuzzy metric, one has either to add axiom (FKM3${}^s$) to the definition of a fuzzy metric (as it is done in [14]) or to replace (FM3) with (FKM3${}^s$) and ask additionally that $M(x,y,-):(0,\infty )\to (0,1]$ is non-decreasing, as we did in [15] and in this paper.

Remark 3. 

There is close relation between strong fuzzy metrics and non-Archimedean fuzzy metrics (see, e.g., [13,16]). Recall that a fuzzy metric $M:X\times X\times (0,\infty )\to (0,1]$ is called non-Archimedean if it satisfies a stronger version of the axiom (FM3), namely

$$(FM3\neg A) M(x,z,t\vee s)\ge M(x,y,t)\ast M(y,z,s)\forall x,y,z\in X,t,s\in (0,\infty )$$

Under the assumption that the function $M:X\times X\times (0,\infty )\to (0,1]$ is non-decreasing, axiom (FM3¬A) is equivalent to the axiom of a strong fuzzy metric (FKM3${}^s$). Indeed, taking in the axiom (FM3) $M(x,z,t+s)\ge M(x,y,t)\ast M(y,z,s)\forall x,y,z\in X,t,s\in (0,\infty )$$t=s$, we obtain axiom (FKM3${}^s$) $M(x,z,t)\ge M(x,y,t)\ast M(y,z,t)\forall x,y,z\in X,t,s\in (0,\infty )$ and hence (FM3¬A) ⟹ (FKM3${}^s$).

Conversely, relying on the axiom (FKM3${}^s$) and non-decreasing nature of function $M:X\times X\times (0,\infty )\to (0,1]$, we have $M(x,z,t\vee s)\ge M(x,y,t\vee s)\ast M(y,z,t\vee s)\ge M(x,y,t)\ast M(y,z,s)$, and hence (FM3¬A) ⟸ (FKM3${}^s$).

3. Fuzzy Approximating Metrics

Inspired by the works of Matthews and coauthors [4,5,17], we realized a certain inconsistency or discrepancy in our works in combinatorics on words which are based on fuzzy metrics with the actual situation. When comparing two words in practice, usually the information is not available as given at present but appears only in the process of computation. We interpret this computation as the procedure along parameter $t\in (0,\infty )$, which is along the third argument in the definition of a fuzzy metric. Under this interpretation, axiom (FM1) is too strong: given a string $x=(x_0,x_1,\dots ,x_n,\dots )$ at the stage $t\in (0,\infty )$, we have information about this string only till $\lfloor t\rfloor$th coordinate and cannot yet confirm that $M(x,x,t)=1$. On the other hand, “at the infinity” we have information about all elements of the string and, therefore, it is natural to request that ${lim}_{t\to \infty }M(x,x,t)=1$ for every $x\in X$. When comparing x and y at every step $\lfloor t\rfloor$, thus having information up to t on both strings and not knowing yet whether $x=y$, we obviously have only relation $M(x,x,t)\ge M(x,y,t)$. We view these observations as justification for the following definitions first introduced in our paper [18].

Definition 4. 

A fuzzy approximating metric on a set X is a mapping $M:X\times X\times (0,\infty )\to (0,1]$ satisfying the following axioms:

(FAM1)

$M(x,x,t)\ge M(x,y,t)\forall x,y\in X$;

(FAM2)

If $x,y\in X$ then ${lim}_{t\to \infty }M(x,y,t)=1$ if and only if $x=y$;

(FAM3)

$M(x,y,t)=M(y,x,t)\forall x,y\in X,\forall t\in (0,\infty )$;

(FAM4)

$M(x,z,t+s)\ge M(x,y,t)\ast M(y,z,s)\forall x,y,z\in X,\forall t,s\in (0,\infty )$;

(FAM5)

$M(x,y,-):(0,\infty )\to (0,1]$ is left semicontinuous for all $x,y\in X.$

Remark 4. 

Comparing Definition 4 and Definition 2, notice first that we revise axiom (FM1) by splitting it into two axioms (FAM1) and (FAM2); the intuitive meaning of this splitting is explained above. We do not revise axioms (FM2) and (FM3) that appear now as axioms (FAM3) and (FAM4) in Definition 4 since they reflect information at finite steps ${\lfloor t\rfloor }^{th}$ and hence are operating with already received information. We do not revise also axiom (FM4) that appears now as axiom (FAM5) since it is given in the global way, that is, for each specific $t\in (0,\infty )$.

From axiom (FAM4) and taking into account axiom (FAM5), we obtain

Proposition 1. 

$M(x,y,-):(0,\infty )\to (0,1]$ is a non-decreasing function and ${lim}_{t\nearrow t_0}M(x,y,t)=M(x,y,t_0).$

Patterned after Definition 3, we introduce the strong version of the fuzzy approximating metric.

Definition 5. 

A fuzzy approximating metric M on a set X is called strong if, in addition to axioms (FAM1)–(FAM3), the following modifications of axioms (FAM4) and (FAM5) are satisfied:

(FAM4^s)

$M(x,z,t)\ge M(x,y,t)\ast M(y,z,t)$ for all $x,y,z\in X$ and for all $t\in (0,\infty )$.

(FAM5^s)

$M(x,y,-):{\mathbb{R}}^{+}\to (0,1]$ is left continuous and non-decreasing, that is $t<s⟹$ $M(x,y,t)\le M(x,y,s)\forall x,y\in X.$

In the next sections of this paper, we discover close relations between approximating parametrized metrics and fuzzy approximating metrics based on some particular t-norms, discuss some connections between fuzzy approximating metrics and fuzzy partial metrics and give an example of the possible application of approximating parametrized metrics in combinatorics on words.

4. Approximating Parametrized Metrics

Many researchers use families of (pseudo)metrics, often endowed with a parameter, in order to characterize objects of their study. For example, J.F. McClendon [19] considers a disjoint collection of metric spaces, whose metrics are compatible with a given topology on the disjoint union of sets, V. Radu [20] applies families of metrics in the research of distribution functions, D. Schueth [21] in her research uses families of Rimannian metrics on simply connected manifolds, etc. On the other hand, we are aware of only a few studies in which just parametrized metrics are considered objects. Actually, the first work known to us, in which parametrized metrics appear, is a work by N. Hussein and co-authors [22]. Namely, a parametrized metric on a set X is a function $P:X\times X\times (0,\infty )\to [0,\infty )$ such that

(PM1)

$P(x,y,t)=0$ for all $t>0$ if and only if $x=y$;

(PM2)

$P(x,y,t)=P(y,x,t)$ for all $x,y\in X$ and all $t>0$;

(PM3)

$P(x,z,t)\le P(x,y,t)+P(y,z,t)$ for all $x,y,z\in X$ and all $t>0$.

Note that in the paper cited above, the authors use for this concept a very inappropriate, in our opinion, name of a parametric metric.

In the paper [8], we present a construction of a parametrized metric based on a appropriately chosen t-conorm. In this paper, in the spirit of this work, we introduce the approximating version for parametrized metrics.

Definition 6. 

Let X be a set. A mapping $P:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ is called an approximating parametrized metric on X if it satisfies the following conditions:

(APM1)

$P(x,x,t)\le P(x,y,t)\forall x,y\in X,\forall t\in (0,+\infty )$;

(APM2)

${lim}_{t\to \infty }P(x,y,t)=0$ if and only if $x=y$;

(APM3)

$P(x,y,t)=P(y,x,t)\forall x,y\in X,\forall t\in (0,+\infty )$;

(APM4)

$P(x,z,t+s)\le P(x,y,t)+P(y,z,s)\forall x,y,z\in X,\forall t\in (0,+\infty )$;

(APM5)

$P(x,y,-):(0,+\infty )\to {\mathbb{R}}^{+}$ is left semicontinuous for all $x,y\in X.$

Patterned after Definition 5, we introduce the strong version of the approximating parametrized metric.

Definition 7. 

An approximating parametrized metric P on a set X is called strong if in addition to axioms (APM1)–(APM3), the following modifications of axioms (APM4) and (APM5) are satisfied:

(APM4^s)

$P(x,z,t)\le P(x,y,t)+P(y,z,t)$ for all $x,y,z\in X$ and for all $t\in (0,\infty )$.

(APM5^s)

$P(x,y,-):(0,+\infty )\to {\mathbb{R}}^{+}$ is left continuous and non-increasing (that is $t<s⟹$ $P(x,y,t)\le P(x,y,s)\forall x,y\in X.$).

It turns out that under certain conditions, fuzzy approximating metrics and approximating parametrized metrics can be considered dual concepts. The details of this statement are revealed later in this section.

Theorem 1. 

Let $M:X\times X\times (0,\infty )\to (0,1]$ be a fuzzy approximating metric for the Hamacher t-norm and let

$$P_M(x,y,t)=\frac{1-M(x,y,t)}{M(x,y,t)}.$$

Then, $P_M:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ is an approximating parametrized metric.

Proof. 

Note first that since $M(x,y,t)>0$ for every $x,y\in X$, $t\in (0,+\infty )$ the definition of $P_M$ is correct. From Proposition 1, it follows that the function $P_M:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ is non-increasing.

Property (APM1) for $P_M$ follows directly from Property (FAM1) for $M:X\times X\times (0,\infty )\to (0,1]$.

Referring to axiom (FAM2) and recalling that by Proposition 1, ${lim}_{t\to \infty }M(x,y,t){=}_{def}a\in (0,1]$ exists for every pair $x,y\in X,$ we establish axiom (APM2) as follows:

$${lim}_{t\to \infty }{P}_M(x,y,t)={lim}_{t\to \infty }\frac{1-M(x,y,t)}{M(x,y,t)}=\frac{1-{lim}_{t\to \infty }M(x,y,t)}{{lim}_{t\to \infty }M(x,y,t)}=0$$

if and only if ${lim}_{x\to \infty }M(x,y,t)=1$, i.e., if and only if $x=y$.

Referring to axiom (FAM3), we establish property (APM3) for $P_M:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ as follows:

$P_M(x,y,t)=\frac{1-M(x,y,t)}{M(x,y,t)}=\frac{1-M(y,x,t)}{M(y,x,t)}=P_M(y,x,t)\forall x,y\in X,\forall t\in (0,+\infty )$.

To show (APM5), notice that by (FAM5)

$${lim}_{t\nearrow t_0}{P}_M(x,y,t)={lim}_{t\nearrow t_0}\frac{1-M(x,y,t)}{M(x,y,t)}=\frac{1-{lim}_{t\nearrow t_0}M(x,y,t)}{{lim}_{t\nearrow t_0}M(x,y,t)}=\frac{1-M(x,y,t_0)}{M(x,y,t_0)}=P_M(x,y,t_0)$$

and recall that $P_M(x,y,-)$ is non-increasing.

To complete the proof, we have to show that axiom (FAM4) in the case of the Hamacher t-norm for $M:X\times X\times (0,+\infty )\to (0,1]$, i.e.,

$$\frac{M(x,y,t)·M(y,z,s)}{M(x,y,t)+M(y,z,s)-M(x,y,t)·M(y,z,s)}\ge M(x,z,t+s)\forall x,y,z\in X,t,s\in (0,\infty )$$

implies property (APM4) for $P_M:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$, i.e.,

$$\begin{gathered} P_M(x,y,t)+P_M(y,z,s)=\frac{1-M(x,y,t)}{M(x,y,t)}+\frac{1-M(y,z,s)}{M(y,z,s)}\ge \\ \frac{1-M(x,z,t+s)}{M(x,z,t+s)}=P_M(x,z,t+s)\forall x,y,z\in X,\forall t,s\in (0,\infty ) \end{gathered}$$

We denote $M(x,y,t)=a, M(y,z,s)=b, M(x,z,t+s)=c$. We have to prove that

$$\frac{1-c}{c}\le \frac{1-a}{a}+\frac{1-b}{b}$$

under the assumption that

$$(\diamond )\frac{a·b}{a+b-a·b}\le c$$

Now we prove the requested inequality as follows:

$$\frac{1-c}{c}\le \frac{1-\frac{a·b}{a+b-a·b}}{\frac{a·b}{a+b-a·b}}=\frac{a+b-2·a·b}{a·b}=\frac{a-a·b}{a·b}+\frac{b-a·b}{a·b}=\frac{1-b}{b}+\frac{1-a}{a}.$$

□

In the proof of property (APM4), the crucial role is played by the inequality $(\diamond )$, where the left side of the inequality is the result obtained by the Hamacher t-norm. Noticing this, we can obtain the following corollary from the previous theorem.

Corollary 1. 

Let $M:X\times X\times (0,\infty )\to (0,1]$ be a fuzzy approximating metric for a t-norm, which is weaker (i.e., smaller) or equal to the Hamacher t-norm. Then by setting

$$P_M(x,y,t)=\frac{1-M(x,y,t)}{M(x,y,t)}.$$

we obtain an approximating parametrized metric $P_M:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$, particularly if it is a fuzzy metric for the product and Łukasiewicz t-norm.

Theorem 2. 

Let $P:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ be an approximating parametrized metric on a set X. Then, the mapping $M_P:X\times X\times (0,\infty )\to (0,1]$ defined by

$$M_P(x,y,t)=\frac{1}{1+P(x,y,t)},\forall x,y\in X,t\in (0,\infty )$$

is a fuzzy approximating metric for the Hamacher t-norm.

Proof. 

We can verify that each one of axioms (APM1)–(APM5) for P implies the validity of the corresponding condition (FAM1)–(FAM5) for the mapping P similarly as we did in the opposite direction in the proof of Theorem 1. We shall linger only on the proof of the less trivial property (FAM4) in case ∗ is the Hamacher t-norm. Explicitly, we have to prove that for all $x,y,z\in X$ and for all $t,s\in (0,\infty )$, the following inequality holds:

$$M_P(x,z,t+s)\ge \frac{M_P(x,y,t)·M_P(y,z,s)}{M_P(x,y,t)+M_P(y,z,s)-M_P(x,y,t)·M_P(y,z,s)}$$

under the assumption that

$$P(x,z,t+s)\le P(x,y,t)+P(y,z,s)\forall x,y,z\in X,\forall t,s\in (0,\infty )$$

We fix $x,y,z\in X, t,s\in (0,\infty )$, denote $P(x,z,t+s)=c, P(x,y,t)=a, P(y,z,s)=b$ and, referring to the definition of $M_P$ through P, we rewrite the provable inequality by

$$\frac{1}{1+c}\ge \frac{\frac{1}{1+a}·\frac{1}{1+b}}{\frac{1}{1+a}+\frac{1}{1+b}-\frac{1}{1+a}·\frac{1}{1+b},}$$

which, after elementary transformation comes to the accepted inequality $c\le a+b$. □

Corollary 2. 

Let $P:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ be an approximating parametrized metric and define $M_P:X\times X\times (0,\infty )\to [0,1]$ by

$$M_P(x,y,t)=\frac{P(x,y,t)}{1+P(x,y,t)}\forall x,y\in X,t\in (0,\infty ).$$

Then $M_P$ is a fuzzy approximating metric for any t-norm ∗ such that $\ast \le {\ast }_H$. In particular, it is a fuzzy metric for the product and Łukasiewicz t-norms.

Notice that from the above constructions and from Theorems 1 and 2, we have the following corollaries:

Corollary 3. 

For every approximating parametrized metric M, the equality $P_{M_P}=P$ holds.

Corollary 4. 

If $M:X\times X\times (0,\infty )\to (0,1]$ is a fuzzy metric for a t-norm ∗ such that $\ast \le {\ast }_H$ then $M=M_{P_M}$.

Remark 5. 

Note, however, that when writing $M_{P_M}=M$, the equality “forgets” the original t-norm ∗ used in the definition of the fuzzy metric (and hence such that $\ast \le {\ast }_H$ by Corollary 1) and the resulting fuzzy metric $M_{P_M}$ (by Theorem 1) is a fuzzy metric for the Hamacher t-norm ${\ast }_H$.

Corollary 5. 

Approximating parametrized metrics and fuzzy approximating metrics for Hamacher t-norms are equivalent concepts.

One can easily modify the proofs of Theorems 1 and 2 and their corollaries for the case of strong fuzzy approximating metrics and strong approximating parametrized metrics. Namely, the following statements hold:

Theorem 3. 

Let $M:X\times X\times (0,\infty )\to (0,1]$ be a strong fuzzy metric for the Hamacher t-norm and let

$$P_M(x,y,t)=\frac{1-M(x,y,t)}{M(x,y,t)}.$$

Then, $P_M:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ is a strong approximating parametrized metric.

Theorem 4. 

Let $P:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ be a strong approximating parametrized metric on a set X. Then, the mapping $M_P:X\times X\times (0,\infty )\to (0,1]$ defined by

$$M_P(x,y,t))=\frac{1}{1+P(x,y,t)},\forall x,y\in X,t\in (0,\infty )$$

is a strong fuzzy approximating metric for the Hamacher t-norm.

Corollary 6. 

Strong approximating parametrized metrics and strong fuzzy approximating metrics for Hamacher t-norms are equivalent concepts.

Patterned after the definition of an ultrametric, a mapping $M:X\times X\times (0,\infty )\to (0,1]$ satisfying properties (APM1), (APM2), (APM3), (APM5) of the Definition 6 and the following stronger version of the property (APM4)

$$\left(\mathrm{APM}{4}^{\mathrm{u}}\right)P(x,z,t+s)\le P(x,y,t)\wedge P(y,z,s)\forall x,y,z\in X,\forall t,s\in (0,+\infty )$$

is called an approximating parametrized ultrametric.

The following theorem shows that approximating parametrized ultrametrics correspond to fuzzy approximating metrics for the minimum t-norm.

Theorem 5. 

If $M:X\times X\times (0,+\infty )\to (0,1]$ is a fuzzy approximating metric for the minimum t norm, then by setting $P_M(x,y,t)=\frac{1-M(x,y,t)}{M(x,y,t)}$, we obtain an approximating parametrized ultrametric $P:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$. Conversely, given an approximating parametrized metric $P:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$, by setting $M_P(x,y,t)=\frac{1}{1+P(x,y,t)}$, we obtain a fuzzy approximating metric for the minimum t-norm.

Proof. 

Obviously, we have to prove that condition $\left(\mathrm{APM}{4}^{\mathrm{u}}\right)$ for a $P:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ is equivalent to axiom (FAM4) in the case of comparing them with the minimum t-norm. In the other way stated, by using notations $M(x,y,t)=a$, $M(y,z,t)=b$, $M(x,z,t)$, we have to prove that

$$a\vee b\ge c⟹\frac{1}{1+c}\ge \frac{1}{1+a}\wedge \frac{1}{1+b}⟹\frac{1-a}{a}\wedge \frac{1-b}{b}\le \frac{1-c}{c}$$

for $a,b,c\in (0, 1]$. However, to see this, just assume that $a\le b$. □

5. Fuzzy Approximating Metrics Versus Fuzzy Partial Metrics

Partial metrics were introduced in 1994 by Matthews [4], and now they are the focus of interest for some mathematicians and theoretical computer scientists, see, e.g., the survey [5].

Basing on the concept of a partial metric, V. Gregori, J-J. Minana and D. Miravet [23] introduced the concept of a fuzzy partial metric, both in KM and GV versions. We rely here on the GV version of a fuzzy partial metric to compare them with our fuzzy approximating metrics.

Definition 8 

([23]). Let X be a set, ∗ a continuous t-norm and ${\mapsto }_{\ast }:[0,1]\times [0,1]\to [0,1]$ the corresponding residuum. A fuzzy partial metric on a set X is a mapping $\mathfrak{p}:X\times X\times {\mathbb{R}}^{+}\to (0,1]$ satisfying the following conditions for all $x,y,z\in X$ and all $s,t>0$:

(FPM1)

$\mathfrak{p}(x,x,t)\ge \mathfrak{p}(x,y,t);$

(FPM2)

$\mathfrak{p}(x,x,t)=\mathfrak{p}(x,y,t)=\mathfrak{p}(y,y,t)$ if and only if $x=y;$

(FPM3)

$\mathfrak{p}(x,y,t)=\mathfrak{p}(y,x,t);$

(FPM4)

$\mathfrak{p}(x,x,t){\mapsto }_{\ast }\mathfrak{p}(x,z,t+s)\ge \left(\mathfrak{p}(x,x,t){\mapsto }_{\ast }\mathfrak{p}(x,y,t)\right)\ast \left(\mathfrak{p}(y,y,s){\mapsto }_{\ast }\mathfrak{p}(y,z,s)\right);$

(FPM5)

mapping $\mathfrak{p}(x,y,-):(0,\infty )\to (0,1]$ is a lower semicontinuous function.

One can easily notice certain common features between our fuzzy approximating metrics on one side and partial and fuzzy partial metrics on the other. And this is not surprise since the idea of both approaches is the problem of evaluation of the distance between two infinite strings. Namely, in practice, the result will not be obtained as given or received at some step but will be achieved in the infinite process of comparing of these strings. However, the tools suggested for this research, that is, fuzzy approximating metrics and (fuzzy) partial metrics are essentially different. In this section, we make a preliminary comparison of fuzzy approximating metrics and fuzzy partial metrics.

We make this comparison by comparing individual axioms in the definitions in the case when x and y are infinite strings. Note first that conditions (FPM1), (FPM3) and (FPM5) are equivalent to conditions (FAM1), (FAM3) and (FAM5), respectively. So, we have to compare (FPM2) with (FAM2) and to compare (FPM4) with (FAM4).

Speaking informally, condition (FAM2) means that, if comparing strings x and y, we notice that they coincide at each step ${\lfloor t\rfloor }^{th}$ and hence ${lim}_{t\to \infty }M(x,y,t)=1$, we conclude that $x=y$. On the other hand, condition (FPM2) asks to compare values $\mathfrak{p}(x,x,t)$, $\mathfrak{p}(x,y,t)$ and $\mathfrak{p}(y,y,t)$ at each step $\lfloor t\rfloor$ and if they are equal, then conclude that $x=y$. In this case, no information about the value $\mathfrak{p}(x,x,t)$ and, specifically, of its limit at the infinity for a given $x\in X$ is specified. So, axioms (FPM2) and (FAM2) are incomparable. However, (FPM2) seems to us more flexible than (FAM2).

In order to compare (FPM4) with (FAM4), we have to fix a t-norm since they are the only axioms where the t-norm (and hence the corresponding residuum ${\mapsto }_{\ast }$) is involved. We restrict here to the case of the Łukasiewicz t-norm and the case of the minimum t-norm and the strong version of the fuzzy approximating version. Just in these cases, the comparison of the axioms becomes the most visual.

In the case of the Łukasiewicz t-norm, condition (FPM4) can be rewritten as

$$\mathfrak{p}(x,z,t+s)\ge \mathfrak{p}(x,y,t)+\mathfrak{p}(y,z,s)-\mathfrak{p}(y,y,t+s) for each t,s>0,$$

and hence if ${lim}_{t\to \infty }\mathfrak{p}(x,x,t)=1$ for each $x\in X$ we have

$${lim}_{t,s\to \infty }\mathfrak{p}(x,z,t+s)\ge {lim}_{t\to \infty }\mathfrak{p}(x,y,t)+{lim}_{t\to \infty }\mathfrak{p}(y,z,s)-1.$$

On the other hand, condition (FAM4) can be rewritten as

$$M(x,z,t+s)\ge M(x,y,t)+M(y,z,s)-1 for every t>0.$$

So although the concepts of a fuzzy partial metric and fuzzy approximating metric are independent, the concept of a fuzzy partial metric in the case of the Łukasiewicz t-norm seems more flexible than the concept of a fuzzy approximating metric.

Now, in the case of the minimum t-norm and taking into account axiom (FPM1), the “strong version”

$$\left(FPM{4}^s\right)\mathfrak{p}(x,x,t){\mapsto }_{\ast }\mathfrak{p}(x,z,t)\ge \left(\mathfrak{p}(x,x,t){\mapsto }_{\ast }\mathfrak{p}(x,y,t)\right)\ast \left(\mathfrak{p}(y,y,t){\mapsto }_{\ast }\mathfrak{p}(y,z,t)\right)$$

of the axiom $\left(FPM4\right)$ can be rewritten as

$$\mathfrak{p}(x,z,t)\ge \mathfrak{p}(x,y,t)\wedge \mathfrak{p}(y,z,t)$$

and this is just the axiom $\left(FAM{4}^s\right)$ of the strong fuzzy approximating metric $M:X\times X\times (0,\infty )\to (0,1].$

6. Examples of Application of the Constructed Approximating Parametrized Metric in Combinatorics on Words

In our previous papers, we presented several approaches and constructions of fuzzy metrics [6,24], parametrized metrics [7] and fuzzy approximating metrics [18], which describe the distance between any infinite words. In these papers, we stress inappropriate numerical results for ordinary metrics on the universe of the infinite words. Here, for the evaluation of the distance between infinite words, we use a strong approximating parametrized metric constructed by means of Theorem 1 from a strong fuzzy approximating metric considered in [18].

Let X be the set of infinite words. We define a sequence

$$\{d_n\mid n\in \mathbb{N}\cup \left\{0\right\}\}$$

of metrics on X as follows. Let $x=(x_0,x_1,x_2,\dots ), y=(y_0,y_1,y_2,\dots )\in X$ and let ${\chi }_i(x,y)=0$ if $x_i=y_i$ and ${\chi }_i(x,y)=1 if x_i\ne y_i$. We define a sequence of metrics:

$${\left\{d_n(x,y)={\sum }_{i=0}^n\left(\frac{5}{6+i}+\frac{2}{3}\right){\chi }_i(x,y)\right\}}_{n\in \mathbb{N}\cup \left\{0\right\}}.$$

Based on this sequence of metrics, we construct the sequence of strong fuzzy approximating metrics in the case of the drastic t-norm $T_D$ on the set X of all infinite words:

$${\left\{{\mu }_n(x,y,t)=\frac{t-d_n(x,y)}{t+c}\vee 0\right\}}_{n\in \mathbb{N}\cup \left\{0\right\}}, \mathrm{where} c\in {\mathbb{R}}_{+}$$

Further, we define the following family of mappings:

$${\left\{M_n(x,y,t)=M_{n-1}(x,y,n)\vee {\mu }_n(x,y,t)\right\}}_{n\in \mathbb{N}\cup \left\{0\right\}}.$$

Finally, we construct a mapping $M^c:X\times X\times {\mathbb{R}}^{+}\to (0,1]$ as follows:

$$M^c(x,y,t)=\left\{\begin{array}{cc}\hfill M_0(x,y,t)& if 0<t\le 1\hfill \\ \hfill M_1(x,y,t)& if 1<t\le 2\hfill \\ \hfill M_2(x,y,t)& if 2<t\le 3\hfill \\ \hfill \dots \\ \hfill M_n(x,y,t)& if n<t\le n+1\hfill \\ \hfill \dots \end{array}\right.$$

It is provable that the mapping $M^c:X\times X\times {\mathbb{R}}^{+}\to (0,1]$ is a strong fuzzy approximating pseudometric in the case of the drastic t-norm $T_D$ (for details, see [18]). Now from Theorem 1, we define an approximating parametrized metric $P_{M^c}(x,y,t)=\frac{1-M^c(x,y,t)}{M^c(x,y,t)}$ and define

$${lim}_{t\to \infty }{P}_{M^c}(x,y,t)=\Gamma (x,y).$$

Suppose we compare three infinite words

$$x=(1^{m}000\cdots ), y=(0^{m}111\cdots )\mathrm{and}z=(0000\cdots ),$$

where $m\in \mathbb{N}$ and the symbol $0^m$ defines a string of the length m, which consists only of zeroes (similarly $1^m$, a string of ones). For a finite m, we expect that $\Gamma (x,z)<\Gamma (y,z)$, as infinite words x and z differ only at the finite positions (the first m) but coincide at all other positions. We introduce the numerical results of this approximating parametrized metric by choosing different parameters c and we also search for the change point, i.e., the length m of the prefix, where the sign for inequality $\Gamma (x,z)<\Gamma (y,z)$ changes. We start with the parameter $c=1$.

As we can see in

Table 1. The values of the approximating parametrized metric for parameter $c=1$ and various m.

m	1	370	371	50,000
$\Gamma (x,z)$	0.00003	0.00269	0.0027	0.5010
$\Gamma (y,z)$	1	0.0027	0.00269	0.00002

, for our approximating parametrized metric $P_{M^c}$, we obtain the expected value for $m\le 370$ (although the change point for our construction of approximating parametrized metric $P_{M^c}$ is not small, i.e., at $m=370$, this result means that already the first 371 positions are more important than all other infinite ones). The one number which outshines from Table 1 is $\Gamma (y,z)=1$, if $m=1$. As y and z coincide only in the first positions and differ in all others, then the approximating parametrized metric gives the value $M^c(y,z,t)=0.5$ as the first position, having half the weight. From this, we obtain that

$$\Gamma (y,z)={lim}_{t\to \infty }{P}_{M^c}(x,y,t)={lim}_{t\to \infty }\frac{1-M^c(y,z,t)}{M^c(y,z,t)}=\frac{1-0.5}{0.5}=1.$$

The increase in parameter c gives us a possibility to put smaller weights on the prefix. For small m, we obtain the expected inequality $\Gamma (x,z)<\Gamma (y,z)$, but at some point, we reach the change point (see

Table 2. The values of the approximating parametrized metric for $c=10$ and various m.

m	1	1192	1193	50,000
$\Gamma (x,z)$	0.00011	0.00838	0.00839	0.5012
$\Gamma (y,z)$	2.00458	0.00839	0.00838	0.0002

and

Table 3. The values of the approximating parametrized metric for $c=100$ and various m.

m	1	3725	3726	50,000
$\Gamma (x,z)$	0.00102	0.02683	0.02684	0.8001
$\Gamma (y,z)$	2.00729	0.02684	0.02683	0.002

). Of course, it can be fixed by increasing parameter c in perpetuity.

Another important point that can be seen in both Table 2 and Table 3 is that $\Gamma (y,z)\approx 2>1$ for $m=10$ and $m=100$ as $P_{M^c}:X\times X\times (0,+\infty )\to {\mathbb{R}}^{+}$ and

$${lim}_{t\to \infty }{M}^c(y,z,t)\approx \frac{1}{3}\mathrm{so}{lim}_{t\to \infty }{P}_{M^c}(y,z,t)\approx 2.$$

In this case, if we increase the parameter c in perpetuity, then for $m=1$, the value $P_{M^c}$ tends to ∞.

7. Conclusions

We introduced the concept of a fuzzy approximating metric; investigated close relations, depending on the choice of a t-norm, between fuzzy approximating metrics and approximating parametrized metrics; discussed relations between fuzzy approximating metrics and fuzzy partial metrics; and illustrated some possible applications of approximating parametrized metrics in the problems of combinatorics on words.

We foresee several directions, both theoretical and practical ones, in which the research started in this work can be continued:

• As the first step, we see the practical use of fuzzy approximating metrics in the problems of combinatorics on words, in particular, to study the advantages/disadvantages of approximating parametrized metrics if compared with other metric type structures, particularly those which were used in [7], by analyzing specific numerical examples.
• The second important issue to be studied is the topological structure induced by fuzzy approximating metrics. A non-triviality of this problem is caused by the fact that the “open balls” induced by fuzzy approximating metrics need not open in the topological sense (as in the situation of b-metric spaces, see, e.g., [25,26]), and this leads to different possible approaches to the study of topology-related issues.
• We also plan to study fuzzy approximating metric spaces as categories, in particular, to define, in the appropriate way, the continuity of the mappings of fuzzy approximating spaces, and to investigate their products, coproducts and other operations.
• A challenging issue would be to carry out a deeper comparative analysis (particularly from the categorical point of view) between fuzzy approximating metrics, approximating parametrized metrics and fuzzy partial metrics.