Finite thickness

From Wikipedia, the free encyclopedia

In formal language theory, a class of languages \mathcal L has finite thickness if for every string s, there are only finite 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 finite 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.

M-finite thickness should be compared with finite thickness. While finite thickness implies the existence of a mind change bound, M-finite thickness does not. For example, let {Ln} be a class of languages such that L_0 \subseteq L_1 \subseteq \ldots then there is no mind change bound for this class.


 This mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../f/i/n/Finite_thickness.html"