Document Open Access Logo

Inductive Inference and Reverse Mathematics

Authors Rupert Hölzl, Sanjay Jain, Frank Stephan

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.420.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Rupert Hölzl
Sanjay Jain
Frank Stephan

Cite As Get BibTex

Rupert Hölzl, Sanjay Jain, and Frank Stephan. Inductive Inference and Reverse Mathematics. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 420-433, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.420

Abstract

The present work investigates inductive inference from the perspective 
of reverse mathematics. Reverse mathematics is a framework which relates
the proof strength of theorems and axioms throughout many areas of
mathematics in an interdisciplinary way. The present work looks at
basic notions of learnability including Angluin's tell-tale condition and its variants for learning in the limit and for conservative learning. Furthermore, the more general criterion of partial learning is investigated. These notions are studied in the reverse mathematics context for uniformly and weakly represented families of languages. The results are stated in terms of axioms referring to domination and induction strength.

Subject Classification

Keywords
  • reverse mathematics
  • recursion theory
  • inductive inference
  • learning from positive data

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Lenny Adleman and Manuel Blum. Inductive inference and unsolvability. The Journal of Symbolic Logic, 56:891-900, 1991. Google Scholar
  2. Dana Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117-135, 1980. Google Scholar
  3. Lenore Blum and Manuel Blum. Towards a mathematical theory of inductive inference. Information and Control, 28:125-155, 1975. Google Scholar
  4. Matthew de Brecht, Masanori Kobayashi, Hiroo Tokunaga, and Akihiro Yamamoto. Inferability of closed set systems from positive data. In New Frontiers in Artificial Intelligence, JSAI 2006. Conference and Workshops, Tokyo, Japan, 5-9 June 2006, Revised Selected Papers, volume 4384 of Lecture Notes in Computer Science, pages 265-275. Springer, 2007. Google Scholar
  5. Matthew de Brecht and Akihiro Yamamoto. Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data. Theoretical Computer Science, 411(7-9):976-985, 2010. Google Scholar
  6. Matthew de Brecht and Akihiro Yamamoto. Topological properties of concept spaces (full version). Information and Computation, 208(4):327-340, 2010. Google Scholar
  7. John Case and Chris Lynes. Machine inductive inference and language identification. In Proceedings of the Nineth International Colloquium on Automata, Languages and Programming, volume 140 of Lecture Notes in Computer Science, pages 107-115. Springer, 1982. Google Scholar
  8. Chi Tat Chong, Theodore A. Slaman, and Yue Yang. Π¹₁-conservation of combinatorial principles weaker than Ramsey’s theorem for pairs. Advances in Mathematics, 230(3):1060-1077, 2012. Google Scholar
  9. Chi Tat Chong, Theodore A. Slaman, and Yue Yang. The metamathematics of stable Ramsey’s theorem for pairs. The Journal of the American Mathematical Society, 27:863-892, 2014. Google Scholar
  10. Damir D. Dzhafarov and Carl Mummert. On the strength of the finite intersection principle. Israel Journal of Mathematics, 196:345-361, 2013. Google Scholar
  11. Harvey Friedman. Some systems of second order arithmetic and their use. In Proceedings of the International Congress of Mathematicians, Vancouver, 1974, volume 1, pages 235-242, 1974. Google Scholar
  12. E. Mark Gold. Language identification in the limit. Information and Control, 10:447-474, 1967. Google Scholar
  13. Susumu Hayashi. Mathematics based on incremental learning - excluded middle and inductive inference. Theoretical Computer Science, 350:125-139, 2006. Google Scholar
  14. Dennis Hirschfeldt. Slicing the Truth. On the Computable and Reverse Mathematics of Combinatorial Principles, volume 28 of Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific, 2014. Google Scholar
  15. Sanjay Jain, Daniel Osherson, James Royer, and Arun Sharma. Systems That Learn: An Introduction to Learning Theory, Second Edition. The MIT Press, Cambridge, Massachusetts, 1999. Google Scholar
  16. Satoshi Kobayashi. Approximate identification, finite elasticity and lattice structure of hypothesis space. Technical Report CSIM 96-04, Department of Computer Science and Information Mathematics, University of Electro-Communications, 1996. Google Scholar
  17. Daniel Osherson, Michael Stob, and Scott Weinstein. Systems That Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists. The MIT Press, Cambridge, Massachusetts, 1986. Google Scholar
  18. Dilip Raghavan, Frank Stephan, and Jing Zhang. Weakly represented families in reverse mathematics. Manuscript, 2014. Google Scholar
  19. Stephen G. Simpson. Subsystems of Second Order Arithmetic. Cambridge University Press, 2009. Google Scholar
  20. Keith Wright. Identification of unions of languages drawn from an identifiable class. In Proceedings of the Second Annual Workshop on Computational Learning Theory, pages 328-333. Morgan Kaufmann, 1989. Google Scholar
  21. Thomas Zeugmann, Steffen Lange, and Shyam Kapur. Characterizations of monotonic and dual monotonic language learning. Information and Computation, 120(2):155-173, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact