User supercooldave - MathOverflow

180˚ vs 360˚ Twists in String Diagrams for Ribbon Categories

2010-06-14T17:31:48Z

Ribbon categories are braided monoidal categories with a twist or balance, $\theta_B:B\to B$, which is a natural transformation from the identity functor to itself. In the string diagram calculus for ribbon categories, the ribbon is represented as a 360˚ twist in a ribbon (op. cit.). (See for example Street's Quantum Groups or Kassel's Quantum Groups for details.)

My questions are:

Is there work describing what happens if we consider a 180˚ twist?
If not, what goes wrong if we take this half twist one of the operations of interest on ribbons?
How are ribbons with a 180˚ twist axiomatised? What if loops are possible and we have twisted tangles? (I believe that Traced Monoidal Categories by Verity, Street and Joyal doesn't cover this case.)

Torsors for monoids

2010-05-25T10:33:02Z

Torsors are defined as a special kind of group action. I am wondering whether the analogous notion exists for monoid actions. Some references would be helpful.

In general I'm interesting in the notion of 'subtraction/division' induced by having a torsor. My application is in computer science. A monoid is used to capture modifications to a computer program and the monoid action corresponds to performing the modification on the program. If I have a torsor-like entity, I can take two software entities and produce the modification required to convert one into the other.

The answer is that any such monoid will automatically be a group. In my application, it seems that I will only get close to the notion of torsor if my modifications have inverses, which they do not.

Lattice of subcategories: subobject classifier in Cat

2010-06-19T12:32:33Z

Two short questions:

Is there any work classifying the lattice of subcategories of an arbitrary (sufficiently small) category $\mathcal{C}$, similar to the way that the set of subsets of set $\mathcal{S}$ is isomorphic to the functions $\mathcal{S}\to\mathbf{2}$, where $\mathbf{2}$ is a two point set?
Is there standard notation denoting the lattice of subcategories of some category?

The definitions found in nLab are phrased in terms of functors going into $\mathcal{C}$, but the definition for sets talks about functions out of the set $\mathcal{S}$. Why are things done differently? That is, rather than characterising subcategories in terms of functors into $\mathcal{C}$, why not characterise them in terms of functors out of $\mathcal{C}$? Something like:

The lattice of subcategories of $\mathcal{C}$ is isomorphic to the functor category $\mathcal{SO}^\mathcal{C}$, for some "subobject classifier" $\mathcal{SO}$.

Answer by supercooldave for Should I check with collaborators before presenting unpublished material?

2010-09-19T15:53:53Z

Check with your collaborators on this one. Opinions vary.

Maximal subcoalgebras of an $F+1$-coalgebra corresponding to an $F$-coalgebra

2010-09-08T08:14:04Z

This context of this question is Rutten's Universal Coalgebra, used for modelling systems. I'm interested in finding a description of a functor between different types of coalgebras corresponding to finding a certain subcoalgebra.

An $F+1$-coalgebra $\langle S,\alpha:S\to F(S)+1\rangle$ can be thought of as a system whose transition shape is given by functor F plus the possibility of an error/termination, given by the +1. Assume that $F$ is a so-called Kripke polynomial functor: $F::=Id ~|~ B ~|~ F+F ~|~ F\times F ~|~ F^ A ~|~ \mathcal{P}_\omega F$, thus it preserves pullbacks.

A subcoalgebra of $\langle S,\alpha:S\to F(S)+1\rangle$ is coalgebra $\langle S',\alpha':S'\to F(S')+1\rangle$, where $S'\subseteq S$ and $\alpha'$ is $\alpha'$ restricted to $S'$, such that its range falls within $F(S')+1$.

I want to find the maximal subcoalgebra of this coalgebra which corresponds to an $F$-coalgebra. In terms of my application, this means I'm looking for the subset of states $S'\subseteq S$ that do not lead to the error state.

Clearly, I can take the pullback of the functions $\alpha:S\to F(S)+1$ and $inl:F(S)\to F(S)+1$ to get a set $S_0\subseteq S$ which do not lead to an error in the first step. Iterating this process for functors $F^i+1$ seems to lead to progressively smaller subsets $S_i$ of $S$ each avoiding the error state for $i$ steps. What I'm lacking is a coherent description of the process.

Is whether there is a more universal description of this construction in terms of limits or colimits, or at least, some known approaches to the problem?

I asked this question on the computer science theory overflow (here), but am re-asking it here as I received no feedback.

Answer by supercooldave for Enumerating a type of two-color cycle

2010-07-08T20:21:28Z

If your graph is $G=(V,E)$ and $B\subseteq E$ are the blue edges, then you can run an appropriate cycle enumeration algorithm on $G-(B\setminus{ b_i })$ for each $b_i\in B$. This ensures that at most one blue edge occurs in the graph. Perhaps the selected algorithm can be adapted to start with the edge $b_i$, ensuring that only graphs with exactly one blue edge are enumerated.

Google reveals many such algorithms. I'm not sure which one suits your needs. No efficient algorithms exist, as along the way you would find Hamiltonian paths, which is an NP-complete problem.

Answer by supercooldave for Is there an explicit construction of a free coalgebra?

2010-07-08T20:25:45Z

One place to really see the difference is by considering Universal Coalgebra (also known as F-coalgebras) (in contrast to Universal Algebra). The structures considered by Universal Coalgebra are typically infinite, whereas those considered by Universal Algebra are finite. This is taken from a computer science angle. Universal Algebra is about data types and Universal Coalgebra is about systems. Initial algebras are correspond to least fixed points, whereas final coalgebras correspond to greatest fixed points.

A free coalgebra (in this setting) corresponds to the final coalgebra of some functor (although one would call it a cofree coalgebra). A general introduction to the kinds of coalgebras I'm talking about is Introduction to Coalgebra by Jiri Adamek. This paper provides a way of constructing the final coalgebras for a certain class of functors.

Answer by supercooldave for Working in groups vs. alone: present vs. past

2010-07-08T17:11:22Z

From my (CS) perspective there are at least 2 forces which encourage working in pairs/groups. Teaching limits ones time and one has students, so one works with students. Secondly, funding schemes often encourages collaboration between various parties (I'm thinking large European projects here). Even local (Belgian) funding schemes favour consortia to individuals.

Answer by supercooldave for When did the career of 1 as a prime number begin and when did it end?

2010-07-06T08:29:39Z

Wikipedia has lots of information on this topic. For example, "Henri Lebesgue is said to be the last professional mathematician to call 1 prime."

Answer by supercooldave for Building optimal rewriting rules.

2010-07-05T08:20:02Z

The trie data structure seems to be precisely the structure you are looking for. It is more efficient in terms of both space and time than providing a table of rewrite rules. There are quite a few references on the wiki page linked above, including volume 3 of Knuth's The Art of Computer Programming. More recent and more efficient variants may exist.

Consider the following example trie. Rather than being a collection of key-value pairs, keys are made up of labels on the paths of the tree, and the corresponding values are associated with a leaf (the numbers in the example). For example, in the figure key to maps to value 7 and key ted maps to value 4.

Answer by supercooldave for Solving a system of linear inequalities -- what is the dimension of the solution set?

2010-07-04T02:39:43Z

These notes give you an answer to question 2, computing the dimension.

Answer by supercooldave for Predicting if something is a code

2010-07-02T15:30:12Z

Interestingly enough, there was an article about this exact topic (more or less) on slashdot recently. Here's a link to the slashdot story, the scientific article it refers to, and MIT news article about the topic.

The abstract of the scientific article is:

In this paper we propose a method for the automatic decipherment of lost languages. Given a non-parallel corpus in a known related language, our model produces both alphabetic mappings and translations of words into their corresponding cognates. We employ a non-arametric Bayesian framework to simultaneously capture both low-level character mappings and high-level morphemic correspondences. This formulation enables us to encode some of the linguistic intuitions that have guided human decipherers. When applied to the ancient Semitic language Ugaritic, the model correctly maps 29 of 30 letters to their Hebrew counterparts, and deduces the correct Hebrew cognate for 60% of the Ugaritic words which have cognates in Hebrew.

Of course, this assumes that you know what language your unknown language is related to. If it is made up, it's probably worth knowing what languages its author knows and/or speaks.

The tool is probably available from the authors. It does not appear on Benjamin Snyder's web page, though other tools do.

On the other hand, if the text is cryptographically encoded (well) then you'll have a hard job of decrypting it. The field of cryptanalysis or 'code-breaking' deals with that topic.

Answer by supercooldave for question on book

2010-07-02T08:02:02Z

That depends upon what you are looking for. If you want to learn about techniques used by hackers to break into systems (and thereby improve your programming to stop those hackers), then this book is no good for you. On the other hand, if you want to learn about low level bit-flipping tricks, then this could be of interest. It is well written and tells a good story. Perhaps not the story you expect.

Answer by supercooldave for Software for Tree-Decompositions

2010-07-01T14:44:32Z

Some tree decomposition software is given here: http://hein.roehrig.name/dipl/. I haven't used it so can say nothing about it's quality.

Answer by supercooldave for reducing a theorem to set theory using first order logic

2010-07-01T13:33:26Z

Naive Set Theory by Paul Halmos could help provide a naive solution.

$\omega$-monoids

2010-06-30T18:28:11Z

Does the notion of $\omega$-monoid exist, analogous to the notions of $\omega$-groupoid and $\omega$-category? If so, some references would be appreciated.

This is an attempted rephrasing of question: http://mathoverflow.net/questions/24723/chain-hierarchy-of-monoids. My application domain is reasoning about modifiers of modifiers in software product line engineering, thus lacking established mathematical background. I find it easier to adapt existing results, even if the application domain is significantly different, so any help would be appreciated.

Answer by supercooldave for Ways to Synthesize Topics in Linear Algebra

2010-06-30T07:45:49Z

Computer graphics relies heavily on linear algebra.

Answer by supercooldave for motivation for compactness

2010-06-30T07:11:00Z

You might want to look at the answers for this question: http://mathoverflow.net/questions/27660/applications-of-compactness

Answer by supercooldave for What is the shortest program for which halting is unknown?

2010-06-29T18:44:41Z

It's quite possible that the Collatz conjecture provides an answer. Apply this function repeatedly. The conjecture is that this process will eventually reach the number 1, regardless of which positive integer is chosen initially.

Not sure how many lines of code this would be. Probably 2 in Haskell.

Answer by supercooldave for [solved] sequent calculus as programming language

2010-06-26T09:21:58Z

To answer your question about representing sequent calculi proofs in a computer, you need to look at the Curry-Howard isomorphism. Formula in a sequent are annotated with terms and the sequent calculus for intuitionistic logic resembles the type rules for the typed lambda calculus. If you want to manipulate this, then you need to record the assumptions (left-hand side of the turnstyle $\vdash$), which corresponds to recording the types of free variables. Then the right-hand side is a $\lambda$-term (describing the proof) and its type (the formula proven).

There's a vast amount of literature about this. The reference you probably want is A $\lambda$-calculus structure isomorphic to sequent calculus structure by Hugo Herbelin. The book by Morten Heine B. Sørensen and Pawel Urzyczyn is an extensive study of the topic. This kind of encoding is at the heart of proof assistants such as Coq.

Other possible correspondences include Sequent calculus ~ Abstract Machine. See Sequent calculi and abstract machines by Zena M. Ariola, Aaron Bohannon, Amr Sabry, ACM Transactions on Programming Languages and Systems (TOPLAS) Volume 31 , Issue 4 (May 2009). Or more generally, and perhaps more loosely, Sequent calculus ~ Operational Semantics. You also have proofs ~ processes, as explored by Abramsky and Saraswat, the latter in the context of concurrent constraint programming.

Answer by supercooldave for Characterizing visual proofs

2010-06-25T07:54:05Z

This may not directly answer to your question. A different MO question about Resources for graphical languages accumulated quite a few references for proofs based on string diagrams. These have precise semantics generally in terms of monoidal categories and can be used to prove results about quantum groups among other things.

Answer by supercooldave for 180˚ vs 360˚ Twists in String Diagrams for Ribbon Categories

2010-06-23T17:14:16Z

I stumbled across Autonomous categories in which $A \cong A^∗$ by Peter Selinger. It states that the graphical representation of the self-duality $h_A:A\to A^*$ is represented by a half-twist of a ribbon. A coherence result is conjectured, but not proven (of course).

Answer by supercooldave for Learning Roadmap for Software Engineer

2010-06-21T06:53:29Z

If you want to learn some of the beautiful things related to computer science, then I recommend the following topics and/or books:

Logic: many introductory books exist. Something like Mathematical Logic for Computer Science by Mordechai Ben-Ari focuses on CS-related topics. Learning about modal logic (eg Modal Logic by Patrick Blackburn, Maarten de Rijke, and Yde Venema, though not as a beginning text) is useful for other fields of computer science, including AI and verification and model checking.
Formal Languages: Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Elements of the Theory of Computation Harry R. Lewis, Christos H. Papadimitriou, and Computational Complexity by Christos H. Papadimitriou.
Programming Language Theory and Type Systems: Types and Programming Languages by BC Pierce
Model Checking: Model Checking by EM Clarke and Principles of Model Checking by Christel Baier and Joost-Pieter Katoen
Concurrency Theory and Process Algebra: firstly Communicating and Mobile Systems: The Pi Calculus by Robin Milner, then The Pi-Calculus: A Theory of Mobile Processes by Davide Sangiorgi and David Walker. Other possibilities include Communicating Sequential Processes by C.A.R. Hoare and Introduction to Process Algebra by Wan Fokkink. Modelling Distributed Systems by Wan Fokkink models systems using process algebra so they can be checked for correctness using model checking.
Verification: Verification of Sequential and Concurrent Programs by Krzysztof R. Apt, Frank S. Boer, and Ernst-Rüdiger Olderog.
Category Theory: Basic Category Theory for Computer Scientists by Benjamin C. Pierce or Categories and Computer Science by R. F. C. Walters.
Graph Theory: Graph Theory: An Advanced Course by Adrian Bondy and U.S.R. Murty
Lattice Theory: Introduction to Lattices and Order by B. A. Davey and H. A. Priestley
Semantics, Domain Theory, Abstract Interpretation: Semantics with Applications: An Appetizer by Hanne Riis Nielson and Flemming Nielson provides a rudimentary introduction, also linking denotational semantics to program analysis via abstract interpretation. Plotkin's notes on Domain Theory are excellent, more comprehensive, and more theoretically bent. Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin applies these ideas to program analysis.

Still missing: field theory (for cryptography), combinatorics, and undoubtedly other topics.

Answer by supercooldave for Mathematics and autodidactism

2010-06-17T08:23:27Z

I find myself attracted to Springer's Graduate Texts in Mathematics and buy too many of them. Then they sit somewhere at home so that I can pick them up and read them whenever I get a chance. These are essentially filling in background information that I don't have or don't remember (I'm as CS prof with a rusty major in mathematics). If I find a topic that particularly interests me, I chase it down using http://arxiv.org/ and plain old google. This is more or less my forward approach to learning new things. I also have a backwards approach, consisting of finding a paper that appeals to me and then trying to fill in the backwards knowledge required to understand it. Of course, without doing the exercises or applying the stuff I read, my level of understanding is not as deep as it could be.

Answer by supercooldave for Good quality data/packages for statistical/structure analysis of words in the English language

2010-06-16T16:51:18Z

The Natural Language Toolkit for Python seems to pretty good.

Answer by supercooldave for Quantum channels as categories: question 1.

2010-06-14T16:05:31Z

Plenty of recent work addresses encoding quantum protocols (and hence quantum channels, I guess) using category theory. Check out the work of Bob Coecke and any one related to him. A good starting point is A categorical semantics of quantum protocols by Samson Abramsky and Bob Coecke. It has many of the ingredients you are probably looking for. Or perhaps Kindergarten Quantum Mechanics also by Bob Coecke. There's also Dagger Categories by Peter Selinger, capturing the underlying categorical structures: Dagger compact closed categories and completely positive maps.

Answer by supercooldave for Relating Category Theory to Programming Language Theory

2010-06-10T15:01:47Z

A lot of work has been done in this area. As mentioned above, there is an essential correspondence between the $\lambda$-calculus and Closed Cartesian Categories. Moggi's seminal work Notions of Computations and Monads developed a unified way of treating many computational effects. This of course inspired Haskell's current approach to dealing with IO, State, Concurrency and so forth. The dual approach, Comonadic Notions of Computation by Tarmo Uustalu and Varmo Vene, captures a other notions, such as stream based computation. Classes and object-oriented languages can be modelled using coalgebra (also mentioned above). A general reference to the coalgebraic approach is Universal Coalgebra: A Theory of Systems by Jan Rutten, and articles showing how to apply it to object-oriented languages include Reasoning about Classes in Object-Oriented Languages: Logical Models and Tools and Coalgebraic Reasoning about Classes in Object-Oriented Languages by Bart Jacobs and colleagues. Although these are aimed at reasoning about programs, they do give semantics for the relevant programming languages along the way.

Answer by supercooldave for Formulas for the liar paradox

2010-06-10T12:30:04Z

There is an extensive discussion of this issue in Vicious Circles by Jon Barwise and Lawrence S. Moss.

Chain/Hierarchy of Monoids

2010-05-15T10:45:40Z

Let's assume that we have the following collection of structures:

Some space $P$.
Monoids $(M_{i+1},\circ_{i+1})$, and
Actions $\bullet_{i+1}:M_{i+1}\times M_i\to M_i$, for $i\ge 0$
And $\bullet_{0}:M_0\times P\to P$.

satisfying

($\bullet$ is a monoid action): $(m\circ_{i+1}m')\bullet_{i+1} n = m\bullet_{i+1}(m'\bullet_{i+1} n)$ and
($m\bullet-$ is a homomorphism): $m\bullet_{i+1}(n\circ_{i}n')=(m\bullet_{i+1}n)\circ_{i} (m\bullet_{i+1} n')$.

In my application, $P$ corresponds to computer programs. $M_0$ are modifications to elements of $P$. If you wish, you can think of $M_0$ as some kind of structured patch. Then each $M_{i+1}$ are higher-order modifications of the modifications in $M_i$.

The hierarchy isn't necessarily infinite.

I'm curious to know what kind of structure I'm looking at. I originally felt that I was defining some kind of $n$-category with one object at each level, namely the endomorphism, but one reader commented that my structures were too floppy, meaning that there were not enough equations.

It seems that the structure I'm interested in is related to the automorphism tower for groups, except that I'm interest in monoids, and rather than automorphism, I'm only concerned with endomorphism, and I am working indirectly through monoid actions, rather than having the endomorphism apply to the morphisms at the level below.

Have I defined a known structure?

What natural equations would one expect to link the various levels with each other?

What additional properties does it satisfy? What reasonable properties should it satisfy?

Are there conditions under which it becomes degenerate?

Any pointers would be appreciated.

Uses of bisimulation outside of computer science.

2010-05-27T18:25:04Z

Bisimulation is one of the most important ideas of theoretical computer science. I was wondering whether bisimilarity is used/known outside of computer science/modal logic? I am aware that it corresponds more or less to back and forth techniques from model theory, but are there any other areas where it finds application?

For those not in the know, here is a definition:

Given a labelled transition system $(S,\Lambda,\to)$, a bisimulation relation is a binary relation $R$ over $S$ (that is, $R\subseteq S\times S$) such that for all pairs of elements $p,q\in S$ with $(p,q)\in R$, and for all $\alpha\in\Lambda$, we have

$p\to^\alpha p'$ implies that there is a $q'$ such that $q\to^\alpha q'$ and $(p',q')\in R$, and

symmetrically for $q$, namely, $q\to^\alpha q'$ implies that there is a $p'$ such that $p\to^\alpha p'$ and $(p',q')\in R$.

Applications collected thus far in answers include:

process equivalence in concurrency theory
model logic: expressiveness characterisations, modal correspondence theory
coinduction, for example in Game Theory
non-well founded set theory
algebraic set theory
geometric topology

Comment by supercooldave

2012-05-16T06:49:55Z

Appears also here: cstheory.stackexchange.com/questions/11414/…

Comment by supercooldave

2011-03-08T09:21:09Z

Cross posted on CSTheory stackexchange: cstheory.stackexchange.com/questions/5346/…

Comment by supercooldave

2010-11-24T08:38:38Z

One thing I find is that mathematical training helps me conceptualise problems better. My girlfriend had no such training. She's a programmer, but it is clear to see the huge difference in the way we conceptualise problems. This is not to say that my conceptualisations are better. They do tend to be more abstract and not get caught up in unnecessary details.

Comment by supercooldave

2010-10-05T15:15:16Z

Different versions of Coq differ in the libraries of theories and tactics and other, often superficial, features. The core logic remains the same.

Comment by supercooldave

2010-09-27T06:48:56Z

A more interesting question is "what is the transitive closure of a hypergraph?"

Comment by supercooldave

2010-09-14T04:49:33Z

That seems to be just what the doctor ordered.

Comment by supercooldave

2010-07-12T13:45:11Z

Vote to close. 3rd junk post by this member.

Comment by supercooldave

2010-07-12T09:50:03Z

And at least one book: amazon.com/Math-Music-Trudi-Hammel-Garland/dp/…. In fact, there's a whole web site devoted to finding such connections: www.google.com

Comment by supercooldave

2010-07-12T09:46:27Z

This is not at all my field, but googling "Finite Element Method" might help get you on the right track, in the absence of better answers.

Comment by supercooldave

2010-07-11T18:14:12Z

The dictionary. Contact certainly does. Perhaps providing some context might help make a better question.

Comment by supercooldave

2010-07-11T13:30:29Z

So: $4=2.2 \to 22 =2.11\to 211$ prime!! Have you written a program to do this? Does the chosen base matter?

Comment by supercooldave

2010-07-10T13:19:46Z

I agree with Mariano.

Comment by supercooldave

2010-07-08T13:51:53Z

Indeed. $r\cos(360x/n)$ is $r*cos(360 * x/ n)$.

Comment by supercooldave

2010-07-08T12:15:38Z

en.wikipedia.org/wiki/Trigonometry

Comment by supercooldave

2010-07-08T11:03:53Z

Looks like nonsense.