papersSEP 10 04:00 UTC
Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy
A new paper gives a complete characterization of when an algorithm can output valid unseen elements of an unknown infinite language from any exhaustive stream of positive examples. The authors show generation is possible exactly when families admit finite witnesses, and they structure the problem's difficulty into a separation-width hierarchy over countable domains. The result extends classical inductive inference and language learnability theory to arbitrary families.