A specific property applicable to subsets of a hom-set in any small category is defined. Subsets with this property are called composition-representative. The notion of composition-representability is motivated both by the representability of a linear functional on an associative algebra, and, by the recognizability of a subset of a monoid. Various characterizations are provided which therefore may be regarded as analogs of certain characterizations for representability and recognizablity. As an application, the special case of an algebraic theory T is considered and simple characterizations for a recognizable forest are given. In particular, it is shown that the composition-representative subsets of the hom-set T(,), the set of all trees, are the recognizable forests and that they, in turn, are characterized by a corresponding finite `syntactic congruence.' Using a decomposition result (proved here), the composition-representative subsets of the hom-set T([m],), (0 \leq m) are shown to be finite unions of m-fold (cartesian) products of recognizable forests.
Keywords: recognizable language, recognizable forest, representative functional, syntactic congruence, algebraic theory, translates
2000 MSC: 18B99, 18C99, 08A62, 08A70
Theory and Applications of Categories,
Vol. 11, 2003,
No. 19, pp 420-437.