[FoRK] wurst ist besser

Dave Long dave.long at bluewin.ch
Fri Sep 13 03:17:51 PDT 2013


There are two informal german phrases, "alles hat ein ende; nur die  
wurst hat zwei" and "es ist mir wurst", which actually comment on the  
possibility of parallelization.

The first (contra everett) is translated by "everything comes to an  
end; only a sausage has two", and can be taken as an observation that  
in general[0], Kleene Algebras don't have an equality between

    mu x (1 + ax), and
    mu x (1 + xa)

The second is translated by "it's all sausage to me", which  
identifies don't-care conditions.  When the two fixpoints above do  
coincide, they are also equal to:

     mu x (1 + ax + xa), and
     mu x (1 + a + xx)

In other words, if we see that a computation can be made either  
backwards or forwards[1], it's a sausage with two ends, and can also  
be computed from the outside in (zipper style), or even in any other  
grouping, for example divide and conquer style: chopping it up into a  
bunch of tiny pieces and mushing them together in a single casing.

-Dave

[0] Leiss, "Towards Kleene Algebra with Recursion", 1991
http://www.cis.uni-muenchen.de/download/publikationen/kar_csl-91.pdf
[1] Gibbons, "The Third Homomorphism Theorem", 1995
http://citeseerx.ist.psu.edu/viewdoc/download? 
doi=10.1.1.45.2247&rep=rep1&type=pdf



More information about the FoRK mailing list