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]

Given a language L and an indexed class C = { L1, L2, L3, ... } of languages, a member language Lj ∈ C is called a minimal concept of L within C if L ⊆ Lj, but not L ⊊ Li ⊆ Lj for any Li ∈ C.[2] The class C is said to satisfy the MEF-condition if every finite subset D of a member language Li ∈ C has a minimal concept Lj ⊆ Li. 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 = { L1, L2, L3, ... } such that L1 ⊆ L2 ⊆ L3 ⊆ ...).

gollark: HPMOR?
gollark: I would read the code but I'm on a phone.
gollark: How do you implement it anyway? Forcing events toward noncontradicting outcomes? What if there aren't any?
gollark: But won't stuff just naturally get worn down and, you know, not be the same atoms?
gollark: They don't actually know if the whole universe will break if they do stuff wrong.

References
  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. 1208. Springer. pp. 301–315.; here: Definition 25
  3. Ambainis et al. 1997, Definition 26
  4. Ambainis et al. 1997, Corollary 29


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.