Timeline for Given an automatic set $S$ coming from a DFA $M$ when read little-endian, is $\overline{d}(S)$ at most the Büchi acceptance probability of $M$?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 19 at 8:43 | comment | added | Harry Altman | Sure, go ahead, email address is on my website linked in my profile! | |
| Apr 19 at 8:11 | comment | added | Sophie M | If you don't mind, I'm just going to email you -- I'm interested in understanding exactly what is going on with the various formulations of your question, and I think there are enough details to spell out that it's best not to try to get them right through successive modifications to this answer. | |
| Apr 19 at 7:40 | comment | added | Harry Altman | Oh wait, I just realized another potential problem with this answer. It's not true that extending a number with $0$'s necessarily leads to a sink. Consider e.g. if $b=2$ and $S$ consists of numbers such that between consecutive $1$s in the binary expansions there's always an odd number of $0$s. Moving around randomly leads to a sink with probability $1$, but for many numbers extending with $0$s will lead to cycling between 2 states, without hitting a sink! | |
| Apr 19 at 5:55 | comment | added | Harry Altman | (Btw, I think you have some off-by-one or off-by-two errors -- it looks like right now you're defining $L$ based on where $\omega$ is just before it hits a sink, rather than when it hits a sink. But that's obviously not that important. Also to be clear I was absolutely not thinking in terms of $L_*P$, I was thinking more about the sequence stabilizing at the sink rather than stopping there and recording the number created this way, but it looks like that may be a useful way to think about it. :) ) | |
| Apr 19 at 5:53 | comment | added | Harry Altman | Thank you! I'm a bit confused about the end though -- OK, that gets you the overall probability, but where does the overall density come in? Given that density is only finitely additive, after all (otherwise there wouldn't be a problem). | |
| Apr 17 at 21:07 | history | answered | Sophie M | CC BY-SA 4.0 |