Finite thickness explained

In formal language theory, in particular in algorithmic learning theory, a class C of languages has finite thickness if every string is contained in at most finitely many languages in C. This condition was introduced by Dana Angluin as a sufficient condition for C being identifiable in the limit.^[1]

The related notion of M-finite thickness

Given a language L and an indexed class C = of languages, a member language L_j ∈ C is called a minimal concept of L within C if L ⊆ L_j, but not L ⊊ L_i ⊆ L_j for any L_i ∈ C.^[2] The class C is said to satisfy the MEF-condition if every finite subset D of a member language L_i ∈ C has a minimal concept L_j ⊆ L_i. Symmetrically, C is said to satisfy the MFF-condition if every nonempty finite set D has at most finitely many minimal concepts in C. Finally, C is said to have M-finite thickness if it satisfies both the MEF- and the MFF-condition.^[3]

Finite thickness implies M-finite thickness.^[4] However, there are classes that are of M-finite thickness but not of finite thickness (for example, any class of languages C = such that L₁ ⊆ L₂ ⊆ L₃ ⊆ ...).

Notes and References

1. Dana Angluin. Inductive Inference of Formal Languages from Positive Data. Information and Control. 1980. 45. 2. 117–135. 10.1016/s0019-9958(80)90285-5. free. (citeseer.ist.psu.edu); here: Condition 3, p.123 mid. Angluin's original requirement (every non-empty string set be contained in at most finitely many languages) is equivalent.
2. Book: Andris Ambainis . Sanjay Jain . Arun Sharma . Ordinal mind change complexity of language identification. Computational Learning Theory. 1997. 1208. 301–315. Springer. LNCS.

   here: Definition 25

3. Ambainis et al. 1997, Definition 26
4. Ambainis et al. 1997, Corollary 29