251 reputation
17
bio website informatics.sussex.ac.uk/…
location London, United Kingdom
age
visits member for 3 years, 1 month
seen Apr 15 at 15:47

Mar
18
accepted Generating functions for context-free languages
Jun
6
accepted Is (im)predicativity decidable
May
31
comment Is (im)predicativity decidable
Thanks, what is the set-theoretic semantics of "$j$ is the $\phi$"?
May
30
comment Is (im)predicativity decidable
Regarding Jane. It depends on what exactly you mean by picking out Jane. If it's something like this: $ tallest = \{x \in R|\forall y \in R. (x \neq y \rightarrow h(y) < h(x))\} $ where $R$ is the set of people in the room, and $h$ a function returning the height of an individual, then I would imagine that the predicate $tallest$ is not defined in an impredicative way.
May
30
comment Is (im)predicativity decidable
I think the real reason people (used to) worry about impredicativity isn't to do with realism or otherwise, is was more because there was a lingering fear that impredicative definitions would eventually turn out to be contradictory. Time has assuaged this worry. That said, I don't particularly care about such issues. I'm interested in the syntactic shape of (im)predicative definitions. I have an intuitive idea why e.g. the impredicative definition of the natural numbers in ZF is unproblematic, and it's a syntactic criterion.
May
30
comment Is (im)predicativity decidable
Another question: would you happen to have a (natural) example of a definition in ZF(C) where it's unclear if it's impredicative or not?
May
30
comment Is (im)predicativity decidable
Thanks for your informative answer. Maybe self-referential is a better term in this context than circular. BTW I am not sure that Ramsey's example is impredicative. Informally, Jane is not freshly constructed, she's existing already. What we define is a predicate $tallestInRoom$ (that happens to hold of Jane). And the predicate is not defined in a self-referential way. This is quite different with the usual impredicative definition of eg. the natural numbers in set theory, where you bring about the set only by the impredicative definition.
May
30
revised Is (im)predicativity decidable
added 130 characters in body
May
30
asked Is (im)predicativity decidable
May
21
comment Career in Number Theory?
Don't worry too much about this now, wait until you've near finishing your PhD. A good PhD qualifies you for many different careers if you are no longer interested in number theory. At this point, I suggest to become as good a mathematician as you can.
May
14
awarded  Caucus
Nov
6
awarded  Commentator
Nov
6
comment Generating functions for context-free languages
Thanks that's neat! Is this transformation of collapsing all terminals functorial in some category of CFGs (whatever that might be)? Anyway, as nice as this is, it doesn't really seem to give a handle on the original question whether we can compute the generating functions (for degrees of ambiguity or number of $n$-length strings), or its power-series coefficients easily. Would you happen to have any further ideas in this direction?
Nov
2
comment Generating functions for context-free languages
@ Hendirk Jan, I'm interested in either, I just thought unambiguous is simpler (and in the case or regular expressions gives rise to a simple inductive definition of generating functions). For unambiguous grammars the coefficients $a_n$ in $\Sigma_{n < \omega}a_n f_n$ are always 'binary', i.e. either 0 or 1. Is there a systematic relationship between such binary formal power series, and power series that count strings of size $n$?
Nov
2
comment Generating functions for context-free languages
@ Hendirk Jan. As far as I understand (not very much) Schuetzenberger does this: let $\Sigma$ be a finite alphabet, and $(f_n)_{n<\omega}$ and enumeration of $\Sigma^*$. Then he produces a formal power-series $\Sigma_{n<\omega}a_n f_n$ such that $a_n$ is the number of ways that $f_n$ can be generated by the CFG. So $a_n$ measures ambiguity. The formal power series is obtained by a limiting process. That makes it difficult to read off the generating function that counts the strings of size $n$. I wonder if somebody wrote down a more convenient way of counting strings of size $n$.
Nov
1
revised Generating functions for context-free languages
added 5 characters in body
Oct
31
revised Generating functions for context-free languages
added 6 characters in body
Oct
30
comment Generating functions for context-free languages
@ Rick Decker: the formulations of the Schuetzenberger-Chomsky theorem I have seen, including the Wikipedia article you've linked to, don't give you the sequence ($a_i$) of cardinalities, or the generating function. But I'm after is the generating function, so I can use it obtain just that sequence. Are you aware of Schuetzenberger-Chomsky variants that enable me to do this?
Oct
30
awarded  Yearling
Oct
30
revised Generating functions for context-free languages
added 21 characters in body