most recent 30 from http://mathoverflow.net 2013-05-23T21:07:53Z http://mathoverflow.net/feeds/user/12823 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/89142/are-context-free-languages-with-context-free-complements-necessarily-deterministi Nick Loughlin 2012-02-21T21:46:23Z 2012-02-22T21:55:46Z

<p>Let $L \subseteq A^\star$ be a formal language over $A$ generated by a context-free grammar, and $L' = A^\star - L$ be the relative complement in $A^\star$.</p> <p>If $L$ and $L'$ are both context-free, are they necessarily deterministic context-free?</p>

http://mathoverflow.net/questions/54759/what-does-rngop-look-like Nick Loughlin 2011-02-08T13:32:29Z 2011-07-23T05:00:04Z

<p>There are several well-known dualization results in category theory, i.e. that such-and-such a well-known category D is isomorphic to the opposite C^{op}. Does anyone know of such a result concerning what the opposite category to Rng, rings (*-monoid on +-group) with their homomorphisms, looks like?</p> <p>I ask (naively I should add) because I'm curious if there's a natural "algebraic" structure on homology dual to that of the ring-structure of cohomology.</p>

http://mathoverflow.net/questions/55200/good-programs-for-drawing-graphs-directed-weighted-graphs/55202#55202 Nick Loughlin 2011-02-12T13:29:23Z 2011-02-12T13:29:23Z

<p>Try Graphviz - it's open source and quite flexible as far as usage is concerned.</p> <p><a href="http://www.graphviz.org/" rel="nofollow">http://www.graphviz.org/</a></p> <p>It's good at automatic layouts etc, where for example Maple would make a mess of things.</p>

http://mathoverflow.net/questions/55027/triangulating-hypercubes Nick Loughlin 2011-02-10T12:58:43Z 2011-02-10T16:12:03Z

<p><strong>Motivation:</strong> I'm working on a computational problem at the moment, and have some very good routines for natively working with simplicial complexes and calculating homology, but the structures I'm dealing with arise naturally as cubical complexes.</p> <p><strong>Problem:</strong> Is there an efficient way to triangulate the n-cube, i.e. calculate a (relatively) small list of n-simplices on the same vertices as the cube, and which define a simplicial complex spanning the cube?</p> <p>I've done some reference-chasing and there seems to be no decently-sharp estimate (as an upper or lower bound) for the asymptotic complexity of the problem, although the best upper-bounds I'm aware of (for the size of the smallest solution-set) seem to indicate something exponentially smaller than factorial (<a href="http://www.springerlink.com/content/x6127672610622g2/" rel="nofollow">see Haiman, 91</a>). This paper also exhibits a lower bound, given below</p> <p><code>$\frac{2^n\,n!}{(n+1)^{{}^{(n+1)/2}}}$</code></p> <p><a href="http://arxiv.org/abs/math/0204157" rel="nofollow">Orden and Santos</a> improved the upper bound somewhat, by reducing the base of the exponential.</p>

http://mathoverflow.net/questions/89142/are-context-free-languages-with-context-free-complements-necessarily-deterministi Nick Loughlin 2012-02-29T16:42:18Z 2012-02-29T16:42:18Z

Yes, it seems from discussion I'd put a typo in my original formulation; thanks - it completely passed me by. It was probably an artefact from my rewriting the question first time around.

http://mathoverflow.net/questions/89142/are-context-free-languages-with-context-free-complements-necessarily-deterministi Nick Loughlin 2012-02-21T22:50:27Z 2012-02-21T22:50:27Z

Perhaps you missed my last edit - I removed that part of the question. To clarify, my original question contained the above, as well as a &quot;dual&quot; question concerning the closure of the set of context-free languages w.r.t. finitary Boolean operations. In this question, I'm not looking for the closure of the class of context-free languages with respect to complements, but merely to know if the proper sub-class of CF languages which have CF complements is in fact the class DCF of deterministic CF languages.

http://mathoverflow.net/questions/62334/probability-of-having-a-bounded-ratio-of-two-types-of-balls-in-each-of-s-bins-a Nick Loughlin 2011-04-19T21:36:13Z 2011-04-19T21:36:13Z

Perhaps you mean to ask the probability of there being two fixed values each in $[0,1]$ such that the ratio <i>in each bin</i> of blue balls to red balls is bounded between them? My apologies, but the wording of your question seems ambiguous to me, or at least unclear.

http://mathoverflow.net/questions/56677/what-notions-are-used-but-not-clearly-defined-in-modern-mathematics/56722#56722 Nick Loughlin 2011-03-01T15:45:15Z 2011-03-01T15:45:15Z

@David: There's a short survey here if you're interested in why it might be useful to have it as an example: <a href="http://arxiv.org/abs/0704.2030" rel="nofollow">arxiv.org/abs/0704.2030</a>

http://mathoverflow.net/questions/56441/mathematics-tv-clips Nick Loughlin 2011-02-28T16:34:48Z 2011-02-28T16:34:48Z

This one is pretty cool, and pretty much subsumes (some of the main results in) a first course on graph theory: <a href="http://www.youtube.com/watch?v=heKK95DAKms" rel="nofollow">youtube.com/watch?v=heKK95DAKms</a>

http://mathoverflow.net/questions/56245/graphs-embedded-on-fractals/56246#56246 Nick Loughlin 2011-02-22T11:38:55Z 2011-02-22T11:38:55Z

No non-planar graph should embed, since the gasket may be realised as sitting on the plane

http://mathoverflow.net/questions/56245/graphs-embedded-on-fractals/56264#56264 Nick Loughlin 2011-02-22T11:27:39Z 2011-02-22T11:27:39Z

There's also the issue of projections onto dust-like sets. For instance, the Cartesian product of some totally-disconnected dust-set and the unit-square will only ever admit planar-graph embeddings. The question is perhaps better-posed in terms of connected self-affine sets with some non-snowflake-like conditions imposed (I'm not familiar with the definition of a &quot;snowflake space&quot;).

http://mathoverflow.net/questions/55027/triangulating-hypercubes/55048#55048 Nick Loughlin 2011-02-11T11:12:54Z 2011-02-11T11:12:54Z

I didn't notice Greg's comment, which would suggest that my last post was off-the-mark, although I will check it out.

http://mathoverflow.net/questions/55027/triangulating-hypercubes/55048#55048 Nick Loughlin 2011-02-11T11:11:49Z 2011-02-11T11:11:49Z

Awesome, thank you! I've been trying in HAP(GAP package), but it's not too happy (so far as I can tell) if I'm not working with a complex where each cube sits inside a cube of maximal dimension, the so-called &quot;pure&quot; complexes. So I can't just start sticking extra squares hanging off my cubes, say.

http://mathoverflow.net/questions/55027/triangulating-hypercubes/55028#55028 Nick Loughlin 2011-02-10T13:20:19Z 2011-02-10T13:20:19Z

Yes, this and some related triangulations are known - a slightly better version (in 3d gives 5 simplices instead of 6) is to 2-colour the vertices and dissect-off a simplex at each odd vertex, say, and then deal with the polytope you're left with - see theorem 3.6.3 here: <a href="http://books.google.com/books?id=SxY1Xrr12DwC&amp;pg=PA315" rel="nofollow">books.google.com/&hellip;</a>

http://mathoverflow.net/questions/54759/what-does-rngop-look-like Nick Loughlin 2011-02-10T11:10:49Z 2011-02-10T11:10:49Z

Sorry, I should also have specified that addition was abelian!

http://mathoverflow.net/questions/54759/what-does-rngop-look-like Nick Loughlin 2011-02-08T21:13:29Z 2011-02-08T21:13:29Z

I meant that multiplication would define a monoid, as opposed to there being some involution floating around, and by analogue, addition a group. My notation $\mathbf{Rng}$ (as it should be typeset) was a lift from a book on Category theory (Abstract and Concrete Categories); I agree that the &quot;rng&quot; would be a &quot;ring without 'I'dentity&quot;.