Algo i mos de an´alisis pa a g am´a icas de inse ci´on
de ´a boles: Relaciones.
Vicen e Ca illo
Depa amen o de Lenguajes y Sis emas In o m´a icos
Uni e sidad de Se illa
[email p o ec ed]
Resumen
T ee Inse ion G amma (TIG) es un comp omiso en e Con ex
F ee G amma (CFG) y T ee Adjoining G amma (TAG) que puede
se analizada con un cos e empo al de O(n3). En la li e a u a, an s´olo
han sido desc i os dos algo i mos de an´alisis pa a TIGs, basados en los
ya conocidos CYK y Ea ley pa a CFGs. En es e in o me se desc iben
en de alle los analizado es pa a TIGs p esen ados en [7, 5, 4], as´ı como
las elaciones o males exis en es en e ellos. El obje i o es de ini la
espina do sal del n´ucleo de una axonom´ıa de analizado es basados en
el algo i mo de Ea ley, simila a las ya exis en es pa a CFGs [20] y
TAGs [1] [9].
1 In oducci´on
Las g am´a icas de adjunci´on de ´a boles (T ee Adjoining G amma , TAG)
[14] cons i uyen un o malismo na u almen e lexicalizado muy adecuado
pa a la desc ipci´on de la sin axis de los lenguajes na u ales. Como con a-
pa ida, el p oceso de an´alisis pa a es e o malismo implica mayo es cos es
compu acionales que el mismo p oceso pa a las g am´a icas independien es
del con ex o (Con ex F ee G amma , CFG): la complejidad empo al en el
caso peo de los analizado es pa a TAG es de O(n6), donde nes la longi-
ud de la cadena de en ada, en e a la complejidad O(n3) que p esen an
los analizado es pa a CFG. En los ´ul imos a˜nos, se han desc i o muchas
ap oximaciones que in en an mejo a las p es aciones de los analizado es
pa a TAG: unas basadas en la compilaci´on de los ´a boles elemen ales en
au ´oma as de es ados ini os [13], o as que aplican cie os il os a los al-
go i mos de an´alisis [6, 8, 11] y o as, como la empleada en es e abajo,
basadas en es icciones sob e el o malismo [15].
1
Las g am´a icas de inse ci´on de ´a boles (T ee Inse ion G amma , TIG)
[15] cons i uyen un comp omiso en e CFG y TAG que combina la e iciencia
de an´alisis de las p ime as con la ue e lexicalizaci´on de las segundas, ya
que, al igual que ocu e con las CFGs, cualquie TIG se puede analiza con
un cos e empo al de O(n3) en el peo caso y, po o a pa e, al se las
TIGs una subclase de las TAGs, se encuen an na u almen e lexicalizadas.
La impo ancia del o malismo TIG se undamen a en el hecho de que la
mayo ´ıa de las g am´a icas de adjunci´on de ´a boles de amplia cobe u a se
co esponden en su mayo pa e con dicho o malismo. Es a a i maci´on se
puede comp oba en la g am´a ica del ingl´es XTAG [12], donde el 99% de los
´a boles y adjunciones posibles son compa ibles con el o malismo TIG.
La mayo ´ıa de los analizado es pa a TAG y TIG son ex ensiones de
analizado es bien conocidos pa a CFG. En la li e a u a podemos encon a
mul i ud de analizado es pa a TAG, algunos usan una es a egia ascenden e
[2, 10, 17], o os u ilizan es a egias ascenden es p edic i as de mane a sim-
ila al algo i mo de Ea ley pa a CFG [2, 16] y o os, como [11, 8], usan una
adap aci´on pa a TAG del conocido il o le co ne pa a CFG con obje o
de aumen a las p es aciones de los analizado es p edic i os.
Pod ´ıa pensa se que los analizado es pa a TIG pueden se de i ados di-
ec amen e de los analizado es pa a TAG, dadas las simili udes en e ambos
o malismos. Sin emba go, los aspec os que los di e encian son lo su icien e-
men e signi ica i os como pa a hace que al adap aci´on no sea sencilla de e-
aliza . Como ilus aci´on, podemos conside a la eno me di e encia exis en e
en e el analizado de ipo Ea ley pa a TAG y el analizado de ipo Ea ley
pa a TIG de inido en [15].En [7] se p esen an un conjun o de analizado es
pa a TIG, conc e amen e cua o, es que usan es a egia ascenden e y uno
ascenden e p edic i o. En es e abajo ampliamos es a ed de analizado es
pa a TIG, in oduciendo un nue o analizado que aplica un il o de ipo
le co ne a una a ian e del analizado ascenden e p edic i o p esen ado
en [7].
El in o me se encuen a es uc u ado de la siguien e mane a. Una p ime a
secci´on donde se in oducen los concep os y la no aci´on necesa ios. Dada
la longi ud del abajo, hemos p e e ido di idi el bloque p incipal en dos
pa es.
En la p ime a pa e se desc iben en de alle algunos de los analizado es
pa a TIGs p esen ados en [7] y las elaciones o males exis en es en e ellos.
Como pun o de pa ida de ini emos un esquema basado en el conocido algo-
i mo CYK pa a CFGs. A con inuaci´on de ini emos un esquema ascenden e
basado en Ea ley que nos pe mi a amplia la clase de g am´a icas sob e la
que pueda ac ua . Y conclui emos el conjun o de esquemas de es a egia
2
ascenden e con la p esen aci´on de un analizado con eco ido bidi eccional
de la cadena de en ada al es ilo del p opues o po de V eugh y Honig pa a
CFGs [21]. Como pun o inal de es a p ime a ed de analizado es, in o-
duci emos una a ian e del esquema basado en el algo i mo de Ea ley pa a
TIGs [15] y es ablece emos las elaciones o males exis en es en e ellos.
En la segunda pa e se de ine el concep o de le co ne en el con ex o del
o malismo TIG, el cual se aplica pa a ob ene una e si´on ascenden e y dos
p edic i as de algo i mos basados en LC pa a TIG. Tambi´en se p esen a ´a
una a ian e p edic i a que se i ´a como esquema in e medio pa a mos a
la elaci´on exis en e en e los dos analizado es p edic i os de inidos. Pa a
e mina demos a emos las elaciones exis en es en e es os esquemas y los
p esen ados en la p ime a pa e.
2 No aci´on
Una TIG es una 5- upla (VN, VT, S, I,A), donde VNes un conjun o de
s´ımbolos no e minales, VTes un conjun o de s´ımbolos e minales, S∈VN
es el axioma, Ies un conjun o ini o de ´a boles iniciales ini os y Aes un
conjun o ini o de ´a boles auxilia es ini os. Al conjun o I∪Ase le denom-
ina ´a boles elemen ales. Nos e e i emos a la a´ız de un ´a bol elemen al γ
como Rγ. En cada ´a bol elemen al, los nodos de la on e a se e ique an con
s´ımbolos e minales, la palab a ac´ıa (ε) o s´ımbolos no e minales ma cados
pa a sus i uci´on, excep o un nodo en cada ´a bol auxilia , cuya e ique a es la
misma que la de la a´ız y que se denomina nodo pie. Deno a emos como Fβ
al nodo pie de un ´a bol auxilia β. Denominamos espina al camino de la a´ız
al pie de un ´a bol auxilia . Usa emos label(Mγ) pa a deno a la e ique a
asociada al nodo Mγ.
Los ´a boles auxilia es en los cuales odo nodo on e a es ´a a la izquie da
(de echa) del nodo pie se denominan ´a boles auxilia es izquie dos (de echos).
El es o de ´a boles auxilia es se denominan ´a boles w apping. Usa emos A
L
yA
R
pa a deno a los conjun os de ´a boles auxilia es izquie dos y de echos,
espec i amen e.
Una de i aci´on TIG comienza con un ´a bol inicial cuya a´ız es ´a e ique-
ada po S. Es e ´a bol se ex iende epe idamen e usando las ope aciones de
adjunci´on ysus i uci´on. La adjunci´on inse a un ´a bol auxilia βen el nodo
Mγde un ´a bol γque enga la misma e ique a que Rβ. En conc e o, Mγes
eemplazado po βyFβes eemplazado po el sub´a bol dominado po Mγ.
Usa emos β∈adj(Mγ) pa a deno a que un ´a bol β∈Apuede se adjun-
ado en un nodo Mγ, es deci , Mγes un nodo de adjunci´on. Si la adjunci´on
3
no es obliga o ia en Mγen onces nil ∈adj(Mγ), donde nil es un s´ımbolo
ac´ıo. La adjunci´on de un ´a bol auxilia izquie do (de echo) se denomina
adjunci´on izquie da (de echa). Usa emos β∈ladj(Mγ) (β∈ adj(Mγ))
pa a deno a que β∈A
L
(β∈A
R
) se puede adjun a en el nodo Mγ, es
deci , Mγes un nodo de adjunci´on izquie da (de echa). Si una adjunci´on
izquie da (de echa) no es obliga o ia en el nodo Mγen onces nil ∈ladj(Mγ)
(nil ∈ adj(Mγ)). La sus i uci´on es una ope aci´on obliga o ia y eemplaza
un nodo ma cado pa a sus i uci´on Mγcon una copia de un ´a bol inicial α
cuya a´ız es ´e e ique ada igual que Mγ. Usamos α∈subs (Mγ) pa a indica
que el nodo Mγpuede se sus i uido po el ´a bol α∈I.
TIG no pe mi e: (1) ´a boles auxilia es w apping, (2) la adjunci´on de un
´a bol auxilia izquie do (de echo) en la espina de un ´a bol auxilia de echo
(izquie do) y (3) la adjunci´on en los nodos a´ız y pie de los ´a boles auxilia es.
Pa a inc emen a los ´a boles que se pueden gene a , TIG pe mi e un n´ume o
a bi a io de adjunciones simul ´aneas sob e un mismo nodo. La adjunci´on
simul ´anea es una ope aci´on esencialmen e ambigua y p o oca la c eaci´on
de muchos ´a boles di e en es. F´acilmen e se pueden imagina a ian es de
TIG donde la adjunci´on simul ´anea es ´e m´as limi ada. Pa a no inc emen-
a la ambiguedad de la de i aci´on, hemos elegido pa a la de inici´on de los
esquemas la a ian e de TIG p esen ada en [18], que como m´aximo pe mi e
una adjunci´on izquie da y o a de echa sob e un mismo nodo. Adem´as, pa a
man ene los ´a boles que se pueden gene a median e adjunci´on simul ´anea,
pe mi i emos la adjunci´on en los nodos a´ız y pie de los ´a boles auxilia es.
Con obje o de ep esen a los ´a boles de an´alisis pa ciales, de inimos
una p oducci´on Nγ→Nγ
1. . . Nγ
gpa a cada nodo Nγy sus secuencia o de-
nada de ghijos Nγ
1. . . Nγ
gen un ´a bol elemen al. Deno a emos el conjun o
de p oducciones asociado a un ´a bol elemen al γcomo P(γ). Po azones
´ecnicas, conside amos las p oducciones adicionales > → Rα,> → Rβy
Fβ→ ⊥ pa a cada ´a bol inicial αy cada ´a bol auxilia β. Pa a man ene la
capacidad gene a i a de la g am´a ica, se p oh´ıbe la adjunci´on y sus i uci´on
en los nodos >y⊥.
Los esquemas de an´alisis sin ´ac ico [20] cons i uyen un m´e odo gene -
al pa a la especi icaci´on de algo i mos de an´alisis sin ´ac ico, que su ge co-
mo una o malizaci´on de abajos p esen ados sob e analizado es deduc i os
[19]. En e sus en ajas undamen ales se encuen an:
•De inici´on de los analizado es sin ene en cuen a las es uc u as de
da os y de con ol que se usa ´an en su implemen aci´on.
•Pe mi e es ablece de una mane a ´acil las elaciones en e dis in os
algo i mos median e el an´alisis de cie as elaciones o males.
4
El uso de sis emas de an´alisis pa a la especi icaci´on de analizado es
sin ´ac icos nos pe mi e explo a odas las p opiedades de los sis emas de-
duc i os, en e o as, la posibilidad de es ablece elaciones en e dis in os
sis emas. En [3] se pueden encon a odas las de iniciones necesa ias pa a
comp ende y aplica los esquemas de an´alisis sin ´ac ico y la no aci´on e e -
en e a ellos empleadas a lo la go de es e in o me.
3 Esquema basado en CYK
El p ime esquema que e emos, que denomina emos CYKi, p esen a una
es a egia de an´alisis ascenden e con lec u a unidi eccional, de izquie da a
de echa, de la cadena de en ada. Se a a de una ex ensi´on del algo i mo
CYK de inido o iginalmen e pa a g am´a icas independien es del con ex o.
El esquema CYKi ue in oducido en [7] y se basa en el p esen ado en o ma
algo ´ı mica pa a las SLTIG en [18].
El esquema CYKis´olo es aplicable a la clase de g am´a icas de inse ci´on
de ´a boles CNFT IG cuyos ´a boles elemen ales p esen an las siguien es e-
s icciones: (i) un nodo in e no, sal o el nodo pie, domina ´a di ec amen e un
m´aximo de dos nodos y (ii) los nodos e ique ados con s´ımbolos e minales,
la palab a ac´ıa o el nodo bo om no end ´an nodos he manos.
El dominio del esquema CYKi iene dado po :
ICYKi={[Mγ, i, j, code]|Mγ∈VN,γ∈I∪A,
0≤i≤j,code ⊆ {L, R}}
La unci´on del pa ´ame o code es indica si sob e el nodo Mγse ha
comple ado una adjunci´on izquie da y/o de echa o no se ha comple ado
ninguna adjunci´on, y puede oma uno de los siguien es alo es:
• ∅ si no ha ha comple ado ninguna adjunci´on en el nodo Mγ,
• {L}si se ha comple ado una adjunci´on de un ´a bol auxilia izquie do
en el nodo Mγ,
• {R}si se ha comple ado una adjunci´on de un ´a bol auxilia de echo
en el nodo Mγ,
• {L, R}si se ha comple ado las adjunciones de un ´a bol auxilia izquie -
do y o o de echo en el nodo Mγ.
5

Los pasos deduc i os del esquema son:
DCYKi=DScan
CYKi∪ Dε
CYKi∪ DCompUna
CYKi∪ DCompBin
CYKi∪ DLAdj
CYKi∪ DRadj
CYKi∪ DSubs
CYKi
DScan
CYKi=[a, j, j + 1]
[Nγ, j, j + 1,∅]Nγ→a∈ P(γ)
Dε
CYKi=[Nγ, j, j, ∅]
Nγ→ε∈ P(γ)
´o Nγ→ ⊥
DCompUna
CYKi=[Oγ, i, j, code]
[Mγ, i, j, ∅]Mγ→Oγ∈ P(γ)
donde se debe cumpli :
(i) (nil ∈ladj(Oγ) y L /∈code) ´o (β∈ladj(Oγ) y L∈code),
(ii) (nil ∈ adj(Oγ) y R /∈code) ´o (β∈ adj(Oγ) y R∈code).
DCompBin
CYKi=
[Oγ
1, i, j, code]
[Oγ
2, j, k, code0]
[Mγ, i, k, ∅]Mγ→Oγ
1Oγ
2∈ P(γ)
donde se debe cumpli :
(i) (nil ∈ladj(Oγ
1) y L /∈code) ´o (β∈ladj(Oγ
1) y L∈code),
(ii) (nil ∈ adj(Oγ
1) y R /∈code) ´o (β∈ adj(Oγ
1) y R∈code),
(iii) (nil ∈ladj(Oγ
2) y L /∈code0) ´o (β∈ladj(Oγ
2) y L∈code0),
(i ) (nil ∈ adj(Oγ
2) y R /∈code0) ´o (β∈ adj(Oγ
2) y R∈code0).
DLAdj
CYKi=
[Pβ, i, j, ∅]
[Mγ, j, k, code]
[Mγ, i, k, {L} ∪ code]
label(Pβ) = >
β∈ladj(Mγ)
L /∈code
DRAdj
CYKi=
[Pβ, j, k, ∅]
[Mγ, i, j, code]
[Mγ, i, k, {R} ∪ code]
label(Pβ) = >
β∈ adj(Mγ)
R /∈code
DSubs
CYKi=[Pα, i, j, ∅]
[Mγ, i, j, ∅]
label(Pα) = >
α∈subs (Mγ)
6
Los pasos deduc i os DScan
CYKi,Dε
CYKison los que inician el econocimien o
ascenden e. Tambi´en se incluye en es e caso los nodos pies de los ´a boles
auxilia es, ya que en los ´a boles auxilia es TIGs no es necesa io ansmi i
la in o maci´on del sub´a bol escindido.
Una ez econocido el sub´a bol dominado po un nodo, los pasos DCompUna
CYKi
yDCompBin
CYKipe mi en con inua el econocimien o ascenden e. Cuando se
ha econocido un ´a bol auxilia izquie do ( esp. de echo), el paso DLAdj
CYKi
(DRAdj
CYKi) e ec ´ua la adjunci´on en un nodo de adjunci´on izquie da ( esp.
de echa), siemp e que el econocimien o lo haya alcanzado y no haya sido ya
adjun ado po la izquie da ( esp. de echa). La condici´on que acompa˜na a
ambos pasos de compleci´on comp ueba que el nodo que domina el sub´a bol
que se a a comple a no p esen e adjunci´on (izquie da y/o de echa) obliga-
o ia y, en el caso de p esen a la, que se haya e ec uado.
Po ´ul imo, la ope aci´on DSubs
CYKisus i uye un ´a bol inicial que ha sido
comple amen e econocido en odos los nodos de sus i uci´on donde se puede
sus i ui dicho ´a bol.
El conjun o de ´ı ems inales se de ine como:
FCYKi={[Pα,0, n, ∅]|α∈I, label(Pα) = >, label(Rα) = S}
4 Esquema ascenden e basado en Ea ley
Es e esquema, al que amos a denomina buEi, es una adap aci´on pa a TIGs
del esquema ascenden e basado en Ea ley (bo om-up Ea ley pa a CFGs
desc i o en [20]. Fue p esen ado en [7] y se puede ob ene a pa i de una
gene alizaci´on del esquema CYKi. El in e ´es de es e esquema adica en
que se a a de un econocedo con es a egia ascenden e que elimina la
es icci´on impues a po el esquema an e io sob e la o ma que deben ene
los ´a boles elemen ales.
El dominio del esquema buEies:
IbuEi=I(i)
buEi∪ I(ii)
buEi
I(i)
buEi={[Mγ→δ•ν, i, j, ∅]|Mγ→δν ∈ P(γ) , γ∈I∪A,
0≤i≤j,ν6=ε}
donde el alo ∅indica que no se ha comple ado ninguna adjunci´on en el
nodo Mγ.
7
I(ii)
buEi={[Mγ→ν•, i, j, code]|Mγ→ν∈ P(γ) , γ∈I∪A,
0≤i≤j,code ⊆ {L, R}}
donde code =∅si no se comple ´o ninguna adjunci´on sob e Mγ,code =
{L}si se comple ´o una adjunci´on izquie da sob e Mγ,code ={R}si se
comple ´o una adjunci´on de echa sob e Mγycode ={L, R}si se comple ´o
una adjunci´on izquie da y o a de echa sob e Mγ.
Los pasos deduc i os del esquema son:
DbuEi=DIni
buEi∪ DScan
buEi∪ Dε
buEi∪ DComp
buEi∪ DLAdj
buEi∪ DRadj
buEi∪ DSubs
buEi
DIni
buEi=[Nγ→ •ν, i, i, ∅]γ∈I∪A
DScan
buEi=
[a, j, j + 1]
[Nγ→δ•Mγν, i, j, ∅]
[Nγ→δMγ•ν, i, j + 1,∅]label(Mγ) = a
Dε
buEi=[Nγ→δ•Mγν, i, j, ∅]
[Nγ→δMγ•ν, i, j, ∅]
label(Mγ) = ε
´o label(Mγ) = ⊥
DComp
buEi=
[Mγ→ω•, j, k, code]
[Nγ→δ•Mγν, i, j, ∅]
[Nγ→δMγ•ν, i, k, ∅]
donde se debe cumpli :
(i) (nil ∈ladj(Mγ) y L /∈code) ´o (β∈ladj(Mγ) y L∈code),
(ii) (nil ∈ adj(Mγ) y R /∈code) ´o (β∈ adj(Mγ) y R∈code).
DLAdj
buEi=
[> → Rβ•, i, j, ∅]
[Mγ→ν•, j, k, code]
[Mγ→ν•, i, k, {L} ∪ code]
β∈ladj(Mγ)
L /∈code
DRAdj
buEi=
[> → Rβ•, j, k, ∅]
[Mγ→ν•, i, j, code]
[Mγ→ν•, i, k, {R} ∪ code]
β∈ adj(Mγ)
R /∈code
8
DSubs
buEi=
[> → Rα•, j, k, ∅]
[Nγ→δ•Mγν, i, j, ∅]
[Nγ→δMγ•ν, i, k, ∅]α∈subs (Mγ)
El paso DIni
buEiinicia el econocimien o desde odos los sub´a boles de los
´a boles elemen ales. El paso DScan
buEi econoce la p esencia de un s´ımbolo e -
minal en la cadena de en ada. Mien as Dε
buEi e leja el hecho de que se
puede sal a sob e nodos e ique ados con εy nodos pie sin ene que econo-
ce nada. El paso DComp
buEicon in´ua el econocimien o ascenden e cuando se
ha comple ado el econocimien o de un sub´a bol. El es o de pasos uncio-
nan de o ma an´aloga a los hom´onimos del esquema an e io .
El conjun o de ´ı ems inales es:
FbuEi={[> → Rα•,0, n, ∅]|α∈I, label(Rα) = S}
4.1 Una a ian e del esquema ascenden e basado en Ea ley
Si es udiamos con a enci´on el esquema buEipodemos obse a cie as de-
iciencias, las cuales son debidas esencialmen e a que el paso DIni
buEiinicia el
econocimien o de odos los sub´a boles, sin comp oba que la a´ız del mismo
sea un nodo que p esen e una es icci´on de adjunci´on izquie da obliga o ia.
Ello p o oca un doble p oblema, el p ime o es de p es aciones del analizado ,
ya que puede econoce sub´a boles que no son co ec os y cuya inco ecci´on
no se de ec a has a que se lle a a cabo un paso de compleci´on de sub´a bol.
Y de ´es o se de i a el segundo p oblema, debido a que el paso DComp
buEidebe
conoce las adjunciones que se han e ec uado an es de ealiza la compleci´on,
lo que obliga al analizado a lle a es a in o maci´on. Sin emba go, si se con-
ola el inicio del econocimien o de cada sub´a bol ob end ´ıamos un doble
bene icio: (1) aumen a ´ıamos la e iciencia eliminando del econocimien o
sub´a boles que de pa ida sabemos que son inco ec os y (2) el pa ´ame o
code se simpli ica ´ıa, ya que s´olo debe indica si u o luga una adjunci´on
de echa sob e el nodo.
El esquema que p oponemos, al que denomina emos buEk, p e ende
palia es os p oblemas. Se ob iene modi icando las condiciones la e ales de
los pasos DIni
buEiyDComp
buEi, el paso DLAdj
buEiy la o ma del pa ´ame o code del
esquema buEi.
El dominio del esquema buEkes:
IbuEk=I(i)
buEk∪ I(ii)
buEk
9
Compleci´on de sub´a bol
Es e paso deduc i o de compleci´on de sub´a bol es igual al del esquema buEk:
DComp
Ea leyi=DComp
buEk
P edicci´on de adjunci´on izquie da
Cuando el econocimien o alcanza un nodo adjun able po la izquie da, el
an´alisis debe lanza el econocimien o de odos los ´a boles auxilia es que se
pueden adjun a en ´el:
DLAdjP ed
Ea leyi=[Nγ→δ•Mγν, i, j, alse]
[> → •Rβ, j, j, alse]β∈ladj(Mγ)
Compleci´on de adjunci´on izquie da
Una ez que se ha comple ado el econocimien o de un ´a bol auxilia izquie -
do, debemos con inua el econocimien o del ´a bol donde se ha e ec uado la
adjunci´on:
DLAdjComp
Ea leyi=
[> → Rβ•, j, k, alse]
[Nγ→δ•Mγν, i, j, alse]
[Mγ→ •ν, j, k, alse]β∈ladj(Mγ)
P edicci´on de adjunci´on de echa
Cuando se comple a el econocimien o de un sub´a bol dominado po un
nodo adjun able po la de echa, el an´alisis debe lanza el econocimien o de
odos los ´a boles auxilia es que se pueden adjun a en ´el:
DRAdjP ed
Ea leyi=[Mγ→ν•, i, j, alse]
[> → •Rβ, j, j, alse]β∈ adj(Mγ)
Compleci´on de adjunci´on de echa
El paso deduc i o de compleci´on de adjunci´on de echa es igual al del esque-
ma buEk:
DRAdjComp
Ea leyi=DRAdj
buEk
P edicci´on de sus i uci´on
16

Cuando el econocimien o alcanza un nodo ma cado pa a sus i uci´on, el
an´alisis debe lanza el econocimien o de odos los ´a boles iniciales que se
pueden sus i ui en ´el:
DSubsP ed
Ea leyi=[Nγ→δ•Mγν, i, j, alse]
[> → •Rα, j, j, alse]α∈subs (Mγ)
Compleci´on de sus i uci´on
El paso deduc i o de compleci´on de sus i uci´on es igual al del esquema
buEk:
DSubsComp
Ea leyi=DSubs
buEk
El conjun o de ´ı ems inales es igual al del esquema buEk:
FEa leyi=FbuEk
7 Relaciones en e esquemas
Teo ema 7.1 Relaci´on en e los esquemas CYKiybuEi
Se man ienen las siguien es elaciones en e esquemas:
CYKisc
=⇒CYKi
1
i
=⇒CYKi
2
s
=⇒ECYKiex
=⇒buEi
P ueba
El esquema CYKi
1se ob iene desdoblando el paso de sus i uci´on del esquema
CYKien cua o.
El dominio del nue o esquema es igual al del CYKi:
ICYKi
1=ICYKi
El conjun o de pasos deduc i os es:
DCYKi
1=DScan
CYKi
1∪ Dε
CYKi
1∪ DCompUna
CYKi
1
∪ DCompBin
CYKi
1
∪ DLAdj
CYKi
1
∪ DRadj
CYKi
1
∪
DSubsUna
CYKi
1∪ DSubsBin1
CYKi
1
∪ DSubsBin2
CYKi
1
∪ DSubsBin3
CYKi
1
DScan
CYKi
1=DScan
CYKi
1
Dε
CYKi
1=Dε
CYKi
1
17
DCompUna
CYKi
1
=DCompUna
CYKi
1
DCompBin
CYKi
1
DCompBin
CYKi
1
DLAdj
CYKi
1
=DLAdj
CYKi
1
DRadj
CYKi
1
=DRadj
CYKi
1
DSubsUna
CYKi
1=[Pα, i, j, ∅]
[Mγ, i, j, ∅]
label(Pα) = >
Mγ→Oγ∈ P(γ)
α∈subs (Oγ)
DSubsBin1
CYKi
1
=
[Pα, i, j, ∅]
[Oγ
2, j, k, code]
[Mγ, i, k, ∅]
label(Pα) = >
Mγ→Oγ
1Oγ
2∈ P(γ)
α∈subs (Oγ
1)
donde se debe cumpli :
(i) (nil ∈ladj(Oγ
2)yL /∈code)´o (β∈ladj(Oγ
2)yL∈code),
(ii) (nil ∈ adj(Oγ
2)yR /∈code)´o (β∈ adj(Oγ
2)yR∈code).
DSubsBin2
CYKi
1
=
[Oγ
1, i, j, code]
[Pα, j, k, ∅]
[Mγ, i, k, ∅]
label(Pα) = >
Mγ→Oγ
1Oγ
2∈ P(γ)
α∈subs (Oγ
2)
donde se debe cumpli :
(i) (nil ∈ladj(Oγ
1)yL /∈code)´o (β∈ladj(Oγ
1)yL∈code),
(ii) (nil ∈ adj(Oγ
1)yR /∈code)´o (β∈ adj(Oγ
1)yR∈code).
DSubsBin3
CYKi
1
=
[Pα, i, j, ∅]
[Pα1, j, k, ∅]
[Mγ, i, k, ∅]
label(Pα) = >
label(Pα1) = >
Mγ→Oγ
1Oγ
2∈ P(γ)
α∈subs (Oγ
1)
α1∈subs (Oγ
2)
El conjun o de i ems inales es id´en ico al del esquema CYKi:
FCYKi
1=FCYKi
Pa a demos a que CYKisc
=⇒CYKi
1hay que p oba que:
18
1. ICYKi
1⊆ ICYKi
2. `∗
CY Ki
1
⊆`∗
CY Ki
Lo p ime o es cie o po de inici´on, ya que los dominios de ambos es-
quemas son iguales:
ICYKi
1=ICYKi
Pa a demos a que `∗
CY Ki
1
⊆`∗
CY Kinos bas a con p oba que DCYKi
1
⊆`∗
CY Ki.
Vamos a e s´olo los pasos de sus i uci´on, el es o de pasos son id´en icos en
ambos esquemas:
•Un paso deduc i o DSubsUna
CYKi
1
es equi alen e a la secuencia o mada po
un paso DSubs
CYKi
[Pα, i, j, ∅]
[Oγ, i, j, ∅]
seguido de o o DCompUna
CYKi
[Oγ, i, j, code]
[Mγ, i, j, ∅]
•Un paso deduc i o DSubsBin1
CYKi
1
es equi alen e a una secuencia o mada
po un paso DSubs
CYKi
[Pα, i, j, ∅]
[Oγ
1, i, j, ∅]
seguido de o o DCompBin
CYKi
[Oγ
1, i, j, ∅]
[Oγ
2, j, k, code]
[Mγ, i, k, ∅]
•Un paso deduc i o DSubsBin2
CYKi
1
es equi alen e a una secuencia o mada
po un paso DSubs
CYKi
[Pα, j, k, ∅]
[Oγ
2, j, k, ∅]
seguido de o o DCompBin
CYKi
[Oγ
1, i, j, code]
[Oγ
2, j, k, ∅]
[Mγ, i, k, ∅]
19
•Un paso deduc i o DSubsBin3
CYKi
1
es equi alen e a una secuencia o mada
po dos pasos DSubs
CYKi
[Pα, i, j, ∅]
[Oγ
1, i, j, ∅]
[Pα1, j, k, ∅]
[Oγ
2, j, k, ∅]
seguidos de o o DCompBin
CYKi
[Oγ
1, i, j, ∅]
[Oγ
2, j, k, ∅]
[Mγ, i, k, ∅]
El esquema CYKi
2se ob iene incluyendo eglas de p oducci´on en los
i ems del esquema CYKi
1.
El dominio de CYKi
2se de ine median e:
ICYKi
2={[Mγ→ν•, i, j, code]|Mγ→ν∈ P(γ),γ∈I∪A,
0≤i≤j,code ⊆ {L, R}}
El conjun o de pasos deduc i os es:
DCYKi
2=DScan
CYKi
2∪ Dε
CYKi
2∪ DCompUna
CYKi
2
∪ DCompBin
CYKi
2
∪ DLAdj
CYKi
2
∪ DRadj
CYKi
2
∪
DSubsUna
CYKi
2∪ DSubsBin1
CYKi
2
∪ DSubsBin2
CYKi
2
∪ DSubsBin3
CYKi
2
DScan
CYKi
2=[a, j, j + 1]
[Nγ→Pγ•, j, j + 1,∅]label(Pγ) = a
Dε
CYKi
2=[Nγ→Pγ•, j, j, ∅]label(Pγ) = ε´o label(Pγ) = ⊥
DCompUna
CYKi
2
=[Oγ→ν•, i, j, code]
[Mγ→Oγ•, i, j, ∅]
donde se debe cumpli :
(i) (nil ∈ladj(Oγ)yL /∈code)´o (β∈ladj(Oγ)yL∈code),
(ii) (nil ∈ adj(Oγ)yR /∈code)´o (β∈ adj(Oγ)yR∈code).
DCompBin
CYKi
2
=
[Oγ
1→ν•, i, j, code]
[Oγ
2→δ•, j, k, code0]
[Mγ→Oγ
1Oγ
2•, i, k, ∅]
20
donde se debe cumpli :
(i) (nil ∈ladj(Oγ
1)yL /∈code)´o (β∈ladj(Oγ
1)yL∈code),
(ii) (nil ∈ adj(Oγ
1)yR /∈code)´o (β∈ adj(Oγ
1)yR∈code),
(iii) (nil ∈ladj(Oγ
2)yL /∈code0)´o (β∈ladj(Oγ
2)yL∈code0),
(i ) (nil ∈ adj(Oγ
2)yR /∈code0)´o (β∈ adj(Oγ
2)yR∈code0).
DLAdj
CYKi
2
=
[> → Rβ•, i, j, ∅]
[Mγ→ν•, j, k, code]
[Mγ→ν•, i, k, {L} ∪ code]
β∈ladj(Mγ)
L /∈code
DRAdj
CYKi
2
=
[> → Rβ•, j, k, ∅]
[Mγ→ν•, i, j, code]
[Mγ→ν•, i, k, {R} ∪ code]
β∈ adj(Mγ)
R /∈code
DSubsUna
CYKi
2=[> → Rα•, i, j, ∅]
[Mγ→Oγ•, i, j, ∅]α∈subs (Oγ)
DSubsBin1
CYKi
2
=
[> → Rα•, i, j, ∅]
[Oγ
2→ν•, j, k, code]
[Mγ→Oγ
1Oγ
2•, i, k, ∅]α∈subs (Oγ
1)
donde se debe cumpli :
(i) (nil ∈ladj(Oγ
2)yL /∈code)´o (β∈ladj(Oγ
2)yL∈code),
(ii) (nil ∈ adj(Oγ
2)yR /∈code)´o (β∈ adj(Oγ
2)yR∈code).
DSubsBin2
CYKi
2
=
[Oγ
1→ν•, i, j, code]
[> → Rα•, j, k, ∅]
[Mγ→Oγ
1Oγ
2•, i, k, ∅]α∈subs (Oγ
2)
donde se debe cumpli :
(i) (nil ∈ladj(Oγ
1)yL /∈code)´o (β∈ladj(Oγ
1)yL∈code),
(ii) (nil ∈ adj(Oγ
1)yR /∈code)´o (β∈ adj(Oγ
1)yR∈code).
DSubsBin3
CYKi
2
=
[> → Rα•, i, j, ∅]
[> → Rα1•, j, k, ∅]
[Mγ→Oγ
1Oγ
2•, i, k, ∅]
α∈subs (Oγ
1)
α1∈subs (Oγ
2)
El conjun o de ´ı ems inales se de ine como:
FCYKi
2={[> → Rα,0, n, code]|α∈I, label(Rα) = S}
P obemos aho a la elaci´on CYKi
1
i
=⇒CYKi
2. Pa a ello debemos
mos a que exis e una unci´on egula :ICYKi
2→ ICYKi
1 al que:
21

1. ICYKi
1= (ICYKi
2)
2. 4CYKi
1= (4CYKi
2)
Una unci´on egula de con acci´on de i ems que cumple es as condiciones
es la siguien e:
([Nγ→δ•, i, j, code]) = [Nγ, i, j, code]
De se sigue inmedia amen e que ICYKi
1= (ICYKi
2)y4CYKi
1= (4CYKi
2)
po inducci´on en la longi ud de las secuencias de de i aci´on.
El esquema ECYKise ob iene a pa i del esquema buEi, es ingiendo
la clase de g am´a icas sob e las que se de ine. De o ma que el esquema
ECYKis´olo es ´a de inido pa a la clase de g am´a icas de inse ci´on de ´a boles
en las cuales ning´un nodo puede ene m´as de dos descendien es y los nodos
e ique ados con s´ımbolos e minales, εo⊥no ienen nodos he manos.
Los conjun os de i ems, pasos deduc i os y inales del esquema ECYKi
son iguales a los del esquema buEi.
IECYKi=IbuEi
DECYKi=DIni
ECYKi∪DScan
ECYKi∪Dε
ECYKi∪DComp
ECYKi∪DLAdj
ECYKi∪DRadj
ECYKi∪DSubs
ECYKi
DIni
ECYKi=DIni
buEi
DScan
ECYKi=DScan
buEi
Dε
ECYKi=Dε
buEi
DComp
ECYKi=DComp
buEi
DLAdj
ECYKi=DLAdj
buEi
DRadj
ECYKi=DRadj
buEi
DSubs
ECYKi=DSubs
buEi
FECYKi=FbuEi
Pa a demos a la elaci´on ECYKiex
=⇒buEihay que p oba :
1. CGECY Ki⊆CGbuEi
2. ECYKi(G)(a1. . . an) = buEi(G)(a1. . . an)
pa a oda G∈ CGECYKiy cadena de en ada a1. . . an
22
Lo p ime o es ob io, ya que la subclase de g am´a icas sob e la que se
de ine ECYKies un subconjun o de la clase de g am´a icas de inse ci´on de
´a boles, sob e la cual es ´a de inido el esquema buEi. Lo segundo es cie o
po de inici´on, ya que ECYKi=buEi.
A con inuaci´on p oba emos la elaci´on CYKi
2
s
=⇒ECYKi. Pa a ello
enemos que demos a que:
1. ICYKi
2⊆ IECYKi
2. `∗
CY Ki
2
⊆`∗
ECY Ki
Lo p ime o es cie o po que el dominio del esquema CYKi
2, que solo
con empla i ems con el pun o al inal de la egla, es ´a con enido en el dominio
de ECYKi:
ICYKi
2⊂ IECYKi
Pa a demos a que `∗
CY Ki
2
⊆`∗
ECY Kinos bas a con p oba que DCYKi
2
⊆`∗
ECY Ki.
Veamos cada paso:
•Un paso deduc i o DScan
CYKi
2
es equi alen e a una secuencia o mada po
un paso DIni
ECYKi
[Nγ→ •Mγ, j, j, ∅]
seguido de o o DScan
ECYKi
[a, j, j + 1]
[Nγ→ •Mγ, j, j, ∅]
[Nγ→Mγ•, j, j + 1,∅]
•Un paso deduc i o Dε
CYKi
2
es equi alen e a una secuencia o mada po
un paso DIni
ECYKi
[Nγ→ •Mγ, j, j, ∅]
seguido de o o Dε
ECYKi
[Nγ→ •Mγ, j, j, ∅]
[Nγ→Mγ•, j, j, ∅]
•Un paso deduc i o DCompUna
CYKi
2
es equi alen e a una secuencia o mada
po un paso DIni
ECYKi
[Nγ→ •Mγ, j, j, ∅]
23
seguido de o o DComp
ECYKi
[Mγ→ν•, j, k, code]
[Nγ→ •Mγ, j, j, ∅]
[Nγ→Mγ•, j, k, code]
•Un paso deduc i o DCompBin
CYKi
2
es equi alen e a una secuencia o mada
po un paso DIni
ECYKi
[Nγ→ •MγPγ, i, i, ∅]
seguido de una secuencia de dos pasos DComp
ECYKi
[Mγ→ν•, i, j, code]
[Nγ→ •MγPγ, i, i, ∅]
[Nγ→Mγ•Pγ, i, j, ∅]
[Pγ→ω•, j, k, code0]
[Nγ→Mγ•Pγ, i, j, ∅]
[Nγ→MγPγ•, i, k, ∅]
•Un paso deduc i o DSubsUna
CYKi
2
es equi alen e a una secuencia o mada
po un paso DIni
ECYKi
[Nγ→ •Mγ, j, j, ∅]
seguido de o o DSubs
ECYKi
[> → Rα•, j, k, ∅]
[Nγ→ •Mγ, j, j, ∅]
[Nγ→Mγ•, j, k, ∅]
•Un paso deduc i o DSubsBin1
CYKi
2
es equi alen e a una secuencia o mada
po un paso DIni
ECYKi
[Nγ→ •MγPγ, i, i, ∅]
seguido de uno DSubs
ECYKi
[> → Rα•, i, j, ∅]
[Nγ→ •MγPγ, i, i, ∅]
[Nγ→Mγ•Pγ, i, j, ∅]
24
y de o o DComp
ECYKi
[Pγ→ν•, j, k, code]
[Nγ→Mγ•Pγ, i, j, ∅]
[Nγ→MγPγ•, i, k, ∅]
•Un paso deduc i o DSubsBin2
CYKi
2
es equi alen e a una secuencia o mada
po un paso DIni
ECYKi
[Nγ→ •MγPγ, i, i, ∅]
seguido de uno DComp
ECYKi
[Mγ→ν•, i, j, code]
[Nγ→ •MγPγ, i, i, ∅]
[Nγ→Mγ•Pγ, i, j, ∅]
y de o o DSubs
ECYKi
[> → Rα•, j, k, ∅]
[Nγ→Mγ•Pγ, i, j, ∅]
[Nγ→MγPγ•, i, k, ∅]
•Un paso deduc i o DSubsBin3
CYKi
2
es equi alen e a una secuencia o mada
po un paso DIni
ECYKi
[Nγ→ •MγPγ, i, i, ∅]
seguido de dos DSubs
ECYKi
[> → Rα•, i, j, ∅]
[Nγ→ •MγPγ, i, i, ∅]
[Nγ→Mγ•Pγ, i, j, ∅]
[> → Rα1•, j, k, ∅]
[Nγ→Mγ•Pγ, i, j, ∅]
[Nγ→MγPγ•, i, k, ∅]
25
•Dado un paso
[Nγ→δ•Mγν, i, j, alse]
[> → •Rα, j, j, alse]∈ DSubsP ed
Ea leyi
exis e un paso
[Nγ→ •ν, j, j, alse]∈ DIni
buEk
y, po an o, exis e la in e encia
[Nγ→δ•Mγν, i, j, alse]`buEk[> → •Rα, j, j, alse]
•El es o de pasos man ienen las siguien es equi alencias:
DScan
Ea leyi=DScan
buEk
Dε
Ea leyi=Dε
buEk
DComp
Ea leyi=DComp
buEk
DRAdjComp
Ea leyi=DRAdj
buEk
DSubsComp
Ea leyi=DSubs
buEk
8 Esquema ascenden e guiado po la esquina izquie -
da
De o ma simila el esquema buLC pa a TAGs [6], es e esquema elimina
del dominio de buEkaquellos i ems que no apo an nada signi ica i o en el
p oceso de an´alisis, y que son los i ems de la o ma:
[Mγ→ •ν, i, i, alse]
Al posibili a el esquema buEkes e ipo de i ems, se p o oca un aumen o en
el n´ume o de i ems deducidos y, po an o, una me ma en el compo amien o
p ´ac ico del analizado . Po ello p oponemos modi ica el dominio y los pasos
deduc i os de dicho esquema pa a e i a que se gene en es e ipo de i ems,
ob eniendo como esul ado el esquema buLCi.
El dominio del esquema buLCies:
IbuLCi=I(i)
buLCi∪ I(ii)
buLCi
32

Ii
buLCi={[Mγ→Pγδ•ν, i, j, alse]|Mγ→δν ∈ P(γ) , γ∈I∪A,
0≤i≤j,ν6=ε}
El subconjun o I(ii)
buLCise de ine igual al del esquema buEk:
I(ii)
buLCi=I(ii)
buEk
Los pasos deduc i os del esquema son:
DbuLCi=DLC
buLCi∪ DLCε
buLCi∪ DLCsubs
buLCi∪ DLCn
buLCi∪ DLAdj
buLCi∪ DLAdjε
buLCi∪ DLAdjsubs
buLCi∪
DLAdjn
buLCi∪ Dε
buLCi∪ DScan
buLCi∪ DComp
buLCi∪ DRAdj
buLCi∪ DSubs
buLCi
DLC
buLCi=[a, j, j + 1]
[Oγ→Mγ•ν, j, j + 1, alse]
nil ∈ladj(Oγ)
label(Mγ) = a
DLCε
buLCi=[Oγ→Mγ•ν, j, j, alse]
nil ∈ladj(Oγ)
label(Mγ) = ε´o label(Mγ) = ⊥
DLCsubs
buLCi=[> → Rα•, j, k, alse]
[Oγ→Mγ•ν, j, k, alse]
nil ∈ladj(Oγ)
α∈subs (Mγ)
DLCn
buLCi=[Oγ→δ•, j, k, adj]
[Qγ→Oγ•ν, j, k, alse]
donde se debe cumpli :
(i) nil ∈ladj(Qγ),
(ii) si adj = alse en onces nil ∈ adj(Oγ).
DLAdj
buLCi=
[> → Rβ•, i, j, alse]
[a, j, j + 1]
[Qγ→Mγ•ν, i, j + 1, alse]
β∈ladj(Qγ)
label(Mγ) = a
DLAdjε
buLCi=[> → Rβ•, i, j, alse]
[Qγ→Mγ•ν, i, j, alse]
β∈ladj(Qγ)
label(Mγ) = ε´o label(Mγ) = ⊥
33
DLAdjsubs
buLCi=
[> → Rβ•, i, j, alse]
[> → Rα•, j, k, alse]
[Qγ→Mγ•ν, i, k, alse]
β∈ladj(Qγ)
α∈subs (Mγ)
DLAdjn
buLCi=
[> → Rβ•, i, j, alse]
[Oγ→δ•, j, k, adj]
[Qγ→Oγ•ν, i, k, alse]
donde se debe cumpli :
(i) β∈ladj(Qγ),
(ii) si adj = alse en onces nil ∈ adj(Oγ).
DScan
buLCi=
[a, j, j + 1]
[Nγ→Pγδ•Mγν, i, j, alse]
[Nγ→PγδMγ•ν, i, j + 1, alse]label(Mγ) = a
Dε
buLCi=[Nγ→Pγδ•Mγν, i, j, alse]
[Nγ→PγδMγ•ν, i, j, alse]label(Mγ) = ε´o label(Mγ) = ⊥
DComp
buLCi=
[Mγ→ν•, j, k, adj]
[Nγ→Pγδ•Mγν, i, j, alse]
[Nγ→PγδMγ•ν, i, k, alse]
donde se debe cumpli que si adj = alse en onces nil ∈ adj(Mγ).
El paso de compleci´on de adjunci´on de echa es igual a su hom´onimo del
esquema buEk:
DRAdj
buLCi=DRAdj
buEk
DSubs
buLCi=
[> → Rα•, j, k, alse]
[Nγ→Pγδ•Mγν, i, j, alse]
[Nγ→PγδMγ•ν, i, k, alse]α∈subs (Mγ)
La eliminaci´on del dominio de un de e minado ipo de ´ı ems p o oca que
engamos que eesc ibi el paso DIni
buEk, ob eniendo los pasos DLC
buLCi,DLCε
buLCi,
DLCsubs
buLCiyDLCn
buLCi, que se aplican cuando el s´ımbolo que es ´a a la izquie da
de la egla (la esquina izquie da) es un e minal, la cadena ac´ıa, un nodo de
sus i uci´on o un no e minal, espec i amen e. Ac uamos de o ma an´aloga
34
con la egla DLAdj
buEkpa a ob ene las cua os eglas: DLAdj
buLCi,DLAdjε
buLCi,DLAdjsubs
buLCi
yDLAdjn
buLCien es e esquema. El es o de pasos uncionan de o ma an´aloga a
sus hom´onimos en el esquema buEk, pe o los pasos DScan
buLCi,Dε
buLCiyDSubs
buLCi
s´olo se aplican a nodos que no son hijos izquie dos.
El conjun o de i ems inales es id´en ico al del esquema buEk:
FbuLCi=FbuEk
9 La elaci´on esquina izquie da en las TIGs
En las siguien es secciones amos a de ini esquemas que usan una ex en-
si´on del concep o de elaci´on de esquina izquie da (LC), conocido sob e las
CFGs, pa a il a las p edicciones en el analizado basado en el algo i mo
de Ea ley pa a TIGs. La complejidad empo al de odos es os algo i mos se
man ienen en la co a de O(n3), pe o mejo an sus p es aciones median e una
educci´on en el ama˜no del cha . An es de desc ibi los nue os analizado es
necesi amos de ini el concep o de elaci´on de esquina izquie da en las TIGs.
De inici´on 9.1 Relaci´on de esquina izquie da (LC) en los ´a boles elemen-
ales de TIGs
La esquina izquie da de un nodo Oγes su hijo izquie do Pγsi y s´olo si
ladj(Pγ) = {nil}.
La elaci´on esquina izquie da >`en VN×{VN∪VT∪{ε, ⊥}} se de ine como
Oγ>`Pγsi hay una p oducci´on Oγ→Pγν∈ P(γ)yladj(Pγ) = {nil}.
La clausu a e lexi a y ansi i a de >`la deno a emos como >∗
`.
En un abuso de no aci´on, amos a deno a como Pγ>`4si hay una
p oducci´on Oγ→Pγν∈ P(γ) y exis e un β al que β∈ladj(Pγ).
La elaci´on LC en las TIGs no a m´as all´a de los l´ımi es de un ´a bol
elemen al. Es impo an e se˜nala que oda elaci´on de LC en las TIGs
comienza en un nodo e ique ado con un s´ımbolo no e minal y inaliza en:
(1) un nodo adjun able po la izquie da; (2) un nodo e ique ado con un
s´ımbolo e minal , εo⊥; (3) ´o un nodo ma cado pa a sus i uci´on.
Las di e encias de es a de inici´on espec o a la que p esen amos pa a
TAGs en [3] son undamen almen e dos:
•Al in oduci la ope aci´on de adjunci´on, en las on e as de los ´a boles
elemen ales de las TIGs pueden apa ece nodos e ique ados con s´ımbolos
no e minales ma cados pa a sus i uci´on. ´
Es o nos obliga a in oduci
es e caso como una posibilidad de inalizaci´on en las elaciones LC.
35
•En las TIGs dis inguimos dos ipos de adjunciones: izquie da y de echa.
Las segundas no a ec an a las elaciones de esquina izquie da, pues o
que s´olo in oducen con ex os de echos en los sub´a boles. Sin emba go,
las p ime as si ompen las elaciones LC. Po es a causa ´unicamen e
enemos en cuen a los nodos adjun ables po la izquie da como in de
una elaci´on LC.
10 Un esquema LC con i ems p edic i os
Es e esquema, denominado pLCiy p esen ado en [4], se ob iene eem-
plazando los pasos p edic i os en el esquema Ea leyipo obje i os que
se in en an sa is ace de o ma ascenden e. La ase ascenden e del p oceso
de econocimien o es guiada hacia el co espondien e obje i o median e la
elaci´on LC. Po an o, en el dominio del esquema pLCi amos a dis ingui
dos ipos de i ems: p edic i os y le co ne , cuya sem´an ica es simila a la
de los i ems de la misma denominaci´on en el esquema pLC pa a TAGs [3].
El conjun o de i ems de pLCise de ine median e:
IpLCi=I(i)
pLCi∪ I(ii)
pLCi∪ I(iii)
pLCi∪ I(i )
pLCi
El conjun o de i ems p edic i os es:
I(i)
pLCi={[Mγ, j]|γ∈I∪A, 0 ≤j}
Y el conjun o de i ems le co ne iene de inido po los es siguien es
subconjun os:
I(ii)
pLCi={[Cγ;Mγ→Pγδ•ν, i, j, alse]|Cγ>∗
`Mγ,Mγ→Pγδν ∈ P(γ) ,
γ∈I∪A, 0 ≤i≤j,ν6=ε}
I(iii)
pLCi={[Cγ;Mγ→ν•, i, j, adj]|Cγ>∗
`Mγ,Mγ→ν∈ P(γ) ,
γ∈I∪A, 0 ≤i≤j, adj ∈ { ue, alse}}
donde adj = alse si no se comple ´o ninguna adjunci´on de echa sob e Mγ
y adj = ue si se comple ´o una adjunci´on de echa sob e Mγ.
I(i )
pLCi={[Cγ;Mγ→ •Pγν, j, j, alse]|Cγ>∗
`Mγ,Mγ→Pγν∈ P(γ) ,
γ∈I∪A, 0 ≤i≤j}
36
donde Pγ>`4´o exis e un α al que α∈subs (Pγ). Es deci , el pun o
s´olo apa ece al comienzo de la egla cuando el hijo izquie do sea un nodo
adjun able po la izquie da o un nodo de sus i uci´on, con obje o de lanza
el econocimien o del ´a bol auxilia izquie do ´o del ´a bol inicial, espec i a-
men e.
Con espec o al conjun o de pasos deduc i os, de inimos subconjun-
os pa a econocimien o ycompleci´on simila es a los del esquema Ea leyi
pa a TIGs. La elaci´on de esquina izquie da se aplica ´a a cinco casos de
p edicci´on: inicial, sub´a bol, pie, adjunci´on izquie da y adjunci´on de echa.
Obs´e ese que apa ece un il o sob e la p edicciones del pie, aunque es e ipo
de p edicci´on apa en emen e no apa ece en el esquema Ea leyi. Sin emba -
go, si nos ijamos con a enci´on el paso de compleci´on de adjunci´on izquie da
DRAdjComp
Ea leyihace una doble unci´on: comple a la adjunci´on izquie da e inicia
el econocimien o del sub´a bol escindido. Po ello podemos aplica un il o
sob e es a p edicci´on de pie.
Los pasos de esquina izquie da ienen en es a iedades, seg´un el ipo
de nodo en que inalice la elaci´on: e minal, cadena ac´ıa ´o nodo bo om,
y no e minal. Los nodos e ique ados con εy⊥se incluyen en el mismo
caso po que los nodos ⊥en las TIGs se compo an igual que una cadena
ac´ıa, debido que no subsumen nada. El ´ul imo caso es necesa io cuando la
esquina izquie da es un nodo de adjunci´on izquie da o es ´a ma cado pa a
sus i uci´on.
Los pasos deduc i os del esquema son:
DpLCi=DLI
pLCi∪ DLIε
pLCi∪ DLIp e
pLCi∪ DScan
pLCi∪ Dε
pLCi∪ DLC
pLCi∪
DLCε
pLCi∪ DLCp e
pLCi∪ DLCn
pLCi∪ DP e
pLCi∪ DComp
pLCi∪ DLA
pLCi∪
DLAε
pLCi∪ DLAp e
pLCi∪ DLF
pLCi∪ DLFε
pLCi∪ DLFp e
pLCi∪ DRAε
pLCi∪
DRAdjComp
pLCi∪ DLS
pLCi∪ DLSε
pLCi∪ DLSp e
pLCi∪ DSubsComp
pLCi
Fil ado de inicio
DLI
pLCi=[a, 0,1]
[>;Oα→Pα•ν, 0,1, alse]
α∈I
label(Rα) = S
label(Pα) = a
DLIε
pLCi=[>;Oα→Pα•ν, 0,0, alse]
α∈I
label(Rα) = S
label(Pα) = ε
37

DLIp e
pLCi=[>;Oα→ •Pαν, 0,0, alse]
α∈I
label(Rα) = S
Pα>`4´o ∃α0∈subs (Pα)
En el paso DLIε
pLCino incluimos la condici´on label(Pα) = ⊥po que es e
paso se aplica exclusi amen e a ´a boles iniciales.
Reconocimien o
Los pasos de econocimien o son simila es a los del esquema Ea leyipe o
s´olo se aplican a nodos que no son hijos izquie dos.
DScan
pLCi=
[a, j, j + 1]
[Cγ;Nγ→Pγδ•Mγν, i, j, alse]
[Cγ;Nγ→PγδMγ•ν, i, j + 1, alse]label(Mγ) = a
Dε
pLCi=[Cγ;Nγ→Pγδ•Mγν, i, j, alse]
[Cγ;Nγ→PγδMγ•ν, i, j, alse]label(Mγ) = ε
Fil ado de p edicci´on de sub´a bol
DLC
pLCi=
[Mγ, j]
[a, j, j + 1]
[Mγ;Oγ→Pγ•ν, j, j + 1, alse]
nil ∈ladj(Mγ)
label(Pγ) = a
DLCε
pLCi=[Mγ, j]
[Mγ;Oγ→Pγ•ν, j, j, alse]
nil ∈ladj(Mγ)
label(Pγ) = ε´o label(Pγ) = ⊥
DLCp e
pLCi=[Mγ, j]
[Mγ;Oγ→ •Pγν, j, j, alse]
nil ∈ladj(Mγ)
Pγ>`4´o ∃α∈subs (Pγ)
Compleci´on en la esquina izquie da
El paso DLCn
pLCies el que lle a a cabo las compleciones en los nodos que han
sido il ados po una elaci´on LC.
DLCn
pLCi=[Mγ;Oγ→ν•, j, k, adj]
[Mγ;Qγ→Oγ•ω, j, k, alse]Mγ6=Oγ
donde se debe cumpli que si adj = alse en onces nil ∈ adj(Oγ).
38
P edicci´on
Es e paso ealiza la p edicci´on de los nodos que dominan elaciones LC,
excep o los nodos a´ıces de los ´a boles elemen ales.
DP e
pLCi=[Cγ;Nγ→δ•Mγν, i, j, alse]
[Mγ, j]label(Mγ)∈VN
Compleci´on de sub´a bol
DComp
pLCi=
[Mγ;Mγ→ν•, j, k, adj]
[Cγ;Nγ→δ•Mγν, i, j, alse]
[Cγ;Nγ→δMγ•ν, i, k, alse]
donde se debe cumpli que si adj = alse en onces nil ∈ adj(Oγ).
Fil ado de p edicci´on de adjunci´on izquie da
DLA
pLCi=
[Mγ, j]
[a, j, j + 1]
[>;Oβ→Pβ•ν, j, j + 1, alse]
β∈ladj(Mγ)
label(Pβ) = a
DLAε
pLCi=[Mγ, j]
[>;Oβ→Pβ•ν, j, j, alse]
β∈ladj(Mγ)
label(Pβ) = ε
DLAp e
pLCi=[Mγ, j]
[>;Oβ→ •Pβν, j, j, alse]
β∈ladj(Mγ)
Pβ>`4´o ∃α∈subs (Pγ)
En el paso DLAε
pLCino incluimos la condici´on label(Pβ) = ⊥po que en un
´a bol auxilia izquie do no se puede da el caso >>∗
`⊥.
Fil ado de p edicci´on de pie
Es e conjun o de pasos son el esul ado de aplica un il o LC al paso
DLAdjComp
Ea leyi, el cual, como dijimos an es, cumple una unci´on de p edicci´on
de pie.
DLF
pLCi=
[a, k, k + 1]
[>;> → Rβ•, j, k, alse]
[Mγ, j]
[Mγ;Oγ→Pγ•ν, k, k + 1, alse]
β∈ladj(Mγ)
label(Pγ) = a
39
DLFε
pLCi=
[>;> → Rβ•, j, k, alse]
[Mγ, j]
[Mγ;Oγ→Pγ•ν, k, k, alse]
β∈ladj(Mγ)
label(Pγ) = ε´o label(Pγ) = ⊥
DLFp e
pLCi=
[>;> → Rβ•, j, k, alse]
[Mγ, j]
[Mγ;Oγ→Pγ•ν, k, k, alse]
β∈ladj(Mγ)
Pγ>`4´o ∃α∈subs (Pγ)
Fil ado de p edicci´on de adjunci´on de echa
Teniendo en cuen a que los ´a boles auxilia es de echos se ca ac e izan po que
a la izquie da de la espina no se pueden adjun a ´a boles auxilia es izquie dos
y en esa pa e de su on e a s´olo pueden apa ece nodos e ique ados con
ε, ´es o educe la inalizaci´on del il o LC sob e la a´ıces de los ´a boles
auxilia es de echos a un solo caso: ε´o ⊥.
DRAε
pLCi=[Cγ;Mγ→δ•, k, l, alse]
[>;Oβ→Pβ•ν, l, l, alse]
β∈ adj(Mγ)
label(Pβ) = ε´o label(Pβ) = ⊥
Compleci´on de adjunci´on de echa
DRAdjComp
pLCi=
[>;> → Rβ•, j, k, alse]
[Cγ;Mγ→ν•, i, j, alse]
[Mγ→ν•, i, k, ue]β∈ adj(Mγ)
Fil ado de p edicci´on de sus i uci´on
DLS
pLCi=
[Mγ, j]
[a, j, j + 1]
[>;Oα→Pα•ν, j, j + 1, alse]
α∈subs (Mγ)
label(Pα) = a
DLSε
pLCi=[Mγ, j]
[>;Oα→Pα•ν, j, j, alse]
α∈subs (Mγ)
label(Pα) = ε
DLSp e
pLCi=[Mγ, j]
[>;Oα→ •Pαν, j, j, alse]
α∈subs (Mγ)
Pα>`4
40
Compleci´on de sus i uci´on
DSubsComp
pLCi=
[>;> → Rα•, j, k, alse]
[Cγ;Nγ→δ•Mγν, i, j, alse]
[Cγ;Nγ→δMγ•ν, i, k, alse]α∈subs (Mγ)
El conjun o de i ems inales del esquema se de ine median e:
FpLCi={[>;> → Rα•,0, n, alse]|α∈I, label(Rα) = S}
11 Un esquema LC con i ems simpli icados
Vamos a de i a un nue o esquema, al que denomina emos sLCi, simpli -
icando los i ems del esquema pLCide o ma simila a como de i amos el
esquema sLC pa a TAGs en [3]. Es deci , al conjun o de i ems le co ne de
pLCiles eliminamos la pa e p edic i a y los con e imos en i ems Ea ley
en el esquema sLCi. E iden emen e, es a modi icaci´on del dominio conlle a
una adap aci´on del conjun o de pasos deduc i os.
El dominio del esquema sLCip esen a dos ipos de i ems: p edic i os y
Ea ley. Y se de ine de la siguien e mane a:
IsLCi=I(i)
sLCi∪ I(ii)
sLCi∪ I(iii)
sLCi∪ I(i )
sLCi
El conjun o de i ems p edic i os es igual al del esquema an e io :
I(i)
sLCi=I(i)
pLCi
El conjun o de i ems Ea ley es simila al del esquema Ea leyi, pe o
cie o ipo de i ems con el pun o al comienzo de las eglas son il ados del
dominio. Dicho conjun o iene de inido po los siguien es subconjun os:
I(ii)
sLCi={[Mγ→Pγδ•ν, i, j, alse]|Mγ→Pγδν ∈ P(γ) ,
γ∈I∪A, 0 ≤i≤j,ν6=ε}
I(iii)
sLCi={[Mγ→ν•, i, j, adj]|Mγ→ν∈ P(γ) ,
γ∈I∪A, 0 ≤i≤j, adj ∈ { ue, alse}}
donde adj = alse si no se comple ´o ninguna adjunci´on de echa sob e Mγ
y adj = ue si se comple ´o una adjunci´on de echa sob e Mγ.
41
Fil ado de p edicci´on de adjunci´on de echa
Es e paso deduc i o es igual a su hom´onimo del esquema sLCi:
DRAε
LCi=DRAε
sLCi
Compleci´on de adjunci´on de echa
Es e paso deduc i o es igual a su hom´onimo del esquema sLCi:
DRAdjComp
LCi=DRAdjComp
sLCi
Fil ado de p edicci´on de sus i uci´on
DLS
LCi=
[Nγ→δ•Mγω, i, j, alse]
[a, j, j + 1]
[Oα→Pα•ν, j, j + 1, alse]
>>∗
`Oα
α∈subs (Mγ)
label(Pα) = a
DLSε
LCi=[Nγ→δ•Mγω, i, j, alse]
[Oα→Pα•ν, j, j, alse]
>>∗
`Oα
α∈subs (Mγ)
label(Pα) = ε
DLSp e
LCi=[Nγ→δ•Mγω, i, j, alse]
[Oα→ •Pαν, j, j, alse]
>>∗
`Oα
α∈subs (Mγ)
Pα>`4
Compleci´on de sus i uci´on
Es e paso deduc i o es igual a su hom´onimo del esquema sLCi:
DSubsComp
LCi=DSubsComp
sLCi
El conjun o de i ems inales es igual al del esquema sLCi:
FLCi=FsLCi
48

13 Relaciones en e esquemas
Teo ema 13.1 Relaci´on en e los esquemas pLCi,sLCiyLCi
Se man ienen las siguien es elaciones de e inamien o de pasos e i ems:
LC s
=⇒sLCii
=⇒pLCi
P ueba
P ime o amos a p oba la elaci´on sLCii
=⇒pLCi. Debemos p oba que
exis e una unci´on egula :IpLCi→ IsLCi al que:
1. IsLCi= (IpLCi)
2. 4sLCi= (4pLCi)
Dada la unci´on egula :
([Cγ;Nγ→δ•ν, i, j |p, q]) = [Nγ→δ•ν, i, j |p, q]
([Cγ, j]) = [Cγ, j]
se sigue inmedia amen e que IsLCi= (IpLCi)y4sLCi= (4pLCi)po
inducci´on en la longi ud de las secuencias de de i aci´on.
Aho a p oba emos la elaci´on LCis
=⇒sLCi. Pa a ello enemos que
demos a que:
1. ILCi⊆ IsLCi
2. `∗
LCi⊆`∗
sLCi
Lo p ime o es cie o po de inici´on, ya que el dominio del esquema LCi
es ´a o mado po los conjun os de i ems de ipo Ea ley del esquema sLCi:
ILCi⊂ IsLCi
Pa a demos a que `∗
LCi⊆`∗
sLCihay que p oba que DLCi⊆`∗
sLCi. Veamos
cada paso:
•Un paso deduc i o DLC
LCies equi alen e a la secuencia o mada po un
paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLC
sLCi
[Mγ, j]
[a, j, j + 1]
[Oγ→Pγ•ν, j, j + 1, alse]
49
•Un paso deduc i o DLCε
LCies equi alen e a la secuencia o mada po un
paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLCε
sLCi
[Mγ, j]
[Oγ→Pγ•ν, j, j, alse]
•Un paso deduc i o DLCp e
LCies equi alen e a la secuencia o mada po
un paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLCp e
sLCi
[Mγ, j]
[Oγ→ •Pγν, j, j, alse]
•Un paso deduc i o DLA
LCies equi alen e a la secuencia o mada po un
paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLA
sLCi
[Mγ, j]
[a, j, j + 1]
[Oβ→Pβ•ν, j, j + 1, alse]
•Un paso deduc i o DLAε
LCies equi alen e a la secuencia o mada po un
paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLAε
sLCi
[Mγ, j]
[Oβ→Pβ•ν, j, j, alse]
50
•Un paso deduc i o DLAp e
LCies equi alen e a la secuencia o mada po
un paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLAp e
sLCi
[Mγ, j]
[Oβ→ •Pβν, j, j, alse]
•Un paso deduc i o DLF
LCies equi alen e a la secuencia o mada po un
paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLF
sLCi
[a, k, k + 1]
[> → Rβ•, j, k, alse]
[Mγ, j]
[Oγ→Pγ•ν, k, k + 1, alse]
•Un paso deduc i o DLFε
LCies equi alen e a la secuencia o mada po un
paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLFε
sLCi
[> → Rβ•, j, k, alse]
[Mγ, j]
[Oγ→Pγ•ν, k, k, alse]
•Un paso deduc i o DLFp e
LCies equi alen e a la secuencia o mada po
un paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLFp e
sLCi
[> → Rβ•, j, k, alse]
[Mγ, j]
[Oγ→ •Pγν, k, k, alse]
51
•Un paso deduc i o DLS
LCies equi alen e a la secuencia o mada po un
paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLS
sLCi
[Mγ, j]
[a, j, j + 1]
[Oα→Pα•ν, j, j + 1, alse]
•Un paso deduc i o DLSε
LCies equi alen e a la secuencia o mada po un
paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLSε
sLCi
[Mγ, j]
[Oα→Pα•ν, j, j, alse]
•Un paso deduc i o DLSp e
LCies equi alen e a la secuencia o mada po
un paso DP e
sLCi
[Nγ→δ•Mγν, i, j, alse]
[Mγ, j]
seguido de o o DLSp e
sLCi
[Mγ, j]
[Oα→ •Pαν, j, j, alse]
•El es o de pasos hom´onimos en ambos esquemas son iguales.
Teo ema 13.2 Relaci´on en e los esquemas buLCiyLCi
Se man iene la siguien es elaciones de e inamien o de pasos y il os din´amicos:
buLCis
=⇒buLCi
1
d
=⇒LCi
1
d
⇐=LCi
P ueba
El esquema buLCi
1se ob iene median e la ampliaci´on del dominio de buLCi
con i ems con el pun o al comienzo de la egla cuando el hijo izquie do sea
52
un nodo adjun able o ma cado pa a sus i uci´on. Po an o, el conjun o de
i ems pa a es e esquema es igual al del esquema LCi:
IbuLCi
1=ILCi
Hay que adap a el conjun o de pasos deduc i os al nue o dominio:
DbuLCi
1=DLC
buLCi
1
∪DLCε
buLCi
1
∪DLCp e
buLCi
1
∪DLCn
buLCi
1
∪DLAdj
buLCi
1
∪DLAdjε
buLCi
1
∪DLAdjp e
buLCi
1
∪
DLAdjn
buLCi
1
∪ Dε
buLCi
1∪ DScan
buLCi
1∪ DComp
buLCi
1
∪ DRAdj
buLCi
1
∪ DSubs
buLCi
1
donde odos los pasos son id´en icos al los hom´onimos de buLCi, excep o el
paso DSubs
buLCi
1
y los nue os pasos DLCp e
buLCi
1
yDLAdjp e
buLCi
1
.
DLC
buLCi
1
=DLC
buLCi
DLCε
buLCi
1
=DLCε
buLCi
DLCn
buLCi
1
=DLCn
buLCi
DLAdj
buLCi
1
=DLAdj
buLCi
DLAdjε
buLCi
1
=DLAdjε
buLCi
DLAdjn
buLCi
1
=DLAdjn
buLCi
DScan
buLCi
1=DScan
buLCi
Dε
buLCi
1=Dε
buLCi
DComp
buLCi
1
=DComp
buLCi
DRAdj
buLCi
1
=DRAdj
buLCi
DLCp e
buLCi
1
=[Oγ→ •Pγν, j, j, alse]
nil ∈ladj(Oγ)
Pγ>`4´o ∃α∈subs (Pγ)
DLAdjp e
buLCi
1
=[> → Rβ•, i, j, alse]
[Oγ→ •Pγν, j, j, alse]
β∈ladj(Oγ)
Pγ>`4´o ∃α∈subs (Pγ)
DSubs
buLCi
1=
[> → Rα•, j, k, alse]
[Nγ→δ•Mγν, i, j, alse]
[Nγ→δMγ•ν, i, k, alse]α∈subs (Mγ)
53

El conjun o de i ems inales es igual al del esquema buLCi:
FbuLCi
1=FbuLCi
P obemos aho a que buLCis
=⇒buLCi
1, pa a lo cual se iene que
cumpli que:
1. IbuLCi⊆ IbuLCi
1
2. `∗
buLCi⊆`∗
buLCi
1
Lo p ime o es cie o po de inici´on, ya que el dominio del esquema
buLCi
1es ´a o mado po los i ems del esquema buLCiampliado con i ems
con el pun o a comienzo de la egla. Po an o:
IbuLCi⊂ IbuLCi
1
Pa a demos a que `∗
buLCi⊆`∗
buLCi
1
nos bas a con p oba que DbuLCi⊆`∗
buLCi
1
.
Veamos ´unicamen e los pasos en que di ie en:
•Un paso deduc i o DLCsubs
buLCies equi alen e a una secuencia o mada po
una paso DLCp e
buLCi
1
[Oγ→ •Pγν, j, j, alse]
seguido de o o DSubs
buLCi
1
[> → Rα•, j, k, alse]
[Oγ→ •Pγν, j, j, alse]
[Oγ→Pγ•ν, j, k, alse]
•Un paso deduc i o DLAdjsubs
buLCies equi alen e a una secuencia o mada
po una paso DLAdjp e
buLCi
1
[> → Rβ•, i, j, alse]
[Oγ→ •Pγν, j, j, alse]
seguido de o o DSubs
buLCi
1
[> → Rα•, j, k, alse]
[Oγ→ •Pγν, j, j, alse]
[Oγ→Pγ•ν, j, k, alse]
54
•Un paso deduc i o DSubs
buLCies ´a incluido en la in e encia del paso DSubs
buLCi
1
,
ya que es e ´ul imo con empla la ope aci´on de sus i uci´on en cualquie
posici´on, mien as el p ime o s´olo es ´alido pa a sus i uciones en no-
dos que no sean hijos izquie dos. Po an o:
DSubs
buLCi⊂ DSubs
buLCi
1
El esquema LCi
1se ob iene desdoblando el paso DComp
LCidel esquema LCi
en los pasos DComp1
LCi
1
yDComp2
LCi
1
, donde el p ime o se enca ga de comple a
los sub´a boles en nodos que no son hijos izquie dos, mien as el segundo las
comple an en los hijos izquie dos.
El dominio de LCi
1es igual al del esquema o iginal:
ILCi
1=ILCi
El conjun o de pasos deduc i os del nue o esquema es:
DLCi
1=DLI
LCi
1
∪ DLIε
LCi
1
∪ DLIp e
LCi
1
∪ DScan
LCi
1∪ Dε
LCi
1∪ DLC
LCi
1
∪
DLCε
LCi
1
∪ DLCp e
LCi
1
∪ DLCn
LCi
1
∪ DComp1
LCi
1
∪ DComp2
LCi
1
∪ DLA
LCi
1
∪
DLAε
LCi
1
∪ DLAp e
LCi
1
∪ DLF
LCi
1
∪ DLFε
LCi
1
∪ DLFp e
LCi
1
∪ DRAε
LCi
1
∪
DRAdjComp
LCi
1
∪ DLS
LCi
1
∪ DLSε
LCi
1
∪ DLSp e
LCi
1
∪ DSubsComp
LCi
1
donde odos los pasos deduc i os son iguales a sus hom´onimos del esquema
LCi, excep o los dos nue os ob enidos median e el desdoble.
DLI
LCi
1
=DLI
LCi
DLIε
LCi
1
=DLIε
LCi
DLIp e
LCi
1
=DLIp e
LCi
DScan
LCi
1=DScan
LCi
Dε
LCi
1=Dε
LCi
DLC
LCi
1
=DLC
LCi
DLCε
LCi
1
=DLCε
LCi
55
DLCp e
LCi
1
=DLCp e
LCi
DLCn
LCi
1
=DLCn
LCi
DLA
LCi
1
=DLA
LCi
DLAε
LCi
1
=DLAε
LCi
DLAp e
LCi
1
=DLAp e
LCi
DLF
LCi
1
=DLF
LCi
DLFε
LCi
1
=DLFε
LCi
DLFp e
LCi
1
=DLFp e
LCi
DRAε
LCi
1
=DRaε
LCi
DRAdjComp
LCi
1
=DRAdjComp
LCi
DLS
LCi
1
=DLS
LCi
DLSε
LCi
1
=DLSε
LCi
DLSp e
LCi
1
=DLSp e
LCi
DSubsComp
LCi
1
=DSubsComp
LCi
DComp1
LCi
1
=
[Mγ→ν•, j, k, adj]
[Nγ→Pγδ•Mγω, i, j, alse]
[Nγ→PγδMγ•ν, i, k, alse]
donde se debe cumpli que si adj = alse en onces nil ∈ adj(Oγ).
DComp2
LCi
1
=
[Mγ→ν•, j, k, adj]
[Nγ→ •Mγω, j, j, alse]
[Nγ→Mγ•ν, j, k, alse]
donde se debe cumpli que si adj = alse en onces nil ∈ adj(Oγ).
El conjun o de i ems inales ambi´en es igual al del esquema LCi:
ILCi
1=ILCi
Pa a p oba que LCid
=⇒LCi
1 enemos que demos a que:
56
1. ILCi
1⊆ ILCi
2. `LCi
1⊆`LCi
Lo p ime o es cie o po de inici´on, ya que los dominios de ambos es-
quemas son iguales:
ILCi
1=ILCi
Pa a p oba que `LCi
1⊆`LCidebemos demos a que DLCi
1
⊆`LCi. S´olo
amos a conside a los dos pasos sob e los que se aplica el il o din´amico,
el es o son id´en icos:
•Dado un paso
[Mγ→ν•, j, k, adj]
[Nγ→Pγδ•Mγω, i, j, alse]
[Nγ→PγδMγ•ν, i, k, alse]∈ DComp1
LCi
1
exis e un paso
[Mγ→ν•, j, k, adj]
[Nγ→δ•Mγω, i, j, alse]
[Nγ→δMγ•ν, i, k, alse]∈ DComp
LCi
y, po an o, exis e la in e encia
[Mγ→ν•, j, k, adj]
[Nγ→Pγδ•Mγω, i, j, alse]`LCi[Nγ→PγδMγ•ν, i, k, alse]
•Dado un paso
[Mγ→ν•, j, k, adj]
[Nγ→ •Mγω, j, j, alse]
[Nγ→Mγ•ν, j, k, alse]∈ DComp2
LCi
1
exis e un paso
[Mγ→ν•, j, k, adj]
[Nγ→δ•Mγω, i, j, alse]
[Nγ→δMγ•ν, i, k, alse]∈ DComp
LCi
y, po an o, exis e la in e encia
[Mγ→ν•, j, k, adj]
[Nγ→ •Mγω, j, j, alse]`LCi[Nγ→Mγ•ν, j, k, alse]
57
Teo ema 13.3 Relaci´on en e los esquemas buEkybuLCi
Se man iene la siguien e elaci´on de con acci´on de secuencias deduc i as:
buEksc
=⇒buLCi
P ueba
Tenemos que demos a que:
1. IbuLCi⊆ IbuEk
2. `∗
buLCi⊆`∗
buEk
Lo p ime o es cie o po de inici´on, ya que el dominio del esquema
buLCies igual al del esquema buEkal que le hemos sup imido los i ems
con el pun o al comienzo de la egla:
IbuLCi⊂ IbuEk
Pa a p oba que `∗
buLCi⊆`∗
buEkdebemos demos a que DbuLCi⊆`∗
buEk.
Veamos cada uno de los pasos:
•Un paso deduc i o DLC
buLCies equi alen e a la secuencia o mada po
un paso DIni
buEk
[Oγ→ •Pγν, j, j, alse]
seguido de o o DScan
buEk
[a, j, j + 1]
[Oγ→ •Pγν, j, j, alse]
[Oγ→δPγ•ν, j, j + 1, alse]
•Un paso deduc i o DLCε
buLCies equi alen e a la secuencia o mada po
un paso DIni
buEk
[Oγ→ •Pγν, j, j, alse]
seguido de o o Dε
buEk
[Oγ→ •Pγν, j, j, alse]
[Oγ→Pγ•ν, j, j, alse]
64

•Un paso deduc i o DLCsubs
buLCies equi alen e a la secuencia o mada po
un paso DIni
buEk
[Oγ→ •Pγν, j, j, alse]
seguido de o o DSubs
buEk
[> → Rα•, j, k, alse]
[Oγ→ •Pγν, j, j, alse]
[Oγ→Pγ•ν, j, k, alse]
•Un paso deduc i o DLCn
buLCies equi alen e a la secuencia o mada po
un paso DIni
buEk
[Qγ→ •Oγω, j, j, alse]
seguido de o o DComp
buEk
[Oγ→ν•, j, k, adj]
[Qγ→ •Oγω, j, j, alse]
[Qγ→Oγ•ω, j, k, alse]
•Un paso deduc i o DLAdj
buLCies equi alen e a la secuencia o mada po
un paso DLAdj
buEk
[> → Rβ•, i, j, alse]
[Oγ→ •Pγν, i, j, alse]
seguido de o o DScan
buEk
[a, j, j + 1]
[Oγ→ •Pγν, i, j, alse]
[Oγ→δPγ•ν, i, j + 1, alse]
•Un paso deduc i o DLAdjε
buLCies equi alen e a la secuencia o mada po
un paso DLAdj
buEk
[> → Rβ•, i, j, alse]
[Oγ→ •Pγν, i, j, alse]
seguido de o o Dε
buEk
[Oγ→ •Pγν, i, j, alse]
[Oγ→Pγ•ν, i, j, alse]
65
•Un paso deduc i o DLAdjsubs
buLCies equi alen e a la secuencia o mada po
un paso DLAdj
buEk
[> → Rβ•, i, j, alse]
[Oγ→ •Pγν, i, j, alse]
seguido de o o DSubs
buEk
[> → Rα•, j, k, alse]
[Oγ→ •Pγν, i, j, alse]
[Oγ→Pγ•ν, i, k, alse]
•Un paso deduc i o DLAdjn
buLCies equi alen e a la secuencia o mada po
un paso DLAdj
buEk
[> → Rβ•, i, j, alse]
[Qγ→ •Oγν, i, j, alse]
seguido de o o DComp
buEk
[Oγ→ν•, j, k, adj]
[Qγ→ •Oγω, i, j, alse]
[Qγ→Oγ•ω, i, k, alse]
•El es o de pasos deduc i os del esquema buLCies ´an incluidos en
las in e encias de sus hom´onimos del esquema buEk, ya que es os
´ul imos con emplan las ope aciones en cualquie posici´on, mien as
que los pe enecien es a buLCis´olo son aplicables en nodos que no
sean hijos izquie dos. Po an o, se cumple:
DScan
buLCi⊂ DScan
buEk
Dε
buLCi⊂ Dε
buEk
DComp
buLCi⊂ DComp
buEk
DSubs
buLCi⊂ DSubs
buEk
Teo ema 13.4 Relaci´on en e los esquemas Ea leyiyLCi
Se man iene la siguien e elaci´on de con acci´on de secuencias deduc i as:
Ea leyisc
=⇒LCi
P ueba
Tenemos que demos a que:
66
1. ILCi⊆ IEa leyi
2. `∗
LCi⊆`∗
Ea leyi
Lo p ime o es cie o po de inici´on, ya que el dominio del esquema LCi
es igual al del esquema Ea leyial que le hemos sup imido un subconjun o
de los i ems con el pun o al comienzo de la egla:
ILCi⊂ IEa leyi
Pa a p oba que `∗
LCi⊆`∗
Ea leyidebemos demos a que DLCi⊆`∗
Ea leyi.
Veamos cada uno de los pasos:
•Un paso DLI
LCies equi alen e a la secuencia o mada po un paso DIni
Ea leyi
[> → •Rα,0,0, alse]
seguido de una secuencia de pasos DP ed
Ea leyi
[> → •Rα,0,0, alse]
[Rα→ •Mγν, 0,0, alse]
[Mγ→ •Oγν, 0,0, alse]
[Oγ→ •Pγδ, 0,0, alse]
y de un paso DScan
Ea leyi
[Oγ→ •Pγν, 0,0, alse]
[a, 0,1]
[Oγ→Pγ•ν, 0,1, alse]
•Un paso DLIε
LCies equi alen e a la secuencia o mada po un paso DIni
Ea leyi
[> → •Rα,0,0, alse]
seguido de una secuencia de pasos DP ed
Ea leyi
[> → •Rα,0,0, alse]]
[Rα→ •Mγν, 0,0, alse]
[Mγ→ •Oγν, 0,0, alse]
[Oγ→ •Pγδ, 0,0, alse]
y de un paso Dε
Ea leyi
[Oγ→ •Pγν, 0,0, alse]
[Oγ→Pγ•ν, 0,0, alse]
67
•Un paso DLIp e
LCies equi alen e a la secuencia o mada po un paso
DIni
Ea leyi
[> → •Rα,0,0, alse]
seguido de una secuencia de pasos DP ed
Ea leyi
[> → •Rα,0,0, alse]
[Rα→ •Mγν, 0,0, alse]
[Mγ→ •Oγν, 0,0, alse]
[Oγ→ •Pγδ, 0,0, alse]
•Un paso DLC
LCies equi alen e a una secuencia de pasos DP ed
Ea leyi
[Nγ→δ•Mγν, i, j, alse]
[Mγ→ •Oγω, j, j, alse]
[Mγ→ •Oγω, j, j, alse]
[Oγ→ •Pγν, j, j, alse]
seguida de un paso DScan
Ea leyi
[Oγ→ •Pγν, j, j, alse]
[a, j, j + 1]
[Oγ→Pγ•ν, j, j + 1, alse]
•Un paso DLCε
LCies equi alen e a una secuencia de pasos DP ed
Ea leyi
[Nγ→δ•Mγν, i, j, alse]
[Mγ→ •Oγω, j, j, alse]
[Mγ→ •Oγω, j, j, alse]
[Oγ→ •Pγν, j, j, alse]
seguida de un paso Dε
Ea leyi
[Oγ→ •Pγν, j, j, alse]
[Oγ→Pγ•ν, j, j, alse]
•Un paso DLCp e
LCies equi alen e a una secuencia de pasos DP ed
Ea leyi:
[Nγ→δ•Mγν, i, j, alse]
[Mγ→ •Oγω, j, j, alse]
[Mγ→ •Oγω, j, j, alse]
[Oγ→ •Pγν, j, j |, alse]
68
•Un paso DLCn
LCies equi alen e a una secuencia de pasos DP ed
Ea leyi
[Nγ→δ•Mγν, i, j, alse]
[Mγ→ •Oγω, j, j, alse]
[Mγ→ •Oγω, j, j, alse]
[Oγ→ •Pγν, j, j, alse]
seguida de un paso DComp
Ea leyi
[Pγ→δ•, j, k, adj]
[Oγ→ •Pγν, j, j, alse]
[Oγ→Pγ•ν, j, k, alse]
•Un paso DLA
LCies equi alen e a la secuencia o mada po un paso
DLAdjP ed
Ea leyi
[Nγ→δ•Mγν, i, j, alse]
[> → •Rβ, j, j, alse]
una secuencia de pasos DP ed
Ea leyi
[> → •Rβ, j, j, alse]
[Rβ→ •Mβω, j, j, alse]
[Mβ→ •Oβω, j, j, alse]
[Oβ→ •Pβν, j, j, alse]
y un paso DScan
Ea leyi
[Oβ→ •Pβν, j, j, alse],
[a, j, j + 1]
[Oβ→Pβ•ν, j, j + 1, alse]
•Un paso DLAε
LCies equi alen e a la secuencia o mada po un paso
DLAdjP ed
Ea leyi
[Nγ→δ•Mγν, i, j, alse]
[> → •Rβ, j, j, alse]
una secuencia de pasos DP ed
Ea leyi
[> → •Rβ, j, j, alse]
[Rβ→ •Mβω, j, j, alse]
69

[Mβ→ •Oβω, j, j, alse]
[Oβ→ •Pβν, j, j, alse]
y un paso Dε
Ea leyi
[Oβ→ •Pβν, j, j, alse]
[Oβ→Pβ•ν, j, j, alse]
•Un paso DLAp e
LCies equi alen e a la secuencia o mada po un paso
DLAdjP ed
Ea leyi
[Nγ→δ•Mγν, i, j, alse]
[> → •Rβ, j, j, alse]
seguido de una secuencia de pasos DP ed
Ea leyi
[> → •Rβ, j, j, alse]
[Rβ→ •Mβω, j, j, alse]
[Mβ→ •Oβω, j, j, alse]
[Oβ→ •Pβν, j, j, alse]
•Un paso DLF
LCies equi alen e a la secuencia o mada po un paso
DLAdjComp
Ea leyi
[> → Rβ•, j, k, alse]
[Oγ→δ•Nγν, i, j, alse]
[Nγ→ •Mγν, j, k, alse]
una secuencia de pasos DP ed
Ea leyi
[Nγ→ •Mγν, k, k, alse]
[Mγ→ •Oγω, k, k, alse]
[Mγ→ •Oγω, k, k, alse]
[Oγ→ •Pγν, k, k, alse]
y un paso DScan
Ea leyi
[Oγ→ •Pγν, k, k, alse]
[a, k, k + 1]
[Oγ→Pγ•ν, k, k + 1, alse]
70
•Un paso DLFε
LCies equi alen e a la secuencia o mada po un paso
DLAdjComp
Ea leyi
[> → Rβ•, j, k, alse]
[Oγ→δ•Nγν, i, j, alse]
[Nγ→ •Mγν, j, k, alse]
una secuencia de pasos DP ed
Ea leyi
[Nγ→ •Mγν, k, k, alse]
[Mγ→ •Oγω, k, k, alse]
[Mγ→ •Oγω, k, k, alse]
[Oγ→ •Pγν, k, k, alse]
y un paso Dε
Ea leyi
[Oγ→ •Pγν, k, k, alse]
[Oγ→Pγ•ν, k, k, alse]
•Un paso DLFp e
LCies equi alen e a la secuencia o mada po un paso
DLAdjComp
Ea leyi
[> → Rβ•, j, k, alse]
[Oγ→δ•Nγν, i, j, alse]
[Nγ→ •Mγν, j, k, alse]
seguido de una secuencia de pasos DP ed
Ea leyi
[Nγ→ •Mγν, k, k, alse]
[Mγ→ •Oγω, k, k, alse]
[Mγ→ •Oγω, k, k, alse]
[Oγ→ •Pγν, k, k, alse]
•Un paso DRAε
LCies equi alen e a la secuencia o mada po un paso
DRAdjP ed
Ea leyi
[Nγ→δ•, i, j, alse]
[> → •Rβ, j, j, alse]
una secuencia de pasos DP ed
Ea leyi
[> → •Rβ, j, j, alse]
[Rβ→ •Mβω, j, j, alse]
71
[Mβ→ •Oβω, j, j, alse]
[Oβ→ •Pβν, j, j, alse]
y un paso Dε
Ea leyi
[Oβ→ •Pβν, j, j, alse]
[Oβ→Pβ•ν, j, j, alse]
•Un paso DLS
LCies equi alen e a la secuencia o mada po un paso DSubsP ed
Ea leyi
[Nγ→δ•Mγν, i, j, alse]
[> → •Rα, j, j, alse]
una secuencia de pasos DP ed
Ea leyi
[> → •Rα, j, j, alse]
[Rα→ •Mαω, j, j, alse]
[Mα→ •Oαω, j, j, alse]
[Oα→ •Pαν, j, j, alse]
y un paso DScan
Ea leyi
[Oα→ •Pαν, j, j, alse],
[a, j, j + 1]
[Oα→Pα•ν, j, j + 1, alse]
•Un paso DLSε
LCies equi alen e a la secuencia o mada po un paso
DSubsP ed
Ea leyi
[Nγ→δ•Mγν, i, j, alse]
[> → •Rα, j, j, alse]
una secuencia de pasos DP ed
Ea leyi
[> → •Rα, j, j, alse]
[Rα→ •Mαω, j, j, alse]
[Mα→ •Oαω, j, j, alse]
[Oα→ •Pαν, j, j, alse]
y un paso Dε
Ea leyi
[Oα→ •Pαν, j, j, alse]
[Oα→Pα•ν, j, j, alse]
72
•Un paso DLSp e
LCies equi alen e a la secuencia o mada po un paso
DSubsP ed
Ea leyi
[Nγ→δ•Mγν, i, j, alse]
[> → •Rα, j, j, alse]
seguido de una secuencia de pasos DP ed
Ea leyi
[> → •Rα, j, j, alse]
[Rα→ •Mαω, j, j, alse]
[Mα→ •Oαω, j, j, alse]
[Oα→ •Pαν, j, j, alse]
•Los pasos deduc i os de econocimien o del esquema LCies ´an inclui-
dos en las in e encias de sus hom´onimos del esquema Ea leyi, ya que
es os ´ul imos con emplan las ope aciones en cualquie posici´on, mien-
as que los pe enecien es a LCis´olo son aplicables en nodos que no
sean hijos izquie dos. Po an o, se cumple:
DScan
LCi⊂ DScan
Ea leyi
Dε
LCi⊂ Dε
Ea leyi
•El es o de pasos son id´en icos en ambos esquemas:
DComp
LCi=DComp
Ea leyi
DRAdjComp
LCi=DRAdjComp
Ea leyi
DSubsComp
LCi=DSubsComp
Ea leyi
Re e encias
[1] Alonso, M. A., ”In e p e aci´on abula de au ´oma as pa a lenguajes de
adjunci´on de ´a boles”, Tesis doc o al, Uni e sidade da Co u˜na, Espa˜na,
2000.
[2] Alonso, M. A., Cab e o, D. , de la Cle ge ie, E. y Vila es, M., ”Tabula
algo i hms o TAG pa sing”, En P oc. o EACL’99, p´aginas 150–157,
Be gen, No uega, 1999.
73