Inducción de lenguajes regulares

En la teoría del aprendizaje computacional , la inducción de lenguajes regulares se refiere a la tarea de aprender una descripción formal (por ejemplo, una gramática) de un lenguaje regular a partir de un conjunto dado de cadenas de ejemplo. Aunque E. Mark Gold ha demostrado que no todos los lenguajes regulares pueden aprenderse de esta manera (véase la identificación de lenguajes en el límite ), se han investigado enfoques para una variedad de subclases. Se describen en este artículo. Para el aprendizaje de gramáticas más generales, consulte Inducción gramatical .

Definiciones

Un lenguaje regular se define como un conjunto (finito o infinito) de cadenas que se pueden describir mediante uno de los formalismos matemáticos llamados " autómata finito ", " gramática regular " o " expresión regular ", todos los cuales tienen el mismo poder expresivo. Dado que el último formalismo conduce a notaciones más cortas, se presentará y utilizará aquí. Dado un conjunto Σ de símbolos (también conocido como alfabeto), una expresión regular puede ser cualquiera de

  • ∅ (que denota el conjunto vacío de cadenas),
  • ε (que denota el conjunto singleton que contiene solo la cadena vacía),
  • a (donde a es cualquier carácter en Σ; que denota el conjunto singleton que contiene solo la cadena de un solo carácter a ),
  • r  +  s (donde r y s son, a su vez, expresiones regulares más simples; que denotan la unión de sus conjuntos)
  • r  ⋅  s (que denota el conjunto de todas las posibles concatenaciones de cadenas del conjunto de r y s ),
  • r  + (que denota el conjunto de n repeticiones de cadenas del conjunto de r , para cualquier n ≥ 1), o
  • r  * (denota de manera similar el conjunto de repeticiones n -veces, pero también incluye la cadena vacía, vista como repetición 0-veces).

Por ejemplo, utilizando Σ = {0,1}, la expresión regular (0+1+ε)⋅(0+1) denota el conjunto de todos los números binarios con uno o dos dígitos (se permite cero a la izquierda), mientras que 1⋅(0+1) * ⋅0 denota el conjunto (infinito) de todos los números binarios pares (sin ceros a la izquierda).

Dado un conjunto de cadenas (también llamadas "ejemplos positivos"), la tarea de la inducción del lenguaje regular es llegar a una expresión regular que denote un conjunto que las contenga todas. Como ejemplo, dado {1, 10, 100}, una descripción "natural" podría ser la expresión regular 1⋅0 * , correspondiente a la caracterización informal " un 1 seguido de arbitrariamente muchos (quizás incluso ninguno) 0 ". Sin embargo, (0+1) * y 1+(1⋅0)+(1⋅0⋅0) es otra expresión regular, que denota el conjunto más grande (asumiendo Σ = {0,1}) y el más pequeño que contiene las cadenas dadas, y se denominan sobregeneralización trivial y subgeneralización , respectivamente. Algunos enfoques funcionan en un entorno extendido donde también se da un conjunto de cadenas de "ejemplo negativo"; luego, se debe encontrar una expresión regular que genere todos los ejemplos positivos, pero ninguno de los negativos.

Red de autómatas

Orden parcial de autómatas que generan las cadenas 1, 10 y 100 (ejemplos positivos). Para cada una de las cadenas de ejemplo negativas 11, 1001, 101 y 0, se muestra el conjunto superior de autómatas que la generan. Los únicos autómatas que generan todos los {1, 10, 100} pero ninguno de los {11, 1001, 101, 0} son el autómata trivial inferior y el correspondiente a la expresión regular 1⋅0 * .

Dupont et al. han demostrado que el conjunto de todos los autómatas finitos estructuralmente completos [nota 1] que generan un conjunto de entrada dado de cadenas de ejemplo forma una red , con el autómata trivial subgeneralizado y el autómata trivial sobregeneralizado como elementos inferior y superior, respectivamente. Cada miembro de esta red se puede obtener factorizando el autómata subgeneralizado mediante una relación de equivalencia apropiada .

Para el conjunto de cadenas de ejemplo anterior {1, 10, 100}, la imagen muestra en su parte inferior el autómata subgeneralizado A a,b,c,d en gris , que consta de los estados a , b , c y d . En el conjunto de estados {a,b,c,d}, existen un total de 15 relaciones de equivalencia, que forman una red. Al asignar [nota 2] cada equivalencia E al lenguaje de autómata cociente correspondiente L ( A a,b,c,d / E ) se obtiene el conjunto parcialmente ordenado que se muestra en la imagen. El lenguaje de cada nodo se denota mediante una expresión regular. El lenguaje puede ser reconocido por autómatas cocientes con respecto a diferentes relaciones de equivalencia, todas las cuales se muestran debajo del nodo. Una flecha entre dos nodos indica que el lenguaje del nodo inferior es un subconjunto propio del del nodo superior.

Si se dan cadenas de ejemplo positivas y negativas, Dupont et al. construyen la red a partir de los ejemplos positivos y luego investigan el borde de separación entre los autómatas que generan algún ejemplo negativo y los que no lo hacen. Los más interesantes son aquellos autómatas inmediatamente debajo del borde. [1] En la imagen, se muestran los bordes de separación para las cadenas de ejemplo negativas 11 ( verde ), 1001 ( azul) , 101 ( cian ) y 0 ( rojo ).

Coste y Nicolas presentan un método de búsqueda propio dentro de la red, que relacionan con el paradigma del espacio de versiones de Mitchell . Para encontrar el borde de separación, utilizan un algoritmo de coloración de grafos sobre la relación de desigualdad de estados inducida por los ejemplos negativos. [2] Posteriormente, investigan varias relaciones de ordenación sobre el conjunto de todas las posibles fusiones de estados. [3]

Kudo y Shimbo utilizan la representación mediante factorizaciones de autómatas para brindar un marco único para los siguientes enfoques (esquematizados a continuación):

  • Lenguajes k-reversibles y el enfoque de seguimiento de "agrupamiento de cola",
  • Autómatas sucesores y el método predecesor-sucesor, y
  • enfoques basados ​​en bombeo (la integración del marco fue cuestionada por Luzeaux, [4] sin embargo).

Se demuestra que cada uno de estos enfoques corresponde a un tipo particular de relaciones de equivalencia utilizadas para la factorización. [5]

Aproches

a-lenguajes reversibles

Angluin considera los llamados autómatas regulares " k -reversibles", es decir, autómatas deterministas en los que cada estado puede alcanzarse desde como máximo un estado siguiendo una cadena de transición de longitud k . Formalmente, si Σ, Q y δ denotan el alfabeto de entrada, el conjunto de estados y la función de transición de un autómata A , respectivamente, entonces A se llama k -reversible si: ∀ a 0 , ..., a k ∈ Σ ∀ s 1 , s 2 ∈ Q : δ * ( s 1 , a 0 ... a k ) = δ * ( s 2 , a 0 ... a k ) ⇒ s 1  =  s 2 , donde δ * significa la extensión homomórfica de δ a palabras arbitrarias. Angluin da un algoritmo cúbico para el aprendizaje del lenguaje k -reversible más pequeño a partir de un conjunto dado de palabras de entrada; para k = 0, el algoritmo tiene una complejidad casi lineal. [6] [7] La ​​unicidad de estado requerida después de k  + 1 símbolos dados obliga a unificar los estados del autómata, lo que conduce a una generalización adecuada diferente del autómata trivial subgeneralizado. Este algoritmo se ha utilizado para aprender partes simples de la sintaxis inglesa; [8] más tarde, se ha proporcionado una versión incremental. [9] Otro enfoque basado en autómatas k -reversibles es el método de agrupamiento de colas . [10]

Autómatas sucesores

A partir de un conjunto dado de cadenas de entrada, Vernadat y Richetin construyen un llamado autómata sucesor , que consiste en un estado para cada carácter distinto y una transición entre los estados de cada dos caracteres adyacentes. [11] Por ejemplo, el conjunto de entrada singleton { aabbaabb } conduce a un autómata correspondiente a la expresión regular ( a + ⋅ b + ) * .

Una extensión de este enfoque es el método predecesor-sucesor que generaliza cada repetición de carácter inmediatamente a un Kleene + y luego incluye para cada carácter el conjunto de sus posibles predecesores en su estado. Los autómatas sucesores pueden aprender exactamente la clase de lenguajes locales . Dado que cada lenguaje regular es la imagen homomórfica de un lenguaje local, las gramáticas de la clase anterior se pueden aprender mediante el levantamiento , si se proporciona un homomorfismo apropiado (dependiendo de la aplicación prevista) . En particular, existe un homomorfismo de este tipo para la clase de lenguajes que se pueden aprender mediante el método predecesor-sucesor. [12] La capacidad de aprendizaje de los lenguajes locales se puede reducir a la de los lenguajes k -reversibles. [13] [14]

Primeros enfoques

Ilustración del lema de bombeo para autómatas regulares

Chomsky y Miller (1957) [15] utilizaron el lema de bombeo : adivinan una parte v de una cadena de entrada uvw e intentan construir un ciclo correspondiente en el autómata a aprender; utilizando consultas de pertenencia preguntan, para un k apropiado , cuál de las cadenas uw , uvvw , uvvvw , ..., uv k w también pertenece al lenguaje a aprender, refinando así la estructura de su autómata. En 1959, Solomonoff generalizó este enfoque a los lenguajes libres de contexto , que también obedecen a un lema de bombeo . [16]

Autómatas de cubierta

Câmpeanu et al. aprenden un autómata finito como una representación compacta de un lenguaje finito grande. Dado dicho lenguaje F , buscan un llamado autómata de cobertura A tal que su lenguaje L ( A ) cubra F en el siguiente sentido: L ( A ) ∩ Σ ≤  l = F , donde l es la longitud de la cadena más larga en F , y Σ ≤  l denota el conjunto de todas las cadenas no más largas que l . Si existe tal autómata de cobertura, F está determinado de forma única por A y l . Por ejemplo, F = { ad , read , reread  } tiene l = 6 y un autómata de cobertura correspondiente a la expresión regular ( r ⋅ e ) * ⋅ a ⋅ d .

Para dos cadenas x e y , Câmpeanu et al. definen x ~ y si xz  ∈  F ⇔ yz  ∈  F para todas las cadenas z de una longitud tal que tanto xz como yz no sean más largas que l . [17] Basándose en esta relación, cuya falta de transitividad [nota 3] causa considerables problemas técnicos, dan un algoritmo O ( n 4 ) [nota 4] para construir a partir de F un autómata de cobertura A de recuento de estados mínimo. Además, para la unión, intersección y diferencia de dos lenguajes finitos proporcionan operaciones correspondientes en sus autómatas de cobertura. [18] [19] Păun et al. mejoran la complejidad temporal a O ( n 2 ). [20]

Autómatas residuales

Derivada de Brzozowski (sobre fondo rojo) de un conjunto de cadenas de diccionario con respecto a " con "

Para un conjunto S de cadenas y una cadena u , la derivada de Brzozowski u −1 S se define como el conjunto de todas las cadenas en reposo obtenibles de una cadena en S cortando su prefijo u (si es posible), formalmente: u −1 S = { v ∈ Σ * : uv ∈ S } , cf. figura. [21] Denis et al. definen un autómata residual como un autómata finito no determinista A donde cada estado q corresponde a una derivada de Brzozowski de su lenguaje aceptado L ( A ), formalmente: ∀ q ∈ Q ∃ u ∈Σ * : L ( A , q ) = u −1 L ( A ), donde L ( A , q ) denota el lenguaje aceptado de q como estado inicial.

Demuestran que cada lenguaje regular es generado por un autómata residual mínimo determinado de forma única. Sus estados son derivados de Brzozowski ∪ -indecomponibles, y puede ser exponencialmente más pequeño que el autómata determinista mínimo. Además, muestran que los autómatas residuales para lenguajes regulares no pueden aprenderse en tiempo polinomial, incluso suponiendo entradas de muestra óptimas. Ofrecen un algoritmo de aprendizaje para autómatas residuales y prueban que aprende el autómata a partir de su muestra característica de cadenas de entrada positivas y negativas. [22] [23]

Aprendizaje de consultas

Los lenguajes regulares no pueden aprenderse en tiempo polinomial utilizando solo consultas de membresía [24] o utilizando solo consultas de equivalencia. [25] Sin embargo, Angluin ha demostrado que los lenguajes regulares pueden aprenderse en tiempo polinomial utilizando consultas de membresía y consultas de equivalencia, y ha proporcionado un algoritmo de aprendizaje denominado L* que hace exactamente eso. [26] El algoritmo L* se generalizó posteriormente para generar un NFA ( autómata finito no determinista ) en lugar de un DFA ( autómata finito determinista ), a través de un algoritmo denominado NL*. [27] Este resultado se generalizó aún más y se ideó un algoritmo que genera un AFA ( autómata finito alternante ) denominado AL*. [28] Se observa que los NFA pueden ser exponencialmente más concisos que los DFA, y que los AFA pueden ser exponencialmente más concisos que los NFA y doblemente exponencialmente más concisos que los DFA. [29] El algoritmo L* y sus generalizaciones tienen implicaciones significativas en el campo de la teoría de autómatas y el aprendizaje formal de lenguajes, ya que demuestran la viabilidad de aprender de manera eficiente modelos de autómatas más expresivos, como NFA y AFA, que pueden representar lenguajes de manera más concisa y capturar patrones más complejos en comparación con los DFA tradicionales.

Expresiones regulares reducidas

Brill define una expresión regular reducida como cualquiera de

  • a (donde a es cualquier carácter en Σ; que denota el conjunto singleton que contiene solo la cadena de un solo carácter a ),
  • ¬ a (que denota cualquier otro carácter individual en Σ excepto a ),
  • • (que denota cualquier carácter individual en Σ)
  • a * , (¬ a ) * , o • * (que denotan arbitrariamente muchas, posiblemente cero, repeticiones de caracteres del conjunto de a , ¬ a o •, respectivamente), o
  • r  ⋅  s (donde r y s son, a su vez, expresiones regulares reducidas más simples; que denotan el conjunto de todas las posibles concatenaciones de cadenas del conjunto de r y s ) .

Dado un conjunto de cadenas de entrada, construye paso a paso un árbol con cada rama etiquetada por una expresión regular reducida que acepta un prefijo de algunas cadenas de entrada, y cada nodo etiquetado con el conjunto de longitudes de los prefijos aceptados. Su objetivo es aprender reglas de corrección para errores ortográficos en inglés, [nota 5] en lugar de consideraciones teóricas sobre la capacidad de aprendizaje de las clases de lenguaje. En consecuencia, utiliza heurísticas para podar la construcción del árbol, lo que conduce a una mejora considerable en el tiempo de ejecución. [30]

Aplicaciones

Notas

  1. ^ es decir, autómatas finitos sin estados y transiciones innecesarios, con respecto al conjunto de cadenas de entrada dado
  2. ^ Esta aplicación no es un homomorfismo reticular , sino sólo una aplicación monótona .
  3. ^ Por ejemplo, F = { aab , baa , aabb } conduce a aab ~ aabb (solo se debe considerar z = ε para comprobar esto) y aabb ~ baa (de manera similar), pero no aab ~ baa (debido al caso z = b ). Según Câmpeanu et al. (2001, Lema 1, p.5), sin embargo, x ~ y ∧ y ~ z → x ~ z se cumple para las cadenas x , y , z con | x | ≤ | y | ≤ | z |.
  4. ^ donde n es el número de estados de un DFA A F tal que L ( A F ) = F
  5. ^ Por ejemplo: Reemplazar " pasado " por " pasado " en el contexto "(¬ t ⋅ o ) * ⋅ SINGULAR_NOUN ⋅ pasado "

Referencias

  1. ^ P. Dupont; L. Miclet; E. Vidal (1994). "¿Cuál es el espacio de búsqueda de la inferencia regular?". En RC Carrasco; J. Oncina (eds.). Actas del Segundo Coloquio Internacional sobre Inferencia Gramatical (ICGI): Inferencia gramatical y aplicaciones . LNCS. Vol. 862. Springer. págs. 25–37. CiteSeerX  10.1.1.54.5734 .
  2. ^ F. Coste; J. Nicolas (1997). "Inferencia regular como un problema de coloración de grafos". Proc. Taller ICML sobre inferencia gramatical, inducción de autómatas y adquisición del lenguaje . págs. 9–7. CiteSeerX 10.1.1.34.4048 . 
  3. ^ F. Coste; J. Nicolas (1998). "Cómo considerar fusiones de estados incompatibles puede reducir el árbol de búsqueda por inducción de DFA". En Vasant Honavar; Giora Slutzki (eds.). Inferencia gramatical, 4.º Coloquio internacional, ICGI . LNCS. Vol. 1433. Springer. págs. 199–210. CiteSeerX 10.1.1.34.2050 . 
  4. ^ Dominique Luzeaux (agosto de 1997). "Un enfoque universal para la inferencia de gramática regular positiva". Proc. 15.° Congreso Mundial IMACS sobre Computación Científica, Modelado y Matemática Aplicada . Archivado desde el original el 13 de enero de 2005. Consultado el 26 de noviembre de 2013 .
  5. ^ M. Kudo; M. Shimbo (1988). "Técnicas eficientes de inferencia gramatical regular mediante el uso de similitudes parciales y sus relaciones lógicas". Reconocimiento de patrones . 21 (4): 401–409. Código Bibliográfico :1988PatRe..21..401K. doi :10.1016/0031-3203(88)90053-2.
  6. ^ D. Angluin (1981). "Una nota sobre el número de consultas necesarias para identificar lenguajes regulares". Información y control . 51 : 76–87. doi :10.1016/s0019-9958(81)90090-5.
  7. ^ D. Angluin (1982). "Inferencia de lenguajes reversibles". J. ACM . 293 (3): 741–765. CiteSeerX 10.1.1.232.8749 . doi :10.1145/322326.322334. S2CID  18300595. 
  8. ^ Robert C. Berwick; Samuel F. Pilato (1987). "Aprendizaje de sintaxis por inducción de autómatas". Aprendizaje automático . 2 (1): 9–38. doi : 10.1007/bf00058753 .
  9. ^ Rajesh Parekh; Codrin Nichitiu; Vasant Honavar (enero de 1997). Un algoritmo incremental de tiempo polinomial para la inferencia de gramática regular (informe técnico). Grupo de investigación de IA, Universidad Estatal de Iowa, pág. 14. TR 97-03.
  10. ^ L. Miclet; C. Faure (1985). Reconnaissance des Formes Structurelle: Développement et Tendances (Informe técnico). INRIA.
  11. ^ F. Vernadat; M. Richetin (1984). "Inferencia regular para el reconocimiento de patrones sintácticos: un estudio de caso". Actas de la 7.ª Conferencia Internacional sobre Reconocimiento de Patrones (ICPR) . págs. 1370–1372.
  12. ^ P. García; E. Vidal; F. Casacuberta (1987). "Lenguajes locales, el método sucesor y un paso hacia una metodología general para la inferencia de gramáticas regulares". IEEE Transactions on Pattern Analysis and Machine Intelligence . 9 .
  13. ^ Takashi Yokomori (octubre de 1989). "Aprendizaje eficiente de lenguajes libres de contexto". En KP Jantke [en alemán] (ed.). Proc. Int. Workshop AII . LNAI. Vol. 397. Springer. págs. 104–123. doi :10.1007/3-540-51734-0_54. ISBN . 978-3-540-51734-4.
  14. ^ Satoshi Kobayashi; Takashi Yokomori (1994). "Aprendizaje de concatenaciones de lenguajes comprobables localmente a partir de datos positivos". En Setsuo Arikawa; Klaus P. Jantke (eds.). Proc. 5th ALT . LNAI. Vol. 872. Springer. págs. 405–422. CiteSeerX 10.1.1.52.4678 . 
  15. ^ N. Chomsky; GA Miller (1957). Concepción de patrones (informe técnico). ASTIA. Documento AD110076.
  16. ^ R. Solomonoff (junio de 1959). "Un nuevo método para descubrir las gramáticas de los lenguajes de estructura sintáctica". Proc. Int. Conf. on Information Processing . R. Oldenbourg. págs. 285–290.
  17. ^ Esta relación generaliza la relación RF del teorema de Myhill-Nerode . Se ha investigado con más detalle en la sección 3 de: Cynthia Dwork; Larry Stockmeyer (1990). "A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata". SIAM Journal on Computing . 19 (6): 1011–1023. doi :10.1137/0219069.
  18. ^ por Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (1998). "Autómatas de cobertura mínima para lenguajes finitos". En J.-M. Champarnaud; D. Maurel; D. Ziadi (eds.). Proc. Taller sobre implementación de autómatas (WIA) (PDF) . LNCS . Vol. 1660. Springer. págs. 43–56. CiteSeerX 10.1.1.37.431 . doi :10.1007/3-540-48057-9_4. ISBN  978-3-540-66652-3.
  19. ^ Cezar Campeanu; Nicolae Santean; Sheng Yu (2001). "Autómatas de cobertura mínima para lenguajes finitos". Informática Teórica . 267 (1–2): 3–16. CiteSeerX 10.1.1.550.3055 . doi : 10.1016/s0304-3975(00)00292-9 . 
  20. ^ Andrei Păun; Nicolae Sântean; Sheng Yu (septiembre de 2001). "Un algoritmo O(n 2 ) para construir autómatas de cobertura mínima para lenguajes finitos". En Sheng Yu; Andrei Păun (eds.). Actas de la 5.ª Conferencia Internacional sobre Implementación y Aplicación de Autómatas (CIAA) (PDF) . LNCS. Vol. 2088. Springer. págs. 243–251. ISBN. 978-3-540-42491-8.
  21. ^ Janusz A. Brzozowski (1964). "Derivadas de expresiones regulares". J ACM . 11 (4): 481–494. doi : 10.1145/321239.321249 . S2CID  14126942.
  22. ^ François Denis; Aurélien Lemay; Alain Terlutte (2000). "Aprendizaje de lenguajes regulares mediante autómatas finitos no deterministas". En Arlindo L. Oliveira (ed.). Inferencia gramatical: algoritmos y aplicaciones, 5.º coloquio internacional, ICGI . LNCS. Vol. 1891. Springer. págs. 39–50. CiteSeerX 10.1.1.13.5559 . ISBN.  978-3-540-41011-9.
  23. ^ François Denis; Aurélien Lemay; Alain Terlutte (2001). "Aprendizaje de lenguajes regulares mediante RFSA" (PDF) . Proc. ALT '01 .
  24. ^ Angluin, Dana (1995). "¿Cuándo no serán útiles las consultas de membresía?". Actas del vigésimo tercer simposio anual de la ACM sobre teoría de la computación - STOC '91 . pp. 444–454. doi : 10.1145/103418.103420 . ISBN . 9780897913973.S2CID 9960280  .
  25. ^ Angluin, Dana (1990). "Resultados negativos para consultas de equivalencia". Aprendizaje automático . 5 (2): 121–150. doi : 10.1007/BF00116034 . S2CID  189902172.
  26. ^ Angluin, Dana (1987). "Aprendizaje de conjuntos regulares a partir de consultas y contraejemplos". Información y computación . 75 (2): 87–106. doi : 10.1016/0890-5401(87)90052-6 .
  27. ^ Bollig; Habermehl; Kern; Leucker (2009). "Aprendizaje de NFA al estilo Angluin" (PDF) . 21.ª Conferencia conjunta internacional sobre inteligencia artificial .
  28. ^ Angluin; Eisenstat; Fisman (2015). "Aprendizaje de lenguajes regulares mediante autómatas alternantes". 24.ª Conferencia conjunta internacional sobre inteligencia artificial .
  29. ^ Mayer, AR; Stockmeyer, Larry J. (1995). "La complejidad de los problemas verbales: esta vez con intercalación". Información y computación . 115 .
  30. ^ de Eric Brill (2000). «Desambiguación basada en patrones para el procesamiento del lenguaje natural» (PDF) . Proc. EMNLP/VLC . Archivado desde el original (PDF) el 2018-02-16 . Consultado el 2018-02-16 .
  31. ^ Alvis Brazma; Inge Jonassen; Jaak Vilo; Esko Ukkonen (1998). "Descubrimiento de patrones en biosecuencias". En Vasant Honavar; Giora Slutzki (eds.). Inferencia Gramatical, IV Coloquio Internacional, ICGI . LNCS. vol. 1433. Saltador. págs. 257–270.
  32. ^ MS Waterman, ed. (enero de 1989). Métodos matemáticos para secuencias de ADN . CRC Press. ISBN 978-0849366642.
  33. ^ Fernando Pereira; Yves Schabes (1992). "Reestimación interna-externa para corpus parcialmente entre corchetes". Actas de la 30.ª Reunión Anual de la Asociación de Lingüística Computacional . págs. 128-135. doi :10.3115/981967.981984. S2CID  63967455.
  34. ^ Helena Ahonen (noviembre de 1996). Generación de gramáticas para documentos estructurados mediante métodos de inferencia gramatical (PDF) (doctorado). Informe. Vol. A-1996-4. Universidad de Helsinki, Departamento de Informática. S2CID  60722498. Archivado desde el original (PDF) el 12 de febrero de 2020.
  35. ^ Stephen Watkinson (1997). Inducción de la sintaxis musical (Máster). Departamento de Inteligencia Artificial, Universidad de Edimburgo. Archivado desde el original el 4 de junio de 2001.
  36. ^ Pedro P. Cruz-Alcázar; Enrique Vidal (1998). "Aprendizaje de gramáticas regulares para modelar el estilo musical: comparación de diferentes esquemas de codificación" (PDF) . En Vasant Honavar; Giora Slutzki (eds.). Inferencia gramatical, 4.º Coloquio internacional, ICGI . LNCS. Vol. 1433. Springer. pp. 211–222. doi :10.1007/BFb0054077. ISBN. 978-3-540-64776-8. S2CID  15302415. Archivado desde el original (PDF) el 16 de febrero de 2018.
  37. ^ Alejandro S. Saidi; Souad Tayeb-bey (1998). "Inferencia gramatical en el reconocimiento de documentos". En Vasant Honavar; Giora Slutzki (eds.). Inferencia Gramatical, IV Coloquio Internacional, ICGI . LNCS. vol. 1433. Saltador. págs. 175-186. ISBN 978-3-540-64776-8.
Obtenido de "https://es.wikipedia.org/w/index.php?title=Inducción_de_lenguas_regulares&oldid=1244311895"