/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.hs /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.hs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty H-Termination with start terms of the given HASKELL could not be shown: (0) HASKELL (1) LR [EQUIVALENT, 0 ms] (2) HASKELL (3) BR [EQUIVALENT, 0 ms] (4) HASKELL (5) COR [EQUIVALENT, 0 ms] (6) HASKELL (7) Narrow [SOUND, 0 ms] (8) AND (9) QDP (10) MRRProof [EQUIVALENT, 25 ms] (11) QDP (12) NonTerminationLoopProof [COMPLETE, 0 ms] (13) NO (14) QDP (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] (16) YES (17) Narrow [COMPLETE, 0 ms] (18) TRUE ---------------------------------------- (0) Obligation: mainModule Main module Maybe where { import qualified Main; import qualified Monad; import qualified Prelude; } module Main where { import qualified Maybe; import qualified Monad; import qualified Prelude; } module Monad where { import qualified Main; import qualified Maybe; import qualified Prelude; foldM :: Monad b => (a -> c -> b a) -> a -> [c] -> b a; foldM _ a [] = return a; foldM f a (x : xs) = f a x >>= (\fax ->foldM f fax xs); } ---------------------------------------- (1) LR (EQUIVALENT) Lambda Reductions: The following Lambda expression "\fax->foldM f fax xs" is transformed to "foldM0 f xs fax = foldM f fax xs; " ---------------------------------------- (2) Obligation: mainModule Main module Maybe where { import qualified Main; import qualified Monad; import qualified Prelude; } module Main where { import qualified Maybe; import qualified Monad; import qualified Prelude; } module Monad where { import qualified Main; import qualified Maybe; import qualified Prelude; foldM :: Monad b => (a -> c -> b a) -> a -> [c] -> b a; foldM _ a [] = return a; foldM f a (x : xs) = f a x >>= foldM0 f xs; foldM0 f xs fax = foldM f fax xs; } ---------------------------------------- (3) BR (EQUIVALENT) Replaced joker patterns by fresh variables and removed binding patterns. ---------------------------------------- (4) Obligation: mainModule Main module Maybe where { import qualified Main; import qualified Monad; import qualified Prelude; } module Main where { import qualified Maybe; import qualified Monad; import qualified Prelude; } module Monad where { import qualified Main; import qualified Maybe; import qualified Prelude; foldM :: Monad a => (c -> b -> a c) -> c -> [b] -> a c; foldM vy a [] = return a; foldM f a (x : xs) = f a x >>= foldM0 f xs; foldM0 f xs fax = foldM f fax xs; } ---------------------------------------- (5) COR (EQUIVALENT) Cond Reductions: The following Function with conditions "undefined |Falseundefined; " is transformed to "undefined = undefined1; " "undefined0 True = undefined; " "undefined1 = undefined0 False; " ---------------------------------------- (6) Obligation: mainModule Main module Maybe where { import qualified Main; import qualified Monad; import qualified Prelude; } module Main where { import qualified Maybe; import qualified Monad; import qualified Prelude; } module Monad where { import qualified Main; import qualified Maybe; import qualified Prelude; foldM :: Monad c => (b -> a -> c b) -> b -> [a] -> c b; foldM vy a [] = return a; foldM f a (x : xs) = f a x >>= foldM0 f xs; foldM0 f xs fax = foldM f fax xs; } ---------------------------------------- (7) Narrow (SOUND) Haskell To QDPs digraph dp_graph { node [outthreshold=100, inthreshold=100];1[label="Monad.foldM",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 3[label="Monad.foldM vz3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 4[label="Monad.foldM vz3 vz4",fontsize=16,color="grey",shape="box"];4 -> 5[label="",style="dashed", color="grey", weight=3]; 5[label="Monad.foldM vz3 vz4 vz5",fontsize=16,color="burlywood",shape="triangle"];40[label="vz5/vz50 : vz51",fontsize=10,color="white",style="solid",shape="box"];5 -> 40[label="",style="solid", color="burlywood", weight=9]; 40 -> 6[label="",style="solid", color="burlywood", weight=3]; 41[label="vz5/[]",fontsize=10,color="white",style="solid",shape="box"];5 -> 41[label="",style="solid", color="burlywood", weight=9]; 41 -> 7[label="",style="solid", color="burlywood", weight=3]; 6[label="Monad.foldM vz3 vz4 (vz50 : vz51)",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3]; 7[label="Monad.foldM vz3 vz4 []",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3]; 8 -> 10[label="",style="dashed", color="red", weight=0]; 8[label="vz3 vz4 vz50 >>= Monad.foldM0 vz3 vz51",fontsize=16,color="magenta"];8 -> 11[label="",style="dashed", color="magenta", weight=3]; 9[label="return vz4",fontsize=16,color="black",shape="box"];9 -> 12[label="",style="solid", color="black", weight=3]; 11[label="vz3 vz4 vz50",fontsize=16,color="green",shape="box"];11 -> 17[label="",style="dashed", color="green", weight=3]; 11 -> 18[label="",style="dashed", color="green", weight=3]; 10[label="vz6 >>= Monad.foldM0 vz3 vz51",fontsize=16,color="burlywood",shape="triangle"];42[label="vz6/vz60 : vz61",fontsize=10,color="white",style="solid",shape="box"];10 -> 42[label="",style="solid", color="burlywood", weight=9]; 42 -> 15[label="",style="solid", color="burlywood", weight=3]; 43[label="vz6/[]",fontsize=10,color="white",style="solid",shape="box"];10 -> 43[label="",style="solid", color="burlywood", weight=9]; 43 -> 16[label="",style="solid", color="burlywood", weight=3]; 12[label="vz4 : []",fontsize=16,color="green",shape="box"];17[label="vz4",fontsize=16,color="green",shape="box"];18[label="vz50",fontsize=16,color="green",shape="box"];15[label="vz60 : vz61 >>= Monad.foldM0 vz3 vz51",fontsize=16,color="black",shape="box"];15 -> 19[label="",style="solid", color="black", weight=3]; 16[label="[] >>= Monad.foldM0 vz3 vz51",fontsize=16,color="black",shape="box"];16 -> 20[label="",style="solid", color="black", weight=3]; 19 -> 25[label="",style="dashed", color="red", weight=0]; 19[label="Monad.foldM0 vz3 vz51 vz60 ++ (vz61 >>= Monad.foldM0 vz3 vz51)",fontsize=16,color="magenta"];19 -> 26[label="",style="dashed", color="magenta", weight=3]; 19 -> 27[label="",style="dashed", color="magenta", weight=3]; 20[label="[]",fontsize=16,color="green",shape="box"];26[label="Monad.foldM0 vz3 vz51 vz60",fontsize=16,color="black",shape="box"];26 -> 30[label="",style="solid", color="black", weight=3]; 27 -> 10[label="",style="dashed", color="red", weight=0]; 27[label="vz61 >>= Monad.foldM0 vz3 vz51",fontsize=16,color="magenta"];27 -> 31[label="",style="dashed", color="magenta", weight=3]; 25[label="vz8 ++ vz7",fontsize=16,color="burlywood",shape="triangle"];44[label="vz8/vz80 : vz81",fontsize=10,color="white",style="solid",shape="box"];25 -> 44[label="",style="solid", color="burlywood", weight=9]; 44 -> 32[label="",style="solid", color="burlywood", weight=3]; 45[label="vz8/[]",fontsize=10,color="white",style="solid",shape="box"];25 -> 45[label="",style="solid", color="burlywood", weight=9]; 45 -> 33[label="",style="solid", color="burlywood", weight=3]; 30 -> 5[label="",style="dashed", color="red", weight=0]; 30[label="Monad.foldM vz3 vz60 vz51",fontsize=16,color="magenta"];30 -> 34[label="",style="dashed", color="magenta", weight=3]; 30 -> 35[label="",style="dashed", color="magenta", weight=3]; 31[label="vz61",fontsize=16,color="green",shape="box"];32[label="(vz80 : vz81) ++ vz7",fontsize=16,color="black",shape="box"];32 -> 36[label="",style="solid", color="black", weight=3]; 33[label="[] ++ vz7",fontsize=16,color="black",shape="box"];33 -> 37[label="",style="solid", color="black", weight=3]; 34[label="vz60",fontsize=16,color="green",shape="box"];35[label="vz51",fontsize=16,color="green",shape="box"];36[label="vz80 : vz81 ++ vz7",fontsize=16,color="green",shape="box"];36 -> 38[label="",style="dashed", color="green", weight=3]; 37[label="vz7",fontsize=16,color="green",shape="box"];38 -> 25[label="",style="dashed", color="red", weight=0]; 38[label="vz81 ++ vz7",fontsize=16,color="magenta"];38 -> 39[label="",style="dashed", color="magenta", weight=3]; 39[label="vz81",fontsize=16,color="green",shape="box"];} ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: new_foldM(vz3, :(vz50, vz51), h, ba) -> new_gtGtEs(vz3, vz51, h, ba) new_gtGtEs(vz3, vz51, h, ba) -> new_gtGtEs(vz3, vz51, h, ba) new_gtGtEs(vz3, vz51, h, ba) -> new_foldM(vz3, vz51, h, ba) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: new_foldM(vz3, :(vz50, vz51), h, ba) -> new_gtGtEs(vz3, vz51, h, ba) new_gtGtEs(vz3, vz51, h, ba) -> new_foldM(vz3, vz51, h, ba) Used ordering: Polynomial interpretation [POLO]: POL(:(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(new_foldM(x_1, x_2, x_3, x_4)) = x_1 + 2*x_2 + x_3 + x_4 POL(new_gtGtEs(x_1, x_2, x_3, x_4)) = 2 + x_1 + 2*x_2 + x_3 + x_4 ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: new_gtGtEs(vz3, vz51, h, ba) -> new_gtGtEs(vz3, vz51, h, ba) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = new_gtGtEs(vz3, vz51, h, ba) evaluates to t =new_gtGtEs(vz3, vz51, h, ba) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from new_gtGtEs(vz3, vz51, h, ba) to new_gtGtEs(vz3, vz51, h, ba). ---------------------------------------- (13) NO ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: new_psPs(:(vz80, vz81), vz7, h) -> new_psPs(vz81, vz7, h) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *new_psPs(:(vz80, vz81), vz7, h) -> new_psPs(vz81, vz7, h) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 ---------------------------------------- (16) YES ---------------------------------------- (17) Narrow (COMPLETE) Haskell To QDPs digraph dp_graph { node [outthreshold=100, inthreshold=100];1[label="Monad.foldM",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 3[label="Monad.foldM vz3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 4[label="Monad.foldM vz3 vz4",fontsize=16,color="grey",shape="box"];4 -> 5[label="",style="dashed", color="grey", weight=3]; 5[label="Monad.foldM vz3 vz4 vz5",fontsize=16,color="burlywood",shape="triangle"];40[label="vz5/vz50 : vz51",fontsize=10,color="white",style="solid",shape="box"];5 -> 40[label="",style="solid", color="burlywood", weight=9]; 40 -> 6[label="",style="solid", color="burlywood", weight=3]; 41[label="vz5/[]",fontsize=10,color="white",style="solid",shape="box"];5 -> 41[label="",style="solid", color="burlywood", weight=9]; 41 -> 7[label="",style="solid", color="burlywood", weight=3]; 6[label="Monad.foldM vz3 vz4 (vz50 : vz51)",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3]; 7[label="Monad.foldM vz3 vz4 []",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3]; 8 -> 10[label="",style="dashed", color="red", weight=0]; 8[label="vz3 vz4 vz50 >>= Monad.foldM0 vz3 vz51",fontsize=16,color="magenta"];8 -> 11[label="",style="dashed", color="magenta", weight=3]; 9[label="return vz4",fontsize=16,color="black",shape="box"];9 -> 12[label="",style="solid", color="black", weight=3]; 11[label="vz3 vz4 vz50",fontsize=16,color="green",shape="box"];11 -> 17[label="",style="dashed", color="green", weight=3]; 11 -> 18[label="",style="dashed", color="green", weight=3]; 10[label="vz6 >>= Monad.foldM0 vz3 vz51",fontsize=16,color="burlywood",shape="triangle"];42[label="vz6/vz60 : vz61",fontsize=10,color="white",style="solid",shape="box"];10 -> 42[label="",style="solid", color="burlywood", weight=9]; 42 -> 15[label="",style="solid", color="burlywood", weight=3]; 43[label="vz6/[]",fontsize=10,color="white",style="solid",shape="box"];10 -> 43[label="",style="solid", color="burlywood", weight=9]; 43 -> 16[label="",style="solid", color="burlywood", weight=3]; 12[label="vz4 : []",fontsize=16,color="green",shape="box"];17[label="vz4",fontsize=16,color="green",shape="box"];18[label="vz50",fontsize=16,color="green",shape="box"];15[label="vz60 : vz61 >>= Monad.foldM0 vz3 vz51",fontsize=16,color="black",shape="box"];15 -> 19[label="",style="solid", color="black", weight=3]; 16[label="[] >>= Monad.foldM0 vz3 vz51",fontsize=16,color="black",shape="box"];16 -> 20[label="",style="solid", color="black", weight=3]; 19 -> 25[label="",style="dashed", color="red", weight=0]; 19[label="Monad.foldM0 vz3 vz51 vz60 ++ (vz61 >>= Monad.foldM0 vz3 vz51)",fontsize=16,color="magenta"];19 -> 26[label="",style="dashed", color="magenta", weight=3]; 19 -> 27[label="",style="dashed", color="magenta", weight=3]; 20[label="[]",fontsize=16,color="green",shape="box"];26[label="Monad.foldM0 vz3 vz51 vz60",fontsize=16,color="black",shape="box"];26 -> 30[label="",style="solid", color="black", weight=3]; 27 -> 10[label="",style="dashed", color="red", weight=0]; 27[label="vz61 >>= Monad.foldM0 vz3 vz51",fontsize=16,color="magenta"];27 -> 31[label="",style="dashed", color="magenta", weight=3]; 25[label="vz8 ++ vz7",fontsize=16,color="burlywood",shape="triangle"];44[label="vz8/vz80 : vz81",fontsize=10,color="white",style="solid",shape="box"];25 -> 44[label="",style="solid", color="burlywood", weight=9]; 44 -> 32[label="",style="solid", color="burlywood", weight=3]; 45[label="vz8/[]",fontsize=10,color="white",style="solid",shape="box"];25 -> 45[label="",style="solid", color="burlywood", weight=9]; 45 -> 33[label="",style="solid", color="burlywood", weight=3]; 30 -> 5[label="",style="dashed", color="red", weight=0]; 30[label="Monad.foldM vz3 vz60 vz51",fontsize=16,color="magenta"];30 -> 34[label="",style="dashed", color="magenta", weight=3]; 30 -> 35[label="",style="dashed", color="magenta", weight=3]; 31[label="vz61",fontsize=16,color="green",shape="box"];32[label="(vz80 : vz81) ++ vz7",fontsize=16,color="black",shape="box"];32 -> 36[label="",style="solid", color="black", weight=3]; 33[label="[] ++ vz7",fontsize=16,color="black",shape="box"];33 -> 37[label="",style="solid", color="black", weight=3]; 34[label="vz60",fontsize=16,color="green",shape="box"];35[label="vz51",fontsize=16,color="green",shape="box"];36[label="vz80 : vz81 ++ vz7",fontsize=16,color="green",shape="box"];36 -> 38[label="",style="dashed", color="green", weight=3]; 37[label="vz7",fontsize=16,color="green",shape="box"];38 -> 25[label="",style="dashed", color="red", weight=0]; 38[label="vz81 ++ vz7",fontsize=16,color="magenta"];38 -> 39[label="",style="dashed", color="magenta", weight=3]; 39[label="vz81",fontsize=16,color="green",shape="box"];} ---------------------------------------- (18) TRUE