nor's blog

[Tutorial] The Floyd-Warshall algorithm and its generalizations
By nor, 10 months ago, In English

https://nor-blog.surge.sh/posts/2023-07-01-floyd-warshall-and-generalizations/

  • Vote: I like it
  • +171
  • Vote: I do not like it

»
10 months ago, # |
← Rev. 8   Vote: I like it +19 Vote: I do not like it

Statement: Given a DFA $$$D$$$, find a regular expression that accepts the same language as $$$D$$$.

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

$$$ ((a|b)b^*a | \varepsilon) ((a|b)b^*a | \varepsilon)^* ((a|b)b^*a | \varepsilon)| (a | b) b^* a | \varepsilon = ((a | b) b^* a)^* $$$

One alternative approach to constructing regex from DFA is by solving the linear system:

$$$ \begin{cases} q_0 = a q_0 | b q_1 \\ q_1 = \varepsilon | b q_1 | a q_2 \\ q_2 = (a|b)q_1 \end{cases} $$$

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):

$$$ x = a | ba | b^2 x = a | ba | b^2 a | b^3 a | \dots = (\varepsilon | b | b^2 | b^3 | \dots) a = b^* a. $$$

This is similar to how the equation $$$x=a+bx$$$ in real numbers is solved by

$$$ x = \left(\frac{1}{1-b}\right)a = (1+b+b^2+b^3+\dots)a. $$$

So, by substitution we find

$$$ q_1 = \varepsilon | bq_1 | a(a|b)q_1 = \varepsilon | (b|aa|ab)q_1 = (b|aa|ab)^*, $$$

from which we get

$$$ q_0 = a q_0 | b(b|aa|ab)^* = a^*b(b|aa|ab)^*. $$$

So, regex for all states are

$$$ \begin{cases} q_0 = a^*b(b|aa|ab)^*, \\ q_1 = (b|aa|ab)^*, \\ q_2 = (a|b) (b|aa|ab)^*. \end{cases} $$$

Of course, it's still exponential growth in the worst case, but at least it's not as fast as with Kleene's method.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    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.

    → Reply
»
10 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Could somebody please finally write a blog post about $$$O(n^{3-\varepsilon})$$$ algorithm for APSP...

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Are there any? Some googling gives this article, and its best is

    $$$ O\left(\frac{n^3}{2^{\Omega(\log n)^{1/2}}}\right). $$$

    Apparently, no $$$O(n^{3-\varepsilon})$$$ was known in 2014 for APSP, and I can't easily find any updates?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      In fact it is conjectured that such an algorithm does not exist, leading to the fascinating theory of fine-grained complexity.

      → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Yeah, sorry... I tried to make a joke. There are many reasons to believe that such an algorithm does not exist.

      → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
»
10 months ago, # |
  Vote: I like it +36 Vote: I do not like it

The most useful thing I know about Floyd-Warshall is described in this blog by bukefala

→ Reply