4 ms·

This language of matching brackets is also called the Dyck language and its syntactic monoid is the bicyclic semigroup, which is an interesting example of an in

This language of matching brackets is also called the Dyck language and its syntactic monoid is the bicyclic semigroup, which is an interesting example of an inverse semigroup. Edward Kmett gave a talk on programming with these sorts of algebraic structures that some might find illuminating: https://www.youtube.com/watch?v=HGi5AxmQUwU https://www.youtube.com/watch?v=HGi5AxmQUwU Inverse semigroups are used in the geometry of interaction to give a parallelizable interpretation of lambda calculus. I don't have a great introductory reference. Here's some people who have implemented a system based on the theory: https://www.cambridge.org/core/journals/mathematical-structures-in-computer-science/article/abstract-machines-optimal-reduction-and-streams/60F590DA98EAC48CC6E7AADB46235B8C https://www.cambridge.org/core/journals/mathematical-structu... Sorry for the citation dump, I'm short on time and I thought they would be interesting to those who found this submission interesting. References https://en.wikipedia.org/wiki/Dyck_language https://en.wikipedia.org/wiki/Dyck_language https://en.wikipedia.org/wiki/Bicyclic_semigroup https://en.wikipedia.org/wiki/Bicyclic_semigroup

rumanator 6y ago
Thanks for the insightful post, specially the Dyck language plug. Really cool stuff.
AnthonBerg 6y ago
Citation dump gratefully received!
raphlinus 6y ago
The Dyck language I was already aware of; I linked it in the previous post in the series. But the bicyclic semigroup was new to me. Yes, the bones of it are very similar to my "stack monoid;" if you erase the actual element values of the stack contents and just count the lengths, it's clearly the same thing. No doubt there's some theory that justifies adding the elements back in as well. I'll have to check out the Kmett talk - from the description it sounds very interesting.
- nilknarf 6y ago
  Although I didn't know it by that name, I have seen the bicyclic semigroup in competitive programming many times before (usually any problem involving intervals/brackets and segment trees). For example in this problem https://codeforces.com/contest/1285/problem/E https://codeforces.com/contest/1285/problem/E, one solution is to parse and count the number of top-level parentheses after small modifications. For example the original string might be "(()())()". Then "(()())" is 1, "(())()" is 2, "()()()" is 3. This is solved with the following monoid to make incremental reparsing fast: neutral = Node(0, 0, 0) def combine(x, y): # Each node tracks numClose, numCount, numOpen: # e.g., )))) (...)(...)(...) (((((( if x.open == y.close == 0: ret = x.close, x.count + y.count, y.open elif x.open == y.close: ret = x.close, x.count + 1 + y.count, y.open elif x.open > y.close: ret = x.close, x.count, x.open - y.close + y.open elif x.open < y.close: ret = x.close + y.close - x.open, y.count, y.open return Node(*ret) Reference solution: https://codeforces.com/contest/1285/submission/92169958 https://codeforces.com/contest/1285/submission/92169958 Monoid cached trees are extremely popular in competitive programming, but never by that name. It's always referred to as a "segment tree" without using any mathematical terminology more advanced than "associativity". Due to its popularity, all kinds of crazy monoid states have already been explored (though you need to squint a bit to see them due to the terminology mismatch): https://codeforces.com/blog/entry/15890 https://codeforces.com/blog/entry/15890. I've never seen stack used though. You almost always want to compress the state as much as possible and the problems I've seen only needed stack depth (aka the bicyclic semigroup), not contents. Requiring O(N) to merge also highly limits its use cases. Anyway, not sure how relevant this is to you since the use of monoids in data structures and for parallelism is slightly different (binary merges all the way down versus stopping at some chunk size).

rumanator 6y ago

Thanks for the insightful post, specially the Dyck language plug. Really cool stuff.

AnthonBerg 6y ago

Citation dump gratefully received!

raphlinus 6y ago

The Dyck language I was already aware of; I linked it in the previous post in the series. But the bicyclic semigroup was new to me. Yes, the bones of it are very similar to my "stack monoid;" if you erase the actual element values of the stack contents and just count the lengths, it's clearly the same thing. No doubt there's some theory that justifies adding the elements back in as well. I'll have to check out the Kmett talk - from the description it sounds very interesting.

nilknarf 6y ago
Although I didn't know it by that name, I have seen the bicyclic semigroup in competitive programming many times before (usually any problem involving intervals/brackets and segment trees). For example in this problem https://codeforces.com/contest/1285/problem/E https://codeforces.com/contest/1285/problem/E, one solution is to parse and count the number of top-level parentheses after small modifications. For example the original string might be "(()())()". Then "(()())" is 1, "(())()" is 2, "()()()" is 3. This is solved with the following monoid to make incremental reparsing fast: neutral = Node(0, 0, 0) def combine(x, y): # Each node tracks numClose, numCount, numOpen: # e.g., )))) (...)(...)(...) (((((( if x.open == y.close == 0: ret = x.close, x.count + y.count, y.open elif x.open == y.close: ret = x.close, x.count + 1 + y.count, y.open elif x.open > y.close: ret = x.close, x.count, x.open - y.close + y.open elif x.open < y.close: ret = x.close + y.close - x.open, y.count, y.open return Node(*ret) Reference solution: https://codeforces.com/contest/1285/submission/92169958 https://codeforces.com/contest/1285/submission/92169958 Monoid cached trees are extremely popular in competitive programming, but never by that name. It's always referred to as a "segment tree" without using any mathematical terminology more advanced than "associativity". Due to its popularity, all kinds of crazy monoid states have already been explored (though you need to squint a bit to see them due to the terminology mismatch): https://codeforces.com/blog/entry/15890 https://codeforces.com/blog/entry/15890. I've never seen stack used though. You almost always want to compress the state as much as possible and the problems I've seen only needed stack depth (aka the bicyclic semigroup), not contents. Requiring O(N) to merge also highly limits its use cases. Anyway, not sure how relevant this is to you since the use of monoids in data structures and for parallelism is slightly different (binary merges all the way down versus stopping at some chunk size).