License
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://drops.dagstuhl.de/opus/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
Seminar: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 25.02.2015


DROPS-Home | Fulltext Search | Imprint Published by LZI