7.69/3.61	YES
9.72/4.15	proof of /export/starexec/sandbox2/benchmark/theBenchmark.hs
9.72/4.15	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
9.72/4.15	
9.72/4.15	
9.72/4.15	H-Termination with start terms of the given HASKELL could be proven:
9.72/4.15	
9.72/4.15	(0) HASKELL
9.72/4.15	(1) LR [EQUIVALENT, 0 ms]
9.72/4.15	(2) HASKELL
9.72/4.15	(3) BR [EQUIVALENT, 0 ms]
9.72/4.15	(4) HASKELL
9.72/4.15	(5) COR [EQUIVALENT, 0 ms]
9.72/4.15	(6) HASKELL
9.72/4.15	(7) LetRed [EQUIVALENT, 0 ms]
9.72/4.15	(8) HASKELL
9.72/4.15	(9) Narrow [SOUND, 0 ms]
9.72/4.15	(10) QDP
9.72/4.15	(11) QDPSizeChangeProof [EQUIVALENT, 0 ms]
9.72/4.15	(12) YES
9.72/4.15	
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(0)
9.72/4.15	Obligation:
9.72/4.15	mainModule Main 
9.72/4.15	module Main where {
9.72/4.15	import qualified Prelude;
9.72/4.15	}
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(1) LR (EQUIVALENT)
9.72/4.15	Lambda Reductions:
9.72/4.15	The following Lambda expression
9.72/4.15	"\(_,zs)->zs"
9.72/4.15	is transformed to
9.72/4.15	"zs0 (_,zs) = zs;
9.72/4.15	"
9.72/4.15	The following Lambda expression
9.72/4.15	"\(ys,_)->ys"
9.72/4.15	is transformed to
9.72/4.15	"ys0 (ys,_) = ys;
9.72/4.15	"
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(2)
9.72/4.15	Obligation:
9.72/4.15	mainModule Main 
9.72/4.15	module Main where {
9.72/4.15	import qualified Prelude;
9.72/4.15	}
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(3) BR (EQUIVALENT)
9.72/4.15	Replaced joker patterns by fresh variables and removed binding patterns.
9.72/4.15	
9.72/4.15	Binding Reductions:
9.72/4.15	The bind variable of the following binding Pattern
9.72/4.15	"xs@(vx : vy)"
9.72/4.15	is replaced by the following term
9.72/4.15	"vx : vy"
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(4)
9.72/4.15	Obligation:
9.72/4.15	mainModule Main 
9.72/4.15	module Main where {
9.72/4.15	import qualified Prelude;
9.72/4.15	}
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(5) COR (EQUIVALENT)
9.72/4.15	Cond Reductions:
9.72/4.15	The following Function with conditions
9.72/4.15	"undefined |Falseundefined;
9.72/4.15	"
9.72/4.15	is transformed to
9.72/4.15	"undefined  = undefined1;
9.72/4.15	"
9.72/4.15	"undefined0 True = undefined;
9.72/4.15	"
9.72/4.15	"undefined1  = undefined0 False;
9.72/4.15	"
9.72/4.15	The following Function with conditions
9.72/4.15	"span p [] = ([],[]);
9.72/4.15	span p (vx : vy)|p vx(vx : ys,zs)|otherwise([],vx : vy) where {
9.72/4.15	vu43  = span p vy;
9.72/4.15	;
9.72/4.15	ys  = ys0 vu43;
9.72/4.15	;
9.72/4.15	ys0 (ys,wu) = ys;
9.72/4.15	;
9.72/4.15	zs  = zs0 vu43;
9.72/4.15	;
9.72/4.15	zs0 (vz,zs) = zs;
9.72/4.15	} 
9.72/4.15	;
9.72/4.15	"
9.72/4.15	is transformed to
9.72/4.15	"span p [] = span3 p [];
9.72/4.15	span p (vx : vy) = span2 p (vx : vy);
9.72/4.15	"
9.72/4.15	"span2 p (vx : vy) = span1 p vx vy (p vx) where {
9.72/4.15	span0 p vx vy True = ([],vx : vy);
9.72/4.15	;
9.72/4.15	span1 p vx vy True = (vx : ys,zs);
9.72/4.15	span1 p vx vy False = span0 p vx vy otherwise;
9.72/4.15	;
9.72/4.15	vu43  = span p vy;
9.72/4.15	;
9.72/4.15	ys  = ys0 vu43;
9.72/4.15	;
9.72/4.15	ys0 (ys,wu) = ys;
9.72/4.15	;
9.72/4.15	zs  = zs0 vu43;
9.72/4.15	;
9.72/4.15	zs0 (vz,zs) = zs;
9.72/4.15	} 
9.72/4.15	;
9.72/4.15	"
9.72/4.15	"span3 p [] = ([],[]);
9.72/4.15	span3 wx wy = span2 wx wy;
9.72/4.15	"
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(6)
9.72/4.15	Obligation:
9.72/4.15	mainModule Main 
9.72/4.15	module Main where {
9.72/4.15	import qualified Prelude;
9.72/4.15	}
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(7) LetRed (EQUIVALENT)
9.72/4.15	Let/Where Reductions:
9.72/4.15	The bindings of the following Let/Where expression
9.72/4.15	"span1 p vx vy (p vx) where {
9.72/4.15	span0 p vx vy True = ([],vx : vy);
9.72/4.15	;
9.72/4.15	span1 p vx vy True = (vx : ys,zs);
9.72/4.15	span1 p vx vy False = span0 p vx vy otherwise;
9.72/4.15	;
9.72/4.15	vu43  = span p vy;
9.72/4.15	;
9.72/4.15	ys  = ys0 vu43;
9.72/4.15	;
9.72/4.15	ys0 (ys,wu) = ys;
9.72/4.15	;
9.72/4.15	zs  = zs0 vu43;
9.72/4.15	;
9.72/4.15	zs0 (vz,zs) = zs;
9.72/4.15	} 
9.72/4.15	"
9.72/4.15	are unpacked to the following functions on top level
9.72/4.15	"span2Zs wz xu = span2Zs0 wz xu (span2Vu43 wz xu);
9.72/4.15	"
9.72/4.15	"span2Zs0 wz xu (vz,zs) = zs;
9.72/4.15	"
9.72/4.15	"span2Ys wz xu = span2Ys0 wz xu (span2Vu43 wz xu);
9.72/4.15	"
9.72/4.15	"span2Span1 wz xu p vx vy True = (vx : span2Ys wz xu,span2Zs wz xu);
9.72/4.15	span2Span1 wz xu p vx vy False = span2Span0 wz xu p vx vy otherwise;
9.72/4.15	"
9.72/4.15	"span2Span0 wz xu p vx vy True = ([],vx : vy);
9.72/4.15	"
9.72/4.15	"span2Ys0 wz xu (ys,wu) = ys;
9.72/4.15	"
9.72/4.15	"span2Vu43 wz xu = span wz xu;
9.72/4.15	"
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(8)
9.72/4.15	Obligation:
9.72/4.15	mainModule Main 
9.72/4.15	module Main where {
9.72/4.15	import qualified Prelude;
9.72/4.15	}
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(9) Narrow (SOUND)
9.72/4.15	Haskell To QDPs
9.72/4.15	
9.72/4.15	digraph dp_graph {
9.72/4.15	node [outthreshold=100, inthreshold=100];1[label="span",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
9.72/4.15	3[label="span xv3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3];
9.72/4.15	4[label="span xv3 xv4",fontsize=16,color="burlywood",shape="triangle"];39[label="xv4/xv40 : xv41",fontsize=10,color="white",style="solid",shape="box"];4 -> 39[label="",style="solid", color="burlywood", weight=9];
9.72/4.15	39 -> 5[label="",style="solid", color="burlywood", weight=3];
9.72/4.15	40[label="xv4/[]",fontsize=10,color="white",style="solid",shape="box"];4 -> 40[label="",style="solid", color="burlywood", weight=9];
9.72/4.15	40 -> 6[label="",style="solid", color="burlywood", weight=3];
9.72/4.15	5[label="span xv3 (xv40 : xv41)",fontsize=16,color="black",shape="box"];5 -> 7[label="",style="solid", color="black", weight=3];
9.72/4.15	6[label="span xv3 []",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3];
9.72/4.15	7[label="span2 xv3 (xv40 : xv41)",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3];
9.72/4.15	8[label="span3 xv3 []",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3];
9.72/4.15	9 -> 11[label="",style="dashed", color="red", weight=0];
9.72/4.15	9[label="span2Span1 xv3 xv41 xv3 xv40 xv41 (xv3 xv40)",fontsize=16,color="magenta"];9 -> 12[label="",style="dashed", color="magenta", weight=3];
9.72/4.15	10[label="([],[])",fontsize=16,color="green",shape="box"];12[label="xv3 xv40",fontsize=16,color="green",shape="box"];12 -> 16[label="",style="dashed", color="green", weight=3];
9.72/4.15	11[label="span2Span1 xv3 xv41 xv3 xv40 xv41 xv5",fontsize=16,color="burlywood",shape="triangle"];41[label="xv5/False",fontsize=10,color="white",style="solid",shape="box"];11 -> 41[label="",style="solid", color="burlywood", weight=9];
9.72/4.15	41 -> 14[label="",style="solid", color="burlywood", weight=3];
9.72/4.15	42[label="xv5/True",fontsize=10,color="white",style="solid",shape="box"];11 -> 42[label="",style="solid", color="burlywood", weight=9];
9.72/4.15	42 -> 15[label="",style="solid", color="burlywood", weight=3];
9.72/4.15	16[label="xv40",fontsize=16,color="green",shape="box"];14[label="span2Span1 xv3 xv41 xv3 xv40 xv41 False",fontsize=16,color="black",shape="box"];14 -> 17[label="",style="solid", color="black", weight=3];
9.72/4.15	15[label="span2Span1 xv3 xv41 xv3 xv40 xv41 True",fontsize=16,color="black",shape="box"];15 -> 18[label="",style="solid", color="black", weight=3];
9.72/4.15	17[label="span2Span0 xv3 xv41 xv3 xv40 xv41 otherwise",fontsize=16,color="black",shape="box"];17 -> 19[label="",style="solid", color="black", weight=3];
9.72/4.15	18[label="(xv40 : span2Ys xv3 xv41,span2Zs xv3 xv41)",fontsize=16,color="green",shape="box"];18 -> 20[label="",style="dashed", color="green", weight=3];
9.72/4.15	18 -> 21[label="",style="dashed", color="green", weight=3];
9.72/4.15	19[label="span2Span0 xv3 xv41 xv3 xv40 xv41 True",fontsize=16,color="black",shape="box"];19 -> 22[label="",style="solid", color="black", weight=3];
9.72/4.15	20[label="span2Ys xv3 xv41",fontsize=16,color="black",shape="box"];20 -> 23[label="",style="solid", color="black", weight=3];
9.72/4.15	21[label="span2Zs xv3 xv41",fontsize=16,color="black",shape="box"];21 -> 24[label="",style="solid", color="black", weight=3];
9.72/4.15	22[label="([],xv40 : xv41)",fontsize=16,color="green",shape="box"];23 -> 27[label="",style="dashed", color="red", weight=0];
9.72/4.15	23[label="span2Ys0 xv3 xv41 (span2Vu43 xv3 xv41)",fontsize=16,color="magenta"];23 -> 28[label="",style="dashed", color="magenta", weight=3];
9.72/4.15	24 -> 32[label="",style="dashed", color="red", weight=0];
9.72/4.15	24[label="span2Zs0 xv3 xv41 (span2Vu43 xv3 xv41)",fontsize=16,color="magenta"];24 -> 33[label="",style="dashed", color="magenta", weight=3];
9.72/4.15	28[label="span2Vu43 xv3 xv41",fontsize=16,color="black",shape="triangle"];28 -> 30[label="",style="solid", color="black", weight=3];
9.72/4.15	27[label="span2Ys0 xv3 xv41 xv6",fontsize=16,color="burlywood",shape="triangle"];43[label="xv6/(xv60,xv61)",fontsize=10,color="white",style="solid",shape="box"];27 -> 43[label="",style="solid", color="burlywood", weight=9];
9.72/4.15	43 -> 31[label="",style="solid", color="burlywood", weight=3];
9.72/4.15	33 -> 28[label="",style="dashed", color="red", weight=0];
9.72/4.15	33[label="span2Vu43 xv3 xv41",fontsize=16,color="magenta"];32[label="span2Zs0 xv3 xv41 xv7",fontsize=16,color="burlywood",shape="triangle"];44[label="xv7/(xv70,xv71)",fontsize=10,color="white",style="solid",shape="box"];32 -> 44[label="",style="solid", color="burlywood", weight=9];
9.72/4.15	44 -> 35[label="",style="solid", color="burlywood", weight=3];
9.72/4.15	30 -> 4[label="",style="dashed", color="red", weight=0];
9.72/4.15	30[label="span xv3 xv41",fontsize=16,color="magenta"];30 -> 36[label="",style="dashed", color="magenta", weight=3];
9.72/4.15	31[label="span2Ys0 xv3 xv41 (xv60,xv61)",fontsize=16,color="black",shape="box"];31 -> 37[label="",style="solid", color="black", weight=3];
9.72/4.15	35[label="span2Zs0 xv3 xv41 (xv70,xv71)",fontsize=16,color="black",shape="box"];35 -> 38[label="",style="solid", color="black", weight=3];
9.72/4.15	36[label="xv41",fontsize=16,color="green",shape="box"];37[label="xv60",fontsize=16,color="green",shape="box"];38[label="xv71",fontsize=16,color="green",shape="box"];}
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(10)
9.72/4.15	Obligation:
9.72/4.15	Q DP problem:
9.72/4.15	The TRS P consists of the following rules:
9.72/4.15	
9.72/4.15	   new_span(xv3, :(xv40, xv41), h) -> new_span2Span1(xv3, xv41, xv40, h)
9.72/4.15	   new_span2Vu43(xv3, xv41, h) -> new_span(xv3, xv41, h)
9.72/4.15	   new_span2Span1(xv3, xv41, xv40, h) -> new_span(xv3, xv41, h)
9.72/4.15	   new_span2Span1(xv3, xv41, xv40, h) -> new_span2Vu43(xv3, xv41, h)
9.72/4.15	
9.72/4.15	R is empty.
9.72/4.15	Q is empty.
9.72/4.15	We have to consider all minimal (P,Q,R)-chains.
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(11) QDPSizeChangeProof (EQUIVALENT)
9.72/4.15	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. 
9.72/4.15	
9.72/4.15	From the DPs we obtained the following set of size-change graphs:
9.72/4.15	*new_span2Span1(xv3, xv41, xv40, h) -> new_span(xv3, xv41, h)
9.72/4.15	The graph contains the following edges 1 >= 1, 2 >= 2, 4 >= 3
9.72/4.15	
9.72/4.15	
9.72/4.15	*new_span2Span1(xv3, xv41, xv40, h) -> new_span2Vu43(xv3, xv41, h)
9.72/4.15	The graph contains the following edges 1 >= 1, 2 >= 2, 4 >= 3
9.72/4.15	
9.72/4.15	
9.72/4.15	*new_span2Vu43(xv3, xv41, h) -> new_span(xv3, xv41, h)
9.72/4.15	The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3
9.72/4.15	
9.72/4.15	
9.72/4.15	*new_span(xv3, :(xv40, xv41), h) -> new_span2Span1(xv3, xv41, xv40, h)
9.72/4.15	The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3, 3 >= 4
9.72/4.15	
9.72/4.15	
9.72/4.15	----------------------------------------
9.72/4.15	
9.72/4.15	(12)
9.72/4.15	YES
10.06/4.22	EOF