7.96/3.57 YES 9.63/4.08 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 9.63/4.08 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.63/4.08 9.63/4.08 9.63/4.08 H-Termination with start terms of the given HASKELL could be proven: 9.63/4.08 9.63/4.08 (0) HASKELL 9.63/4.08 (1) BR [EQUIVALENT, 0 ms] 9.63/4.08 (2) HASKELL 9.63/4.08 (3) COR [EQUIVALENT, 0 ms] 9.63/4.08 (4) HASKELL 9.63/4.08 (5) Narrow [SOUND, 0 ms] 9.63/4.08 (6) AND 9.63/4.08 (7) QDP 9.63/4.08 (8) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.63/4.08 (9) YES 9.63/4.08 (10) QDP 9.63/4.08 (11) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.63/4.08 (12) YES 9.63/4.08 (13) QDP 9.63/4.08 (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.63/4.08 (15) YES 9.63/4.08 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (0) 9.63/4.08 Obligation: 9.63/4.08 mainModule Main 9.63/4.08 module Main where { 9.63/4.08 import qualified Prelude; 9.63/4.08 data List a = Cons a (List a) | Nil ; 9.63/4.08 9.63/4.08 data Tup0 = Tup0 ; 9.63/4.08 9.63/4.08 foldr :: (a -> b -> b) -> b -> List a -> b; 9.63/4.08 foldr f z Nil = z; 9.63/4.08 foldr f z (Cons x xs) = f x (foldr f z xs); 9.63/4.08 9.63/4.08 gtGt0 q vv = q; 9.63/4.08 9.63/4.08 gtGtEsNil :: List a -> (a -> List b) -> List b; 9.63/4.08 gtGtEsNil (Cons x xs) f = psPs (f x) (gtGtEsNil xs f); 9.63/4.08 gtGtEsNil Nil f = Nil; 9.63/4.08 9.63/4.08 gtGtNil :: List a -> List b -> List b; 9.63/4.08 gtGtNil p q = gtGtEsNil p (gtGt0 q); 9.63/4.08 9.63/4.08 psPs :: List a -> List a -> List a; 9.63/4.08 psPs Nil ys = ys; 9.63/4.08 psPs (Cons x xs) ys = Cons x (psPs xs ys); 9.63/4.08 9.63/4.08 returnNil :: a -> List a; 9.63/4.08 returnNil x = Cons x Nil; 9.63/4.08 9.63/4.08 sequence_Nil :: List (List a) -> List Tup0; 9.63/4.08 sequence_Nil = foldr gtGtNil (returnNil Tup0); 9.63/4.08 9.63/4.08 } 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (1) BR (EQUIVALENT) 9.63/4.08 Replaced joker patterns by fresh variables and removed binding patterns. 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (2) 9.63/4.08 Obligation: 9.63/4.08 mainModule Main 9.63/4.08 module Main where { 9.63/4.08 import qualified Prelude; 9.63/4.08 data List a = Cons a (List a) | Nil ; 9.63/4.08 9.63/4.08 data Tup0 = Tup0 ; 9.63/4.08 9.63/4.08 foldr :: (a -> b -> b) -> b -> List a -> b; 9.63/4.08 foldr f z Nil = z; 9.63/4.08 foldr f z (Cons x xs) = f x (foldr f z xs); 9.63/4.08 9.63/4.08 gtGt0 q vv = q; 9.63/4.08 9.63/4.08 gtGtEsNil :: List a -> (a -> List b) -> List b; 9.63/4.08 gtGtEsNil (Cons x xs) f = psPs (f x) (gtGtEsNil xs f); 9.63/4.08 gtGtEsNil Nil f = Nil; 9.63/4.08 9.63/4.08 gtGtNil :: List b -> List a -> List a; 9.63/4.08 gtGtNil p q = gtGtEsNil p (gtGt0 q); 9.63/4.08 9.63/4.08 psPs :: List a -> List a -> List a; 9.63/4.08 psPs Nil ys = ys; 9.63/4.08 psPs (Cons x xs) ys = Cons x (psPs xs ys); 9.63/4.08 9.63/4.08 returnNil :: a -> List a; 9.63/4.08 returnNil x = Cons x Nil; 9.63/4.08 9.63/4.08 sequence_Nil :: List (List a) -> List Tup0; 9.63/4.08 sequence_Nil = foldr gtGtNil (returnNil Tup0); 9.63/4.08 9.63/4.08 } 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (3) COR (EQUIVALENT) 9.63/4.08 Cond Reductions: 9.63/4.08 The following Function with conditions 9.63/4.08 "undefined |Falseundefined; 9.63/4.08 " 9.63/4.08 is transformed to 9.63/4.08 "undefined = undefined1; 9.63/4.08 " 9.63/4.08 "undefined0 True = undefined; 9.63/4.08 " 9.63/4.08 "undefined1 = undefined0 False; 9.63/4.08 " 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (4) 9.63/4.08 Obligation: 9.63/4.08 mainModule Main 9.63/4.08 module Main where { 9.63/4.08 import qualified Prelude; 9.63/4.08 data List a = Cons a (List a) | Nil ; 9.63/4.08 9.63/4.08 data Tup0 = Tup0 ; 9.63/4.08 9.63/4.08 foldr :: (a -> b -> b) -> b -> List a -> b; 9.63/4.08 foldr f z Nil = z; 9.63/4.08 foldr f z (Cons x xs) = f x (foldr f z xs); 9.63/4.08 9.63/4.08 gtGt0 q vv = q; 9.63/4.08 9.63/4.08 gtGtEsNil :: List b -> (b -> List a) -> List a; 9.63/4.08 gtGtEsNil (Cons x xs) f = psPs (f x) (gtGtEsNil xs f); 9.63/4.08 gtGtEsNil Nil f = Nil; 9.63/4.08 9.63/4.08 gtGtNil :: List b -> List a -> List a; 9.63/4.08 gtGtNil p q = gtGtEsNil p (gtGt0 q); 9.63/4.08 9.63/4.08 psPs :: List a -> List a -> List a; 9.63/4.08 psPs Nil ys = ys; 9.63/4.08 psPs (Cons x xs) ys = Cons x (psPs xs ys); 9.63/4.08 9.63/4.08 returnNil :: a -> List a; 9.63/4.08 returnNil x = Cons x Nil; 9.63/4.08 9.63/4.08 sequence_Nil :: List (List a) -> List Tup0; 9.63/4.08 sequence_Nil = foldr gtGtNil (returnNil Tup0); 9.63/4.08 9.63/4.08 } 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (5) Narrow (SOUND) 9.63/4.08 Haskell To QDPs 9.63/4.08 9.63/4.08 digraph dp_graph { 9.63/4.08 node [outthreshold=100, inthreshold=100];1[label="sequence_Nil",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 9.63/4.08 3[label="sequence_Nil vy3",fontsize=16,color="black",shape="triangle"];3 -> 4[label="",style="solid", color="black", weight=3]; 9.63/4.08 4[label="foldr gtGtNil (returnNil Tup0) vy3",fontsize=16,color="burlywood",shape="triangle"];28[label="vy3/Cons vy30 vy31",fontsize=10,color="white",style="solid",shape="box"];4 -> 28[label="",style="solid", color="burlywood", weight=9]; 9.63/4.08 28 -> 5[label="",style="solid", color="burlywood", weight=3]; 9.63/4.08 29[label="vy3/Nil",fontsize=10,color="white",style="solid",shape="box"];4 -> 29[label="",style="solid", color="burlywood", weight=9]; 9.63/4.08 29 -> 6[label="",style="solid", color="burlywood", weight=3]; 9.63/4.08 5[label="foldr gtGtNil (returnNil Tup0) (Cons vy30 vy31)",fontsize=16,color="black",shape="box"];5 -> 7[label="",style="solid", color="black", weight=3]; 9.63/4.08 6[label="foldr gtGtNil (returnNil Tup0) Nil",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3]; 9.63/4.08 7 -> 9[label="",style="dashed", color="red", weight=0]; 9.63/4.08 7[label="gtGtNil vy30 (foldr gtGtNil (returnNil Tup0) vy31)",fontsize=16,color="magenta"];7 -> 10[label="",style="dashed", color="magenta", weight=3]; 9.63/4.08 8[label="returnNil Tup0",fontsize=16,color="black",shape="box"];8 -> 11[label="",style="solid", color="black", weight=3]; 9.63/4.08 10 -> 4[label="",style="dashed", color="red", weight=0]; 9.63/4.08 10[label="foldr gtGtNil (returnNil Tup0) vy31",fontsize=16,color="magenta"];10 -> 12[label="",style="dashed", color="magenta", weight=3]; 9.63/4.08 9[label="gtGtNil vy30 vy4",fontsize=16,color="black",shape="triangle"];9 -> 13[label="",style="solid", color="black", weight=3]; 9.63/4.08 11[label="Cons Tup0 Nil",fontsize=16,color="green",shape="box"];12[label="vy31",fontsize=16,color="green",shape="box"];13[label="gtGtEsNil vy30 (gtGt0 vy4)",fontsize=16,color="burlywood",shape="triangle"];30[label="vy30/Cons vy300 vy301",fontsize=10,color="white",style="solid",shape="box"];13 -> 30[label="",style="solid", color="burlywood", weight=9]; 9.63/4.08 30 -> 14[label="",style="solid", color="burlywood", weight=3]; 9.63/4.08 31[label="vy30/Nil",fontsize=10,color="white",style="solid",shape="box"];13 -> 31[label="",style="solid", color="burlywood", weight=9]; 9.63/4.08 31 -> 15[label="",style="solid", color="burlywood", weight=3]; 9.63/4.08 14[label="gtGtEsNil (Cons vy300 vy301) (gtGt0 vy4)",fontsize=16,color="black",shape="box"];14 -> 16[label="",style="solid", color="black", weight=3]; 9.63/4.08 15[label="gtGtEsNil Nil (gtGt0 vy4)",fontsize=16,color="black",shape="box"];15 -> 17[label="",style="solid", color="black", weight=3]; 9.63/4.08 16 -> 18[label="",style="dashed", color="red", weight=0]; 9.63/4.08 16[label="psPs (gtGt0 vy4 vy300) (gtGtEsNil vy301 (gtGt0 vy4))",fontsize=16,color="magenta"];16 -> 19[label="",style="dashed", color="magenta", weight=3]; 9.63/4.08 17[label="Nil",fontsize=16,color="green",shape="box"];19 -> 13[label="",style="dashed", color="red", weight=0]; 9.63/4.08 19[label="gtGtEsNil vy301 (gtGt0 vy4)",fontsize=16,color="magenta"];19 -> 20[label="",style="dashed", color="magenta", weight=3]; 9.63/4.08 18[label="psPs (gtGt0 vy4 vy300) vy5",fontsize=16,color="black",shape="triangle"];18 -> 21[label="",style="solid", color="black", weight=3]; 9.63/4.08 20[label="vy301",fontsize=16,color="green",shape="box"];21[label="psPs vy4 vy5",fontsize=16,color="burlywood",shape="triangle"];32[label="vy4/Cons vy40 vy41",fontsize=10,color="white",style="solid",shape="box"];21 -> 32[label="",style="solid", color="burlywood", weight=9]; 9.63/4.08 32 -> 22[label="",style="solid", color="burlywood", weight=3]; 9.63/4.08 33[label="vy4/Nil",fontsize=10,color="white",style="solid",shape="box"];21 -> 33[label="",style="solid", color="burlywood", weight=9]; 9.63/4.08 33 -> 23[label="",style="solid", color="burlywood", weight=3]; 9.63/4.08 22[label="psPs (Cons vy40 vy41) vy5",fontsize=16,color="black",shape="box"];22 -> 24[label="",style="solid", color="black", weight=3]; 9.63/4.08 23[label="psPs Nil vy5",fontsize=16,color="black",shape="box"];23 -> 25[label="",style="solid", color="black", weight=3]; 9.63/4.08 24[label="Cons vy40 (psPs vy41 vy5)",fontsize=16,color="green",shape="box"];24 -> 26[label="",style="dashed", color="green", weight=3]; 9.63/4.08 25[label="vy5",fontsize=16,color="green",shape="box"];26 -> 21[label="",style="dashed", color="red", weight=0]; 9.63/4.08 26[label="psPs vy41 vy5",fontsize=16,color="magenta"];26 -> 27[label="",style="dashed", color="magenta", weight=3]; 9.63/4.08 27[label="vy41",fontsize=16,color="green",shape="box"];} 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (6) 9.63/4.08 Complex Obligation (AND) 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (7) 9.63/4.08 Obligation: 9.63/4.08 Q DP problem: 9.63/4.08 The TRS P consists of the following rules: 9.63/4.08 9.63/4.08 new_foldr(Cons(vy30, vy31), h) -> new_foldr(vy31, h) 9.63/4.08 9.63/4.08 R is empty. 9.63/4.08 Q is empty. 9.63/4.08 We have to consider all minimal (P,Q,R)-chains. 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (8) QDPSizeChangeProof (EQUIVALENT) 9.63/4.08 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.63/4.08 9.63/4.08 From the DPs we obtained the following set of size-change graphs: 9.63/4.08 *new_foldr(Cons(vy30, vy31), h) -> new_foldr(vy31, h) 9.63/4.08 The graph contains the following edges 1 > 1, 2 >= 2 9.63/4.08 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (9) 9.63/4.08 YES 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (10) 9.63/4.08 Obligation: 9.63/4.08 Q DP problem: 9.63/4.08 The TRS P consists of the following rules: 9.63/4.08 9.63/4.08 new_psPs(Cons(vy40, vy41), vy5) -> new_psPs(vy41, vy5) 9.63/4.08 9.63/4.08 R is empty. 9.63/4.08 Q is empty. 9.63/4.08 We have to consider all minimal (P,Q,R)-chains. 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (11) QDPSizeChangeProof (EQUIVALENT) 9.63/4.08 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.63/4.08 9.63/4.08 From the DPs we obtained the following set of size-change graphs: 9.63/4.08 *new_psPs(Cons(vy40, vy41), vy5) -> new_psPs(vy41, vy5) 9.63/4.08 The graph contains the following edges 1 > 1, 2 >= 2 9.63/4.08 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (12) 9.63/4.08 YES 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (13) 9.63/4.08 Obligation: 9.63/4.08 Q DP problem: 9.63/4.08 The TRS P consists of the following rules: 9.63/4.08 9.63/4.08 new_gtGtEsNil(Cons(vy300, vy301), vy4, h) -> new_gtGtEsNil(vy301, vy4, h) 9.63/4.08 9.63/4.08 R is empty. 9.63/4.08 Q is empty. 9.63/4.08 We have to consider all minimal (P,Q,R)-chains. 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (14) QDPSizeChangeProof (EQUIVALENT) 9.63/4.08 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.63/4.08 9.63/4.08 From the DPs we obtained the following set of size-change graphs: 9.63/4.08 *new_gtGtEsNil(Cons(vy300, vy301), vy4, h) -> new_gtGtEsNil(vy301, vy4, h) 9.63/4.08 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 9.63/4.08 9.63/4.08 9.63/4.08 ---------------------------------------- 9.63/4.08 9.63/4.08 (15) 9.63/4.08 YES 9.88/4.21 EOF