# Finite thickness

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]}

## [edit]

Given a language *L* and an indexed class *C* = { *L*_{1}, *L*_{2}, *L*_{3}, ... } 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* = { *L*_{1}, *L*_{2}, *L*_{3}, ... } such that *L*_{1} ⊆ *L*_{2} ⊆ *L*_{3} ⊆ ...).

## References[edit]

**^**Dana Angluin (1980). "Inductive Inference of Formal Languages from Positive Data" (PDF).*Information and Control*.**45**(2): 117–135. doi:10.1016/s0019-9958(80)90285-5. (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.**^**Andris Ambainis; Sanjay Jain; Arun Sharma (1997). "Ordinal mind change complexity of language identification".*Computational Learning Theory*(PDF). LNCS. Vol. 1208. Springer. pp. 301–315.; here: Definition 25**^**Ambainis et al. 1997, Definition 26**^**Ambainis et al. 1997, Corollary 29