9.00/3.91	YES
11.04/4.49	proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
11.04/4.49	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
11.04/4.49	
11.04/4.49	
11.04/4.49	H-Termination with start terms of the given HASKELL could be proven:
11.04/4.49	
11.04/4.49	(0) HASKELL
11.04/4.49	(1) LR [EQUIVALENT, 0 ms]
11.04/4.49	(2) HASKELL
11.04/4.49	(3) BR [EQUIVALENT, 0 ms]
11.04/4.49	(4) HASKELL
11.04/4.49	(5) COR [EQUIVALENT, 0 ms]
11.04/4.49	(6) HASKELL
11.04/4.49	(7) Narrow [SOUND, 0 ms]
11.04/4.49	(8) QDP
11.04/4.49	(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
11.04/4.49	(10) YES
11.04/4.49	
11.04/4.49	
11.04/4.49	----------------------------------------
11.04/4.49	
11.04/4.49	(0)
11.04/4.49	Obligation:
11.04/4.49	mainModule Main 
11.04/4.49	module Maybe where {
11.04/4.49	import qualified Main;
11.04/4.49	import qualified Monad;
11.04/4.49	import qualified Prelude;
11.04/4.49	}
11.04/4.49	module Main where {
11.04/4.49	import qualified Maybe;
11.04/4.49	import qualified Monad;
11.04/4.49	import qualified Prelude;
11.04/4.49	}
11.04/4.49	module Monad where {
11.04/4.49	import qualified Main;
11.04/4.49	import qualified Maybe;
11.04/4.49	import qualified Prelude;
11.04/4.49	foldM :: Monad b => (a  ->  c  ->  b a)  ->  a  ->  [c]  ->  b a;
11.04/4.49	foldM _ a [] = return a;
11.04/4.49	foldM f a (x : xs) = f a x >>= (\fax ->foldM f fax xs);
11.04/4.49	
11.04/4.49	foldM_ :: Monad c => (b  ->  a  ->  c b)  ->  b  ->  [a]  ->  c ();
11.04/4.49	foldM_ f a xs = foldM f a xs >> return ();
11.04/4.50	
11.04/4.50	}
11.04/4.50	
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(1) LR (EQUIVALENT)
11.04/4.50	Lambda Reductions:
11.04/4.50	The following Lambda expression
11.04/4.50	"\_->q"
11.04/4.50	is transformed to
11.04/4.50	"gtGt0 q _ = q;
11.04/4.50	"
11.04/4.50	The following Lambda expression
11.04/4.50	"\fax->foldM f fax xs"
11.04/4.50	is transformed to
11.04/4.50	"foldM0 f xs fax = foldM f fax xs;
11.04/4.50	"
11.04/4.50	
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(2)
11.04/4.50	Obligation:
11.04/4.50	mainModule Main 
11.04/4.50	module Maybe where {
11.04/4.50	import qualified Main;
11.04/4.50	import qualified Monad;
11.04/4.50	import qualified Prelude;
11.04/4.50	}
11.04/4.50	module Main where {
11.04/4.50	import qualified Maybe;
11.04/4.50	import qualified Monad;
11.04/4.50	import qualified Prelude;
11.04/4.50	}
11.04/4.50	module Monad where {
11.04/4.50	import qualified Main;
11.04/4.50	import qualified Maybe;
11.04/4.50	import qualified Prelude;
11.04/4.50	foldM :: Monad c => (b  ->  a  ->  c b)  ->  b  ->  [a]  ->  c b;
11.04/4.50	foldM _ a [] = return a;
11.04/4.50	foldM f a (x : xs) = f a x >>= foldM0 f xs;
11.04/4.50	
11.04/4.50	foldM0 f xs fax = foldM f fax xs;
11.04/4.50	
11.04/4.50	foldM_ :: Monad b => (c  ->  a  ->  b c)  ->  c  ->  [a]  ->  b ();
11.04/4.50	foldM_ f a xs = foldM f a xs >> return ();
11.04/4.50	
11.04/4.50	}
11.04/4.50	
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(3) BR (EQUIVALENT)
11.04/4.50	Replaced joker patterns by fresh variables and removed binding patterns.
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(4)
11.04/4.50	Obligation:
11.04/4.50	mainModule Main 
11.04/4.50	module Maybe where {
11.04/4.50	import qualified Main;
11.04/4.50	import qualified Monad;
11.04/4.50	import qualified Prelude;
11.04/4.50	}
11.04/4.50	module Main where {
11.04/4.50	import qualified Maybe;
11.04/4.50	import qualified Monad;
11.04/4.50	import qualified Prelude;
11.04/4.50	}
11.04/4.50	module Monad where {
11.04/4.50	import qualified Main;
11.04/4.50	import qualified Maybe;
11.04/4.50	import qualified Prelude;
11.04/4.50	foldM :: Monad a => (c  ->  b  ->  a c)  ->  c  ->  [b]  ->  a c;
11.04/4.50	foldM vz a [] = return a;
11.04/4.50	foldM f a (x : xs) = f a x >>= foldM0 f xs;
11.04/4.50	
11.04/4.50	foldM0 f xs fax = foldM f fax xs;
11.04/4.50	
11.04/4.50	foldM_ :: Monad a => (b  ->  c  ->  a b)  ->  b  ->  [c]  ->  a ();
11.04/4.50	foldM_ f a xs = foldM f a xs >> return ();
11.04/4.50	
11.04/4.50	}
11.04/4.50	
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(5) COR (EQUIVALENT)
11.04/4.50	Cond Reductions:
11.04/4.50	The following Function with conditions
11.04/4.50	"undefined |Falseundefined;
11.04/4.50	"
11.04/4.50	is transformed to
11.04/4.50	"undefined  = undefined1;
11.04/4.50	"
11.04/4.50	"undefined0 True = undefined;
11.04/4.50	"
11.04/4.50	"undefined1  = undefined0 False;
11.04/4.50	"
11.04/4.50	
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(6)
11.04/4.50	Obligation:
11.04/4.50	mainModule Main 
11.04/4.50	module Maybe where {
11.04/4.50	import qualified Main;
11.04/4.50	import qualified Monad;
11.04/4.50	import qualified Prelude;
11.04/4.50	}
11.04/4.50	module Main where {
11.04/4.50	import qualified Maybe;
11.04/4.50	import qualified Monad;
11.04/4.50	import qualified Prelude;
11.04/4.50	}
11.04/4.50	module Monad where {
11.04/4.50	import qualified Main;
11.04/4.50	import qualified Maybe;
11.04/4.50	import qualified Prelude;
11.04/4.50	foldM :: Monad a => (c  ->  b  ->  a c)  ->  c  ->  [b]  ->  a c;
11.04/4.50	foldM vz a [] = return a;
11.04/4.50	foldM f a (x : xs) = f a x >>= foldM0 f xs;
11.04/4.50	
11.04/4.50	foldM0 f xs fax = foldM f fax xs;
11.04/4.50	
11.04/4.50	foldM_ :: Monad c => (a  ->  b  ->  c a)  ->  a  ->  [b]  ->  c ();
11.04/4.50	foldM_ f a xs = foldM f a xs >> return ();
11.04/4.50	
11.04/4.50	}
11.04/4.50	
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(7) Narrow (SOUND)
11.04/4.50	Haskell To QDPs
11.04/4.50	
11.04/4.50	digraph dp_graph {
11.04/4.50	node [outthreshold=100, inthreshold=100];1[label="Monad.foldM_",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
11.04/4.50	3[label="Monad.foldM_ wu3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3];
11.04/4.50	4[label="Monad.foldM_ wu3 wu4",fontsize=16,color="grey",shape="box"];4 -> 5[label="",style="dashed", color="grey", weight=3];
11.04/4.50	5[label="Monad.foldM_ wu3 wu4 wu5",fontsize=16,color="black",shape="triangle"];5 -> 6[label="",style="solid", color="black", weight=3];
11.04/4.50	6[label="Monad.foldM wu3 wu4 wu5 >> return ()",fontsize=16,color="black",shape="box"];6 -> 7[label="",style="solid", color="black", weight=3];
11.04/4.50	7[label="Monad.foldM wu3 wu4 wu5 >>= gtGt0 (return ())",fontsize=16,color="burlywood",shape="triangle"];30[label="wu5/wu50 : wu51",fontsize=10,color="white",style="solid",shape="box"];7 -> 30[label="",style="solid", color="burlywood", weight=9];
11.04/4.50	30 -> 8[label="",style="solid", color="burlywood", weight=3];
11.04/4.50	31[label="wu5/[]",fontsize=10,color="white",style="solid",shape="box"];7 -> 31[label="",style="solid", color="burlywood", weight=9];
11.04/4.50	31 -> 9[label="",style="solid", color="burlywood", weight=3];
11.04/4.50	8[label="Monad.foldM wu3 wu4 (wu50 : wu51) >>= gtGt0 (return ())",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3];
11.04/4.50	9[label="Monad.foldM wu3 wu4 [] >>= gtGt0 (return ())",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3];
11.04/4.50	10 -> 12[label="",style="dashed", color="red", weight=0];
11.04/4.50	10[label="wu3 wu4 wu50 >>= Monad.foldM0 wu3 wu51 >>= gtGt0 (return ())",fontsize=16,color="magenta"];10 -> 13[label="",style="dashed", color="magenta", weight=3];
11.04/4.50	11[label="return wu4 >>= gtGt0 (return ())",fontsize=16,color="black",shape="box"];11 -> 14[label="",style="solid", color="black", weight=3];
11.04/4.50	13[label="wu3 wu4 wu50",fontsize=16,color="green",shape="box"];13 -> 19[label="",style="dashed", color="green", weight=3];
11.04/4.50	13 -> 20[label="",style="dashed", color="green", weight=3];
11.04/4.50	12[label="wu6 >>= Monad.foldM0 wu3 wu51 >>= gtGt0 (return ())",fontsize=16,color="burlywood",shape="triangle"];32[label="wu6/Nothing",fontsize=10,color="white",style="solid",shape="box"];12 -> 32[label="",style="solid", color="burlywood", weight=9];
11.04/4.50	32 -> 17[label="",style="solid", color="burlywood", weight=3];
11.04/4.50	33[label="wu6/Just wu60",fontsize=10,color="white",style="solid",shape="box"];12 -> 33[label="",style="solid", color="burlywood", weight=9];
11.04/4.50	33 -> 18[label="",style="solid", color="burlywood", weight=3];
11.04/4.50	14[label="Just wu4 >>= gtGt0 (return ())",fontsize=16,color="black",shape="box"];14 -> 21[label="",style="solid", color="black", weight=3];
11.04/4.50	19[label="wu4",fontsize=16,color="green",shape="box"];20[label="wu50",fontsize=16,color="green",shape="box"];17[label="Nothing >>= Monad.foldM0 wu3 wu51 >>= gtGt0 (return ())",fontsize=16,color="black",shape="box"];17 -> 22[label="",style="solid", color="black", weight=3];
11.04/4.50	18[label="Just wu60 >>= Monad.foldM0 wu3 wu51 >>= gtGt0 (return ())",fontsize=16,color="black",shape="box"];18 -> 23[label="",style="solid", color="black", weight=3];
11.04/4.50	21[label="gtGt0 (return ()) wu4",fontsize=16,color="black",shape="box"];21 -> 24[label="",style="solid", color="black", weight=3];
11.04/4.50	22[label="Nothing >>= gtGt0 (return ())",fontsize=16,color="black",shape="box"];22 -> 25[label="",style="solid", color="black", weight=3];
11.04/4.50	23[label="Monad.foldM0 wu3 wu51 wu60 >>= gtGt0 (return ())",fontsize=16,color="black",shape="box"];23 -> 26[label="",style="solid", color="black", weight=3];
11.04/4.50	24[label="return ()",fontsize=16,color="black",shape="box"];24 -> 27[label="",style="solid", color="black", weight=3];
11.04/4.50	25[label="Nothing",fontsize=16,color="green",shape="box"];26 -> 7[label="",style="dashed", color="red", weight=0];
11.04/4.50	26[label="Monad.foldM wu3 wu60 wu51 >>= gtGt0 (return ())",fontsize=16,color="magenta"];26 -> 28[label="",style="dashed", color="magenta", weight=3];
11.04/4.50	26 -> 29[label="",style="dashed", color="magenta", weight=3];
11.04/4.50	27[label="Just ()",fontsize=16,color="green",shape="box"];28[label="wu60",fontsize=16,color="green",shape="box"];29[label="wu51",fontsize=16,color="green",shape="box"];}
11.04/4.50	
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(8)
11.04/4.50	Obligation:
11.04/4.50	Q DP problem:
11.04/4.50	The TRS P consists of the following rules:
11.04/4.50	
11.04/4.50	   new_gtGtEs(wu3, wu51, h, ba) -> new_gtGtEs0(wu3, wu51, h, ba)
11.04/4.50	   new_gtGtEs0(wu3, :(wu50, wu51), h, ba) -> new_gtGtEs(wu3, wu51, h, ba)
11.04/4.50	
11.04/4.50	R is empty.
11.04/4.50	Q is empty.
11.04/4.50	We have to consider all minimal (P,Q,R)-chains.
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(9) QDPSizeChangeProof (EQUIVALENT)
11.04/4.50	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.04/4.50	
11.04/4.50	From the DPs we obtained the following set of size-change graphs:
11.04/4.50	*new_gtGtEs0(wu3, :(wu50, wu51), h, ba) -> new_gtGtEs(wu3, wu51, h, ba)
11.04/4.50	The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3, 4 >= 4
11.04/4.50	
11.04/4.50	
11.04/4.50	*new_gtGtEs(wu3, wu51, h, ba) -> new_gtGtEs0(wu3, wu51, h, ba)
11.04/4.50	The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4
11.04/4.50	
11.04/4.50	
11.04/4.50	----------------------------------------
11.04/4.50	
11.04/4.50	(10)
11.04/4.50	YES
11.26/8.38	EOF