Timeline for Growth zeta-functions of regular languages
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 31, 2013 at 12:15 | comment | added | Sam Nead | The tricky part is that the deterministic FSA may be exponentially larger than the given regular expression! Disambiguation is also supposedly dealt with in Volume A, Chapter 8 of "Automata, languages, and machines" by Samuel Eilenberg. I found this reference somewhat cryptic. | |
| May 31, 2013 at 12:11 | comment | added | Sam Nead | I've deleted my previous comments, after pulling all of the interesting material here. For anybody reading this: there is a delicate point residing in the phrase "unambiguous regular expression". If you are given the language via a regular expression, then the process of disambiguation goes via constructing a deterministic FSA for the language. For a how-to, see: mathoverflow.net/questions/45149/… | |
| Jun 21, 2011 at 20:21 | comment | added | Victor | Thanks, it's actually so obvious now indeed that the correspondent power series is rational. I should have given a normal proper thought about the question. | |
| Jun 21, 2011 at 20:18 | vote | accept | Victor | ||
| Jun 21, 2011 at 20:04 | history | answered | Steven Stadnicki | CC BY-SA 3.0 |