Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Gold-Style Learning Theory Read chapter Read first chapter

2016 | OriginalPaper | Chapter

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

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

Published in: Topics in Grammatical Inference

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Learning Grammars and Automata with Queries
next chapter Learning Probability Distributions Generated by Finite-State Machines
Literature
1.
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.
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.
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.
4.
5.
6.
7.
D. Angluin. Queries and Concept Learning. Machine Learning, 2(4):319–342, 1988.
8.
D. Angluin. Negative Results for Equivalence Queries. Machine Learning, 5(2):121–150, 1990.
9.
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.
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.
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.
J. H. Conway. Regular Algebras and Finite Machines. Chapman & Hall, London, 1974.
13.
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.
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.
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.
C. de la Higuera. A bibliographical study of grammatical inference. Pattern Recognition, 38:1332–1348, 2005.CrossRef
17.
C. de la Higuera. Grammatical Inference. Learning Automata and Grammars. Cambridge University Press, 2010.CrossRefMATH
18.
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.
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.
F. Denis, A. Lemay, and A. Terlutte. Residual finite state automata. Fundamenta Informaticae, 51(4):339–368, 2002.MathSciNetMATH
21.
F. Denis, A. Lemay, and A. Terlutte. Learning regular languages using non-deterministic finite automata. LNCS, 1891:39–50, 2004.MATH
22.
F. Denis, A. Lemay, and A. Terlutte. Learning regular languages using RFSA. Theoretical Computer Science, 313(2):267–294, 2004.MathSciNetCrossRefMATH
23.
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.
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.
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.
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.
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.
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.
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.
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.
E. M. Gold. Language identification in the limit. Information and Control, 10:447–474, 1967.CrossRefMATH
32.
33.
G. Gramlich and G. Schnitger. Minimizing NFA’s and regular expressions. Journal of Computer and System Sciences, 73(6):908–923, 2007.MathSciNetCrossRefMATH
34.
J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
35.
36.
T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Trans. on Computers, 19(7):617–627, 1970.MathSciNetCrossRefMATH
37.
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.
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.
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.
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.
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.
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.
B.A. Trakhtenbrot and Ya. M. Barzdin. Finite automata. Behavior and Synthesis. North-Holland, 1973.
45.
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.
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.
T. Yokomori. Learning non-deterministic finite automata from queries and counterexamples. Machine Learning, 13:169–189, 1994.
48.
T. Yokomori. Polynomial-time identification of very simple grammars from positive data. Theoretical Computer Science, 298:179–206, 2003.MathSciNetCrossRefMATH
Metadata
Title
On the Inference of Finite State Automata from Positive and Negative Data
Authors
Damián López
Pedro García
Copyright Year
2016
Publisher
Springer Berlin Heidelberg
Book
Topics in Grammatical Inference

Print ISBN: 978-3-662-48393-0

Electronic ISBN: 978-3-662-48395-4

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-662-48395-4_4

Premium Partner

    Image Credits