[HN Gopher] Formal proof and analysis of an incremental cycle de...
       ___________________________________________________________________
        
       Formal proof and analysis of an incremental cycle detection
       algorithm
        
       Author : lelf
       Score  : 21 points
       Date   : 2020-02-20 05:34 UTC (17 hours ago)
        
 (HTM) web link (gallium.inria.fr)
 (TXT) w3m dump (gallium.inria.fr)
        
       | superpermutat0r wrote:
       | I remember reading somewhere about programs being turned into
       | generating functions and then asymptotic complexity follows from
       | that. Not just asymptotic in the worst-case but also the best-
       | case and average case.
       | 
       | It did not require a formal proof. It just turned code into
       | generating functions.
       | 
       | It was probably work by Philippe Flajolet, also at Inria.
       | 
       | I think I also remember it being used for memory reads and writes
       | in addition to comparison ops analysis.
       | 
       | Really great stuff.
        
       ___________________________________________________________________
       (page generated 2020-02-20 23:00 UTC)