# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Solutions to Open Questions for Non-U-Shaped Learning with Memory Limitations

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Case, J., & Kötzing, T. (2010). Solutions to Open Questions for Non-U-Shaped Learning
with Memory Limitations. In M. Hutter, F. Stephan, V. Vovk, & T. Zeugmann (*Algorithmic Learning Theory* (pp. 285-299). Berlin: Springer. doi:10.1007/978-3-642-16108-7_24.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-16E6-6

##### Abstract

A U-shape occurs when a learner first learns, then unlearns, and, finally,
relearns, some target concept. Within the framework of Inductive Inference,
previous results have shown, for example, that U-shapes are unnecessary for
explanatory learning, but are necessary for behaviorally correct learning.
This paper solves the following
two problems regarding non-U-shaped learning posed in the prior literature.
First, it is shown that there are classes learnable with three memory states
that are not learnable non-U-shapedly with any finite number of memory states.
This result is surprising, as for learning with one or two memory states,
U-shapes are known to be unnecessary.
Secondly, it is shown that there is a class learnable memorylessly with a
single feedback query such that this class is not learnable non-U-shapedly
memorylessly with any finite number of feedback queries. This result is
complemented by the result that any class of \emph{infinite} languages
learnable memorylessly with finitely many feedback queries is so learnable
without U-shapes -- in fact, all classes of infinite languages learnable with
\emph{complete} memory are learnable memorylessly with finitely many feedback
queries and without U-shapes. On the other hand, we show that there is a
class of infinite languages learnable memorylessly with a single feedback
query, which is \emph{not} learnable with\emph{out} U-shapes by any particular
bounded number of feedback queries.