Abstract
We describe algorithms that directly infer regular expressions from positive data and characterize the regular language classes that can be learned this way.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ahonen, H.: Disambiguation of SGML content models. In: Nicholas, C., Wood, D. (eds.) PODDP 1996 and PODP 1996. LNCS, vol. 1293, pp. 27–37. Springer, Heidelberg (1997)
Ahonen, H., Mannila, H., Nikunen, E.: Forming grammars for structured documents: an application of grammatical inference. In: Carrasco, R.C., Oncina, J. (eds.) ICGI 1994. LNCS (LNAI), vol. 862, pp. 153–167. Springer, Heidelberg (1994)
Berstel, J., Boasson, L.: Formal properties of XML grammars and languages. Acta Informatica 38(9), 649–671 (2002)
Blackwell, A.F.: SWYN: A visual representation for regular expressions. In: Lieberman, H. (ed.) Your wish is my command: Giving users the power to instruct their software, pp. 245–270. Morgan Kaufmann, San Francisco (2001)
Brazma, A.: Efficient learning of regular expressions from approximate examples. In: Greiner, R., Petsche, T., Hanson, S.J. (eds.) Computational Learning Theory and Natural Learning Systems, Making Learning Systems Practical, ch.19, vol. IV, pp. 337–352. MIT Press, Cambridge (1997)
Chung, Y.D., Kim, J.W., Kim, M.H.: Efficient preprocessing of XML queries using structured signatures. Information Processing Letters 87, 257–264 (2003)
CZ-Redaktion.: Maschinenmenschen plaudern per XML mit der Unternehmens-IT. Computer Zeitung (50), 30 (2000)
Fernau, H.: Learning XML grammars. In: Perner, P. (ed.) MLDM 2001. LNCS (LNAI), vol. 2123, pp. 73–87. Springer, Heidelberg (2001)
Garofalakis, M., Gionis, A., Rastogi, R., Seshadri, S., Shim, K.: XTRACT: learning document type descriptors from XML document collections. Data Mining and Knowledge Discovery 7, 23–56 (2003)
Gold, E.M.: Language identification in the limit. Information and Control (now Information and Computation) 10, 447–474 (1967)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)
Laird., P.D.: Learning from Good and Bad Data. Kluwer Academic Publishers, Norwell (1988)
Nevill-Manning, C.G., Witten, I.H.: Online and offline heuristics for inferring hierarchies of repetitions in sequences. Proc. IEEE 88, 1745–1755 (2000)
Smith, T.C., Witten, I.H., Cleary, J.G., Legg, S.: Objective evaluation of inferred context-free grammars. In: Proc. Australian and New Zealand Conference on Intelligent Information Systems, Brisbane, Australia (November 1994)
van Zaanen, M.: Bootstrapping Structure into Language: Alignment-Based Learning. PhD, School of Computing, University of Leeds, UK (September 2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fernau, H. (2005). Algorithms for Learning Regular Expressions. In: Jain, S., Simon, H.U., Tomita, E. (eds) Algorithmic Learning Theory. ALT 2005. Lecture Notes in Computer Science(), vol 3734. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11564089_24
Download citation
DOI: https://doi.org/10.1007/11564089_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29242-5
Online ISBN: 978-3-540-31696-1
eBook Packages: Computer ScienceComputer Science (R0)