Timeline for characterization of regular languages among (say) those computable in linear time
Current License: CC BY-SA 2.5
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 28, 2010 at 7:15 | comment | added | Qiaochu Yuan | Stanley, Enumerative Combinatorics, Vol. II, Theorem 6.5.7. | |
| Apr 28, 2010 at 6:46 | answer | added | Dylan Thurston | timeline score: 3 | |
| Apr 17, 2010 at 15:20 | comment | added | Łukasz Grabowski | Dylan: can you give a reference for that? | |
| Apr 17, 2010 at 2:36 | comment | added | Dylan Thurston | On the other hand, if you can consider the sum of all the words in the language as an element in a non-commutative power series ring. That sum is rational iff the language is regular. | |
| Apr 16, 2010 at 17:22 | comment | added | Qiaochu Yuan | The language of palindromes over an alphabet of at least two letters is recognizable in linear time, context-free, and has rational generating function, but is not regular. So you're going to need a pretty severe restriction to exclude palindromes... | |
| Apr 16, 2010 at 17:11 | history | asked | Łukasz Grabowski | CC BY-SA 2.5 |