Finite thickness

From Wikipedia, the free encyclopedia
  (Redirected from MEF-condition)
Jump to: navigation, search

In formal language theory, a class of languages \mathcal L has finite thickness if for every string s, there are only finitely many consistent languages in \mathcal L. This condition was introduced by Dana Angluin in connection with learning, as a sufficient condition for language identification in the limit. The related notion of M-finite thickness

We say that \mathcal L satisfies the MEF-condition if for each string s and each consistent language L in the class, there is a minimal consistent language in \mathcal L, which is a sublanguage of L. Symmetrically, we say that \mathcal L satisfies the MFF-condition if for every string s there are only finitely many minimal consistent languages in \mathcal L. Finally, \mathcal L is said to have M-finite thickness if it satisfies both the MEF and MFF conditions.

Finite thickness implies M-finite thickness. However, there are classes that are of M-finite thickness but not of finite thickness (for example, let {Ln} be a class of languages such that L_0 \subseteq L_1 \subseteq \ldots ).

Personal tools
Namespaces
Variants
Actions
Navigation
Interaction
Toolbox
Print/export