Editing Finite thickness

In [[formal language theory]], in particular in [[algorithmic learning theory]], a class ''C'' of [[formal language#Definition|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 [[language identification in the limit#Finite thickness|identifiable in the limit]].
<ref>{{cite journal| author=Dana Angluin| title=Inductive Inference of Formal Languages from Positive Data| journal=Information and Control| year=1980| volume=45| issue=2| pages=117–135|url=https://www-personal.umich.edu/~yinw/papers/Angluin80.pdf| doi=10.1016/s0019-9958(80)90285-5| doi-access=free}} ([http://citeseer.ist.psu.edu/context/14508/0 citeseer.ist.psu.edu]); 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.</ref>

==The related notion of M-finite thickness==

Given a language ''L'' and an indexed class ''C'' = { ''L''<sub>1</sub>, ''L''<sub>2</sub>, ''L''<sub>3</sub>, ... } of languages, a member language ''L''<sub>''j''</sub> ∈ ''C'' is called a '''minimal concept''' of ''L'' within ''C'' if ''L'' ⊆ ''L''<sub>''j''</sub>, but not ''L'' ⊊ ''L''<sub>''i''</sub> ⊆ ''L''<sub>''j''</sub> for any ''L''<sub>''i''</sub> ∈ ''C''.<ref>{{cite book|author1=Andris Ambainis |author2=Sanjay Jain |author3=Arun Sharma | chapter=Ordinal mind change complexity of language identification| title=Computational Learning Theory| year=1997| volume=1208| pages=301–315| publisher=Springer| series=LNCS| url=https://www.comp.nus.edu.sg/~sanjay/paps/efs2.pdf}}; here: Definition 25</ref>
The class ''C'' is said to satisfy the '''MEF-condition''' if every finite subset ''D'' of a member language ''L''<sub>''i''</sub> ∈ ''C'' has a minimal concept ''L''<sub>''j''</sub> ⊆ ''L''<sub>''i''</sub>. 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.
<ref>Ambainis et al. 1997, Definition 26</ref>
<!---commented-out former, unsourced definitions:---
We say that <math>\mathcal L</math> satisfies the '''MEF-condition''' if for each string s and each consistent language L in the class, there is a minimal consistent language in <math>\mathcal L</math>, which is a sublanguage of L. Symmetrically, we say that <math>\mathcal L</math> satisfies the '''MFF-condition''' if for every string s there are only finitely many minimal consistent languages in <math>\mathcal L</math>.
--->

Finite thickness implies M-finite thickness.<ref>Ambainis et al. 1997, Corollary 29</ref> However, there are classes that are of M-finite thickness but not of finite thickness (for example, any class of languages ''C'' = { ''L''<sub>1</sub>, ''L''<sub>2</sub>, ''L''<sub>3</sub>, ... } such that ''L''<sub>1</sub> ⊆ ''L''<sub>2</sub> ⊆ ''L''<sub>3</sub> ⊆  ...).

== References ==
{{reflist}}

[[Category:Formal languages]]


{{comp-sci-theory-stub}}