* Open problems @ 2014-12-12 21:56 Harley Eades III 2014-12-14 18:12 ` Vaughan Pratt 0 siblings, 1 reply; 3+ messages in thread From: Harley Eades III @ 2014-12-12 21:56 UTC (permalink / raw) To: Categories mailing list Hi, everyone. Dee Roytenberg’s email pushed me to write an email I have been wanting to write for a bit. One thing I have been trying to do recently is figure out what the major (and minor) open problems are with respect to applications of category theory to CS. I am very new to this area, and getting an idea of what folks are working on, and what problems people feel are important will help young researchers learns where to concentrate their efforts. I am thinking perhaps we could compile a list of research topics/open problems in this area. I hope some of the experts who read this mailing list would like to add their thoughts. To start us off here are a few that I know of: 1. Homotopy type theory - The study of a new interpretation of intensional type theory based in homotopy theory. This line of research has a lot of interesting problems that need to be solved, and as applications in the design and analysis of functional programming languages, and software verification. 2. Databases - David Spivak has done a lot of great work applying category theory to the design and analysis of databases. I am not sure what the current major open problems are. 3. Security - Dusko Pavlovic currently has a number of projects related to security that use category theory either explicitly or are inspired by categorical concepts. I have read a few of his papers in this line of work, but I am not sure of the current open problems. A list of the papers in this line were posted here awhile ago and can be found here: http://article.gmane.org/gmane.science.mathematics.categories/8068/match= What other topics or specific open problems do others know about? I look forward to hearing about more. Very best regards, Harley Eades [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Open problems 2014-12-12 21:56 Open problems Harley Eades III @ 2014-12-14 18:12 ` Vaughan Pratt 2014-12-14 23:35 ` Michael Barr 0 siblings, 1 reply; 3+ messages in thread From: Vaughan Pratt @ 2014-12-14 18:12 UTC (permalink / raw) To: Categories mailing list On 12/12/2014 1:56 PM, Harley Eades III wrote: > Dee Roytenberg?s email pushed me to write an email I have been wanting to write > for a bit. > > One thing I have been trying to do recently is figure out what the major (and minor) > open problems are with respect to applications of category theory to CS. I am very > new to this area, and getting an idea of what folks are working on, and what problems > people feel are important will help young researchers learns where to concentrate > their efforts. At http://thue.stanford.edu/puzzle.html can be seen a problem about Chu spaces that's been open for close to two decades, and that's been translated during the past three years into Belorussian, Ukrainian, Polish, Slovenian, Czech, French, and Bulgarian by volunteers who apparently found the problem sufficiently interesting to be worth the effort, perhaps motivated by its connection to crossword puzzles. The problem is whether every T1 comonoid in Chu(Set,2) is discrete. This is so for two special cases. 1. Countable comonoids, taking cardinality of a Chu space to be that of its points. 2. Representable comonoids (of any cardinality), in the sense of representation by directed CPOs as per the hierarchy of full embeddings on page 6 of the paper "Comonoids in chu: a large cartesian closed sibling of topological spaces" at http://boole.stanford.edu/pub/comonoids.pdf . T1 DCPOs are of course discrete simply because T1 posets are discrete and the structure of any DCPO is determined by its order via the Scott topology (as distinct from the Alexandroff topology, though they coincide in the T1 case). The problem remains open for uncountable comonoids not representable as DCPOs. The provenance of Chu spaces is arguably category-theoretic, the enriched case Chu(V,k) having been invented by Mike Barr and first studied in detail in the late 1970s by his masters student Po-Hsiang (Peter) Chu. As a computer scientist my own application for the ordinary or set-enriched case Chu(Set,K) has been to concurrency theory, starting around 1991 shortly after Lafont and Streicher proposed that case (under the rubric of "games") as a very nice model of Girard's linear logic. In the latter application the image of Girard's exponential construct !A is naturally modeled as the cartesian closed full subcategory of that of Chu spaces consisting of comonoids. In any symmetric monoidal category with tensor product A@B and unit I, a comonoid is a structure with a comultiplication d: A --> A@A and a counit e: A --> I. A comonoid homomorphism is any morphism preserving that structure. In Set, taking tensor @ to be cartesian product x and I to be 1 makes every set a comonoid by taking d to be the diagonal and e the unique map to 1, and those are the only comonoids in Set. Every function is thereby a comonoid homomorphism. The standard tensor @ of Chu(V,k) is given by A@B ~ (A --o B')' ~ (B --o A')' (1) where A' is the dual or transpose of A and --o is the external hom of Chu(V,k) internalized by suitably "chupologizing" it. The unit is that of V likewise chupologized. For Chu(Set,K), a Chu space A = (A,X) can be understood as a space A whose points are positions for letters, and (the points of) its dual A' as a set (so these are actually *extensional* Chu spaces) X of words of length A over the alphabet K, with each word formed by filling each position with a letter from K, i.e. functions A --> K, making X a subset of K^A. Duality then requires that A' also be extensional ("little Chu" or chu(Set,K) in Barr's terminology). From that perspective (A@B)' can be visualized as the space of all AxB crosswords that can be formed by taking the across words from B' (given by a map from A to B') and the down words from A' (given by a map from B to A'), as per the two isomorphisms in (1) above, the second of which amounts to an adjointness condition on the two maps. The comonoids in Chu(Set,K) are those Chu spaces A for which every crossword in (A@A)' has for its main diagonal a word in A', and such that A' includes all one-letter (constant) words aaa...aa, bbb...bb, .... The T1 comonoids can be defined as those comonoids A such that every word of length A begun by writing down two of its letters (at any two positions) can be completed to a word in A'. For any alphabet K, the unit makes this automatic when the two letters are the same, so for the alphabet {0,1} T1 reduces to: at any two given positions both ...0...1... and ...1...0... can be completed to a word. With the interpretation of words over {0,1} as open sets this is recognizable as one definition of a T1 topological space (the other topological definition of T1, every singleton closed, does not give the chupological definition.) So, is every T1 comonoid in Chu(Set,2) discrete? Vaughan Pratt [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Open problems 2014-12-14 18:12 ` Vaughan Pratt @ 2014-12-14 23:35 ` Michael Barr 0 siblings, 0 replies; 3+ messages in thread From: Michael Barr @ 2014-12-14 23:35 UTC (permalink / raw) To: Vaughan Pratt; +Cc: Categories mailing list I just wanted to add to what Vaughan said about the provenance of Chu spaces. When I started working on duality in 1975 at the ETH, one prominent example was topologicalvector spaces. So I looked at several books on the subject, one by Grothendieck. They all mentioned a construction of pairs (V,V') of spaces equipped with a bilinear map V x V' --> K (the ground field). This simple example, with its obvious duality led pretty directly to the Chu construction. It was amazing that it turned to not only give and obvious duality but also a natural *-autonomous structure (that Peter Chu studied). At some point I decided to track down the source. It certainly had an air of Grothendieck about it, but no, it turned out to go back to George Mackey's thesis, published in TAMS around 1944, I think. He looked at pairs (V,V') as above and assumed they were extensional but not necessarily separated. He was aware of the duality in the separated extensional case, but didn't pursue it in any detail. So what was the motivation. I can guess that he was thinking that V', as a space of functionals on V, coud replace the topology. Just as in a locally compact abelian group, you could recover the topology if you knew which characters were "admissible". I once wrote him to ask if that was his original motivation, but he died within the ensuing year, not having answered me. But truly, it goes back to Mackey. Michael ----- Original Message ----- From: "Vaughan Pratt" <pratt@cs.stanford.edu> To: "Categories mailing list" <categories@mta.ca> Sent: Sunday, 14 December, 2014 1:12:58 PM Subject: categories: Re: Open problems On 12/12/2014 1:56 PM, Harley Eades III wrote: > Dee Roytenberg?s email pushed me to write an email I have been wanting to write > for a bit. > > One thing I have been trying to do recently is figure out what the major (and minor) > open problems are with respect to applications of category theory to CS. I am very > new to this area, and getting an idea of what folks are working on, and what problems > people feel are important will help young researchers learns where to concentrate > their efforts. At http://thue.stanford.edu/puzzle.html can be seen a problem about Chu spaces that's been open for close to two decades, and that's been translated during the past three years into Belorussian, Ukrainian, Polish, Slovenian, Czech, French, and Bulgarian by volunteers who apparently found the problem sufficiently interesting to be worth the effort, perhaps motivated by its connection to crossword puzzles. The problem is whether every T1 comonoid in Chu(Set,2) is discrete. This is so for two special cases. 1. Countable comonoids, taking cardinality of a Chu space to be that of its points. 2. Representable comonoids (of any cardinality), in the sense of representation by directed CPOs as per the hierarchy of full embeddings on page 6 of the paper "Comonoids in chu: a large cartesian closed sibling of topological spaces" at http://boole.stanford.edu/pub/comonoids.pdf . T1 DCPOs are of course discrete simply because T1 posets are discrete and the structure of any DCPO is determined by its order via the Scott topology (as distinct from the Alexandroff topology, though they coincide in the T1 case). The problem remains open for uncountable comonoids not representable as DCPOs. ... [For admin and other information see: http://www.mta.ca/~cat-dist/ ] ^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2014-12-14 23:35 UTC | newest] Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2014-12-12 21:56 Open problems Harley Eades III 2014-12-14 18:12 ` Vaughan Pratt 2014-12-14 23:35 ` Michael Barr
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).