Exclusion dimension (total-concept convention)¶

Exclusion dimension is the worst minimum specifying size for total functions outside a finite Boolean concept class.

Version: v1 · 2026-10-31 · History
Domain-specific #: 14494
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Exact Learning, Concept Classes → Computer Science & Software Engineering

Core Idea¶

For finite X and a finite Boolean concept class C with at least one total function outside C, select an outside function f and find the fewest of its labels that leave at most one C member consistent. Exclusion dimension XD(C) is the largest such minimum over the outside functions. “At most one” allows one survivor; it does not require eliminating the entire class.^[1]

How would you explain it like I'm…

No faithful explanation at this level. Two of three generators judged a kid-level version becomes a guessing game of ruling out every option, losing both the worst-case max-over-min structure and the rule that one surviving class member is allowed.

Fewest Looks to Spot the Outsider

Imagine a club of answer sheets, each with yes/no answers to the same questions. Now take an answer sheet that is not in the club. You want to show as few of its answers as possible so that at most one club sheet still matches all of them. Do this for every outside sheet, and the hardest one — the one needing the most answers shown — gives the exclusion dimension. It's okay if one club sheet still matches; you don't have to rule them all out.

Worst-Case Specifying Set Size

In computer science learning theory, take a finite set X and a finite class C of yes/no functions on X, where at least one yes/no function exists outside C. For an outside function f, a specifying restriction picks some points of X and labels them the way f does, so that at most one member of C agrees with all those labels. Find the smallest number of points needed for each outside f. The exclusion dimension XD(C) is the largest of these smallest numbers. Notice the test allows one member of C to survive — it doesn't need to eliminate all of C. If C contains every possible function, there's no outside function, and this version just leaves the dimension undefined.

Let X be a finite domain and C a finite class of Boolean functions on X such that at least one total Boolean function on X lies outside C. For each total f ∉ C, a specifying restriction is a set of coordinates in X, labeled according to f, such that at most one member of C agrees with f on all selected coordinates. Let s(f) be the minimum size of such a set. The exclusion dimension is XD(C) = max over total f ∉ C of s(f) — a worst case over outside functions of a best-case certificate size. The criterion permits zero or one surviving class member; it does not require eliminating every member of C. Under this total-concept convention, the full class containing all Boolean functions on X has no outside function and is excluded from the definition rather than being assigned a value for an empty maximum.

Examples¶

For the four-concept addressing class in Angluin's indexed Figure 7, independent enumeration gives 60 outside functions: 56 require one specifying coordinate and four require two, so XD=2. This global enumeration is derived independently.^[1]

For the derived class C={100,010,001}, outside function 000 requires two zero labels, and the other four outsiders require one. Its XD is 2. This calculation is not a second published example.

Boundaries¶

SXD ranges over inconsistent partial samples, rather than only total outsiders; XD≤SXD when both stated finite quantities are defined. The class C=2^X has no outsider and falls outside this bounded account. A stronger test eliminating every class member can require more labels than the at-most-one convention. The source's complete chapter and empty-case convention remain library follow-ups.

Neighborhood in Abstraction Space¶

Exclusion dimension (total-concept convention) sits in a sparse region of the domain-specific corpus (77^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2835 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-31

References¶

[1] Dana Angluin, “Queries Revisited,” in Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence 2225 (2001), 12–31, DOI 10.1007/3-540-45583-3_3. Publisher abstract: https://link.springer.com/chapter/10.1007/3-540-45583-3_3. Definition and Figure 7 were checked in search-indexed proceedings excerpts; the complete chapter remains a library follow-up. registry ↩a ↩b