3 ms·
Do succint trees like https://arxiv.org/pdf/1601.06939.pdf https://arxiv.org/pdf/1601.06939.pdf solve the same problems that stack monoids solve? I'll take some
by qazxcvbnm 3y ago
Do succint trees like https://arxiv.org/pdf/1601.06939.pdf https://arxiv.org/pdf/1601.06939.pdf solve the same problems that stack monoids solve? I'll take some more time to fully digest the contents of this family of problems, but on first glance they seem closely related, with the input Balanced Parentheses being precisely the "BP" succint tree representation. I'm not sure of it, but from my understanding it seems probable that building the succint tree can be parallelised.
- raphlinus 3y agoThey are related, thanks for the pointer! The representation of the tree is very similar, as are the techniques to get better than O(log n) - the work efficiency stuff. I'll add a reference to that if/when I do a published version. That said, I am unaware of any publications on parallel implementations of succinct trees.
- qazxcvbnm 3y agoWhile I was reading up further on succint trees, I noticed this https://web.cs.dal.ca/~mhe/publications/sea15_parallelsuccinctrees.pdf https://web.cs.dal.ca/~mhe/publications/sea15_parallelsuccin... . I've not gone through it thoroughly yet, but it seems that someone has done it.