Skip to main content

2016 | OriginalPaper | Buchkapitel

4. On the Inference of Finite State Automata from Positive and Negative Data

verfasst von : Damián López, Pedro García

Erschienen in: Topics in Grammatical Inference

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The works by Thrakhtenbrot–Barzdin and Gold can be considered to be the first works on the identification of Finite Automata from given data. The main drawback of their results is that they may obtain hypotheses that may be inconsistent with the provided data. This drawback was solved by the RPNI and Lang algorithms. Aside from these works, other works have introduced more efficient algorithms with respect to the training data. The direct consequence of this improvement has lead to algorithms that have lower error rates. Recently, some works have tackled the identification of NFAs instead of using the traditional DFA model. In this line of research, the inference of Residual Finite State Automata (RFSA) provides a canonical non-deterministic model. Other works consider the inference of teams of NFAs to be a method that is suitable to solve the grammatical inference of finite automata. We review the main approaches that solve the inference of finite automata by using positive and negative data from the target language. In this review, we will describe the above-mentioned formalisms and induction techniques.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat J. Abela, F. Coste, and S. Spina. Mutually compatible and incompatible merges for the search of the smallest consistent DFA. LNAI, 3264:28–39. 7th International Colloquium, ICGI-04. Springer. 2004. J. Abela, F. Coste, and S. Spina. Mutually compatible and incompatible merges for the search of the smallest consistent DFA. LNAI, 3264:28–39. 7th International Colloquium, ICGI-04. Springer. 2004.
2.
Zurück zum Zitat G. I. Álvarez. Estudio de la Mezcla de Estados Determinista y No Determinista en el Diseño de Algoritmos para Inferencia Gramatical de Lenguajes Regulares. PhD Thesis in Computer Science, Departamento de Sistemas Informáticos y Computación. Universidad Politécnica de Valencia, 2007. in Spanish. G. I. Álvarez. Estudio de la Mezcla de Estados Determinista y No Determinista en el Diseño de Algoritmos para Inferencia Gramatical de Lenguajes Regulares. PhD Thesis in Computer Science, Departamento de Sistemas Informáticos y Computación. Universidad Politécnica de Valencia, 2007. in Spanish.
3.
Zurück zum Zitat G. I. Álvarez, J. Ruiz, A. Cano, and P. García. Non-deterministic regular positive negative inference NRPNI. In J.F. Díaz, C. Rueda, and A.A. Buss, editors, Proc. of the XXXI Conferencia Latinoamericana de Informática (CLEI2005), pages 239–249, 2005. ISBN:958-670-422-X. G. I. Álvarez, J. Ruiz, A. Cano, and P. García. Non-deterministic regular positive negative inference NRPNI. In J.F. Díaz, C. Rueda, and A.A. Buss, editors, Proc. of the XXXI Conferencia Latinoamericana de Informática (CLEI2005), pages 239–249, 2005. ISBN:958-670-422-X.
5.
6.
7.
Zurück zum Zitat D. Angluin. Queries and Concept Learning. Machine Learning, 2(4):319–342, 1988. D. Angluin. Queries and Concept Learning. Machine Learning, 2(4):319–342, 1988.
8.
Zurück zum Zitat D. Angluin. Negative Results for Equivalence Queries. Machine Learning, 5(2):121–150, 1990. D. Angluin. Negative Results for Equivalence Queries. Machine Learning, 5(2):121–150, 1990.
9.
Zurück zum Zitat R. C. Carrasco and J. Oncina. Learning stochastic regular grammars by means of a state merging method. Lecture Notes in Artificial Intelligence, 862:139–152, 1994. R. C. Carrasco and J. Oncina. Learning stochastic regular grammars by means of a state merging method. Lecture Notes in Artificial Intelligence, 862:139–152, 1994.
10.
Zurück zum Zitat J. M. Champarnaud and F. Coulon. NFA reduction algorithms by means of regular inequalities. Theoretical Computer Science, 327(3):241–253, 2004. Erratum in TCS 347:437-440 (2005). J. M. Champarnaud and F. Coulon. NFA reduction algorithms by means of regular inequalities. Theoretical Computer Science, 327(3):241–253, 2004. Erratum in TCS 347:437-440 (2005).
11.
Zurück zum Zitat O. Cichello and S. C. Kremer. Inducing grammars from sparse data sets: A survey of algorithms and results. Journal of Machine Learning Research, 4:603–632, 2003.MathSciNet O. Cichello and S. C. Kremer. Inducing grammars from sparse data sets: A survey of algorithms and results. Journal of Machine Learning Research, 4:603–632, 2003.MathSciNet
12.
Zurück zum Zitat J. H. Conway. Regular Algebras and Finite Machines. Chapman & Hall, London, 1974. J. H. Conway. Regular Algebras and Finite Machines. Chapman & Hall, London, 1974.
13.
Zurück zum Zitat F. Coste and D. Fredouille. Efficient ambiguity detection in C-NFA. a step towards the inference of non-deterministic automata. LNAI, 1891:25–38. 5th International Colloquium, ICGI-00. Springer. 2000. F. Coste and D. Fredouille. Efficient ambiguity detection in C-NFA. a step towards the inference of non-deterministic automata. LNAI, 1891:25–38. 5th International Colloquium, ICGI-00. Springer. 2000.
14.
Zurück zum Zitat F. Coste and D. Fredouille. Unambiguous automata inference by means of state-merging methods. LNCS, 2837:60–71, 2003. 14th European Conference ECML-03. F. Coste and D. Fredouille. Unambiguous automata inference by means of state-merging methods. LNCS, 2837:60–71, 2003. 14th European Conference ECML-03.
15.
Zurück zum Zitat F. Coste and D. Fredouille. What is the search space for the inference of non-deterministic, unambiguous and deterministic automata? Technical Report 4907, INRIA, 2003. Internal Report Project Symbiose. F. Coste and D. Fredouille. What is the search space for the inference of non-deterministic, unambiguous and deterministic automata? Technical Report 4907, INRIA, 2003. Internal Report Project Symbiose.
16.
Zurück zum Zitat C. de la Higuera. A bibliographical study of grammatical inference. Pattern Recognition, 38:1332–1348, 2005.CrossRef C. de la Higuera. A bibliographical study of grammatical inference. Pattern Recognition, 38:1332–1348, 2005.CrossRef
17.
Zurück zum Zitat C. de la Higuera. Grammatical Inference. Learning Automata and Grammars. Cambridge University Press, 2010.CrossRefMATH C. de la Higuera. Grammatical Inference. Learning Automata and Grammars. Cambridge University Press, 2010.CrossRefMATH
18.
Zurück zum Zitat C. de la Higuera, J. Oncina, and E. Vidal. Identification of DFA: data-dependent vs data-independent algorithms. LNAI, 1147:313–325. 3rd International Colloquium, ICGI-96. Springer. 1996 C. de la Higuera, J. Oncina, and E. Vidal. Identification of DFA: data-dependent vs data-independent algorithms. LNAI, 1147:313–325. 3rd International Colloquium, ICGI-96. Springer. 1996
19.
Zurück zum Zitat F. Denis, A. Lemay, and A. Terlutte. Learning regular languages using non-deterministic finite automata. LNAI, 1891:39–50. 5th International Colloquium, ICGI-00. Springer. 2000 F. Denis, A. Lemay, and A. Terlutte. Learning regular languages using non-deterministic finite automata. LNAI, 1891:39–50. 5th International Colloquium, ICGI-00. Springer. 2000
20.
Zurück zum Zitat F. Denis, A. Lemay, and A. Terlutte. Residual finite state automata. Fundamenta Informaticae, 51(4):339–368, 2002.MathSciNetMATH F. Denis, A. Lemay, and A. Terlutte. Residual finite state automata. Fundamenta Informaticae, 51(4):339–368, 2002.MathSciNetMATH
21.
Zurück zum Zitat F. Denis, A. Lemay, and A. Terlutte. Learning regular languages using non-deterministic finite automata. LNCS, 1891:39–50, 2004.MATH F. Denis, A. Lemay, and A. Terlutte. Learning regular languages using non-deterministic finite automata. LNCS, 1891:39–50, 2004.MATH
22.
Zurück zum Zitat F. Denis, A. Lemay, and A. Terlutte. Learning regular languages using RFSA. Theoretical Computer Science, 313(2):267–294, 2004.MathSciNetCrossRefMATH F. Denis, A. Lemay, and A. Terlutte. Learning regular languages using RFSA. Theoretical Computer Science, 313(2):267–294, 2004.MathSciNetCrossRefMATH
23.
Zurück zum Zitat P. García, D. López, and M. Vázquez de Parga. Polynomial characteristic sets for DFA identification. Theoretical Computer Science, 448:41–46, 2012.MathSciNetCrossRefMATH P. García, D. López, and M. Vázquez de Parga. Polynomial characteristic sets for DFA identification. Theoretical Computer Science, 448:41–46, 2012.MathSciNetCrossRefMATH
24.
Zurück zum Zitat P. García, A. Cano, and J. Ruiz. A comparative study of two algorithms for automata identification. LNAI, 1891:115–126. 5th International Colloquium, ICGI-00. 2000. P. García, A. Cano, and J. Ruiz. A comparative study of two algorithms for automata identification. LNAI, 1891:115–126. 5th International Colloquium, ICGI-00. 2000.
25.
Zurück zum Zitat P. García and J. Ruiz. Learning in varieties of the form \(V*LI\) from positive data. Theoretical Computer Science, 362(1–3):100–114, 2006.MathSciNetCrossRefMATH P. García and J. Ruiz. Learning in varieties of the form \(V*LI\) from positive data. Theoretical Computer Science, 362(1–3):100–114, 2006.MathSciNetCrossRefMATH
26.
Zurück zum Zitat P. García, J. Ruiz, A. Cano, and G. I. Álvarez. Is learning RFSAs better than learning DFAs? LNCS, 3845:343–344, 2005. 10th International Conference on Implementation and Application of Automata (CIAA-05). P. García, J. Ruiz, A. Cano, and G. I. Álvarez. Is learning RFSAs better than learning DFAs? LNCS, 3845:343–344, 2005. 10th International Conference on Implementation and Application of Automata (CIAA-05).
27.
Zurück zum Zitat P. García, M. Vázquez de Parga, G. I. Álvarez, and J. Ruiz. Learning regular languages using nondeterministic finite automata. LNCS, 5148:92–102, 13th International Conference on Implementation of Automata (CIAA’08). Springer. 2008. P. García, M. Vázquez de Parga, G. I. Álvarez, and J. Ruiz. Learning regular languages using nondeterministic finite automata. LNCS, 5148:92–102, 13th International Conference on Implementation of Automata (CIAA’08). Springer. 2008.
28.
Zurück zum Zitat P. García, M. Vázquez de Parga, G. I. Álvarez, and J. Ruiz. Universal automata and NFA learning. Theoretical Computer Science, 407(1-3):192–202, 2008.MathSciNetCrossRefMATH P. García, M. Vázquez de Parga, G. I. Álvarez, and J. Ruiz. Universal automata and NFA learning. Theoretical Computer Science, 407(1-3):192–202, 2008.MathSciNetCrossRefMATH
29.
Zurück zum Zitat P. García, M. Vázquez de Parga, D. López, and J. Ruiz. Learning automata teams. LNAI, 6339:52–65. 10th International Colloquium, ICGI-10. Springer. 2010. P. García, M. Vázquez de Parga, D. López, and J. Ruiz. Learning automata teams. LNAI, 6339:52–65. 10th International Colloquium, ICGI-10. Springer. 2010.
30.
Zurück zum Zitat P. García and E. Vidal. Inference of k-testable Languages in the Strict Sense and application to Syntactic Pattern Recognition. IEEE Trans. Pattern Analysis and Machine Intelligence, pages 920–925, 1990. P. García and E. Vidal. Inference of k-testable Languages in the Strict Sense and application to Syntactic Pattern Recognition. IEEE Trans. Pattern Analysis and Machine Intelligence, pages 920–925, 1990.
31.
Zurück zum Zitat E. M. Gold. Language identification in the limit. Information and Control, 10:447–474, 1967.CrossRefMATH E. M. Gold. Language identification in the limit. Information and Control, 10:447–474, 1967.CrossRefMATH
32.
33.
Zurück zum Zitat G. Gramlich and G. Schnitger. Minimizing NFA’s and regular expressions. Journal of Computer and System Sciences, 73(6):908–923, 2007.MathSciNetCrossRefMATH G. Gramlich and G. Schnitger. Minimizing NFA’s and regular expressions. Journal of Computer and System Sciences, 73(6):908–923, 2007.MathSciNetCrossRefMATH
34.
Zurück zum Zitat J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
35.
36.
Zurück zum Zitat T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Trans. on Computers, 19(7):617–627, 1970.MathSciNetCrossRefMATH T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Trans. on Computers, 19(7):617–627, 1970.MathSciNetCrossRefMATH
37.
Zurück zum Zitat 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. LNAI, 1433:1–12. 4th International Colloquium, ICGI-98. Springer. 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. LNAI, 1433:1–12. 4th International Colloquium, ICGI-98. Springer. 1998.
38.
Zurück zum Zitat K.J. Lang. Random DFA’s can be approximately learned from sparse uniform examples. In Proceedings of the fifth annual workshop on Computational learning theory, pages 45–52, 1992. K.J. Lang. Random DFA’s can be approximately learned from sparse uniform examples. In Proceedings of the fifth annual workshop on Computational learning theory, pages 45–52, 1992.
39.
Zurück zum Zitat S. Lombardy and J. Sakarovitch. The universal automaton. In Jörg Flum, Erich Grädel, and Thomas Wilke, editors, Logic and Automata, volume 2 of Texts in Logic and Games, pages 457–504. Amsterdam University Press, 2008. S. Lombardy and J. Sakarovitch. The universal automaton. In Jörg Flum, Erich Grädel, and Thomas Wilke, editors, Logic and Automata, volume 2 of Texts in Logic and Games, pages 457–504. Amsterdam University Press, 2008.
40.
Zurück zum Zitat O. Matz and A. Potthoff. Computing small nondeterministic finite automata. In Tools and Algorithms for the Construction and Analysis of Systems - TACAS ’95, volume NS-95-2 of BRICS Notes Series, pages 74–88, 1995. O. Matz and A. Potthoff. Computing small nondeterministic finite automata. In Tools and Algorithms for the Construction and Analysis of Systems - TACAS ’95, volume NS-95-2 of BRICS Notes Series, pages 74–88, 1995.
41.
Zurück zum Zitat J. Oncina and P. García. Inferring regular languages in polynomial updated time. Pattern recognition and image analysis, volume 1, pages 49–61. World Scientific, 1992. J. Oncina and P. García. Inferring regular languages in polynomial updated time. Pattern recognition and image analysis, volume 1, pages 49–61. World Scientific, 1992.
42.
Zurück zum Zitat J. Oncina, P. Garcia, and E. Vidal. Learning subsequential transducers for pattern recognition interpretation tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(5):448–458, 1993.CrossRef J. Oncina, P. Garcia, and E. Vidal. Learning subsequential transducers for pattern recognition interpretation tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(5):448–458, 1993.CrossRef
43.
44.
Zurück zum Zitat B.A. Trakhtenbrot and Ya. M. Barzdin. Finite automata. Behavior and Synthesis. North-Holland, 1973. B.A. Trakhtenbrot and Ya. M. Barzdin. Finite automata. Behavior and Synthesis. North-Holland, 1973.
45.
Zurück zum Zitat M. Vázquez de Parga. Autómatas finitos: Irreducibilidad e inferencia. PhD Thesis in Computer Science, Departamento de Sistemas Informáticos y Computación. Universidad Politécnica de Valencia, 2008. in Spanish. M. Vázquez de Parga. Autómatas finitos: Irreducibilidad e inferencia. PhD Thesis in Computer Science, Departamento de Sistemas Informáticos y Computación. Universidad Politécnica de Valencia, 2008. in Spanish.
46.
Zurück zum Zitat M. Vázquez de Parga, P. García, and J. Ruiz. A family of algorithms for non-deterministic regular language inference. LNCS, 4094:265–274, 2008. 12th International Conference on Implementation of Automata (CIAA’06). M. Vázquez de Parga, P. García, and J. Ruiz. A family of algorithms for non-deterministic regular language inference. LNCS, 4094:265–274, 2008. 12th International Conference on Implementation of Automata (CIAA’06).
47.
Zurück zum Zitat T. Yokomori. Learning non-deterministic finite automata from queries and counterexamples. Machine Learning, 13:169–189, 1994. T. Yokomori. Learning non-deterministic finite automata from queries and counterexamples. Machine Learning, 13:169–189, 1994.
48.
Zurück zum Zitat T. Yokomori. Polynomial-time identification of very simple grammars from positive data. Theoretical Computer Science, 298:179–206, 2003.MathSciNetCrossRefMATH T. Yokomori. Polynomial-time identification of very simple grammars from positive data. Theoretical Computer Science, 298:179–206, 2003.MathSciNetCrossRefMATH
Metadaten
Titel
On the Inference of Finite State Automata from Positive and Negative Data
verfasst von
Damián López
Pedro García
Copyright-Jahr
2016
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-662-48395-4_4