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
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 16 at 2:53 | comment | added | Harry Altman | Oh, oops, I only just now saw the edit. Thanks! Yes #2 makes no sense, but it's not obvious to me why your argument would fail with #1 (but would succeed in the little-endian case). The issues you point out with #1 don't seem to me to be relevant to anything you actually use. Maybe the problem would be clearer if the argument were more expanded, but it seems to me like formally it ought to be similar even if the meaning is much less natural. | |
| Apr 4 at 19:02 | history | edited | Sophie M | CC BY-SA 4.0 |
fixed sign error in final para, no substantive change
|
| Apr 4 at 8:11 | history | edited | Sophie M | CC BY-SA 4.0 |
substantial elaboration in response to comments
|
| Apr 3 at 22:04 | comment | added | Harry Altman | I mean it looks like you are in fact thinking of reading from the little end, I just don't see how this sketch uses that fact, like, if we imagined it was reading from this big end, it looks to me like this sketch would still apply; yet we know it doesn't work in that case, so that suggests something is wrong with the original. | |
| Apr 3 at 22:02 | comment | added | Harry Altman | No, by "reading from the big end" vs "reading from the little end" isn't refering to something about the compuation, it's about how we define the set itself. By "reading from the little end" -- right-to-left, as I also clarified in the original question -- I mean that we are feeding in the digits of the number starting at the little end, the 1s place, and then moving to the left; as opposed to starting at the highest place and moving right. These will give you different sets, and the big-endian version doesn't work with natural density! (But it might still with logarithmic density?) | |
| Apr 3 at 15:03 | comment | added | Sophie M | Correction to my response to the first question (sorry for the multiple comments): instead of "you're really computing the probability of accepting assuming it's all 0's to the left", I should have said that you're deciding whether $n \in S$, assuming it's all $0$'s to the left. So you accept or reject based on partial information ($T$ digits) about the infinite string, and the probability of accepting after $T$ digits happens to approximate the density of $S$ among $T$-digit integers. | |
| Apr 3 at 14:49 | comment | added | Sophie M | Second question: yes, easy to add in. The limiting acceptance probability is the sum of the probabilities of the accepting sinks. If most strings have hit a sink already at $T$ digits, then the fraction that have reached a given sink is going to be close to the limiting probability of that sink. | |
| Apr 3 at 14:46 | comment | added | Sophie M | First question: by reading from the big end, I guess you mean that you fix $T \approx \log_b N$ then compute $|S \cap [1,N]|$ by looking at the integers with $T$ digits? The difference, digging into the weeds a bit, is that you're then no longer looking at successive refinements of partitions/algebras on the space of left-infinite strings $\{0, 1, \dots, b-1 \}^{\mathbb{N}}$. It occurs to me that maybe what I need to say in my second para is that when you halt after $T$ digits from the right, you're really computing the probability of accepting assuming it's all $0$'s to the left. | |
| Apr 3 at 5:43 | comment | added | Harry Altman | This is a helpful start, thanks! But there's something confusing me here: Where does this use the fact that we're reading from the little end? We know the statement is false if we start at the big end, but this sketch doesn't seem to use the fact that we're reading from the little end. Also, maybe I'm missing something, but while this bounds the probability of not reaching a sink, it doesn't seem to say anything about the distribution on the sinks after $T$ being close to the limiting distribution? (I guess that's probably easy to add in?) | |
| Apr 2 at 17:08 | history | edited | Sophie M | CC BY-SA 4.0 |
small substantive fix to a step of the argument; conclusion and overall strategy unaffected
|
| Apr 2 at 16:17 | history | answered | Sophie M | CC BY-SA 4.0 |