Finite thickness

In formal language theory, in particular in algorithmic learning theory, a class C of 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 identifiable in the limit.

{{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.

References

{{reflist}}

Category:Formal languages

{{comp-sci-theory-stub}}