10.56/4.47 YES 12.78/5.05 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 12.78/5.05 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 12.78/5.05 12.78/5.05 12.78/5.05 H-Termination with start terms of the given HASKELL could be proven: 12.78/5.05 12.78/5.05 (0) HASKELL 12.78/5.05 (1) IFR [EQUIVALENT, 0 ms] 12.78/5.05 (2) HASKELL 12.78/5.05 (3) BR [EQUIVALENT, 0 ms] 12.78/5.05 (4) HASKELL 12.78/5.05 (5) COR [EQUIVALENT, 21 ms] 12.78/5.05 (6) HASKELL 12.78/5.05 (7) Narrow [SOUND, 0 ms] 12.78/5.05 (8) QDP 12.78/5.05 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 12.78/5.05 (10) AND 12.78/5.05 (11) QDP 12.78/5.05 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.78/5.05 (13) YES 12.78/5.05 (14) QDP 12.78/5.05 (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.78/5.05 (16) YES 12.78/5.05 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (0) 12.78/5.05 Obligation: 12.78/5.05 mainModule Main 12.78/5.05 module Maybe where { 12.78/5.05 import qualified List; 12.78/5.05 import qualified Main; 12.78/5.05 import qualified Prelude; 12.78/5.05 } 12.78/5.05 module List where { 12.78/5.05 import qualified Main; 12.78/5.05 import qualified Maybe; 12.78/5.05 import qualified Prelude; 12.78/5.05 delete :: Eq a => a -> [a] -> [a]; 12.78/5.05 delete = deleteBy (==); 12.78/5.05 12.78/5.05 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]; 12.78/5.05 deleteBy _ _ [] = []; 12.78/5.05 deleteBy eq x (y : ys) = if x `eq` y then ys else y : deleteBy eq x ys; 12.78/5.05 12.78/5.05 } 12.78/5.05 module Main where { 12.78/5.05 import qualified List; 12.78/5.05 import qualified Maybe; 12.78/5.05 import qualified Prelude; 12.78/5.05 } 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (1) IFR (EQUIVALENT) 12.78/5.05 If Reductions: 12.78/5.05 The following If expression 12.78/5.05 "if eq x y then ys else y : deleteBy eq x ys" 12.78/5.05 is transformed to 12.78/5.05 "deleteBy0 ys y eq x True = ys; 12.78/5.05 deleteBy0 ys y eq x False = y : deleteBy eq x ys; 12.78/5.05 " 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (2) 12.78/5.05 Obligation: 12.78/5.05 mainModule Main 12.78/5.05 module Maybe where { 12.78/5.05 import qualified List; 12.78/5.05 import qualified Main; 12.78/5.05 import qualified Prelude; 12.78/5.05 } 12.78/5.05 module List where { 12.78/5.05 import qualified Main; 12.78/5.05 import qualified Maybe; 12.78/5.05 import qualified Prelude; 12.78/5.05 delete :: Eq a => a -> [a] -> [a]; 12.78/5.05 delete = deleteBy (==); 12.78/5.05 12.78/5.05 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]; 12.78/5.05 deleteBy _ _ [] = []; 12.78/5.05 deleteBy eq x (y : ys) = deleteBy0 ys y eq x (x `eq` y); 12.78/5.05 12.78/5.05 deleteBy0 ys y eq x True = ys; 12.78/5.05 deleteBy0 ys y eq x False = y : deleteBy eq x ys; 12.78/5.05 12.78/5.05 } 12.78/5.05 module Main where { 12.78/5.05 import qualified List; 12.78/5.05 import qualified Maybe; 12.78/5.05 import qualified Prelude; 12.78/5.05 } 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (3) BR (EQUIVALENT) 12.78/5.05 Replaced joker patterns by fresh variables and removed binding patterns. 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (4) 12.78/5.05 Obligation: 12.78/5.05 mainModule Main 12.78/5.05 module Maybe where { 12.78/5.05 import qualified List; 12.78/5.05 import qualified Main; 12.78/5.05 import qualified Prelude; 12.78/5.05 } 12.78/5.05 module List where { 12.78/5.05 import qualified Main; 12.78/5.05 import qualified Maybe; 12.78/5.05 import qualified Prelude; 12.78/5.05 delete :: Eq a => a -> [a] -> [a]; 12.78/5.05 delete = deleteBy (==); 12.78/5.05 12.78/5.05 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]; 12.78/5.05 deleteBy vy vz [] = []; 12.78/5.05 deleteBy eq x (y : ys) = deleteBy0 ys y eq x (x `eq` y); 12.78/5.05 12.78/5.05 deleteBy0 ys y eq x True = ys; 12.78/5.05 deleteBy0 ys y eq x False = y : deleteBy eq x ys; 12.78/5.05 12.78/5.05 } 12.78/5.05 module Main where { 12.78/5.05 import qualified List; 12.78/5.05 import qualified Maybe; 12.78/5.05 import qualified Prelude; 12.78/5.05 } 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (5) COR (EQUIVALENT) 12.78/5.05 Cond Reductions: 12.78/5.05 The following Function with conditions 12.78/5.05 "undefined |Falseundefined; 12.78/5.05 " 12.78/5.05 is transformed to 12.78/5.05 "undefined = undefined1; 12.78/5.05 " 12.78/5.05 "undefined0 True = undefined; 12.78/5.05 " 12.78/5.05 "undefined1 = undefined0 False; 12.78/5.05 " 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (6) 12.78/5.05 Obligation: 12.78/5.05 mainModule Main 12.78/5.05 module Maybe where { 12.78/5.05 import qualified List; 12.78/5.05 import qualified Main; 12.78/5.05 import qualified Prelude; 12.78/5.05 } 12.78/5.05 module List where { 12.78/5.05 import qualified Main; 12.78/5.05 import qualified Maybe; 12.78/5.05 import qualified Prelude; 12.78/5.05 delete :: Eq a => a -> [a] -> [a]; 12.78/5.05 delete = deleteBy (==); 12.78/5.05 12.78/5.05 deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]; 12.78/5.05 deleteBy vy vz [] = []; 12.78/5.05 deleteBy eq x (y : ys) = deleteBy0 ys y eq x (x `eq` y); 12.78/5.05 12.78/5.05 deleteBy0 ys y eq x True = ys; 12.78/5.05 deleteBy0 ys y eq x False = y : deleteBy eq x ys; 12.78/5.05 12.78/5.05 } 12.78/5.05 module Main where { 12.78/5.05 import qualified List; 12.78/5.05 import qualified Maybe; 12.78/5.05 import qualified Prelude; 12.78/5.05 } 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (7) Narrow (SOUND) 12.78/5.05 Haskell To QDPs 12.78/5.05 12.78/5.05 digraph dp_graph { 12.78/5.05 node [outthreshold=100, inthreshold=100];1[label="List.delete",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 12.78/5.05 3[label="List.delete wu3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 12.78/5.05 4[label="List.delete wu3 wu4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 12.78/5.05 5[label="List.deleteBy (==) wu3 wu4",fontsize=16,color="burlywood",shape="triangle"];30[label="wu4/wu40 : wu41",fontsize=10,color="white",style="solid",shape="box"];5 -> 30[label="",style="solid", color="burlywood", weight=9]; 12.78/5.05 30 -> 6[label="",style="solid", color="burlywood", weight=3]; 12.78/5.05 31[label="wu4/[]",fontsize=10,color="white",style="solid",shape="box"];5 -> 31[label="",style="solid", color="burlywood", weight=9]; 12.78/5.05 31 -> 7[label="",style="solid", color="burlywood", weight=3]; 12.78/5.05 6[label="List.deleteBy (==) wu3 (wu40 : wu41)",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3]; 12.78/5.05 7[label="List.deleteBy (==) wu3 []",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3]; 12.78/5.05 8[label="List.deleteBy0 wu41 wu40 (==) wu3 ((==) wu3 wu40)",fontsize=16,color="burlywood",shape="box"];32[label="wu3/False",fontsize=10,color="white",style="solid",shape="box"];8 -> 32[label="",style="solid", color="burlywood", weight=9]; 12.78/5.05 32 -> 10[label="",style="solid", color="burlywood", weight=3]; 12.78/5.05 33[label="wu3/True",fontsize=10,color="white",style="solid",shape="box"];8 -> 33[label="",style="solid", color="burlywood", weight=9]; 12.78/5.05 33 -> 11[label="",style="solid", color="burlywood", weight=3]; 12.78/5.05 9[label="[]",fontsize=16,color="green",shape="box"];10[label="List.deleteBy0 wu41 wu40 (==) False ((==) False wu40)",fontsize=16,color="burlywood",shape="box"];34[label="wu40/False",fontsize=10,color="white",style="solid",shape="box"];10 -> 34[label="",style="solid", color="burlywood", weight=9]; 12.78/5.05 34 -> 12[label="",style="solid", color="burlywood", weight=3]; 12.78/5.05 35[label="wu40/True",fontsize=10,color="white",style="solid",shape="box"];10 -> 35[label="",style="solid", color="burlywood", weight=9]; 12.78/5.05 35 -> 13[label="",style="solid", color="burlywood", weight=3]; 12.78/5.05 11[label="List.deleteBy0 wu41 wu40 (==) True ((==) True wu40)",fontsize=16,color="burlywood",shape="box"];36[label="wu40/False",fontsize=10,color="white",style="solid",shape="box"];11 -> 36[label="",style="solid", color="burlywood", weight=9]; 12.78/5.05 36 -> 14[label="",style="solid", color="burlywood", weight=3]; 12.78/5.05 37[label="wu40/True",fontsize=10,color="white",style="solid",shape="box"];11 -> 37[label="",style="solid", color="burlywood", weight=9]; 12.78/5.05 37 -> 15[label="",style="solid", color="burlywood", weight=3]; 12.78/5.05 12[label="List.deleteBy0 wu41 False (==) False ((==) False False)",fontsize=16,color="black",shape="box"];12 -> 16[label="",style="solid", color="black", weight=3]; 12.78/5.05 13[label="List.deleteBy0 wu41 True (==) False ((==) False True)",fontsize=16,color="black",shape="box"];13 -> 17[label="",style="solid", color="black", weight=3]; 12.78/5.05 14[label="List.deleteBy0 wu41 False (==) True ((==) True False)",fontsize=16,color="black",shape="box"];14 -> 18[label="",style="solid", color="black", weight=3]; 12.78/5.05 15[label="List.deleteBy0 wu41 True (==) True ((==) True True)",fontsize=16,color="black",shape="box"];15 -> 19[label="",style="solid", color="black", weight=3]; 12.78/5.05 16[label="List.deleteBy0 wu41 False (==) False True",fontsize=16,color="black",shape="box"];16 -> 20[label="",style="solid", color="black", weight=3]; 12.78/5.05 17[label="List.deleteBy0 wu41 True (==) False False",fontsize=16,color="black",shape="box"];17 -> 21[label="",style="solid", color="black", weight=3]; 12.78/5.05 18[label="List.deleteBy0 wu41 False (==) True False",fontsize=16,color="black",shape="box"];18 -> 22[label="",style="solid", color="black", weight=3]; 12.78/5.05 19[label="List.deleteBy0 wu41 True (==) True True",fontsize=16,color="black",shape="box"];19 -> 23[label="",style="solid", color="black", weight=3]; 12.78/5.05 20[label="wu41",fontsize=16,color="green",shape="box"];21[label="True : List.deleteBy (==) False wu41",fontsize=16,color="green",shape="box"];21 -> 24[label="",style="dashed", color="green", weight=3]; 12.78/5.05 22[label="False : List.deleteBy (==) True wu41",fontsize=16,color="green",shape="box"];22 -> 25[label="",style="dashed", color="green", weight=3]; 12.78/5.05 23[label="wu41",fontsize=16,color="green",shape="box"];24 -> 5[label="",style="dashed", color="red", weight=0]; 12.78/5.05 24[label="List.deleteBy (==) False wu41",fontsize=16,color="magenta"];24 -> 26[label="",style="dashed", color="magenta", weight=3]; 12.78/5.05 24 -> 27[label="",style="dashed", color="magenta", weight=3]; 12.78/5.05 25 -> 5[label="",style="dashed", color="red", weight=0]; 12.78/5.05 25[label="List.deleteBy (==) True wu41",fontsize=16,color="magenta"];25 -> 28[label="",style="dashed", color="magenta", weight=3]; 12.78/5.05 25 -> 29[label="",style="dashed", color="magenta", weight=3]; 12.78/5.05 26[label="False",fontsize=16,color="green",shape="box"];27[label="wu41",fontsize=16,color="green",shape="box"];28[label="True",fontsize=16,color="green",shape="box"];29[label="wu41",fontsize=16,color="green",shape="box"];} 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (8) 12.78/5.05 Obligation: 12.78/5.05 Q DP problem: 12.78/5.05 The TRS P consists of the following rules: 12.78/5.05 12.78/5.05 new_deleteBy(True, :(False, wu41)) -> new_deleteBy(True, wu41) 12.78/5.05 new_deleteBy(False, :(True, wu41)) -> new_deleteBy(False, wu41) 12.78/5.05 12.78/5.05 R is empty. 12.78/5.05 Q is empty. 12.78/5.05 We have to consider all minimal (P,Q,R)-chains. 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (9) DependencyGraphProof (EQUIVALENT) 12.78/5.05 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (10) 12.78/5.05 Complex Obligation (AND) 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (11) 12.78/5.05 Obligation: 12.78/5.05 Q DP problem: 12.78/5.05 The TRS P consists of the following rules: 12.78/5.05 12.78/5.05 new_deleteBy(False, :(True, wu41)) -> new_deleteBy(False, wu41) 12.78/5.05 12.78/5.05 R is empty. 12.78/5.05 Q is empty. 12.78/5.05 We have to consider all minimal (P,Q,R)-chains. 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (12) QDPSizeChangeProof (EQUIVALENT) 12.78/5.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. 12.78/5.05 12.78/5.05 From the DPs we obtained the following set of size-change graphs: 12.78/5.05 *new_deleteBy(False, :(True, wu41)) -> new_deleteBy(False, wu41) 12.78/5.05 The graph contains the following edges 1 >= 1, 2 > 2 12.78/5.05 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (13) 12.78/5.05 YES 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (14) 12.78/5.05 Obligation: 12.78/5.05 Q DP problem: 12.78/5.05 The TRS P consists of the following rules: 12.78/5.05 12.78/5.05 new_deleteBy(True, :(False, wu41)) -> new_deleteBy(True, wu41) 12.78/5.05 12.78/5.05 R is empty. 12.78/5.05 Q is empty. 12.78/5.05 We have to consider all minimal (P,Q,R)-chains. 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (15) QDPSizeChangeProof (EQUIVALENT) 12.78/5.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. 12.78/5.05 12.78/5.05 From the DPs we obtained the following set of size-change graphs: 12.78/5.05 *new_deleteBy(True, :(False, wu41)) -> new_deleteBy(True, wu41) 12.78/5.05 The graph contains the following edges 1 >= 1, 2 > 2 12.78/5.05 12.78/5.05 12.78/5.05 ---------------------------------------- 12.78/5.05 12.78/5.05 (16) 12.78/5.05 YES 12.83/8.39 EOF