Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes

We investigate learning collections of languages from texts by an inductive\ninference machine with access to the current datum and a bounded memory in form\nof states. Such a bounded memory states (BMS) learner is considered successful\nin case it eventually settles on a correct hypothesis while exploiting only\nfinitely many different states.\n We give the complete map of all pairwise relations for an established\ncollection of criteria of successfull learning. Most prominently, we show that\nnon-U-shapedness is not restrictive, while conservativeness and (strong)\nmonotonicity are. Some results carry over from iterative learning by a general\nlemma showing that, for a wealth of restrictions (the semantic restrictions),\niterative and bounded memory states learning are equivalent. We also give an\nexample of a non-semantic restriction (strongly non-U-shapedness) where the two\nsettings differ.\n