8.21/3.61 YES 9.78/4.09 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 9.78/4.09 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.78/4.09 9.78/4.09 9.78/4.09 H-Termination with start terms of the given HASKELL could be proven: 9.78/4.09 9.78/4.09 (0) HASKELL 9.78/4.09 (1) BR [EQUIVALENT, 0 ms] 9.78/4.09 (2) HASKELL 9.78/4.09 (3) COR [EQUIVALENT, 0 ms] 9.78/4.09 (4) HASKELL 9.78/4.09 (5) Narrow [SOUND, 0 ms] 9.78/4.09 (6) AND 9.78/4.09 (7) QDP 9.78/4.09 (8) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.78/4.09 (9) YES 9.78/4.09 (10) QDP 9.78/4.09 (11) TransformationProof [EQUIVALENT, 0 ms] 9.78/4.09 (12) QDP 9.78/4.09 (13) UsableRulesProof [EQUIVALENT, 0 ms] 9.78/4.09 (14) QDP 9.78/4.09 (15) QReductionProof [EQUIVALENT, 0 ms] 9.78/4.09 (16) QDP 9.78/4.09 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.78/4.09 (18) YES 9.78/4.09 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (0) 9.78/4.09 Obligation: 9.78/4.09 mainModule Main 9.78/4.09 module Main where { 9.78/4.09 import qualified Prelude; 9.78/4.09 import qualified Queue; 9.78/4.09 } 9.78/4.09 module Queue where { 9.78/4.09 import qualified Main; 9.78/4.09 import qualified Prelude; 9.78/4.09 data Queue a = Q [a] [a] [a] ; 9.78/4.09 9.78/4.09 queueToList :: Queue a -> [a]; 9.78/4.09 queueToList (Q xs ys _) = xs ++ reverse ys; 9.78/4.09 9.78/4.09 } 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (1) BR (EQUIVALENT) 9.78/4.09 Replaced joker patterns by fresh variables and removed binding patterns. 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (2) 9.78/4.09 Obligation: 9.78/4.09 mainModule Main 9.78/4.09 module Main where { 9.78/4.09 import qualified Prelude; 9.78/4.09 import qualified Queue; 9.78/4.09 } 9.78/4.09 module Queue where { 9.78/4.09 import qualified Main; 9.78/4.09 import qualified Prelude; 9.78/4.09 data Queue a = Q [a] [a] [a] ; 9.78/4.09 9.78/4.09 queueToList :: Queue a -> [a]; 9.78/4.09 queueToList (Q xs ys vx) = xs ++ reverse ys; 9.78/4.09 9.78/4.09 } 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (3) COR (EQUIVALENT) 9.78/4.09 Cond Reductions: 9.78/4.09 The following Function with conditions 9.78/4.09 "undefined |Falseundefined; 9.78/4.09 " 9.78/4.09 is transformed to 9.78/4.09 "undefined = undefined1; 9.78/4.09 " 9.78/4.09 "undefined0 True = undefined; 9.78/4.09 " 9.78/4.09 "undefined1 = undefined0 False; 9.78/4.09 " 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (4) 9.78/4.09 Obligation: 9.78/4.09 mainModule Main 9.78/4.09 module Main where { 9.78/4.09 import qualified Prelude; 9.78/4.09 import qualified Queue; 9.78/4.09 } 9.78/4.09 module Queue where { 9.78/4.09 import qualified Main; 9.78/4.09 import qualified Prelude; 9.78/4.09 data Queue a = Q [a] [a] [a] ; 9.78/4.09 9.78/4.09 queueToList :: Queue a -> [a]; 9.78/4.09 queueToList (Q xs ys vx) = xs ++ reverse ys; 9.78/4.09 9.78/4.09 } 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (5) Narrow (SOUND) 9.78/4.09 Haskell To QDPs 9.78/4.09 9.78/4.09 digraph dp_graph { 9.78/4.09 node [outthreshold=100, inthreshold=100];1[label="Queue.queueToList",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 9.78/4.09 3[label="Queue.queueToList vy3",fontsize=16,color="burlywood",shape="triangle"];43[label="vy3/Queue.Q vy30 vy31 vy32",fontsize=10,color="white",style="solid",shape="box"];3 -> 43[label="",style="solid", color="burlywood", weight=9]; 9.78/4.09 43 -> 4[label="",style="solid", color="burlywood", weight=3]; 9.78/4.09 4[label="Queue.queueToList (Queue.Q vy30 vy31 vy32)",fontsize=16,color="black",shape="box"];4 -> 5[label="",style="solid", color="black", weight=3]; 9.78/4.09 5[label="vy30 ++ reverse vy31",fontsize=16,color="burlywood",shape="triangle"];44[label="vy30/vy300 : vy301",fontsize=10,color="white",style="solid",shape="box"];5 -> 44[label="",style="solid", color="burlywood", weight=9]; 9.78/4.09 44 -> 6[label="",style="solid", color="burlywood", weight=3]; 9.78/4.09 45[label="vy30/[]",fontsize=10,color="white",style="solid",shape="box"];5 -> 45[label="",style="solid", color="burlywood", weight=9]; 9.78/4.09 45 -> 7[label="",style="solid", color="burlywood", weight=3]; 9.78/4.09 6[label="(vy300 : vy301) ++ reverse vy31",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3]; 9.78/4.09 7[label="[] ++ reverse vy31",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3]; 9.78/4.09 8[label="vy300 : vy301 ++ reverse vy31",fontsize=16,color="green",shape="box"];8 -> 10[label="",style="dashed", color="green", weight=3]; 9.78/4.09 9[label="reverse vy31",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3]; 9.78/4.09 10 -> 5[label="",style="dashed", color="red", weight=0]; 9.78/4.09 10[label="vy301 ++ reverse vy31",fontsize=16,color="magenta"];10 -> 12[label="",style="dashed", color="magenta", weight=3]; 9.78/4.09 11[label="foldl (flip (:)) [] vy31",fontsize=16,color="burlywood",shape="box"];46[label="vy31/vy310 : vy311",fontsize=10,color="white",style="solid",shape="box"];11 -> 46[label="",style="solid", color="burlywood", weight=9]; 9.78/4.09 46 -> 13[label="",style="solid", color="burlywood", weight=3]; 9.78/4.09 47[label="vy31/[]",fontsize=10,color="white",style="solid",shape="box"];11 -> 47[label="",style="solid", color="burlywood", weight=9]; 9.78/4.09 47 -> 14[label="",style="solid", color="burlywood", weight=3]; 9.78/4.09 12[label="vy301",fontsize=16,color="green",shape="box"];13[label="foldl (flip (:)) [] (vy310 : vy311)",fontsize=16,color="black",shape="box"];13 -> 15[label="",style="solid", color="black", weight=3]; 9.78/4.09 14[label="foldl (flip (:)) [] []",fontsize=16,color="black",shape="box"];14 -> 16[label="",style="solid", color="black", weight=3]; 9.78/4.09 15[label="foldl (flip (:)) (flip (:) [] vy310) vy311",fontsize=16,color="burlywood",shape="box"];48[label="vy311/vy3110 : vy3111",fontsize=10,color="white",style="solid",shape="box"];15 -> 48[label="",style="solid", color="burlywood", weight=9]; 9.78/4.09 48 -> 17[label="",style="solid", color="burlywood", weight=3]; 9.78/4.09 49[label="vy311/[]",fontsize=10,color="white",style="solid",shape="box"];15 -> 49[label="",style="solid", color="burlywood", weight=9]; 9.78/4.09 49 -> 18[label="",style="solid", color="burlywood", weight=3]; 9.78/4.09 16[label="[]",fontsize=16,color="green",shape="box"];17[label="foldl (flip (:)) (flip (:) [] vy310) (vy3110 : vy3111)",fontsize=16,color="black",shape="box"];17 -> 19[label="",style="solid", color="black", weight=3]; 9.78/4.09 18[label="foldl (flip (:)) (flip (:) [] vy310) []",fontsize=16,color="black",shape="box"];18 -> 20[label="",style="solid", color="black", weight=3]; 9.78/4.09 19 -> 26[label="",style="dashed", color="red", weight=0]; 9.78/4.09 19[label="foldl (flip (:)) (flip (:) (flip (:) [] vy310) vy3110) vy3111",fontsize=16,color="magenta"];19 -> 27[label="",style="dashed", color="magenta", weight=3]; 9.78/4.09 19 -> 28[label="",style="dashed", color="magenta", weight=3]; 9.78/4.09 19 -> 29[label="",style="dashed", color="magenta", weight=3]; 9.78/4.09 19 -> 30[label="",style="dashed", color="magenta", weight=3]; 9.78/4.09 20[label="flip (:) [] vy310",fontsize=16,color="black",shape="box"];20 -> 23[label="",style="solid", color="black", weight=3]; 9.78/4.09 27[label="[]",fontsize=16,color="green",shape="box"];28[label="vy3110",fontsize=16,color="green",shape="box"];29[label="vy310",fontsize=16,color="green",shape="box"];30[label="vy3111",fontsize=16,color="green",shape="box"];26[label="foldl (flip (:)) (flip (:) (flip (:) vy4 vy3110) vy31110) vy31111",fontsize=16,color="burlywood",shape="triangle"];50[label="vy31111/vy311110 : vy311111",fontsize=10,color="white",style="solid",shape="box"];26 -> 50[label="",style="solid", color="burlywood", weight=9]; 9.78/4.09 50 -> 32[label="",style="solid", color="burlywood", weight=3]; 9.78/4.09 51[label="vy31111/[]",fontsize=10,color="white",style="solid",shape="box"];26 -> 51[label="",style="solid", color="burlywood", weight=9]; 9.78/4.09 51 -> 33[label="",style="solid", color="burlywood", weight=3]; 9.78/4.09 23[label="(:) vy310 []",fontsize=16,color="green",shape="box"];32[label="foldl (flip (:)) (flip (:) (flip (:) vy4 vy3110) vy31110) (vy311110 : vy311111)",fontsize=16,color="black",shape="box"];32 -> 34[label="",style="solid", color="black", weight=3]; 9.78/4.09 33[label="foldl (flip (:)) (flip (:) (flip (:) vy4 vy3110) vy31110) []",fontsize=16,color="black",shape="box"];33 -> 35[label="",style="solid", color="black", weight=3]; 9.78/4.09 34 -> 26[label="",style="dashed", color="red", weight=0]; 9.78/4.09 34[label="foldl (flip (:)) (flip (:) (flip (:) (flip (:) vy4 vy3110) vy31110) vy311110) vy311111",fontsize=16,color="magenta"];34 -> 36[label="",style="dashed", color="magenta", weight=3]; 9.78/4.09 34 -> 37[label="",style="dashed", color="magenta", weight=3]; 9.78/4.09 34 -> 38[label="",style="dashed", color="magenta", weight=3]; 9.78/4.09 34 -> 39[label="",style="dashed", color="magenta", weight=3]; 9.78/4.09 35[label="flip (:) (flip (:) vy4 vy3110) vy31110",fontsize=16,color="black",shape="box"];35 -> 40[label="",style="solid", color="black", weight=3]; 9.78/4.09 36[label="flip (:) vy4 vy3110",fontsize=16,color="black",shape="triangle"];36 -> 41[label="",style="solid", color="black", weight=3]; 9.78/4.09 37[label="vy311110",fontsize=16,color="green",shape="box"];38[label="vy31110",fontsize=16,color="green",shape="box"];39[label="vy311111",fontsize=16,color="green",shape="box"];40[label="(:) vy31110 flip (:) vy4 vy3110",fontsize=16,color="green",shape="box"];40 -> 42[label="",style="dashed", color="green", weight=3]; 9.78/4.09 41[label="(:) vy3110 vy4",fontsize=16,color="green",shape="box"];42 -> 36[label="",style="dashed", color="red", weight=0]; 9.78/4.09 42[label="flip (:) vy4 vy3110",fontsize=16,color="magenta"];} 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (6) 9.78/4.09 Complex Obligation (AND) 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (7) 9.78/4.09 Obligation: 9.78/4.09 Q DP problem: 9.78/4.09 The TRS P consists of the following rules: 9.78/4.09 9.78/4.09 new_psPs(:(vy300, vy301), vy31, h) -> new_psPs(vy301, vy31, h) 9.78/4.09 9.78/4.09 R is empty. 9.78/4.09 Q is empty. 9.78/4.09 We have to consider all minimal (P,Q,R)-chains. 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (8) QDPSizeChangeProof (EQUIVALENT) 9.78/4.09 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.78/4.09 9.78/4.09 From the DPs we obtained the following set of size-change graphs: 9.78/4.09 *new_psPs(:(vy300, vy301), vy31, h) -> new_psPs(vy301, vy31, h) 9.78/4.09 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 9.78/4.09 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (9) 9.78/4.09 YES 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (10) 9.78/4.09 Obligation: 9.78/4.09 Q DP problem: 9.78/4.09 The TRS P consists of the following rules: 9.78/4.09 9.78/4.09 new_foldl(vy4, vy3110, vy31110, :(vy311110, vy311111), h) -> new_foldl(new_flip(vy4, vy3110, h), vy31110, vy311110, vy311111, h) 9.78/4.09 9.78/4.09 The TRS R consists of the following rules: 9.78/4.09 9.78/4.09 new_flip(vy4, vy3110, h) -> :(vy3110, vy4) 9.78/4.09 9.78/4.09 The set Q consists of the following terms: 9.78/4.09 9.78/4.09 new_flip(x0, x1, x2) 9.78/4.09 9.78/4.09 We have to consider all minimal (P,Q,R)-chains. 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (11) TransformationProof (EQUIVALENT) 9.78/4.09 By rewriting [LPAR04] the rule new_foldl(vy4, vy3110, vy31110, :(vy311110, vy311111), h) -> new_foldl(new_flip(vy4, vy3110, h), vy31110, vy311110, vy311111, h) at position [0] we obtained the following new rules [LPAR04]: 9.78/4.09 9.78/4.09 (new_foldl(vy4, vy3110, vy31110, :(vy311110, vy311111), h) -> new_foldl(:(vy3110, vy4), vy31110, vy311110, vy311111, h),new_foldl(vy4, vy3110, vy31110, :(vy311110, vy311111), h) -> new_foldl(:(vy3110, vy4), vy31110, vy311110, vy311111, h)) 9.78/4.09 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (12) 9.78/4.09 Obligation: 9.78/4.09 Q DP problem: 9.78/4.09 The TRS P consists of the following rules: 9.78/4.09 9.78/4.09 new_foldl(vy4, vy3110, vy31110, :(vy311110, vy311111), h) -> new_foldl(:(vy3110, vy4), vy31110, vy311110, vy311111, h) 9.78/4.09 9.78/4.09 The TRS R consists of the following rules: 9.78/4.09 9.78/4.09 new_flip(vy4, vy3110, h) -> :(vy3110, vy4) 9.78/4.09 9.78/4.09 The set Q consists of the following terms: 9.78/4.09 9.78/4.09 new_flip(x0, x1, x2) 9.78/4.09 9.78/4.09 We have to consider all minimal (P,Q,R)-chains. 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (13) UsableRulesProof (EQUIVALENT) 9.78/4.09 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.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (14) 9.78/4.09 Obligation: 9.78/4.09 Q DP problem: 9.78/4.09 The TRS P consists of the following rules: 9.78/4.09 9.78/4.09 new_foldl(vy4, vy3110, vy31110, :(vy311110, vy311111), h) -> new_foldl(:(vy3110, vy4), vy31110, vy311110, vy311111, h) 9.78/4.09 9.78/4.09 R is empty. 9.78/4.09 The set Q consists of the following terms: 9.78/4.09 9.78/4.09 new_flip(x0, x1, x2) 9.78/4.09 9.78/4.09 We have to consider all minimal (P,Q,R)-chains. 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (15) QReductionProof (EQUIVALENT) 9.78/4.09 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 9.78/4.09 9.78/4.09 new_flip(x0, x1, x2) 9.78/4.09 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (16) 9.78/4.09 Obligation: 9.78/4.09 Q DP problem: 9.78/4.09 The TRS P consists of the following rules: 9.78/4.09 9.78/4.09 new_foldl(vy4, vy3110, vy31110, :(vy311110, vy311111), h) -> new_foldl(:(vy3110, vy4), vy31110, vy311110, vy311111, h) 9.78/4.09 9.78/4.09 R is empty. 9.78/4.09 Q is empty. 9.78/4.09 We have to consider all minimal (P,Q,R)-chains. 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (17) QDPSizeChangeProof (EQUIVALENT) 9.78/4.09 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.78/4.09 9.78/4.09 From the DPs we obtained the following set of size-change graphs: 9.78/4.09 *new_foldl(vy4, vy3110, vy31110, :(vy311110, vy311111), h) -> new_foldl(:(vy3110, vy4), vy31110, vy311110, vy311111, h) 9.78/4.09 The graph contains the following edges 3 >= 2, 4 > 3, 4 > 4, 5 >= 5 9.78/4.09 9.78/4.09 9.78/4.09 ---------------------------------------- 9.78/4.09 9.78/4.09 (18) 9.78/4.09 YES 10.04/4.16 EOF