Algoritmos de análisis para gramáticas de inserción de árboles: Relaciones (LSI-2003-01)

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