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