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

3. Learning Grammars and Automata with Queries

Author : Colin de la Higuera

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

When learning languages or grammars, an attractive alternative to using a large corpus is to learn by interacting with the environment. This can allow us to deal with situations where data is scarce or expensive, but testing or experimenting is possible. The situation, which arises in a number of fields, is formalised in a setting called active learning or query learning. By controlling better the information to which one has access, this setting provides us with a better understanding of the hardness of learning tasks. But the setting also allows us to solve practical learning situations, for which new algorithms are needed.

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 Efficiency in the Identification in the Limit Learning Paradigm
next chapter On the Inference of Finite State Automata from Positive and Negative Data
Footnotes
2
The different papers presented at the workshop can be found at http://​users.​dsic.​upv.​es/​workshops/​icgi2010/​.
 
Literature
1.
F. Aarts, H. Kuppens, J. Tretmans, F. Vaandrager, and S. Verwer. Learning and testing the bounded retransmission protocol. In Heinz et al. [41], pages 4–18.
2.
H. I. Akram, C. de la Higuera, and Claudia Eckert. Actively learning probabilistic subsequential transducers. In Heinz et al. [41], pages 19–33.
3.
R. Alquézar and A. Sanfeliu. A hybrid connectionist-symbolic approach to regular grammatical inference based on neural learning and hierarchical clustering. In R. C. Carrasco and J. Oncina, editors, Grammatical Inference and Applications, Proceedings of ICGI ’94, number 862 in LNAI, pages 203–211. Springer-Verlag, 1994.
4.
5.
D. Angluin. Queries and concept learning. Machine Learning Journal, 2:319–342, 1987.
6.
D. Angluin. Learning regular sets from queries and counterexamples. Information and Control, 39:337–350, 1988.MathSciNetCrossRef
7.
D. Angluin. Negative results for equivalence queries. Machine Learning Journal, 5:121–150, 1990.
8.
9.
D. Angluin and M. Kharitonov. When won’t membership queries help? In Proceedings of 24th ACM Symposium on Theory of Computing, pages 444–454, New York, 1991. ACM Press.
10.
J. L. Balcázar, J. Diaz, R. Gavaldà, and O. Watanabe. An optimal parallel algorithm for learning DFA. In Proceedings of the 7th COLT, pages 208–217, New York, 1994. ACM Press.
11.
J. L. Balcázar, J. Diaz, R. Gavaldà, and O. Watanabe. The query complexity of learning DFA. New Generation Computing, 12:337–358, 1994.
12.
L. Beccera-Bonache, C. Bibire, and A. Horia Dediu. Learning DFA from corrections. In Henning Fernau, editor, Proceedings of the Workshop on Theoretical Aspects of Grammar Induction (TAGI), WSI-2005-14, pages 1–11. Technical Report, University of Tübingen, 2005.
13.
L. Becerra-Bonache, C. de la Higuera, J. C. Janodet, and F. Tantini. Learning balls of strings from edit corrections. Journal of Machine Learning Research, 9:1841–1870, 2008.MathSciNetMATH
14.
L. Becerra-Bonache, A. Horia Dediu, and C. Tîrnauca. Learning DFA from correction and equivalence queries. In Sakakibara et al. [54], pages 281–292.
15.
L. Becerra-Bonache and T. Yokomori. Learning mild context-sensitiveness: Toward understanding children’s language learning. In Paliouras and Sakakibara [49], pages 53–64.
16.
T. Berg, O. Grinchtein, B. Jonsson, M. Leucker, H. Raffelt, and B. Steffen. On the correspondence between conformance testing and regular inference. In Proceedings of Fundamental Approaches to Software Engineering, 8th International Conference, FASE 2005, volume 3442 of LNCS, pages 175–189. Springer-Verlag, 2005.
17.
F. Bergadano and S. Varricchio. Learning behaviors of automata from multiplicity and equivalence queries. SIAM Journal of Computing, 25(6):1268–1280, 1996.
18.
L. Bréhélin, O. Gascuel, and G. Caraux. Hidden Markov models with patterns to learn boolean vector sequences and application to the built-in self-test for integrated circuits. Pattern Analysis and Machine Intelligence, 23(9):997–1008, 2001.CrossRef
19.
N. H. Bshouty, R. Cleve, R. Gavaldà, S. Kannan, and C. Tamon. Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences, 52:421–433, 1996.MathSciNetCrossRefMATH
20.
J. Carme, R. Gilleron, A. Lemay, and J. Niehren. Interactive learning of node selecting tree transducer. In IJCAI Workshop on Grammatical Inference, 2005.
21.
J. Carme, R. Gilleron, A. Lemay, and J. Niehren. Interactive learning of node selecting tree transducer. Machine Learning Journal, 66(1):33–67, 2007.CrossRef
22.
D. Carmel and S. Markovitch. Model-based learning of interaction strategies in multi-agent systems. Journal of Experimental and Theoretical Artificial Intelligence, 10(3):309–332, 1998.CrossRefMATH
23.
D. Carmel and S. Markovitch. Exploration strategies for model-based learning in multiagent systems. Autonomous Agents and Multi-agent Systems, 2(2):141–172, 1999.CrossRef
24.
J. Castro and D. Guijarro. PACS, simple-PAC and query learning. Information Processing Letters, 73(1–2):11–16, 2000.
25.
J. Chandlee, J. Fu, K. Karydis, Cesar Koirala, J. Heinz, and H. G. Tanner. Integrating grammatical inference into robotic planning. In Heinz et al. [41], pages 69–83.
26.
A. Clark. Distributional learning of some context-free languages with a minimally adequate teacher. In J. Sempere and P. García, editors, Grammatical Inference: Theoretical Results and Applications, Proceedings of ICGI ’10, volume 6339 of LNCS, pages 24–37. Springer-Verlag, 2010.
27.
A. Clark, F. Coste, and L. Miclet, editors. Grammatical Inference: Algorithms and Applications, Proceedings of ICGI ’08, volume 5278 of LNCS. Springer-Verlag, 2008.
28.
D. Combe, C. de la Higuera, and J.-C. Janodet. Zulu: An interactive learning competition. In Proceedings of FSMNLP ’09, volume 6062 of LNCS, pages 139–146. Springer-Verlag, 2009.
29.
C. de la Higuera. Characteristic sets for polynomial grammatical inference. Machine Learning Journal, 27:125–138, 1997.CrossRefMATH
30.
C. de la Higuera. Data complexity issues in grammatical inference. In M. Basu and T. Kam Ho, editors, Data Complexity in Pattern Recognition, pages 153–172. Springer-Verlag, 2006.
31.
C. de la Higuera. Ten open problems in grammatical inference. In Sakakibara et al. [54], pages 32–44.
32.
C. de la Higuera. Grammatical inference: learning automata and grammars. Cambridge University Press, 2010.
33.
C. de la Higuera, J.-C. Janodet, and F. Tantini. Learning languages from bounded resources: the case of the DFA and the balls of strings. In Clark et al. [54], pages 43–56.
34.
C. de la Higuera and J. Oncina. Learning probabilistic finite automata. In Paliouras and Sakakibara [49], pages 175–186.
35.
T. Dean, K. Basye, L. Kaelbling, E. Kokkevis, O. Maron, D. Angluin, and S. Engelson. Inferring finite automata with stochastic output functions and an application to map learning. In W. Swartout, editor, Proceedings of the 10th National Conference on Artificial Intelligence, pages 208–214, San Jose, CA, 1992. MIT Press.
36.
R. Gavaldà. On the power of equivalence queries. In Proceedings of the 1st European Conference on Computational Learning Theory, volume 53 of The Institute of Mathematics and its Applications Conference Series, pages 193–203. Oxford University Press, 1993.
37.
C. L. Giles, S. Lawrence, and A.C. Tsoi. Noisy time series prediction using recurrent neural networks and grammatical inference. Machine Learning, 44(1):161–183, 2001.
38.
E. M. Gold. Language identification in the limit. Information and Control, 10(5):447–474, 1967.CrossRefMATH
39.
O. Guttman, S. V. N. Vishwanathan, and R. C. Williamson. Learnability of probabilistic automata via oracles. In S. Jain, H.-U. Simon, and E. Tomita, editors, Proceedings of ALT 2005, volume 3734 of LNCS, pages 171–182. Springer-Verlag, 2005.
40.
A. Hagerer, H. Hungar, O. Niese, and B. Steffen. Model generation by moderated regular extrapolation. In R. Kutsche and H. Weber, editors, Proceedings of the 5th International Conference on Fundamental Approaches to Software Engineering (FASE ’02), volume 2306 of LNCS, pages 80–95, Heidelberg, Germany, 2002. Springer-Verlag.
41.
J. Heinz, C. de la Higuera, and T. Oates, editors. Grammatical Inference: Theoretical Results and Applications, 11th International Conference, ICGI 2012, University of Maryland, College Park, United States. Proceedings, volume 21. JMLR.org, 2012.
42.
F. Howar, B. Steffen, and M. Merten. From ZULU to RERS—lessons learned in the zulu challenge. In 4th International Symposium on Leveraging Applications, ISoLA 2010, volume 6415 of Lncs, pages 687–704. Springer-Verlag, 2010.
43.
M. Kearns. Efficient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 392–401, 1993.
44.
M. Kearns and L. Valiant. Cryptographic limitations on learning boolean formulae and finite automata. In 21st ACM Symposium on Theory of Computing, pages 433–444, 1989.
45.
M. J. Kearns and U. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.
46.
E. B. Kinber. On learning regular expressions and patterns via membership and correction queries. In Clark et al. [27], pages 125–138.
47.
V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Doklady Akademii Nauk SSSR, 163(4):845–848, 1965.MathSciNetMATH
48.
O. Maler and A. Pnueli. On the learnability of infinitary regular sets. In Proceedings of COLT, pages 128–136, San Mateo, 1991. Morgan–Kaufmann.
49.
G. Paliouras and Y. Sakakibara, editors. Grammatical Inference: Algorithms and Applications, Proceedings of ICGI ’04, volume 3264 of LNAI. Springer-Verlag, 2004.
50.
L. Pitt. Inductive inference, DFA’s, and computational complexity. In Analogical and Inductive Inference, number 397 in LNAI, pages 18–44. Springer-Verlag, 1989.
51.
H. Raffelt and B. Steffen. LearnLib: A library for automata learning and experimentation. In Proceedings of FASE 2006, volume 3922 of LNCS, pages 377–380. Springer-Verlag, 2006.
52.
R. L. Rivest and R. E. Schapire. Inference of finite automata using homing sequences. Information and Computation, 103:299–347, 1993.MathSciNetCrossRefMATH
53.
Y. Sakakibara. Inferring parsers of context-free languages from structural examples. Technical Report 81, Fujitsu Limited, International Institute for Advanced Study of Social Information Science, Numazu, Japan, 1987.
54.
Y. Sakakibara, S. Kobayashi, K. Sato, T. Nishino, and E. Tomita, editors. Grammatical Inference: Algorithms and Applications, Proceedings of ICGI ’06, volume 4201 of LNAI. Springer-Verlag, 2006.
55.
B. Steffen, F. Howar, and M. Merten. Introduction to active automata learning from a practical perspective. In SFM 2011. Advanced Lectures, volume 6659 of LNCS, pages 256–296. Springer-Verlag, 2011.
56.
C. Tirnauca. A note on the relationship between different types of correction queries. In Clark et al. [27], pages 213–223.
57.
L. G. Valiant. A theory of the learnable. Communications of the Association for Computing Machinery, 27(11):1134–1142, 1984.CrossRefMATH
58.
J. M. Vilar. Query learning of subsequential transducers. In L. Miclet and C. de la Higuera, editors, Proceedings of ICGI ’96, number 1147 in LNAI, pages 72–83. Springer-Verlag, 1996.
59.
R. Wagner and M. Fisher. The string-to-string correction problem. Journal of the ACM, 21:168–178, 1974.
60.
M. Warmuth. Towards representation independence in PAC-learning. In K. P. Jantke, editor, Proceedings of AII ’89, volume 397 of LNAI, pages 78–103. Springer-Verlag, 1989.
61.
T. Yokomori. Learning non-deterministic finite automata from queries and counterexamples. Machine Intelligence, 13:169–189, 1994.
62.
T. Yokomori. Learning two-tape automata from queries and counterexamples. Mathematical Systems Theory, pages 259–270, 1996.
Metadata
Title
Learning Grammars and Automata with Queries
Author
Colin de la Higuera
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_3

Premium Partner

    Image Credits