Diferencia entre revisiones de «Inducción de lenguajes regulares»
mSin resumen de edición |
mSin resumen de edición |
||
| Línea 53: | Línea 53: | ||
=== Autómata residual === |
=== Autómata residual === |
||
Para un conjunto ''S'' de cadenas y una cadena ''u'', la derivada de Brzozowski<span data-ve-clipboard-key="0.03473874744820726-33"> </span><i>u</i><sup>−1</sup><i>S</i> se define como el conjunto de todas las cadenas de reposo que se pueden obtener de una cadena en S cortando su prefijo u (si es posible), formalmente: <span data-ve-clipboard-key="0.03473874744820726-34"> </span><i>u</i><sup>−1</sup><i>S</i> = { <i>v</i> ∈ Σ<sup>*</sup>: ''uv'' ∈ <i>S</i> }, cf. foto.<ref>{{cite journal|author=Janusz A. Brzozowski|title=Derivatives of Regular Expressions|journal=JACM|year=1964|volume=11|pages=481–494|doi=10.1145/321239.321249}}</ref> Denis et al. define un '''autómata residual''' como un autómata finito no determinista ''A'' donde cada estado ''q'' corresponde a una derivación de Brzozowski de su lenguaje aceptado ''L(A)'', formalmente: |
Para un conjunto ''S'' de cadenas y una cadena ''u'', la derivada de Brzozowski<span data-ve-clipboard-key="0.03473874744820726-33"> </span><i>u</i><sup>−1</sup><i>S</i> se define como el conjunto de todas las cadenas de reposo que se pueden obtener de una cadena en S cortando su prefijo u (si es posible), formalmente: <span data-ve-clipboard-key="0.03473874744820726-34"> </span><i>u</i><sup>−1</sup><i>S</i> = { <i>v</i> ∈ Σ<sup>*</sup>: ''uv'' ∈ <i>S</i> }, cf. foto.<ref>{{cite journal|author=Janusz A. Brzozowski|title=Derivatives of Regular Expressions|journal=JACM|year=1964|volume=11|pages=481–494|doi=10.1145/321239.321249}}</ref> Denis et al. define un '''autómata residual''' como un autómata finito no determinista ''A'' donde cada estado ''q'' corresponde a una derivación de Brzozowski de su lenguaje aceptado ''L(A)'', formalmente: ∀''q''∈''Q'' ∃<i>u</i>∈Σ<sup>*</sup>: ''L''(''A'',<i>q</i>) = ''u''<sup href="Myhill-Nerode theorem#Statement of the theorem">−1</sup>''L''(''A''), donde <span data-ve-clipboard-key="0.03473874744820726-36"> </span><i>L</i>(<i>A</i>,''q'') denota el idioma aceptado de ''q'' como estado de inicio. |
||
Muestran que cada idioma regular se genera mediante un autómata residual mínimo determinado de manera única. Sus estados son derivaciones de Brzozowski ∪-indecomposables, 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 se pueden aprender en tiempo polinomial, incluso suponiendo entradas de muestra óptimas. Proporcionan un algoritmo de aprendizaje para autómatas residuales y prueban que aprende el autómata de su muestra característica de cadenas de entrada positivas y negativas.<ref>{{cite book|author1=François Denis|author2=Aurélien Lemay|author3=Alain Terlutte|chapter=Learning Regular Languages Using Non Deterministic Finite Automata|title=Grammatical Inference: Algorithms and Applications, 5th International Colloquium, ICGI|year=2000|volume=1891|pages=39–50|publisher=Springer|editor=Arlindo L. Oliveira|series=LNCS|isbn=3-540-41011-2|url=http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=FDDBA47D5A1172EEFB7EE38953F544D6?doi=10.1.1.13.5559&rep=rep1&type=pdf}}</ref><ref>{{cite book|author1=François Denis|author2=Aurélien Lemay|author3=Alain Terlutte|chapter=Learning Regular Languages using RFSA|title=Proc. ALT '01|year=2001|url=http://www.dsic.upv.es/asignaturas/facultad/apr/rfsa.pdf}}</ref> |
Muestran que cada idioma regular se genera mediante un autómata residual mínimo determinado de manera única. Sus estados son derivaciones de Brzozowski ∪-indecomposables, 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 se pueden aprender en tiempo polinomial, incluso suponiendo entradas de muestra óptimas. Proporcionan un algoritmo de aprendizaje para autómatas residuales y prueban que aprende el autómata de su muestra característica de cadenas de entrada positivas y negativas.<ref>{{cite book|author1=François Denis|author2=Aurélien Lemay|author3=Alain Terlutte|chapter=Learning Regular Languages Using Non Deterministic Finite Automata|title=Grammatical Inference: Algorithms and Applications, 5th International Colloquium, ICGI|year=2000|volume=1891|pages=39–50|publisher=Springer|editor=Arlindo L. Oliveira|series=LNCS|isbn=3-540-41011-2|url=http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=FDDBA47D5A1172EEFB7EE38953F544D6?doi=10.1.1.13.5559&rep=rep1&type=pdf}}</ref><ref>{{cite book|author1=François Denis|author2=Aurélien Lemay|author3=Alain Terlutte|chapter=Learning Regular Languages using RFSA|title=Proc. ALT '01|year=2001|url=http://www.dsic.upv.es/asignaturas/facultad/apr/rfsa.pdf}}</ref> |
||
| Línea 67: | Línea 67: | ||
== Aplicaciones == |
== Aplicaciones == |
||
* Encontrar patrones comunes en las descripciones de estructura de ADN y ARN<ref>{{cite book|author1=Alvis Brazma|author2=Inge Jonassen|author3=Jaak Vilo|author4=Esko Ukkonen|chapter=Pattern Discovery in Biosequences|title=Grammatical Inference, 4th International Colloquium, ICGI|year=1998|volume=1433|pages=257–270|publisher=Springer|editor1=Vasant Honavar|editor2=Giora Slutzki|series=LNCS}}</ref><ref>{{cite book|title=Mathematical Methods for DNA Sequences|date=Jan 1989|publisher=CRC Press|editor=M.S. Waterman|isbn=084936664X}}</ref>(Bioinformática) |
|||
Encontrar patrones comunes en las descripciones de estructura de ADN y ARN (Bioinformática) |
|||
Modelando la adquisición del lenguaje natural por los humanos |
* Modelando la adquisición del lenguaje natural por los humanos.<ref>{{cite book|author1=Fernando Pereira|author2=Yves Schabes|chapter=Inside-Outside Reestimation for partially Bracketed Corpora|title=Proc. 30th Ann. Meeting of the Assoc. for Comp. Linguistics|year=1992|pages=128–135}}</ref> |
||
Aprendizaje de descripciones estructurales de documentos de ejemplo estructurados, en particular Definiciones de Tipo de Documento (DTD) a partir de documentos SGML |
* Aprendizaje de descripciones estructurales de documentos de ejemplo estructurados, en particular Definiciones de Tipo de Documento (DTD) a partir de documentos SGML.<ref>{{cite thesis|type=Ph.D.|author=Helena Ahonen|title=Generating Grammars for Structured Documents Using Grammatical Inference Methods|date=Nov 1996|volume=A-1996-4|publisher=University of Helsinki, Department of Computer Science|series=Report}}</ref> |
||
* Aprender la estructura de las piezas de música.<ref>{{cite thesis|type=Master|author=Stephen Watkinson|title=Induction of Musical Syntax|year=1997|publisher=Dept. of AI, Univ. Edinburgh|url=http://www-users.cs.york.ac.uk/~stephenw/msc.ps|deadurl=yes|archiveurl=https://web.archive.org/web/20010604023544/http://www-users.cs.york.ac.uk/~stephenw/msc.ps|archivedate=June 4, 2001}}</ref><ref>{{cite book|author1=Pedro P. Cruz-Alcázar|author2=Enrique Vidal|chapter=Learning Regular Grammars to Model Musical Style: Comparing Different Coding Schemes|title=Grammatical Inference, 4th International Colloquium, ICGI|year=1998|volume=1433|pages=211–222|publisher=Springer|editor1=Vasant Honavar|editor2=Giora Slutzki|series=LNCS}}</ref> |
|||
Aprender la estructura de las piezas de música |
|||
Obtener representaciones compactas de lenguajes finitos |
* Obtener representaciones compactas de lenguajes finitos.<ref name="Campeanu.Santean.Yu.1998" /> |
||
* Clasificación y recuperación de documentos.<ref>{{cite book|author1=Alexander S. Saidi|author2=Souad Tayeb-bey|chapter=Grammatical Inference in Document Recognition|title=Grammatical Inference, 4th International Colloquium, ICGI|year=1998|volume=1433|pages=175–186|publisher=Springer|editor1=Vasant Honavar|editor2=Giora Slutzki|series=LNCS|isbn=3-540-64776-7}}</ref> |
|||
Clasificación y recuperación de documentos |
|||
Generación de reglas de corrección dependientes del contexto para errores gramaticales en inglés |
* Generación de reglas de corrección dependientes del contexto para errores gramaticales en inglés.<ref name="Brill.2000" /> |
||
== Notas == |
== Notas == |
||
{{reflist|group=note}} |
{{reflist|group=note}} |
||
Revisión del 06:05 20 nov 2017
En la teoría de 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 de un conjunto dado de cadenas de ejemplos. Aunque Mark E. Gold ha demostrado que no todos los idiomas regulares se pueden aprender de esta manera (ver la identificación del lenguaje en el límite), varios enfoques se han investigado para una variedad de subclases. Estos están bosquejados en este artículo. Para aprender sobre gramáticas más generales, ver Inducción de gramáticas.
Ejemplo
Un lenguaje regular se define como un conjunto (finito o infinito) de cadenas que pueden describirse mediante uno de los formalismos matemáticos llamado "autómata finito", "gramática regular" o "expresión regular", que tienen el mismo poder expresivo. Como este último formalismo conduce a notaciones más cortas, será introducido y utilizado aquí. Dado un conjunto (E) de símbolos (también llamado alfabeto), una expresión regular puede ser cualquiera de
- ∅ (denotando el conjunto vacío de cuerdas),
- ε (denotando el singleton el conjunto que contiene justo la cuerda vacía),
- a (dónde a es cualquier carácter en Σ; denotando el singleton conjunto justo conteniendo la cuerda de carácter solo un),
- r+s (dónde r y s son expresiones regulares más sencillas; denotando la unión de su conjunto)
- r⋅s (denotando el conjunto de todas las concatenaciones posibles de cadenas de los conjuntos de r y s),
- r+ (denotando el conjunto de n-concatenaciones de cadenas del conjunto de r de r conjunto, para cualquier n≥1), o
- r* (de modo similar, denotando el conjunto de n-concatenaciones de cadenas, pero también incluyendo la cadena vacía, vista como una 0-concatenación).
Por ejemplo, usando Σ = {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 (con cero inicial permitido), mientras que 1⋅ ( 0 + 1) * ⋅ 0 denota el conjunto (infinito) de todos los números binarios pares (sin ceros iniciales).
Dado un conjunto de cadenas (también llamadas "ejemplos positivos"), la tarea de la inducción regular del lenguaje es crear 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*, que corresponde a la caracterización informal "un uno seguido de muchos (incluso puede que ninguno) ceros". Sin embargo, (0 + 1)* y 1 + (1⋅0) + (1⋅0⋅0) es otra expresión regular, que denotan (suponiendo que Σ = {0,1}) el más grande y el más pequeño conjunto que contiene las cadenas dadas, llamados sobregeneralización y subgeneralización triviales, respectivamente. Algunos enfoques funcionan en una configuración extendida donde también se da un conjunto de cadenas de "ejemplos negativos"; luego, se debe encontrar una expresión regular que genere todos los ejemplos positivos, pero ninguno de los negativos.
 |
Enrejado de automata
Dupont et al. ha demostrado que el conjunto de todos los autómatas finitos estructuralmente completos[note 1] que generan un conjunto de cadenas de ejemplo dado forma un enrejado, con el autómata subgeneralizado trivial y el autómata sobregeneralizado trivial como elementos inferior y superior, respectivamente. Cada miembro de este enrejado puede obtenerse factorizando el autómata subgeneralizado mediante una relación de congruencia apropiada. La imagen muestra un ejemplo para la cadena de entrada anterior {1, 10, 100}. Cada autómata se denota con una expresión regular equivalente. Para la subgeneralización trivial en el nodo inferior, la forma del autómata también se colorea en gris, y consta de los estados a, b, c y d. El autómata de cada nodo es el resultado de factorizar el autómata inferior por la relación de congruencia que se muestra en gris debajo del nodo.
Si se dan cadenas de ejemplos positivas y negativas, Dupont et al. construye el enrejado a partir de los ejemplos positivos, y luego investiga el límite de separación entre los autómatas que generan ejemplos negativos y los que no. Los más interesantes son los autómatas inmediatamente debajo de la frontera[1]. En la imagen, se muestran los límites de separación para las cadenas de ejemplo negativas 11, 1001, 101, 0.
Coste y Nicolas presentan un método de búsqueda propio dentro de este enrejado, que relacionan con el paradigma de espacio de versión de Mitchell. Para encontrar el límite de separación, usan un algoritmo de coloreado gráfico sobre la relación de desigualdad de estado inducida por los ejemplos negativos[2]. Más tarde, investigan varias relaciones de ordenamiento en el conjunto de todas las fusiones de estado posibles.[3]
Kudo y Shimbo usan la representación por factorizaciones de autómata para proporcionar un marco único para los siguientes enfoques:
Cada uno de estos enfoques corresponde a un tipo particular de relaciones de congruencia usadas para factorizar.[5]
Enfoques
Lenguajes k-reversibles
Angluin considera los autómatas regulares "k-reversibles", esto es, autómatas deterministas en los que se puede llegar a cada estado desde a lo sumo un estado siguiendo una cadena de transiciones 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: ∀a0,...,ak ∈ Σ ∀s1, s2 ∈ Q: δ*(s1,a0...ak) = δ*(s2,a0...ak) ⇒ s1 = s2, donde δ* es la extensión homomórfica de δ a palabras arbitrarias. Angluin proporciona un algoritmo de orden cúbico para aprender el lenguaje k-reversible más pequeño a partir de un conjunto dado de palabras de entrada; para k = 0, el algoritmo tiene incluso una complejidad casi lineal[6][7]. La unicidad de estado requerida después de dados k+1 símbolos obliga a unificar estados del autómata, lo que conduce a una generalización adecuada diferente del autómata subgeneralizado trivial. Este algoritmo se ha utilizado para aprender partes simples de la sintaxis en inglés[8]; más tarde, se ha proporcionado una versión incremental[9]. Otro enfoque basado en un autómata k-reversible es el método de agrupamiento de cola.[10]
Autómata sucesor
A partir de un conjunto dado de cadenas de entrada, Vernadat y Richetin construyen un autómata sucesor, que consta de un estado para cada carácter distinto y una transición entre los dos estados de los caracteres adyacentes[11]. Por ejemplo, el conjunto de entrada {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 la repetición de cada carácter inmediatamente a un Kleene + y luego incluye para cada personaje el conjunto de sus posibles predecesores en su estado. Los autómatas sucesores pueden aprender exactamente la clase de los idiomas locales. Dado que cada idioma regular es la imagen homomórfica de un idioma local, las gramáticas de la primera clase se pueden aprender levantando, si se proporciona un homomorfismo adecuado (según la aplicación). En particular, existe tal homomorfismo para la clase de lenguajes aprendidos por el método predecesor-sucesor[12]. La capacidad de aprendizaje de los idiomas locales se puede reducir a la de los k-idiomas reversibles.[13][14]
 |
 |
Aproximaciones tempranas
Chomsky y Miller (1957)[15] utilizaron el lema del bombeo: supusieron que una parte v de una cadena de entrada uvw y trataron de construir un ciclo correspondiente en el autómata para ser aprendido; usando consultas de membresía, preguntan, para k apropiado, cuál de las cadenas uw, uvvw, uvvvw, ..., uvkw también Pertenece al lenguaje que se 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 el lema de bombeo.[16]
Autónoma de cubrimiento
Câmpeanu et al. entiende un autómata finito como una representación compacta de un gran lenguaje finito. Dado tal lenguaje F, buscan un autómata de cobertura A tal que su lenguaje L (A) cubre 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 dicho autómata de cobertura, F está determinado únicamente por A y l. Por ejemplo, F = { ad, read, reread } tiene l = 6 y un autómata de cubrimiento correspondiente a la expresión regular (r⋅e)*⋅a⋅d.
Para dos cadenas x y y, Câmpeanu et al. defina 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 largos que l[17]. En base a esta relación, cuya falta de transitividad[note 2] causa problemas técnicos considerables, dan un algoritmo O(n4)[note 3] para construir desde F un autómata A de cobertura de conteo de estado mínimo. Además, para la unión, intersección y diferencia de dos idiomas finitos, proporciona operaciones correspondientes en su autómata de cubrimiento[18][19]. Păun et al. mejora la complejidad temporal a O(n2).[20]
Autómata residual
Para un conjunto S de cadenas y una cadena u, la derivada de Brzozowski u−1S se define como el conjunto de todas las cadenas de reposo que se pueden obtener de una cadena en S cortando su prefijo u (si es posible), formalmente: u−1S = { v ∈ Σ*: uv ∈ S }, cf. foto.[21] Denis et al. define un autómata residual como un autómata finito no determinista A donde cada estado q corresponde a una derivación de Brzozowski de su lenguaje aceptado L(A), formalmente: ∀q∈Q ∃u∈Σ*: L(A,q) = u−1L(A), donde L(A,q) denota el idioma aceptado de q como estado de inicio.
Muestran que cada idioma regular se genera mediante un autómata residual mínimo determinado de manera única. Sus estados son derivaciones de Brzozowski ∪-indecomposables, 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 se pueden aprender en tiempo polinomial, incluso suponiendo entradas de muestra óptimas. Proporcionan un algoritmo de aprendizaje para autómatas residuales y prueban que aprende el autómata de su muestra característica de cadenas de entrada positivas y negativas.[22][23]
Expresiones regulares reducidas
Brill define una expresión regular reducida como cualquiera de
- a (donde a es cualquier carácter en Σ; denotando el singleton conjunto justo conteniendo la cuerda de carácter solo a),
- ¬a (denotando cualquier otro carácter solo en Σ excepto un),
- • (denotando cualquier carácter solo en Σ)
- a*, (¬a)*, o •* (denotando arbitrariamente muchos, posiblemente cero, repeticiones de caracteres del conjunto de un, ¬a, o •, respectivamente), o
- r⋅s (donde r y s son expresiones regulares más sencillas; denotando el conjunto de todas las concatenaciones posibles de cadenas de los conjuntos 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 prefijos aceptados. Su objetivo es aprender las reglas de corrección para los errores de ortografía en inglés[note 4], en lugar de las consideraciones teóricas sobre la capacidad de aprendizaje de las clases de los idiomas. En consecuencia, utiliza heurística para podar la acumulación de árboles, lo que lleva a una mejora considerable en el tiempo de ejecución.[24]
Aplicaciones
- Encontrar patrones comunes en las descripciones de estructura de ADN y ARN[25][26](Bioinformática)
- Modelando la adquisición del lenguaje natural por los humanos.[27]
- Aprendizaje de descripciones estructurales de documentos de ejemplo estructurados, en particular Definiciones de Tipo de Documento (DTD) a partir de documentos SGML.[28]
- Aprender la estructura de las piezas de música.[29][30]
- Obtener representaciones compactas de lenguajes finitos.[18]
- Clasificación y recuperación de documentos.[31]
- Generación de reglas de corrección dependientes del contexto para errores gramaticales en inglés.[24]
Notas
- ↑ i.e. autómata finito sin estados y transiciones innecesarios con respecto a un conjunto dado de cadenas.
- ↑ Por ejemplo, F = { aab, baa, aabb } conduce a aab ~ aabb (solo z=ε necesita ser chequeado para esto) y aabb ~ baa (de forma similar), pero no aab ~ baa (debido a z=b). Sin embargo, de acuerdo con Câmpeanu et al. (2001, Lemma 1, p.5), x ~ y ∧ y ~ z → x ~ z se aplica a las cadenas x, y, z con |x| ≤ |y| ≤ |z|.
- ↑ donde n es el número de estados de un autómata finito determinista AF tal que L(AF) = F.
- ↑ Por ejemplo: Reemplace "past" por "passed" en el contexto "(¬t⋅o)*⋅SINGULAR_NOUN⋅past"
Referencias
- ↑ P. Dupont; L. Miclet; E. Vidal (1994). «What is the Search Space of the Regular Inference?». En R. C. Carrasco; J. Oncina, eds. Proceedings of the Second International Colloquium on Grammatical Inference (ICGI): Grammatical Inference and Applications. LNCS 862. Springer. pp. 25-37.
- ↑ F. Coste; J. Nicolas (1997). «Regular Inference as a Graph Coloring Problem». Proc. ICML Workshop on Grammatical Inference, Automata Induction, and Language Acquisition.
- ↑ F. Coste; J. Nicolas (1998). «How Considering Incompatible State Mergings May Reduce the DFA Induction Search Tree». En Vasant Honavar; Giora Slutzki, eds. Grammatical Inference, 4th International Colloquium, ICGI. LNCS 1433. Springer. pp. 199-210.
- ↑ Dominique Luzeaux (Aug 1997). «A Universal Approach to Positive Regular Grammar Inference». Proc. 15th World IMACS Congress on Scientific Computation, Modelling and Applied Mathematics.
- ↑ M. Kudo; M. Shimbo (1988). «Efficient Regular Grammatical Inference Techniques by the Use of Partial Similarities and Their Logical Relationships». Pattern Recognition 21: 401-409. doi:10.1016/0031-3203(88)90053-2.
- ↑ D. Angluin (1981). «A Note on the Number of Queries Needed to Identify Regular Languages». Information and Control 51: 76-87. doi:10.1016/s0019-9958(81)90090-5.
- ↑ D. Angluin (1982). «Inference of Reversible Languages». J. ACM 293: 741-765.
- ↑ Robert C. Berwick; Samuel F. Pilato (1987). «Learning Syntax by Automata Induction». Machine Learning 2 (1): 9-38. doi:10.1007/bf00058753.
- ↑ Plantilla:Cite techreport
- ↑ Plantilla:Cite techreport
- ↑ F. Vernadat; M. Richetin (1984). «Regular Inference for Syntactic Pattern Recognition: A Case Study». Proc. 7th International Conference on Pattern Recognition (ICPR). pp. 1370-1372.
- ↑ P. Garcia; E. Vidal; F. Casacuberta (1987). «Local Languages, The Successor Method, and a Step Towards a General Methodology for the Inference of Regular Grammars». IEEE Trans. on Pattern Analysis and Machine Intelligence 9.
- ↑ Takashi Yokomori (Oct 1989). «Learning Context-Free Languages Efficiently». En K.P. Jantke, ed. Proc. Int. Workshop AII. LNAI 397. Springer. pp. 104-123.
- ↑ Satoshi Kobayashi; Takashi Yokomori (1994). «Learning Concatenations of Locally Testable Languages from Positive Data». En Setsuo Arikawa; Klaus P. Jantke, eds. Proc. 5th ALT. LNAI 872. Springer. pp. 405-422.
- ↑ Plantilla:Cite techreport
- ↑ R. Solomonoff (Jun 1959). «A New Method for Discovering the Grammars of Phrase Structure Languages». Proc. Int. Conf. on Information Processing. R.Oldenbourg. pp. 285-290.
- ↑ This relation generalizes the relation RF from the Myhill-Nerode theorem. It has been investigated in more detail in sect.3 of: 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.
- ↑ a b Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (1998). «Minimal Cover-Automata for Finite Languages». En J.-M. Champarnaud; D. Maurel; D. Ziadi, eds. Proc. Workshop on Implementing Automata (WIA). LNCS 1660. Springer. pp. 43-56. doi:10.1007/3-540-48057-9_4.
- ↑ Cezar Câmpeanu; Nicolae Sântean; Sheng Yu (2001). «Minimal Cover-Automata for Finite Languages». Theoretical Computer Science 267: 3-16. doi:10.1016/s0304-3975(00)00292-9.
- ↑ Andrei Păun; Nicolae Sântean; Sheng Yu (Sep 2001). «An O(n2) Algorithm for Constructing Minimal Cover Automata for Finite Languages». En Sheng Yu; Andrei Păun, eds. Proc. 5th Int. Conf. on Implementation and Application of Automata (CIAA). LNCS 2088. Springer. pp. 243-251. ISBN 978-3-540-42491-8.
- ↑ Janusz A. Brzozowski (1964). «Derivatives of Regular Expressions». JACM 11: 481-494. doi:10.1145/321239.321249.
- ↑ François Denis; Aurélien Lemay; Alain Terlutte (2000). «Learning Regular Languages Using Non Deterministic Finite Automata». En Arlindo L. Oliveira, ed. Grammatical Inference: Algorithms and Applications, 5th International Colloquium, ICGI. LNCS 1891. Springer. pp. 39-50. ISBN 3-540-41011-2.
- ↑ François Denis; Aurélien Lemay; Alain Terlutte (2001). «Learning Regular Languages using RFSA». Proc. ALT '01.
- ↑ a b Eric Brill (2000). «Pattern–Based Disambiguation for Natural Language Processing». Proc. EMNLP/VLC.
- ↑ Alvis Brazma; Inge Jonassen; Jaak Vilo; Esko Ukkonen (1998). «Pattern Discovery in Biosequences». En Vasant Honavar; Giora Slutzki, eds. Grammatical Inference, 4th International Colloquium, ICGI. LNCS 1433. Springer. pp. 257-270.
- ↑ M.S. Waterman, ed. (Jan 1989). Mathematical Methods for DNA Sequences. CRC Press. ISBN 084936664X.
- ↑ Fernando Pereira; Yves Schabes (1992). «Inside-Outside Reestimation for partially Bracketed Corpora». Proc. 30th Ann. Meeting of the Assoc. for Comp. Linguistics. pp. 128-135.
- ↑ Helena Ahonen (Nov 1996). Generating Grammars for Structured Documents Using Grammatical Inference Methods (Ph.D.). Report. A-1996-4. University of Helsinki, Department of Computer Science.
- ↑ Stephen Watkinson (1997). Induction of Musical Syntax (Master). Dept. of AI, Univ. Edinburgh. Archivado desde el original el June 4, 2001.
- ↑ Pedro P. Cruz-Alcázar; Enrique Vidal (1998). «Learning Regular Grammars to Model Musical Style: Comparing Different Coding Schemes». En Vasant Honavar; Giora Slutzki, eds. Grammatical Inference, 4th International Colloquium, ICGI. LNCS 1433. Springer. pp. 211-222.
- ↑ Alexander S. Saidi; Souad Tayeb-bey (1998). «Grammatical Inference in Document Recognition». En Vasant Honavar; Giora Slutzki, eds. Grammatical Inference, 4th International Colloquium, ICGI. LNCS 1433. Springer. pp. 175-186. ISBN 3-540-64776-7.