Finite Thickness¶
A formal-language class has finite thickness when each word belongs to only finitely many distinct languages in that class.
Core Idea¶
Finite thickness is a property of a class of formal languages. Fix a common alphabet. For each word, count the distinct languages in the class that contain that word. The class has finite thickness if this number is finite for every word. The count may change with the word; the whole class and its individual languages may still be infinite.[ref-0694bf94e95c][ref-3a13dac0c7b3]
Under the assumptions of an effectively indexed, uniformly decidable family of nonempty recursive languages, finite thickness is a sufficient condition for learning the target language in the limit from positive examples. It does not promise a fast learning rate and is not required by every learnable family.[ref-0694bf94e95c][ref-2bab901ea839]
Scope of Application¶
The condition is used in formal-language learning. Two unlike examples are nonerasing pattern languages and languages denoted by nonerasing restricted regular expressions. Both have finite thickness, though they describe languages in different ways. The erasing restricted-expression counterpart does not have the property.[ref-0694bf94e95c][ref-3a13dac0c7b3]
Clarity¶
The key phrase is for every word. For a word of length \(n\), a nonerasing pattern that generates it cannot be longer than \(n\). Over a finite alphabet, that leaves only finitely many different patterns up to variable renaming and therefore finitely many containing languages. This is a per-word bound, not a uniform cap for all words.[ref-0694bf94e95c][ref-a3fbae2e379b]
Do not count differently named expressions as different languages when they denote the same set of words. Conversely, finding infinitely many distinct languages containing one word disproves finite thickness.[ref-0694bf94e95c][ref-3a13dac0c7b3]
Manages Complexity¶
A positive example can fit many hypotheses. Finite thickness makes the set of class languages compatible with any one observed word finite, even when the class itself is infinite. The result lets a learning proof use this local restriction, provided its separate effectiveness assumptions hold.[^ref-0694bf94e95c]
Abstract Reasoning¶
To test a proposed language class, choose an arbitrary word \(w\). Describe every distinct class language containing \(w\), then prove this collection finite. A length bound on descriptions can help, but only if it bounds the denoted languages. One counterexample word with infinitely many containing languages defeats the condition.[ref-0694bf94e95c][ref-3a13dac0c7b3]
When applying the learning theorem, state the indexed family and membership assumptions separately. Failure of finite thickness alone does not prove that a class cannot be learned by another argument.[^ref-0694bf94e95c]
Knowledge Transfer¶
Pattern languages use nonempty substitutions; restricted expressions use concatenation and nonerasing repetition. The same word-to-language counting test works in both. What transfers within formal-language theory is the finite incidence fiber, not a shared grammar syntax or a single learning algorithm.[ref-0694bf94e95c][ref-3a13dac0c7b3]
The proposed parent is live Finiteness by presupposition: each word's containing-language set must be finite. Finite Thickness is not a subtype of a finite collection, because the language class may be infinite.
Example¶
Pattern languages. A word of length \(n\) can be produced only by patterns no longer than \(n\) when variables take nonempty strings. Thus it belongs to finitely many distinct pattern languages. Mapped roles: word → length-\(n\) string; class → pattern languages; incidence → generation by substitution; finite fiber → bounded pattern length.[^ref-0694bf94e95c]
Nonerasing restricted expressions. For a fixed finite alphabet, the class \(RREG_+\) is built from terminals, concatenation and nonerasing repetition. The authors prove that each word belongs to finitely many denoted languages. Mapped roles: word → alphabet string; class → \(RREG_+\) languages; incidence → expression denotes a language containing it; finite fiber → the authors' per-word result. Erasing \(RREG_*\) is a negative contrast.[^ref-3a13dac0c7b3]
Relationships to Other Abstractions¶
Current abstraction Finite Thickness Domain-specific
Parents (1) — more general patterns this builds on
-
Finite Thickness presupposes Finiteness Prime
Finite Thickness requires each word's incidence set of class languages to be finite.
Hierarchy path (1) — routes to 1 parentless root
- Finite Thickness → Finiteness → Boundedness
Neighborhood in Abstraction Space¶
Finite Thickness sits in a sparse region of the domain-specific corpus (92nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Formal Language — 0.84
- Post Canonical System — 0.79
- Polyptoton — 0.79
- Dependency Grammar — 0.78
- Noun — 0.78
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
A finite language, a finite class, a uniform bound over all words, a count of syntax names, finite elasticity, or M-finite thickness. The positive-data learning result is conditional sufficiency, not the definition itself.[ref-0694bf94e95c][ref-3a13dac0c7b3]
References¶
[^ref-2bab901ea839]: Dana Angluin, “Inductive Inference of Formal Languages from Positive Data”, Information and Control 45, no. 2 (1980): 117–135, DOI 10.1016/S0019-9958(80)90285-5. Original publisher record and abstract checked; the full theorem page was not directly accessible. The condition and Corollary 2 attribution in this draft are checked through Shinohara's author survey. [^ref-a3fbae2e379b]: Dana Angluin, “Finding Patterns Common to a Set of Strings”, Journal of Computer and System Sciences 21, no. 1 (1980): 46–62, DOI 10.1016/0022-0000(80)90041-0. Original publisher abstract confirms finite-alphabet nonerasing pattern semantics; the finite-thickness deduction is verified in Shinohara's author survey. [^ref-0694bf94e95c]: Takeshi Shinohara, “Developments from Enquiries into the Learnability of Pattern Languages”, author research survey, PDF p. 2, Definition 4 and Theorems 5–7. Full text inspected; states the finite-thickness definition, attributes the positive-data sufficient condition and pattern-language example to Angluin, and gives the nonerasing length argument. [^ref-3a13dac0c7b3]: Steffen Lange, Thomas Zeugmann, and Sandra Zilles, “Learning Indexed Families of Recursive Languages from Positive Data”, author research survey, Definition 9 at PDF p. 13, Proposition 11 at PDF p. 14, §4.1 at PDF p. 36, and the erasing contrast at PDF pp. 36–37. Full text inspected; the cited nonerasing restricted-expression class has finite thickness, while the erasing class does not.