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*([1],[0]), 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]),
(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.

http://www.tac.mta.ca/tac/volumes/11/19/11-19.dvi

http://www.tac.mta.ca/tac/volumes/11/19/11-19.ps

http://www.tac.mta.ca/tac/volumes/11/19/11-19.pdf

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/11/19/11-19.dvi

ftp://ftp.tac.mta.ca/pub/tac/html/volumes/11/19/11-19.ps