1 Search Results for "Kinber, Efim"

Document
DOI: 10.4230/LIPIcs.STACS.2012.350
Mind Change Speed-up for Learning Languages from Positive Data

Authors: Sanjay Jain and Efim Kinber

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
Within the frameworks of learning in the limit of indexed classes of recursive languages from positive data and automatic learning in the limit of indexed classes of regular languages (with automatically computable sets of indices), we study the problem of minimizing the maximum number of mind changes F_M(n) by a learner M on all languages with indices not exceeding n. For inductive inference of recursive languages, we establish two conditions under which F_M(n) can be made smaller than any recursive unbounded non-decreasing function. We also establish how F_M(n) is affected if at least one of these two conditions does not hold. In the case of automatic learning, some partial results addressing speeding up the function F_M(n) are obtained.
Cite as

Sanjay Jain and Efim Kinber. Mind Change Speed-up for Learning Languages from Positive Data. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 350-361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{jain_et_al:LIPIcs.STACS.2012.350,
  author =	{Jain, Sanjay and Kinber, Efim},
  title =	{{Mind Change Speed-up for Learning Languages from Positive Data}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{350--361},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.350},
  URN =		{urn:nbn:de:0030-drops-33936},
  doi =		{10.4230/LIPIcs.STACS.2012.350},
  annote =	{Keywords: Algorithmic and automatic learning, mind changes, speedup}
}
  • Refine by Author
  • 1 Jain, Sanjay
  • 1 Kinber, Efim

  • Refine by Classification

  • Refine by Keyword
  • 1 Algorithmic and automatic learning
  • 1 mind changes
  • 1 speedup

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2012

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 Imprint Privacy Contact