Inference of Regular Grammars and Finite Automata

[Angluin, 1982]

D. Angluin. Inference of reversible languages. Journal of the Association for Computing Machinery, 29(3):741-765, 1982.

[de la Higuera et al., 1996]

C. de la Higuera, J. Oncina, and E. Vidal. Identification of DFA: data-dependent versus data-independent algorithm. In L. Miclet and C. de la Higuera, editors, Grammatical Inference: Learning Syntax from Sentences, number 1147 in Lecture Notes in Artificial Intelligence, pages 313-325. Springer Verlag, 1996.

[de la Higuera, 1997]

C. de la Higuera. Characteristic sets for polynomial grammatical inference. Machine Learning, 27:125-138, 1997.

[Dupont and Chase, 1998]

P. Dupont and L. Chase. Using symbol clustering to improve probabilistic automaton inference. In Grammatical Inference, ICGI'98, number 1433 in Lecture Notes in Artificial Intelligence, pages 232-243. Springer Verlag, 1998.

[Dupont and Pinson, 1994]

P. Dupont and F. Pinson. Inférence grammaticale régulière par optimisation génétique à partir d'échantillons positifs et négatifs : la méthode gig. In Journées Francophones sur l'Apprentissage, pages G1-G13, Strasbourg, 1994.

[Dupont et al., 1994]

P. Dupont, L. Miclet, and E. Vidal. What is the search space of the regular inference ? In Grammatical Inference and Applications, ICGI'94, number 862 in Lecture Notes in Artificial Intelligence, pages 25-37. Springer Verlag, 1994.

[Dupont, 1994]

P. Dupont. Regular grammatical inference from positive and negative samples by genetic search : the GIG method. In Grammatical Inference and Applications, ICGI'94, number 862 in Lecture Notes in Artificial Intelligence, pages 236-245. Springer Verlag, 1994.

[Dupont, 1996a]

P. Dupont. Incremental regular inference. In Grammatical Inference : Learning Syntax from Sentences, ICGI'96, number 1147 in Lecture Notes in Artificial Intelligence, pages 222-237. Springer Verlag, 1996.

[Dupont, 1996b]

P. Dupont. Utilisation et Apprentissage de Modèles de Langage pour la Reconnaissance de la Parole Continue. Thèse de Doctorat, Ecole Nationale Supérieure des Télécommunications, Paris, France, 1996.

[García and Vidal, 1990]

P. García and E. Vidal. Inference of K-testable languages in the strict sense and applications to syntactic pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(9):920-925, 1990.

[García et al., 1987]

P. García, E. Vidal, and F. Casacuberta. Local languages, the Successor method, and a step towards a general methodology for the inference of regular grammars. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(6):841-845, 1987.

[García et al., 1990]

P. García, E. Segarra, E. Vidal, and I. Galiano. On the use of the Morphic Generator Grammatical Inference (MGGI) methodology in automatic speech recognition. International Journal of Pattern Recognition and Artificial Intelligence, 4(4):667-685, 1990.

[Henaff, 1995]

M.-M. Henaff. Inférence de grammaires régulières à partir d'échantillons positifs et négatifs. Rapport de stage, DEA Informatique, IFSIC, ENSSAT, 1995.

[Ibarra and Jiang, 1988]

O.H. Ibarra and T. Jiang. Learning regular languages from counterexamples. In D. Haussler and L. Pitt, editors, Workshop on Computational Learning Theory, pages 371-385. Morgan Kaufmann, 1988.

[Juillé and Pollack, 1998]

H. Juillé and J.B. Pollack. A stochastic search approach to grammar induction. In Grammatical Inference, number 1433 in Lecture Notes in Artificial Intelligence, pages 126-137. Springer-Verlag, 1998.

[Knuutila, 1993]

T. Knuutila. How to invent characterizable methods for regular languages. In 4th workshop on Algorithmic Learning Theory, number 744 in Lecture Notes in Artificial Intelligence, pages 209-222, Tokyo, 1993. Springer Verlag.

[Lang et al., 1998]

K.J. Lang, B.A. Pearlmutter, and R.A. Price. Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm. In Grammatical Inference, number 1433 in Lecture Notes in Artificial Intelligence, pages 1-12. Springer-Verlag, 1998.

[Lang, 1992]

K.J. Lang. Random DFA's can be approximately learned from sparse uniform examples. In 5th ACM workshop on Computational Learning Theory, pages 45-52, 1992.

[Lang, 1997]

K. Lang. Merge order counts. Technical report, NEC Research Institute, September 1997.

[Miclet and de Gentile, 1994]

L. Miclet and C. de Gentile. Inférence grammaticale à partir d'exemples et de contre-exemples : deux algorithmes optimaux (BIG et RIG) et une version heuristique (brig). In Neuvièmes Journées Francophones sur l'Apprentissage, pages F1-F13, Strasbourg, France, 1994.

[Miclet et al., 1995]

L. Miclet, P. Dupont, and S. Vial. Inférence grammaticale régulière : Méthodes semi-itératives et mesure de performance. In Journées Acquisition, Validation, Apprentissage, pages 103-116, Grenoble, France, 1995.

[Miclet, 1979]

L. Miclet. Inférence de Grammaires Régulières. Thèse de Doctorat, Ecole Nationale Supérieure des Télécommunications, Paris, France, 1979.

[Miclet, 1980]

L. Miclet. Regular inference with a tail-clustering method. IEEE Transactions on Systems, Man and Cybernetics, 10:737-743, 1980.

[Oncina and García, 1992a]

J. Oncina and P. García. Identifying regular languages in polynomial time. In H. Bunke, editor, Advances in Structural and Syntactic Pattern Recognition, volume 5 of Series in Machine Perception and Artificial Intelligence, pages 99-108. World Scientific, 1992.

[Oncina and García, 1992b]

J. Oncina and P. García. Inferring regular languages in polynomial update time. In N. Pérez de la Blanca, A. Sanfeliu, and E.Vidal, editors, Pattern Recognition and Image Analysis, volume 1 of Series in Machine Perception and Artificial Intelligence, pages 49-61. World Scientific, 1992.

[Parekh and Honavar, 1996]

R. Parekh and V. Honavar. An incremental interactive algorithm for regular grammar inference. In Grammatical Inference : Learning Syntax from Sentences, ICGI'96, number 1147 in Lecture Notes in Artificial Intelligence, pages 238-249. Springer Verlag, 1996.

[Parekh and Honavar, 1997]

R. Parekh and V. Honavar. Learning DFA from simple examples. In Workshop on Automata Induction, Grammatical Inference, and Language Acquisition, ICML-97, 1997.

[Parekh et al., 1998]

R. Parekh, C. Nichitiu, and V. Honavar. A polynomial time incremental algorithm for learning DFA. In Grammatical Inference, ICGI'98, number 1433 in Lecture Notes in Artificial Intelligence, pages 37-49. Springer Verlag, 1998.

[Richetin and Vernadat, 1984]

M. Richetin and F. Vernadat. Efficient regular grammatical inference for pattern recognition. Pattern Recognition, 17(2):245-250, 1984.

[Rivest and Schapire, 1989]

R.L. Rivest and R.E. Schapire. Inference of finite automata using Homing sequences. In 21st ACM Symposium on Theory of Computing, pages 411-420, 1989.

[Rulot and Vidal, 1988]

H. Rulot and E. Vidal. An efficient algorithm for the inference of circuit-free automata. In G. Ferratè, T. Pavlidis, A. Sanfeliu, and H. Bunke, editors, Advances in Structural and Syntactic Pattern Recognition, pages 173-184. NATO ASI, Springer-Verlag, 1988.

[Rulot, 1992]

H. Rulot. ECGI : Un Algoritmo de Inferencia Gramatical Mediante Corrección de Errores. Ph. D. dissertation, Universitát de València, 1992.

[Tomita, 1982]

M. Tomita. Dynamic construction of finite-automata from examples using hill-climbing. In 4th Annual Cognitive Science Conference, pages 105-108, 1982.

[Trakhtenbrot and Barzdin, 1973]

B. Trakhtenbrot and Ya. Barzdin. Finite Automata: Behavior and Synthesis. North Holland Pub. Comp., Amsterdam, 1973.

[Wharton, 1977]

R.M. Wharton. Grammar enumeration and inference. Information and Control, 33:253-272, 1977.

[Wyard, 1994]

P. Wyard. Representational issues for context free grammars induction using genetic algorithms. In Grammatical Inference and Applications, ICGI'94, number 862 in Lecture Notes in Artificial Intelligence, pages 222-235. Springer Verlag, 1994.

[Yokomori, 1994]

T. Yokomori. Learning non-deterministic finite automata from queries and counterexamples. Machine Intelligence, 13:xx-yy, 1994.