In formal language theory, a class of languages has finite thickness if for every string s, there are only finitely many consistent languages in . 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 satisfies the MEF-condition if for each string s and each consistent language L in the class, there is a minimal consistent language in, which is a sublanguage of L. Symmetrically, we say that satisfies the MFF-condition if for every string s there are only finitely many minimal consistent languages in . Finally, 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 be a class of languages such that ).
Other articles related to "finite thickness, finite":
... Finite thickness implies finite elasticity the converse is not true ... Finite elasticity and conservatively learnable implies the existence of a mind change bound Finite elasticity and M-finite thickness implies the existence of a ... However, M-finite thickness alone does not imply the existence of a mind change bound neither does the existence of a mind change bound imply M-finite thickness Existence ...
... A class of languages has finite thickness if for every string s, there are only a finite number of languages in the class that are consistent with s ... Angluin showed that if a class of recursive languages has finite thickness, then it is learnable in the limit ... A class with finite thickness certainly satisfies MEF-condition and MFF-condition in other words, finite thickness implies M-finite thickness ...
Famous quotes containing the words thickness and/or finite:
“For his teeth seem for laughing round an apple.
There lurk no claws behind his fingers supple;
And God will grow no talons at his heels,
Nor antlers through the thickness of his curls.”
—Wilfred Owen (1893–1918)
“Are not all finite beings better pleased with motions relative than absolute?”
—Henry David Thoreau (1817–1862)