Re: Functionally complete/universal basis for graph homomorphisms?

[Patrik Eklund <peklund@cs.umu.se>]

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/ ]