Peter Taylor
Reputation
4,772
Top tag
Next privilege 5,000 Rep.
Approve tag wiki edits
 Apr8 comment Round Robin for Team Matches Does en.wikipedia.org/wiki/… help? Apr8 comment Making 7 vertices triangle free graph bipartite by deleting an edge There's a trivial counter-example: the graph with $|V|=7$ and $|E|=0$. Apr7 comment Characterizing a certain set of matrices arising from binary trees Your diagram doesn't look like a binary tree. It could be converted into a binary tree by inserting three non-leaf nodes, but if this is done symmetrically then the distances between leaf nodes would be $2$ and $4$. What is the actual tree structure? Apr4 comment Josephus Variant You might want to check your results against oeis.org/A032434. Apr4 revised Physics Related Watt Question edited tags Apr2 comment Minimal DFA for a given regular expression Are you familiar with the Myhill-Nerode theorem? Apr1 reviewed Edit Order and element set of the group with presentation $\langle a,b \;|\; a^9=1, b^3=a^3, [a,b]=a^3\rangle$ Apr1 revised Order and element set of the group with presentation $\langle a,b \;|\; a^9=1, b^3=a^3, [a,b]=a^3\rangle$ deleted 2 characters in body Mar29 comment Are there useful combinatorial constructions of grammars? I don't have enough to make an answer, and you stand more chance of getting a more complete answer if I stick to comments. But Flajolet and Sedgewick's book on Analytic Combinatorics seems to address something related to context-free grammars, so you might want to try to find a copy. Mar28 comment Are there useful combinatorial constructions of grammars? I think you need to be a bit more careful in distinguishing between a rule from a CFG and the CFG itself. I can understand that you might want to identify the CFG with the rule which defines its initial non-terminal, but things might become clearer if you define the size of a rule as the number of symbols in its definition and the size of a grammar as the sum of the sizes of the rules reachable from its initial non-terminal. For a start, that immediately highlights the importance of the transitive closure, and suggests looking at graph combinatorics. Mar22 comment Maximum board position in 2048 game How is the score computed from the move sequence? Mar16 answered Distinguishing between hash function digest and message corruption Mar10 answered What is the pupose of using minute and seconds with degree? Mar10 comment What is the pupose of using minute and seconds with degree? Is your question a mathematical history question ("What's the history of base-60 being preferred to base-10?") or is it about present day usage? If the second, could you give examples of where you've encountered it? Feb27 comment Smullyan-To-Mock-a-Mockingbird, Find egocentric bird in L The stack overflow was due to $LL(LL) \rightarrow_{\beta} L(LL(LL))$. Manually eliminating that case, I managed to run the others for tens of thousands of beta-expansions and stopped when the program was using 14GB of memory. They were all expanded to at least 3 times their starting size. Feb27 comment Smullyan-To-Mock-a-Mockingbird, Find egocentric bird in L NB I've attempted to test all expressions of the form $BB$ where $|B| < 6$ by beta-expanding repeatedly (using a priority queue by size of expression) and checking for each expression $XY$ so reached whether both $X$ and $Y$ had previously been encountered. The program failed with a stack overflow when looking for beta-expansions in a 1001-$L$ expression. $(N_3 N_3)(N_3 N_3)$, on the other hand, succeeds at the first opportunity with a 24-$L$ expression. So certainly there's no smaller solution which behaves as nicely as $(N_3 N_3)(N_3 N_3)$. Feb25 revised Given a victory condition and a set strategy, what are the chances of winning on a given turn in a game of Magic: The Gathering? Replaced dead link with one which goes directly to the source Feb24 answered Smullyan-To-Mock-a-Mockingbird, Find egocentric bird in L Feb24 comment Smullyan-To-Mock-a-Mockingbird, Find egocentric bird in L @Snowball, the problem there is that checking whether two combinator expressions are equivalent is undecidable in the general case, and the behaviour of $L L (L L) = L (L L (L L)) = \lambda x. L L (L L) (x x)$ seems to rule out testing extensionality for small cases, looking for a counterexample, as a strategy. Feb23 comment Is it possible to build a circle with quadratic Bézier curves? @JasonS, I took a screenshot of the linked PDF.