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


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


YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.hs
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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, 0 ms]
(6) HASKELL
(7) Narrow [SOUND, 0 ms]
(8) QDP
(9) DependencyGraphProof [EQUIVALENT, 0 ms]
(10) AND
    (11) QDP
        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (13) YES
    (14) QDP
        (15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (16) YES


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

(0)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;

instance (Eq a, Eq b) => Eq FiniteMap b a where { 
}
elemFM :: Ord b => b  ->  FiniteMap b a  ->  Bool;
elemFM key fm = case lookupFM fm key of { 
Nothing-> False; 
Just elt-> True; 
 } ;

lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
 | key_to_find > key = lookupFM fm_r key_to_find
 | otherwise = Just elt;

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

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

(1) CR (EQUIVALENT)
Case Reductions:
The following Case expression
"case lookupFM fm key of {
Nothing  -> False;
Just elt  -> True}
"
is transformed to
"elemFM0 Nothing = False;
elemFM0 (Just elt) = True;
"

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

(2)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
}
elemFM :: Ord b => b  ->  FiniteMap b a  ->  Bool;
elemFM key fm = elemFM0 (lookupFM fm key);

elemFM0 Nothing = False;
elemFM0 (Just elt) = True;

lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
 | key_to_find > key = lookupFM fm_r key_to_find
 | otherwise = Just elt;

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

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

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

(4)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
}
elemFM :: Ord b => b  ->  FiniteMap b a  ->  Bool;
elemFM key fm = elemFM0 (lookupFM fm key);

elemFM0 Nothing = False;
elemFM0 (Just elt) = True;

lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt vy fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
 | key_to_find > key = lookupFM fm_r key_to_find
 | otherwise = Just elt;

}
module Maybe where {
import qualified FiniteMap;
import qualified Main;
import qualified Prelude;
}
module Main where {
import qualified FiniteMap;
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;
"
The following Function with conditions
"lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt vy fm_l fm_r) key_to_find|key_to_find < keylookupFM fm_l key_to_find|key_to_find > keylookupFM fm_r key_to_find|otherwiseJust elt;
"
is transformed to
"lookupFM EmptyFM key = lookupFM4 EmptyFM key;
lookupFM (Branch key elt vy fm_l fm_r) key_to_find = lookupFM3 (Branch key elt vy fm_l fm_r) key_to_find;
"
"lookupFM0 key elt vy fm_l fm_r key_to_find True = Just elt;
"
"lookupFM1 key elt vy fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
lookupFM1 key elt vy fm_l fm_r key_to_find False = lookupFM0 key elt vy fm_l fm_r key_to_find otherwise;
"
"lookupFM2 key elt vy fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
lookupFM2 key elt vy fm_l fm_r key_to_find False = lookupFM1 key elt vy fm_l fm_r key_to_find (key_to_find > key);
"
"lookupFM3 (Branch key elt vy fm_l fm_r) key_to_find = lookupFM2 key elt vy fm_l fm_r key_to_find (key_to_find < key);
"
"lookupFM4 EmptyFM key = Nothing;
lookupFM4 wv ww = lookupFM3 wv ww;
"

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

(6)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
}
elemFM :: Ord b => b  ->  FiniteMap b a  ->  Bool;
elemFM key fm = elemFM0 (lookupFM fm key);

elemFM0 Nothing = False;
elemFM0 (Just elt) = True;

lookupFM :: Ord a => FiniteMap a b  ->  a  ->  Maybe b;
lookupFM EmptyFM key = lookupFM4 EmptyFM key;
lookupFM (Branch key elt vy fm_l fm_r) key_to_find = lookupFM3 (Branch key elt vy fm_l fm_r) key_to_find;

lookupFM0 key elt vy fm_l fm_r key_to_find True = Just elt;

lookupFM1 key elt vy fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
lookupFM1 key elt vy fm_l fm_r key_to_find False = lookupFM0 key elt vy fm_l fm_r key_to_find otherwise;

lookupFM2 key elt vy fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
lookupFM2 key elt vy fm_l fm_r key_to_find False = lookupFM1 key elt vy fm_l fm_r key_to_find (key_to_find > key);

lookupFM3 (Branch key elt vy fm_l fm_r) key_to_find = lookupFM2 key elt vy fm_l fm_r key_to_find (key_to_find < key);

lookupFM4 EmptyFM key = Nothing;
lookupFM4 wv ww = lookupFM3 wv ww;

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

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

(7) Narrow (SOUND)
Haskell To QDPs

digraph dp_graph {
node [outthreshold=100, inthreshold=100];1[label="FiniteMap.elemFM",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
3[label="FiniteMap.elemFM wx3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3];
4[label="FiniteMap.elemFM wx3 wx4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3];
5[label="FiniteMap.elemFM0 (FiniteMap.lookupFM wx4 wx3)",fontsize=16,color="burlywood",shape="triangle"];759[label="wx4/FiniteMap.EmptyFM",fontsize=10,color="white",style="solid",shape="box"];5 -> 759[label="",style="solid", color="burlywood", weight=9];
759 -> 6[label="",style="solid", color="burlywood", weight=3];
760[label="wx4/FiniteMap.Branch wx40 wx41 wx42 wx43 wx44",fontsize=10,color="white",style="solid",shape="box"];5 -> 760[label="",style="solid", color="burlywood", weight=9];
760 -> 7[label="",style="solid", color="burlywood", weight=3];
6[label="FiniteMap.elemFM0 (FiniteMap.lookupFM FiniteMap.EmptyFM wx3)",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3];
7[label="FiniteMap.elemFM0 (FiniteMap.lookupFM (FiniteMap.Branch wx40 wx41 wx42 wx43 wx44) wx3)",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3];
8[label="FiniteMap.elemFM0 (FiniteMap.lookupFM4 FiniteMap.EmptyFM wx3)",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3];
9[label="FiniteMap.elemFM0 (FiniteMap.lookupFM3 (FiniteMap.Branch wx40 wx41 wx42 wx43 wx44) wx3)",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3];
10[label="FiniteMap.elemFM0 Nothing",fontsize=16,color="black",shape="box"];10 -> 12[label="",style="solid", color="black", weight=3];
11[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 wx40 wx41 wx42 wx43 wx44 wx3 (wx3 < wx40))",fontsize=16,color="black",shape="box"];11 -> 13[label="",style="solid", color="black", weight=3];
12[label="False",fontsize=16,color="green",shape="box"];13[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 wx40 wx41 wx42 wx43 wx44 wx3 (compare wx3 wx40 == LT))",fontsize=16,color="black",shape="box"];13 -> 14[label="",style="solid", color="black", weight=3];
14[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 wx40 wx41 wx42 wx43 wx44 wx3 (primCmpChar wx3 wx40 == LT))",fontsize=16,color="burlywood",shape="box"];761[label="wx3/Char wx30",fontsize=10,color="white",style="solid",shape="box"];14 -> 761[label="",style="solid", color="burlywood", weight=9];
761 -> 15[label="",style="solid", color="burlywood", weight=3];
15[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 wx40 wx41 wx42 wx43 wx44 (Char wx30) (primCmpChar (Char wx30) wx40 == LT))",fontsize=16,color="burlywood",shape="box"];762[label="wx40/Char wx400",fontsize=10,color="white",style="solid",shape="box"];15 -> 762[label="",style="solid", color="burlywood", weight=9];
762 -> 16[label="",style="solid", color="burlywood", weight=3];
16[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char wx400) wx41 wx42 wx43 wx44 (Char wx30) (primCmpChar (Char wx30) (Char wx400) == LT))",fontsize=16,color="black",shape="box"];16 -> 17[label="",style="solid", color="black", weight=3];
17[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char wx400) wx41 wx42 wx43 wx44 (Char wx30) (primCmpNat wx30 wx400 == LT))",fontsize=16,color="burlywood",shape="box"];763[label="wx30/Succ wx300",fontsize=10,color="white",style="solid",shape="box"];17 -> 763[label="",style="solid", color="burlywood", weight=9];
763 -> 18[label="",style="solid", color="burlywood", weight=3];
764[label="wx30/Zero",fontsize=10,color="white",style="solid",shape="box"];17 -> 764[label="",style="solid", color="burlywood", weight=9];
764 -> 19[label="",style="solid", color="burlywood", weight=3];
18[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char wx400) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (primCmpNat (Succ wx300) wx400 == LT))",fontsize=16,color="burlywood",shape="box"];765[label="wx400/Succ wx4000",fontsize=10,color="white",style="solid",shape="box"];18 -> 765[label="",style="solid", color="burlywood", weight=9];
765 -> 20[label="",style="solid", color="burlywood", weight=3];
766[label="wx400/Zero",fontsize=10,color="white",style="solid",shape="box"];18 -> 766[label="",style="solid", color="burlywood", weight=9];
766 -> 21[label="",style="solid", color="burlywood", weight=3];
19[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char wx400) wx41 wx42 wx43 wx44 (Char Zero) (primCmpNat Zero wx400 == LT))",fontsize=16,color="burlywood",shape="box"];767[label="wx400/Succ wx4000",fontsize=10,color="white",style="solid",shape="box"];19 -> 767[label="",style="solid", color="burlywood", weight=9];
767 -> 22[label="",style="solid", color="burlywood", weight=3];
768[label="wx400/Zero",fontsize=10,color="white",style="solid",shape="box"];19 -> 768[label="",style="solid", color="burlywood", weight=9];
768 -> 23[label="",style="solid", color="burlywood", weight=3];
20[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx4000)) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (primCmpNat (Succ wx300) (Succ wx4000) == LT))",fontsize=16,color="black",shape="box"];20 -> 24[label="",style="solid", color="black", weight=3];
21[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char Zero) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (primCmpNat (Succ wx300) Zero == LT))",fontsize=16,color="black",shape="box"];21 -> 25[label="",style="solid", color="black", weight=3];
22[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx4000)) wx41 wx42 wx43 wx44 (Char Zero) (primCmpNat Zero (Succ wx4000) == LT))",fontsize=16,color="black",shape="box"];22 -> 26[label="",style="solid", color="black", weight=3];
23[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) (primCmpNat Zero Zero == LT))",fontsize=16,color="black",shape="box"];23 -> 27[label="",style="solid", color="black", weight=3];
24 -> 323[label="",style="dashed", color="red", weight=0];
24[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx4000)) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (primCmpNat wx300 wx4000 == LT))",fontsize=16,color="magenta"];24 -> 324[label="",style="dashed", color="magenta", weight=3];
24 -> 325[label="",style="dashed", color="magenta", weight=3];
24 -> 326[label="",style="dashed", color="magenta", weight=3];
24 -> 327[label="",style="dashed", color="magenta", weight=3];
24 -> 328[label="",style="dashed", color="magenta", weight=3];
24 -> 329[label="",style="dashed", color="magenta", weight=3];
24 -> 330[label="",style="dashed", color="magenta", weight=3];
24 -> 331[label="",style="dashed", color="magenta", weight=3];
25[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char Zero) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (GT == LT))",fontsize=16,color="black",shape="box"];25 -> 30[label="",style="solid", color="black", weight=3];
26[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx4000)) wx41 wx42 wx43 wx44 (Char Zero) (LT == LT))",fontsize=16,color="black",shape="box"];26 -> 31[label="",style="solid", color="black", weight=3];
27[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) (EQ == LT))",fontsize=16,color="black",shape="box"];27 -> 32[label="",style="solid", color="black", weight=3];
324[label="wx300",fontsize=16,color="green",shape="box"];325[label="wx300",fontsize=16,color="green",shape="box"];326[label="wx41",fontsize=16,color="green",shape="box"];327[label="wx44",fontsize=16,color="green",shape="box"];328[label="wx42",fontsize=16,color="green",shape="box"];329[label="wx4000",fontsize=16,color="green",shape="box"];330[label="wx43",fontsize=16,color="green",shape="box"];331[label="wx4000",fontsize=16,color="green",shape="box"];323[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpNat wx32 wx33 == LT))",fontsize=16,color="burlywood",shape="triangle"];769[label="wx32/Succ wx320",fontsize=10,color="white",style="solid",shape="box"];323 -> 769[label="",style="solid", color="burlywood", weight=9];
769 -> 404[label="",style="solid", color="burlywood", weight=3];
770[label="wx32/Zero",fontsize=10,color="white",style="solid",shape="box"];323 -> 770[label="",style="solid", color="burlywood", weight=9];
770 -> 405[label="",style="solid", color="burlywood", weight=3];
30[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char Zero) wx41 wx42 wx43 wx44 (Char (Succ wx300)) False)",fontsize=16,color="black",shape="box"];30 -> 37[label="",style="solid", color="black", weight=3];
31[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx4000)) wx41 wx42 wx43 wx44 (Char Zero) True)",fontsize=16,color="black",shape="box"];31 -> 38[label="",style="solid", color="black", weight=3];
32[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) False)",fontsize=16,color="black",shape="box"];32 -> 39[label="",style="solid", color="black", weight=3];
404[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpNat (Succ wx320) wx33 == LT))",fontsize=16,color="burlywood",shape="box"];771[label="wx33/Succ wx330",fontsize=10,color="white",style="solid",shape="box"];404 -> 771[label="",style="solid", color="burlywood", weight=9];
771 -> 406[label="",style="solid", color="burlywood", weight=3];
772[label="wx33/Zero",fontsize=10,color="white",style="solid",shape="box"];404 -> 772[label="",style="solid", color="burlywood", weight=9];
772 -> 407[label="",style="solid", color="burlywood", weight=3];
405[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpNat Zero wx33 == LT))",fontsize=16,color="burlywood",shape="box"];773[label="wx33/Succ wx330",fontsize=10,color="white",style="solid",shape="box"];405 -> 773[label="",style="solid", color="burlywood", weight=9];
773 -> 408[label="",style="solid", color="burlywood", weight=3];
774[label="wx33/Zero",fontsize=10,color="white",style="solid",shape="box"];405 -> 774[label="",style="solid", color="burlywood", weight=9];
774 -> 409[label="",style="solid", color="burlywood", weight=3];
37[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (Char (Succ wx300) > Char Zero))",fontsize=16,color="black",shape="box"];37 -> 44[label="",style="solid", color="black", weight=3];
38 -> 5[label="",style="dashed", color="red", weight=0];
38[label="FiniteMap.elemFM0 (FiniteMap.lookupFM wx43 (Char Zero))",fontsize=16,color="magenta"];38 -> 45[label="",style="dashed", color="magenta", weight=3];
38 -> 46[label="",style="dashed", color="magenta", weight=3];
39[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) (Char Zero > Char Zero))",fontsize=16,color="black",shape="box"];39 -> 47[label="",style="solid", color="black", weight=3];
406[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpNat (Succ wx320) (Succ wx330) == LT))",fontsize=16,color="black",shape="box"];406 -> 410[label="",style="solid", color="black", weight=3];
407[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpNat (Succ wx320) Zero == LT))",fontsize=16,color="black",shape="box"];407 -> 411[label="",style="solid", color="black", weight=3];
408[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpNat Zero (Succ wx330) == LT))",fontsize=16,color="black",shape="box"];408 -> 412[label="",style="solid", color="black", weight=3];
409[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpNat Zero Zero == LT))",fontsize=16,color="black",shape="box"];409 -> 413[label="",style="solid", color="black", weight=3];
44[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (compare (Char (Succ wx300)) (Char Zero) == GT))",fontsize=16,color="black",shape="box"];44 -> 53[label="",style="solid", color="black", weight=3];
45[label="Char Zero",fontsize=16,color="green",shape="box"];46[label="wx43",fontsize=16,color="green",shape="box"];47[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) (compare (Char Zero) (Char Zero) == GT))",fontsize=16,color="black",shape="box"];47 -> 54[label="",style="solid", color="black", weight=3];
410 -> 323[label="",style="dashed", color="red", weight=0];
410[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpNat wx320 wx330 == LT))",fontsize=16,color="magenta"];410 -> 414[label="",style="dashed", color="magenta", weight=3];
410 -> 415[label="",style="dashed", color="magenta", weight=3];
411[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (GT == LT))",fontsize=16,color="black",shape="box"];411 -> 416[label="",style="solid", color="black", weight=3];
412[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (LT == LT))",fontsize=16,color="black",shape="box"];412 -> 417[label="",style="solid", color="black", weight=3];
413[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (EQ == LT))",fontsize=16,color="black",shape="box"];413 -> 418[label="",style="solid", color="black", weight=3];
53[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (primCmpChar (Char (Succ wx300)) (Char Zero) == GT))",fontsize=16,color="black",shape="box"];53 -> 62[label="",style="solid", color="black", weight=3];
54[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) (primCmpChar (Char Zero) (Char Zero) == GT))",fontsize=16,color="black",shape="box"];54 -> 63[label="",style="solid", color="black", weight=3];
414[label="wx320",fontsize=16,color="green",shape="box"];415[label="wx330",fontsize=16,color="green",shape="box"];416[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) False)",fontsize=16,color="black",shape="triangle"];416 -> 419[label="",style="solid", color="black", weight=3];
417[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) True)",fontsize=16,color="black",shape="box"];417 -> 420[label="",style="solid", color="black", weight=3];
418 -> 416[label="",style="dashed", color="red", weight=0];
418[label="FiniteMap.elemFM0 (FiniteMap.lookupFM2 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) False)",fontsize=16,color="magenta"];62[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (primCmpNat (Succ wx300) Zero == GT))",fontsize=16,color="black",shape="box"];62 -> 72[label="",style="solid", color="black", weight=3];
63[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) (primCmpNat Zero Zero == GT))",fontsize=16,color="black",shape="box"];63 -> 73[label="",style="solid", color="black", weight=3];
419[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (Char (Succ wx31) > Char (Succ wx26)))",fontsize=16,color="black",shape="box"];419 -> 421[label="",style="solid", color="black", weight=3];
420 -> 5[label="",style="dashed", color="red", weight=0];
420[label="FiniteMap.elemFM0 (FiniteMap.lookupFM wx29 (Char (Succ wx31)))",fontsize=16,color="magenta"];420 -> 422[label="",style="dashed", color="magenta", weight=3];
420 -> 423[label="",style="dashed", color="magenta", weight=3];
72[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char (Succ wx300)) (GT == GT))",fontsize=16,color="black",shape="box"];72 -> 81[label="",style="solid", color="black", weight=3];
73[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) (EQ == GT))",fontsize=16,color="black",shape="box"];73 -> 82[label="",style="solid", color="black", weight=3];
421[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (compare (Char (Succ wx31)) (Char (Succ wx26)) == GT))",fontsize=16,color="black",shape="box"];421 -> 424[label="",style="solid", color="black", weight=3];
422[label="Char (Succ wx31)",fontsize=16,color="green",shape="box"];423[label="wx29",fontsize=16,color="green",shape="box"];81[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char (Succ wx300)) True)",fontsize=16,color="black",shape="box"];81 -> 92[label="",style="solid", color="black", weight=3];
82[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) False)",fontsize=16,color="black",shape="box"];82 -> 93[label="",style="solid", color="black", weight=3];
424[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpChar (Char (Succ wx31)) (Char (Succ wx26)) == GT))",fontsize=16,color="black",shape="box"];424 -> 425[label="",style="solid", color="black", weight=3];
92 -> 5[label="",style="dashed", color="red", weight=0];
92[label="FiniteMap.elemFM0 (FiniteMap.lookupFM wx44 (Char (Succ wx300)))",fontsize=16,color="magenta"];92 -> 104[label="",style="dashed", color="magenta", weight=3];
92 -> 105[label="",style="dashed", color="magenta", weight=3];
93[label="FiniteMap.elemFM0 (FiniteMap.lookupFM0 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) otherwise)",fontsize=16,color="black",shape="box"];93 -> 106[label="",style="solid", color="black", weight=3];
425 -> 648[label="",style="dashed", color="red", weight=0];
425[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx26)) wx27 wx28 wx29 wx30 (Char (Succ wx31)) (primCmpNat (Succ wx31) (Succ wx26) == GT))",fontsize=16,color="magenta"];425 -> 649[label="",style="dashed", color="magenta", weight=3];
425 -> 650[label="",style="dashed", color="magenta", weight=3];
425 -> 651[label="",style="dashed", color="magenta", weight=3];
425 -> 652[label="",style="dashed", color="magenta", weight=3];
425 -> 653[label="",style="dashed", color="magenta", weight=3];
425 -> 654[label="",style="dashed", color="magenta", weight=3];
425 -> 655[label="",style="dashed", color="magenta", weight=3];
425 -> 656[label="",style="dashed", color="magenta", weight=3];
104[label="Char (Succ wx300)",fontsize=16,color="green",shape="box"];105[label="wx44",fontsize=16,color="green",shape="box"];106[label="FiniteMap.elemFM0 (FiniteMap.lookupFM0 (Char Zero) wx41 wx42 wx43 wx44 (Char Zero) True)",fontsize=16,color="black",shape="box"];106 -> 116[label="",style="solid", color="black", weight=3];
649[label="wx26",fontsize=16,color="green",shape="box"];650[label="wx31",fontsize=16,color="green",shape="box"];651[label="wx29",fontsize=16,color="green",shape="box"];652[label="wx30",fontsize=16,color="green",shape="box"];653[label="Succ wx31",fontsize=16,color="green",shape="box"];654[label="wx27",fontsize=16,color="green",shape="box"];655[label="wx28",fontsize=16,color="green",shape="box"];656[label="Succ wx26",fontsize=16,color="green",shape="box"];648[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (primCmpNat wx79 wx80 == GT))",fontsize=16,color="burlywood",shape="triangle"];775[label="wx79/Succ wx790",fontsize=10,color="white",style="solid",shape="box"];648 -> 775[label="",style="solid", color="burlywood", weight=9];
775 -> 737[label="",style="solid", color="burlywood", weight=3];
776[label="wx79/Zero",fontsize=10,color="white",style="solid",shape="box"];648 -> 776[label="",style="solid", color="burlywood", weight=9];
776 -> 738[label="",style="solid", color="burlywood", weight=3];
116[label="FiniteMap.elemFM0 (Just wx41)",fontsize=16,color="black",shape="triangle"];116 -> 128[label="",style="solid", color="black", weight=3];
737[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (primCmpNat (Succ wx790) wx80 == GT))",fontsize=16,color="burlywood",shape="box"];777[label="wx80/Succ wx800",fontsize=10,color="white",style="solid",shape="box"];737 -> 777[label="",style="solid", color="burlywood", weight=9];
777 -> 739[label="",style="solid", color="burlywood", weight=3];
778[label="wx80/Zero",fontsize=10,color="white",style="solid",shape="box"];737 -> 778[label="",style="solid", color="burlywood", weight=9];
778 -> 740[label="",style="solid", color="burlywood", weight=3];
738[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (primCmpNat Zero wx80 == GT))",fontsize=16,color="burlywood",shape="box"];779[label="wx80/Succ wx800",fontsize=10,color="white",style="solid",shape="box"];738 -> 779[label="",style="solid", color="burlywood", weight=9];
779 -> 741[label="",style="solid", color="burlywood", weight=3];
780[label="wx80/Zero",fontsize=10,color="white",style="solid",shape="box"];738 -> 780[label="",style="solid", color="burlywood", weight=9];
780 -> 742[label="",style="solid", color="burlywood", weight=3];
128[label="True",fontsize=16,color="green",shape="box"];739[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (primCmpNat (Succ wx790) (Succ wx800) == GT))",fontsize=16,color="black",shape="box"];739 -> 743[label="",style="solid", color="black", weight=3];
740[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (primCmpNat (Succ wx790) Zero == GT))",fontsize=16,color="black",shape="box"];740 -> 744[label="",style="solid", color="black", weight=3];
741[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (primCmpNat Zero (Succ wx800) == GT))",fontsize=16,color="black",shape="box"];741 -> 745[label="",style="solid", color="black", weight=3];
742[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (primCmpNat Zero Zero == GT))",fontsize=16,color="black",shape="box"];742 -> 746[label="",style="solid", color="black", weight=3];
743 -> 648[label="",style="dashed", color="red", weight=0];
743[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (primCmpNat wx790 wx800 == GT))",fontsize=16,color="magenta"];743 -> 747[label="",style="dashed", color="magenta", weight=3];
743 -> 748[label="",style="dashed", color="magenta", weight=3];
744[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (GT == GT))",fontsize=16,color="black",shape="box"];744 -> 749[label="",style="solid", color="black", weight=3];
745[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (LT == GT))",fontsize=16,color="black",shape="box"];745 -> 750[label="",style="solid", color="black", weight=3];
746[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) (EQ == GT))",fontsize=16,color="black",shape="box"];746 -> 751[label="",style="solid", color="black", weight=3];
747[label="wx790",fontsize=16,color="green",shape="box"];748[label="wx800",fontsize=16,color="green",shape="box"];749[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) True)",fontsize=16,color="black",shape="box"];749 -> 752[label="",style="solid", color="black", weight=3];
750[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) False)",fontsize=16,color="black",shape="triangle"];750 -> 753[label="",style="solid", color="black", weight=3];
751 -> 750[label="",style="dashed", color="red", weight=0];
751[label="FiniteMap.elemFM0 (FiniteMap.lookupFM1 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) False)",fontsize=16,color="magenta"];752 -> 5[label="",style="dashed", color="red", weight=0];
752[label="FiniteMap.elemFM0 (FiniteMap.lookupFM wx77 (Char (Succ wx78)))",fontsize=16,color="magenta"];752 -> 754[label="",style="dashed", color="magenta", weight=3];
752 -> 755[label="",style="dashed", color="magenta", weight=3];
753[label="FiniteMap.elemFM0 (FiniteMap.lookupFM0 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) otherwise)",fontsize=16,color="black",shape="box"];753 -> 756[label="",style="solid", color="black", weight=3];
754[label="Char (Succ wx78)",fontsize=16,color="green",shape="box"];755[label="wx77",fontsize=16,color="green",shape="box"];756[label="FiniteMap.elemFM0 (FiniteMap.lookupFM0 (Char (Succ wx73)) wx74 wx75 wx76 wx77 (Char (Succ wx78)) True)",fontsize=16,color="black",shape="box"];756 -> 757[label="",style="solid", color="black", weight=3];
757 -> 116[label="",style="dashed", color="red", weight=0];
757[label="FiniteMap.elemFM0 (Just wx74)",fontsize=16,color="magenta"];757 -> 758[label="",style="dashed", color="magenta", weight=3];
758[label="wx74",fontsize=16,color="green",shape="box"];}

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

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

   new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Succ(wx330), h) -> new_elemFM01(wx29, Char(Succ(wx31)), h)
   new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx320), Zero, h) -> new_elemFM00(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx31), Succ(wx26), h)
   new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Zero, ba) -> new_elemFM01(wx77, Char(Succ(wx78)), ba)
   new_elemFM01(Branch(Char(Zero), wx41, wx42, wx43, wx44), Char(Succ(wx300)), bb) -> new_elemFM01(wx44, Char(Succ(wx300)), bb)
   new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Zero, h) -> new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h)
   new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h) -> new_elemFM00(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx31), Succ(wx26), h)
   new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx320), Succ(wx330), h) -> new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, wx320, wx330, h)
   new_elemFM01(Branch(Char(Succ(wx4000)), wx41, wx42, wx43, wx44), Char(Succ(wx300)), bb) -> new_elemFM0(wx4000, wx41, wx42, wx43, wx44, wx300, wx300, wx4000, bb)
   new_elemFM01(Branch(Char(Succ(wx4000)), wx41, wx42, wx43, wx44), Char(Zero), bb) -> new_elemFM01(wx43, Char(Zero), bb)
   new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Succ(wx800), ba) -> new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, wx790, wx800, ba)

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

(9) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs.
----------------------------------------

(10)
Complex Obligation (AND)

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

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

   new_elemFM01(Branch(Char(Succ(wx4000)), wx41, wx42, wx43, wx44), Char(Zero), bb) -> new_elemFM01(wx43, Char(Zero), bb)

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

(12) 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_elemFM01(Branch(Char(Succ(wx4000)), wx41, wx42, wx43, wx44), Char(Zero), bb) -> new_elemFM01(wx43, Char(Zero), bb)
The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3


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

(13)
YES

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

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

   new_elemFM01(Branch(Char(Zero), wx41, wx42, wx43, wx44), Char(Succ(wx300)), bb) -> new_elemFM01(wx44, Char(Succ(wx300)), bb)
   new_elemFM01(Branch(Char(Succ(wx4000)), wx41, wx42, wx43, wx44), Char(Succ(wx300)), bb) -> new_elemFM0(wx4000, wx41, wx42, wx43, wx44, wx300, wx300, wx4000, bb)
   new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Succ(wx330), h) -> new_elemFM01(wx29, Char(Succ(wx31)), h)
   new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx320), Zero, h) -> new_elemFM00(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx31), Succ(wx26), h)
   new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Succ(wx800), ba) -> new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, wx790, wx800, ba)
   new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Zero, ba) -> new_elemFM01(wx77, Char(Succ(wx78)), ba)
   new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Zero, h) -> new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h)
   new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h) -> new_elemFM00(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx31), Succ(wx26), h)
   new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx320), Succ(wx330), h) -> new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, wx320, wx330, h)

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

(15) 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_elemFM01(Branch(Char(Zero), wx41, wx42, wx43, wx44), Char(Succ(wx300)), bb) -> new_elemFM01(wx44, Char(Succ(wx300)), bb)
The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3


*new_elemFM01(Branch(Char(Succ(wx4000)), wx41, wx42, wx43, wx44), Char(Succ(wx300)), bb) -> new_elemFM0(wx4000, wx41, wx42, wx43, wx44, wx300, wx300, wx4000, bb)
The graph contains the following edges 1 > 1, 1 > 2, 1 > 3, 1 > 4, 1 > 5, 2 > 6, 2 > 7, 1 > 8, 3 >= 9


*new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Succ(wx330), h) -> new_elemFM01(wx29, Char(Succ(wx31)), h)
The graph contains the following edges 4 >= 1, 9 >= 3


*new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Zero, ba) -> new_elemFM01(wx77, Char(Succ(wx78)), ba)
The graph contains the following edges 5 >= 1, 9 >= 3


*new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx320), Succ(wx330), h) -> new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, wx320, wx330, h)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 7 > 7, 8 > 8, 9 >= 9


*new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Succ(wx800), ba) -> new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, wx790, wx800, ba)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 7 > 7, 8 > 8, 9 >= 9


*new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h) -> new_elemFM00(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx31), Succ(wx26), h)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 7 >= 9


*new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx320), Zero, h) -> new_elemFM00(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx31), Succ(wx26), h)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 9 >= 9


*new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Zero, h) -> new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 9 >= 7


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

(16)
YES