7.86/3.55 YES 9.81/4.06 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 9.81/4.06 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.81/4.06 9.81/4.06 9.81/4.06 H-Termination with start terms of the given HASKELL could be proven: 9.81/4.06 9.81/4.06 (0) HASKELL 9.81/4.06 (1) BR [EQUIVALENT, 0 ms] 9.81/4.06 (2) HASKELL 9.81/4.06 (3) COR [EQUIVALENT, 0 ms] 9.81/4.06 (4) HASKELL 9.81/4.06 (5) Narrow [EQUIVALENT, 31 ms] 9.81/4.06 (6) YES 9.81/4.06 9.81/4.06 9.81/4.06 ---------------------------------------- 9.81/4.06 9.81/4.06 (0) 9.81/4.06 Obligation: 9.81/4.06 mainModule Main 9.81/4.06 module Main where { 9.81/4.06 import qualified Prelude; 9.81/4.06 data MyBool = MyTrue | MyFalse ; 9.81/4.06 9.81/4.06 data Ordering = LT | EQ | GT ; 9.81/4.06 9.81/4.06 compare0 x y MyTrue = GT; 9.81/4.06 9.81/4.06 compare1 x y MyTrue = LT; 9.81/4.06 compare1 x y MyFalse = compare0 x y otherwise; 9.81/4.06 9.81/4.06 compare2 x y MyTrue = EQ; 9.81/4.06 compare2 x y MyFalse = compare1 x y (ltEsMyBool x y); 9.81/4.06 9.81/4.06 compare3 x y = compare2 x y (esEsMyBool x y); 9.81/4.06 9.81/4.06 compareMyBool :: MyBool -> MyBool -> Ordering; 9.81/4.06 compareMyBool x y = compare3 x y; 9.81/4.06 9.81/4.06 esEsMyBool :: MyBool -> MyBool -> MyBool; 9.81/4.06 esEsMyBool MyFalse MyFalse = MyTrue; 9.81/4.06 esEsMyBool MyFalse MyTrue = MyFalse; 9.81/4.06 esEsMyBool MyTrue MyFalse = MyFalse; 9.81/4.06 esEsMyBool MyTrue MyTrue = MyTrue; 9.81/4.06 9.81/4.06 esEsOrdering :: Ordering -> Ordering -> MyBool; 9.81/4.06 esEsOrdering LT LT = MyTrue; 9.81/4.06 esEsOrdering LT EQ = MyFalse; 9.81/4.06 esEsOrdering LT GT = MyFalse; 9.81/4.06 esEsOrdering EQ LT = MyFalse; 9.81/4.06 esEsOrdering EQ EQ = MyTrue; 9.81/4.06 esEsOrdering EQ GT = MyFalse; 9.81/4.06 esEsOrdering GT LT = MyFalse; 9.81/4.06 esEsOrdering GT EQ = MyFalse; 9.81/4.06 esEsOrdering GT GT = MyTrue; 9.81/4.06 9.81/4.06 ltEsMyBool :: MyBool -> MyBool -> MyBool; 9.81/4.06 ltEsMyBool MyFalse MyFalse = MyTrue; 9.81/4.06 ltEsMyBool MyFalse MyTrue = MyTrue; 9.81/4.06 ltEsMyBool MyTrue MyFalse = MyFalse; 9.81/4.06 ltEsMyBool MyTrue MyTrue = MyTrue; 9.81/4.06 9.81/4.06 ltMyBool :: MyBool -> MyBool -> MyBool; 9.81/4.06 ltMyBool x y = esEsOrdering (compareMyBool x y) LT; 9.81/4.06 9.81/4.06 otherwise :: MyBool; 9.81/4.06 otherwise = MyTrue; 9.81/4.06 9.81/4.06 } 9.81/4.06 9.81/4.06 ---------------------------------------- 9.81/4.06 9.81/4.06 (1) BR (EQUIVALENT) 9.81/4.06 Replaced joker patterns by fresh variables and removed binding patterns. 9.81/4.06 ---------------------------------------- 9.81/4.06 9.81/4.06 (2) 9.81/4.06 Obligation: 9.81/4.06 mainModule Main 9.81/4.06 module Main where { 9.81/4.06 import qualified Prelude; 9.81/4.06 data MyBool = MyTrue | MyFalse ; 9.81/4.06 9.81/4.06 data Ordering = LT | EQ | GT ; 9.81/4.06 9.81/4.06 compare0 x y MyTrue = GT; 9.81/4.06 9.81/4.06 compare1 x y MyTrue = LT; 9.81/4.06 compare1 x y MyFalse = compare0 x y otherwise; 9.81/4.06 9.81/4.06 compare2 x y MyTrue = EQ; 9.81/4.06 compare2 x y MyFalse = compare1 x y (ltEsMyBool x y); 9.81/4.06 9.81/4.06 compare3 x y = compare2 x y (esEsMyBool x y); 9.81/4.06 9.81/4.06 compareMyBool :: MyBool -> MyBool -> Ordering; 9.81/4.06 compareMyBool x y = compare3 x y; 9.81/4.06 9.81/4.06 esEsMyBool :: MyBool -> MyBool -> MyBool; 9.81/4.06 esEsMyBool MyFalse MyFalse = MyTrue; 9.81/4.06 esEsMyBool MyFalse MyTrue = MyFalse; 9.81/4.06 esEsMyBool MyTrue MyFalse = MyFalse; 9.81/4.06 esEsMyBool MyTrue MyTrue = MyTrue; 9.81/4.06 9.81/4.06 esEsOrdering :: Ordering -> Ordering -> MyBool; 9.81/4.06 esEsOrdering LT LT = MyTrue; 9.81/4.06 esEsOrdering LT EQ = MyFalse; 9.81/4.06 esEsOrdering LT GT = MyFalse; 9.81/4.06 esEsOrdering EQ LT = MyFalse; 9.81/4.06 esEsOrdering EQ EQ = MyTrue; 9.81/4.06 esEsOrdering EQ GT = MyFalse; 9.81/4.06 esEsOrdering GT LT = MyFalse; 9.81/4.06 esEsOrdering GT EQ = MyFalse; 9.81/4.06 esEsOrdering GT GT = MyTrue; 9.81/4.06 9.81/4.06 ltEsMyBool :: MyBool -> MyBool -> MyBool; 9.81/4.06 ltEsMyBool MyFalse MyFalse = MyTrue; 9.81/4.06 ltEsMyBool MyFalse MyTrue = MyTrue; 9.81/4.06 ltEsMyBool MyTrue MyFalse = MyFalse; 9.81/4.06 ltEsMyBool MyTrue MyTrue = MyTrue; 9.81/4.06 9.81/4.06 ltMyBool :: MyBool -> MyBool -> MyBool; 9.81/4.06 ltMyBool x y = esEsOrdering (compareMyBool x y) LT; 9.81/4.06 9.81/4.06 otherwise :: MyBool; 9.81/4.06 otherwise = MyTrue; 9.81/4.06 9.81/4.06 } 9.81/4.06 9.81/4.06 ---------------------------------------- 9.81/4.06 9.81/4.06 (3) COR (EQUIVALENT) 9.81/4.06 Cond Reductions: 9.81/4.06 The following Function with conditions 9.81/4.06 "undefined |Falseundefined; 9.81/4.06 " 9.81/4.06 is transformed to 9.81/4.06 "undefined = undefined1; 9.81/4.06 " 9.81/4.06 "undefined0 True = undefined; 9.81/4.06 " 9.81/4.06 "undefined1 = undefined0 False; 9.81/4.06 " 9.81/4.06 9.81/4.06 ---------------------------------------- 9.81/4.06 9.81/4.06 (4) 9.81/4.06 Obligation: 9.81/4.06 mainModule Main 9.81/4.06 module Main where { 9.81/4.06 import qualified Prelude; 9.81/4.06 data MyBool = MyTrue | MyFalse ; 9.81/4.06 9.81/4.06 data Ordering = LT | EQ | GT ; 9.81/4.06 9.81/4.06 compare0 x y MyTrue = GT; 9.81/4.06 9.81/4.06 compare1 x y MyTrue = LT; 9.81/4.06 compare1 x y MyFalse = compare0 x y otherwise; 9.81/4.06 9.81/4.06 compare2 x y MyTrue = EQ; 9.81/4.06 compare2 x y MyFalse = compare1 x y (ltEsMyBool x y); 9.81/4.06 9.81/4.06 compare3 x y = compare2 x y (esEsMyBool x y); 9.81/4.06 9.81/4.06 compareMyBool :: MyBool -> MyBool -> Ordering; 9.81/4.06 compareMyBool x y = compare3 x y; 9.81/4.06 9.81/4.06 esEsMyBool :: MyBool -> MyBool -> MyBool; 9.81/4.06 esEsMyBool MyFalse MyFalse = MyTrue; 9.81/4.06 esEsMyBool MyFalse MyTrue = MyFalse; 9.81/4.06 esEsMyBool MyTrue MyFalse = MyFalse; 9.81/4.06 esEsMyBool MyTrue MyTrue = MyTrue; 9.81/4.06 9.81/4.06 esEsOrdering :: Ordering -> Ordering -> MyBool; 9.81/4.06 esEsOrdering LT LT = MyTrue; 9.81/4.06 esEsOrdering LT EQ = MyFalse; 9.81/4.06 esEsOrdering LT GT = MyFalse; 9.81/4.06 esEsOrdering EQ LT = MyFalse; 9.81/4.06 esEsOrdering EQ EQ = MyTrue; 9.81/4.06 esEsOrdering EQ GT = MyFalse; 9.81/4.06 esEsOrdering GT LT = MyFalse; 9.81/4.06 esEsOrdering GT EQ = MyFalse; 9.81/4.06 esEsOrdering GT GT = MyTrue; 9.81/4.06 9.81/4.06 ltEsMyBool :: MyBool -> MyBool -> MyBool; 9.81/4.06 ltEsMyBool MyFalse MyFalse = MyTrue; 9.81/4.06 ltEsMyBool MyFalse MyTrue = MyTrue; 9.81/4.06 ltEsMyBool MyTrue MyFalse = MyFalse; 9.81/4.06 ltEsMyBool MyTrue MyTrue = MyTrue; 9.81/4.06 9.81/4.06 ltMyBool :: MyBool -> MyBool -> MyBool; 9.81/4.06 ltMyBool x y = esEsOrdering (compareMyBool x y) LT; 9.81/4.06 9.81/4.06 otherwise :: MyBool; 9.81/4.06 otherwise = MyTrue; 9.81/4.06 9.81/4.06 } 9.81/4.06 9.81/4.06 ---------------------------------------- 9.81/4.06 9.81/4.06 (5) Narrow (EQUIVALENT) 9.81/4.06 Haskell To QDPs 9.81/4.06 9.81/4.06 digraph dp_graph { 9.81/4.06 node [outthreshold=100, inthreshold=100];1[label="ltMyBool",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 9.81/4.06 3[label="ltMyBool vx3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 9.81/4.06 4[label="ltMyBool vx3 vx4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 9.81/4.06 5[label="esEsOrdering (compareMyBool vx3 vx4) LT",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3]; 9.81/4.06 6[label="esEsOrdering (compare3 vx3 vx4) LT",fontsize=16,color="black",shape="box"];6 -> 7[label="",style="solid", color="black", weight=3]; 9.81/4.06 7[label="esEsOrdering (compare2 vx3 vx4 (esEsMyBool vx3 vx4)) LT",fontsize=16,color="burlywood",shape="box"];31[label="vx3/MyTrue",fontsize=10,color="white",style="solid",shape="box"];7 -> 31[label="",style="solid", color="burlywood", weight=9]; 9.81/4.06 31 -> 8[label="",style="solid", color="burlywood", weight=3]; 9.81/4.06 32[label="vx3/MyFalse",fontsize=10,color="white",style="solid",shape="box"];7 -> 32[label="",style="solid", color="burlywood", weight=9]; 9.81/4.06 32 -> 9[label="",style="solid", color="burlywood", weight=3]; 9.81/4.06 8[label="esEsOrdering (compare2 MyTrue vx4 (esEsMyBool MyTrue vx4)) LT",fontsize=16,color="burlywood",shape="box"];33[label="vx4/MyTrue",fontsize=10,color="white",style="solid",shape="box"];8 -> 33[label="",style="solid", color="burlywood", weight=9]; 9.81/4.06 33 -> 10[label="",style="solid", color="burlywood", weight=3]; 9.81/4.06 34[label="vx4/MyFalse",fontsize=10,color="white",style="solid",shape="box"];8 -> 34[label="",style="solid", color="burlywood", weight=9]; 9.81/4.06 34 -> 11[label="",style="solid", color="burlywood", weight=3]; 9.81/4.06 9[label="esEsOrdering (compare2 MyFalse vx4 (esEsMyBool MyFalse vx4)) LT",fontsize=16,color="burlywood",shape="box"];35[label="vx4/MyTrue",fontsize=10,color="white",style="solid",shape="box"];9 -> 35[label="",style="solid", color="burlywood", weight=9]; 9.81/4.06 35 -> 12[label="",style="solid", color="burlywood", weight=3]; 9.81/4.06 36[label="vx4/MyFalse",fontsize=10,color="white",style="solid",shape="box"];9 -> 36[label="",style="solid", color="burlywood", weight=9]; 9.81/4.06 36 -> 13[label="",style="solid", color="burlywood", weight=3]; 9.81/4.06 10[label="esEsOrdering (compare2 MyTrue MyTrue (esEsMyBool MyTrue MyTrue)) LT",fontsize=16,color="black",shape="box"];10 -> 14[label="",style="solid", color="black", weight=3]; 9.81/4.06 11[label="esEsOrdering (compare2 MyTrue MyFalse (esEsMyBool MyTrue MyFalse)) LT",fontsize=16,color="black",shape="box"];11 -> 15[label="",style="solid", color="black", weight=3]; 9.81/4.06 12[label="esEsOrdering (compare2 MyFalse MyTrue (esEsMyBool MyFalse MyTrue)) LT",fontsize=16,color="black",shape="box"];12 -> 16[label="",style="solid", color="black", weight=3]; 9.81/4.06 13[label="esEsOrdering (compare2 MyFalse MyFalse (esEsMyBool MyFalse MyFalse)) LT",fontsize=16,color="black",shape="box"];13 -> 17[label="",style="solid", color="black", weight=3]; 9.81/4.06 14[label="esEsOrdering (compare2 MyTrue MyTrue MyTrue) LT",fontsize=16,color="black",shape="box"];14 -> 18[label="",style="solid", color="black", weight=3]; 9.81/4.06 15[label="esEsOrdering (compare2 MyTrue MyFalse MyFalse) LT",fontsize=16,color="black",shape="box"];15 -> 19[label="",style="solid", color="black", weight=3]; 9.81/4.06 16[label="esEsOrdering (compare2 MyFalse MyTrue MyFalse) LT",fontsize=16,color="black",shape="box"];16 -> 20[label="",style="solid", color="black", weight=3]; 9.81/4.06 17[label="esEsOrdering (compare2 MyFalse MyFalse MyTrue) LT",fontsize=16,color="black",shape="box"];17 -> 21[label="",style="solid", color="black", weight=3]; 9.81/4.06 18[label="esEsOrdering EQ LT",fontsize=16,color="black",shape="triangle"];18 -> 22[label="",style="solid", color="black", weight=3]; 9.81/4.06 19[label="esEsOrdering (compare1 MyTrue MyFalse (ltEsMyBool MyTrue MyFalse)) LT",fontsize=16,color="black",shape="box"];19 -> 23[label="",style="solid", color="black", weight=3]; 9.81/4.06 20[label="esEsOrdering (compare1 MyFalse MyTrue (ltEsMyBool MyFalse MyTrue)) LT",fontsize=16,color="black",shape="box"];20 -> 24[label="",style="solid", color="black", weight=3]; 9.81/4.06 21 -> 18[label="",style="dashed", color="red", weight=0]; 9.81/4.06 21[label="esEsOrdering EQ LT",fontsize=16,color="magenta"];22[label="MyFalse",fontsize=16,color="green",shape="box"];23[label="esEsOrdering (compare1 MyTrue MyFalse MyFalse) LT",fontsize=16,color="black",shape="box"];23 -> 25[label="",style="solid", color="black", weight=3]; 9.81/4.06 24[label="esEsOrdering (compare1 MyFalse MyTrue MyTrue) LT",fontsize=16,color="black",shape="box"];24 -> 26[label="",style="solid", color="black", weight=3]; 9.81/4.06 25[label="esEsOrdering (compare0 MyTrue MyFalse otherwise) LT",fontsize=16,color="black",shape="box"];25 -> 27[label="",style="solid", color="black", weight=3]; 9.81/4.06 26[label="esEsOrdering LT LT",fontsize=16,color="black",shape="box"];26 -> 28[label="",style="solid", color="black", weight=3]; 9.81/4.06 27[label="esEsOrdering (compare0 MyTrue MyFalse MyTrue) LT",fontsize=16,color="black",shape="box"];27 -> 29[label="",style="solid", color="black", weight=3]; 9.81/4.06 28[label="MyTrue",fontsize=16,color="green",shape="box"];29[label="esEsOrdering GT LT",fontsize=16,color="black",shape="box"];29 -> 30[label="",style="solid", color="black", weight=3]; 9.81/4.06 30[label="MyFalse",fontsize=16,color="green",shape="box"];} 9.81/4.06 9.81/4.06 ---------------------------------------- 9.81/4.06 9.81/4.06 (6) 9.81/4.06 YES 9.81/4.10 EOF