Canonicalizable

Canonicalizable is an adjective used in mathematics and computer science to describe an object that can be transformed into a canonical form under a specified notion of equivalence. A canonical form is a distinguished representative of each equivalence class, chosen according to a fixed convention or algorithm. When an object is canonicalizable, there exists a procedure that assigns to every object in the class a unique form that serves as the standard representative. This concept underpins reliable comparison, classification, and storage, since different presentations of the same underlying object can be reduced to the same canonical form.

In graph theory, a common use is canonical labeling: a graph is canonicalizable if there exists a labeling or encoding that is invariant under graph isomorphism, so isomorphic graphs share the same canonical form. Canonical labeling algorithms are central to isomorphism testing and graph databases, though their practical efficiency varies with graph structure and size.

In linear algebra and symbolic computation, canonical forms provide standard representations of objects. For example, a matrix can be reduced to reduced row echelon form, which serves as a canonical representative of its row space under row operations. In term rewriting, expressions may be converted to a canonical normal form under a confluent and terminating rewrite system, enabling reliable comparison and simplification.

Limitations include that not all classes admit an easily computable or unique canonical form; some procedures are expensive, and different conventions may yield distinct, yet valid, canonical forms. The term canonicalizable emphasizes the existence of a canonicalization map rather than its practicality. Related concepts include canonical form, normalization, and isomorphism invariants.