/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.hs /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


H-Termination with start terms of the given HASKELL could be proven:

(0) HASKELL
(1) CR [EQUIVALENT, 0 ms]
(2) HASKELL
(3) BR [EQUIVALENT, 0 ms]
(4) HASKELL
(5) COR [EQUIVALENT, 22 ms]
(6) HASKELL
(7) Narrow [SOUND, 0 ms]
(8) AND
    (9) QDP
        (10) MRRProof [EQUIVALENT, 13 ms]
        (11) QDP
        (12) DependencyGraphProof [EQUIVALENT, 0 ms]
        (13) TRUE
    (14) QDP
        (15) DependencyGraphProof [EQUIVALENT, 0 ms]
        (16) QDP
        (17) QDPSizeChangeProof [EQUIVALENT, 54 ms]
        (18) YES
    (19) QDP
        (20) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (21) YES
    (22) QDP
        (23) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (24) YES


----------------------------------------

(0)
Obligation:
mainModule Main 
module Maybe where {
import qualified List;
import qualified Main;
import qualified Prelude;
}
module List where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
merge :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a]  ->  [a];
merge cmp xs [] = xs;
merge cmp [] ys = ys;
merge cmp (x : xs) (y : ys) = case x `cmp` y of { 
GT-> y : merge cmp (x : xs) ys; 
_-> x : merge cmp xs (y : ys); 
 } ;

merge_pairs :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [[a]];
merge_pairs cmp [] = [];
merge_pairs cmp (xs : []) = xs : [];
merge_pairs cmp (xs : ys : xss) = merge cmp xs ys : merge_pairs cmp xss;

mergesort :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
mergesort cmp = mergesort' cmp . map wrap;

mergesort' :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [a];
mergesort' cmp [] = [];
mergesort' cmp (xs : []) = xs;
mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss);

sortBy :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
sortBy cmp l = mergesort cmp l;

wrap :: a  ->  [a];
wrap x = x : [];

}
module Main where {
import qualified List;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(1) CR (EQUIVALENT)
Case Reductions:
The following Case expression
"case cmp x y of {
GT  -> y : merge cmp (x : xs) ys;
_  -> x : merge cmp xs (y : ys)}
"
is transformed to
"merge0 y cmp x xs ys GT = y : merge cmp (x : xs) ys;
merge0 y cmp x xs ys _ = x : merge cmp xs (y : ys);
"

----------------------------------------

(2)
Obligation:
mainModule Main 
module Maybe where {
import qualified List;
import qualified Main;
import qualified Prelude;
}
module List where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
merge :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a]  ->  [a];
merge cmp xs [] = xs;
merge cmp [] ys = ys;
merge cmp (x : xs) (y : ys) = merge0 y cmp x xs ys (x `cmp` y);

merge0 y cmp x xs ys GT = y : merge cmp (x : xs) ys;
merge0 y cmp x xs ys _ = x : merge cmp xs (y : ys);

merge_pairs :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [[a]];
merge_pairs cmp [] = [];
merge_pairs cmp (xs : []) = xs : [];
merge_pairs cmp (xs : ys : xss) = merge cmp xs ys : merge_pairs cmp xss;

mergesort :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
mergesort cmp = mergesort' cmp . map wrap;

mergesort' :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [a];
mergesort' cmp [] = [];
mergesort' cmp (xs : []) = xs;
mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss);

sortBy :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
sortBy cmp l = mergesort cmp l;

wrap :: a  ->  [a];
wrap x = x : [];

}
module Main where {
import qualified List;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(3) BR (EQUIVALENT)
Replaced joker patterns by fresh variables and removed binding patterns.
----------------------------------------

(4)
Obligation:
mainModule Main 
module Maybe where {
import qualified List;
import qualified Main;
import qualified Prelude;
}
module List where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
merge :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a]  ->  [a];
merge cmp xs [] = xs;
merge cmp [] ys = ys;
merge cmp (x : xs) (y : ys) = merge0 y cmp x xs ys (x `cmp` y);

merge0 y cmp x xs ys GT = y : merge cmp (x : xs) ys;
merge0 y cmp x xs ys vy = x : merge cmp xs (y : ys);

merge_pairs :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [[a]];
merge_pairs cmp [] = [];
merge_pairs cmp (xs : []) = xs : [];
merge_pairs cmp (xs : ys : xss) = merge cmp xs ys : merge_pairs cmp xss;

mergesort :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
mergesort cmp = mergesort' cmp . map wrap;

mergesort' :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [a];
mergesort' cmp [] = [];
mergesort' cmp (xs : []) = xs;
mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss);

sortBy :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
sortBy cmp l = mergesort cmp l;

wrap :: a  ->  [a];
wrap x = x : [];

}
module Main where {
import qualified List;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(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 List;
import qualified Main;
import qualified Prelude;
}
module List where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
merge :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a]  ->  [a];
merge cmp xs [] = xs;
merge cmp [] ys = ys;
merge cmp (x : xs) (y : ys) = merge0 y cmp x xs ys (x `cmp` y);

merge0 y cmp x xs ys GT = y : merge cmp (x : xs) ys;
merge0 y cmp x xs ys vy = x : merge cmp xs (y : ys);

merge_pairs :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [[a]];
merge_pairs cmp [] = [];
merge_pairs cmp (xs : []) = xs : [];
merge_pairs cmp (xs : ys : xss) = merge cmp xs ys : merge_pairs cmp xss;

mergesort :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
mergesort cmp = mergesort' cmp . map wrap;

mergesort' :: (a  ->  a  ->  Ordering)  ->  [[a]]  ->  [a];
mergesort' cmp [] = [];
mergesort' cmp (xs : []) = xs;
mergesort' cmp xss = mergesort' cmp (merge_pairs cmp xss);

sortBy :: (a  ->  a  ->  Ordering)  ->  [a]  ->  [a];
sortBy cmp l = mergesort cmp l;

wrap :: a  ->  [a];
wrap x = x : [];

}
module Main where {
import qualified List;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(7) Narrow (SOUND)
Haskell To QDPs

digraph dp_graph {
node [outthreshold=100, inthreshold=100];1[label="List.sortBy",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
3[label="List.sortBy vz3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3];
4[label="List.sortBy vz3 vz4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3];
5[label="List.mergesort vz3 vz4",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3];
6[label="(List.mergesort' vz3) . map List.wrap",fontsize=16,color="black",shape="box"];6 -> 7[label="",style="solid", color="black", weight=3];
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];
572 -> 8[label="",style="solid", color="burlywood", weight=3];
573[label="vz4/[]",fontsize=10,color="white",style="solid",shape="box"];7 -> 573[label="",style="solid", color="burlywood", weight=9];
573 -> 9[label="",style="solid", color="burlywood", weight=3];
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];
9[label="List.mergesort' vz3 (map List.wrap [])",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3];
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];
574 -> 12[label="",style="solid", color="burlywood", weight=3];
575[label="vz41/[]",fontsize=10,color="white",style="solid",shape="box"];10 -> 575[label="",style="solid", color="burlywood", weight=9];
575 -> 13[label="",style="solid", color="burlywood", weight=3];
11[label="List.mergesort' vz3 []",fontsize=16,color="black",shape="box"];11 -> 14[label="",style="solid", color="black", weight=3];
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[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];
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];
16[label="List.mergesort' vz3 (List.wrap vz40 : [])",fontsize=16,color="black",shape="box"];16 -> 18[label="",style="solid", color="black", weight=3];
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];
18[label="List.wrap vz40",fontsize=16,color="black",shape="triangle"];18 -> 20[label="",style="solid", color="black", weight=3];
19 -> 260[label="",style="dashed", color="red", weight=0];
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];
19 -> 262[label="",style="dashed", color="magenta", weight=3];
19 -> 263[label="",style="dashed", color="magenta", weight=3];
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];
262[label="List.merge vz3 (List.wrap vz40) (List.wrap vz410)",fontsize=16,color="magenta"];262 -> 493[label="",style="dashed", color="magenta", weight=3];
262 -> 494[label="",style="dashed", color="magenta", weight=3];
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];
576 -> 495[label="",style="solid", color="burlywood", weight=3];
577[label="vz411/[]",fontsize=10,color="white",style="solid",shape="box"];263 -> 577[label="",style="solid", color="burlywood", weight=9];
577 -> 496[label="",style="solid", color="burlywood", weight=3];
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];
578 -> 497[label="",style="solid", color="burlywood", weight=3];
579[label="vz38/[]",fontsize=10,color="white",style="solid",shape="box"];260 -> 579[label="",style="solid", color="burlywood", weight=9];
579 -> 498[label="",style="solid", color="burlywood", weight=3];
493 -> 18[label="",style="dashed", color="red", weight=0];
493[label="List.wrap vz40",fontsize=16,color="magenta"];494 -> 18[label="",style="dashed", color="red", weight=0];
494[label="List.wrap vz410",fontsize=16,color="magenta"];494 -> 499[label="",style="dashed", color="magenta", weight=3];
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];
580 -> 500[label="",style="solid", color="burlywood", weight=3];
581[label="vz39/[]",fontsize=10,color="white",style="solid",shape="box"];492 -> 581[label="",style="solid", color="burlywood", weight=9];
581 -> 501[label="",style="solid", color="burlywood", weight=3];
495[label="map List.wrap (vz4110 : vz4111)",fontsize=16,color="black",shape="box"];495 -> 502[label="",style="solid", color="black", weight=3];
496[label="map List.wrap []",fontsize=16,color="black",shape="box"];496 -> 503[label="",style="solid", color="black", weight=3];
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];
582 -> 504[label="",style="solid", color="burlywood", weight=3];
583[label="vz381/[]",fontsize=10,color="white",style="solid",shape="box"];497 -> 583[label="",style="solid", color="burlywood", weight=9];
583 -> 505[label="",style="solid", color="burlywood", weight=3];
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];
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];
584 -> 507[label="",style="solid", color="burlywood", weight=3];
585[label="vz40/[]",fontsize=10,color="white",style="solid",shape="box"];500 -> 585[label="",style="solid", color="burlywood", weight=9];
585 -> 508[label="",style="solid", color="burlywood", weight=3];
501[label="List.merge vz3 vz40 []",fontsize=16,color="black",shape="box"];501 -> 509[label="",style="solid", color="black", weight=3];
502[label="List.wrap vz4110 : map List.wrap vz4111",fontsize=16,color="green",shape="box"];502 -> 510[label="",style="dashed", color="green", weight=3];
502 -> 511[label="",style="dashed", color="green", weight=3];
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];
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];
506[label="List.mergesort' vz36 (vz37 : [])",fontsize=16,color="black",shape="box"];506 -> 514[label="",style="solid", color="black", weight=3];
507[label="List.merge vz3 (vz400 : vz401) (vz390 : vz391)",fontsize=16,color="black",shape="box"];507 -> 515[label="",style="solid", color="black", weight=3];
508[label="List.merge vz3 [] (vz390 : vz391)",fontsize=16,color="black",shape="box"];508 -> 516[label="",style="solid", color="black", weight=3];
509[label="vz40",fontsize=16,color="green",shape="box"];510 -> 18[label="",style="dashed", color="red", weight=0];
510[label="List.wrap vz4110",fontsize=16,color="magenta"];510 -> 517[label="",style="dashed", color="magenta", weight=3];
511 -> 263[label="",style="dashed", color="red", weight=0];
511[label="map List.wrap vz4111",fontsize=16,color="magenta"];511 -> 518[label="",style="dashed", color="magenta", weight=3];
512 -> 519[label="",style="dashed", color="red", weight=0];
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];
513[label="List.mergesort' vz36 (vz37 : vz380 : [])",fontsize=16,color="black",shape="box"];513 -> 521[label="",style="solid", color="black", weight=3];
514[label="vz37",fontsize=16,color="green",shape="box"];515 -> 522[label="",style="dashed", color="red", weight=0];
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];
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];
520[label="List.merge vz36 vz380 vz3810",fontsize=16,color="magenta"];520 -> 524[label="",style="dashed", color="magenta", weight=3];
520 -> 525[label="",style="dashed", color="magenta", weight=3];
520 -> 526[label="",style="dashed", color="magenta", weight=3];
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];
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];
523[label="vz3 vz400 vz390",fontsize=16,color="green",shape="box"];523 -> 534[label="",style="dashed", color="green", weight=3];
523 -> 535[label="",style="dashed", color="green", weight=3];
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];
586 -> 531[label="",style="solid", color="burlywood", weight=3];
587[label="vz42/EQ",fontsize=10,color="white",style="solid",shape="box"];522 -> 587[label="",style="solid", color="burlywood", weight=9];
587 -> 532[label="",style="solid", color="burlywood", weight=3];
588[label="vz42/GT",fontsize=10,color="white",style="solid",shape="box"];522 -> 588[label="",style="solid", color="burlywood", weight=9];
588 -> 533[label="",style="solid", color="burlywood", weight=3];
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];
528 -> 260[label="",style="dashed", color="red", weight=0];
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];
528 -> 538[label="",style="dashed", color="magenta", weight=3];
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];
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];
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];
536 -> 260[label="",style="dashed", color="red", weight=0];
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];
536 -> 543[label="",style="dashed", color="magenta", weight=3];
537 -> 492[label="",style="dashed", color="red", weight=0];
537[label="List.merge vz36 vz37 vz380",fontsize=16,color="magenta"];537 -> 544[label="",style="dashed", color="magenta", weight=3];
537 -> 545[label="",style="dashed", color="magenta", weight=3];
537 -> 546[label="",style="dashed", color="magenta", weight=3];
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];
540[label="vz400 : List.merge vz3 vz401 (vz390 : vz391)",fontsize=16,color="green",shape="box"];540 -> 548[label="",style="dashed", color="green", weight=3];
541[label="vz390 : List.merge vz3 (vz400 : vz401) vz391",fontsize=16,color="green",shape="box"];541 -> 549[label="",style="dashed", color="green", weight=3];
542 -> 492[label="",style="dashed", color="red", weight=0];
542[label="List.merge vz36 vz37 vz41",fontsize=16,color="magenta"];542 -> 550[label="",style="dashed", color="magenta", weight=3];
542 -> 551[label="",style="dashed", color="magenta", weight=3];
542 -> 552[label="",style="dashed", color="magenta", weight=3];
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];
589 -> 553[label="",style="solid", color="burlywood", weight=3];
590[label="vz3811/[]",fontsize=10,color="white",style="solid",shape="box"];543 -> 590[label="",style="solid", color="burlywood", weight=9];
590 -> 554[label="",style="solid", color="burlywood", weight=3];
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];
547[label="List.merge vz3 vz401 (vz390 : vz391)",fontsize=16,color="magenta"];547 -> 555[label="",style="dashed", color="magenta", weight=3];
547 -> 556[label="",style="dashed", color="magenta", weight=3];
548 -> 492[label="",style="dashed", color="red", weight=0];
548[label="List.merge vz3 vz401 (vz390 : vz391)",fontsize=16,color="magenta"];548 -> 557[label="",style="dashed", color="magenta", weight=3];
548 -> 558[label="",style="dashed", color="magenta", weight=3];
549 -> 492[label="",style="dashed", color="red", weight=0];
549[label="List.merge vz3 (vz400 : vz401) vz391",fontsize=16,color="magenta"];549 -> 559[label="",style="dashed", color="magenta", weight=3];
549 -> 560[label="",style="dashed", color="magenta", weight=3];
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];
591 -> 561[label="",style="solid", color="burlywood", weight=3];
592[label="vz38111/[]",fontsize=10,color="white",style="solid",shape="box"];553 -> 592[label="",style="solid", color="burlywood", weight=9];
592 -> 562[label="",style="solid", color="burlywood", weight=3];
554[label="List.merge_pairs vz36 []",fontsize=16,color="black",shape="box"];554 -> 563[label="",style="solid", color="black", weight=3];
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];
562[label="List.merge_pairs vz36 (vz38110 : [])",fontsize=16,color="black",shape="box"];562 -> 565[label="",style="solid", color="black", weight=3];
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];
564 -> 567[label="",style="dashed", color="green", weight=3];
565[label="vz38110 : []",fontsize=16,color="green",shape="box"];566 -> 492[label="",style="dashed", color="red", weight=0];
566[label="List.merge vz36 vz38110 vz381110",fontsize=16,color="magenta"];566 -> 568[label="",style="dashed", color="magenta", weight=3];
566 -> 569[label="",style="dashed", color="magenta", weight=3];
566 -> 570[label="",style="dashed", color="magenta", weight=3];
567 -> 543[label="",style="dashed", color="red", weight=0];
567[label="List.merge_pairs vz36 vz381111",fontsize=16,color="magenta"];567 -> 571[label="",style="dashed", color="magenta", weight=3];
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"];}

----------------------------------------

(8)
Complex Obligation (AND)

----------------------------------------

(9)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_merge0(vz390, vz3, vz400, vz401, vz391, ba) -> new_merge(vz3, :(vz400, vz401), vz391, ba)
   new_merge0(vz390, vz3, vz400, vz401, vz391, ba) -> new_merge(vz3, vz401, :(vz390, vz391), ba)
   new_merge(vz3, :(vz400, vz401), :(vz390, vz391), ba) -> new_merge0(vz390, vz3, vz400, vz401, vz391, 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_merge0(vz390, vz3, vz400, vz401, vz391, ba) -> new_merge(vz3, :(vz400, vz401), vz391, ba)
   new_merge(vz3, :(vz400, vz401), :(vz390, vz391), ba) -> new_merge0(vz390, vz3, vz400, vz401, vz391, ba)


Used ordering: Polynomial interpretation [POLO]:

   POL(:(x_1, x_2)) = 1 + x_1 + x_2
   POL(new_merge(x_1, x_2, x_3, x_4)) = x_1 + x_2 + 2*x_3 + x_4
   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


----------------------------------------

(11)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_merge0(vz390, vz3, vz400, vz401, vz391, ba) -> new_merge(vz3, vz401, :(vz390, vz391), ba)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(12) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
----------------------------------------

(13)
TRUE

----------------------------------------

(14)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_mergesort'0(vz36, vz37, :(vz380, :(vz3810, vz3811)), ba) -> new_mergesort'(vz36, vz37, new_merge1(vz36, vz380, vz3810, ba), vz3811, ba)
   new_mergesort'0(vz36, vz37, :(vz380, []), ba) -> new_mergesort'0(vz36, new_merge1(vz36, vz37, vz380, ba), [], ba)
   new_mergesort'(vz36, vz37, vz41, vz3811, ba) -> new_mergesort'0(vz36, new_merge1(vz36, vz37, vz41, ba), new_merge_pairs0(vz36, vz3811, ba), ba)

The TRS R consists of the following rules:

   new_merge_pairs0(vz36, :(vz38110, []), ba) -> :(vz38110, [])
   new_merge_pairs0(vz36, [], ba) -> []
   new_merge_pairs0(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> :(new_merge1(vz36, vz38110, vz381110, ba), new_merge_pairs0(vz36, vz381111, ba))

The set Q consists of the following terms:

   new_merge_pairs0(x0, :(x1, []), x2)
   new_merge_pairs0(x0, :(x1, :(x2, x3)), x4)
   new_merge_pairs0(x0, [], x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(15) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
----------------------------------------

(16)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_mergesort'(vz36, vz37, vz41, vz3811, ba) -> new_mergesort'0(vz36, new_merge1(vz36, vz37, vz41, ba), new_merge_pairs0(vz36, vz3811, ba), ba)
   new_mergesort'0(vz36, vz37, :(vz380, :(vz3810, vz3811)), ba) -> new_mergesort'(vz36, vz37, new_merge1(vz36, vz380, vz3810, ba), vz3811, ba)

The TRS R consists of the following rules:

   new_merge_pairs0(vz36, :(vz38110, []), ba) -> :(vz38110, [])
   new_merge_pairs0(vz36, [], ba) -> []
   new_merge_pairs0(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> :(new_merge1(vz36, vz38110, vz381110, ba), new_merge_pairs0(vz36, vz381111, ba))

The set Q consists of the following terms:

   new_merge_pairs0(x0, :(x1, []), x2)
   new_merge_pairs0(x0, :(x1, :(x2, x3)), x4)
   new_merge_pairs0(x0, [], x1)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(17) QDPSizeChangeProof (EQUIVALENT)
We used the following order together with the size-change analysis [AAECC05] to show that there are no infinite chains for this DP problem. 

Order:Polynomial interpretation [POLO]:

   POL(:(x_1, x_2)) = 1 + x_2
   POL([]) = 0
   POL(new_merge1(x_1, x_2, x_3, x_4)) = 1
   POL(new_merge_pairs0(x_1, x_2, x_3)) = x_2




From the DPs we obtained the following set of size-change graphs:
*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})
The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 4, 4 >= 5


*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})
The graph contains the following edges 1 >= 1, 4 >= 3, 5 >= 4



We oriented the following set of usable rules [AAECC05,FROCOS05].

   new_merge_pairs0(vz36, [], ba) -> []
   new_merge_pairs0(vz36, :(vz38110, []), ba) -> :(vz38110, [])
   new_merge_pairs0(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> :(new_merge1(vz36, vz38110, vz381110, ba), new_merge_pairs0(vz36, vz381111, ba))

----------------------------------------

(18)
YES

----------------------------------------

(19)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_map(:(vz4110, vz4111), ba) -> new_map(vz4111, ba)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(20) 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_map(:(vz4110, vz4111), ba) -> new_map(vz4111, ba)
The graph contains the following edges 1 > 1, 2 >= 2


----------------------------------------

(21)
YES

----------------------------------------

(22)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_merge_pairs(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> new_merge_pairs(vz36, vz381111, ba)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(23) 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_merge_pairs(vz36, :(vz38110, :(vz381110, vz381111)), ba) -> new_merge_pairs(vz36, vz381111, ba)
The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3


----------------------------------------

(24)
YES