Finite thickness (original) (raw)

From Wikipedia, the free encyclopedia

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]

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 ⊆ ...).

  1. ^ 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.
  2. ^ 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
  3. ^ Ambainis et al. 1997, Definition 26
  4. ^ Ambainis et al. 1997, Corollary 29