I haven't looked at it in this way, but we have been looking into the notion of 'arity', when we deal with extensions to many-valued terms. In general, the category of signatures is tricky. Just mapping operators to operators, and respecting arities, is very shallow. That category being tricky is also seen in Goguen's institutions and Meseguer's entailment systems, where Sign is a black box. Benabou's definition is that shallow thing, and so is efforts to categorize trees as part of tree automata. Categorizing automata is hard enough as we see through Budach, Ehrig, Goguen, Manes, Adamek, etc. Note also that the stroke is a binary/boolean operator, so we are on the borderline between terms and sentences. Note also that extending 2 to a quantale, and even non-commutative ones, adds complexity, and involves questions related to your but different in their objectives. The category of graphs may also need revision. Defining a graph as mapping an edge to a pair of vertices hides arities and invites to defining paths. Nevertheless, vertices in trees are seen as operator names. Sorry for not precisely answering your question, and for being rather general and intuitive in my reflections, but they are related to our ongoing work on the foundations of many-valuedness. Our take is that unless we have something more innovative on Sign, we are unable to proceed with sentence functors (not extendable to monads!), and so towards more ingredients in logic machineries, separated "latively", as I have written before. Patrik On 2017-09-26 07:17, Mike Stay wrote:
The Sheffer stroke / NAND gate suffices to implement any function from 2^n -> 2. I'm looking for a similar universal basis for graph homomorphisms from Omega^n -> Omega, where Omega is the subgraph classifier with two vertices t, f and five edges
in:t->t, out1:t->t, out2:t->f, out3:f->t, out4:f->f.
There's obviously a finite set of operations that covers all graph homomorphisms from Omega^n to Omega, because the set of all operations of that form is finite. But how small can that set be? I'd be satisfied with a formula parametric in n, but surprised if it actually depends on n; I'd expect it to be a finite set of binary operations.
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]