formal language theory In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...

, in particular in

algorithmic learning theory Algorithmic learning theory is a mathematical framework for analyzing machine learning problems and algorithms. Synonyms include formal learning theory and algorithmic inductive inference. Algorithmic learning theory is different from statistica ...

, a class ''C'' of

languages Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...

has finite thickness if every string is contained in at most finitely many languages in ''C''. This condition was introduced by

Dana Angluin Dana Angluin is a professor emeritus of computer science at Yale University. She is known for foundational work in computational learning theory and distributed computing. Education Angluin received her B.A. (1969) and Ph.D. (1976) at University ...

as a

sufficient condition In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...

for ''C'' being identifiable in the limit.

The related notion of M-finite thickness

Given a language ''L'' and an indexed class ''C'' = of languages, a member language ''L''_''j'' ∈ ''C'' is called a minimal concept of ''L'' within ''C'' if ''L'' ⊆ ''L''_''j'', but not ''L'' ⊊ ''L''_''i'' ⊆ ''L''_''j'' for any ''L''_''i'' ∈ ''C''. The class ''C'' is said to satisfy the MEF-condition if every finite subset ''D'' of a member language ''L''_''i'' ∈ ''C'' has a minimal concept ''L''_''j'' ⊆ ''L''_''i''. 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. Finite thickness implies M-finite thickness.Ambainis et al. 1997, Corollary 29 However, there are classes that are of M-finite thickness but not of finite thickness (for example, any class of languages ''C'' = such that ''L''₁ ⊆ ''L''₂ ⊆ ''L''₃ ⊆ ...).

References

Formal languages {{comp-sci-theory-stub