Composition-Representative Subsets

Gary Griffing

Theory and applications of categories, Tome 11 (2003), pp. 420-437

Résumé

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.

Détail

Classification : 18B99, 18C99, 08A62, 08A70
Keywords: recognizable language, recognizable forest, representative functional, syntactic congruence, algebraic theory, translates