License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.420
URN: urn:nbn:de:0030-drops-49324
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4932/
Go to the corresponding LIPIcs Volume Portal

Hölzl, Rupert ; Jain, Sanjay ; Stephan, Frank

Inductive Inference and Reverse Mathematics

pdf-format:
32.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{hlzl_et_al:LIPIcs:2015:4932,
  author =	{Rupert H{\"o}lzl and Sanjay Jain and Frank Stephan},
  title =	{{Inductive Inference and Reverse Mathematics}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{420--433},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4932},
  URN =		{urn:nbn:de:0030-drops-49324},
  doi =		{10.4230/LIPIcs.STACS.2015.420},
  annote =	{Keywords: reverse mathematics, recursion theory, inductive inference, learning from positive data}
}

Keywords: reverse mathematics, recursion theory, inductive inference, learning from positive data
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI