10.78/4.81 YES 12.94/5.38 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 12.94/5.38 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 12.94/5.38 12.94/5.38 12.94/5.38 H-Termination with start terms of the given HASKELL could be proven: 12.94/5.38 12.94/5.38 (0) HASKELL 12.94/5.38 (1) CR [EQUIVALENT, 0 ms] 12.94/5.38 (2) HASKELL 12.94/5.38 (3) BR [EQUIVALENT, 0 ms] 12.94/5.38 (4) HASKELL 12.94/5.38 (5) COR [EQUIVALENT, 0 ms] 12.94/5.38 (6) HASKELL 12.94/5.38 (7) Narrow [SOUND, 0 ms] 12.94/5.38 (8) QDP 12.94/5.38 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 12.94/5.38 (10) AND 12.94/5.38 (11) QDP 12.94/5.38 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.94/5.38 (13) YES 12.94/5.38 (14) QDP 12.94/5.38 (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.94/5.38 (16) YES 12.94/5.38 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (0) 12.94/5.38 Obligation: 12.94/5.38 mainModule Main 12.94/5.38 module FiniteMap where { 12.94/5.38 import qualified Main; 12.94/5.38 import qualified Maybe; 12.94/5.38 import qualified Prelude; 12.94/5.38 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 12.94/5.38 12.94/5.38 instance (Eq a, Eq b) => Eq FiniteMap b a where { 12.94/5.38 } 12.94/5.38 elemFM :: Ord b => b -> FiniteMap b a -> Bool; 12.94/5.38 elemFM key fm = case lookupFM fm key of { 12.94/5.38 Nothing-> False; 12.94/5.38 Just elt-> True; 12.94/5.38 } ; 12.94/5.38 12.94/5.38 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 12.94/5.38 lookupFM EmptyFM key = Nothing; 12.94/5.38 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 12.94/5.38 | key_to_find > key = lookupFM fm_r key_to_find 12.94/5.38 | otherwise = Just elt; 12.94/5.38 12.94/5.38 } 12.94/5.38 module Maybe where { 12.94/5.38 import qualified FiniteMap; 12.94/5.38 import qualified Main; 12.94/5.38 import qualified Prelude; 12.94/5.38 } 12.94/5.38 module Main where { 12.94/5.38 import qualified FiniteMap; 12.94/5.38 import qualified Maybe; 12.94/5.38 import qualified Prelude; 12.94/5.38 } 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (1) CR (EQUIVALENT) 12.94/5.38 Case Reductions: 12.94/5.38 The following Case expression 12.94/5.38 "case lookupFM fm key of { 12.94/5.38 Nothing -> False; 12.94/5.38 Just elt -> True} 12.94/5.38 " 12.94/5.38 is transformed to 12.94/5.38 "elemFM0 Nothing = False; 12.94/5.38 elemFM0 (Just elt) = True; 12.94/5.38 " 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (2) 12.94/5.38 Obligation: 12.94/5.38 mainModule Main 12.94/5.38 module FiniteMap where { 12.94/5.38 import qualified Main; 12.94/5.38 import qualified Maybe; 12.94/5.38 import qualified Prelude; 12.94/5.38 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 12.94/5.38 12.94/5.38 instance (Eq a, Eq b) => Eq FiniteMap b a where { 12.94/5.38 } 12.94/5.38 elemFM :: Ord b => b -> FiniteMap b a -> Bool; 12.94/5.38 elemFM key fm = elemFM0 (lookupFM fm key); 12.94/5.38 12.94/5.38 elemFM0 Nothing = False; 12.94/5.38 elemFM0 (Just elt) = True; 12.94/5.38 12.94/5.38 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 12.94/5.38 lookupFM EmptyFM key = Nothing; 12.94/5.38 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 12.94/5.38 | key_to_find > key = lookupFM fm_r key_to_find 12.94/5.38 | otherwise = Just elt; 12.94/5.38 12.94/5.38 } 12.94/5.38 module Maybe where { 12.94/5.38 import qualified FiniteMap; 12.94/5.38 import qualified Main; 12.94/5.38 import qualified Prelude; 12.94/5.38 } 12.94/5.38 module Main where { 12.94/5.38 import qualified FiniteMap; 12.94/5.38 import qualified Maybe; 12.94/5.38 import qualified Prelude; 12.94/5.38 } 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (3) BR (EQUIVALENT) 12.94/5.38 Replaced joker patterns by fresh variables and removed binding patterns. 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (4) 12.94/5.38 Obligation: 12.94/5.38 mainModule Main 12.94/5.38 module FiniteMap where { 12.94/5.38 import qualified Main; 12.94/5.38 import qualified Maybe; 12.94/5.38 import qualified Prelude; 12.94/5.38 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 12.94/5.38 12.94/5.38 instance (Eq a, Eq b) => Eq FiniteMap a b where { 12.94/5.38 } 12.94/5.38 elemFM :: Ord b => b -> FiniteMap b a -> Bool; 12.94/5.38 elemFM key fm = elemFM0 (lookupFM fm key); 12.94/5.38 12.94/5.38 elemFM0 Nothing = False; 12.94/5.38 elemFM0 (Just elt) = True; 12.94/5.38 12.94/5.38 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 12.94/5.38 lookupFM EmptyFM key = Nothing; 12.94/5.38 lookupFM (Branch key elt vy fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 12.94/5.38 | key_to_find > key = lookupFM fm_r key_to_find 12.94/5.38 | otherwise = Just elt; 12.94/5.38 12.94/5.38 } 12.94/5.38 module Maybe where { 12.94/5.38 import qualified FiniteMap; 12.94/5.38 import qualified Main; 12.94/5.38 import qualified Prelude; 12.94/5.38 } 12.94/5.38 module Main where { 12.94/5.38 import qualified FiniteMap; 12.94/5.38 import qualified Maybe; 12.94/5.38 import qualified Prelude; 12.94/5.38 } 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (5) COR (EQUIVALENT) 12.94/5.38 Cond Reductions: 12.94/5.38 The following Function with conditions 12.94/5.38 "undefined |Falseundefined; 12.94/5.38 " 12.94/5.38 is transformed to 12.94/5.38 "undefined = undefined1; 12.94/5.38 " 12.94/5.38 "undefined0 True = undefined; 12.94/5.38 " 12.94/5.38 "undefined1 = undefined0 False; 12.94/5.38 " 12.94/5.38 The following Function with conditions 12.94/5.38 "lookupFM EmptyFM key = Nothing; 12.94/5.38 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; 12.94/5.38 " 12.94/5.38 is transformed to 12.94/5.38 "lookupFM EmptyFM key = lookupFM4 EmptyFM key; 12.94/5.38 lookupFM (Branch key elt vy fm_l fm_r) key_to_find = lookupFM3 (Branch key elt vy fm_l fm_r) key_to_find; 12.94/5.38 " 12.94/5.38 "lookupFM0 key elt vy fm_l fm_r key_to_find True = Just elt; 12.94/5.38 " 12.94/5.38 "lookupFM1 key elt vy fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 12.94/5.38 lookupFM1 key elt vy fm_l fm_r key_to_find False = lookupFM0 key elt vy fm_l fm_r key_to_find otherwise; 12.94/5.38 " 12.94/5.38 "lookupFM2 key elt vy fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 12.94/5.38 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); 12.94/5.38 " 12.94/5.38 "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); 12.94/5.38 " 12.94/5.38 "lookupFM4 EmptyFM key = Nothing; 12.94/5.38 lookupFM4 wv ww = lookupFM3 wv ww; 12.94/5.38 " 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (6) 12.94/5.38 Obligation: 12.94/5.38 mainModule Main 12.94/5.38 module FiniteMap where { 12.94/5.38 import qualified Main; 12.94/5.38 import qualified Maybe; 12.94/5.38 import qualified Prelude; 12.94/5.38 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 12.94/5.38 12.94/5.38 instance (Eq a, Eq b) => Eq FiniteMap a b where { 12.94/5.38 } 12.94/5.38 elemFM :: Ord b => b -> FiniteMap b a -> Bool; 12.94/5.38 elemFM key fm = elemFM0 (lookupFM fm key); 12.94/5.38 12.94/5.38 elemFM0 Nothing = False; 12.94/5.38 elemFM0 (Just elt) = True; 12.94/5.38 12.94/5.38 lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b; 12.94/5.38 lookupFM EmptyFM key = lookupFM4 EmptyFM key; 12.94/5.38 lookupFM (Branch key elt vy fm_l fm_r) key_to_find = lookupFM3 (Branch key elt vy fm_l fm_r) key_to_find; 12.94/5.38 12.94/5.38 lookupFM0 key elt vy fm_l fm_r key_to_find True = Just elt; 12.94/5.38 12.94/5.38 lookupFM1 key elt vy fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 12.94/5.38 lookupFM1 key elt vy fm_l fm_r key_to_find False = lookupFM0 key elt vy fm_l fm_r key_to_find otherwise; 12.94/5.38 12.94/5.38 lookupFM2 key elt vy fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 12.94/5.38 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); 12.94/5.38 12.94/5.38 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); 12.94/5.38 12.94/5.38 lookupFM4 EmptyFM key = Nothing; 12.94/5.38 lookupFM4 wv ww = lookupFM3 wv ww; 12.94/5.38 12.94/5.38 } 12.94/5.38 module Maybe where { 12.94/5.38 import qualified FiniteMap; 12.94/5.38 import qualified Main; 12.94/5.38 import qualified Prelude; 12.94/5.38 } 12.94/5.38 module Main where { 12.94/5.38 import qualified FiniteMap; 12.94/5.38 import qualified Maybe; 12.94/5.38 import qualified Prelude; 12.94/5.38 } 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (7) Narrow (SOUND) 12.94/5.38 Haskell To QDPs 12.94/5.38 12.94/5.38 digraph dp_graph { 12.94/5.38 node [outthreshold=100, inthreshold=100];1[label="FiniteMap.elemFM",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 12.94/5.38 3[label="FiniteMap.elemFM wx3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 12.94/5.38 4[label="FiniteMap.elemFM wx3 wx4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 12.94/5.38 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]; 12.94/5.38 759 -> 6[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 760 -> 7[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 6[label="FiniteMap.elemFM0 (FiniteMap.lookupFM FiniteMap.EmptyFM wx3)",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3]; 12.94/5.38 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]; 12.94/5.38 8[label="FiniteMap.elemFM0 (FiniteMap.lookupFM4 FiniteMap.EmptyFM wx3)",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3]; 12.94/5.38 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]; 12.94/5.38 10[label="FiniteMap.elemFM0 Nothing",fontsize=16,color="black",shape="box"];10 -> 12[label="",style="solid", color="black", weight=3]; 12.94/5.38 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.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 761 -> 15[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 762 -> 16[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 763 -> 18[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 764[label="wx30/Zero",fontsize=10,color="white",style="solid",shape="box"];17 -> 764[label="",style="solid", color="burlywood", weight=9]; 12.94/5.38 764 -> 19[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 765 -> 20[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 766[label="wx400/Zero",fontsize=10,color="white",style="solid",shape="box"];18 -> 766[label="",style="solid", color="burlywood", weight=9]; 12.94/5.38 766 -> 21[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 767 -> 22[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 768[label="wx400/Zero",fontsize=10,color="white",style="solid",shape="box"];19 -> 768[label="",style="solid", color="burlywood", weight=9]; 12.94/5.38 768 -> 23[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 24 -> 323[label="",style="dashed", color="red", weight=0]; 12.94/5.38 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]; 12.94/5.38 24 -> 325[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 24 -> 326[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 24 -> 327[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 24 -> 328[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 24 -> 329[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 24 -> 330[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 24 -> 331[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 769 -> 404[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 770[label="wx32/Zero",fontsize=10,color="white",style="solid",shape="box"];323 -> 770[label="",style="solid", color="burlywood", weight=9]; 12.94/5.38 770 -> 405[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 771 -> 406[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 772[label="wx33/Zero",fontsize=10,color="white",style="solid",shape="box"];404 -> 772[label="",style="solid", color="burlywood", weight=9]; 12.94/5.38 772 -> 407[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 773 -> 408[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 774[label="wx33/Zero",fontsize=10,color="white",style="solid",shape="box"];405 -> 774[label="",style="solid", color="burlywood", weight=9]; 12.94/5.38 774 -> 409[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 38 -> 5[label="",style="dashed", color="red", weight=0]; 12.94/5.38 38[label="FiniteMap.elemFM0 (FiniteMap.lookupFM wx43 (Char Zero))",fontsize=16,color="magenta"];38 -> 45[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 38 -> 46[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 410 -> 323[label="",style="dashed", color="red", weight=0]; 12.94/5.38 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]; 12.94/5.38 410 -> 415[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 418 -> 416[label="",style="dashed", color="red", weight=0]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 420 -> 5[label="",style="dashed", color="red", weight=0]; 12.94/5.38 420[label="FiniteMap.elemFM0 (FiniteMap.lookupFM wx29 (Char (Succ wx31)))",fontsize=16,color="magenta"];420 -> 422[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 420 -> 423[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 92 -> 5[label="",style="dashed", color="red", weight=0]; 12.94/5.38 92[label="FiniteMap.elemFM0 (FiniteMap.lookupFM wx44 (Char (Succ wx300)))",fontsize=16,color="magenta"];92 -> 104[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 92 -> 105[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 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]; 12.94/5.38 425 -> 648[label="",style="dashed", color="red", weight=0]; 12.94/5.38 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]; 12.94/5.38 425 -> 650[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 425 -> 651[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 425 -> 652[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 425 -> 653[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 425 -> 654[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 425 -> 655[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 425 -> 656[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 775 -> 737[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 776[label="wx79/Zero",fontsize=10,color="white",style="solid",shape="box"];648 -> 776[label="",style="solid", color="burlywood", weight=9]; 12.94/5.38 776 -> 738[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 116[label="FiniteMap.elemFM0 (Just wx41)",fontsize=16,color="black",shape="triangle"];116 -> 128[label="",style="solid", color="black", weight=3]; 12.94/5.38 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]; 12.94/5.38 777 -> 739[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 778[label="wx80/Zero",fontsize=10,color="white",style="solid",shape="box"];737 -> 778[label="",style="solid", color="burlywood", weight=9]; 12.94/5.38 778 -> 740[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 779 -> 741[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 780[label="wx80/Zero",fontsize=10,color="white",style="solid",shape="box"];738 -> 780[label="",style="solid", color="burlywood", weight=9]; 12.94/5.38 780 -> 742[label="",style="solid", color="burlywood", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 743 -> 648[label="",style="dashed", color="red", weight=0]; 12.94/5.38 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]; 12.94/5.38 743 -> 748[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 751 -> 750[label="",style="dashed", color="red", weight=0]; 12.94/5.38 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]; 12.94/5.38 752[label="FiniteMap.elemFM0 (FiniteMap.lookupFM wx77 (Char (Succ wx78)))",fontsize=16,color="magenta"];752 -> 754[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 752 -> 755[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 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]; 12.94/5.38 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]; 12.94/5.38 757 -> 116[label="",style="dashed", color="red", weight=0]; 12.94/5.38 757[label="FiniteMap.elemFM0 (Just wx74)",fontsize=16,color="magenta"];757 -> 758[label="",style="dashed", color="magenta", weight=3]; 12.94/5.38 758[label="wx74",fontsize=16,color="green",shape="box"];} 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (8) 12.94/5.38 Obligation: 12.94/5.38 Q DP problem: 12.94/5.38 The TRS P consists of the following rules: 12.94/5.38 12.94/5.38 new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Succ(wx330), h) -> new_elemFM01(wx29, Char(Succ(wx31)), h) 12.94/5.38 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) 12.94/5.38 new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Zero, ba) -> new_elemFM01(wx77, Char(Succ(wx78)), ba) 12.94/5.38 new_elemFM01(Branch(Char(Zero), wx41, wx42, wx43, wx44), Char(Succ(wx300)), bb) -> new_elemFM01(wx44, Char(Succ(wx300)), bb) 12.94/5.38 new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Zero, h) -> new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h) 12.94/5.38 new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h) -> new_elemFM00(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx31), Succ(wx26), h) 12.94/5.38 new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx320), Succ(wx330), h) -> new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, wx320, wx330, h) 12.94/5.38 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) 12.94/5.38 new_elemFM01(Branch(Char(Succ(wx4000)), wx41, wx42, wx43, wx44), Char(Zero), bb) -> new_elemFM01(wx43, Char(Zero), bb) 12.94/5.38 new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Succ(wx800), ba) -> new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, wx790, wx800, ba) 12.94/5.38 12.94/5.38 R is empty. 12.94/5.38 Q is empty. 12.94/5.38 We have to consider all minimal (P,Q,R)-chains. 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (9) DependencyGraphProof (EQUIVALENT) 12.94/5.38 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (10) 12.94/5.38 Complex Obligation (AND) 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (11) 12.94/5.38 Obligation: 12.94/5.38 Q DP problem: 12.94/5.38 The TRS P consists of the following rules: 12.94/5.38 12.94/5.38 new_elemFM01(Branch(Char(Succ(wx4000)), wx41, wx42, wx43, wx44), Char(Zero), bb) -> new_elemFM01(wx43, Char(Zero), bb) 12.94/5.38 12.94/5.38 R is empty. 12.94/5.38 Q is empty. 12.94/5.38 We have to consider all minimal (P,Q,R)-chains. 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (12) QDPSizeChangeProof (EQUIVALENT) 12.94/5.38 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. 12.94/5.38 12.94/5.38 From the DPs we obtained the following set of size-change graphs: 12.94/5.38 *new_elemFM01(Branch(Char(Succ(wx4000)), wx41, wx42, wx43, wx44), Char(Zero), bb) -> new_elemFM01(wx43, Char(Zero), bb) 12.94/5.38 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 12.94/5.38 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (13) 12.94/5.38 YES 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (14) 12.94/5.38 Obligation: 12.94/5.38 Q DP problem: 12.94/5.38 The TRS P consists of the following rules: 12.94/5.38 12.94/5.38 new_elemFM01(Branch(Char(Zero), wx41, wx42, wx43, wx44), Char(Succ(wx300)), bb) -> new_elemFM01(wx44, Char(Succ(wx300)), bb) 12.94/5.38 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) 12.94/5.38 new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Succ(wx330), h) -> new_elemFM01(wx29, Char(Succ(wx31)), h) 12.94/5.38 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) 12.94/5.38 new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Succ(wx800), ba) -> new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, wx790, wx800, ba) 12.94/5.38 new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Zero, ba) -> new_elemFM01(wx77, Char(Succ(wx78)), ba) 12.94/5.38 new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Zero, h) -> new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h) 12.94/5.38 new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h) -> new_elemFM00(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx31), Succ(wx26), h) 12.94/5.38 new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx320), Succ(wx330), h) -> new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, wx320, wx330, h) 12.94/5.38 12.94/5.38 R is empty. 12.94/5.38 Q is empty. 12.94/5.38 We have to consider all minimal (P,Q,R)-chains. 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (15) QDPSizeChangeProof (EQUIVALENT) 12.94/5.38 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. 12.94/5.38 12.94/5.38 From the DPs we obtained the following set of size-change graphs: 12.94/5.38 *new_elemFM01(Branch(Char(Zero), wx41, wx42, wx43, wx44), Char(Succ(wx300)), bb) -> new_elemFM01(wx44, Char(Succ(wx300)), bb) 12.94/5.38 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 12.94/5.38 12.94/5.38 12.94/5.38 *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) 12.94/5.38 The graph contains the following edges 1 > 1, 1 > 2, 1 > 3, 1 > 4, 1 > 5, 2 > 6, 2 > 7, 1 > 8, 3 >= 9 12.94/5.38 12.94/5.38 12.94/5.38 *new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Succ(wx330), h) -> new_elemFM01(wx29, Char(Succ(wx31)), h) 12.94/5.38 The graph contains the following edges 4 >= 1, 9 >= 3 12.94/5.38 12.94/5.38 12.94/5.38 *new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Zero, ba) -> new_elemFM01(wx77, Char(Succ(wx78)), ba) 12.94/5.38 The graph contains the following edges 5 >= 1, 9 >= 3 12.94/5.38 12.94/5.38 12.94/5.38 *new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx320), Succ(wx330), h) -> new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, wx320, wx330, h) 12.94/5.38 The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 7 > 7, 8 > 8, 9 >= 9 12.94/5.38 12.94/5.38 12.94/5.38 *new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Succ(wx800), ba) -> new_elemFM00(wx73, wx74, wx75, wx76, wx77, wx78, wx790, wx800, ba) 12.94/5.38 The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 7 > 7, 8 > 8, 9 >= 9 12.94/5.38 12.94/5.38 12.94/5.38 *new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h) -> new_elemFM00(wx26, wx27, wx28, wx29, wx30, wx31, Succ(wx31), Succ(wx26), h) 12.94/5.38 The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 7 >= 9 12.94/5.38 12.94/5.38 12.94/5.38 *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) 12.94/5.38 The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 9 >= 9 12.94/5.38 12.94/5.38 12.94/5.38 *new_elemFM0(wx26, wx27, wx28, wx29, wx30, wx31, Zero, Zero, h) -> new_elemFM02(wx26, wx27, wx28, wx29, wx30, wx31, h) 12.94/5.38 The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5, 6 >= 6, 9 >= 7 12.94/5.38 12.94/5.38 12.94/5.38 ---------------------------------------- 12.94/5.38 12.94/5.38 (16) 12.94/5.38 YES 13.09/5.42 EOF