8.26/3.63	YES
10.11/4.12	proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
10.11/4.12	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
10.11/4.12	
10.11/4.12	
10.11/4.12	H-Termination with start terms of the given HASKELL could be proven:
10.11/4.12	
10.11/4.12	(0) HASKELL
10.11/4.12	(1) LR [EQUIVALENT, 0 ms]
10.11/4.12	(2) HASKELL
10.11/4.12	(3) BR [EQUIVALENT, 0 ms]
10.11/4.12	(4) HASKELL
10.11/4.12	(5) COR [EQUIVALENT, 0 ms]
10.11/4.12	(6) HASKELL
10.11/4.12	(7) Narrow [SOUND, 0 ms]
10.11/4.12	(8) QDP
10.11/4.12	(9) QDPSizeChangeProof [EQUIVALENT, 0 ms]
10.11/4.12	(10) YES
10.11/4.12	
10.11/4.12	
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(0)
10.11/4.12	Obligation:
10.11/4.12	mainModule Main 
10.11/4.12	module Main where {
10.11/4.12	import qualified Prelude;
10.11/4.12	}
10.11/4.12	
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(1) LR (EQUIVALENT)
10.11/4.12	Lambda Reductions:
10.11/4.12	The following Lambda expression
10.11/4.12	"\xs->return (x : xs)"
10.11/4.12	is transformed to
10.11/4.12	"sequence0 x xs = return (x : xs);
10.11/4.12	"
10.11/4.12	The following Lambda expression
10.11/4.12	"\x->sequence cs >>= sequence0 x"
10.11/4.12	is transformed to
10.11/4.12	"sequence1 cs x = sequence cs >>= sequence0 x;
10.11/4.12	"
10.11/4.12	
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(2)
10.11/4.12	Obligation:
10.11/4.12	mainModule Main 
10.11/4.12	module Main where {
10.11/4.12	import qualified Prelude;
10.11/4.12	}
10.11/4.12	
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(3) BR (EQUIVALENT)
10.11/4.12	Replaced joker patterns by fresh variables and removed binding patterns.
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(4)
10.11/4.12	Obligation:
10.11/4.12	mainModule Main 
10.11/4.12	module Main where {
10.11/4.12	import qualified Prelude;
10.11/4.12	}
10.11/4.12	
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(5) COR (EQUIVALENT)
10.11/4.12	Cond Reductions:
10.11/4.12	The following Function with conditions
10.11/4.12	"undefined |Falseundefined;
10.11/4.12	"
10.11/4.12	is transformed to
10.11/4.12	"undefined  = undefined1;
10.11/4.12	"
10.11/4.12	"undefined0 True = undefined;
10.11/4.12	"
10.11/4.12	"undefined1  = undefined0 False;
10.11/4.12	"
10.11/4.12	
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(6)
10.11/4.12	Obligation:
10.11/4.12	mainModule Main 
10.11/4.12	module Main where {
10.11/4.12	import qualified Prelude;
10.11/4.12	}
10.11/4.12	
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(7) Narrow (SOUND)
10.11/4.12	Haskell To QDPs
10.11/4.12	
10.11/4.12	digraph dp_graph {
10.11/4.12	node [outthreshold=100, inthreshold=100];1[label="mapM",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
10.11/4.12	3[label="mapM vx3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3];
10.11/4.12	4[label="mapM vx3 vx4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3];
10.11/4.12	5[label="sequence . map vx3",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3];
10.11/4.12	6[label="sequence (map vx3 vx4)",fontsize=16,color="burlywood",shape="triangle"];44[label="vx4/vx40 : vx41",fontsize=10,color="white",style="solid",shape="box"];6 -> 44[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	44 -> 7[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	45[label="vx4/[]",fontsize=10,color="white",style="solid",shape="box"];6 -> 45[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	45 -> 8[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	7[label="sequence (map vx3 (vx40 : vx41))",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3];
10.11/4.12	8[label="sequence (map vx3 [])",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3];
10.11/4.12	9[label="sequence (vx3 vx40 : map vx3 vx41)",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3];
10.11/4.12	10[label="sequence []",fontsize=16,color="black",shape="box"];10 -> 12[label="",style="solid", color="black", weight=3];
10.11/4.12	11[label="vx3 vx40 >>= sequence1 (map vx3 vx41)",fontsize=16,color="black",shape="box"];11 -> 13[label="",style="solid", color="black", weight=3];
10.11/4.12	12[label="return []",fontsize=16,color="black",shape="box"];12 -> 14[label="",style="solid", color="black", weight=3];
10.11/4.12	13 -> 15[label="",style="dashed", color="red", weight=0];
10.11/4.12	13[label="primbindIO (vx3 vx40) (sequence1 (map vx3 vx41))",fontsize=16,color="magenta"];13 -> 16[label="",style="dashed", color="magenta", weight=3];
10.11/4.12	14[label="primretIO []",fontsize=16,color="black",shape="box"];14 -> 17[label="",style="solid", color="black", weight=3];
10.11/4.12	16[label="vx3 vx40",fontsize=16,color="green",shape="box"];16 -> 23[label="",style="dashed", color="green", weight=3];
10.11/4.12	15[label="primbindIO vx5 (sequence1 (map vx3 vx41))",fontsize=16,color="burlywood",shape="triangle"];46[label="vx5/IO vx50",fontsize=10,color="white",style="solid",shape="box"];15 -> 46[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	46 -> 19[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	47[label="vx5/AProVE_IO vx50",fontsize=10,color="white",style="solid",shape="box"];15 -> 47[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	47 -> 20[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	48[label="vx5/AProVE_Exception vx50",fontsize=10,color="white",style="solid",shape="box"];15 -> 48[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	48 -> 21[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	49[label="vx5/AProVE_Error vx50",fontsize=10,color="white",style="solid",shape="box"];15 -> 49[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	49 -> 22[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	17[label="AProVE_IO []",fontsize=16,color="green",shape="box"];23[label="vx40",fontsize=16,color="green",shape="box"];19[label="primbindIO (IO vx50) (sequence1 (map vx3 vx41))",fontsize=16,color="black",shape="box"];19 -> 24[label="",style="solid", color="black", weight=3];
10.11/4.12	20[label="primbindIO (AProVE_IO vx50) (sequence1 (map vx3 vx41))",fontsize=16,color="black",shape="box"];20 -> 25[label="",style="solid", color="black", weight=3];
10.11/4.12	21[label="primbindIO (AProVE_Exception vx50) (sequence1 (map vx3 vx41))",fontsize=16,color="black",shape="box"];21 -> 26[label="",style="solid", color="black", weight=3];
10.11/4.12	22[label="primbindIO (AProVE_Error vx50) (sequence1 (map vx3 vx41))",fontsize=16,color="black",shape="box"];22 -> 27[label="",style="solid", color="black", weight=3];
10.11/4.12	24[label="error []",fontsize=16,color="red",shape="box"];25[label="sequence1 (map vx3 vx41) vx50",fontsize=16,color="black",shape="box"];25 -> 28[label="",style="solid", color="black", weight=3];
10.11/4.12	26[label="AProVE_Exception vx50",fontsize=16,color="green",shape="box"];27[label="AProVE_Error vx50",fontsize=16,color="green",shape="box"];28 -> 29[label="",style="dashed", color="red", weight=0];
10.11/4.12	28[label="sequence (map vx3 vx41) >>= sequence0 vx50",fontsize=16,color="magenta"];28 -> 30[label="",style="dashed", color="magenta", weight=3];
10.11/4.12	30 -> 6[label="",style="dashed", color="red", weight=0];
10.11/4.12	30[label="sequence (map vx3 vx41)",fontsize=16,color="magenta"];30 -> 31[label="",style="dashed", color="magenta", weight=3];
10.11/4.12	29[label="vx6 >>= sequence0 vx50",fontsize=16,color="black",shape="triangle"];29 -> 32[label="",style="solid", color="black", weight=3];
10.11/4.12	31[label="vx41",fontsize=16,color="green",shape="box"];32[label="primbindIO vx6 (sequence0 vx50)",fontsize=16,color="burlywood",shape="box"];50[label="vx6/IO vx60",fontsize=10,color="white",style="solid",shape="box"];32 -> 50[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	50 -> 33[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	51[label="vx6/AProVE_IO vx60",fontsize=10,color="white",style="solid",shape="box"];32 -> 51[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	51 -> 34[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	52[label="vx6/AProVE_Exception vx60",fontsize=10,color="white",style="solid",shape="box"];32 -> 52[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	52 -> 35[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	53[label="vx6/AProVE_Error vx60",fontsize=10,color="white",style="solid",shape="box"];32 -> 53[label="",style="solid", color="burlywood", weight=9];
10.11/4.12	53 -> 36[label="",style="solid", color="burlywood", weight=3];
10.11/4.12	33[label="primbindIO (IO vx60) (sequence0 vx50)",fontsize=16,color="black",shape="box"];33 -> 37[label="",style="solid", color="black", weight=3];
10.11/4.12	34[label="primbindIO (AProVE_IO vx60) (sequence0 vx50)",fontsize=16,color="black",shape="box"];34 -> 38[label="",style="solid", color="black", weight=3];
10.11/4.12	35[label="primbindIO (AProVE_Exception vx60) (sequence0 vx50)",fontsize=16,color="black",shape="box"];35 -> 39[label="",style="solid", color="black", weight=3];
10.11/4.12	36[label="primbindIO (AProVE_Error vx60) (sequence0 vx50)",fontsize=16,color="black",shape="box"];36 -> 40[label="",style="solid", color="black", weight=3];
10.11/4.12	37[label="error []",fontsize=16,color="red",shape="box"];38[label="sequence0 vx50 vx60",fontsize=16,color="black",shape="box"];38 -> 41[label="",style="solid", color="black", weight=3];
10.11/4.12	39[label="AProVE_Exception vx60",fontsize=16,color="green",shape="box"];40[label="AProVE_Error vx60",fontsize=16,color="green",shape="box"];41[label="return (vx50 : vx60)",fontsize=16,color="black",shape="box"];41 -> 42[label="",style="solid", color="black", weight=3];
10.11/4.12	42[label="primretIO (vx50 : vx60)",fontsize=16,color="black",shape="box"];42 -> 43[label="",style="solid", color="black", weight=3];
10.11/4.12	43[label="AProVE_IO (vx50 : vx60)",fontsize=16,color="green",shape="box"];}
10.11/4.12	
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(8)
10.11/4.12	Obligation:
10.11/4.12	Q DP problem:
10.11/4.12	The TRS P consists of the following rules:
10.11/4.12	
10.11/4.12	   new_primbindIO(vx3, vx41, h, ba) -> new_sequence(vx3, vx41, h, ba)
10.11/4.12	   new_sequence(vx3, :(vx40, vx41), h, ba) -> new_primbindIO(vx3, vx41, h, ba)
10.11/4.12	
10.11/4.12	R is empty.
10.11/4.12	Q is empty.
10.11/4.12	We have to consider all minimal (P,Q,R)-chains.
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(9) QDPSizeChangeProof (EQUIVALENT)
10.11/4.12	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. 
10.11/4.12	
10.11/4.12	From the DPs we obtained the following set of size-change graphs:
10.11/4.12	*new_sequence(vx3, :(vx40, vx41), h, ba) -> new_primbindIO(vx3, vx41, h, ba)
10.11/4.12	The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3, 4 >= 4
10.11/4.12	
10.11/4.12	
10.11/4.12	*new_primbindIO(vx3, vx41, h, ba) -> new_sequence(vx3, vx41, h, ba)
10.11/4.12	The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4
10.11/4.12	
10.11/4.12	
10.11/4.12	----------------------------------------
10.11/4.12	
10.11/4.12	(10)
10.11/4.12	YES
10.17/4.16	EOF