Esquemas basados en Left Corner sin prefijo válido para TAGs: Relaciones (LSI-2002-03)

Esquemas basados en Left Corner sin prefijo v´alido para TAGs: Relaciones Vicente Carrillo Departamento de Lenguajes y Sistemas Inform´aticos Universidad de Sevilla [email protected] Resumen Las Gram´aticas de Adjunci´on de ´ Arboles (TAGs, Tree Adjoining Grammars) es un formalismo ampliamente usado en el procesamiento del lenguaje natural, sin embargo, el coste computacional te´orico que requieren los analizadores sint´acticos definidos para el mismo es excesivamente elevado respecto al requerido en otros formalismos tambi´en muy empleados, aunque con menor poder expresivo, como podr´ıan ser las Gram´aticas Independientes del Contexto (CFGs, Context Free Grammars). En la literatura podemos encontrar numerosos trabajos que intentan minimizar el coste real del an´alisis, ya sea aplicando restricciones al formalismo ´o aplicando t´ecnicas de compactaci´on de gram´aticas. Nuestra propuesta va en la l´ınea de aumentar las prestaciones pr´acticas de los analizadores basados en Earley para TAGs, mediante la aplicaci´on de un filtro left corner al estilo de los ya conocidos para CFGs. En este trabajo mostramos cuatro nuevos analizadores para TAGs que hacen uso de este tipo filtrado y establecemos las relaciones formales que existen entre ellos. Usaremos los esquemas de an´alisis como m´etodo general para descripci´on de algoritmos de an´alisis sint´actico, ya que, entre otras ventajas, nos permiten definir analizadores sint´acticos de manera abstracta y establecer relaciones formales entre ellos. 1 Introducci´on Las Gram´aticas de Adjunci´on de ´ Arboles (TAGs) fueron definidas inicialmente por Joshi, Levy y Takahashi en [Joshi et al.,75]. Posteriormente el propio Joshi establece la definici´on moderna de TAG en [Joshi, 87]. Una 1 descripci´on detallada del formalismo y sus propiedades se pueden encontrar en [Joshi y Schabes, 97]. Las gram´aticas de adjunci´on de ´arboles constituyen un formalismo gramatical que utiliza ´arboles como elementos de composici´on b´asicos, frente a las producciones usadas en formalismos como las gram´aticas incontextuales (CFGs). Asimismo utiliza como operaci´on de composici´on b´asica la operaci´on de adjunci´on, la cual permite una potencia expresiva superior a la de las gram´aticas incontextuales. La importancia de las gram´aticas de adjunci´on de ´arboles viene dada porque todas sus estructuras se encuentran lexicalizadas de manera natural y aporta un dominio de localidad extendido, con los beneficios tanto ling¨u´ısticos como computacionales que estas caracter´ısticas conllevan. Los analizadores para TAGs que se encuentran en la literatura habitualmente son adaptaciones de analizadores estudiados para gram´aticas incontextuales. En concreto, y por la relevancia que tiene para este trabajo, podemos citar el analizador ascendente basado en Earley (buE,bottom-up Earley) o el analizador ascendente-predictivo tipo Earley (E,Earley) para TAGs que se describen en [Alonso et al., 99b]. En esta memoria, y como punto de partida, presentamos un analizador que utiliza una estrategia ascendente guiada por la esquina izquierda para TAGs como una adaptaci´on para este formalismo del analizador buLC1(bottom-up Left Corner) para CFGs descrito en [Sikkel, 97]. Mostraremos como se puede extender el concepto de left corner (esquina izquierda) conocido para CFGs al formalismo TAGs, con objeto de obtener tres analizadores que mejoran las prestaciones del ya definido Emediante una reducci´on en el n´umero de ´ıtems deducidos. Una vez introducidos los cuatro nuevos analizadores, estableceremos y demostraremos las relaciones formales que presentan entre ellos. Para especificar todos los analizadores usaremos los esquemas de an´alisis sint´actico [Sikkel, 97]. En esta secci´on se introducir´an los conceptos b´asicos, tanto de las gram´aticas de adjunci´on de ´arboles como de los esquemas de an´alisis, necesarios para la comprensi´on de los algoritmos descritos en el resto del informe. Por claridad y mantenimiento de la l´ınea argumental del trabajo, en las secciones 2 y 4 se describen los esquemas buE yEpara TAGs. En la secci´on 3 analizamos las posibles mejoras que se pueden introducir a buE, y c´omo desde ´estas se deriva el nuevo esquema buLC. En la secci´on 5 introducimos el concepto de relaci´on de esquina izquierda (left corner) en las gram´aticas de adjunci´on de ´arboles y lo usamos para definir un nuevo esquema, al 1Utilizaremos el subrayado para indicar que un determinado esquema est´a definido para CFGs y permitir de este modo distinguirlo del esquema del mismo nombre definido para TAGs. 2 que denominamos pLC(predictive left corner). En la secci´on 6 se presenta un esquema intermedio, que denominamos sLC(simplified left corner), que servir´a de ”puente”para definir finalmente el esquema LC(left corner) en la secci´on 7. Por ´ultimo, la secci´on 8 incluye las relaciones que existen entre los analizadores presentados y las demostraciones de las mismas. 1.1 Las Gram´aticas de Adjunci´on de ´ Arboles Formalmente una TAG es una qu´ıntupla (VN, VT, S, I,A), donde VNes el conjunto finito de s´ımbolos no terminales, VTes el conjunto finito de s´ımbolos terminales, S∈VNes el axioma de la gram´atica, I∪Aes un conjunto finito de ´arboles finitos denominados ´arboles elementales. A los ´arboles del conjunto Ise les denomina ´arboles iniciales, y se caracterizan porque todos sus nodos interiores est´an etiquetados con s´ımbolos de VN, mientras los nodos de su frontera se etiquetan con s´ımbolos de VTo la cadena vac´ıa ². A los ´arboles del conjunto Ase les denomina ´arboles auxiliares, y se caracterizan porque todos sus nodos interiores est´an etiquetados con s´ımbolos de VN, mientras los nodos de su frontera se etiquetan con s´ımbolos de VTo la cadena vac´ıa ², salvo uno, denominado pie, que est´a etiquetado con el mismo s´ımbolo que la ra´ız del ´arbol. El camino que va desde la ra´ız hasta el pie se denomina espina. Vamos a denotar con Mγun nodo interior perteneciente a un ´arbol elemental γ. Nos referiremos a la ra´ız de un ´arbol elemental γcomo Rγy al pie de un ´arbol auxiliar βcomo Fβ. Los otros nodos frontera los denotaremos con sus etiquetas. A diferencia de las gram´aticas incontextuales, en las cuales se usa la sustituci´on de reglas como operaci´on de composici´on, en las TAGs la composici´on de estructuras m´as complejas se lleva a cabo mediante la operaci´on de adjunci´on. Esta operaci´on, que dota a las TAGs de una potencia expresiva superior a las CFGs, consiste en lo siguiente: dado un nodo Mγ etiquetado con el mismo s´ımbolo que la ra´ız de un ´arbol auxiliar Rβ, la adjunci´on de βen Mγescinde el sub´arbol que pende de Mγ, pega el ´arbol auxiliar βen Mγy, por ´ultimo, pega el sub´arbol escindido en el nodo pie Fβ. Denotaremos mediante β∈adj(Mγ) que el ´arbol auxiliar βpueda ser adjuntado en el nodo Mγ. Si un nodo no tiene adjunci´on obligatoria entonces nil ∈adj(Mγ), donde nil es un s´ımbolo vac´ıo que no pertenece al conjunto de ´arboles auxiliares. Para usar esquemas de an´alisis como m´etodo de especificaci´on es habitual representar mediante reglas el reconocimiento parcial de los ´arboles elementales [D´ıaz et al., 98b]. Por tanto, es necesario traducir cada ´arbol 3 elemental γen un conjunto de producciones P(γ) de la siguiente manera: P(γ) = {Nγ→Nγ 1. . . Nγ g} donde Nγes un nodo interior de γyNγ 1. . . Nγ ges el conjunto ordenado de sus nodo hijos. Por razones t´ecnicas, y siguiendo el enfoque de [Nederhof, 97], vamos a introducir dos reglas adicionales: (1) > → Rγpara cada ´arbol elemental γy, (2) Fγ→ ⊥ para cada ´arbol auxiliar β. Los nuevos nodos >y⊥presentan una restricci´on de adjunci´on nula con objeto de no modificar la capacidad generativa de la gram´atica. 1.2 Esquemas de an´alisis sint´actico Los esquemas de an´alisis sint´actico [Sikkel, 97] constituyen un m´etodo general para la especificaci´on de algoritmos de an´alisis sint´actico, que surge como una formalizaci´on de trabajos presentados sobre analizadores deductivos [Shieber et al., 95]. Entre sus ventajas fundamentales se encuentran: •Definici´on de los analizadores sin tener en cuenta las estructuras de datos y de control que se usar´an en su implementaci´on. •Permite establecer de una manera f´acil las relaciones entre distintos algoritmos mediante el an´alisis de ciertas relaciones formales. Definici´on 1.1 Sistema de an´alisis Un sistema de an´alisis IP para una gram´atica Gy una cadena de entrada a1...anes una tripleta <I,H,D>, donde: • I es un conjunto de ´ıtems, denominado dominio; • H es un conjunto finito de ´ıtems, llamados hip´otesis. Hno tiene que ser un subconjunto de I; • D ⊆ ℘(H∪I)×I es un conjunto de pasos deductivos. Con ℘denotamos el conjunto potencia de conjuntos finitos. La notaci´on que vamos a usar para especificar los pasos deductivos, mediante los cuales se derivan nuevos ´ıtems ξa partir de los ´ıtems ηiexistentes, es η1,...,ηk ξcond. El analizador sint´actico a˜nadir´a el consecuente ξ∈ I si todos los antecedentes del paso deductivo ηi∈ H ∪ I existen y la condici´on cond se cumple. 4 Definici´on 1.2 ´´ıtems v´alidos El conjunto de ´ıtems v´alidos para un sistema de an´alisis IP =<I,H,D> se define como VIP ={ξ∈ I | H `∗ξ} donde `∗es una secuencia de pasos deductivos. Definici´on 1.3 Sistema de an´alisis no instanciado Un sistema de an´alisis no instanciado para una gram´atica Ges una tripleta <I,H,D>, donde Hes una funci´on que asigna un conjunto de hip´otesis a cada cadena de entrada a1...an, tal que <I,H(a1...an),D>es un sistema de an´alisis. La funci´on Hque se usar´a en este trabajo es: H(a1...an) = {[a, i −1, i]|a=ai∧1≤i≤n} Definici´on 1.4 Esquema de an´alisis Un esquema de an´alisis para una clase de gram´aticas es una funci´on que asigna un sistema de an´alisis no instanciado a cada gram´atica de dicha clase. El uso de sistemas de an´alisis para la especificaci´on de analizadores sint´acticos nos permite explotar todas las propiedades de los sistemas deductivos, entre otras, la posibilidad de establecer relaciones entre distintos sistemas. El establecer las relaciones formales entre los analizadores tiene una serie de ventajas seg´un el uso que hagamos de ellas: •M´etodo descriptivo Nos permite crear una red de analizadores donde se puede comprobar, desde un alto nivel de abstracci´on, c´omo se relacionan distintos analizadores, que en principio, pueden parecer que no poseen nada en com´un. •M´etodo generativo Una vez definido un analizador, podemos crear un nuevo analizador aplic´andole alguna de las relaciones. En este caso, entendemos las relaciones como m´etodos de transformaci´on y, por tanto, como un m´etodo sistem´atico para la creaci´on de nuevos analizadores a partir de otros conocidos. •M´etodo para determinar la correcci´on Aunque la demostraci´on de la correcci´on de un esquema, en general, 5 no es una tarea trivial, como se detalla en [Sikkel, 95], una de las ventajas de formalizar las relaciones entre esquemas es que nos permite establecer qu´e propiedades respecto a la correcci´on preserva cada tipo de relaci´on. De manera que si un analizador se relaciona con otro, cuya correcci´on est´a probada, podemos deducir ciertas propiedades del primero a partir de la relaci´on que mantiene con el segundo. En esta secci´on introduciremos los conceptos te´oricos necesarios para definir las relaciones que se pueden establecer entre esquemas de an´alisis y las propiedades que cumplen. Notaci´on 1 ◦Consideraremos los siguientes esquemas: P1= (I1,H,D1)yP2= (I2,H,D2); ◦ `1y`2son las relaciones de inferencia definidas sobre los esquemas P1 yP2; ◦ V1yV2son los conjuntos de ´ıtems v´alidos de los esquemas P1yP2. Definici´on 1.5 Funci´on regular entre ´ıtems Una funci´on f:I1→ I2es una funci´on regular entre ´ıtems si para todo ´ıtem ι∈ I1y para todo ´arbol t∈ι, se verifica que t∈f(i). Vamos a generalizar esta definici´on para que sea aplicable a conjuntos de ´ıtems, pasos deductivos y secuencias deductivas. Definici´on 1.6 Funci´on entre conjunto ´ıtems Dado un conjunto Y⊆ I1, una funci´on entre conjunto ´ıtems se define mediante: f(Y) = {ξ∈ I2| ∃η∈Y:f(η) = ξ} Definici´on 1.7 Funci´on entre pasos deductivos Dado un paso deductivo η1. . . ηk`ξ∈ D1, una funci´on entre pasos deductivos se define mediante: f(η1. . . ηk`ξ) = f(η1). . . f(ηk)`f(ξ) Se asume que: (1) el conjunto de hip´otesis es disjunto con respecto al conjunto de los ´ıtems en I1yI2, y (2) f(h) = hpara todo h∈ H. Definici´on 1.8 Funci´on entre secuencias deductivas Si tenemos en cuenta las siguientes equivalencias: 4P2=Y2`2x1`2. . . `2xj 6 4P1=Y1`1x0 1`1. . . `1x0 j Una funci´on f f(4P1) = 4P2 es una funci´on entre secuencias deductivas si y solo si se cumple Y1∈℘(H∪ I1)con f(Y1) = Y2yx0 1, . . . x0 j∈ I1con f(x0 i) = xi. Vamos a describir a continuaci´on de manera informal los distintos tipos de relaciones que se pueden establecer entre dos esquemas, las cuales se pueden dividir en dos grupos: generalizaciones y filtros. •Generalizaciones Un esquema es la generalizaci´on de otro cuando es fruto de un refinamiento y/o una extensi´on. Por tanto, las generalizaciones incluyen los refinamientos y la extensi´on. –Refinamientos Introducen m´as detalles en el analizador con objeto de obtener mejoras cualitativas en el mismo. En este grupo se sit´uan los siguientes tipos de relaciones: ∗Refinamiento de ´ıtems Cuando los ´ıtems de un esquema se dividen en varios ´ıtems para obtener otro esquema. Este cambio en el conjunto de ´ıtems puede requerir una modificaci´on del conjunto de pasos deductivos del nuevo esquema para adaptarlo al nuevo dominio. La relaci´on inversa al refinamiento de ´ıtems se denomina contracci´on de ´ıtems, y consiste en agrupar en un s´olo ´ıtem de un esquema varios ´ıtems de otro. ∗Refinamiento de pasos deductivos Cuando un paso deductivo de un esquema de an´alisis es descompuesto en varios pasos para obtener otro esquema. Este cambio en el conjunto de pasos deductivos puede requerir una modificaci´on del dominio del nuevo esquema. –Extensi´on Cuando un esquema se obtiene ampliando la clase de gram´aticas sobre la que est´a definido otro esquema. •Filtros Introducen mejoras cuantitativas en el analizador mediante la eliminaci´on de ´ıtems de su dominio o la reducci´on de las secuencias deductivas. En este grupo se sit´uan los siguientes tipos de relaciones: 7 –Filtro est´atico Cuando se eliminan ´ıtems y/o pasos deductivos redundantes de un esquema para obtener un nuevo esquema. Produce una optimizaci´on en tiempo de compilaci´on y son independientes de la cadena de entrada. –Filtro din´amico Cuando se introduce informaci´on contextual en un esquema, mediante la adici´on de nuevos antecedentes en los pasos deductivos. De esta forma el reconocimiento de ´ıtems durante el proceso deductivo se puede hacer dependiendo de la existencia de otros ´ıtems. Este tipo de filtro, a diferencia del anterior, genera optimizaciones en tiempo de ejecuci´on y van a depender de la cadena de entrada. –Contracci´on de secuencias deductivas Cuando una secuencia deductiva de un esquema se sustituye por otra de menor longitud. Se trata de la relaci´on inversa al refinamiento de pasos deductivos. Pasemos ahora a definir cada una de estas relaciones, as´ı como las propiedades de inter´es que se derivan de ellas. Definici´on 1.9 Refinamiento de ´ıtems El esquema P2es un refinamiento de los ´ıtems del esquema P1, y lo denotamos como P1 ir =⇒P2, si existe una funci´on regular entre ´ıtems f:I2→ I1 tal que: 1. I1=f(I2) 2. 4P1=f(4P2) Corolario 1.1 La relaci´on ir =⇒es reflexiva y transitiva. Adem´as si P1 ir =⇒P2, entonces la correcci´on del esquema P2implica la correcci´on de P1. La relaci´on inversa al refinamiento de ´ıtems se denomina contracci´on de ´ıtems y la denotamos como ic =⇒. Por tanto, si se verifica P2 ic =⇒P1, entonces P1 ir =⇒P2. Corolario 1.2 La relaci´on ic =⇒es reflexiva, transitiva y preserva la correcci´on. 8 Definici´on 1.10 Refinamiento de pasos deductivos El esquema P2es un refinamiento de los pasos deductivos del esquema P1, y lo denotamos como P1 sr =⇒P2, si se cumple: 1. I1⊆ I2 2. `∗ 1⊆`∗ 2 Corolario 1.3 La relaci´on sr =⇒es reflexiva, transitiva y preserva la completitud. Definici´on 1.11 Extensi´on Sea P1un esquema definido sobre una clase de gram´aticas CG1yP2un esquema definido sobre una clase de gram´aticas CG2, decimos que P2es una extensi´on del esquema P1, y lo denotamos como P1 ext =⇒P2, si se cumple: 1. CG1⊆CG2 2. P1(G)(a1. . . an) = P2(G)(a1. . . an)para toda G∈CG1y cadena de entrada a1. . . an. Corolario 1.4 La relaci´on ext =⇒es reflexiva y transitiva. Definici´on 1.12 Filtro est´atico El esquema P2es un filtro est´atico del esquema P1, y lo denotamos como P1 sf =⇒P2, si se cumple: 1. I1⊇ I2 2. D1⊇ D2 Definici´on 1.13 Filtro din´amico El esquema P2es un filtro din´amico del esquema P1, y lo denotamos como P1 df = ⇒P2, si se cumple: 1. I1⊇ I2 2. `1⊇`2 Definici´on 1.14 Contracci´on de secuencias deductivas El esquema P2es una contracci´on de secuencias deductivas del esquema P1, y lo denotamos como P1 sc =⇒P2, si se cumple: 9 y compleci´on. Evidentemente, con las variantes que provoca la operaci´on de adjunci´on tanto en la predicci´on como en la compleci´on. Inicio El reconocimiento comienza con la predicci´on de todo ´arbol inicial (α∈I) cuya ra´ız sea el axioma (label(Rα) = S: DIni E=[> → •Rα,0,0| −,−]α∈I∧label(Rα) = S Reconocimiento Los pasos deductivos de reconocimiento son iguales a los del esquema buE: DScan E=DScan buE Dε E=Dε buE Los pasos deductivos que establecen la estrategia ascendente predictiva del analizador Earley para CFGs son los correspondientes a predicciones y compleciones. Para el caso de las TAGs, vamos a distinguir tres tipos de predicciones con sus correspondientes pasos de compleci´on asociados: sub´arbol, adjunci´on y pie. Predicci´on de sub´arbol Este paso deductivo es similar al paso predictivo del analizador Earley para CFGs. De manera que si se alcanza un nodo Mγque no presenta adjunci´on obligatoria (nil ∈adj(Mγ)), el an´alisis debe continuar el reconocimiento descendente del sub´arbol dominado por Mγ: DPred E=[Nγ→δ•Mγν, i, j |p, q] [Mγ→ •υ, j, j | −,−]nil ∈adj(Mγ) Compleci´on de sub´arbol Este paso deductivo de compleci´on de sub´arbol es igual al del esquema buE: DComp E=DComp buE Predicci´on de adjunci´on Cuando el reconocimiento alcanza un nodo adjuntable Mγ(β∈adj(Mγ)), el an´alisis debe lanzar el reconocimiento de todos los ´arboles auxiliares (β) que se pueden adjuntar en Mγ: DAdjPred E=[Nγ→δ•Mγν, i, j |p, q] [> → •Rβ, j, j | −,−]β∈adj(Mγ) 16 Predicci´on de pie Cuando el reconocimiento alcanza el nodo pie de un ´arbol auxiliar β, se debe continuar con el sub´arbol escindido por la operaci´on de adjunci´on. Ni en los ´ıtems ni en el chart existe informaci´on suficiente para determinar sobre qu´e sub´arbol se debe continuar el reconocimiento, y precisamente esta carencia es la que provoca que el analizador no cumpla la propiedad del prefijo v´alido. Por ello, la operaci´on DFootPred Ese ve obligada a lanzar todos los sub´arboles dominados por Mγdonde β∈adj(Mγ): DFootPred E=[Fβ→ •⊥, k, k | −,−] [Mγ→ •δ, k, k | −,−]β∈adj(Mγ) Compleci´on de pie Cuando se completa el reconocimiento de un sub´arbol escindido dominado por Mγ, el an´alisis debe continuar con el contexto derecho del ´arbol auxiliar adjuntado β: DFootComp E= [Mγ→δ•, k, l |p, q], [Fβ→ •⊥, k, k | −,−] [Fβ→ ⊥•, k, l |k, l]β∈adj(Mγ) Compleci´on de adjunci´on Una vez que se ha completado el reconocimiento de un ´arbol auxiliar β, debemos continuar el reconocimiento del ´arbol γdonde se ha efectuado la adjunci´on: DAdjComp E= [> → Rβ•, j, m |k, l], [Mγ→υ•, k, l |p, q], [Nγ→δ•Mγν, i, j |p0, q0] [Nγ→δMγ•ν, i, m |p∪p0, q ∪q0]β∈adj(Mγ) El conjunto de ´ıtems finales del esquema viene dado por: FE={[> → Rα•,0, n | −,−]|α∈I∧label(Rα) = S} 17 5 Esquema Left Corner con ´ıtems predictivos En esta secci´on presentamos un analizador que usa la relaci´on de esquina izquierda para filtrar las predicciones del esquema tipo Earley para TAGs descrito en la secci´on anterior. La complejidad temporal del algoritmo con respecto a la longitud nde la cadena de entrada permanece en O(n6), pero las prestaciones pr´acticas se mejoran con respecto al algoritmo tipo Earley, debido a una reducci´on en el n´umero de ´ıtems deducidos. En el formalismo CFG, la esquina izquierda de un s´ımbolo no terminal Aes el s´ımbolo terminal o no terminal Xsi y s´olo si existe una producci´on A→Xν en la gram´atica, donde νes una secuencia de s´ımbolos. Para el caso A→ε, consideramos εcomo la esquina izquierda de A. Para el caso de las TAGs extendemos la definici´on anterior al ´ambito de los ´arboles elementales de una gram´atica TAG. Definici´on 5.1 Relaci´on de esquina izquierda (left corner) en los ´arboles elementales de una TAG La esquina izquierda de un nodo Oγes su hijo izquierdo Pγsi y s´olo si adj(Pγ) = {nil}. La relaci´on esquina izquierda >`sobre (VN∪ >)×(VN∪ VT∪{ε, ⊥})se define mediante Oγ>`Pγsi hay una producci´on Oγ→Pγν∈ P(γ)yadj(Pγ) = {nil}. La clausura reflexiva y transitiva de >`la denotamos como >∗ `. Es importante se˜nalar que una relaci´on de esquina izquierda siempre comienza con un nodo etiquetado con un s´ımbolo no terminal y finaliza en un nodo de adjunci´on, un nodo etiquetado con un s´ımbolo terminal o un nodo etiquetado con ε. Usaremos Mγ>`4para denotar que Mγes un nodo de adjunci´on. En el esquema que introducimos en esta secci´on, al que denominaremos pLC, los pasos predictivos en el esquema Eson reemplazados por objetivos que se intentan satisfacer de forma ascendente. La fase ascendente del proceso de reconocimiento es guiada hacia el correspondiente objetivo mediante la relaci´on de esquina izquierda. Por tanto, en el dominio del esquema pLC vamos a distinguir dos tipos de´ıtems: predictivos y left corner. Por la propia naturaleza del analizador estos ´ultimos se dividen en dos subtipos. IpLC =Ip pLC ∪ Ilc pLC ∪ Ilc0 pLC Los ´ıtems predictivos son aquellos que lanzan la predicci´on (de adjunci´on o sub´arbol) de un nodo Mγdesde una posici´on de la cadena de entrada, por 18 tanto, solo es necesaria la informaci´on del propio nodo y la posici´on de la cadena de entrada j. Ip pLC ={[Mγ, j]|γ∈I∪A, 0 ≤j} Los ´ıtems left corner tienen la misma forma que los ´ıtems del analizador tipo Earley para las TAGs pero se le a˜nade un nodo delante (Cγ), que es el nodo que domina por una relaci´on de esquina izquierda al nodo situado a la izquierda de la producci´on (Mγ). Esta informaci´on adicional, aunque no es necesaria, va a permitir al analizador simplificar algunos de sus pasos deductivos y el reconocimiento ascendente a trav´es de una secuencia de relaciones de esquinas izquierdas. El esquema pLC filtra los ´ıtems de Eeliminando de su dominio aquellos ´ıtems que inician el reconocimiento en la esquina izquierda de una producci´on. Ilc pLC ={[Cγ;Mγ→δ•ν, i, j |p, q]|Mγ→δν ∈ P(γ) , γ∈I∪A, Cγ>∗ `Mγ, 0 ≤i≤j,δ6=², ((p, q)≤(i, j) ´o (p, q) = (−,−))} Sin embargo, este filtro no es posible cuando la esquina izquierda de la producci´on Pγes: •Un nodo adjuntable, ya que la inclusi´on de un ´arbol auxiliar detiene la relaci´on de esquina izquierda con sus descendientes. •Un nodo ⊥, ya que la relaci´on de esquina izquierda, como la hemos definido, no va m´as all´a de un ´arbol elemental. Para recoger estos dos casos especiales, definimos la siguiente clase de ´ıtems left corner: Ilc0 pLC ={[Cγ;Mγ→ •Pγν, j, j | −,−]|Mγ→Pγν∈ P(γ) , γ∈I∪A, Cγ>∗ `Mγ, 0 ≤j, (Pγ>`4´o label(Pγ) = ⊥)} Con respecto al conjunto de pasos deductivos, definimos subconjuntos para reconocimiento ycompleci´on similares a los del esquema Epara TAGs. La relaci´on de esquina izquierda se aplicar´a a los cuatro casos de predicci´on: inicial, sub´arbol, pie y adjunci´on. Los pasos de esquina izquierda vienen en tres variedades, seg´un el tipo de nodo en que finalice la relaci´on: terminal, cadena vac´ıa y no terminal. El ´ultimo caso es necesario cuando la esquina izquierda es un nodo de adjunci´on o el nodo bottom de un ´arbol auxiliar, ya 19 que el ´arbol auxiliar o el sub´arbol escindido mediante una adjunci´on deben ser reconocidos. El conjunto de pasos deductivos del esquema es: DpLC =DLIt pLC ∪ DLIε pLC ∪ DLIpre pLC ∪ DScan pLC ∪ Dε pLC ∪ DLCt pLC ∪ DLCε pLC∪ DLCpre pLC ∪ DLCn pLC ∪ DPre pLC ∪ DComp pLC ∪ DLAt pLC ∪ DLAε pLC∪ DLApre pLC ∪ DAdjComp pLC ∪ DLFt pLC ∪ DLFε pLC ∪ DLFpre pLC ∪ DFootComp pLC Filtrado de inicio El reconocimiento comienza prediciendo todos los ´arboles iniciales (α∈I) cuya ra´ız sea el axioma (label(Rα) = S). Dado que siempre se cumplir´a que >>∗ `OαyOα→Pαν∈ P(α), podemos aplicar un filtro LC y obtenemos los siguientes pasos: DLIt pLC =[a, 0,1] [>;Oα→Pα•ν, 0,1| −,−]label(Pα) = a DLIε pLC =[>;Oα→Pα•ν, 0,0| −,−]label(Pα) = ε DLIpre pLC =[>;Oα→ •Pαν, 0,0| −,−]Pα>`4 El paso DLIt pLC se aplicar´a cuando la esquina izquierda Pαest´a etiquetada con un s´ımbolo terminal. El paso DLIε pLC se usa cuando Pαes la cadena vac´ıa. Y si Pαes una nodo de adjunci´on entonces se aplica DLIpre pLC . Al tratarse de ´arboles iniciales los ´arboles elementales cuyas predicciones se filtran en este grupo, no tenemos en cuenta el caso en que la esquina izquierda sea un nodo ⊥. Reconocimiento El paso deductivo DScan pLC se aplica cuando el reconocimiento alcanza un nodo cuya etiqueta coincide con el s´ımbolo terminal que corresponde en la cadena de entrada. Es evidente que este terminal no puede ser la esquina izquierda de una producci´on, ya que ese tipo de ´ıtems no pertenecen al dominio del esquema. DScan pLC = [Cγ;Nγ→Pγδ•Mγν, i, j |p, q] [a, j, j + 1] [Cγ;Nγ→PγδMγ•ν, i, j + 1 |p, q]label(Mγ) = a 20 Para efectuar el reconocimiento de s´ımbolos εse usa el paso deductivo Dε pLC. Dε pLC =[Cγ;Nγ→Pγδ•Mγν, i, j |p, q] [Cγ;Nγ→PγδMγ•ν, i, j |p, q]label(Mγ) = ε Filtrado de predicci´on de sub´arbol Si un nodo (Mγ), cuyo reconocimiento ha sido predicho, no presenta una restricci´on de adjunci´on obligatoria y adem´as domina por una relaci´on de esquina izquierda a otro nodo (Oγ), se podr´ıan eliminar todas las predicciones entre ambos. En el caso de que el hijo izquierdo de Oγest´e etiquetado con un s´ımbolo terminal se aplica el paso DLCt pLC, el cual es el equivalente a DScan pLC cuando el nodo a reconocer es la esquina izquierda de una producci´on. DLCt pLC = [Mγ, j] [a, j, j + 1] [Mγ;Oγ→Pγ•ν, j, j + 1 | −,−] label(Pγ) = a nil ∈adj(Mγ) El paso DLCε pLC tiene la misma funci´on que DLCt pLC, pero se aplica cuando el hijo izquierdo de Oγes un s´ımbolo etiquetado como ε. Es la operaci´on equivalente a Dε pLC para los s´ımbolos de la esquina izquierda. DLCε pLC =[Mγ, j] [Mγ;Oγ→Pγ•ν, j, j | −,−] label(Pγ) = ε nil ∈adj(Mγ) Cuando el hijo izquierdo de Oγsea un nodo adjuntable se elimina la relaci´on de esquina izquierda y se detiene el reconocimiento para lanzar los ´arboles auxiliares adjuntables en dicho nodo. Lo mismo ocurre cuando γ∈Ay el hijo izquierdo de Oγest´a etiquetado con ⊥, ya que hay que iniciar el reconocimiento del sub´arbol escindido en el nodo donde se ha llevado a cabo la adjunci´on de este ´arbol auxiliar. DLCpre pLC =[Mγ, j] [Mγ;Oγ→ •Pγν, j, j | −,−] nil ∈adj(Mγ) Pγ>`4´o label(Pγ) = ⊥ Compleci´on en la esquina izquierda El recorrido ascendente a trav´es de los nodos dominados por una relaci´on de esquina izquierda se lleva a cabo mediante el paso DLCn pLC. Esta operaci´on es la equivalente a la compleci´on de un sub´arbol para los nodos que se encuentran dentro de una relaci´on de esquina izquierda. Obs´ervese como el 21 elemento auxiliar incluido en los ´ıtems (nodo ancla de la relaci´on esquina izquierda) permite establecer el fin de este recorrido ascendente, ya que la cadena de operaciones DLCn pLC se detendr´a cuando se alcance dicho nodo. DLCn pLC =[Mγ;Oγ→ν•, j, k |p, q] [Mγ;Qγ→Oγ•ω, j, k |p, q]Mγ6=Oγ Predicci´on Mediante el paso DPre pLC se realiza la predicci´on de los nodos etiquetados con s´ımbolos no terminales que no se encuentran dominados en una relaci´on de esquina izquierda, por tanto, estos nodos se convertir´an en anclas dentro de ´ıtems de tipo left corner. DPre pLC =[Cγ;Nγ→δ•Mγν, i, j |p, q] [Mγ, j]label(Mγ)∈VN Compleci´on de sub´arbol El paso DComp pLC efect´ua el reconocimiento ascendente de los sub´arboles dominados por nodos que no se encuentran en la esquina izquierda. Tambi´en lleva a cabo la compleci´on aunque el nodo sea esquina izquierda, siempre que ´este sea un nodo adjuntable (Mγ>`4) pero sin adjunci´on obligatoria (nil ∈adj(Mγ)). DCmp pLC = [Cγ;Nγ→δ•Mγν, i, j |p, q] [Mγ;Mγ→ν•, j, k |p0, q0] [Cγ;Nγ→δMγ•ν, i, k |p∪p0, q ∪q0]nil ∈adj(Mγ) Filtrado de predicci´on de adjunci´on Cuando se predice un nodo que es adjuntable, hay que lanzar el reconocimiento de todos los ´arboles auxiliares (β) que pueden ser adjuntados en el mismo. Sin embargo, en lugar de comenzar el reconocimiento en la ra´ıces de dichos ´arboles auxiliares, se bajar´a hasta aquellos nodos (Oβ) que est´en dominados por una relaci´on LC por los nodos top (>). En funci´on del tipo de nodo que sea hijo izquierdo de Oβse distinguen tres pasos deductivos:DLAt pLC,DLAε pLC y DLApre pLC . Si el hijo izquierdo de Oβest´a etiquetado con un s´ımbolo terminal se aplica DLAt pLC: DLAt pLC = [Mγ, j] [a, j, j + 1] [>;Oβ→Pβ•ν, j, j + 1 | −,−] label(Pβ) = a β∈adj(Mγ) 22 Si el hijo izquierdo de Oβest´a etiquetado con εse aplica DLAε pLC: DLAε pLC =[Mγ, j] [>;Oβ→Pβ•ν, j, j | −,−] label(Pβ) = ε β∈adj(Mγ) Si el hijo izquierdo de Oβes un nodo adjuntable o el nodo etiquetado ⊥se aplica DLApre pLC , que posteriormente lanzar´a la predicci´on de los ´arboles auxiliares adjuntables o del sub´arbol escindido por el ´arbol auxiliar β. DLApre pLC =[Mγ, j] [>;Oβ→ •Pβν, j, j | −,−] β∈adj(Mγ) Pβ>`4´o label(Pβ) = ⊥ Compleci´on de adjunci´on Una vez que se ha completado el reconocimiento de un ´arbol auxiliar hay que continuar el reconocimiento del ´arbol sobre el que se ha completado la adjunci´on. DAdjComp pLC = [Cγ;Nγ→δ•Mγν, i, j |p0, q0] [>;> → Rβ•, j, m |k, l] [Mγ;Mγ→ω•, k, l |p, q] [Cγ;Nγ→δMγ•ν, i, m |p∪p0, q ∪q0]β∈adj(Mγ) Filtrado de predicci´on de pie Cuando un ´arbol auxiliar β, adjuntable en un nodo Mγ, se ha reconocido hasta su nodo ⊥, se debe iniciar el reconocimiento del sub´arbol que domina Mγ. Al tratarse de un analizador que no posee la propiedad del prefijo v´alido, se debe lanzar el reconocimiento de todos los sub´arboles donde puede ser adjuntado el ´arbol auxiliar β. Hay que tener en cuenta que el hecho de incluir un ´arbol auxiliar entre el nodo Mγy el sub´arbol que domina provoca que Mγse duplique, apareciendo como ra´ız y pie del ´arbol auxiliar adjuntado. Es evidente que el nodo Mγ que funciona como ra´ız, al insertar un ´arbol auxiliar, ha perdido su relaci´on de esquina izquierda respecto a su sub´arbol, pero el nodo Mγque funciona como pie la sigue manteniendo. Sobre este ´ultimo se puede aplicar un filtro en las predicciones, bajando hasta el nodo que sea su esquina izquierda Oγ. Como en casos anteriores, en funci´on del tipo de nodo que sea el hijo izquierdo de Oγse aplica uno de los siguientes pasos deductivos: DLFt pLC,DLFε pLC yDLFpre pLC . 23 DLFt pLC = [Eβ;Fβ→ •⊥, k, k | −,−] [a, k, k + 1] [Mγ;Oγ→Pγ•ν, k, k + 1 | −,−] label(Pγ) = a β∈adj(Mγ) DLFε pLC =[Eβ;Fβ→ •⊥, k, k | −,−] [Mγ;Oγ→Pγ•ν, k, k | −,−] label(Pγ) = ε β∈adj(Mγ) DLFpre pLC =[Eβ;Fβ→ •⊥, k, k | −,−] [Mγ;Oγ→ •Pγν, k, k | −,−] β∈adj(Mγ) Pγ>`4´o label(Pγ) = ⊥ Compleci´on de pie Cuando un sub´arbol escindido por una adjunci´on es completamente reconocido, hay que pasar a reconocer el contexto derecho del ´arbol auxiliar adjuntado mediante el paso deductivo DFootComp pLC : DFootComp pLC = [Eβ;Fβ→ •⊥, k, k | −,−] [Mγ;Mγ→ν•, k, l |p, q] [Eβ;Fβ→ ⊥•, k, l |k, l]β∈adj(Mγ) El conjunto de ´ıtems finales del esquema es igual al del esquema E: FpLC =FE 6 Esquema Left Corner con ´ıtems simplificados Un ´ıtem left corner [Cγ;Nγ→δ•ν, i, j |p, q] puede considerarse compuesto de dos partes claramente diferenciadas: por un lado est´a la parte predicha [Cγ, i] y por otro la parte reconocida [Nγ→δ•ν, i, j |p, q]. Si tenemos en cuenta que la informaci´on que conlleva la parte predicha ya est´a almacenada en el chart y que la parte reconocida son ´ıtems earley convencionales, podemos simplificar el esquema pLC. Derivamos el esquema sLC a partir del esquema pLC de la siguiente manera: •A los ´ıtems left corner les eliminamos la parte predictiva (el ancla de la relaci´on esquina izquierda) y lo convertimos en ´ıtems earley. •Se modifican los pasos deductivos, a˜nadiendo condiciones laterales en aquellos casos que sean necesarias. 24 En el dominio del esquema sLC vamos a distinguir dos tipos de ´ıtems: predictivos y earley. Por la propia naturaleza del analizador estos ´ultimos se dividen en dos subtipos: IsLC =Ip sLC ∪ Ie sLC ∪ Ie0 sLC Los ´ıtems predictivos en este esquema son id´enticos a los de la misma denominaci´on en el esquema pLC: Ip sLC =Ip pLC . Los ´ıtems earley tienen la misma forma que los ´ıtems del analizador tipo earley para las TAGs pero con la particularidad de que se han filtrado los ´ıtems con el punto al comienzo de la regla, salvo en los casos descritos en la definici´on de Ilc0 pLC en la secci´on anterior. Por tanto, este tipo de ´ıtems se define mediante: Ie sLC ={[Mγ→δ•ν, i, j |p, q]} tal que Mγ→δν ∈ P(γ)∧γ∈I∪A∧0≤i≤j∧δ6=²∧((p, q)≤ (i, j)∨(p, q) = (−,−)). Ie0 sLC ={[Mγ→ •Pγν, j, j | −,−]} tal que Mγ→Pγν∈ P(γ)∧γ∈I∪A∧0≤j∧(Pγ>`4 ∨ label(Pγ) = ⊥) . El conjunto de pasos deductivos del esquema es: DsLC =DLIt sLC ∪ DLIε sLC ∪ DLIpre sLC ∪ DScan sLC ∪ Dε sLC ∪ DLCt sLC ∪ DLCε sLC ∪ DLCpre sLC ∪ DLCn sLC ∪ DPre sLC ∪ DComp sLC ∪ DLAt sLC ∪ DLAε sLC ∪ DLApre sLC ∪ DAdjComp sLC ∪ DLFt sLC ∪ DLFε sLC ∪ DLFpre sLC ∪ DFootComp sLC Filtrado de inicio DLIt sLC =[a, 0,1] [Oα→Pα•ν, 0,1| −,−] α∈I >>∗ `Oα label(Pα) = a 25 dominio del esquema LC0es igual al del esquema LC0y viene dado por el conjunto: ILC0=Ie LC0∪ Ie0 LC0 donde Ie LC0=Ie LC yIe0 LC0=Ie0 LC. El conjunto de pasos deductivos del esquema es: DLC0=DLIt LC0∪ DLIε LC0∪ DLIpre LC0∪ DScan LC0∪ Dε LC0∪ DLCt LC0∪ DLCε LC0∪ DLCpre LC0∪ DLCn LC0∪ DComp LC0∪ DLAt LC0∪ DLAε LC0∪ DLApre LC0∪ DAdjComp LC0∪ DLFt LC0∪ DLFε LC0∪ DLFpre LC0∪ DFootComp LC0 El conjunto de pasos deductivos es b´asicamente igual al del esquema LC, salvo en los pasos dedicados al filtrado de predicci´on de sub´arbol y pie, y el dedicado a la compleci´on del nodo pie: DLIt LC0=DLIt LC DLIε LC0=DLIε LC DLIpre LC0=DLIpre LC0 DScan LC0=DScan LC Dε LC0=Dε LC DComp LC0=DComp LC DAdjComp LC0=DAdjComp LC Filtrado de predicci´on de sub´arbol Los pasos deductivos de predicci´on de sub´arbol donde la etiqueta de ´ultimo nodo de la relaci´on de LC es un s´ımbolo terminal o εson iguales a los del esquema LC: DLCt LC0=DLCt LC DLCε LC0=DLCε LC Sin embargo, cuando el ´ultimo nodo de la relaci´on de LC es un nodo de adjunci´on se aplica el paso siguiente: DLCpre LC0=[Nγ→δ•Mγν, i, j |p, q] [Oγ→ •Pγω, j, j | −,−] nil ∈adj(Mγ) Mγ>∗ `Oα Pγ>`4 32 Este paso difiere del DLCpre LC en la condici´on lateral, en la cual hemos suprimido el caso en que el nodo Pγestuviera etiquetado con ⊥. De este caso ya se ocupan el conjunto de pasos de predicci´on de pie, que veremos posteriormente. Filtrado de predicci´on de adjunci´on Los pasos deductivos de predicci´on de adjunci´on son iguales a los del esquema LC: DLAt LC0=DLAt LC DLAε LC0=DLAε LC DLApre LC0=DLApre LC0 Para el paso deductivo DLApre LC0se mantiene la condici´on lateral en la que se detiene la relaci´on LC cuando el ´ultimo nodo sea un nodo adjuntable o est´e etiquetado con ⊥. Esto ´ultimo es necesario porque en caso de no recoger esta situaci´on, si en el ´arbol auxiliar que se va a adjuntar se cumple >>∗ `⊥ entonces se ignorar´a en el reconocimiento. Filtrado de predicci´on de pie Sea Mγun nodo en un ´arbol elemental γsobre el que se puede adjuntar un ´arbol auxiliar β. Supongamos que el reconocimiento ha alcanzado el nodo Eβ, el cual que no presenta adjunci´on obligatoria y adem´as domina el nodo pie por una relaci´on LC. Estos nuevos pasos deductivos filtran tanto las predicciones sobre los nodos del ´arbol auxiliar βcomo sobre el ´arbol elemental γdonde se est´a llevando a cabo la adjunci´on: DLFt LC0= [Nβ→δ•Eβω, j, k | −,−] [a, k, k + 1] [Oγ→Pγ•ν, k, k + 1 | −,−] β∈adj(Mγ) Mγ>∗ `Oγ Eβ>∗ `⊥ label(Pγ) = a DLFε LC0=[Nβ→δ•Eβω, j, k | −,−] [Oγ→Pγ•ν, k, k | −,−] β∈adj(Mγ) Mγ>∗ `Oγ Eβ>∗ `⊥ label(Pγ) = ε DLFpre LC0=[Nβ→δ•Eβω, j, k | −,−] [Oγ→ •Pγν, k, k | −,−] β∈adj(Mγ) Mγ>∗ `Oγ Eβ>∗ `⊥ Pγ>`4 ∨ label(Pγ) = ⊥ 33 Obs´ervese que en el paso deductivo DLFpre LC0, al igual que ocurre en DLApre LC0, tambi´en se mantiene la condici´on Pγ>`4 ∨ label(Pγ) = ⊥, con objeto de poder realizar la compleci´on del sub´arbol que domina el nodo pie si el ´arbol γfuese un ´arbol auxiliar y adem´as cumpliera que Mγ>∗ `⊥. Compleci´on de pie El paso deductivo de compleci´on de pie es similar al del esquema LC, pero hemos sustituido el antecedente [Fβ→ •⊥, k, l |k, l], el cual ya no tenemos garant´ıa que est´e almacenado en el chart: DFootComp LC0= [Nβ→δ•Eβω, j, k | −,−] [Mγ→ν•, k, l |p, q] [Fβ→ ⊥•, k, l |k, l] β∈adj(Mγ) Eβ>∗ `⊥ El conjunto de ´ıtems finales del esquema es igual al del esquema LC: FLC0=FLC 8 Relaciones entre los esquemas Veamos a continuaci´on las relaciones formales que existen entre los distintos esquemas que hemos propuesto en este cap´ıtulo. Teorema 8.1 Relaci´on entre los esquemas pLC,sLC yLC Se mantienen las siguientes relaciones de refinamiento de pasos e ´ıtems: LC sr =⇒sLC ir =⇒pLC Prueba Primero vamos a probar la relaci´on sLC ir =⇒pLC. Debemos probar que existe una funci´on regular f:IpLC → IsLC tal que: 1. IsLC =f(IpLC) 2. 4sLC =f(4pLC) Una funci´on regular de contracci´on de ´ıtems que cumple estas condiciones es la siguiente: f([Cγ;Nγ→δ•ν, i, j |p, q]) = [Nγ→δ•ν, i, j |p, q] 34 Puesto que los ´ıtems predictivos son iguales en ambos esquemas: f([Cγ, j]) = [Cγ, j] De fse sigue inmediatamente que IsLC =f(IpLC)y4sLC =f(4pLC)por inducci´on en la longitud de las secuencias de derivaci´on. A continuaci´on probaremos la relaci´on LC sr =⇒sLC. Para ello tenemos que demostrar que: 1. ILC ⊆ IsLC 2. `∗ LC⊆`∗ sLC Lo primero es cierto por definici´on, ya que el dominio del esquema sLC est´a formado por los conjuntos de ´ıtems del esquema LC y los predictivos: IsLC =Ip sLC ∪ ILC Para demostrar que `∗ LC⊆`∗ sLC nos basta con probar que DLC ⊆`∗ sLC. Veamos cada paso: •Un paso deductivo DLCt LC es equivalente a la secuencia formada por un paso DPre sLC [Nγ→δ•Mγν, i, j |p, q] [Mγ, j] seguido de otro DLCt sLC [Mγ, j] [a, j, j + 1] [Oγ→Pγ•ν, j, j + 1 | −,−] •Un paso deductivo DLCε LC es equivalente a la secuencia formada por un paso DPre sLC [Nγ→δ•Mγν, i, j |p, q] [Mγ, j] seguido de otro DLCε sLC [Mγ, j] [Oγ→Pγ•ν, j, j | −,−] 35 •Un paso deductivo DLCpre LC es equivalente a la secuencia formada por un paso DPre sLC [Nγ→δ•Mγν, i, j |p, q] [Mγ, j] seguido de otro DLCpre sLC [Mγ, j] [Oγ→ •Pγν, j, j | −,−] •Un paso deductivo DLAt LC es equivalente a la secuencia formada por un paso DPre sLC [Nγ→δ•Mγν, i, j |p, q] [Mγ, j] seguido de otro DLAt sLC [Mγ, j] [a, j, j + 1] [Oβ→Pβ•ν, j, j + 1 | −,−] •Un paso deductivo DLAε LC es equivalente a la secuencia formada por un paso DPre sLC [Nγ→δ•Mγν, i, j |p, q] [Mγ, j] seguido de otro DLAε sLC [Mγ, j] [Oβ→Pβ•ν, j, j | −,−] •Un paso deductivo DLApre LC es equivalente a la secuencia formada por un paso DPre sLC [Nγ→δ•Mγν, i, j |p, q] [Mγ, j] seguido de otro DLApre sLC [Mγ, j] [Oβ→ •Pβν, j, j | −,−] •El resto de pasos deductivos es igual en ambos esquemas 36 Teorema 8.2 Relaci´on entre los esquemas buLC yLC Se mantiene la siguientes relaciones de filtros din´amicos: LC df =⇒LC1 df ⇐=buLC1 sr ⇐=buLC Prueba Antes de iniciar la demostraci´on vamos a definir dos nuevos esquemas que nos servir´an de enlaces para establecer la relaci´on entre los dos esquemas de inter´es. El primero, que denominaremos LC1, se trata de una transformaci´on trivial sobre el esquema LC que consiste en el desdoble de los pasos DComp LC yDAdjComp LC en cuatro: DComp1 LC1,DComp2 LC1,DAdjComp1 LC1yDAdjComp2 LC1. De forma que los que presentan sub´ındice 1 se encargan de completar los sub´arboles y las adjunciones en nodos que no son hijos izquierdos y los que tienen sub´ındice 2 las completan en los hijos izquierdos. El dominio de LC1viene dado por: ILC1=ILC El conjunto de pasos deductivos del nuevo esquema es: DLC1=DLIt LC1∪ DLIε LC1∪ DLIpre LC1∪ DScan LC1∪ Dε LC1∪ DLCt LC1∪ DLCε LC1∪ DLCpre LC1∪ DLCn LC1∪ DComp1 LC1∪ DComp2 LC1∪ DLAt LC1∪ DLAε LC1∪ DLApre LC1∪ DAdjComp1 LC1∪ DAdjComp2 LC1∪ DLFt LC1∪ DLFε LC1∪ DLFpre LC1∪ DFootComp LC1 donde todos los pasos deductivos son iguales a sus hom´onimos del esquema LC, salvo los cuatro nombrados anteriormente. DLIt LC1=DLIt LC DLIε LC1=DLIε LC DLIpre LC1=DLIpre LC DScan LC1=DScan LC Dε LC1=Dε LC DLCt LC1=DLCt LC DLCε LC1=DLCε LC 37 DLCpre LC1=DLCpre LC DLCn LC1=DLCn LC DLAt LC1=DLAt LC DLAε LC1=DLAε LC DLApre LC1=DLApre LC DLFt LC1=DLFt LC DLFε LC1=DLFε LC DLFpre LC1=DLFpre LC DFootComp LC1=DFootComp LC DComp1 LC1= [Nγ→Pγδ•Mγν, i, j |p, q] [Mγ→ν•, j, k |p0, q0] [Nγ→PγδMγ•ν, i, k |p∪p0, q ∪q0]nil ∈adj(Mγ) DComp2 LC1= [Nγ→ •Mγν, j, j | −,−] [Mγ→ν•, j, k |p, q] [Nγ→Mγ•ν, j, k |p, q]nil ∈adj(Mγ) DAdjComp1 LC1= [Nγ→Pγδ•Mγν, i, j |p0, q0] [> → Rβ•, j, m |k, l] [Mγ→ω•, k, l |p, q] [Nγ→PγδMγ•ν, i, m |p∪p0, q ∪q0]β∈adj(Mγ) DAdjComp2 LC1= [Nγ→ •Mγν, j, j | −,−] [> → Rβ•, j, m |k, l] [Mγ→ω•, k, l |p, q] [Nγ→Mγ•ν, j, m |p, q]β∈adj(Mγ) El conjunto de ´ıtems finales tambi´en es igual al del esquema LC: ILC1=ILC El segundo esquema intermedio, al que vamos a denominar buLC1, consiste en la ampliaci´on del dominio de buLC con ´ıtems con el punto al comienzo de la regla cuando el hijo izquierdo sea un nodo adjuntable. El dominio viene dado por: IbuLC1=Ie buLC1∪ Ie0 buLC1 38 Ie buLC1={[Mγ→δ•ν, i, j |p, q]} tal que Mγ→δν ∈ P(γ)∧γ∈I∪A∧0≤i≤j∧δ6=²∧((p, q)≤ (i, j)∨(p, q) = (−,−)). Ie0 buLC1={[Mγ→ •Pγν, j, j | −,−]} tal que Mγ→Pγν∈ P(γ)∧γ∈I∪A∧0≤j∧(Pγ>`4 ∨ label(Pγ) = ⊥). Por tanto, se cumple que: IbuLC1=ILC =ILC1 Hay que adaptar el conjunto de pasos deductivos al nuevo dominio: DbuLC1=DLCt buLC1∪ DLCε buLC1∪ DLCn buLC1∪ DLCpre buLC1∪ DLCcad buLC1 ∪DFoot buLC1∪ DScan buLC1∪ Dε buLC1∪ DComp buLC1∪ DAdjComp buLC1 donde todos los pasos son id´enticos al los hom´onimos de buLC, excepto el paso Dcad buLC y el nuevo paso DLCpre buLC1. DLCt buLC1=DLCt buLC DLCε buLC1=DLCε buLC DLCn buLC1=DLCn buLC DFoot buLC1=DFoot buLC DScan buLC1=DScan buLC Dε buLC1=Dε buLC DComp buLC1=DComp buLC DAdjComp buLC1=DAdjComp buLC DLCpre buLC1=[Qγ→ •Oγω, j, j, −,−]Oγ>`4 39 DLCcad buLC1= [Qγ→ •Oγω, j, j, −,−] [> → Rβ•, j, m, k, l] [Oγ→ν•, k, l, p, q] [Qγ→Oγ•ω, j, m, p, q]β∈adj(Oγ) El conjunto de ´ıtems finales es igual al del esquema buLC: FbuLC1=FbuLC Para probar que LC df =⇒LC1tenemos que demostrar que: 1. ILC1⊆ ILC 2. `LC1⊆`LC Lo primero es cierto por definici´on, ya que los dominios de ambos esquemas son iguales: ILC1=ILC Para probar que `LC1⊆`LC debemos demostrar que DLC1⊆`LC . S´olo vamos a considerar los cuatro pasos sobre los que se aplica el filtro din´amico, el resto son id´enticos: •Dado un paso [Nγ→Pγδ•Mγν, i, j |p0, q0] [> → Rβ•, j, m |k, l] [Mγ→ω•, k, l |p, q] [Nγ→PγδMγ•ν, i, m |p∪p0, q ∪q0]∈ DAdjComp1 LC1 existe un paso [Nγ→δ•Mγν, i, j |p0, q0] [> → Rβ•, j, m |k, l] [Mγ→ω•, k, l |p, q] [Nγ→δMγ•ν, i, m |p∪p0, q ∪q0]∈ DAdjComp LC y, por tanto, existe la inferencia [Nγ→Pγδ•Mγν, i, j |p0, q0] [> → Rβ•, j, m |k, l] [Mγ→ω•, k, l |p, q] `LC [Nγ→PγδMγ•ν, i, m |p∪p0, q∪q0] 40 •Dado un paso [Nγ→ •Mγν, j, j | −,−] [> → Rβ•, j, m |k, l] [Mγ→ω•, k, l |p, q] [Nγ→Mγ•ν, j, m |p, q]∈ DAdjComp2 LC1 existe un paso [Nγ→δ•Mγν, i, j |p0, q0] [> → Rβ•, j, m |k, l] [Mγ→ω•, k, l |p, q] [Nγ→δMγ•ν, i, m |p∪p0, q ∪q0]∈ DAdjComp LC y, por tanto, existe la inferencia [Nγ→ •Mγν, j, j | −,−] [> → Rβ•, j, m |k, l] [Mγ→ω•, k, l |p, q] `LC [Nγ→Mγ•ν, j, m |p, q] •Dado un paso [Nγ→Pγδ•Mγν, i, j |p, q] [Mγ→ν•, j, k |p0, q0] [Nγ→PγδMγ•ν, i, k |p∪p0, q ∪q0]∈ DComp1 LC1 existe un paso [Nγ→δ•Mγν, i, j |p, q] [Mγ→ν•, j, k |p0, q0] [Nγ→δMγ•ν, i, k |p∪p0, q ∪q0]∈ DComp LC y, por tanto, existe la inferencia [Nγ→Pγδ•Mγν, i, j |p, q] [Mγ→ν•, j, k |p0, q0]`LC [Nγ→PγδMγ•ν, i, k |p∪p0, q∪q0] •Dado un paso [Nγ→ •Mγν, j, j | −,−] [Mγ→ν•, j, k |p, q] [Nγ→Mγ•ν, j, k |p, q]∈ DComp2 LC1 41 Teorema 8.3 Relaci´on entre los esquemas LC yLC0 Se mantiene la siguiente relaci´on de contracci´on de secuencias deductivas: LC sc =⇒LC0 Prueba Tenemos que probar que: 1. ILC0⊆ ILC 2. `∗ LC0⊆`∗ LC Lo primero es cierto por definici´on, ya que los dominios de ambos esquemas son iguales: ILC =ILC0 Para probar que `∗ LC0⊆`∗ LC debemos demostrar que DLC0⊆`∗ LC. Veamos cada caso particular: •Un paso deductivo DLFt LC0es equivalente a la secuencia formada por un paso DLCpre LC [Nβ→δ•Eβν, j, k | −,−] [Fβ→ •⊥, k, k | −,−] seguido de otro DLFt LC [Fβ→ •⊥, k, k | −,−] [a, k, k + 1] [Oγ→Pγ•ν, k, k + 1 | −,−] •Un paso deductivo DLFε LC0es equivalente a la secuencia formada por un paso DLCpre LC [Nβ→δ•Eβν, j, k | −,−] [Fβ→ •⊥, k, k | −,−] seguido de otro DLFε LC [Fβ→ •⊥, k, k | −,−] [Oγ→Pγ•ν, k, k | −,−] •Un paso deductivo DLFpre LC0es equivalente a la secuencia formada por un paso DLCpre LC [Nβ→δ•Eβν, j, k | −,−] [Fβ→ •⊥, k, k | −,−] 48 seguido de otro DLFpre LC [Fβ→ •⊥, k, k | −,−] [Oγ→ •Pγν, k, k | −,−] •Un paso deductivo DFootComp LC0es equivalente a la secuencia formada por un paso DLCpre LC [Nβ→δ•Eβν, j, k | −,−] [Fβ→ •⊥, k, k | −,−] seguido de otro DFootComp LC [Fβ→ •⊥, k, k | −,−] [Mγ→ν•, k, l |p, q] [Fβ→ ⊥•, k, l |k, l] •El resto de pasos deductivos es igual en ambos esquemas Teorema 8.4 Relaci´on entre los esquemas buE ybuLC Se mantiene las siguientes relaciones de contracci´on de secuencias deductivas y filtros din´amicos: buE sc =⇒buLC2 df =⇒buLC Prueba Antes de iniciar la demostraci´on vamos a definir el nuevo esquemas que nos servir´a de enlace para establecer la relaci´on entre los dos esquemas de inter´es. El dominio del esquema buLC2es igual al del esquema buLC: IbuLC2=IbuLC El conjunto de pasos deductivos es: DbuLC2=DLCt buLC2∪ DLCε buLC2∪ DLCn buLC2∪ DLCcad buLC2∪ DFoot buLC2∪ DScan buLC2∪ Dε buLC2∪ DComp buLC2∪ DAdjComp buLC2 donde todos los pasos son id´enticos al los hom´onimos de buLC, excepto el paso DFoot buLC. DLCt buLC2=DLCt buLC 49 DLCε buLC2=DLCε buLC DLCn buLC2=DLCn buLC DLCcad buLC2=DLCcad buLC DScan buLC2=DScan buLC Dε buLC2=Dε buLC DComp buLC2=DComp buLC DAdjComp buLC2=DAdjComp buLC DFoot buLC2=[Fβ→ ⊥•, k, l, k, l] El conjunto de ´ıtems finales tambi´en es igual al del esquema buLC: FbuLC2=FbuLC Ahora probaremos que buE sc =⇒buLC2, para lo cual tenemos que demostrar que: 1. IbuLC2⊆ IbuE 2. `∗ buLC2⊆`∗ buE Lo primero es cierto por definici´on, ya que el dominio del esquema buLC2es igual al del esquema buE al que le hemos suprimido los ´ıtems con el punto al comienzo de la regla: IbuLC2⊂ IbuE Para probar que `∗ buLC2⊆`∗ buE debemos demostrar que DbuLC2⊆`∗ buE. Veamos cada uno de los pasos: •Un paso deductivo DLCt buLC2es equivalente a la secuencia formada por un paso DIni buE [Oγ→ •Pγν, j, j | −,−] seguido de otro DScan buE [Oγ→ •Pγν, j, j | −,−], [a, j, j + 1] [Oγ→Pγ•ν, j, j + 1 | −,−] 50 •Un paso deductivo DLCε buLC2es equivalente a la secuencia formada por un paso DIni buE [Oγ→ •Pγν, j, j | −,−] seguido de otro Dε buE [Oγ→ •Pγν, j, j | −,−] [Oγ→Pγ•ν, j, j | −,−] •Un paso deductivo DLCn buLC2es equivalente a la secuencia formada por un paso DIni buE [Qγ→ •Oγω, j, j | −,−] seguido de otro DComp buE [Oγ→ν•, j, k |p, q] [Qγ→ •Oγω, j, j | −,−] [Qγ→Oγ•ω, j, k |p, q] •Un paso deductivo DLCcad buLC2es equivalente a la secuencia formada por un paso DIni buE [Qγ→ •Oγω, j, j | −,−] seguido de otro DAdjComp buE [> → Rβ•, j, m |k, l] [Oγ→δ•, k, l |p, q] [Qγ→ •Oγν, j, j | −,−] [Qγ→Oγ•ν, j, m |p, q] •El paso de compleci´on de pie es id´entico en ambos esquemas: DFoot buLC2=DFoot buE •El resto de pasos deductivos del esquema buLC2est´an incluidos en las inferencias de sus hom´onimos del esquema buE, ya que estos ´ultimos contemplan las operaciones en cualquier posici´on, mientras que los pertenecientes a buLC2s´olo son aplicables en nodos que no sean hijos izquierdos. Por tanto, se cumple: DScan buLC2⊂ DScan buE 51 Dε buLC2⊂ Dε buE DComp buLC2⊂ DComp buE DAdjComp buLC2⊂ DAdjComp buE Ahora probaremos que buLC2 df =⇒buLC, para lo cual tenemos que demostrar que: 1. IbuLC ⊆ IbuLC2 2. `buLC⊆`buLC2 Lo primero es cierto por definici´on, ya que los dominios de ambos esquemas son iguales: IbuLC =IbuLC2 Para probar que `buLC⊆`buLC2debemos demostrar que DbuLC ⊆`buLC2. Todos los pasos deductivos con la misma denominaci´on son id´enticos en ambos esquemas, con la excepci´on del paso DFoot buLC que incorpora un antecedente. Para este caso, se cumple que dado un paso [Oγ→ν•, k, l, p, q] [Fβ→ ⊥•, k, l, k, l]∈ DFoot buLC existe un paso [Fβ→ ⊥•, k, l, k, l]∈ DFoot buLC2 y, por tanto, existe la inferencia [Oγ→ν•, k, l, p, q]`buLC2[Fβ→ ⊥•, k, l, k, l] . Teorema 8.5 Relaci´on entre los esquemas EyLC Se mantiene la siguiente relaci´on de contracci´on de secuencias deductivas: Esc =⇒LC Prueba Tenemos que demostrar que: 1. ILC ⊆ IE 2. `∗ LC⊆`∗ E 52 Lo primero es cierto por definici´on, ya que el dominio del esquema LC es igual al del esquema Eal que le hemos suprimido los ´ıtems con el punto al comienzo de la regla en ciertos casos: ILC ⊂ IE Para probar que `∗ LC⊆`∗ Edebemos demostrar que DLC ⊆`∗ E. Veamos cada uno de los pasos: •Un paso DLIt LC es equivalente a la secuencia formada por un paso DIni E [> → •Rα,0,0| −,−] seguido de una secuencia de pasos DPred E [> → •Rα,0,0| −,−] [Rα→ •Mγν, 0,0| −,−] [Mγ→ •Oγν, 0,0| −,−] [Oγ→ •Pγδ, 0,0| −,−] y de un paso DScan E [Oγ→ •Pγν, 0,0| −,−], [a, 0,1] [Oγ→Pγ•ν, 0,1| −,−] •Un paso DLIε LC es equivalente a la secuencia formada por un paso DIni E [> → •Rα,0,0| −,−] seguido de una secuencia de pasos DPred E [> → •Rα,0,0| −,−] [Rα→ •Mγν, 0,0| −,−] [Mγ→ •Oγν, 0,0| −,−] [Oγ→ •Pγδ, 0,0| −,−] y de un paso Dε E[Oγ→ •Pγν, 0,0| −,−] [Oγ→Pγ•ν, 0,0| −,−] 53 •Un paso DLIpre LC es equivalente a la secuencia formada por un paso DIni E [> → •Rα,0,0| −,−] seguido de una secuencia de pasos DPred E [> → •Rα,0,0| −,−] [Rα→ •Mγν, 0,0| −,−] [Mγ→ •Oγν, 0,0| −,−] [Oγ→ •Pγδ, 0,0| −,−] •Un paso DLCt LC es equivalente a una secuencia de pasos DPred E [Nγ→δ•Mγν, i, j |p, q] [Mγ→ •Oγω, j, j | −,−] [Mγ→ •Oγω, j, j | −,−] [Oγ→ •Pγν, j, j | −,−] seguida de un paso DScan E [Oγ→ •Pγν, j, j | −,−], [a, j, j + 1] [Oγ→Pγ•ν, j, j + 1 | −,−] •Un paso DLCε LC es equivalente a una secuencia de pasos DPred E [Nγ→δ•Mγν, i, j |p, q] [Mγ→ •Oγω, j, j | −,−] [Mγ→ •Oγω, j, j | −,−] [Oγ→ •Pγν, j, j | −,−] seguida de un paso Dε E [Oγ→ •Pγν, j, j | −,−] [Oγ→Pγ•ν, j, j | −,−] •Un paso DLCpre LC es equivalente a una secuencia de pasos DPred E: [Nγ→δ•Mγν, i, j |p, q] [Mγ→ •Oγω, j, j | −,−] [Mγ→ •Oγω, j, j | −,−] [Oγ→ •Pγν, j, j | −,−] 54 •Un paso DLCn LC es equivalente a una secuencia de pasos DPred E [Nγ→δ•Mγν, i, j |p, q] [Mγ→ •Oγω, j, j | −,−] [Mγ→ •Oγω, j, j | −,−] [Oγ→ •Pγν, j, j | −,−] seguida de un paso DComp E [Pγ→δ•, j, k |p, q] [Oγ→ •Pγν, j, j | −,−] [Oγ→Pγ•ν, j, k |p, q] •Un paso DLAt LC es equivalente a la secuencia formada por un paso DAdjPred E[Nγ→δ•Mγν, i, j |p, q] [> → •Rβ, j, j | −,−] una secuencia de pasos DPred E [> → •Rβ, j, j | −,−] [Rβ→ •Mβω, j, j | −,−] [Mβ→ •Oβω, j, j | −,−] [Oβ→ •Pβν, j, j | −,−] y un paso DScan E [Oβ→ •Pβν, j, j | −,−], [a, j, j + 1] [Oβ→Pβ•ν, j, j + 1 | −,−] •Un paso DLAε LC es equivalente a la secuencia formada por un paso DAdjPred E[Nγ→δ•Mγν, i, j |p, q] [> → •Rβ, j, j | −,−] una secuencia de pasos DPred E [> → •Rβ, j, j | −,−] [Rβ→ •Mβω, j, j | −,−] 55 [Mβ→ •Oβω, j, j | −,−] [Oβ→ •Pβν, j, j | −,−] y un paso Dε E [Oβ→ •Pβν, j, j | −,−] [Oβ→Pβ•ν, j, j | −,−] •Un paso DLApre LC es equivalente a la secuencia formada por un paso DAdjPred E[Nγ→δ•Mγν, i, j |p, q] [> → •Rβ, j, j | −,−] seguido de una secuencia de pasos DPred E [> → •Rβ, j, j | −,−] [Rβ→ •Mβω, j, j | −,−] [Mβ→ •Oβω, j, j | −,−] [Oβ→ •Pβν, j, j | −,−] •Un paso DLFt LC es equivalente a la secuencia formada por un paso DFootPred E [Fβ→ •⊥, k, k | −,−] [Nγ→ •Mγν, k, k | −,−] una secuencia de pasos DPred E [Nγ→ •Mγν, k, k | −,−] [Mγ→ •Oγω, k, k | −,−] [Mγ→ •Oγω, k, k | −,−] [Oγ→ •Pγν, k, k | −,−] y un paso DScan E [Oγ→ •Pγν, k, k | −,−], [a, k, k + 1] [Oγ→Pγ•ν, k, k + 1 | −,−] •Un paso DLFε LC es equivalente a la secuencia formada por un paso DFootPred E [Fβ→ •⊥, k, k | −,−] [Nγ→ •Mγν, k, k | −,−] 56 una secuencia de pasos DPred E [Nγ→ •Mγν, k, k | −,−] [Mγ→ •Oγω, k, k | −,−] [Mγ→ •Oγω, k, k | −,−] [Oγ→ •Pγν, k, k | −,−] y un paso Dε E[Oγ→ •Pγν, k, k | −,−] [Oγ→Pγ•ν, k, k | −,−] •Un paso DLFpre LC es equivalente a la secuencia formada por un paso DFootPred E [Fβ→ •⊥, k, k | −,−] [Nγ→ •Mγν, k, k | −,−] seguido por una secuencia de pasos DPred E [Nγ→ •Mγν, k, k | −,−] [Mγ→ •Oγω, k, k | −,−] [Mγ→ •Oγω, k, k | −,−] [Oγ→ •Pγν, k, k | −,−] •Los pasos deductivos de reconocimiento del esquema LC est´an incluidos en las inferencias de sus hom´onimos del esquema E, ya que estos ´ultimos contemplan las operaciones en cualquier posici´on, mientras que los pertenecientes a LC s´olo son aplicables en nodos que no sean hijos izquierdos. Por tanto, se cumple: DScan LC ⊂ DScan E Dε LC ⊂ Dε E •El resto de pasos son id´enticos en ambos esquemas: DComp LC =DComp E DAdjComp LC =DAdjComp E DFootComp LC =DFootComp E 57