From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/9363 Path: news.gmane.org!.POSTED!not-for-mail From: Patrik Eklund Newsgroups: gmane.science.mathematics.categories Subject: Re: Functionally complete/universal basis for graph homomorphisms? Date: Wed, 27 Sep 2017 07:28:55 +0300 Message-ID: References: Reply-To: Patrik Eklund NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit X-Trace: blaine.gmane.org 1506558165 2653 195.159.176.226 (28 Sep 2017 00:22:45 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 28 Sep 2017 00:22:45 +0000 (UTC) Cc: categories To: Mike Stay Original-X-From: majordomo@mlist.mta.ca Thu Sep 28 02:22:41 2017 Return-path: Envelope-to: gsmc-categories@m.gmane.org Original-Received: from smtp2.mta.ca ([198.164.44.40]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dxMbB-0000Jr-3y for gsmc-categories@m.gmane.org; Thu, 28 Sep 2017 02:22:41 +0200 Original-Received: from mlist.mta.ca ([138.73.1.63]:45927) by smtp2.mta.ca with esmtp (Exim 4.80) (envelope-from ) id 1dxMcI-0001U9-BP; Wed, 27 Sep 2017 21:23:50 -0300 Original-Received: from majordomo by mlist.mta.ca with local (Exim 4.71) (envelope-from ) id 1dxMaS-0003fF-Gi for categories-list@mlist.mta.ca; Wed, 27 Sep 2017 21:21:56 -0300 In-Reply-To: Precedence: bulk Xref: news.gmane.org gmane.science.mathematics.categories:9363 Archived-At: 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/ ]