Dear Mike, I don't have an answer for this precise question, but, assuming I understand your question, I do have a reference for a general approach that can provide a potential lower bound on the number of such operations. Take a look at "Homological Computations for Term Rewriting Systems" by Philippe Malbos and Samuel Mimram: http://math.univ-lyon1.fr/~malbos/Art/hcTRS.pdf It uses some rather heavyweight abstract homology theory but produces a purely mechanical procedure for obtaining results (though the authors to my knowledge haven't yet implemented a computer program to perform this automatically). Cheers, Gershom On Tue, Sep 26, 2017 at 12:17 AM, Mike Stay <metaweta@gmail.com> 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/ ]
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]