9.38/3.94 YES 11.52/4.52 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 11.52/4.52 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 11.52/4.52 11.52/4.52 11.52/4.52 H-Termination with start terms of the given HASKELL could be proven: 11.52/4.52 11.52/4.52 (0) HASKELL 11.52/4.52 (1) LR [EQUIVALENT, 0 ms] 11.52/4.52 (2) HASKELL 11.52/4.52 (3) BR [EQUIVALENT, 0 ms] 11.52/4.52 (4) HASKELL 11.52/4.52 (5) COR [EQUIVALENT, 0 ms] 11.52/4.52 (6) HASKELL 11.52/4.52 (7) Narrow [SOUND, 0 ms] 11.52/4.52 (8) AND 11.52/4.52 (9) QDP 11.52/4.52 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 11.52/4.52 (11) YES 11.52/4.52 (12) QDP 11.52/4.52 (13) QDPSizeChangeProof [EQUIVALENT, 0 ms] 11.52/4.52 (14) YES 11.52/4.52 (15) QDP 11.52/4.52 (16) QDPSizeChangeProof [EQUIVALENT, 0 ms] 11.52/4.52 (17) YES 11.52/4.52 (18) QDP 11.52/4.52 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 11.52/4.52 (20) YES 11.52/4.52 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (0) 11.52/4.52 Obligation: 11.52/4.52 mainModule Main 11.52/4.52 module Maybe where { 11.52/4.52 import qualified Main; 11.52/4.52 import qualified Monad; 11.52/4.52 import qualified Prelude; 11.52/4.52 } 11.52/4.52 module Main where { 11.52/4.52 import qualified Maybe; 11.52/4.52 import qualified Monad; 11.52/4.52 import qualified Prelude; 11.52/4.52 } 11.52/4.52 module Monad where { 11.52/4.52 import qualified Main; 11.52/4.52 import qualified Maybe; 11.52/4.52 import qualified Prelude; 11.52/4.52 liftM3 :: Monad c => (e -> b -> a -> d) -> c e -> c b -> c a -> c d; 11.52/4.52 liftM3 f m1 m2 m3 = m1 >>= (\x1 ->m2 >>= (\x2 ->m3 >>= (\x3 ->return (f x1 x2 x3)))); 11.52/4.52 11.52/4.52 } 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (1) LR (EQUIVALENT) 11.52/4.52 Lambda Reductions: 11.52/4.52 The following Lambda expression 11.52/4.52 "\x3->return (f x1 x2 x3)" 11.52/4.52 is transformed to 11.52/4.52 "liftM30 f x1 x2 x3 = return (f x1 x2 x3); 11.52/4.52 " 11.52/4.52 The following Lambda expression 11.52/4.52 "\x2->m3 >>= liftM30 f x1 x2" 11.52/4.52 is transformed to 11.52/4.52 "liftM31 m3 f x1 x2 = m3 >>= liftM30 f x1 x2; 11.52/4.52 " 11.52/4.52 The following Lambda expression 11.52/4.52 "\x1->m2 >>= liftM31 m3 f x1" 11.52/4.52 is transformed to 11.52/4.52 "liftM32 m2 m3 f x1 = m2 >>= liftM31 m3 f x1; 11.52/4.52 " 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (2) 11.52/4.52 Obligation: 11.52/4.52 mainModule Main 11.52/4.52 module Maybe where { 11.52/4.52 import qualified Main; 11.52/4.52 import qualified Monad; 11.52/4.52 import qualified Prelude; 11.52/4.52 } 11.52/4.52 module Main where { 11.52/4.52 import qualified Maybe; 11.52/4.52 import qualified Monad; 11.52/4.52 import qualified Prelude; 11.52/4.52 } 11.52/4.52 module Monad where { 11.52/4.52 import qualified Main; 11.52/4.52 import qualified Maybe; 11.52/4.52 import qualified Prelude; 11.52/4.52 liftM3 :: Monad e => (b -> d -> c -> a) -> e b -> e d -> e c -> e a; 11.52/4.52 liftM3 f m1 m2 m3 = m1 >>= liftM32 m2 m3 f; 11.52/4.52 11.52/4.52 liftM30 f x1 x2 x3 = return (f x1 x2 x3); 11.52/4.52 11.52/4.52 liftM31 m3 f x1 x2 = m3 >>= liftM30 f x1 x2; 11.52/4.52 11.52/4.52 liftM32 m2 m3 f x1 = m2 >>= liftM31 m3 f x1; 11.52/4.52 11.52/4.52 } 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (3) BR (EQUIVALENT) 11.52/4.52 Replaced joker patterns by fresh variables and removed binding patterns. 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (4) 11.52/4.52 Obligation: 11.52/4.52 mainModule Main 11.52/4.52 module Maybe where { 11.52/4.52 import qualified Main; 11.52/4.52 import qualified Monad; 11.52/4.52 import qualified Prelude; 11.52/4.52 } 11.52/4.52 module Main where { 11.52/4.52 import qualified Maybe; 11.52/4.52 import qualified Monad; 11.52/4.52 import qualified Prelude; 11.52/4.52 } 11.52/4.52 module Monad where { 11.52/4.52 import qualified Main; 11.52/4.52 import qualified Maybe; 11.52/4.52 import qualified Prelude; 11.52/4.52 liftM3 :: Monad b => (a -> d -> c -> e) -> b a -> b d -> b c -> b e; 11.52/4.52 liftM3 f m1 m2 m3 = m1 >>= liftM32 m2 m3 f; 11.52/4.52 11.52/4.52 liftM30 f x1 x2 x3 = return (f x1 x2 x3); 11.52/4.52 11.52/4.52 liftM31 m3 f x1 x2 = m3 >>= liftM30 f x1 x2; 11.52/4.52 11.52/4.52 liftM32 m2 m3 f x1 = m2 >>= liftM31 m3 f x1; 11.52/4.52 11.52/4.52 } 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (5) COR (EQUIVALENT) 11.52/4.52 Cond Reductions: 11.52/4.52 The following Function with conditions 11.52/4.52 "undefined |Falseundefined; 11.52/4.52 " 11.52/4.52 is transformed to 11.52/4.52 "undefined = undefined1; 11.52/4.52 " 11.52/4.52 "undefined0 True = undefined; 11.52/4.52 " 11.52/4.52 "undefined1 = undefined0 False; 11.52/4.52 " 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (6) 11.52/4.52 Obligation: 11.52/4.52 mainModule Main 11.52/4.52 module Maybe where { 11.52/4.52 import qualified Main; 11.52/4.52 import qualified Monad; 11.52/4.52 import qualified Prelude; 11.52/4.52 } 11.52/4.52 module Main where { 11.52/4.52 import qualified Maybe; 11.52/4.52 import qualified Monad; 11.52/4.52 import qualified Prelude; 11.52/4.52 } 11.52/4.52 module Monad where { 11.52/4.52 import qualified Main; 11.52/4.52 import qualified Maybe; 11.52/4.52 import qualified Prelude; 11.52/4.52 liftM3 :: Monad c => (b -> a -> d -> e) -> c b -> c a -> c d -> c e; 11.52/4.52 liftM3 f m1 m2 m3 = m1 >>= liftM32 m2 m3 f; 11.52/4.52 11.52/4.52 liftM30 f x1 x2 x3 = return (f x1 x2 x3); 11.52/4.52 11.52/4.52 liftM31 m3 f x1 x2 = m3 >>= liftM30 f x1 x2; 11.52/4.52 11.52/4.52 liftM32 m2 m3 f x1 = m2 >>= liftM31 m3 f x1; 11.52/4.52 11.52/4.52 } 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (7) Narrow (SOUND) 11.52/4.52 Haskell To QDPs 11.52/4.52 11.52/4.52 digraph dp_graph { 11.52/4.52 node [outthreshold=100, inthreshold=100];1[label="Monad.liftM3",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 11.52/4.52 3[label="Monad.liftM3 vy3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 11.52/4.52 4[label="Monad.liftM3 vy3 vy4",fontsize=16,color="grey",shape="box"];4 -> 5[label="",style="dashed", color="grey", weight=3]; 11.52/4.52 5[label="Monad.liftM3 vy3 vy4 vy5",fontsize=16,color="grey",shape="box"];5 -> 6[label="",style="dashed", color="grey", weight=3]; 11.52/4.52 6[label="Monad.liftM3 vy3 vy4 vy5 vy6",fontsize=16,color="black",shape="triangle"];6 -> 7[label="",style="solid", color="black", weight=3]; 11.52/4.52 7[label="vy4 >>= Monad.liftM32 vy5 vy6 vy3",fontsize=16,color="burlywood",shape="triangle"];67[label="vy4/vy40 : vy41",fontsize=10,color="white",style="solid",shape="box"];7 -> 67[label="",style="solid", color="burlywood", weight=9]; 11.52/4.52 67 -> 8[label="",style="solid", color="burlywood", weight=3]; 11.52/4.52 68[label="vy4/[]",fontsize=10,color="white",style="solid",shape="box"];7 -> 68[label="",style="solid", color="burlywood", weight=9]; 11.52/4.52 68 -> 9[label="",style="solid", color="burlywood", weight=3]; 11.52/4.52 8[label="vy40 : vy41 >>= Monad.liftM32 vy5 vy6 vy3",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3]; 11.52/4.52 9[label="[] >>= Monad.liftM32 vy5 vy6 vy3",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3]; 11.52/4.52 10 -> 27[label="",style="dashed", color="red", weight=0]; 11.52/4.52 10[label="Monad.liftM32 vy5 vy6 vy3 vy40 ++ (vy41 >>= Monad.liftM32 vy5 vy6 vy3)",fontsize=16,color="magenta"];10 -> 28[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 10 -> 29[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 11[label="[]",fontsize=16,color="green",shape="box"];28[label="Monad.liftM32 vy5 vy6 vy3 vy40",fontsize=16,color="black",shape="box"];28 -> 38[label="",style="solid", color="black", weight=3]; 11.52/4.52 29 -> 7[label="",style="dashed", color="red", weight=0]; 11.52/4.52 29[label="vy41 >>= Monad.liftM32 vy5 vy6 vy3",fontsize=16,color="magenta"];29 -> 39[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 27[label="vy8 ++ vy7",fontsize=16,color="burlywood",shape="triangle"];69[label="vy8/vy80 : vy81",fontsize=10,color="white",style="solid",shape="box"];27 -> 69[label="",style="solid", color="burlywood", weight=9]; 11.52/4.52 69 -> 40[label="",style="solid", color="burlywood", weight=3]; 11.52/4.52 70[label="vy8/[]",fontsize=10,color="white",style="solid",shape="box"];27 -> 70[label="",style="solid", color="burlywood", weight=9]; 11.52/4.52 70 -> 41[label="",style="solid", color="burlywood", weight=3]; 11.52/4.52 38[label="vy5 >>= Monad.liftM31 vy6 vy3 vy40",fontsize=16,color="burlywood",shape="triangle"];71[label="vy5/vy50 : vy51",fontsize=10,color="white",style="solid",shape="box"];38 -> 71[label="",style="solid", color="burlywood", weight=9]; 11.52/4.52 71 -> 42[label="",style="solid", color="burlywood", weight=3]; 11.52/4.52 72[label="vy5/[]",fontsize=10,color="white",style="solid",shape="box"];38 -> 72[label="",style="solid", color="burlywood", weight=9]; 11.52/4.52 72 -> 43[label="",style="solid", color="burlywood", weight=3]; 11.52/4.52 39[label="vy41",fontsize=16,color="green",shape="box"];40[label="(vy80 : vy81) ++ vy7",fontsize=16,color="black",shape="box"];40 -> 44[label="",style="solid", color="black", weight=3]; 11.52/4.52 41[label="[] ++ vy7",fontsize=16,color="black",shape="box"];41 -> 45[label="",style="solid", color="black", weight=3]; 11.52/4.52 42[label="vy50 : vy51 >>= Monad.liftM31 vy6 vy3 vy40",fontsize=16,color="black",shape="box"];42 -> 46[label="",style="solid", color="black", weight=3]; 11.52/4.52 43[label="[] >>= Monad.liftM31 vy6 vy3 vy40",fontsize=16,color="black",shape="box"];43 -> 47[label="",style="solid", color="black", weight=3]; 11.52/4.52 44[label="vy80 : vy81 ++ vy7",fontsize=16,color="green",shape="box"];44 -> 48[label="",style="dashed", color="green", weight=3]; 11.52/4.52 45[label="vy7",fontsize=16,color="green",shape="box"];46 -> 27[label="",style="dashed", color="red", weight=0]; 11.52/4.52 46[label="Monad.liftM31 vy6 vy3 vy40 vy50 ++ (vy51 >>= Monad.liftM31 vy6 vy3 vy40)",fontsize=16,color="magenta"];46 -> 49[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 46 -> 50[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 47[label="[]",fontsize=16,color="green",shape="box"];48 -> 27[label="",style="dashed", color="red", weight=0]; 11.52/4.52 48[label="vy81 ++ vy7",fontsize=16,color="magenta"];48 -> 51[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 49[label="Monad.liftM31 vy6 vy3 vy40 vy50",fontsize=16,color="black",shape="box"];49 -> 52[label="",style="solid", color="black", weight=3]; 11.52/4.52 50 -> 38[label="",style="dashed", color="red", weight=0]; 11.52/4.52 50[label="vy51 >>= Monad.liftM31 vy6 vy3 vy40",fontsize=16,color="magenta"];50 -> 53[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 51[label="vy81",fontsize=16,color="green",shape="box"];52[label="vy6 >>= Monad.liftM30 vy3 vy40 vy50",fontsize=16,color="burlywood",shape="triangle"];73[label="vy6/vy60 : vy61",fontsize=10,color="white",style="solid",shape="box"];52 -> 73[label="",style="solid", color="burlywood", weight=9]; 11.52/4.52 73 -> 54[label="",style="solid", color="burlywood", weight=3]; 11.52/4.52 74[label="vy6/[]",fontsize=10,color="white",style="solid",shape="box"];52 -> 74[label="",style="solid", color="burlywood", weight=9]; 11.52/4.52 74 -> 55[label="",style="solid", color="burlywood", weight=3]; 11.52/4.52 53[label="vy51",fontsize=16,color="green",shape="box"];54[label="vy60 : vy61 >>= Monad.liftM30 vy3 vy40 vy50",fontsize=16,color="black",shape="box"];54 -> 56[label="",style="solid", color="black", weight=3]; 11.52/4.52 55[label="[] >>= Monad.liftM30 vy3 vy40 vy50",fontsize=16,color="black",shape="box"];55 -> 57[label="",style="solid", color="black", weight=3]; 11.52/4.52 56 -> 27[label="",style="dashed", color="red", weight=0]; 11.52/4.52 56[label="Monad.liftM30 vy3 vy40 vy50 vy60 ++ (vy61 >>= Monad.liftM30 vy3 vy40 vy50)",fontsize=16,color="magenta"];56 -> 58[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 56 -> 59[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 57[label="[]",fontsize=16,color="green",shape="box"];58[label="Monad.liftM30 vy3 vy40 vy50 vy60",fontsize=16,color="black",shape="box"];58 -> 60[label="",style="solid", color="black", weight=3]; 11.52/4.52 59 -> 52[label="",style="dashed", color="red", weight=0]; 11.52/4.52 59[label="vy61 >>= Monad.liftM30 vy3 vy40 vy50",fontsize=16,color="magenta"];59 -> 61[label="",style="dashed", color="magenta", weight=3]; 11.52/4.52 60[label="return (vy3 vy40 vy50 vy60)",fontsize=16,color="black",shape="box"];60 -> 62[label="",style="solid", color="black", weight=3]; 11.52/4.52 61[label="vy61",fontsize=16,color="green",shape="box"];62[label="vy3 vy40 vy50 vy60 : []",fontsize=16,color="green",shape="box"];62 -> 63[label="",style="dashed", color="green", weight=3]; 11.52/4.52 63[label="vy3 vy40 vy50 vy60",fontsize=16,color="green",shape="box"];63 -> 64[label="",style="dashed", color="green", weight=3]; 11.52/4.52 63 -> 65[label="",style="dashed", color="green", weight=3]; 11.52/4.52 63 -> 66[label="",style="dashed", color="green", weight=3]; 11.52/4.52 64[label="vy40",fontsize=16,color="green",shape="box"];65[label="vy50",fontsize=16,color="green",shape="box"];66[label="vy60",fontsize=16,color="green",shape="box"];} 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (8) 11.52/4.52 Complex Obligation (AND) 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (9) 11.52/4.52 Obligation: 11.52/4.52 Q DP problem: 11.52/4.52 The TRS P consists of the following rules: 11.52/4.52 11.52/4.52 new_gtGtEs(:(vy60, vy61), vy3, vy40, vy50, h, ba, bb, bc) -> new_gtGtEs(vy61, vy3, vy40, vy50, h, ba, bb, bc) 11.52/4.52 11.52/4.52 R is empty. 11.52/4.52 Q is empty. 11.52/4.52 We have to consider all minimal (P,Q,R)-chains. 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (10) QDPSizeChangeProof (EQUIVALENT) 11.52/4.52 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. 11.52/4.52 11.52/4.52 From the DPs we obtained the following set of size-change graphs: 11.52/4.52 *new_gtGtEs(:(vy60, vy61), vy3, vy40, vy50, h, ba, bb, bc) -> new_gtGtEs(vy61, vy3, vy40, vy50, h, ba, bb, bc) 11.52/4.52 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 7 >= 7, 8 >= 8 11.52/4.52 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (11) 11.52/4.52 YES 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (12) 11.52/4.52 Obligation: 11.52/4.52 Q DP problem: 11.52/4.52 The TRS P consists of the following rules: 11.52/4.52 11.52/4.52 new_gtGtEs1(:(vy40, vy41), vy5, vy6, vy3, h, ba, bb, bc) -> new_gtGtEs1(vy41, vy5, vy6, vy3, h, ba, bb, bc) 11.52/4.52 11.52/4.52 R is empty. 11.52/4.52 Q is empty. 11.52/4.52 We have to consider all minimal (P,Q,R)-chains. 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (13) QDPSizeChangeProof (EQUIVALENT) 11.52/4.52 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. 11.52/4.52 11.52/4.52 From the DPs we obtained the following set of size-change graphs: 11.52/4.52 *new_gtGtEs1(:(vy40, vy41), vy5, vy6, vy3, h, ba, bb, bc) -> new_gtGtEs1(vy41, vy5, vy6, vy3, h, ba, bb, bc) 11.52/4.52 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 7 >= 7, 8 >= 8 11.52/4.52 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (14) 11.52/4.52 YES 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (15) 11.52/4.52 Obligation: 11.52/4.52 Q DP problem: 11.52/4.52 The TRS P consists of the following rules: 11.52/4.52 11.52/4.52 new_gtGtEs0(:(vy50, vy51), vy6, vy3, vy40, h, ba, bb, bc) -> new_gtGtEs0(vy51, vy6, vy3, vy40, h, ba, bb, bc) 11.52/4.52 11.52/4.52 R is empty. 11.52/4.52 Q is empty. 11.52/4.52 We have to consider all minimal (P,Q,R)-chains. 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (16) QDPSizeChangeProof (EQUIVALENT) 11.52/4.52 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. 11.52/4.52 11.52/4.52 From the DPs we obtained the following set of size-change graphs: 11.52/4.52 *new_gtGtEs0(:(vy50, vy51), vy6, vy3, vy40, h, ba, bb, bc) -> new_gtGtEs0(vy51, vy6, vy3, vy40, h, ba, bb, bc) 11.52/4.52 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 7 >= 7, 8 >= 8 11.52/4.52 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (17) 11.52/4.52 YES 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (18) 11.52/4.52 Obligation: 11.52/4.52 Q DP problem: 11.52/4.52 The TRS P consists of the following rules: 11.52/4.52 11.52/4.52 new_psPs(:(vy80, vy81), vy7, h) -> new_psPs(vy81, vy7, h) 11.52/4.52 11.52/4.52 R is empty. 11.52/4.52 Q is empty. 11.52/4.52 We have to consider all minimal (P,Q,R)-chains. 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (19) QDPSizeChangeProof (EQUIVALENT) 11.52/4.52 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. 11.52/4.52 11.52/4.52 From the DPs we obtained the following set of size-change graphs: 11.52/4.52 *new_psPs(:(vy80, vy81), vy7, h) -> new_psPs(vy81, vy7, h) 11.52/4.52 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 11.52/4.52 11.52/4.52 11.52/4.52 ---------------------------------------- 11.52/4.52 11.52/4.52 (20) 11.52/4.52 YES 11.79/4.56 EOF