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