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¶

Let X be finite and C a finite class of Boolean functions on X, with at least one total Boolean function outside C. For each outside function f, a specifying restriction selects coordinates labeled by f so that at most one member of C agrees with all selected labels. Find the smallest number of coordinates for each f; exclusion dimension XD(C) is the maximum of those minima over total f outside C.^[1]

The test permits zero or one surviving class member. It does not require a restriction that eliminates every member of C. This account excludes a full class with no outside function, rather than assigning a value to its empty maximum.

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.

Structural Signature¶

Sig role-phrases:

Finite domain: X supplies the coordinates that can be labeled.
Concept class: C is a specified finite set of Boolean functions on X.
Total outside concept: The outer range consists of total functions f not in C.
Specifying restriction: A subset of f's coordinate labels leaves at most one C member agreeing with them.
Local minimum: Minimize the number of selected labels for each outside function.
Class maximum: Take the largest local minimum over all outside functions, within the stated nonempty range.^[1]

What It Is Not¶

“At most one” is weaker than “none”: a specifying restriction can leave one candidate. An inconsistent partial sample need not label every coordinate; using all such partial samples as the outer range defines a different parameter. A full class C=2^X has no outside function and is outside this bounded scope.

Scope of Application¶

Both examples use finite Boolean classes. The addressing carrier is reported in an indexed source excerpt; the complete enumerations and the singleton example are independent derivations. The definition alone does not establish an algorithmic query bound or a mind-change guarantee.

Clarity¶

Name the full outside function before selecting a subset of its labels. Count the C concepts agreeing on that subset; then distinguish the minimum for one outsider from the maximum over all outsiders.

Manages Complexity¶

XD summarizes the hardest local specifying requirement by one count. It does not preserve which outside functions attain that count or how many class members survive each restriction.

Abstract Reasoning¶

To establish an exact XD value, one needs an outside function for which no smaller restriction works and an argument that every outsider has a restriction no larger than the claimed bound. These are complementary proof obligations, not competing pressures.

Knowledge Transfer¶

For a new finite class, enumerate or characterize total functions outside it, test restrictions against the same class, minimize for each and establish the maximum. State the at-most-one convention explicitly; replacing it with full elimination changes the question.

Examples¶

Canonical: addressing class¶

Angluin's indexed Figure 7 gives C={001000,010100,100010,110001} on coordinates (x1,x2,y1,y2,y3,y4). An outside function with all y values zero needs two labels to leave at most one class member; the pair x1,x2 is one such restriction.^[1]

Mapped back: The vectors form C; a complete six-bit assignment outside C is the outer object; its selected coordinates are tested for agreement against all four vectors. An independent enumeration of all 64 total functions finds 60 outsiders: 56 have minimum one and four have minimum two. Thus XD(C)=2. The indexed source supplies the carrier and local witness; the complete histogram is independently derived, not attributed to Angluin. The complete chapter was not inspected.

Applied/practice: worked singleton-indicator class¶

Take X={1,2,3} and C={100,010,001}. The outside function 000 needs two zero labels to leave one member of C; a single zero leaves two. The other four outside functions have a one-label specifying restriction.

Mapped back: The three positions are X, the three vectors form C, and the five remaining total functions are the outer range. The independent enumeration gives XD(C)=2. This is a derived mathematical example, not a second published case.

Structural Tensions¶

No independent structural tradeoff is established by these examples. A hard outside witness and an upper bound for all outside functions are complementary requirements for an exact maximum; neither is a cost of choosing the other.

Structural–Framed Character¶

The relation joins a finite concept class, total outsiders, local specifying minima and their maximum. It is mathematically framed: Boolean labels and agreement with a chosen class are constitutive. Researchers choose a class for a learning question, and a value is assessed by mathematical correctness rather than moral worth. The documented context is exact concept-learning research; the addressing carrier comes from an indexed Angluin excerpt, while the global enumerations and singleton example are independent derivations. “Exclusion” and “worst case” travel to other fields, but applying this parameter imports its total-function range, at-most-one test and max–min rule; recognizing a similar term does not. Its character: a finite-class parameter built from local specifying minima and a worst-case maximum.

Structural Core vs. Domain Accent¶

The portable skeleton is a maximum of minimum witness sizes. The named identity adds finite Boolean functions, total outside concepts and agreement with at most one class member. Those mathematical commitments keep it in computational learning theory; any cross-domain Prime for this extremal skeleton would need separate evidence and assessment.

Sample Exclusion Dimension uses inconsistent partial samples as its outer range; every total outsider is one such sample, so XD(C)≤SXD(C) when both stated finite quantities are defined. Teaching Dimension asks about identifying a target inside a class, while Witness Set addresses a declared target and rivals. No typed parent is asserted here.

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

Not to Be Confused With¶

For C={000,111} and outside f=001, a single label leaves one class member, so it specifies f under the at-most-one test. Eliminating both members instead needs a zero and a one label. The stronger full-exclusion certificate is not automatically this XD. Exclusion dimension and sample exclusion dimension use different outer ranges and should not be equated.^[1]

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 ↩c ↩d