Skip to main content
Springer Nature Link
Log in

Learning Analysis by Reduction from Positive Data

  • Conference paper
Grammatical Inference: Algorithms and Applications (ICGI 2006)

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

Included in the following conference series:

  • 574 Accesses

  • 9 Citations

Abstract

Analysis by reduction is a linguistically motivated method for checking correctness of a sentence. It can be modelled by restarting automata. In this paper we propose a method for learning restarting automata which are strictly locally testable (SLT-R-automata). The method is based on the concept of identification in the limit from positive examples only. Also we characterize the class of languages accepted by SLT-R-automata with respect to the Chomsky hierarchy.

F. Mráz and M. Plátek were partially supported by the Grant Agency of the Czech Republic under Grant-No. 201/04/2102 and by the program ‘Information Society’ under project 1ET100300517. F. Mráz was also supported by the Grant Agency of Charles University in Prague under Grant-No. 358/2006/A-INF/MFF.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Buntrock, G., Otto, F.: Growing context-sensitive languages and Church-Rosser languages. Information and Computation 141, 1–36 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  2. Čejka, J.: Learning correctness preserving reduction analysis. BSc. project, Faculty of Mathematics and Physics, Charles University, Prague (2003) (in Czech)

    Google Scholar 

  3. Garcia, P., Vidal, E.: Inference of k-testable languages in the strict sense and application to syntactic pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence 12, 920–925 (1990)

    Article  Google Scholar 

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

    Article  MATH  Google Scholar 

  5. Hoffmann, P.: Learning restarting automata by genetic algorithms. In: Bieliková, M. (ed.) SOFSEM 2002: Student research forum, Milovy, Czech Republic, pp. 15–20 (2002)

    Google Scholar 

  6. Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) FCT 1995. LNCS, vol. 965, pp. 283–292. Springer, Heidelberg (1995)

    Google Scholar 

  7. Jančar, P., Mráz, F., Plátek, M., Vogel, J.: On monotonic automata with a restart operation. Journal of Automata, Languages and Combinatorics 4, 287–311 (1999)

    MATH  MathSciNet  Google Scholar 

  8. Lopatková, M., Plátek, M., Kuboň, V.: Modeling syntax of free word-order languages: Dependency analysis by reduction. In: Matoušek, V., Mautner, P., Pavelka, T. (eds.) TSD 2005. LNCS (LNAI), vol. 3658, pp. 140–147. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  9. McNaughton, R.: Algebraic decision procedures for local testability. Mathematical Systems Theory 8, 60–76 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  10. Niemann, G., Otto, F.: On the power of RRWW-automata. In: Ito, M., Pǎun, G., Yu, S. (eds.) Words, Semigroups, and Transductions, pp. 341–355. World Scientific, Singapore (2001)

    Chapter  Google Scholar 

  11. Otto, F.: Restarting automata and their relation to the Chomsky hierarchy. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 55–74. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  12. Plátek, M., Lopatková, M., Oliva, K.: Restarting automata: motivations and applications. In: Holzer, M. (ed.) Workshop Petrinetze and 13. Theorietag Formale Sprachen und Automaten, Proc., pp. 90–96. Institut für Informatik, Technische Universität München (2003)

    Google Scholar 

  13. Yokomori, T., Kobayashi, S.: Learning local languages and their application to DNA sequence analysis. IEEE Trans. on Pattern Anal. and Machine Intell 20, 1067–1079 (1998)

    Article  Google Scholar 

  14. Zalcstein, Y.: Locally testable languages. Journal of Computer and System Sciences 6, 151–167 (1972)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00, PRAHA 1, Czech Republic

    František Mráz & Martin Plátek

  2. Fachbereich Mathematik/Informatik, Universität Kassel, 34109, Kassel, Germany

    Friedrich Otto

Authors
  1. František Mráz
    View author publications

    Search author on:PubMed Google Scholar

  2. Friedrich Otto
    View author publications

    Search author on:PubMed Google Scholar

  3. Martin Plátek
    View author publications

    Search author on:PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Biosciences and Informatics, Keio University, 3-14-1 Hiyoshi, Kohoku-ku, 223-8522, Yokohama, Japan

    Yasubumi Sakakibara

  2. Dept. of Computer Science, Kyoto Sangyo University, Kamigamo Motoyama, Kita-ku, Kyoto, Japan

    Satoshi Kobayashi

  3. Japan Biological Informatics Consortium, 10F TIME24 Building, 2-45 Aomi, Koto-ku, 135-8073, Tokyo, Japan

    Kengo Sato

  4. Department of Information and Communication Engineering, Graduate School of Electro-Communications, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu-shi, 182-8585, Tokyo, Japan

    Tetsuro Nishino

  5. Department of Information and Communication Engineering, Faculty of Electro-Communications, The University of Electro-Communications, Chofugaoka 1–5–1, Chofu, 182-8585, Tokyo, Japan

    Etsuji Tomita

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Mráz, F., Otto, F., Plátek, M. (2006). Learning Analysis by Reduction from Positive Data. In: Sakakibara, Y., Kobayashi, S., Sato, K., Nishino, T., Tomita, E. (eds) Grammatical Inference: Algorithms and Applications. ICGI 2006. Lecture Notes in Computer Science(), vol 4201. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11872436_11

Download citation

Publish with us

Policies and ethics