Timeline for Communication complexity of Dyck language
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 26, 2023 at 14:24 | comment | added | Kai | oeis.org/A000975 | |
| Nov 26, 2023 at 12:08 | comment | added | Kai | The wording is fine, my thinking wasn't. I interpret your signatures roughly as "what's on the stack of a PDA for Dyck$(2)$". We ought to exclude those signatures $x$ for which there's no matching $y\in A^n$. If I'm not mistaken, they are the $x$ with an odd $n - |x|$. Sadly, I'm not aware of a closed form for $\sum_{i+j\le n\\ n-i-j\bmod 2 = 0}{i+j\choose i}$. | |
| Nov 24, 2023 at 22:08 | comment | added | D.W.♦ | @Kai, sorry for the imprecise wording. That's not a lower bound. There are strings in $\{[,(\}^{\le n}$ that are not a possible signature. e.g., for $n=3$, $[($ is not a possible signature, i.e., there is no string $x$ of length 3 whose signature is $[($. Consequently, $2^{n+1}-1$ is an upper bound on the number of different signatures but not a lower bound. | |
| Nov 24, 2023 at 22:07 | history | edited | D.W.♦ | CC BY-SA 4.0 |
Clarify definition of N
|
| Nov 23, 2023 at 11:30 | comment | added | Kai | Looks like you've already done all the work for the lower bound being $\lg (2^{n+1}-1)$, too. | |
| Nov 23, 2023 at 8:41 | history | answered | D.W.♦ | CC BY-SA 4.0 |