Timeline for Approaches to implicitly defining generating function
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18, 2014 at 4:40 | vote | accept | XL _At_Here_There | ||
| May 14, 2014 at 9:27 | history | edited | XL _At_Here_There | CC BY-SA 3.0 |
added 56 characters in body
|
| May 14, 2014 at 9:06 | history | edited | XL _At_Here_There | CC BY-SA 3.0 |
deleted 37 characters in body
|
| May 14, 2014 at 8:59 | history | edited | XL _At_Here_There | CC BY-SA 3.0 |
deleted 37 characters in body
|
| May 14, 2014 at 8:25 | answer | added | Dima Pasechnik | timeline score: 1 | |
| May 14, 2014 at 8:20 | comment | added | Dima Pasechnik | (continuing) let $F$ be the GF for a recursively enumerable language with non-recursively enumerable complement, and $A$ the GF for the language of all words. Then $A-F$ is the GF for the complement of $F$, i.e. for a non-Chomsky language. | |
| May 14, 2014 at 8:12 | history | edited | XL _At_Here_There | CC BY-SA 3.0 |
added 11 characters in body
|
| May 14, 2014 at 8:08 | comment | added | Dima Pasechnik | If it is the way I described in my comment then there certainly are GFs not corresponding to any language in Chomsky hierarchy, as the latter must be recursively enumerable, a property known not to be closed under taking the complement. | |
| May 14, 2014 at 8:06 | comment | added | XL _At_Here_There | @DimaPasechnik,yes,that is what I mean | |
| May 14, 2014 at 8:05 | history | edited | XL _At_Here_There | CC BY-SA 3.0 |
added 45 characters in body
|
| May 14, 2014 at 8:05 | comment | added | Dima Pasechnik | I am not sure if it is well-known how does a language $L$ correspond to a generating function $F(t)=\sum_i a_i t^i$. Is $a_i$ equal to the number of length $i$ words in $L$? | |
| May 14, 2014 at 7:54 | history | edited | XL _At_Here_There | CC BY-SA 3.0 |
added 105 characters in body
|
| May 14, 2014 at 7:21 | history | asked | XL _At_Here_There | CC BY-SA 3.0 |