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 ⊆ ...).
- ↑ Lua error in package.lua at line 80: module 'strict' not found.; 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.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.; here: Definition 25
- ↑ Ambainis et al. 1997, Definition 26
- ↑ Ambainis et al. 1997, Corollary 29
<templatestyles src="Asbox/styles.css"></templatestyles>
