Clustering, Lattices & Formal Sets

← Back to Domain-Specific Families

Abstractions about complete-linkage clustering, lattice problems, signed sets, algebraic extremal methods, and formal-language complexity.

5 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Complete-linkage clustering — Build an agglomerative hierarchy by defining intercluster distance as the farthest cross-cluster pair and repeatedly merging the pair with the smallest such maximum.
• Flag algebra — Razborov's algebraic framework for asymptotic densities of partially labeled finite structures, turning extremal combinatorics inequalities into positive semidefinite and semidefinite-programming certificates.
• Generalized star-height problem — The open formal-language question of whether every regular language has a generalized regular expression whose Kleene-star nesting depth is bounded by a universal constant when complement is allowed.
• Lattice problem — A computational search or approximation problem over integer lattices, such as finding unusually short, close or independent lattice vectors.
• Signed set — A set equipped with a positive-or-negative label on every element, equivalently an ordered pair of disjoint positive and negative subsets or a map to a two-element sign set.