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