**INTRODUCTION**

Menger (1942) introduced the notion of a probabilistic
metric space and since then the theory of probabilistic metric spaces has developed
in many directions (Schweizer and Sklar, 1983). The idea
of Menger (1942) was to use distribution functions instead
of nonnegative real numbers as values of the metric. The notion of a probabilistic
metric space corresponds to situations when we do not know exactly the distance
between two points, but is knew probabilities of possible values of this distance.
A probabilistic generalization of metric spaces appears to be interest in the
investigation of physical quantities and physiological thresholds. It is also
of fundamental importance in probabilistic functional analysis and random differential
equations (Chang *et al*., 2001). Throughout this
study, the space of all probability distribution functions (briefly, df`s) is
denoted by:

Δ^{+} = {F: R∪(-∞, +∞)→[0,
1]: F(0) = 0 and F(+∞) = 1} |

where, F is left continuous and non decreasing on R.

Also the subset is the set:

D^{+} = {FεΔ^{+}:
*l*^{-}F (+∞) = 1} |

where, *l*^{-}f (x) denotes the left limit of the function
f at the point x, *l*^{-}f (x) = lim_{t→x} f
(t) The space Δ^{+} is partially ordered by the usual point-wise
ordering of functions, i.e., F≤G if and only if F(t) ≤G (t) for
all t in R. The maximal element for Δ^{+} in this order is
the df given by:

**Definition 1:** A mapping T: [0, 1]x[0,1→[0,1] is a continuous
t-norm if T satisfies the following conditions:

• |
T is commutative and associative |

• |
T is continuous |

• |
T (a, 1) = a for all aε(0, 1) |

• |
T (a, b)≤T(c, d) whenever a≤c and b≤d and a, b, c, d ε[0,
1] |

Two typical examples of continuous t-norm are T (a, b) = ab and T(a,
b) = min (a, b). Now t-norms are recursively defined by T^{1}
= T and T^{n} (x_{1}, …, x_{n+1}) = T (T^{n-1}
(x_{1}, .., x_{n}), x_{n+1}) for n≤2 and x_{i}
ε[0, 1] for all I ε{1, 2, .., n+1}

**Definition 2:** The t-norm T is Hadzic type if for given
εε(0, 1) there is δε(0, 1) such that:

T^{m} (1-δ, …, 1-δ)>1-ε,
mεN |

A typical example of such t-norms is T (a, b) = min (a, b).

**Definition 3:** A Menger Probabilistic Quasi-Metric space (briefly,
Menger PQM space) is a triple (X, F, T), where, X is a nonempty set, T
is a continuous t-norm and F is a mapping from XxX into D^{+}
such that, if F_{x,y} denotes the value of F at the pair (x, y),
the following conditions hold: for all x, y, z ε X, (PM1) F_{x,y}
(t) = ε_{0} (t) for all t > 0 if and only if x = y; (PM2)
F_{x,y} (t+s)≥T (F_{x, z} (t), F_{z, y} (s))
for all x, y, z εX and t, s>0.

If (X, F, T) is a Menger PQM space then (X, F^{-1}, T) is a Menger
PQM space, where, F_{x,y}^{-1} (t) = F_{x,y} (t).
Moreover, if we denote by F^{i} the probabilistic quasi-metric
in XxXx (0, ∞) given by:

F^{i}_{x,y} (t) = T (F_{x,y}
(t), F^{-1}_{x,y} (t)) |

then (X, F^{i}, T) is a Menger PQM space.

**Definition 4:** Let (X, F, T) be a Menger PM-space:

• |
A sequence {x_{n}} in X is said to be convergent to x in
X if, for every α>0 and β>0, there exists positive
integer N such that Fx_{n},x (α)>1-β whenever
n≥N. |

• |
A sequence {x_{n}} in X is called Cauchy sequence if, for
every α>0 and β>0, there exists positive integer N
such that Fx_{n},x_{m}(α)>1-β whenever,
m≥N |

• |
A Menger PM-space (X, F, T) is said to be complete if and only if
every Cauchy sequence in X is convergent to a point in X |

**Definition 5:** A sequence {x_{n}} in a Menger PM-space
(X, F, T) is called a G-Cauchy sequence if lim_{n→4} Fx_{n},x_{n+P}(t)
= 1 for each t>0 and pεN. A Menger PM-space is said to be G-complete
if and only if every G-Cauchy sequence is convergent.

**Definition 6:** A sequence {x_{n}} in a Menger PQM-space
(X, F, T) is G-Cauchy if it is G-Cauchy in the Menger PQM-space (X, F^{i},
T).

**Definition 7:** A a Menger PQM-space (X, F, T) is called G-bicomplete
if the a Menger PQM-space (X, F^{i}, T) is G-complete. In this
case, we say that F is a G-bicomplete Menger PQM-space on X.

**Definition 8:** Let (X, F, T) be a Menger PQM-space. For each p
in X and α>0, the strong α-neighborhood of p is the set N_{P}
(α) = (qεX: F_{p, q} (α)>1-α) and the strong
neighborhood system for X is the union ∪_{pεX}where,
{N_{p} (α): α>0}.

The strong neighborhood system for X determines a Hausdorff topology
for X.

**Example 1:** Let (X, d) be a quasi metric space. Let

then (X, F, min) is a Menger PQM-space.

**THE BANACH FIXED POINT THEOREM IN MENGER PQM-SPACE**

A B-contraction on a Menger PQM-space (X, F, T) is a self mapping f on
X such that there is a constant k ε (0, 1) satisfying:

The following theorem is an extension of Sehgal and Bharucha-Reid`s
theorem (1972).

**Theorem 1:** Let (X, F, T) be a G-bicomplete Menger PQM-space. Then
every B-contraction on X has a unique fixed point.

**G-BICOMPLETENESS IN NON-ARCHIMEDIAN PQM-SPACE**

**Definition 9:** If in a PQM-space (X, F, T) the triangle inequality,
(PM2) of Definition 3, is replaced by:

F_{x,y} (t)≥T (F_{x,z} (t),
F_{z,y} (t)) |

for all x, y, z εX and t>0 is called a non-Archimedian PQM-space.

**Example 2:** Let (X, d) be a quasi metric space. It is immediate
to show that (X, d) is a non-Archimedian quasi metric space if and only
if (X, F^{d}, min) is a non-Archimedian PQM-space.

**Theorem 2:** Each G-Cauchy sequence in a non-Archimedian PQM-space
(X, F, T), where, T is Hadzic type, is Cauchy sequence.

**Proof:** Since T is Hadzic type, for given ε ε
(0, 1) there is δε (0, 1) such that T^{m} (1-δ,
…, 1-δ) >1-ε, mεN.

Let (x_{n}) be a G-Cauchy sequence in the non-Archimedian PQM-space
(X, F, T). Fix εε (0, 1) and t>0 and consider n_{0}
such that for
all n≥n_{0}. Then, for all n≥n_{0} and j>0 we
have:

This shows that (x_{n}) be a Cauchy sequence in (X, F, T).

**Theorem 3:** Each bicomplete non-Archimedian PQM-space (X, F, T),
where, T is Hadzic type, is G-complete.

**Proof: **Let {x_{n}} be a G-Cauchy sequence in the non-Archimedian
PQM-space. By Theorem 3, (x_{n}) is a Cauchy sequence in (X, F,
T). Then, there exists xεX such that lim_{n→4} F^{i}x,x_{n}
(t) = 1 for all t>0. Hence, (X, F^{i}, T) is G-complete, i.e.,
(X, F, T) is G-bicomplete.

**APPLICATIONS TO THE DOMAIN OF WORDS**

Let ∑ be a nonempty alphabet. Let ∑^{∞} be the
set of all finite and infinite sequence (words) over ∑, where is
adopted the convention that the empty sequence φ is an element of
∑^{∞}.

Denote by ⊆ the prefix order on ∑^{∞}, i.e.,
x⊆⇔x is a prefix of y. For each xε∑^{∞}
denote by *l* (x) the length of x. Then *l*(x)ε(*1*,
∞) whenever ≠ φ and *l*(φ) = 0. For each x, y
ε∑^{∞} let xII y be the common prefix of x
and y. Thus, the function d_{⊆} defined on∑^{∞}H∑^{∞}
by:

d_{⊆} (x, y) = 2^{-l(xII y)},
otherwise, |

is a quasi metric on ∑^{∞}. It adopt the convention that 2^{-4}
= 0 (for more details see De Bakker *et al.* (1998)).

Let
be defined as:

• |
(0) |
= |
0, for all x, y ε ∑^{∞} |

• |
(t) |
= |
ε_{0} if x is a prefix of y and t>0 |

• |
(t) |
= |
1-2^{-l(xII y)} if x is not a prefix of y and tε(0,1) |

• |
(t) |
= |
ε_{0}(t) if x is not a prefix of y and t>1. |

**Theorem 4:** (∑^{∞}, F^{d⊆1}, min)
is a bicomplete non- Archimedian PQM-space.

**Proof:** (Romaguera *et al*., 2007).

Let
be defined as:

If t = 0, for all x, yε ∑^{∞},

if t > 0, if x is not a prefix of y, if t>0, if x is a prefix of
y, where, k>1.

**Theorem 5:** (∑^{∞}, F^{d⊆}, min) is a bicomplete
non-Archimedian PQM-space. Next, is applied Theorem 1 to the complexity analysis
of Quicksort algorithms. The following recurrence equation (Romaguera
*et al*., 2007):

is obtained in the average case analysis of Quicksort algorithms. Consider
as an alphabet ∑ the set of nonnegative real numbers, i.e., ∑
= (0, ∞). Now is associated to T the functional Φ: ∑^{∞}6∑^{∞}
given by:

for all n≥2 (if xε ∑^{∞} has length, n<∞
is wrote x: = xSUB>1x_{2}..x_{n} and if x is an
infinite word is wrote x:= x_{1}x_{2}…).

Now, is showed that Φ is a B-contractive mapping on the bicomplete
non-Archimedean. PQM-space (∑^{∞}, F^{d⊆},
min) with contraction constant 1/k.

By construction, *l* (Φ (x)) = *l* (x)+1 for all x, yε∑^{∞}
(in particular, *l* (Φ (x)) = ∞ whenever l (x) = ∞). Furthermore,
it is clear that x⊆y if and only if Φ (x) ⊆Φ(y) and consequently, Φ(xII
y)⊆Φ(x)II Φ(y) for all x, yε∑^{∞}. Hence *l* (Φ (xII y))
≤*l* (Φ (x) II Φ (y)) for all x, y ε∑^{∞}.

From the preceding observations is deduced that if x is a prefix of y,
then

and if x is not a prefix of y, then

for all t>0. Similarly,

Therefore, Φ is a B-contraction on (∑^{∞}, F^{d⊆},
min) with contraction constant 1/k. By Theorem 1, Φ has a unique
fixed point z = z_{1}z_{2}…, which is the unique solution
to the recurrence equation T, i.e., z_{1} = 0 and

for all n≥2.