Timeline for Counting words accepted by a regular grammar
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 2, 2014 at 13:38 | comment | added | Raphael | @joro In case of unambiguous grammars, I think that this is true, yes. | |
| Apr 2, 2014 at 12:36 | comment | added | joro | Are you saying you can count words of length $n$ in a regular language in polynomial time and without constructing DFA? Asked about the complexity of this on MO: mathoverflow.net/questions/162186/… | |
| Sep 27, 2011 at 19:40 | comment | added | Charles | Thanks! (I of course upvoted you the moment I first read the answer, which is excellent. Otherwise I'd upvote you now.) | |
| Sep 27, 2011 at 18:27 | comment | added | Raphael | I see, I misunderstood. In that case, if you want to read into this, I recommend Kuich (1970) which I found more accessible than the work of C&S. He also covers this in a book of his which I don't remember. | |
| Sep 26, 2011 at 20:34 | comment | added | Charles | No disagreement, I just appreciate the addition of the reference which makes it easier to attribute things. | |
| Sep 25, 2011 at 9:28 | history | edited | Raphael | CC BY-SA 3.0 |
added 38 characters in body
|
| Sep 13, 2011 at 10:23 | history | edited | Raphael | CC BY-SA 3.0 |
added 285 characters in body
|
| Sep 12, 2011 at 21:33 | comment | added | Raphael | Er, this is actually a method that works really well (and is simple, once you get it) in many circumstances. For example, you can do CFGs in exactly the same way. | |
| Sep 12, 2011 at 21:03 | comment | added | Charles | I appreciate the historical note! | |
| Sep 12, 2011 at 18:47 | history | answered | Raphael | CC BY-SA 3.0 |