Skip to main content
SpringerLink
Log in
Book cover

Conference on Computability in Europe

CiE 2022: Revolutions and Revelations in Computability pp 1–12Cite as

Calculating the Mind Change Complexity of Learning Algebraic Structures

  • Conference paper
  • First Online:

  • 379 Accesses

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13359))

Abstract

This paper studies algorithmic learning theory applied to algebraic structures. In previous papers, we have defined our framework, where a learner, given a family of structures, receives larger and larger pieces of an arbitrary copy of a structure in the family and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. The learning is successful if there is a learner that eventually stabilizes to a correct conjecture. Here, we analyze the number of mind changes that are needed to learn a given family \(\mathfrak {K}\). We give a descriptive set-theoretic interpretation of such mind change complexity. We also study how bounding the Turing degree of learners affects the mind change complexity of a given family of algebraic structures.

Bazhenov was supported by the Ministry of Education and Science of the Republic of Kazakhstan, grant AP08856493 “Positive graphs and computable reducibility on them as mathematical model of databases”. Cipriani’s research was partially supported by the Italian PRIN 2017 Grant “Mathematical Logic: models, sets, computability”. We also thank the anonymous referees for their careful reading of the paper and the valuable suggestions.

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

Chapter
USD   29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD   54.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD   69.99
Price excludes VAT (USA)
  • 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

Learn about institutional subscriptions

References

  1. Ambainis, A., Jain, S., Sharma, A.: Ordinal mind change complexity of language identification. In: Ben-David, S. (ed.) EuroCOLT 1997. LNCS, vol. 1208, pp. 301–315. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62685-9_25

    Chapter  Google Scholar 

  2. Ash, C., Knight, J.: Computable Structures and the Hyperarithmetical Hierarchy. ISSN, Elsevier Science (2000)

    Google Scholar 

  3. Bazhenov, N., Cipriani, V., San Mauro, L.: Learning algebraic structures with the help of Borel equivalence relations (2021). Preprint arXiv:2110.14512

  4. Bazhenov, N., Fokina, E., Rossegger, D., San Mauro, L.: Degrees of bi-embeddable categoricity. Computability 10(1), 1–16 (2021)

    Article  MathSciNet  Google Scholar 

  5. Bazhenov, N., Fokina, E., San Mauro, L.: Learning families of algebraic structures from informant. Inf. Comput. 275, 104590 (2020). https://doi.org/10.1016/j.ic.2020.104590

  6. Bazhenov, N., San Mauro, L.: On the Turing complexity of learning finite families of algebraic structures. J. Log. Comput. 31(7), 1891–1900 (2021). https://doi.org/10.1093/logcom/exab044

    Article  MathSciNet  MATH  Google Scholar 

  7. Fokina, E.B., Kalimullin, I., Miller, R.: Degrees of categoricity of computable structures. Arch. Math. Logic 49(1), 51–67 (2010)

    Article  MathSciNet  Google Scholar 

  8. Freivalds, R., Smith, C.: On the role of procrastination in machine learning. Inf. Comput. 107(2), 237–271 (1993). https://doi.org/10.1006/inco.1993.1068

    Article  MathSciNet  MATH  Google Scholar 

  9. Gao, Z., Stephan, F., Wu, G., Yamamoto, A.: Learning families of closed sets in matroids. In: Dinneen, M.J., Khoussainov, B., Nies, A. (eds.) WTCS 2012. LNCS, vol. 7160, pp. 120–139. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-27654-5_10

    Chapter  Google Scholar 

  10. Glymour, C.: Inductive inference in the limit. Erkenntnis 22, 23–31 (1985). https://doi.org/10.1007/BF00269958

    Article  Google Scholar 

  11. Gold, E.M.: Language identification in the limit. Inf. Control 10(5), 447–474 (1967). https://doi.org/10.1016/S0019-9958(67)91165-5

    Article  MathSciNet  MATH  Google Scholar 

  12. Harizanov, V.S., Stephan, F.: On the learnability of vector spaces. J. Comput. Syst. Sci. 73(1), 109–122 (2007). https://doi.org/10.1016/j.jcss.2006.09.001

    Article  MathSciNet  MATH  Google Scholar 

  13. Kechris, A.: Classical Descriptive Set Theory. Graduate Texts in Mathematics, Springer, New York (2012)

    MATH  Google Scholar 

  14. Luo, W., Schulte, O.: Mind change efficient learning. Inf. Comput. 204(6), 989–1011 (2006). https://doi.org/10.1016/j.ic.2006.02.004

    Article  MathSciNet  MATH  Google Scholar 

  15. Merkle, W., Stephan, F.: Trees and learning. J. Comput. Syst. Sci. 68(1), 134–156 (2004). https://doi.org/10.1016/j.jcss.2003.08.001

    Article  MathSciNet  MATH  Google Scholar 

  16. Putnam, H.: Trial and error predicates and the solution to a problem of Mostowski. J. Symbolic Logic 30(1), 49–57 (1965). https://doi.org/10.2307/2270581

    Article  MathSciNet  MATH  Google Scholar 

  17. Stephan, F., Ventsov, Y.: Learning algebraic structures from text. Theor. Comput. Sci. 268(2), 221–273 (2001). https://doi.org/10.1016/S0304-3975(00)00272-3

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Sobolev Institute of Mathematics, Novosibirsk, Russia

    Nikolay Bazhenov

  2. Università degli Studi di Udine, Udine, Italy

    Vittorio Cipriani

  3. Sapienza Università di Roma, Roma, Italy

    Luca San Mauro

Authors
  1. Nikolay Bazhenov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vittorio Cipriani
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luca San Mauro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vittorio Cipriani .

Editor information

Editors and Affiliations

  1. Department of Computer Science, Swansea University, Swansea, UK

    Ulrich Berger

  2. Department of Mathematics, Hofstra University, Hempstead, NY, USA

    Johanna N. Y. Franklin

  3. Georg-August University Göttingen, Göttingen, Germany

    Florin Manea

  4. Department of Computer Science, Swansea University, Swansea, UK

    Arno Pauly

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Bazhenov, N., Cipriani, V., San Mauro, L. (2022). Calculating the Mind Change Complexity of Learning Algebraic Structures. In: Berger, U., Franklin, J.N.Y., Manea, F., Pauly, A. (eds) Revolutions and Revelations in Computability. CiE 2022. Lecture Notes in Computer Science, vol 13359. Springer, Cham. https://doi.org/10.1007/978-3-031-08740-0_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-08740-0_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-08739-4

  • Online ISBN: 978-3-031-08740-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation