Timeline for Chomsky Schützenberger enumeration theorem
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 22, 2020 at 12:24 | comment | added | Jori | Have you found access in the mean time to your copy? | |
| Jul 29, 2020 at 6:23 | comment | added | Jeffrey Shallit | Not the transcendence of $\pi$ but rather the transcendence of the formal power series analogue over a finite field. I can't tell you what to read in the book because the pandemic makes it impossible for me to access a copy currently. | |
| Jul 28, 2020 at 19:39 | comment | added | Jori | So what would I need to read in the Kuich-Salomaa book? I'm a logician, so this is not really my topic, but I've always wanted to learn about this proof; I remember reading that the transcendence of $\pi$ was equivalent to some language being inherently ambiguous and found that quite neat, although I'm not sure I remember the details correctly. | |
| Jul 28, 2020 at 18:48 | comment | added | Jeffrey Shallit | The ingredient that is needed is some guarantee that when you take an unambiguous CFG and convert it to a system of algebraic equations in the almost-trivial way described by Chomsky and Schützenberger, that there indeed exists a solution to this system in power series, and that it is unique. | |
| Jul 27, 2020 at 17:28 | comment | added | Jori | Oh I see, no that isn't at all uncommon. But how big is the gap between the ideas that Chomky and Schützenberger provide and the actual proof? Because from casual glancing both Kuich&Salomaa and Panholzer need quite a bit of machinery to get there (I don't know how much because there is no explicitly delineated proof in those either, as far as I can tell). How much of the Kuich-Salomaa book do you need? | |
| Jul 27, 2020 at 16:04 | comment | added | Jeffrey Shallit | It is named for them because they had the basic statement and idea in their paper, although they did not supply a complete formal proof. That is not unusual in mathematics. | |
| Jul 26, 2020 at 15:42 | comment | added | Jori | But it's called Chomsky-Schützenberger enumeration theorem; shouldn't there be a proof in their Algebraic theory of context-free languages (Studies in Logic and the Foundations of Mathematic), which seems very accessible? However, I quickly looked through it but I couldn't find an explicit statement there (let alone a proof). If it isn't there, then the question rises where the name comes from... | |
| Jul 25, 2016 at 11:46 | vote | accept | Christian Hagemeier | ||
| Jul 25, 2016 at 10:55 | history | answered | Jeffrey Shallit | CC BY-SA 3.0 |