7.92/3.58 YES 9.61/4.04 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 9.61/4.04 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.61/4.04 9.61/4.04 9.61/4.04 H-Termination with start terms of the given HASKELL could be proven: 9.61/4.04 9.61/4.04 (0) HASKELL 9.61/4.04 (1) BR [EQUIVALENT, 0 ms] 9.61/4.04 (2) HASKELL 9.61/4.04 (3) COR [EQUIVALENT, 0 ms] 9.61/4.04 (4) HASKELL 9.61/4.04 (5) Narrow [SOUND, 0 ms] 9.61/4.04 (6) QDP 9.61/4.04 (7) TransformationProof [EQUIVALENT, 0 ms] 9.61/4.04 (8) QDP 9.61/4.04 (9) UsableRulesProof [EQUIVALENT, 0 ms] 9.61/4.04 (10) QDP 9.61/4.04 (11) QReductionProof [EQUIVALENT, 0 ms] 9.61/4.04 (12) QDP 9.61/4.04 (13) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.61/4.04 (14) YES 9.61/4.04 9.61/4.04 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (0) 9.61/4.04 Obligation: 9.61/4.04 mainModule Main 9.61/4.04 module Main where { 9.61/4.04 import qualified Prelude; 9.61/4.04 data List a = Cons a (List a) | Nil ; 9.61/4.04 9.61/4.04 flip :: (c -> a -> b) -> a -> c -> b; 9.61/4.04 flip f x y = f y x; 9.61/4.04 9.61/4.04 foldl :: (a -> b -> a) -> a -> List b -> a; 9.61/4.04 foldl f z Nil = z; 9.61/4.04 foldl f z (Cons x xs) = foldl f (f z x) xs; 9.61/4.04 9.61/4.04 reverse :: List a -> List a; 9.61/4.04 reverse = foldl (flip Cons) Nil; 9.61/4.04 9.61/4.04 } 9.61/4.04 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (1) BR (EQUIVALENT) 9.61/4.04 Replaced joker patterns by fresh variables and removed binding patterns. 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (2) 9.61/4.04 Obligation: 9.61/4.04 mainModule Main 9.61/4.04 module Main where { 9.61/4.04 import qualified Prelude; 9.61/4.04 data List a = Cons a (List a) | Nil ; 9.61/4.04 9.61/4.04 flip :: (c -> a -> b) -> a -> c -> b; 9.61/4.04 flip f x y = f y x; 9.61/4.04 9.61/4.04 foldl :: (a -> b -> a) -> a -> List b -> a; 9.61/4.04 foldl f z Nil = z; 9.61/4.04 foldl f z (Cons x xs) = foldl f (f z x) xs; 9.61/4.04 9.61/4.04 reverse :: List a -> List a; 9.61/4.04 reverse = foldl (flip Cons) Nil; 9.61/4.04 9.61/4.04 } 9.61/4.04 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (3) COR (EQUIVALENT) 9.61/4.04 Cond Reductions: 9.61/4.04 The following Function with conditions 9.61/4.04 "undefined |Falseundefined; 9.61/4.04 " 9.61/4.04 is transformed to 9.61/4.04 "undefined = undefined1; 9.61/4.04 " 9.61/4.04 "undefined0 True = undefined; 9.61/4.04 " 9.61/4.04 "undefined1 = undefined0 False; 9.61/4.04 " 9.61/4.04 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (4) 9.61/4.04 Obligation: 9.61/4.04 mainModule Main 9.61/4.04 module Main where { 9.61/4.04 import qualified Prelude; 9.61/4.04 data List a = Cons a (List a) | Nil ; 9.61/4.04 9.61/4.04 flip :: (c -> a -> b) -> a -> c -> b; 9.61/4.04 flip f x y = f y x; 9.61/4.04 9.61/4.04 foldl :: (a -> b -> a) -> a -> List b -> a; 9.61/4.04 foldl f z Nil = z; 9.61/4.04 foldl f z (Cons x xs) = foldl f (f z x) xs; 9.61/4.04 9.61/4.04 reverse :: List a -> List a; 9.61/4.04 reverse = foldl (flip Cons) Nil; 9.61/4.04 9.61/4.04 } 9.61/4.04 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (5) Narrow (SOUND) 9.61/4.04 Haskell To QDPs 9.61/4.04 9.61/4.04 digraph dp_graph { 9.61/4.04 node [outthreshold=100, inthreshold=100];1[label="reverse",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 9.61/4.04 3[label="reverse vx3",fontsize=16,color="black",shape="triangle"];3 -> 4[label="",style="solid", color="black", weight=3]; 9.61/4.04 4[label="foldl (flip Cons) Nil vx3",fontsize=16,color="burlywood",shape="box"];35[label="vx3/Cons vx30 vx31",fontsize=10,color="white",style="solid",shape="box"];4 -> 35[label="",style="solid", color="burlywood", weight=9]; 9.61/4.04 35 -> 5[label="",style="solid", color="burlywood", weight=3]; 9.61/4.04 36[label="vx3/Nil",fontsize=10,color="white",style="solid",shape="box"];4 -> 36[label="",style="solid", color="burlywood", weight=9]; 9.61/4.04 36 -> 6[label="",style="solid", color="burlywood", weight=3]; 9.61/4.04 5[label="foldl (flip Cons) Nil (Cons vx30 vx31)",fontsize=16,color="black",shape="box"];5 -> 7[label="",style="solid", color="black", weight=3]; 9.61/4.04 6[label="foldl (flip Cons) Nil Nil",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3]; 9.61/4.04 7[label="foldl (flip Cons) (flip Cons Nil vx30) vx31",fontsize=16,color="burlywood",shape="box"];37[label="vx31/Cons vx310 vx311",fontsize=10,color="white",style="solid",shape="box"];7 -> 37[label="",style="solid", color="burlywood", weight=9]; 9.61/4.04 37 -> 9[label="",style="solid", color="burlywood", weight=3]; 9.61/4.04 38[label="vx31/Nil",fontsize=10,color="white",style="solid",shape="box"];7 -> 38[label="",style="solid", color="burlywood", weight=9]; 9.61/4.04 38 -> 10[label="",style="solid", color="burlywood", weight=3]; 9.61/4.04 8[label="Nil",fontsize=16,color="green",shape="box"];9[label="foldl (flip Cons) (flip Cons Nil vx30) (Cons vx310 vx311)",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3]; 9.61/4.04 10[label="foldl (flip Cons) (flip Cons Nil vx30) Nil",fontsize=16,color="black",shape="box"];10 -> 12[label="",style="solid", color="black", weight=3]; 9.61/4.04 11 -> 18[label="",style="dashed", color="red", weight=0]; 9.61/4.04 11[label="foldl (flip Cons) (flip Cons (flip Cons Nil vx30) vx310) vx311",fontsize=16,color="magenta"];11 -> 19[label="",style="dashed", color="magenta", weight=3]; 9.61/4.04 11 -> 20[label="",style="dashed", color="magenta", weight=3]; 9.61/4.04 11 -> 21[label="",style="dashed", color="magenta", weight=3]; 9.61/4.04 11 -> 22[label="",style="dashed", color="magenta", weight=3]; 9.61/4.04 12[label="flip Cons Nil vx30",fontsize=16,color="black",shape="box"];12 -> 15[label="",style="solid", color="black", weight=3]; 9.61/4.04 19[label="vx310",fontsize=16,color="green",shape="box"];20[label="vx30",fontsize=16,color="green",shape="box"];21[label="Nil",fontsize=16,color="green",shape="box"];22[label="vx311",fontsize=16,color="green",shape="box"];18[label="foldl (flip Cons) (flip Cons (flip Cons vx4 vx310) vx3110) vx3111",fontsize=16,color="burlywood",shape="triangle"];39[label="vx3111/Cons vx31110 vx31111",fontsize=10,color="white",style="solid",shape="box"];18 -> 39[label="",style="solid", color="burlywood", weight=9]; 9.61/4.04 39 -> 24[label="",style="solid", color="burlywood", weight=3]; 9.61/4.04 40[label="vx3111/Nil",fontsize=10,color="white",style="solid",shape="box"];18 -> 40[label="",style="solid", color="burlywood", weight=9]; 9.61/4.04 40 -> 25[label="",style="solid", color="burlywood", weight=3]; 9.61/4.04 15[label="Cons vx30 Nil",fontsize=16,color="green",shape="box"];24[label="foldl (flip Cons) (flip Cons (flip Cons vx4 vx310) vx3110) (Cons vx31110 vx31111)",fontsize=16,color="black",shape="box"];24 -> 26[label="",style="solid", color="black", weight=3]; 9.61/4.04 25[label="foldl (flip Cons) (flip Cons (flip Cons vx4 vx310) vx3110) Nil",fontsize=16,color="black",shape="box"];25 -> 27[label="",style="solid", color="black", weight=3]; 9.61/4.04 26 -> 18[label="",style="dashed", color="red", weight=0]; 9.61/4.04 26[label="foldl (flip Cons) (flip Cons (flip Cons (flip Cons vx4 vx310) vx3110) vx31110) vx31111",fontsize=16,color="magenta"];26 -> 28[label="",style="dashed", color="magenta", weight=3]; 9.61/4.04 26 -> 29[label="",style="dashed", color="magenta", weight=3]; 9.61/4.04 26 -> 30[label="",style="dashed", color="magenta", weight=3]; 9.61/4.04 26 -> 31[label="",style="dashed", color="magenta", weight=3]; 9.61/4.04 27[label="flip Cons (flip Cons vx4 vx310) vx3110",fontsize=16,color="black",shape="box"];27 -> 32[label="",style="solid", color="black", weight=3]; 9.61/4.04 28[label="vx31110",fontsize=16,color="green",shape="box"];29[label="vx3110",fontsize=16,color="green",shape="box"];30[label="flip Cons vx4 vx310",fontsize=16,color="black",shape="triangle"];30 -> 33[label="",style="solid", color="black", weight=3]; 9.61/4.04 31[label="vx31111",fontsize=16,color="green",shape="box"];32[label="Cons vx3110 (flip Cons vx4 vx310)",fontsize=16,color="green",shape="box"];32 -> 34[label="",style="dashed", color="green", weight=3]; 9.61/4.04 33[label="Cons vx310 vx4",fontsize=16,color="green",shape="box"];34 -> 30[label="",style="dashed", color="red", weight=0]; 9.61/4.04 34[label="flip Cons vx4 vx310",fontsize=16,color="magenta"];} 9.61/4.04 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (6) 9.61/4.04 Obligation: 9.61/4.04 Q DP problem: 9.61/4.04 The TRS P consists of the following rules: 9.61/4.04 9.61/4.04 new_foldl(vx4, vx310, vx3110, Cons(vx31110, vx31111), h) -> new_foldl(new_flip(vx4, vx310, h), vx3110, vx31110, vx31111, h) 9.61/4.04 9.61/4.04 The TRS R consists of the following rules: 9.61/4.04 9.61/4.04 new_flip(vx4, vx310, h) -> Cons(vx310, vx4) 9.61/4.04 9.61/4.04 The set Q consists of the following terms: 9.61/4.04 9.61/4.04 new_flip(x0, x1, x2) 9.61/4.04 9.61/4.04 We have to consider all minimal (P,Q,R)-chains. 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (7) TransformationProof (EQUIVALENT) 9.61/4.04 By rewriting [LPAR04] the rule new_foldl(vx4, vx310, vx3110, Cons(vx31110, vx31111), h) -> new_foldl(new_flip(vx4, vx310, h), vx3110, vx31110, vx31111, h) at position [0] we obtained the following new rules [LPAR04]: 9.61/4.04 9.61/4.04 (new_foldl(vx4, vx310, vx3110, Cons(vx31110, vx31111), h) -> new_foldl(Cons(vx310, vx4), vx3110, vx31110, vx31111, h),new_foldl(vx4, vx310, vx3110, Cons(vx31110, vx31111), h) -> new_foldl(Cons(vx310, vx4), vx3110, vx31110, vx31111, h)) 9.61/4.04 9.61/4.04 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (8) 9.61/4.04 Obligation: 9.61/4.04 Q DP problem: 9.61/4.04 The TRS P consists of the following rules: 9.61/4.04 9.61/4.04 new_foldl(vx4, vx310, vx3110, Cons(vx31110, vx31111), h) -> new_foldl(Cons(vx310, vx4), vx3110, vx31110, vx31111, h) 9.61/4.04 9.61/4.04 The TRS R consists of the following rules: 9.61/4.04 9.61/4.04 new_flip(vx4, vx310, h) -> Cons(vx310, vx4) 9.61/4.04 9.61/4.04 The set Q consists of the following terms: 9.61/4.04 9.61/4.04 new_flip(x0, x1, x2) 9.61/4.04 9.61/4.04 We have to consider all minimal (P,Q,R)-chains. 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (9) UsableRulesProof (EQUIVALENT) 9.61/4.04 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (10) 9.61/4.04 Obligation: 9.61/4.04 Q DP problem: 9.61/4.04 The TRS P consists of the following rules: 9.61/4.04 9.61/4.04 new_foldl(vx4, vx310, vx3110, Cons(vx31110, vx31111), h) -> new_foldl(Cons(vx310, vx4), vx3110, vx31110, vx31111, h) 9.61/4.04 9.61/4.04 R is empty. 9.61/4.04 The set Q consists of the following terms: 9.61/4.04 9.61/4.04 new_flip(x0, x1, x2) 9.61/4.04 9.61/4.04 We have to consider all minimal (P,Q,R)-chains. 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (11) QReductionProof (EQUIVALENT) 9.61/4.04 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 9.61/4.04 9.61/4.04 new_flip(x0, x1, x2) 9.61/4.04 9.61/4.04 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (12) 9.61/4.04 Obligation: 9.61/4.04 Q DP problem: 9.61/4.04 The TRS P consists of the following rules: 9.61/4.04 9.61/4.04 new_foldl(vx4, vx310, vx3110, Cons(vx31110, vx31111), h) -> new_foldl(Cons(vx310, vx4), vx3110, vx31110, vx31111, h) 9.61/4.04 9.61/4.04 R is empty. 9.61/4.04 Q is empty. 9.61/4.04 We have to consider all minimal (P,Q,R)-chains. 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (13) QDPSizeChangeProof (EQUIVALENT) 9.61/4.04 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 9.61/4.04 9.61/4.04 From the DPs we obtained the following set of size-change graphs: 9.61/4.04 *new_foldl(vx4, vx310, vx3110, Cons(vx31110, vx31111), h) -> new_foldl(Cons(vx310, vx4), vx3110, vx31110, vx31111, h) 9.61/4.04 The graph contains the following edges 3 >= 2, 4 > 3, 4 > 4, 5 >= 5 9.61/4.04 9.61/4.04 9.61/4.04 ---------------------------------------- 9.61/4.04 9.61/4.04 (14) 9.61/4.04 YES 9.61/4.08 EOF