# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | Um_nik | 162 |
3 | maomao90 | 162 |
5 | adamant | 157 |
5 | -is-this-fft- | 157 |
5 | djm03178 | 157 |
8 | awoo | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Name |
---|
While Kleene's algorithm can be used here, it's generally quite impractical. Consider the DFA from the linked article:
The example in the article has nearly 30 steps involving manually simplifying very long expressions such as
One alternative approach to constructing regex from DFA is by solving the linear system:
By expressing variables $$$q_0$$$, $$$q_1$$$ and $$$q_2$$$ through one another, we eventually arrive at the equation $$$x = a|bx$$$, where $$$a$$$ and $$$b$$$ are regex. Then, the minimum solution $$$x$$$ is found by iterating this equation (also known as Arden's rule):
This is similar to how the equation $$$x=a+bx$$$ in real numbers is solved by
So, by substitution we find
from which we get
So, regex for all states are
Of course, it's still exponential growth in the worst case, but at least it's not as fast as with Kleene's method.
Thanks for the comment! It is indeed similar to the approach in one of the papers mentioned in the TL;DR too.
A natural generalization is Gaussian elimination, and algorithms similar to it are mentioned for semirings after transforming these problems into systems of linear equations in those papers.
Could somebody please finally write a blog post about $$$O(n^{3-\varepsilon})$$$ algorithm for APSP...
Are there any? Some googling gives this article, and its best is
Apparently, no $$$O(n^{3-\varepsilon})$$$ was known in 2014 for APSP, and I can't easily find any updates?
In fact it is conjectured that such an algorithm does not exist, leading to the fascinating theory of fine-grained complexity.
Yeah, sorry... I tried to make a joke. There are many reasons to believe that such an algorithm does not exist.
It might be surprising for some people to know that there is an $$$O(n^{2 + o(1)})$$$ (probabilistic) algorithm for all pairs min cut — so APMC is probably easier than APSP. I was planning on writing a blog for it, but haven't gotten the time to complete it — the paper is here.
The most useful thing I know about Floyd-Warshall is described in this blog by bukefala