Learning a Subclass of Regular Patterns in Polynomial Time | SpringerLink
Skip to main content
Springer Nature Link
Log in

Learning a Subclass of Regular Patterns in Polynomial Time

  • Conference paper
Algorithmic Learning Theory (ALT 2003)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2842))

Included in the following conference series:

Abstract

Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability of success on extended regular languages generated by patterns π of the form x 0 α 1 x 1 ... α m x m for unknown m but known c, from number of examples polynomial in m (and exponential in c), where α 1...α m are variables and where α 1,...,α m are each strings of constants or terminals of length c. This assumes that the algorithm randomly draws samples with natural and plausible assumptions on the distribution.

The more general looking case of extended regular patterns which alternate between a variable and fixed length constant strings, beginning and ending with either a variable or a constant string is similarly handled.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Angluin, D.: Finding patterns common to a set of strings. Journal of Computer and System Sciences 21, 46–62 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  2. Arikawa, S., Shinohara, T., Yamamoto, A.: Learning elementary formal systems. Theoretical Computer Science 95, 97–113 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  3. Shinohara, T., Arimura, H.: Inductive inference of unbounded unions of pattern languages from positive data. Theoretical Computer Science 241, 191–209 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bratko, I., Muggleton, S.: Applications of inductive logic programming. Communications of the ACM (1995)

    Google Scholar 

  5. Brāzma, A., Ukkonen, E., Vilo, J.: Discovering unbounded unions of regular pattern languages from positive examples. In: Nagamochi, H., Suri, S., Igarashi, Y., Miyano, S., Asano, T. (eds.) ISAAC 1996. LNCS, vol. 1178, pp. 95–104. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  6. Case, J., Jain, S., Kaufmann, S., Sharma, A., Stephan, F.: Predictive learning models for concept drift. Theoretical Computer Science 268, 323–349 (2001) (Special Issue for ALT 1998)

    Article  MATH  MathSciNet  Google Scholar 

  7. Case, J., Jain, S., Lange, S., Zeugmann, T.: Incremental concept learning for bounded data mining. Information and Computation 152(1), 74–110 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  8. Erlebach, T., Rossmanith, P., Stadtherr, H., Steger, A., Zeugmann, T.: Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries. Theoretical Computer Science 261(1), 119–156 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  9. Gold, E.M.: Language identification in the limit. Information & Control 10, 447–474 (1967)

    Article  MATH  Google Scholar 

  10. Kearns, M., Pitt, L.: A polynomial-time algorithm for learning k-variable pattern languages from examples. In: Rivest, R., Haussler, D., Warmuth, M.K. (eds.) Proceedings of the Second Annual ACM Workshop on Computational Learning Theory, pp. 57–71. Morgan Kaufmann Publishers Inc., San Francisco (1989)

    Google Scholar 

  11. Kilpeläinen, P., Mannila, H., Ukkonen, E.: MDL learning of unions of simple pattern languages from positive examples. In: Vitányi, P.M.B. (ed.) EuroCOLT 1995. LNCS, vol. 904, pp. 252–260. Springer, Heidelberg (1995)

    Google Scholar 

  12. Lange, S., Wiehagen, R.: Polynomial time inference of arbitrary pattern languages. New Generation Computing 8, 361–370 (1991)

    Article  MATH  Google Scholar 

  13. Lavrač, N., Džeroski, S.: Inductive Logic Programming: Techniques and Applications. Ellis Horwood (1994)

    Google Scholar 

  14. Matsumoto, S., Shinohara, A.: Learnability of subsequence languages. In: Information Modeling and Knowledge Bases VIII, pp. 335–344. IOS Press, Amsterdam (1997)

    Google Scholar 

  15. Mitchell, T.: Machine Learning. McGraw Hill, New York (1997)

    MATH  Google Scholar 

  16. Miyano, S., Shinohara, A., Shinohara, T.: Polynomial-time learning of elementary formal systems. New Generation Computing 18, 217–242 (2000)

    Article  Google Scholar 

  17. Muggleton, S., De Raedt, L.: Inductive logic programming: Theory and methods. Journal of Logic Programming 19/20, 669–679 (1994)

    Article  Google Scholar 

  18. Nix, R.: Editing by examples. Technical Report 280, Department of Computer Science, Yale University, New Haven, CT, USA (1983)

    Google Scholar 

  19. Reidenbach, D.: A Negative Result on Inductive Inference of Extended Pattern Languages. In: Cesa-Bianchi, N., Numao, M. (eds.) Proceedings of 13th International Conference Algorithmic Learning Theory, ALT 2002, pp. 308–320. Springer, Heidelberg (2002)

    Google Scholar 

  20. Reischuk, R., Zeugmann, T.: Learning one-variable pattern languages in linear average time. In: Proceedings of the Eleventh Annual Conference on Computational Learning Theory, pp. 198–208. ACM Press, New York (1998)

    Chapter  Google Scholar 

  21. Rossmanith, P., Zeugmann, T.: Stochastic Finite Learning of the Pattern Languages. Machine Learning 44(1/2), 67–91 (2001); Special Issue on Automata Induction, Grammar Inference, and Language Acquisition

    Article  MATH  Google Scholar 

  22. Salomaa, A.: Patterns (The Formal Language Theory Column). EATCS Bulletin 54, 46–62 (1994)

    Google Scholar 

  23. Salomaa, A.: Return to patterns (The Formal Language Theory Column). EATCS Bulletin 55, 144–157 (1994)

    Google Scholar 

  24. Schapire, R.: Pattern languages are not learnable. In: Fulk, M.A., Case, J. (eds.) Proceedings, 3rd Annual ACM Workshop on Computational Learning Theory, pp. 122–129. Morgan Kaufmann Publishers, Inc., San Francisco (1990)

    Google Scholar 

  25. Shimozono, S., Shinohara, A., Shinohara, T., Miyano, S., Kuhara, S., Arikawa, S.: Knowledge acquisition from amino acid sequences by machine learning system BONSAI. Trans. Information Processing Society of Japan 35, 2009–2018 (1994)

    Google Scholar 

  26. Shinohara, T.: Polynomial time inference of extended regular pattern languages. In: Goto, E., Nakajima, R., Yonezawa, A., Nakata, I., Furukawa, K. (eds.) RIMS 1982. LNCS, vol. 147, pp. 115–127. Springer, Heidelberg (1983)

    Google Scholar 

  27. Shinohara, T.: Inferring unions of two pattern languages. Bulletin of Informatics and Cybernetics 20, 83–88 (1983)

    MATH  MathSciNet  Google Scholar 

  28. Shinohara, T., Arikawa, S.: Learning data entry systems: An application of inductive inference of pattern languages. Research Report 102, Research Institute of Fundamental Information Science, Kyushu University (1983)

    Google Scholar 

  29. Shinohara, T., Arikawa, S.: Pattern inference. In: Lange, S., Jantke, K.P. (eds.) GOSLER 1994. LNCS (LNAI), vol. 961, pp. 259–291. Springer, Heidelberg (1995)

    Google Scholar 

  30. Smullyan, R.: Theory of Formal Systems, Annals of Mathematical Studies, Princeton, NJ, vol. (47) (1961)

    Google Scholar 

  31. Valiant, L.G.: A theory of the learnable. Communications of the ACM 27, 1134–1142 (1984)

    Article  MATH  Google Scholar 

  32. Wright, K.: Identification of unions of languages drawn from an identifiable class. In: Rivest, R., Haussler, D., Warmuth, M.K. (eds.) Proceedings of the Second Annual Workshop on Computational Learning Theory, pp. 328–333. Morgan Kaufmann Publishers, Inc., San Francisco (1989)

    Google Scholar 

  33. Zeugmann, T.: Lange and Wiehagen’s pattern language learning algorithm: An average-case analysis with respect to its total learning time. Annals of Mathematics and Artificial Intelligence 23(1–2), 117–145 (1998)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer and Information Sciences, University of Delaware, Newark, DE, 19716-2586, USA

    John Case

  2. School of Computing, National University of Singapore, Singapore, 117543

    Sanjay Jain

  3. Institute for Theoretical Informatics, University at Lübeck, Wallstr. 40, 23560, Lübeck, Germany

    Rüdiger Reischuk & Thomas Zeugmann

  4. Mathematisches Institut, Universität Heidelberg, Im Neuenheimer Feld 294, 69120, Heidelberg, Germany

    Frank Stephan

Authors
  1. John Case
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sanjay Jain
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rüdiger Reischuk
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Frank Stephan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Thomas Zeugmann
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Universitat Politècnica de Catalunya, Barcelona, Spain

    Ricard Gavaldá

  2. Meme Media Laboratory, Hokkaido University Sapporo, Kita 13, Nishi 8, Kita-ku, 060-8628, Sapporo, Japan

    Klaus P. Jantke

  3.  ,  

    Eiji Takimoto

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Case, J., Jain, S., Reischuk, R., Stephan, F., Zeugmann, T. (2003). Learning a Subclass of Regular Patterns in Polynomial Time. In: Gavaldá, R., Jantke, K.P., Takimoto, E. (eds) Algorithmic Learning Theory. ALT 2003. Lecture Notes in Computer Science(), vol 2842. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39624-6_19

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-39624-6_19

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-20291-2

  • Online ISBN: 978-3-540-39624-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation