Normal Forms for (Semantically) Witness-Based Learners in Inductive
  Inference
  We study learners (computable devices) inferring formal languages, a setting
referred to as language learning in the limit or inductive inference. In
particular, we require the learners we investigate to be witness-based, that
is, to justify each of their mind changes. Besides being a natural requirement
for a learning task, this restriction deserves special attention as it is a
specialization of various important learning paradigms. In particular, with the
help of witness-based learning, explanatory learners are shown to be equally
powerful under these seemingly incomparable paradigms. Nonetheless, until now,
witness-based learners have only been studied sparsely.
  In this work, we conduct a thorough study of these learners both when
requiring syntactic and semantic convergence and obtain normal forms thereof.
In the former setting, we extend known results such that they include
witness-based learning and generalize these to hold for a variety of learners.
Transitioning to behaviourally correct learning, we also provide normal forms
for semantically witness-based learners. Most notably, we show that set-driven
globally semantically witness-based learners are equally powerful as their
Gold-style semantically conservative counterpart. Such results are key to
understanding the, yet undiscovered, mutual relation between various important
learning paradigms when learning behaviourally correctly.
