Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra

Подождите немного. Документ загружается.

Completeness of automaton mappings 103

(Note that f = g can hold.) Thus we have the following four equivalence classes with respect

to σ

= {F

(et)

(non ◦ vel)

},K

= {F

(eq)

},K

= {F

)

},K

= {F

)

All functions of K

are not contained in neither Lin nor in Sd. The functions of K

, K

and

do not belong to Mon, T

and T

, respectively.

Now let M be a σ

-complete set. Then M contains at least one element of each of the

classes K

, K

and K

.ThusM



is not contained in any of the maximal subalgebras

, T

,Lin,SdandMonofP

. By Theorem 2.14 (1), M



is complete in P

. Hence F

(non)

can be generated by the elements of M .SinceM is σ

-complete, we can generate at least

one element of any equivalence class with respect to σ

.ButusingF

(non)

, we can generate

the other element (if it is diﬀerent), too. Thus M can generate any sequential function, i.e.,

M is complete.

Obviously, if M is complete, then it is σ

-complete, too.

(2) We note that F

(non)

is dual to itself, i.e., the equivalence class of F

(non)

only consists

of this function. Thus any σ

-complete set contains F

(non)

. As above we can prove the

completeness of any σ

-complete set. 2

From Theorem 4.13 we immediately obtain the following result on the algorithmic aspect.

4.14 Corollary

(1) There is no algorithm which decides the σ

-completeness of a ﬁnite set.

(2) There is no algorithm which decides the σ

-completeness of a ﬁnite set.

5 Metric completeness

In this section we change the concept of equivalence. We do not consider equivalence of

functions, but equivalence of sets of functions. We start with the formal deﬁnition.

5.1 Deﬁnition For F ∈F

and G ∈F

,wedeﬁne

d(F, G)=

if and only if F (p)=G(p) for all p with |p|≤t − 1and

F (p



) = G(p



)forsomep



with |p



| = t

The easy proof of the following lemma is left to the reader.

5.2 Lemma For any m ∈ N, d is a distance on F

5.3 Deﬁnition M ⊆Fand M



⊆Fare called metrically equivalent if, for any t ∈ N and

any two sequential functions F ∈ M and F



∈ M



, there are sequential functions G ∈ M



and G



∈ M such that

d(F, G) ≤

and d(F



) ≤

Again, it is easy to prove that the following statement holds.

104 J. Dassow

5.4 Lemma The metric equivalence is an equivalence relation on the powerset of F.

5.5 Example For F ∈Fand i ∈ N,letF

be deﬁned by

(p)=



F (p)if|p|≤i

F (q



if |p| >i, p= q





, |q



| = i, |q



| = n

Further we deﬁne

Q = {F

| F ∈F,i∈ N}.

Obviously, Q is a proper subset of F, and it is easy to see that Q is metrically equivalent to

Note that Q forms a subalgebra and that Q is not ﬁnitely generated. The last fact can

be seen as follows. If M is a ﬁnite subset of Q, then there is a number i such that ϕ

= k

for all G ∈ Mand all j>i.Thenϕ

= k

for j>ialso holds for any sequential function

generated by M. However, this property is not valid for Q.

We now deﬁne metric completeness.

5.6 Deﬁnition M ⊂Fis called metrically complete if and only if [M] is metrically equiva-

lent to F.

In the deﬁnition of -completeness of a set M where  is some equivalence relation, we have

required that, for any sequential function F ∈F,[M] contains a function equivalent to F .In

case of metric completeness, we require that, for any sequential function F and any t ∈ N,[M]

contains a sequential function G with d(G, F ) < 1/t. Thus we replace equivalence by small

distance. Thus it is natural to study metric completeness in connection with completeness

with respect to equivalence relations. Furthermore, we shall see that metric completeness is

nearly related to σ

-completeness for t ∈ N.

5.7 Theorem There is no algorithm which decides whether or not a ﬁnite set is metrically

complete.

Proof The proof can be given by small modiﬁcations of the proof of Theorem 2.13. 2

We now discuss the corresponding concept of maximal subalgebras and its use as a com-

pleteness criterion. We start with the deﬁnition of metric maximality.

5.8 Deﬁnition A subalgebra M ⊂Fis called metrically maximal if

• M is not metrically complete and

• M ∪{F } is metrically complete for any F ∈F.

5.9 Theorem

(1) Any metrically maximal subalgebra of F is σ

-maximal for some t ∈ N.Fort ∈ N,any

-maximal subalgebra of F is a metrically maximal subalgebra.

(2) The set of all metrically maximal subalgebras of F has the same cardinality as N.

Completeness of automaton mappings 105

(3) M is metrically complete if and only if M is not contained in any metrically maximal

subalgebra of F.

Proof (1) Let M be a metrically maximal subalgebra of F. Then there is a function F ∈F

and a number t ∈ N such that d(F, G) ≥ 1/t for any function G ∈ M .HenceM is not

-complete. Thus M is contained in a σ

-maximal subalgebra N .IfM ⊂ N, then there is a

sequential function H ∈ N \M. Hence [M ∪{H}] ⊆ N. Since, obviously, N is not metrically

equivalent to F, this contradicts the metric maximality of M. Therefore M = N and the

ﬁrst statement of (1) has been shown.

Now let M be a σ

-maximal subalgebra for some t ∈ N. First we note that M contains

any function F where

((x

,...,x

), (x

,...,x

),...,(x

,...,x

)) = x

for some k and i ≤ t. If we assume the contrary, then [M ∪{F }] is a subalgebra of F with

M ⊂ [M ∪{F }]. (5.1)

Moreover, M and [M ∪{F}]areσ

-equivalent since using F we cannot change the behaviour at

the ﬁrst t moments. Hence [M ∪{F }]andF are not σ

-equivalent. Taking into consideration

(5.1) we get a contradiction to the deﬁnition of σ

-maximality.

Thus M contains the functions F

∈F

, F

∈F

and F

∈F

with

((x

), (x

),...,(x

)) =



if i ≤ t,

sh(x

)ifi>t,

,...,x



if i ≤ t,

i−1

if i>t,

((x

), (x

),...,(x

)) =



if i ≤ t,

if i>t.

Now let F be an arbitrary function not in M .Then[M ∪{F }]isasubalgebraσ

-equivalent

to F. Therefore, [M ∪{F}] contains sequential functions G

and G

such that

((x

), (x

),...,(x

)) = sh(x

)fori ≤ t,

,...,x



0ifi =1,

i−1

if i ∈{2, 3,...,t}.

Then the functions

),F

)) and F

(p),F

(p))

belong to [M ∪{F }] and coincide with F

(sh)

and F

(id;1)

. Therefore, [M ∪{F }]=F which

proves that [M ∪{F}] is metrically equivalent to F. Hence M is metrically maximal.

(2) follows from (1) and Theorem 3.10.

(3) We prove that M is not metrically complete if and only if is contained in some

metrically maximal subalgebra.

106 J. Dassow

Assume that M is not metrically complete. Then there is a function F ∈Fand a number

t ∈ N such that d(F, G) ≥ 1/t for any function G ∈ [M]. Thus M is not σ

-complete. By

Theorem 3.9, there is a σ

-maximal subalgebra N with M ⊆ N.By(1)N is metrically

maximal, too. Thus M is contained in a metrically maximal subalgebra.

The converse statement is obvious. 2

We now combine the notions of metric completeness and σ

-completeness.

5.10 Deﬁnition AsetM is called 1-metrically Kleene-complete,if[M ] is metrically equiv-

alent to a σ

-algebra.

By this deﬁnition we require that M is 1-metrically Kleene-complete if, for any regular

set R and any t ∈ N,[M] contains a function F such that there is a function G which accepts

R and satisﬁes d(F, G) < 1/t. It is natural to modify the concept such that the metric does

not work on the functions but on the regular sets.

5.11 Deﬁnition For R ∈ ({0, 1}

)

and Q ∈ ({0, 1}

)

, we deﬁne



(R, Q)=

if and only if p ∈ R if and only if p ∈ Q for all p with |p|≤t − 1and



∈ R ∪ Q and p



/∈ R ∩ Q for some p



with |p



| = t

5.12 Lemma For any n ∈ N, d



is a metric on the powerset of ({0, 1}

)

5.13 Deﬁnition M is called 2-metrically Kleene-complete iﬀ, for any regular set R and any

integer t ∈ N, there is a sequential function F in [M] which accepts a set Q with d(R, Q) ≤ 1/t.

The following theorem relates the two notions of metric Kleene-completeness to each

other.

5.14 Theorem M is 1-metrically Kleene-complete if and only if M is 2-metrically Kleene-

complete.

Proof Let M be 1-metrically Kleene-complete. Let R be an arbitrary regular set and t an

arbitrary element of N.SinceM is 1-metrically complete, [M] contains a sequential function

F such that there is sequential function G which accepts R by Y for some Y ⊂{0, 1} and

satisﬁes d(F, G) < 1/t.LetQ be the set accepted by F by Y . Obviously, d



(R, Q) < 1/t.

Thus, for any R and any t, there is a sequential function F ∈ [M] which accepts a regular

set Q such that d



(R, Q) < 1/t, i.e. M is 2-metrically Kleene-complete.

In a similar way one proves the converse statement. 2

5.15 Theorem

(1) There is no algorithm which decides the 1-metric Kleene-completeness of a ﬁnite set.

(2) There is no algorithm which decides the 2-metric Kleene-completeness of a ﬁnite set.

Proof (1) It is easy to see that 1-metrically Kleene-complete set M is metrically complete

if and only if M contains sequential functions F and G with F/∈ M

and G/∈ M

.Thus

the decidability of 1-metric Kleene-completeness would imply the decidability of Kleene-

completeness in contrast to Theorem 4.10.

(2) follows from (1) and Theorem 5.14. 2

Completeness of automaton mappings 107

References

[1] V. A. Buevic, Construction of a universal bounded-determined function with two input

variables, Probl. kibernetiki 15 (1965).

[2] V. A. Buevic, On the algorithmic undecidability of the A-completeness of bounded-

determined mappings, Mat. Zametki 6 (1972), 687–697 (in Russian).

[3] V. A. Buevic, On the τ-completeness in the class of automaton mappings, Dokl. Akad.

Nauk 252 (1980), 1037–1041 (in Russian).

[4] G. N. Blochina, W. B. Kudrjavcev, and G. Burosch, Ein Vollst¨andigkeitskriterium bis auf

eine gewise

Aquivalenzrelation f¨ur eine verallgemeinerte Postsche Algebra, Publicationes

Math. 20 (1973), 141–152.

[5] J. Dassow, Kleene-Mengen und Kleene-Vollst¨andigkeit. EIK 10 (1974), 287–295.

[6] J. Dassow, Kleene-Vollst¨andigkeit bei stark-deﬁniten Ereignissen. EIK 10 (1974), 399–

405.

[7] J. Dassow, Kleene-Mengen und trennende Mengen, Math. Nachr. 74 (1976), 89–97.

[8] J. Dassow, Some remarks on the algebra of automaton mappings, in: Proc. Symp. Fun-

damentals of Computation Theory (M. Karpinski, ed.), Lecture Notes in Comput. Sci.

56, Springer, 1977, 78–83.

[9] J. Dassow, Ein modiﬁzierter Vollst¨andigkeitsbegriﬀ in einer Algebra von Automatenab-

bildungen, Habilitationsschrift, Universit¨at Rostock, 1978.

[10] J. Dassow, On the congruence lattice of algebras of automaton mappings, in: Proc.

Finite Algebras and Multiple-Valued Logic (B. Csakany, ed.), Colloq. Math. Soc. Janos

Bolyai 28, North-Holland, 1979, 161–182.

[11] J. Dassow, Completeness Problems in the Structural Theory of Automata,Akademie-

Verlag, Berlin, 1981.

[12] F. Gecseg and I. Peak, Algebraic Theory of Automata, Budapest, 1972.

[13] V. V. Gorlov, On congruence relations on closed Post classes, Mat. Zametki 13 (1973),

725–736 (in Russian).

[14] T. Hikita and I. G. Rosenberg, Completeness of uniformly delayed operations, in: Struc-

tural Theory of Automata, Semigroups, and Universal Algebra, NATO Adv. Study Inst.

Ser. C, Kluwer, Dordrecht, 2005, 109–147.

[15] J. Hoˇrejˇs, Durch endliche Automaten deﬁnierte Abbildungen, Probleme der Kybernetik

6 (1977), 285–297.

[16] S. V. Jablonskij, G. P. Gawrilow, and W. B. Kudrjawzew, Boolesche Funktionen und

Postsche Klassen, Berlin, 1970.

[17] C. C. Kleene, Introduction to Metemathematics, Amsterdam, 1967.

108 J. Dassow

[18] N. E. Kobrinski and B. A. Trachtenbrot, Einf¨uhrung in die Theorie der endlichen Au-

tomaten, Berlin, 1967.

[19] M. I. Kratko, The algorithmic undecidability of the completeness problem for ﬁnite

automata, Dokl. Akad. Nauk 155 (1964), 35–37 (in Russian).

[20] V. B. Kudryavtsev, On the cardinality of the set of precomplete sets of some functional

systems related to automata, Probl. kibernetiki 13 (1965), 45–74 (in Russian).

[21] V. B. Kudryavtsev, S. V. Alesin, and A. S. Podkolsin, Elements of the Theory of Au-

tomata, Moscow, 1978 (in Russian).

[22] D. Lau, Kongruenzen auf gewissen Teilklassen von P

k,l

, Rostock. Math. Colloq. 3 (1977),

37–44.

[23] A. A. Letichevsky, Criteria for the completeness of a class of Moore automata. Materi-

ali nauchnych seminarov po teoret. i prikladn. voprosam kibernetiki 2 (1963), 1–39 (in

Russian).

[24] M. Steinby, Algebraic classiﬁcations of regular tree languages, in: Structural Theory of

Automata, Semigroups, and Universal Algebra,NATOAdv.StudyInst.Ser.C,Kluwer,

Dordrecht, 2005, 381–432.

[25] B. Thalheim,

Uber ein Vollst¨andigkeitskriterium f¨ur eine Klasse von Automaten (ein-

stellige Approximationsautomaten), Rostock. Math. Kolloq. 18 (1981), 99–111.

Completeness of uniformly delayed operations

Teruo HIKITA

Department of Computer Science

Meiji University

1-1-1 Higashimita

Tama-ku, Kawasaki 214-8571

Japan

Ivo G. ROSENBERG

∗

D´epartement de math´ematiques et de statistique

Universit´e de Montr´eal

C.P. 6128, Succursale Centre-ville

Montr´eal, Qu´e., H3C 3J7

Canada

Abstract

The paper reports on progress toward an eﬀective completeness criterion for uniformly

delayed multiple-valued combinatorial circuits. In view of previous work by Hikita and

Nozaki, and Hikita it suﬃces to study periodic closed spectra. The main tool is the

use of polyrelations and certain constructions on polyrelations developed by Hikita and

Mili˘ci´c. We were able to restrict the search to unary polyrelations and three types of

binary polyrelations ρ =(ρ

,ρ

,...):

(1) period 2

, ρ

bounded order, ρ

m−1

its converse and ρ

= ι

:= {(a, a) | a ∈ k}

otherwise,

(2) every nonempty ρ

= {(a, s

(a)) | a ∈ k} where s

is a permutation of k;the

permutations are interrelated,

(3) components are either (i) all equivalence relations on k or (ii) all central or equal

to k

. In both cases they have strong properties in terms of intersecting cliques.

1 Introduction

This paper reports on progress toward an eﬀective general completeness criterion for uni-

formly delayed k-valued combinatorial circuits (this and other rather technical concepts

are fully explained in Section 2). In a historical retrospective, the topic was introduced

rather early by Kudryavtsev in 1960 who deﬁned the various basic concepts and gave an

eﬀective completeness criterion for uniformly delayed binary circuits based on precomplete

∗

Research partially supported by CRSNG Canada grants DGP 5407 and by JSPS Japan fellowship programs

1991 and 2003.

109

V. B. Kudryavtsev and I. G. Rosenberg (eds.),

Structural Theory of Automata, Semigroups, and Universal Algebra, 109–147.

110 T.HikitaandI.G.Rosenberg

classes [Ku60, Ku62]. For ordinary non-delayed circuits and logic such a criterion was given

by Post [Po21] for k =2,Iablonskiˇı [Ia58] for k = 3, and the second author for k>3

[Ro65, Ro70, Ro77]. Some of Kudryavtsev’s results were rediscovered by Loomis [Lo65].

Other completeness aspects for delayed circuits were studied by Biryukova and Kudryavtsev

[BK70]. After this early Russian start the focus moved to Japan where Nozaki and his school

took up and expanded the study of multiple-valued delayed circuits, to the extent that dur-

ing the past 33 years all papers in this domain (with the lone exception of [MRR78]) were

published by the Japanese school. For uniformly delayed circuits the breakthrough came in

Hikita and Nozaki’s 1977 paper [HN77] which reduced the problem to three more manageable

types. The ﬁrst case (type A) is directly solved by the primality criterion [Ro65, Ro70] while

the third case (type C) was solved by Hikita in 1976 [Hi81b]. Meanwhile Hikita also com-

pletely classiﬁed the ternary case [Hi78]. The relational theory for uniformly delayed circuits

was partly given by Hikita [Hi81a] and fully by Mili˘ci´c [Mi84, Mi88]. It is based on inﬁnite

sequences ρ =(ρ

,ρ

,...) of relations of the same arity on the alphabet k := {0, 1,...,k−1}.

For such a sequence, called a polyrelation,ann-ary operation f with nonnegative integer de-

lay δ carries ρ

into ρ

i+δ

for all i ≥ 0. This concept replaces the preservation of a single

relation which is the basic concept in the nondelayed case.

We report on the results for the remaining case of periodic spectra (type B) and the

corresponding periodic polyrelations. The precomplete classes obtained are rather exceptional

as witnessed by the fact that they are determined by at most binary polyrelations. We

have succeeded in limiting them to unary periodic polyrelations and to binary polyrelations

ρ =(ρ

,ρ

,...)ofperiodp of the following three types:

(1) p =2

(m>0), ρ

is a bounded partial order ≤ on k, ρ

m−1

is ≥ and ρ

= ι

:= {(a, a) |

a ∈ k} for 0 <i<2

, i =2

m−1

. Each of these polyrelations gives a precomplete class

[Ku60, Ku62].

(2) Every nonempty component is of the form {(a, s(a)) | a ∈ k} where s is a permutation

of k. The permutations involved are intimately linked and the case is essentially one of

a group-theoretical nature.

(3) All components ρ

,...,ρ

p−1

are either (i) equivalence relations = ι

or (ii) all are central

or equal to k

(a binary symmetric relation σ is central if ι

⊂ σ ⊂ k

and c ×k ⊆ σ for

some c ∈ k). In both cases we have strong properties in terms of intersecting cliques.

Although the uniformity and the completeness concepts are open to discussion as to their

practicality and relation to reality, the authors feel that this study is justiﬁed as a ﬁrst step

in this direction, and perhaps even more by the richness of the mathematical theory involved.

The ﬁnancial support provided to the second author in 1990 by S.T.A. Japan Research

Award, by NSERC Canada operating grant A-9128, and by FCAR Qu´ebec Subvention

d’´equipe Eq-0539, and the 1991 and 2003 J.S.P.S., Japan, grants as well as the hospitality

of Universit´edeMontr´eal, Meiji University (Tokyo), Electrotechnical Laboratory (Tsukuba)

and Tsukuba College of Technology is gratefully acknowledged.

2 Preliminaries

2.1 Switching circuits are built from basic hardware components which we shall henceforth

call gates. For simplicity each gate (Fig. 1) is a device with a single output and n inputs

Completeness of uniformly delayed op erations 111

where n is a positive integer. The gate receives and emits signals in the same ﬁnite alphabet

which will be identiﬁed with k := {0, 1,...,k − 1}. If the signal on the i-th input is x

(i =1,...,n) then the response of the gate is a unique output signal determined by the

n-tuple (x

,...,x

) ∈ k

. Denoting this signal by x

= f (x

,...,x

)wecandescribethe

functioning of a gate by an n-ary operation f on k (i.e., a map f : k

→ k). Thus each gate

carries an operation f describing its behavior (also called a logic or switching function or a

connective). Denote by O

(n)

the set of all n-ary operations on k and set O :=



∞

n=1

(n)

In reality, the physical time dependent signal x

(t)onthei-th input (1 ≤ i ≤ n)and

the output signal x

(t) are continuous functions of time t. The real situation may be rather

complex and so we approximate it by assuming that there are time invariant delays δ

,...,δ

such that for all t ≥ max(δ

,...,δ

)

(t)=f(x

(t − δ

),...,x

(t − δ

)) (2.1)

where x

(t)aremapsfrom[0, ∞)intok (i =1,...,n). Thus (2.1) means that the present

output depends on the value of the i-th input δ

time units ago (i =1,...,n). Such gates are

called delayed input devices (or d-modules). For simplicity we assume that all δ

belong to the

set N = {0, 1,...} of nonnegative integers. The integrality assumption follows the connections

to automata theory; however the delays of real gates are at best known approximately and,

moreover, may depend on extremal conditions, e.g. the temperature, or on the age of the

circuit. In this paper we go even further and assume that δ

= ··· = δ

. This restriction,

common to most engineering literature, is far reaching, substantially limiting the composition

and causing the theory to be nonalgebraic. Such a gate is called a uniformly delayed device

(or k-module), and it is fully described by the pair (f,δ) called an operation (or function)

with delay δ on k.Thesetofalln-ary operations with delay on k is U

(n)

:= O

(n)

× N,and

U := O×N is the set of all operations with delay on k.

2.2 Switching circuits are obtained from a collection of gates by attaching outputs of certain

gates to inputs of other gates. Again for simplicity we consider only the combinatorial (i.e.

feedback-free) switching circuits. The simplest case is the following. We have a gate F

described by (f,δ) ∈U

(n)

and n gates G

determined by (g

,δ

) ∈U

)

, i =1,...,n.Ifwe

attach the single output of G

to the i-th input of F , i =1,...,n, the resulting tree-like circuit

has m := m

+···+m

external inputs and realizes the operation h = f ⊗(g

,...,g

) ∈O

(m)

deﬁned by setting

h(x

,...,x

) ≈ f(g

,...,x

),...,g

m−m

,...,x

))

112 T.HikitaandI.G.Rosenberg

where ≈ means that the equation holds for all x

,...,x

∈ k. The accumulated delays are

(δ + δ

,...,δ+ δ

). It follows that the circuit will have a uniform delay

if and only if δ

= ···= δ

. In this paper we restrict ourselves to uniformly delayed circuits

and so we only accept the ⊗-composition (f ⊗(g

,...,g

),δ+ δ



)withF := (f,δ) ∈U

(n)

and

:= (g

,δ



) ∈U

)

(i =1,...,n). Denote the resulting circuit by F ⊗ (G

,...,G

Suppose we have a circuit in the shape of a rooted tree with gates at the vertices distinct

from the leaves and external inputs (not necessarily pairwise distinct) at the leaves and let

the sum of the delays be constant on each branch from a leaf to the root. Working from

the leaves to the root we can express the delayed function represented by the tree through

repeated composition (e.g. in the situation of Fig. 2 the function is (f ⊗(g⊗(h, i),j), 4). Thus

the ⊗-composition suﬃces for the description of functions associated with acyclic circuits

yielding uniform delays.

It should be stressed that the ⊗-composition can be performed if and only if the inside

functions have an identical delay. This restriction diﬀerentiates our structure from universal

algebra and propositional calculus of most logics which allow unrestricted composition. The

structure may be described by a suitable partial algebra, but as this fact seems to have little

impact on completeness, we should not dwell on it.

2.3 In what follows we need the projection (trivial operation or selector). This is an n-ary

operation e

on k such that e

,...,x

) ≈ x

(1 ≤ i ≤ n). Denote by J := {e

| 1 ≤ i ≤

n<ℵ

} the set of all projections. For a subset V of U deﬁne V  as the least subset of U

containing F ⊗ (G

,...,G

) whenever F ∈V  and G

∈ V ∪ (J ×{0})(i =1,...,n)(it

being understood that G

,...,G

have the same delay). We have added J ×{0} to allow

arbitrary changes of variables (i.e. for F ∈V  the set V  also contains each F



obtained

from F by permuting (i.e. exchanging or switching) or identifying (fusing) the variables).

Clearly V →V  is a closure operator on U. The subsets V of U satisfying V = V 

are called closed uniform sets. A closed uniform set containing J ×{0} is a uniform clone.

We say that V ⊆Uis complete if to every f ∈Othere is δ ∈ N such that (f,δ) ∈V .

This was introduced for k = 2 by Kudryavtsev [Ku60, Ku62] (as completeness in the second

sense) and captures the possibility of constructing each operation with some—possibly very

large—delay. The object of this paper is to give a universal completeness criterion. Before

embarking into the technical details we comment on the relation between our model and