11.78/4.78	YES
13.96/5.36	proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
13.96/5.36	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
13.96/5.36	
13.96/5.36	
13.96/5.36	H-Termination with start terms of the given HASKELL could be proven:
13.96/5.36	
13.96/5.36	(0) HASKELL
13.96/5.36	(1) CR [EQUIVALENT, 0 ms]
13.96/5.36	(2) HASKELL
13.96/5.36	(3) BR [EQUIVALENT, 0 ms]
13.96/5.36	(4) HASKELL
13.96/5.36	(5) COR [EQUIVALENT, 26 ms]
13.96/5.36	(6) HASKELL
13.96/5.36	(7) Narrow [SOUND, 0 ms]
13.96/5.36	(8) AND
13.96/5.36	    (9) QDP
13.96/5.36	        (10) MRRProof [EQUIVALENT, 29 ms]
13.96/5.36	        (11) QDP
13.96/5.36	        (12) DependencyGraphProof [EQUIVALENT, 0 ms]
13.96/5.36	        (13) TRUE
13.96/5.36	    (14) QDP
13.96/5.36	        (15) DependencyGraphProof [EQUIVALENT, 0 ms]
13.96/5.36	        (16) QDP
13.96/5.36	        (17) QDPSizeChangeProof [EQUIVALENT, 1 ms]
13.96/5.36	        (18) YES
13.96/5.36	    (19) QDP
13.96/5.36	        (20) QDPSizeChangeProof [EQUIVALENT, 0 ms]
13.96/5.36	        (21) YES
13.96/5.36	    (22) QDP
13.96/5.36	        (23) QDPSizeChangeProof [EQUIVALENT, 0 ms]
13.96/5.36	        (24) YES
13.96/5.36	
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(0)
13.96/5.36	Obligation:
13.96/5.36	mainModule Main 
13.96/5.36	module Maybe where {
13.96/5.36	import qualified List;
13.96/5.36	import qualified Main;
13.96/5.36	import qualified Prelude;
13.96/5.36	}
13.96/5.36	module List where {
13.96/5.36	import qualified Main;
13.96/5.36	import qualified Maybe;
13.96/5.36	import qualified Prelude;
13.96/5.36	merge :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a]  ->  [a];
13.96/5.36	merge cmp xs [] = xs;
13.96/5.36	merge cmp [] ys = ys;
13.96/5.36	merge cmp (x : xs) (y : ys) = case x `cmp` y of { 
13.96/5.36	GT-> y : merge cmp (x : xs) ys; 
13.96/5.36	_-> x : merge cmp xs (y : ys); 
13.96/5.36	 } ;
13.96/5.36	
13.96/5.36	merge_pairs :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [[a]];
13.96/5.36	merge_pairs cmp [] = [];
13.96/5.36	merge_pairs cmp (xs : []) = xs : [];
13.96/5.36	merge_pairs cmp (xs : ys : xss) = merge cmp xs ys : merge_pairs cmp xss;
13.96/5.36	
13.96/5.36	mergesort :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
13.96/5.36	mergesort cmp = mergesort' cmp . map wrap;
13.96/5.36	
13.96/5.36	mergesort' :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [a];
13.96/5.36	mergesort' cmp [] = [];
13.96/5.36	mergesort' cmp (xs : []) = xs;
13.96/5.36	mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss);
13.96/5.36	
13.96/5.36	sortBy :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
13.96/5.36	sortBy cmp l = mergesort cmp l;
13.96/5.36	
13.96/5.36	wrap :: a  ->  [a];
13.96/5.36	wrap x = x : [];
13.96/5.36	
13.96/5.36	}
13.96/5.36	module Main where {
13.96/5.36	import qualified List;
13.96/5.36	import qualified Maybe;
13.96/5.36	import qualified Prelude;
13.96/5.36	}
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(1) CR (EQUIVALENT)
13.96/5.36	Case Reductions:
13.96/5.36	The following Case expression
13.96/5.36	"case cmp x y of {
13.96/5.36	GT  -> y : merge cmp (x : xs) ys;
13.96/5.36	_  -> x : merge cmp xs (y : ys)}
13.96/5.36	"
13.96/5.36	is transformed to
13.96/5.36	"merge0 y cmp x xs ys GT = y : merge cmp (x : xs) ys;
13.96/5.36	merge0 y cmp x xs ys _ = x : merge cmp xs (y : ys);
13.96/5.36	"
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(2)
13.96/5.36	Obligation:
13.96/5.36	mainModule Main 
13.96/5.36	module Maybe where {
13.96/5.36	import qualified List;
13.96/5.36	import qualified Main;
13.96/5.36	import qualified Prelude;
13.96/5.36	}
13.96/5.36	module List where {
13.96/5.36	import qualified Main;
13.96/5.36	import qualified Maybe;
13.96/5.36	import qualified Prelude;
13.96/5.36	merge :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a]  ->  [a];
13.96/5.36	merge cmp xs [] = xs;
13.96/5.36	merge cmp [] ys = ys;
13.96/5.36	merge cmp (x : xs) (y : ys) = merge0 y cmp x xs ys (x `cmp` y);
13.96/5.36	
13.96/5.36	merge0 y cmp x xs ys GT = y : merge cmp (x : xs) ys;
13.96/5.36	merge0 y cmp x xs ys _ = x : merge cmp xs (y : ys);
13.96/5.36	
13.96/5.36	merge_pairs :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [[a]];
13.96/5.36	merge_pairs cmp [] = [];
13.96/5.36	merge_pairs cmp (xs : []) = xs : [];
13.96/5.36	merge_pairs cmp (xs : ys : xss) = merge cmp xs ys : merge_pairs cmp xss;
13.96/5.36	
13.96/5.36	mergesort :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
13.96/5.36	mergesort cmp = mergesort' cmp . map wrap;
13.96/5.36	
13.96/5.36	mergesort' :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [a];
13.96/5.36	mergesort' cmp [] = [];
13.96/5.36	mergesort' cmp (xs : []) = xs;
13.96/5.36	mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss);
13.96/5.36	
13.96/5.36	sortBy :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
13.96/5.36	sortBy cmp l = mergesort cmp l;
13.96/5.36	
13.96/5.36	wrap :: a  ->  [a];
13.96/5.36	wrap x = x : [];
13.96/5.36	
13.96/5.36	}
13.96/5.36	module Main where {
13.96/5.36	import qualified List;
13.96/5.36	import qualified Maybe;
13.96/5.36	import qualified Prelude;
13.96/5.36	}
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(3) BR (EQUIVALENT)
13.96/5.36	Replaced joker patterns by fresh variables and removed binding patterns.
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(4)
13.96/5.36	Obligation:
13.96/5.36	mainModule Main 
13.96/5.36	module Maybe where {
13.96/5.36	import qualified List;
13.96/5.36	import qualified Main;
13.96/5.36	import qualified Prelude;
13.96/5.36	}
13.96/5.36	module List where {
13.96/5.36	import qualified Main;
13.96/5.36	import qualified Maybe;
13.96/5.36	import qualified Prelude;
13.96/5.36	merge :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a]  ->  [a];
13.96/5.36	merge cmp xs [] = xs;
13.96/5.36	merge cmp [] ys = ys;
13.96/5.36	merge cmp (x : xs) (y : ys) = merge0 y cmp x xs ys (x `cmp` y);
13.96/5.36	
13.96/5.36	merge0 y cmp x xs ys GT = y : merge cmp (x : xs) ys;
13.96/5.36	merge0 y cmp x xs ys vy = x : merge cmp xs (y : ys);
13.96/5.36	
13.96/5.36	merge_pairs :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [[a]];
13.96/5.36	merge_pairs cmp [] = [];
13.96/5.36	merge_pairs cmp (xs : []) = xs : [];
13.96/5.36	merge_pairs cmp (xs : ys : xss) = merge cmp xs ys : merge_pairs cmp xss;
13.96/5.36	
13.96/5.36	mergesort :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
13.96/5.36	mergesort cmp = mergesort' cmp . map wrap;
13.96/5.36	
13.96/5.36	mergesort' :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [a];
13.96/5.36	mergesort' cmp [] = [];
13.96/5.36	mergesort' cmp (xs : []) = xs;
13.96/5.36	mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss);
13.96/5.36	
13.96/5.36	sortBy :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
13.96/5.36	sortBy cmp l = mergesort cmp l;
13.96/5.36	
13.96/5.36	wrap :: a  ->  [a];
13.96/5.36	wrap x = x : [];
13.96/5.36	
13.96/5.36	}
13.96/5.36	module Main where {
13.96/5.36	import qualified List;
13.96/5.36	import qualified Maybe;
13.96/5.36	import qualified Prelude;
13.96/5.36	}
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(5) COR (EQUIVALENT)
13.96/5.36	Cond Reductions:
13.96/5.36	The following Function with conditions
13.96/5.36	"undefined |Falseundefined;
13.96/5.36	"
13.96/5.36	is transformed to
13.96/5.36	"undefined  = undefined1;
13.96/5.36	"
13.96/5.36	"undefined0 True = undefined;
13.96/5.36	"
13.96/5.36	"undefined1  = undefined0 False;
13.96/5.36	"
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(6)
13.96/5.36	Obligation:
13.96/5.36	mainModule Main 
13.96/5.36	module Maybe where {
13.96/5.36	import qualified List;
13.96/5.36	import qualified Main;
13.96/5.36	import qualified Prelude;
13.96/5.36	}
13.96/5.36	module List where {
13.96/5.36	import qualified Main;
13.96/5.36	import qualified Maybe;
13.96/5.36	import qualified Prelude;
13.96/5.36	merge :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a]  ->  [a];
13.96/5.36	merge cmp xs [] = xs;
13.96/5.36	merge cmp [] ys = ys;
13.96/5.36	merge cmp (x : xs) (y : ys) = merge0 y cmp x xs ys (x `cmp` y);
13.96/5.36	
13.96/5.36	merge0 y cmp x xs ys GT = y : merge cmp (x : xs) ys;
13.96/5.36	merge0 y cmp x xs ys vy = x : merge cmp xs (y : ys);
13.96/5.36	
13.96/5.36	merge_pairs :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [[a]];
13.96/5.36	merge_pairs cmp [] = [];
13.96/5.36	merge_pairs cmp (xs : []) = xs : [];
13.96/5.36	merge_pairs cmp (xs : ys : xss) = merge cmp xs ys : merge_pairs cmp xss;
13.96/5.36	
13.96/5.36	mergesort :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
13.96/5.36	mergesort cmp = mergesort' cmp . map wrap;
13.96/5.36	
13.96/5.36	mergesort' :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [a];
13.96/5.36	mergesort' cmp [] = [];
13.96/5.36	mergesort' cmp (xs : []) = xs;
13.96/5.36	mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss);
13.96/5.36	
13.96/5.36	sortBy :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
13.96/5.36	sortBy cmp l = mergesort cmp l;
13.96/5.36	
13.96/5.36	wrap :: a  ->  [a];
13.96/5.36	wrap x = x : [];
13.96/5.36	
13.96/5.36	}
13.96/5.36	module Main where {
13.96/5.36	import qualified List;
13.96/5.36	import qualified Maybe;
13.96/5.36	import qualified Prelude;
13.96/5.36	}
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(7) Narrow (SOUND)
13.96/5.36	Haskell To QDPs
13.96/5.36	
13.96/5.36	digraph dp_graph {
13.96/5.36	node [outthreshold=100, inthreshold=100];1[label="List.sortBy",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
13.96/5.36	3[label="List.sortBy vz3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3];
13.96/5.36	4[label="List.sortBy vz3 vz4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3];
13.96/5.36	5[label="List.mergesort vz3 vz4",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3];
13.96/5.36	6[label="(List.mergesort' vz3) . map List.wrap",fontsize=16,color="black",shape="box"];6 -> 7[label="",style="solid", color="black", weight=3];
13.96/5.36	7[label="List.mergesort' vz3 (map List.wrap vz4)",fontsize=16,color="burlywood",shape="box"];572[label="vz4/vz40 : vz41",fontsize=10,color="white",style="solid",shape="box"];7 -> 572[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	572 -> 8[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	573[label="vz4/[]",fontsize=10,color="white",style="solid",shape="box"];7 -> 573[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	573 -> 9[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	8[label="List.mergesort' vz3 (map List.wrap (vz40 : vz41))",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3];
13.96/5.36	9[label="List.mergesort' vz3 (map List.wrap [])",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3];
13.96/5.36	10[label="List.mergesort' vz3 (List.wrap vz40 : map List.wrap vz41)",fontsize=16,color="burlywood",shape="box"];574[label="vz41/vz410 : vz411",fontsize=10,color="white",style="solid",shape="box"];10 -> 574[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	574 -> 12[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	575[label="vz41/[]",fontsize=10,color="white",style="solid",shape="box"];10 -> 575[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	575 -> 13[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	11[label="List.mergesort' vz3 []",fontsize=16,color="black",shape="box"];11 -> 14[label="",style="solid", color="black", weight=3];
13.96/5.36	12[label="List.mergesort' vz3 (List.wrap vz40 : map List.wrap (vz410 : vz411))",fontsize=16,color="black",shape="box"];12 -> 15[label="",style="solid", color="black", weight=3];
13.96/5.36	13[label="List.mergesort' vz3 (List.wrap vz40 : map List.wrap [])",fontsize=16,color="black",shape="box"];13 -> 16[label="",style="solid", color="black", weight=3];
13.96/5.36	14[label="[]",fontsize=16,color="green",shape="box"];15[label="List.mergesort' vz3 (List.wrap vz40 : List.wrap vz410 : map List.wrap vz411)",fontsize=16,color="black",shape="box"];15 -> 17[label="",style="solid", color="black", weight=3];
13.96/5.36	16[label="List.mergesort' vz3 (List.wrap vz40 : [])",fontsize=16,color="black",shape="box"];16 -> 18[label="",style="solid", color="black", weight=3];
13.96/5.36	17[label="List.mergesort' vz3 (List.merge_pairs vz3 (List.wrap vz40 : List.wrap vz410 : map List.wrap vz411))",fontsize=16,color="black",shape="box"];17 -> 19[label="",style="solid", color="black", weight=3];
13.96/5.36	18[label="List.wrap vz40",fontsize=16,color="black",shape="triangle"];18 -> 20[label="",style="solid", color="black", weight=3];
13.96/5.36	19 -> 260[label="",style="dashed", color="red", weight=0];
13.96/5.36	19[label="List.mergesort' vz3 (List.merge vz3 (List.wrap vz40) (List.wrap vz410) : List.merge_pairs vz3 (map List.wrap vz411))",fontsize=16,color="magenta"];19 -> 261[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	19 -> 262[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	19 -> 263[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	20[label="vz40 : []",fontsize=16,color="green",shape="box"];261[label="vz3",fontsize=16,color="green",shape="box"];262 -> 492[label="",style="dashed", color="red", weight=0];
13.96/5.36	262[label="List.merge vz3 (List.wrap vz40) (List.wrap vz410)",fontsize=16,color="magenta"];262 -> 493[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	262 -> 494[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	263[label="map List.wrap vz411",fontsize=16,color="burlywood",shape="triangle"];576[label="vz411/vz4110 : vz4111",fontsize=10,color="white",style="solid",shape="box"];263 -> 576[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	576 -> 495[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	577[label="vz411/[]",fontsize=10,color="white",style="solid",shape="box"];263 -> 577[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	577 -> 496[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	260[label="List.mergesort' vz36 (vz37 : List.merge_pairs vz36 vz38)",fontsize=16,color="burlywood",shape="triangle"];578[label="vz38/vz380 : vz381",fontsize=10,color="white",style="solid",shape="box"];260 -> 578[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	578 -> 497[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	579[label="vz38/[]",fontsize=10,color="white",style="solid",shape="box"];260 -> 579[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	579 -> 498[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	493 -> 18[label="",style="dashed", color="red", weight=0];
13.96/5.36	493[label="List.wrap vz40",fontsize=16,color="magenta"];494 -> 18[label="",style="dashed", color="red", weight=0];
13.96/5.36	494[label="List.wrap vz410",fontsize=16,color="magenta"];494 -> 499[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	492[label="List.merge vz3 vz40 vz39",fontsize=16,color="burlywood",shape="triangle"];580[label="vz39/vz390 : vz391",fontsize=10,color="white",style="solid",shape="box"];492 -> 580[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	580 -> 500[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	581[label="vz39/[]",fontsize=10,color="white",style="solid",shape="box"];492 -> 581[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	581 -> 501[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	495[label="map List.wrap (vz4110 : vz4111)",fontsize=16,color="black",shape="box"];495 -> 502[label="",style="solid", color="black", weight=3];
13.96/5.36	496[label="map List.wrap []",fontsize=16,color="black",shape="box"];496 -> 503[label="",style="solid", color="black", weight=3];
13.96/5.36	497[label="List.mergesort' vz36 (vz37 : List.merge_pairs vz36 (vz380 : vz381))",fontsize=16,color="burlywood",shape="box"];582[label="vz381/vz3810 : vz3811",fontsize=10,color="white",style="solid",shape="box"];497 -> 582[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	582 -> 504[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	583[label="vz381/[]",fontsize=10,color="white",style="solid",shape="box"];497 -> 583[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	583 -> 505[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	498[label="List.mergesort' vz36 (vz37 : List.merge_pairs vz36 [])",fontsize=16,color="black",shape="box"];498 -> 506[label="",style="solid", color="black", weight=3];
13.96/5.36	499[label="vz410",fontsize=16,color="green",shape="box"];500[label="List.merge vz3 vz40 (vz390 : vz391)",fontsize=16,color="burlywood",shape="box"];584[label="vz40/vz400 : vz401",fontsize=10,color="white",style="solid",shape="box"];500 -> 584[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	584 -> 507[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	585[label="vz40/[]",fontsize=10,color="white",style="solid",shape="box"];500 -> 585[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	585 -> 508[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	501[label="List.merge vz3 vz40 []",fontsize=16,color="black",shape="box"];501 -> 509[label="",style="solid", color="black", weight=3];
13.96/5.36	502[label="List.wrap vz4110 : map List.wrap vz4111",fontsize=16,color="green",shape="box"];502 -> 510[label="",style="dashed", color="green", weight=3];
13.96/5.36	502 -> 511[label="",style="dashed", color="green", weight=3];
13.96/5.36	503[label="[]",fontsize=16,color="green",shape="box"];504[label="List.mergesort' vz36 (vz37 : List.merge_pairs vz36 (vz380 : vz3810 : vz3811))",fontsize=16,color="black",shape="box"];504 -> 512[label="",style="solid", color="black", weight=3];
13.96/5.36	505[label="List.mergesort' vz36 (vz37 : List.merge_pairs vz36 (vz380 : []))",fontsize=16,color="black",shape="box"];505 -> 513[label="",style="solid", color="black", weight=3];
13.96/5.36	506[label="List.mergesort' vz36 (vz37 : [])",fontsize=16,color="black",shape="box"];506 -> 514[label="",style="solid", color="black", weight=3];
13.96/5.36	507[label="List.merge vz3 (vz400 : vz401) (vz390 : vz391)",fontsize=16,color="black",shape="box"];507 -> 515[label="",style="solid", color="black", weight=3];
13.96/5.36	508[label="List.merge vz3 [] (vz390 : vz391)",fontsize=16,color="black",shape="box"];508 -> 516[label="",style="solid", color="black", weight=3];
13.96/5.36	509[label="vz40",fontsize=16,color="green",shape="box"];510 -> 18[label="",style="dashed", color="red", weight=0];
13.96/5.36	510[label="List.wrap vz4110",fontsize=16,color="magenta"];510 -> 517[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	511 -> 263[label="",style="dashed", color="red", weight=0];
13.96/5.36	511[label="map List.wrap vz4111",fontsize=16,color="magenta"];511 -> 518[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	512 -> 519[label="",style="dashed", color="red", weight=0];
13.96/5.36	512[label="List.mergesort' vz36 (vz37 : List.merge vz36 vz380 vz3810 : List.merge_pairs vz36 vz3811)",fontsize=16,color="magenta"];512 -> 520[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	513[label="List.mergesort' vz36 (vz37 : vz380 : [])",fontsize=16,color="black",shape="box"];513 -> 521[label="",style="solid", color="black", weight=3];
13.96/5.36	514[label="vz37",fontsize=16,color="green",shape="box"];515 -> 522[label="",style="dashed", color="red", weight=0];
13.96/5.36	515[label="List.merge0 vz390 vz3 vz400 vz401 vz391 (vz3 vz400 vz390)",fontsize=16,color="magenta"];515 -> 523[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	516[label="vz390 : vz391",fontsize=16,color="green",shape="box"];517[label="vz4110",fontsize=16,color="green",shape="box"];518[label="vz4111",fontsize=16,color="green",shape="box"];520 -> 492[label="",style="dashed", color="red", weight=0];
13.96/5.36	520[label="List.merge vz36 vz380 vz3810",fontsize=16,color="magenta"];520 -> 524[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	520 -> 525[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	520 -> 526[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	519[label="List.mergesort' vz36 (vz37 : vz41 : List.merge_pairs vz36 vz3811)",fontsize=16,color="black",shape="triangle"];519 -> 527[label="",style="solid", color="black", weight=3];
13.96/5.36	521[label="List.mergesort' vz36 (List.merge_pairs vz36 (vz37 : vz380 : []))",fontsize=16,color="black",shape="box"];521 -> 528[label="",style="solid", color="black", weight=3];
13.96/5.36	523[label="vz3 vz400 vz390",fontsize=16,color="green",shape="box"];523 -> 534[label="",style="dashed", color="green", weight=3];
13.96/5.36	523 -> 535[label="",style="dashed", color="green", weight=3];
13.96/5.36	522[label="List.merge0 vz390 vz3 vz400 vz401 vz391 vz42",fontsize=16,color="burlywood",shape="triangle"];586[label="vz42/LT",fontsize=10,color="white",style="solid",shape="box"];522 -> 586[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	586 -> 531[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	587[label="vz42/EQ",fontsize=10,color="white",style="solid",shape="box"];522 -> 587[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	587 -> 532[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	588[label="vz42/GT",fontsize=10,color="white",style="solid",shape="box"];522 -> 588[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	588 -> 533[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	524[label="vz380",fontsize=16,color="green",shape="box"];525[label="vz36",fontsize=16,color="green",shape="box"];526[label="vz3810",fontsize=16,color="green",shape="box"];527[label="List.mergesort' vz36 (List.merge_pairs vz36 (vz37 : vz41 : List.merge_pairs vz36 vz3811))",fontsize=16,color="black",shape="box"];527 -> 536[label="",style="solid", color="black", weight=3];
13.96/5.36	528 -> 260[label="",style="dashed", color="red", weight=0];
13.96/5.36	528[label="List.mergesort' vz36 (List.merge vz36 vz37 vz380 : List.merge_pairs vz36 [])",fontsize=16,color="magenta"];528 -> 537[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	528 -> 538[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	534[label="vz400",fontsize=16,color="green",shape="box"];535[label="vz390",fontsize=16,color="green",shape="box"];531[label="List.merge0 vz390 vz3 vz400 vz401 vz391 LT",fontsize=16,color="black",shape="box"];531 -> 539[label="",style="solid", color="black", weight=3];
13.96/5.36	532[label="List.merge0 vz390 vz3 vz400 vz401 vz391 EQ",fontsize=16,color="black",shape="box"];532 -> 540[label="",style="solid", color="black", weight=3];
13.96/5.36	533[label="List.merge0 vz390 vz3 vz400 vz401 vz391 GT",fontsize=16,color="black",shape="box"];533 -> 541[label="",style="solid", color="black", weight=3];
13.96/5.36	536 -> 260[label="",style="dashed", color="red", weight=0];
13.96/5.36	536[label="List.mergesort' vz36 (List.merge vz36 vz37 vz41 : List.merge_pairs vz36 (List.merge_pairs vz36 vz3811))",fontsize=16,color="magenta"];536 -> 542[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	536 -> 543[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	537 -> 492[label="",style="dashed", color="red", weight=0];
13.96/5.36	537[label="List.merge vz36 vz37 vz380",fontsize=16,color="magenta"];537 -> 544[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	537 -> 545[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	537 -> 546[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	538[label="[]",fontsize=16,color="green",shape="box"];539[label="vz400 : List.merge vz3 vz401 (vz390 : vz391)",fontsize=16,color="green",shape="box"];539 -> 547[label="",style="dashed", color="green", weight=3];
13.96/5.36	540[label="vz400 : List.merge vz3 vz401 (vz390 : vz391)",fontsize=16,color="green",shape="box"];540 -> 548[label="",style="dashed", color="green", weight=3];
13.96/5.36	541[label="vz390 : List.merge vz3 (vz400 : vz401) vz391",fontsize=16,color="green",shape="box"];541 -> 549[label="",style="dashed", color="green", weight=3];
13.96/5.36	542 -> 492[label="",style="dashed", color="red", weight=0];
13.96/5.36	542[label="List.merge vz36 vz37 vz41",fontsize=16,color="magenta"];542 -> 550[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	542 -> 551[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	542 -> 552[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	543[label="List.merge_pairs vz36 vz3811",fontsize=16,color="burlywood",shape="triangle"];589[label="vz3811/vz38110 : vz38111",fontsize=10,color="white",style="solid",shape="box"];543 -> 589[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	589 -> 553[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	590[label="vz3811/[]",fontsize=10,color="white",style="solid",shape="box"];543 -> 590[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	590 -> 554[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	544[label="vz37",fontsize=16,color="green",shape="box"];545[label="vz36",fontsize=16,color="green",shape="box"];546[label="vz380",fontsize=16,color="green",shape="box"];547 -> 492[label="",style="dashed", color="red", weight=0];
13.96/5.36	547[label="List.merge vz3 vz401 (vz390 : vz391)",fontsize=16,color="magenta"];547 -> 555[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	547 -> 556[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	548 -> 492[label="",style="dashed", color="red", weight=0];
13.96/5.36	548[label="List.merge vz3 vz401 (vz390 : vz391)",fontsize=16,color="magenta"];548 -> 557[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	548 -> 558[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	549 -> 492[label="",style="dashed", color="red", weight=0];
13.96/5.36	549[label="List.merge vz3 (vz400 : vz401) vz391",fontsize=16,color="magenta"];549 -> 559[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	549 -> 560[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	550[label="vz37",fontsize=16,color="green",shape="box"];551[label="vz36",fontsize=16,color="green",shape="box"];552[label="vz41",fontsize=16,color="green",shape="box"];553[label="List.merge_pairs vz36 (vz38110 : vz38111)",fontsize=16,color="burlywood",shape="box"];591[label="vz38111/vz381110 : vz381111",fontsize=10,color="white",style="solid",shape="box"];553 -> 591[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	591 -> 561[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	592[label="vz38111/[]",fontsize=10,color="white",style="solid",shape="box"];553 -> 592[label="",style="solid", color="burlywood", weight=9];
13.96/5.36	592 -> 562[label="",style="solid", color="burlywood", weight=3];
13.96/5.36	554[label="List.merge_pairs vz36 []",fontsize=16,color="black",shape="box"];554 -> 563[label="",style="solid", color="black", weight=3];
13.96/5.36	555[label="vz401",fontsize=16,color="green",shape="box"];556[label="vz390 : vz391",fontsize=16,color="green",shape="box"];557[label="vz401",fontsize=16,color="green",shape="box"];558[label="vz390 : vz391",fontsize=16,color="green",shape="box"];559[label="vz400 : vz401",fontsize=16,color="green",shape="box"];560[label="vz391",fontsize=16,color="green",shape="box"];561[label="List.merge_pairs vz36 (vz38110 : vz381110 : vz381111)",fontsize=16,color="black",shape="box"];561 -> 564[label="",style="solid", color="black", weight=3];
13.96/5.36	562[label="List.merge_pairs vz36 (vz38110 : [])",fontsize=16,color="black",shape="box"];562 -> 565[label="",style="solid", color="black", weight=3];
13.96/5.36	563[label="[]",fontsize=16,color="green",shape="box"];564[label="List.merge vz36 vz38110 vz381110 : List.merge_pairs vz36 vz381111",fontsize=16,color="green",shape="box"];564 -> 566[label="",style="dashed", color="green", weight=3];
13.96/5.36	564 -> 567[label="",style="dashed", color="green", weight=3];
13.96/5.36	565[label="vz38110 : []",fontsize=16,color="green",shape="box"];566 -> 492[label="",style="dashed", color="red", weight=0];
13.96/5.36	566[label="List.merge vz36 vz38110 vz381110",fontsize=16,color="magenta"];566 -> 568[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	566 -> 569[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	566 -> 570[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	567 -> 543[label="",style="dashed", color="red", weight=0];
13.96/5.36	567[label="List.merge_pairs vz36 vz381111",fontsize=16,color="magenta"];567 -> 571[label="",style="dashed", color="magenta", weight=3];
13.96/5.36	568[label="vz38110",fontsize=16,color="green",shape="box"];569[label="vz36",fontsize=16,color="green",shape="box"];570[label="vz381110",fontsize=16,color="green",shape="box"];571[label="vz381111",fontsize=16,color="green",shape="box"];}
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(8)
13.96/5.36	Complex Obligation (AND)
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(9)
13.96/5.36	Obligation:
13.96/5.36	Q DP problem:
13.96/5.36	The TRS P consists of the following rules:
13.96/5.36	
13.96/5.36	   new_merge0(vz390, vz3, vz400, vz401, vz391, ba) -> new_merge(vz3, :(vz400, vz401), vz391, ba)
13.96/5.36	   new_merge0(vz390, vz3, vz400, vz401, vz391, ba) -> new_merge(vz3, vz401, :(vz390, vz391), ba)
13.96/5.36	   new_merge(vz3, :(vz400, vz401), :(vz390, vz391), ba) -> new_merge0(vz390, vz3, vz400, vz401, vz391, ba)
13.96/5.36	
13.96/5.36	R is empty.
13.96/5.36	Q is empty.
13.96/5.36	We have to consider all minimal (P,Q,R)-chains.
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(10) MRRProof (EQUIVALENT)
13.96/5.36	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.
13.96/5.36	
13.96/5.36	Strictly oriented dependency pairs:
13.96/5.36	
13.96/5.36	   new_merge0(vz390, vz3, vz400, vz401, vz391, ba) -> new_merge(vz3, :(vz400, vz401), vz391, ba)
13.96/5.36	   new_merge(vz3, :(vz400, vz401), :(vz390, vz391), ba) -> new_merge0(vz390, vz3, vz400, vz401, vz391, ba)
13.96/5.36	
13.96/5.36	
13.96/5.36	Used ordering: Polynomial interpretation [POLO]:
13.96/5.36	
13.96/5.36	   POL(:(x_1, x_2)) = 1 + x_1 + x_2
13.96/5.36	   POL(new_merge(x_1, x_2, x_3, x_4)) = x_1 + x_2 + 2*x_3 + x_4
13.96/5.36	   POL(new_merge0(x_1, x_2, x_3, x_4, x_5, x_6)) = 2 + 2*x_1 + x_2 + x_3 + x_4 + 2*x_5 + x_6
13.96/5.36	
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(11)
13.96/5.36	Obligation:
13.96/5.36	Q DP problem:
13.96/5.36	The TRS P consists of the following rules:
13.96/5.36	
13.96/5.36	   new_merge0(vz390, vz3, vz400, vz401, vz391, ba) -> new_merge(vz3, vz401, :(vz390, vz391), ba)
13.96/5.36	
13.96/5.36	R is empty.
13.96/5.36	Q is empty.
13.96/5.36	We have to consider all minimal (P,Q,R)-chains.
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(12) DependencyGraphProof (EQUIVALENT)
13.96/5.36	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(13)
13.96/5.36	TRUE
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(14)
13.96/5.36	Obligation:
13.96/5.36	Q DP problem:
13.96/5.36	The TRS P consists of the following rules:
13.96/5.36	
13.96/5.36	   new_mergesort'0(vz36, vz37, :(vz380, :(vz3810, vz3811)), ba) -> new_mergesort'(vz36, vz37, new_merge1(vz36, vz380, vz3810, ba), vz3811, ba)
13.96/5.36	   new_mergesort'0(vz36, vz37, :(vz380, []), ba) -> new_mergesort'0(vz36, new_merge1(vz36, vz37, vz380, ba), [], ba)
13.96/5.36	   new_mergesort'(vz36, vz37, vz41, vz3811, ba) -> new_mergesort'0(vz36, new_merge1(vz36, vz37, vz41, ba), new_merge_pairs0(vz36, vz3811, ba), ba)
13.96/5.36	
13.96/5.36	The TRS R consists of the following rules:
13.96/5.36	
13.96/5.36	   new_merge_pairs0(vz36, :(vz38110, []), ba) -> :(vz38110, [])
13.96/5.36	   new_merge_pairs0(vz36, [], ba) -> []
13.96/5.36	   new_merge_pairs0(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> :(new_merge1(vz36, vz38110, vz381110, ba), new_merge_pairs0(vz36, vz381111, ba))
13.96/5.36	
13.96/5.36	The set Q consists of the following terms:
13.96/5.36	
13.96/5.36	   new_merge_pairs0(x0, :(x1, []), x2)
13.96/5.36	   new_merge_pairs0(x0, :(x1, :(x2, x3)), x4)
13.96/5.36	   new_merge_pairs0(x0, [], x1)
13.96/5.36	
13.96/5.36	We have to consider all minimal (P,Q,R)-chains.
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(15) DependencyGraphProof (EQUIVALENT)
13.96/5.36	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(16)
13.96/5.36	Obligation:
13.96/5.36	Q DP problem:
13.96/5.36	The TRS P consists of the following rules:
13.96/5.36	
13.96/5.36	   new_mergesort'(vz36, vz37, vz41, vz3811, ba) -> new_mergesort'0(vz36, new_merge1(vz36, vz37, vz41, ba), new_merge_pairs0(vz36, vz3811, ba), ba)
13.96/5.36	   new_mergesort'0(vz36, vz37, :(vz380, :(vz3810, vz3811)), ba) -> new_mergesort'(vz36, vz37, new_merge1(vz36, vz380, vz3810, ba), vz3811, ba)
13.96/5.36	
13.96/5.36	The TRS R consists of the following rules:
13.96/5.36	
13.96/5.36	   new_merge_pairs0(vz36, :(vz38110, []), ba) -> :(vz38110, [])
13.96/5.36	   new_merge_pairs0(vz36, [], ba) -> []
13.96/5.36	   new_merge_pairs0(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> :(new_merge1(vz36, vz38110, vz381110, ba), new_merge_pairs0(vz36, vz381111, ba))
13.96/5.36	
13.96/5.36	The set Q consists of the following terms:
13.96/5.36	
13.96/5.36	   new_merge_pairs0(x0, :(x1, []), x2)
13.96/5.36	   new_merge_pairs0(x0, :(x1, :(x2, x3)), x4)
13.96/5.36	   new_merge_pairs0(x0, [], x1)
13.96/5.36	
13.96/5.36	We have to consider all minimal (P,Q,R)-chains.
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(17) QDPSizeChangeProof (EQUIVALENT)
13.96/5.36	We used the following order together with the size-change analysis [AAECC05] to show that there are no infinite chains for this DP problem. 
13.96/5.36	
13.96/5.36	Order:Polynomial interpretation [POLO]:
13.96/5.36	
13.96/5.36	   POL(:(x_1, x_2)) = 1 + x_2
13.96/5.36	   POL([]) = 0
13.96/5.36	   POL(new_merge1(x_1, x_2, x_3, x_4)) = 1
13.96/5.36	   POL(new_merge_pairs0(x_1, x_2, x_3)) = x_2
13.96/5.36	
13.96/5.36	
13.96/5.36	
13.96/5.36	
13.96/5.36	From the DPs we obtained the following set of size-change graphs:
13.96/5.36	*new_mergesort'0(vz36, vz37, :(vz380, :(vz3810, vz3811)), ba) -> new_mergesort'(vz36, vz37, new_merge1(vz36, vz380, vz3810, ba), vz3811, ba) (allowed arguments on rhs = {1, 2, 3, 4, 5})
13.96/5.36	The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 4, 4 >= 5
13.96/5.36	
13.96/5.36	
13.96/5.36	*new_mergesort'(vz36, vz37, vz41, vz3811, ba) -> new_mergesort'0(vz36, new_merge1(vz36, vz37, vz41, ba), new_merge_pairs0(vz36, vz3811, ba), ba) (allowed arguments on rhs = {1, 2, 3, 4})
13.96/5.36	The graph contains the following edges 1 >= 1, 4 >= 3, 5 >= 4
13.96/5.36	
13.96/5.36	
13.96/5.36	
13.96/5.36	We oriented the following set of usable rules [AAECC05,FROCOS05].
13.96/5.36	
13.96/5.36	   new_merge_pairs0(vz36, [], ba) -> []
13.96/5.36	   new_merge_pairs0(vz36, :(vz38110, []), ba) -> :(vz38110, [])
13.96/5.36	   new_merge_pairs0(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> :(new_merge1(vz36, vz38110, vz381110, ba), new_merge_pairs0(vz36, vz381111, ba))
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(18)
13.96/5.36	YES
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(19)
13.96/5.36	Obligation:
13.96/5.36	Q DP problem:
13.96/5.36	The TRS P consists of the following rules:
13.96/5.36	
13.96/5.36	   new_map(:(vz4110, vz4111), ba) -> new_map(vz4111, ba)
13.96/5.36	
13.96/5.36	R is empty.
13.96/5.36	Q is empty.
13.96/5.36	We have to consider all minimal (P,Q,R)-chains.
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(20) QDPSizeChangeProof (EQUIVALENT)
13.96/5.36	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. 
13.96/5.36	
13.96/5.36	From the DPs we obtained the following set of size-change graphs:
13.96/5.36	*new_map(:(vz4110, vz4111), ba) -> new_map(vz4111, ba)
13.96/5.36	The graph contains the following edges 1 > 1, 2 >= 2
13.96/5.36	
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(21)
13.96/5.36	YES
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(22)
13.96/5.36	Obligation:
13.96/5.36	Q DP problem:
13.96/5.36	The TRS P consists of the following rules:
13.96/5.36	
13.96/5.36	   new_merge_pairs(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> new_merge_pairs(vz36, vz381111, ba)
13.96/5.36	
13.96/5.36	R is empty.
13.96/5.36	Q is empty.
13.96/5.36	We have to consider all minimal (P,Q,R)-chains.
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(23) QDPSizeChangeProof (EQUIVALENT)
13.96/5.36	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. 
13.96/5.36	
13.96/5.36	From the DPs we obtained the following set of size-change graphs:
13.96/5.36	*new_merge_pairs(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> new_merge_pairs(vz36, vz381111, ba)
13.96/5.36	The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3
13.96/5.36	
13.96/5.36	
13.96/5.36	----------------------------------------
13.96/5.36	
13.96/5.36	(24)
13.96/5.36	YES
14.16/8.10	EOF