bio | website | |
---|---|---|
location | ||
age | ||
visits | member for | 4 years, 9 months |
seen | Jun 16 at 13:11 | |
stats | profile views | 208 |
Jun 27 |
comment |
Inherent ambiguity of the context-sensitive language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j} $ or $a^nb^nc^nd^ne^nf^n$
@XL_at_China, WorldCat says there are copies of both of those books in the National Library of China; perhaps that is accessible to you? |
Jun 26 |
comment |
Inherent ambiguity of the context-sensitive language $L = {a^ib^ic^id^je^jf^j \bigcap a^ib^jc^id^je^if^j} $ or $a^nb^nc^nd^ne^nf^n$
I personally don't know of a good definition of a parse for a context-sensitive grammar, and it seems you need that if you want to define ambiguity as having multiple parses (is there another way to define ambiguity?). It might be interesting to look at less powerful grammars (e.g. conjunctive grammars) with a clear definition of a parse. |
May 9 |
awarded | Popular Question |
Aug 17 |
revised |
Most memorable titles
refresh link |
Aug 17 |
awarded | Nice Answer |
Jun 25 |
awarded | Yearling |
Jun 7 |
awarded | Nice Question |
Oct 14 |
comment |
Awfully sophisticated proof for simple facts
While this is obviously overkill, the general technique is so useful that perhaps students should see this proof -- when cardinality is introduced, it's not immediately obvious just how useful it is. For example, even before saying what a computer program is (but knowing that they are specified by strings), one can deduce that there are uncomputable sets, and similarly non-regular languages, etc. I'd say the general idea is that we often have countably many descriptions (programs, grammars, restrictions to $\mathbf{Q}$) but uncountably many objects, so most objects cannot be described. |
Sep 27 |
comment |
Open?: Bpp VS EXP^NP
I'm not an expert, and maybe I'm having a dumb moment, but isn't BPP easily shown to be in EXP by simulating all possible coin flips? |
Jun 21 |
comment |
Open problems with monetary rewards
Knuth says his cheques are much more often cached than cashed. |
May 5 |
comment |
What is the easiest randomized algorithm to motivate to the layperson?
This algorithm is more obviously correct than Buffon's needle, though. |
May 1 |
answered | What would you want to see at the Museum of Mathematics? |
May 1 |
revised |
What would you want to see at the Museum of Mathematics?
deleted 25 characters in body |
Apr 20 |
comment |
German mathematical terms like “Nullstellensatz”
I always assumed $U$ was for subspaces because you call a topological space $T$ for topological space, and when you take a subspace of it, you just take the next letter. |
Apr 4 |
comment |
What are the most misleading alternate definitions in taught mathematics?
The $A$ is not needed, but it makes the presentation of inverse functions more symmetrical and allows one to define partial functions with fixed domains so that functions are partial functions. |
Apr 4 |
comment |
What are the most misleading alternate definitions in taught mathematics?
Another problem with this definition is that it's wrong -- in modern mathematics (though less so in the informal language of some analysts, IME) a function has a codomain. Under this definition a function has an image, but any superset of the image could be its domain. As an undergraduate, I was given this definition several times, and it bothered me. A function is a triple $(A, B, R)$ where R is a subset of $A\times B$ such that... |
Mar 16 |
comment |
Proofs without words
I think that there is a nice pictorial proof for this fact, but I don't think this is it. It's a proof for a specific $n$. To make it a general proof, the inductive step needs to be illustrated. |
Mar 16 |
comment |
Which mathematical ideas have done most to change history?
Another WWII statistics idea: the German tank problem (recently used to estimate Apple's production of iPods, among many other things) |
Mar 16 |
comment |
Which mathematical ideas have done most to change history?
I like this quote which gives some impression of pre-decimal arithmetic. It is advice given to a German man (I think) on his son's education. I have lost the source. "If you only want him to be able to cope with addition and subtraction, then any French or German university will do. But if you are intent on your son going on to multiplication and divisionâ€”assuming that he has sufficient giftsâ€”then you will have to send him to Italy." |
Mar 3 |
comment |
What does the adjective “natural” actually mean?
Clearly the use of "natural" is increasing, but is it increasing faster than the volume of MathSciNet? I would presume that both the total rate of mathematics production is going up, and also that MathSciNet comes much closer to indexing the full text of 2000 mathematics than 1945 mathematics. |