Non-Uniform Language Identification in the Limit

We study language identification in the limit and ask when the number of examples needed for identification can be bounded independently of their order of presentation. The learner must identify every target in the limit and must be correct whenever it has observed at least a target-dependent number of distinct positive examples. In learning theory, allowing the bound to depend on the target is known as a non-uniform guarantee. We characterize which countable collections admit non-uniform identification through a variant of Angluin's condition, and give a corresponding characterization of the stronger requirement of uniform identification. We extend these characterizations to variants studied in classical and recent work, asking whether more flexible outputs and additional information can overcome the obstacles to non-uniform identification. These variants permit a list of at most $k$ languages containing the target, finitely many disagreements with the target, or provide the learner with certain auxiliary information about the target language, as allowed by Charikar, Kleinberg, and Pabbaraju (2026). Even with these relaxations, non-uniform identification can fail for collections that admit identification in the limit without an order-independent bound. However, suitably chosen binary labels attached to every prefix of an example suffice for non-uniform identification of every countable collection of infinite languages.