Proximidad entre cláusulas en programación lógica inductiva
Full text
P oximidad en e lausulas en P og amaion
Logia Indu i a
M.A. Gu ie ez Na anjo J.A. Alonso Jimenez
?
J. Bo ego Daz
Dp o. Cienias de la Compu aion e In eligenia A iial { Uni e sidad de Se illa
E{mail:
magu ie ,jalonso,jbo ego
g
ia.es
WWW:
h p://www-s.us.es/
na anjo,
jalonso,
jbo ego
g
Abs a
En es e a ulo es udiamos la idea de p oximidad en el onjun o de lausulas de un
lengua je donde dos lausulas equi alen es po subsunion se onside an la misma. La
o malizaion de p oximidad que p esen amos es a basada en una quasi{me ia (una
me ia en la que no onside amos la ondiion de sime a)
d
:
C
R
=
C
R
=
!
[0
;
+
1
℄ donde
C
=
es el espaio o ien e ob enido a pa i del onjun o de lausulas
C
p o la elaion de equi alenia basada en subsunion.
Palab as la e:
P og amai
on L
ogia Indu i a, Quasi-m
e ia
1 In o duion
En Ap endiza je Au oma io hay una eien e neesidad de o maliza el onep o de p o-
ximidad en espaios ada ez mas abs a os. En P og amaion Logia Indu i a (ILP), el
p oblema de uan ia la p oximidad en e lausulas ya ha sido es udiado on an e io i-
dad p o A. Hu hinson [4℄ y S.{H.Nienhuys{Cheng [6℄, o eiendo dis in as al e na i as de
soluion al p oblema. En ambos asos se dene p ime o una dis ania en e li e ales y luego
se usa la me ia de Hausdo pa a ob ene a pa i de es a una dis ania en e lausulas.
Es o iene dos des en a jas. Po un lado la me ia de Hausdo dep ende exlusi amen e de
los pun os ex emos ( e [1℄) y p o o o, es os li e ales se onside an aislados y en ningun
momen o se onside an las p osibles elaiones en e los li e ales de la misma lausula.
En es e a ulo, p oponemos una soluion al p oblema de uan ia la p oximidad en-
e lausulas, onside andolas omo elemen os de un en amado de elaiones a subsunion
que nos a a p e mi i aede de una lausula a o a, en ie o sen ido, p o el amino mas
o o. Es a ap oximaion ep esen a una imp o an e di e enia on [4℄ y [6℄, que onside an
los li e ales omo elemen os aislados. Pa a ello, p oponemos
Pa ialmen e naniados po DGES, p oye os PB96{0098-C04{04 y PB96{1345
1. Que dos lausulas equi alen es ba jo subsunion se onside en iden ias. Es e plan-
eamien o es muho mas ue e que la equi alenia modulo enomb amien o y nos a
a pe mi i deni nues a union sob e lases de equi alenia.
2. Siguiendo la in uiion geome ia, la dis ania en e dos pun os se a la longi ud del
amino mas o o en e ellas, onside ando que dos lausulas es an a dis ania inni a
si no exis e un amino que las una.
2 Clausulas
A on inuaion eo damos algunas deniiones sob e lausulas que usa emos mas adelan e.
Una ision gene al puede ob ene se en [7℄.
En nues a ons uion onside a emos un lengua je
L
de p ime o den.
V a
y
T e m
son, esp e i amen e, los onjun os de a iables y e minos de
L
. Una
lausula
es un on-
jun o ni o de li e ales y
C
es el onjun o de las lausulas del lengua je.
Sea
S
V a
un onjun o ni o de a iables. Una
sus i uion
es una apliaion
:
S
!
T e m
al que (
8
x
2
S
)[
x
6
=
x
℄. Un
enomb amien o
es una sus i uion inye-
i a
al que (
8
x
2
S
) [
x
2
V a
℄. Si
C
es una lausula y
es un enomb amien o,
C
y
C
=
L
j
L
2
C
g
son
a ian es
.
Sean
C
y
D
dos lausulas.
C
subsume
a
D
,
C
D
, si exis e una sus i uion
al
que
C
D
. Si
C
D
y
D
C
en ones
C
y
D
son equi alen es p o subsunion y lo
es ibi emos
C
D
. Si
C
D
y
D
6
C
es ibi emos
C
D
. Una
lausula eduida
es una
lausula
C
al que no iene ning un sub onjun o p opio
D
al que
D
C
. Plo kin [9℄ p obo
que dos lausulas eduidas equi alen es son a ian es.
Pues o que
es una elaion de equi alenia, deno a emos p o
C
=
el espaio o ien e
y, si
C
2
C
, [
C
℄ =
D
2
C
j
C
D
g
. Denimos el o den pa ial
sob e
C
=
omo
(
8
[
C
℄
;
[
D
℄
2
C
=
) ([
C
℄
[
D
℄
,
C
D
) El o den
es a bien denido y no ausa a
on usion si usamos
en luga de
.
3 ILP
La P og amaion Logia Indu i a (ILP) puede deni se omo el a ea de in es igaion en la
in e seion del Ap endiza je Au oma io y la Logia Compu aional uyo p inipal ob je i o
es el desa ollo de eo as y algo i mos p a ios pa a el ap endiza je indu i o de p og amas
logios (N. La a y L. De Raed , 1995).
Del Ap endiza je Au oma io oma sus ob je i os, es o es, la sn esis de ono imien os
a pa i de la exp e ienia. En es e on ex o, el ap endiza je de onep os in en a ob ene
deniiones
de onep os a pa i de ins anias p osi i as (ejemplos que e ian la p opiedad
que que emos deni ) e ins anias nega i as (ejemplos que no la e ian) on la in enion
de ob ene una lasiaion de las ins anias obse adas as omo de p edei la posible
lasiaion de ins anias no obse adas.
De la Logia Compu aional, la ILP oma su ep esen aion o mal, su o ien aion
seman ia y sus enias. La deniion de un onep o se ep esen a median e un p og ama
logio, que no es mas que un onjun o ni o o denado de lausulas denidas, que puede
se is o omo el onjun o de axiomas de una eo a. Si nues a
deniion
(i.e. nues o
p og ama logio) es demasiado gene al, es o es, engloba ejemplos que no deseamos, deb emos
2
espeializa lo
. Si p o el on a io es demasiado esp eo, es o es, deja ue a ins anias que
deb e a onside a , en ones deb e se gene alizado. Es as
gene alizaiones
y
espeializa-
iones
se ealizan apliando a alguna lausula del p og ama un op e ado adeuado. De
es e modo se esp e a que as la suesi a apliaion de op e ado es la suesion de p og amas
on e ja a uno que ub a odos los ejemplos posi i os y ninguno de los nega i os. En
[8℄ Nienhuys{Cheng y Van de Laag denie on un op e ado de enamien o
que omaba
omo da o de en ada una lausula eduida
C
y de ol a un onjun o de lausulas eduidas
(
C
):
Deniion 1 (Adap ada de [8℄)
Sea
C
una lausula eduida. En ones
D
2
(
C
)
si
D
es eduida y se e ia una de las siguien es ondiiones:
1
:
C
D
y exis en dos lausulas
C
0
2
[
C
℄
y
D
0
2
[
D
℄
ales que
C
0
=
D
0
, donde
es la
sus i uion
=
x=
(
y
1
;:::;y
n
)
g
,
es un smbolo de union
1
,
x
ou e en
C
0
, y las
a iables
y
1
;:::;y
n
son a iables dis in as que no ou en en
C
0
.
2
:
C
D
y exis en dos lausulas
C
0
2
[
C
℄
y
D
0
2
[
D
℄
ales que
C
0
=
D
0
, donde
=
x=y
g
y ademas las a iables
x
e
y
ou en en
C
0
.
3
:
D
=
C
[
L
g
donde
L
solo iene a iables dis in as que no ou en en
C
y pa a odo
li e al
M
2
C
,
L
die e de
M
en el smbolo de p ediado o en el signo.
Una
{adena de longi ud
n
de
C
a
D
es una suesion ni a
C
=
C
0
; C
1
;:::;C
n
=
D
al
que pa a odo
i
2
1
; : : : ; n
g
,
C
i
2
(
C
i
1
)
.
Po ejemplo, onside emos la lausula
enendida
(
x
)
bombil l a
(
x
)
; abl e
(
x; y
)
; o ien e
(
y
)
que exp esada omo onjun o de li e ales es
C
=
enendida
(
x
)
;
:
bombil l a
(
x
)
;
:
abl e
(
x; y
)
;
:
o ien e
(
y
)
g
. Si es a lausula ue a demasido gene al p o demos hae la mas esp ea
apliando alguno de los ope ado es de enamien o.
Po el op e ado
1
, si apliamos la sus i uion
1
=
y =ba e ia
g
, donde
ba e ia
es un
smbolo de union de a idad e o, end amos la lausula
C
=
enendida
(
x
)
;
:
bombil l a
(
x
)
;
:
abl e
(
x; ba e ia
)
;
:
o ien e
(
ba e ia
)
g
.
Po el op e ado
2
, si apliamos la sus i uion
2
=
y =x
g
, end amos la lausula
C
=
enendida
(
x
)
;
:
bombil l a
(
x
)
;
:
abl e
(
x; x
)
;
:
o ien e
(
x
)
g
.
El op e ado
3
es mas enio. Nos p e mi e a ~nadi li e ales nue os omo
no undida
(
z
)
y onsegui lausulas omo
C
1
=
enendida
(
x
)
;
:
bombil l a
(
x
)
;
:
abl e
(
x; y
)
;
:
o ien e
(
y
)
;
no undida
(
z
)
g
, pa a despues aplia o os op e ado es, p o ejemplo
3
median e la sus i-
uion la sus i uion
3
=
z =x
g
y ob ene
C
1
3
=
enendida
(
x
)
;
:
bombil l a
(
x
)
;
:
abl e
(
x; y
)
;
:
o ien e
(
y
)
; no undida
(
x
)
g
.
4 Quasi{me ias
Las uniones de dis ania no sime ias ya ue on onside adas p o Hausdo [3℄ a p inipios
de siglo. Wilson [12℄ in o dujo el e mino
quasi{me is
pa a es as uniones en 1931. A
1
Conside amos las ons an es omo smb olos de union de a idad e o.
3
lo la go del siglo di e sos in es igado es han on ibuido al desa ollo de las dis anias
no sime ias, eibiendo eien emen e un nue o empuje on los aba jos en ompu aion
eo ia de Lawson [5℄ o Smy h [11℄ en e o os.
Deniion 2 ([11℄)
Una quasi{me ia sob e un onjun o
X
es una apliaion de
X
X
en los eales no nega i os, inluyendo posiblemen e
+
1
al que
(
8
x
2
X
) [
d
(
x; x
) = 0℄
(
8
x; y
2
X
) [
d
(
x; y
) =
d
(
y ; x
) = 0
)
x
=
y
℄
(
8
x; y ; z
2
X
) [
d
(
x; z
)
d
(
x; y
) +
d
(
y ; z
)℄
No ese que una quasi{me ia e ia las ondiiones de me ia de F ehe [2℄, exep o la
ondiion de sime a. Veamos algunos ejemplos (o os ejemplos mas sos iados pueden
enon a se en [11℄).
Ejemplo 1:
Dado ualquie onjun o pa ialmen e o denado
h
P ;
i
, la
quasi{me ia
dis e a
se dene omo
d
(
x; y
) =
0 si
x
y
1 e.o..
Ejemplo 2:
En el in e alo unidad [0
;
1℄ p o demos deni la quasi{me ia siguien e, uya
me ia asoiada es la dis ania euldea en el onjun o.
d
(
x; y
) =
0 si
x
y
x
y
si
y < x
5 Una quasi{me ia sob e las lases de equi alenia
En [8℄ Nienhuys-Cheng y y Van de Laag p oba on que si
C
y
D
son lausulas eduidas y
C
D
en ones exis e una
{adena
de
C
a
D
. Vamos a usa esas adenas pa a o maliza
la p oximidad en e lausulas. En nues a deniion, la dis ania en e dos lausulas end a
de e minada p o la longi ud del
amino
mas o o en e ellas, onside ando omo amino la
suesion de lases de equi alenia aso iada a una
{adena.
Deniion 3
Di emos que la suesion
C
=
h
[
C
0
℄
;:::;
[
C
n
℄
i
, on
[
C
i
℄
2
C
=
pa a odo
i
2
0
;:::;n
g
es una
L
{adena de
[
C
0
℄
a
[
C
n
℄
si podemos elegi omo ep esen an es de
dihas lases las lausulas eduidas
C
0
;:::;C
n
y dihas lausulas o man una
{adena.
En ese aso di emos que la
L
{adena
C
iene longi ud
n
y lo deno a emos po
jC j
=
n
.
Deno a emos omo
L
([
C
℄
;
[
D
℄)
el onjun o de odas las
L
{adenas de
[
C
℄
a
[
D
℄
. El unio
elemen o de
L
([
C
℄
;
[
C
℄)
es la suesion de longi ud e o
h
[
C
℄
i
.
Es i ial omp oba que si
C
1
=
h
[
C
0
℄
;:::;
[
C
n
℄
i
es una
L
{adena de [
C
0
℄ a [
C
n
℄ y
C
2
=
h
[
D
0
℄
;:::;
[
D
m
℄
i
es una
L
{adena de [
D
0
℄ a [
D
m
℄ on [
C
n
℄ = [
D
0
℄, en ones
C
3
=
h
[
C
0
℄
;:::;
[
C
n
℄
;
[
D
1
℄
;:::;
[
D
m
℄
i
es una
L
{adena de [
C
0
℄ a [
D
m
℄ de longi ud
n
+
m
que llama emos la
ona enaion
de
C
1
y
C
2
. Sab emos que si
C
y
D
son lausulas eduidas y
C
D
, en ones exis e una
{adena
de
C
a
D
. Como onseuenia inmedia a enemos el siguien e eo ema:
4
Teo ema 4
Conside emos
[
C
℄
;
[
D
℄
2
C
=
ales que
[
C
℄
[
D
℄
. En ones exis e una
L
{
adena de
[
C
℄
a
[
D
℄
.
Demos aion:
Sean [
C
℄
;
[
D
℄
2
C
=
ales lases de equi alenia y sean
C
0
y
D
0
dos lausulas
eduidas ales que
C
0
2
[
C
℄ y
D
0
2
[
D
℄. Pues o que
C
0
D
0
, se iene que exis e una
{adena de
C
0
a
D
0
. Las lases de equi alenia aso iadas a los elemen os de la
{adena
o man una
L
{adena de [
C
℄ a [
D
℄.
A on inuaion denimos nues a quasi{me ia. Si [
C
℄
[
D
℄ en ones exis e al menos una
L
{adena de [
C
℄ a [
D
℄, (el onjun o
L
([
C
℄
;
[
D
℄) no es ao) y iene sen ido onside a el
mnimo del onjun o de longi udes de aminos en
L
([
C
℄
;
[
D
℄).
Siguiendo la in uiion geome ia, si onside amos esas
L
{adenas omo
aminos
de
[
C
℄ a [
D
℄, po demos deni nues a quasi{me ia omo la longi ud del amino mas o o de
[
C
℄ a [
D
℄. Si no exis e ning un amino, p ensamos que [
D
℄ no puede se alanzado desde [
C
℄,
as que es an sepa ados p o una dis ania inni a.
Deniion 5
Denimos la apliaion
d
:
C
=
C
=
!
[0
;
+
1
℄
de la siguien e mane a
d
([
C
℄
;
[
D
℄) =
min
jC j
:
C 2
L
([
C
℄
;
[
D
℄)
g
si
[
C
℄
[
D
℄
+
1
e.o..
Teo ema 6
d
es una quasi{me ia
Demos aion:
(1) Pues o que [
C
℄
[
C
℄ pa a o do [
C
℄
2
C
=
, se iene que la
L
{adena
h
[
C
℄
i 2
L
([
C
℄
;
[
C
℄). Ademas
jh
[
C
℄
ij
= 0, luego
d
([
C
℄
;
[
C
℄) = 0.
(2) Si
d
([
C
℄
;
[
D
℄) =
d
([
D
℄
;
[
C
℄) = 0, en ones [
C
℄
[
D
℄ y po an o [
C
℄ = [
D
℄.
(3) Tenemos que p oba que
d
([
C
1
℄
;
[
C
3
℄)
d
([
C
1
℄
;
[
C
2
℄) +
d
([
C
2
℄
;
[
C
3
℄). Si [
C
1
℄
6
[
C
2
℄ o
[
C
2
℄
6
[
C
3
℄ el esul ado se iene i ialmen e, luego supongamos [
C
1
℄
[
C
2
℄ y [
C
2
℄
[
C
3
℄.
Sean
C
1
=
h
[
D
0
℄
;:::;
[
D
n
℄
i
una
L
{adena de [
C
1
℄ a [
C
2
℄ (es o es, [
D
0
℄ = [
C
1
℄ y [
D
n
℄ = [
C
2
℄)
al que
n
=
jC
1
j
=
d
([
C
1
℄
;
[
C
2
℄) y
C
2
=
h
[
D
0
0
℄
;:::;
[
D
0
m
℄
i
una
L
{adena de [
C
2
℄ a [
C
3
℄ (i.e.,
[
D
0
0
℄ = [
C
2
℄ y [
D
m
℄ = [
C
3
℄ ) al que
m
=
jC
2
j
=
d
([
C
2
℄
;
[
C
3
℄) Si ona enamos
C
1
y
C
2
ob enemos
C
12
=
h
[
D
0
℄
;:::;
[
D
n
℄
;
[
D
0
1
℄
;:::;
[
D
0
m
℄
i
que es una
L
{adena de [
C
1
℄ a [
C
3
℄ de
longi ud
n
+
m
, luego
d
([
C
1
℄
;
[
C
3
℄)
jC
12
j
=
n
+
m
=
d
([
C
1
℄
;
[
C
2
℄) +
d
([
C
2
℄
;
[
C
3
℄)
Po an o es una quasi{me ia. Si aho a ol emos a onside a las lausulas aisladas y no
las lases de equi alenia end emos una union
b
d
:
C
C
!
[0
;
+
1
℄
h
C; D
i 7!
b
d
(
C; D
) =
d
([
C
℄
;
[
D
℄)
en la ual dos lausulas equi alen es es an a dis ania e o ( eniamen e una pseudo{quasi{
dis ania) en la ual man enemos las siguien es p opiedades:
5
1.
b
d
(
C; D
) = 0
,
C
D
2.
b
d
(
C; D
) = +
1 ,
C
6
D
3. (
8
C
1
; C
2
; C
3
2
C
) [
b
d
(
C
1
; C
3
)
b
d
(
C
1
; C
2
) +
b
d
(
C
2
; C
3
)℄
Pensamos que de es a mane a,
b
d
(
C; D
) o dia de mane a nume ia suien e in o maion
sob e la elaion de subsunion en e
C
y
D
y p e mi e un a amien o algeb aio de la
elaion de p oximidad.
6 T aba jos elaionados
Como apun abamos en la in o duion, en la li e a u a puede enon a se di e sas ap o-
ximaiones al p oblema de uan ia la elaion de p oximidad en e lausulas. Nues a
p opues a se suma al es ue zo de a o ja luz sob e el p oblema.
6.1 Nienhuys{Cheng [6℄ y Ramon y B uyno oghe [10℄
En [6℄, Nienhuys-Cheng dene una dis ania pa a a omos e ados
d
n;g
(
e; e
) = 0
p=n
6
=
q =m
)
d
n;g
(
p
(
s
1
;:::;s
n
)
; q
(
1
;:::;
m
)) = 1
d
n;g
(
p
(
s
1
;:::;s
n
)
; p
(
1
;:::;
n
)) =
1
2
n
P
n
i
=1
d
n;g
(
s
i
;
i
)
y luego onside a la me ia de Hausdo pa a aslada esa dis ania a onjun os de a omos.
d
h
(
A; B
) = max
max
a
2
A
min
d
n;g
(
a; b
)
j
b
2
B
gg
;
max
b
2
B
min
d
n;g
(
a; b
)
j
a
2
A
ggg
El ob je i o de es a dis ania e a deni una me ia en e in e p e aiones de He b and,
as que
d
n;g
es aba solo denida sob e a omos e ados. En [10℄, Ramon y B uyno oghe
ex endie on es a dis ania a una union sob e exp esiones e adas y no e adas:
d
n
(
e
1
; e
2
) =
d
n;g
(
e
1
; e
2
) si
e
1
; e
2
son exp esiones e adas.
d
n
(
p
(
s
1
;:::;s
n
)
; X
) =
d
n
(
X ; p
(
s
1
;:::;s
n
)) = 1 on
X
una a iable.
d
n
(
X ; Y
) = 1 y
d
n
(
X ; X
) = 0 pa a odo
X
6
=
Y
on
X
e
Y
a iables.
Apliando a
d
n
la me ia de Hausdo enemos una dis ania sob e lausulas, omo mues-
a el siguien e ejemplo
C
1
=
p
(
(
U
)
; X ;
(
a
))
g
C
2
=
p
(
(
a
)
; X ;
(
a
))
g
C
3
=
p
(
(
a
)
; X ;
(
a
))
; p
(
Z; X ; Z
)
g
C
4
=
p
(
(
a
)
; X ;
(
a
))
; p
(
(
a
)
; V ;
(
a
))
g
6
on
d
h
(
C
1
; C
2
) =
1
12
,
d
h
(
C
1
; C
3
) =
1
3
,
d
h
(
C
1
; C
4
) =
1
4
. Se obse a que los es alo es son
muy dis in os a p esa de que
C
2
,
C
3
y
C
4
son equi alen es ba jo subsunion. Con nues a
union se iene
b
d
(
C
1
; C
2
) =
b
d
(
C
1
; C
3
) =
b
d
(
C
1
; C
4
) = 1
pues o que [
C
2
℄ = [
C
3
℄ = [
C
4
℄ on [
C
1
℄
6
= [
C
2
℄ y
C
1
=
C
2
on
=
U =a
g
.
6.2 Hu hinson [4℄
En [4℄, Hu hinson da una pseudo-me ia sob e el onjun o de e minos y la ex iende al
onjun o de li e ales. En ones, onside a la me ia de Hausdo sob e el onjun o de
lausulas usando su pseudo{me ia sob e li e ales.
En su deniion de dis ania sob e e minos, usa una union del onjun o de sus i u-
iones sob e
R
llamada
size
. Da las ondiiones que iene que sa is ae una union pa a
se una
size
y da una union on e a on esas a a e s ias
S
(
) =
X
w
=n
j
(
9
x
) (
x
2
V a
y
=n
o u e en
x
)
g
donde
w
=n
es un p eso p osi i o pa a el smb olo de union
=n
. Con la me ia de Hausdo
basada en esa pseudo{me ia enemos que pa a las lausulas
C
1
=
p
(
X ; X ; Y ; Y
)
g
C
2
=
p
(
U; V ; U; V
)
g
ob enemos los alo es
d
h
(
C
1
; C
1
) = 0 y
d
h
(
C
1
; C
2
) = 0 a p esa de que
C
1
y
C
2
no son ni
siquie a ompa ables ba jo subsunion.
Con nues a union
b
d
, al no exis i ning un amino de
C
1
a
C
2
, esa elaion de ina-
esibilidad se o dia on el smb olo +
1
.
b
d
(
C
1
; C
2
) =
b
d
(
C
2
; C
1
) = +
1
7 Conlusiones
Es e es un aba jo p elimina sob e omo uan ia la elaion de p oximidad en e lau-
sulas y se suma a o as ap oximaiones en un in en o de a o ja luz sob e el p oblema. La
idea de nues a ap oximaion es ap o eha la elaion p eexis en e en e las lausulas pa a
deni una union de mane a na u al. Al se es a elaion de subsunion no sime ia, es a
o malizaion de la p oximidad amp o o iene p o que se lo.
Conside amos que deni una dis ania en e lausulas apliando la me ia de Haus-
do sob e una dis ania en e li e ales quiza no sea lo mas ae ado ya que depende exlu-
si amen e de alo es ex emos.
Po o o lado, quiza la o malizaion de dis ania de F ehe [2℄ sea demasiado es i a
pa a espaios donde la p inipal elaion es la de o den pa ial. En es e sen ido, pensamos
que es e a ulo ab e una pue a a esa nue a onep ion en la o malizaion de p oximidad.
Nues a in es igaion se en a en es ablee i e ios de p oximidad en el onjun o de
lasulas y es udia sus p opiedades. Pa a ello deb emos do a al onjun o de lausulas de
una op ologa ap opiada y onside a los op e ado es de gene alizaion (y esp eializaion)
omo uniones del onjun o de lausulas en s mismo.
7
Es a o malizaion se undamen a en un es udio op ologio de op e ado es en e p og a-
mas logios (o sub onjun os de ellos) y p e mi i a una mejo omp ension del onep o de
p oximidad mas alla de los espaios me ios y espe amos que ayude a mejo a los algo i mos
de b usqueda de soluiones en ILP.
Re e enias
[1℄ T. Ei e and H. Mannila:
Dis ane Measu es o Poin Se s and Thei Compu a ion
.
A a In o ma ia 34, 2, pp.: 109{133, 1997.
[2℄ M. F ehe .
Su quelques poin s du alul on ionnel
. Reudion del Ci ulo Ma em-
a io di Pale mo, ol 22, 1906.
[3℄ F. Hausdo .
G undzuge de Mengenleh e
. Leipzig, 1914.
[4℄ A. Hu hinson.
Me is on Te ms and Clauses
. P o . ECML{97 P ague Ap il 1997
(Sp inge ).
p.// p.ds.kl.a.uk/pub/ eh- epo s/ 96-11.ps.gz
[5℄ J.D. Lawson.
O de and s ongly sobe ompa ia ions.
In. G.M. Reed, A.W. Rosoe
and R.F. Wah e (Eds.), Top ology and Ca ego y Theo y in Compu e Siene, Ox o d
Uni e si y P ess, pp. 179{205, 1991.
[6℄ S-H. Nienhuys-Cheng.
Dis ane be ween He b and in e p e a ions. a measu e o ap-
p oxima ions o a a ge onep
. Tehnial Rep o EUR{FEW{CS{97{05. Depa men
o Compu e Siene, E asmus Uni e si y, he Ne he lands, 1997.
www. ew.eu .nl/ ew
/ esea h/pubs/s/1997/eu - ew-s-97-05.pd
[7℄ S-H. Nienhuys-Cheng and R. de Wol .
Founda ions o Indu i e Logi P og amming
.
LNCS 1228. Sp inge , 1997
[8℄ P.R.J. an de Laag, S.-H. Nienhuys-Cheng.
Comple eness and p ope ness o enemen
ope a o s in Indu i e Logi P og amming
. Jou nal o Logi P og amming, Vol 34, n.3,
pp.. 201{225, Ma h 1998
[9℄ G.D. Plo kin.
A No e on Indu i e Gene aliza ion
. In Mahine In elligene 5, pp..
153{163. Edinbu gh Uni e si y P ess, Edinbu gh, 1970.
[10℄ J. Ramon and M. B uyno oghe.
A amewo k o dening dis anes be ween s {o de
logi{obje s.
Rep o CW 263, Depa men o Compu e Siene, Ka holieke Uni e -
si ei Leu en, May 1998.
h p.//www.s.kuleu en.a.be/publia ies/ appo en
/w/CW263.ps.gz
[11℄ M.B. Smy h.
To al ly bounded spaes and ompa o de ed spaes as domains o ompu-
a ion.
In. G.M. Reed, A.W. Roso e and R.F. Wah e (Eds.), Top ology and Ca ego y
Theo y in Compu e Siene, Ox o d Uni e si y P ess, pp. 207-229, 1991.
[12℄ W.A. Wilson.
On quasi{me i spaes
. Ame . J. Ma h. 53, pp. 675{684, 1931.
8