10.74/4.58 YES 13.73/5.32 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 13.73/5.32 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.73/5.32 13.73/5.32 13.73/5.32 H-Termination with start terms of the given HASKELL could be proven: 13.73/5.32 13.73/5.32 (0) HASKELL 13.73/5.32 (1) LR [EQUIVALENT, 0 ms] 13.73/5.32 (2) HASKELL 13.73/5.32 (3) CR [EQUIVALENT, 0 ms] 13.73/5.32 (4) HASKELL 13.73/5.32 (5) IFR [EQUIVALENT, 0 ms] 13.73/5.32 (6) HASKELL 13.73/5.32 (7) BR [EQUIVALENT, 0 ms] 13.73/5.32 (8) HASKELL 13.73/5.32 (9) COR [EQUIVALENT, 13 ms] 13.73/5.32 (10) HASKELL 13.73/5.32 (11) NumRed [SOUND, 0 ms] 13.73/5.32 (12) HASKELL 13.73/5.32 (13) Narrow [SOUND, 0 ms] 13.73/5.32 (14) QDP 13.73/5.32 (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.73/5.32 (16) YES 13.73/5.32 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (0) 13.73/5.32 Obligation: 13.73/5.32 mainModule Main 13.73/5.32 module Maybe where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 module List where { 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 elemIndices :: Eq a => a -> [a] -> [Int]; 13.73/5.32 elemIndices x = findIndices (== x); 13.73/5.32 13.73/5.32 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.73/5.32 findIndices p xs = concatMap (\vv1 ->case vv1 of { 13.73/5.32 (x,i)-> if p x then i : [] else []; 13.73/5.32 _-> []; 13.73/5.32 } ) (zip xs (enumFrom 0)); 13.73/5.32 13.73/5.32 } 13.73/5.32 module Main where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (1) LR (EQUIVALENT) 13.73/5.32 Lambda Reductions: 13.73/5.32 The following Lambda expression 13.73/5.32 "\ab->(a,b)" 13.73/5.32 is transformed to 13.73/5.32 "zip0 a b = (a,b); 13.73/5.32 " 13.73/5.32 The following Lambda expression 13.73/5.32 "\vv1->case vv1 of { 13.73/5.32 (x,i) -> if p x then i : [] else []; 13.73/5.32 _ -> []} 13.73/5.32 " 13.73/5.32 is transformed to 13.73/5.32 "findIndices0 p vv1 = case vv1 of { 13.73/5.32 (x,i) -> if p x then i : [] else []; 13.73/5.32 _ -> []} 13.73/5.32 ; 13.73/5.32 " 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (2) 13.73/5.32 Obligation: 13.73/5.32 mainModule Main 13.73/5.32 module Maybe where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 module List where { 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 elemIndices :: Eq a => a -> [a] -> [Int]; 13.73/5.32 elemIndices x = findIndices (== x); 13.73/5.32 13.73/5.32 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.73/5.32 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.73/5.32 13.73/5.32 findIndices0 p vv1 = case vv1 of { 13.73/5.32 (x,i)-> if p x then i : [] else []; 13.73/5.32 _-> []; 13.73/5.32 } ; 13.73/5.32 13.73/5.32 } 13.73/5.32 module Main where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (3) CR (EQUIVALENT) 13.73/5.32 Case Reductions: 13.73/5.32 The following Case expression 13.73/5.32 "case vv1 of { 13.73/5.32 (x,i) -> if p x then i : [] else []; 13.73/5.32 _ -> []} 13.73/5.32 " 13.73/5.32 is transformed to 13.73/5.32 "findIndices00 p (x,i) = if p x then i : [] else []; 13.73/5.32 findIndices00 p _ = []; 13.73/5.32 " 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (4) 13.73/5.32 Obligation: 13.73/5.32 mainModule Main 13.73/5.32 module Maybe where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 module List where { 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 elemIndices :: Eq a => a -> [a] -> [Int]; 13.73/5.32 elemIndices x = findIndices (== x); 13.73/5.32 13.73/5.32 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.73/5.32 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.73/5.32 13.73/5.32 findIndices0 p vv1 = findIndices00 p vv1; 13.73/5.32 13.73/5.32 findIndices00 p (x,i) = if p x then i : [] else []; 13.73/5.32 findIndices00 p _ = []; 13.73/5.32 13.73/5.32 } 13.73/5.32 module Main where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (5) IFR (EQUIVALENT) 13.73/5.32 If Reductions: 13.73/5.32 The following If expression 13.73/5.32 "if p x then i : [] else []" 13.73/5.32 is transformed to 13.73/5.32 "findIndices000 i True = i : []; 13.73/5.32 findIndices000 i False = []; 13.73/5.32 " 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (6) 13.73/5.32 Obligation: 13.73/5.32 mainModule Main 13.73/5.32 module Maybe where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 module List where { 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 elemIndices :: Eq a => a -> [a] -> [Int]; 13.73/5.32 elemIndices x = findIndices (== x); 13.73/5.32 13.73/5.32 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.73/5.32 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.73/5.32 13.73/5.32 findIndices0 p vv1 = findIndices00 p vv1; 13.73/5.32 13.73/5.32 findIndices00 p (x,i) = findIndices000 i (p x); 13.73/5.32 findIndices00 p _ = []; 13.73/5.32 13.73/5.32 findIndices000 i True = i : []; 13.73/5.32 findIndices000 i False = []; 13.73/5.32 13.73/5.32 } 13.73/5.32 module Main where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (7) BR (EQUIVALENT) 13.73/5.32 Replaced joker patterns by fresh variables and removed binding patterns. 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (8) 13.73/5.32 Obligation: 13.73/5.32 mainModule Main 13.73/5.32 module Maybe where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 module List where { 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 elemIndices :: Eq a => a -> [a] -> [Int]; 13.73/5.32 elemIndices x = findIndices (== x); 13.73/5.32 13.73/5.32 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.73/5.32 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.73/5.32 13.73/5.32 findIndices0 p vv1 = findIndices00 p vv1; 13.73/5.32 13.73/5.32 findIndices00 p (x,i) = findIndices000 i (p x); 13.73/5.32 findIndices00 p wv = []; 13.73/5.32 13.73/5.32 findIndices000 i True = i : []; 13.73/5.32 findIndices000 i False = []; 13.73/5.32 13.73/5.32 } 13.73/5.32 module Main where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (9) COR (EQUIVALENT) 13.73/5.32 Cond Reductions: 13.73/5.32 The following Function with conditions 13.73/5.32 "undefined |Falseundefined; 13.73/5.32 " 13.73/5.32 is transformed to 13.73/5.32 "undefined = undefined1; 13.73/5.32 " 13.73/5.32 "undefined0 True = undefined; 13.73/5.32 " 13.73/5.32 "undefined1 = undefined0 False; 13.73/5.32 " 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (10) 13.73/5.32 Obligation: 13.73/5.32 mainModule Main 13.73/5.32 module Maybe where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 module List where { 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 elemIndices :: Eq a => a -> [a] -> [Int]; 13.73/5.32 elemIndices x = findIndices (== x); 13.73/5.32 13.73/5.32 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.73/5.32 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.73/5.32 13.73/5.32 findIndices0 p vv1 = findIndices00 p vv1; 13.73/5.32 13.73/5.32 findIndices00 p (x,i) = findIndices000 i (p x); 13.73/5.32 findIndices00 p wv = []; 13.73/5.32 13.73/5.32 findIndices000 i True = i : []; 13.73/5.32 findIndices000 i False = []; 13.73/5.32 13.73/5.32 } 13.73/5.32 module Main where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (11) NumRed (SOUND) 13.73/5.32 Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero. 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (12) 13.73/5.32 Obligation: 13.73/5.32 mainModule Main 13.73/5.32 module Maybe where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 module List where { 13.73/5.32 import qualified Main; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 elemIndices :: Eq a => a -> [a] -> [Int]; 13.73/5.32 elemIndices x = findIndices (== x); 13.73/5.32 13.73/5.32 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.73/5.32 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom (Pos Zero))); 13.73/5.32 13.73/5.32 findIndices0 p vv1 = findIndices00 p vv1; 13.73/5.32 13.73/5.32 findIndices00 p (x,i) = findIndices000 i (p x); 13.73/5.32 findIndices00 p wv = []; 13.73/5.32 13.73/5.32 findIndices000 i True = i : []; 13.73/5.32 findIndices000 i False = []; 13.73/5.32 13.73/5.32 } 13.73/5.32 module Main where { 13.73/5.32 import qualified List; 13.73/5.32 import qualified Maybe; 13.73/5.32 import qualified Prelude; 13.73/5.32 } 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (13) Narrow (SOUND) 13.73/5.32 Haskell To QDPs 13.73/5.32 13.73/5.32 digraph dp_graph { 13.73/5.32 node [outthreshold=100, inthreshold=100];1[label="List.elemIndices",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 13.73/5.32 3[label="List.elemIndices ww3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 13.73/5.32 4[label="List.elemIndices ww3 ww4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 13.73/5.32 5[label="List.findIndices (ww3 ==) ww4",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3]; 13.73/5.32 6[label="concatMap (List.findIndices0 (ww3 ==)) (zip ww4 (enumFrom (Pos Zero)))",fontsize=16,color="black",shape="box"];6 -> 7[label="",style="solid", color="black", weight=3]; 13.73/5.32 7[label="concat . map (List.findIndices0 (ww3 ==))",fontsize=16,color="black",shape="box"];7 -> 8[label="",style="solid", color="black", weight=3]; 13.73/5.32 8[label="concat (map (List.findIndices0 (ww3 ==)) (zip ww4 (enumFrom (Pos Zero))))",fontsize=16,color="black",shape="box"];8 -> 9[label="",style="solid", color="black", weight=3]; 13.73/5.32 9[label="foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zip ww4 (enumFrom (Pos Zero))))",fontsize=16,color="black",shape="box"];9 -> 10[label="",style="solid", color="black", weight=3]; 13.73/5.32 10[label="foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zipWith zip0 ww4 (enumFrom (Pos Zero))))",fontsize=16,color="burlywood",shape="box"];98[label="ww4/ww40 : ww41",fontsize=10,color="white",style="solid",shape="box"];10 -> 98[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 98 -> 11[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 99[label="ww4/[]",fontsize=10,color="white",style="solid",shape="box"];10 -> 99[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 99 -> 12[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 11[label="foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zipWith zip0 (ww40 : ww41) (enumFrom (Pos Zero))))",fontsize=16,color="black",shape="box"];11 -> 13[label="",style="solid", color="black", weight=3]; 13.73/5.32 12[label="foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zipWith zip0 [] (enumFrom (Pos Zero))))",fontsize=16,color="black",shape="box"];12 -> 14[label="",style="solid", color="black", weight=3]; 13.73/5.32 13[label="foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zipWith zip0 (ww40 : ww41) (numericEnumFrom (Pos Zero))))",fontsize=16,color="black",shape="box"];13 -> 15[label="",style="solid", color="black", weight=3]; 13.73/5.32 14[label="foldr (++) [] (map (List.findIndices0 (ww3 ==)) [])",fontsize=16,color="black",shape="triangle"];14 -> 16[label="",style="solid", color="black", weight=3]; 13.73/5.32 15[label="foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zipWith zip0 (ww40 : ww41) (Pos Zero : (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];15 -> 17[label="",style="solid", color="black", weight=3]; 13.73/5.32 16[label="foldr (++) [] []",fontsize=16,color="black",shape="box"];16 -> 18[label="",style="solid", color="black", weight=3]; 13.73/5.32 17[label="foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zip0 ww40 (Pos Zero) : zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];17 -> 19[label="",style="solid", color="black", weight=3]; 13.73/5.32 18[label="[]",fontsize=16,color="green",shape="box"];19[label="foldr (++) [] (List.findIndices0 (ww3 ==) (zip0 ww40 (Pos Zero)) : map (List.findIndices0 (ww3 ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];19 -> 20[label="",style="solid", color="black", weight=3]; 13.73/5.32 20[label="(++) List.findIndices0 (ww3 ==) (zip0 ww40 (Pos Zero)) foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];20 -> 21[label="",style="solid", color="black", weight=3]; 13.73/5.32 21[label="(++) List.findIndices00 (ww3 ==) (zip0 ww40 (Pos Zero)) foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];21 -> 22[label="",style="solid", color="black", weight=3]; 13.73/5.32 22[label="(++) List.findIndices00 (ww3 ==) (ww40,Pos Zero) foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];22 -> 23[label="",style="solid", color="black", weight=3]; 13.73/5.32 23[label="(++) List.findIndices000 (Pos Zero) (ww3 == ww40) foldr (++) [] (map (List.findIndices0 (ww3 ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="burlywood",shape="box"];100[label="ww3/()",fontsize=10,color="white",style="solid",shape="box"];23 -> 100[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 100 -> 24[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 24[label="(++) List.findIndices000 (Pos Zero) (() == ww40) foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="burlywood",shape="box"];101[label="ww40/()",fontsize=10,color="white",style="solid",shape="box"];24 -> 101[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 101 -> 25[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 25[label="(++) List.findIndices000 (Pos Zero) (() == ()) foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];25 -> 26[label="",style="solid", color="black", weight=3]; 13.73/5.32 26[label="(++) List.findIndices000 (Pos Zero) True foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];26 -> 27[label="",style="solid", color="black", weight=3]; 13.73/5.32 27[label="(++) (Pos Zero : []) foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];27 -> 28[label="",style="solid", color="black", weight=3]; 13.73/5.32 28[label="Pos Zero : [] ++ foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="green",shape="box"];28 -> 29[label="",style="dashed", color="green", weight=3]; 13.73/5.32 29 -> 55[label="",style="dashed", color="red", weight=0]; 13.73/5.32 29[label="[] ++ foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="magenta"];29 -> 56[label="",style="dashed", color="magenta", weight=3]; 13.73/5.32 29 -> 57[label="",style="dashed", color="magenta", weight=3]; 13.73/5.32 56[label="Zero",fontsize=16,color="green",shape="box"];57[label="ww41",fontsize=16,color="green",shape="box"];55[label="[] ++ foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww411 (numericEnumFrom $! Pos ww5 + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="triangle"];55 -> 59[label="",style="solid", color="black", weight=3]; 13.73/5.32 59[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww411 (numericEnumFrom $! Pos ww5 + fromInt (Pos (Succ Zero)))))",fontsize=16,color="burlywood",shape="triangle"];102[label="ww411/ww4110 : ww4111",fontsize=10,color="white",style="solid",shape="box"];59 -> 102[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 102 -> 60[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 103[label="ww411/[]",fontsize=10,color="white",style="solid",shape="box"];59 -> 103[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 103 -> 61[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 60[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 (ww4110 : ww4111) (numericEnumFrom $! Pos ww5 + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];60 -> 62[label="",style="solid", color="black", weight=3]; 13.73/5.32 61[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 [] (numericEnumFrom $! Pos ww5 + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];61 -> 63[label="",style="solid", color="black", weight=3]; 13.73/5.32 62[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 (ww4110 : ww4111) (Pos ww5 + fromInt (Pos (Succ Zero)) `seq` numericEnumFrom (Pos ww5 + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];62 -> 64[label="",style="solid", color="black", weight=3]; 13.73/5.32 63 -> 14[label="",style="dashed", color="red", weight=0]; 13.73/5.32 63[label="foldr (++) [] (map (List.findIndices0 (() ==)) [])",fontsize=16,color="magenta"];63 -> 65[label="",style="dashed", color="magenta", weight=3]; 13.73/5.32 64[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 (ww4110 : ww4111) (enforceWHNF (WHNF (Pos ww5 + fromInt (Pos (Succ Zero)))) (numericEnumFrom (Pos ww5 + fromInt (Pos (Succ Zero)))))))",fontsize=16,color="black",shape="box"];64 -> 66[label="",style="solid", color="black", weight=3]; 13.73/5.32 65[label="()",fontsize=16,color="green",shape="box"];66[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 (ww4110 : ww4111) (enforceWHNF (WHNF (primPlusInt (Pos ww5) (fromInt (Pos (Succ Zero))))) (numericEnumFrom (primPlusInt (Pos ww5) (fromInt (Pos (Succ Zero))))))))",fontsize=16,color="black",shape="box"];66 -> 67[label="",style="solid", color="black", weight=3]; 13.73/5.32 67[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 (ww4110 : ww4111) (enforceWHNF (WHNF (primPlusInt (Pos ww5) (Pos (Succ Zero)))) (numericEnumFrom (primPlusInt (Pos ww5) (Pos (Succ Zero)))))))",fontsize=16,color="black",shape="box"];67 -> 68[label="",style="solid", color="black", weight=3]; 13.73/5.32 68[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 (ww4110 : ww4111) (enforceWHNF (WHNF (Pos (primPlusNat ww5 (Succ Zero)))) (numericEnumFrom (Pos (primPlusNat ww5 (Succ Zero)))))))",fontsize=16,color="black",shape="box"];68 -> 69[label="",style="solid", color="black", weight=3]; 13.73/5.32 69[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 (ww4110 : ww4111) (numericEnumFrom (Pos (primPlusNat ww5 (Succ Zero))))))",fontsize=16,color="black",shape="box"];69 -> 70[label="",style="solid", color="black", weight=3]; 13.73/5.32 70[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 (ww4110 : ww4111) (Pos (primPlusNat ww5 (Succ Zero)) : (numericEnumFrom $! Pos (primPlusNat ww5 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];70 -> 71[label="",style="solid", color="black", weight=3]; 13.73/5.32 71[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zip0 ww4110 (Pos (primPlusNat ww5 (Succ Zero))) : zipWith zip0 ww4111 (numericEnumFrom $! Pos (primPlusNat ww5 (Succ Zero)) + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];71 -> 72[label="",style="solid", color="black", weight=3]; 13.73/5.32 72[label="foldr (++) [] (List.findIndices0 (() ==) (zip0 ww4110 (Pos (primPlusNat ww5 (Succ Zero)))) : map (List.findIndices0 (() ==)) (zipWith zip0 ww4111 (numericEnumFrom $! Pos (primPlusNat ww5 (Succ Zero)) + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];72 -> 73[label="",style="solid", color="black", weight=3]; 13.73/5.32 73 -> 74[label="",style="dashed", color="red", weight=0]; 13.73/5.32 73[label="(++) List.findIndices0 (() ==) (zip0 ww4110 (Pos (primPlusNat ww5 (Succ Zero)))) foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww4111 (numericEnumFrom $! Pos (primPlusNat ww5 (Succ Zero)) + fromInt (Pos (Succ Zero)))))",fontsize=16,color="magenta"];73 -> 75[label="",style="dashed", color="magenta", weight=3]; 13.73/5.32 75 -> 59[label="",style="dashed", color="red", weight=0]; 13.73/5.32 75[label="foldr (++) [] (map (List.findIndices0 (() ==)) (zipWith zip0 ww4111 (numericEnumFrom $! Pos (primPlusNat ww5 (Succ Zero)) + fromInt (Pos (Succ Zero)))))",fontsize=16,color="magenta"];75 -> 76[label="",style="dashed", color="magenta", weight=3]; 13.73/5.32 75 -> 77[label="",style="dashed", color="magenta", weight=3]; 13.73/5.32 74[label="(++) List.findIndices0 (() ==) (zip0 ww4110 (Pos (primPlusNat ww5 (Succ Zero)))) ww6",fontsize=16,color="black",shape="triangle"];74 -> 78[label="",style="solid", color="black", weight=3]; 13.73/5.32 76[label="primPlusNat ww5 (Succ Zero)",fontsize=16,color="burlywood",shape="triangle"];104[label="ww5/Succ ww50",fontsize=10,color="white",style="solid",shape="box"];76 -> 104[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 104 -> 79[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 105[label="ww5/Zero",fontsize=10,color="white",style="solid",shape="box"];76 -> 105[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 105 -> 80[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 77[label="ww4111",fontsize=16,color="green",shape="box"];78 -> 81[label="",style="dashed", color="red", weight=0]; 13.73/5.32 78[label="(++) List.findIndices00 (() ==) (zip0 ww4110 (Pos (primPlusNat ww5 (Succ Zero)))) ww6",fontsize=16,color="magenta"];78 -> 82[label="",style="dashed", color="magenta", weight=3]; 13.73/5.32 79[label="primPlusNat (Succ ww50) (Succ Zero)",fontsize=16,color="black",shape="box"];79 -> 83[label="",style="solid", color="black", weight=3]; 13.73/5.32 80[label="primPlusNat Zero (Succ Zero)",fontsize=16,color="black",shape="box"];80 -> 84[label="",style="solid", color="black", weight=3]; 13.73/5.32 82 -> 76[label="",style="dashed", color="red", weight=0]; 13.73/5.32 82[label="primPlusNat ww5 (Succ Zero)",fontsize=16,color="magenta"];81[label="(++) List.findIndices00 (() ==) (zip0 ww4110 (Pos ww7)) ww6",fontsize=16,color="black",shape="triangle"];81 -> 85[label="",style="solid", color="black", weight=3]; 13.73/5.32 83[label="Succ (Succ (primPlusNat ww50 Zero))",fontsize=16,color="green",shape="box"];83 -> 86[label="",style="dashed", color="green", weight=3]; 13.73/5.32 84[label="Succ Zero",fontsize=16,color="green",shape="box"];85[label="(++) List.findIndices00 (() ==) (ww4110,Pos ww7) ww6",fontsize=16,color="black",shape="box"];85 -> 87[label="",style="solid", color="black", weight=3]; 13.73/5.32 86[label="primPlusNat ww50 Zero",fontsize=16,color="burlywood",shape="box"];106[label="ww50/Succ ww500",fontsize=10,color="white",style="solid",shape="box"];86 -> 106[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 106 -> 88[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 107[label="ww50/Zero",fontsize=10,color="white",style="solid",shape="box"];86 -> 107[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 107 -> 89[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 87[label="(++) List.findIndices000 (Pos ww7) (() == ww4110) ww6",fontsize=16,color="burlywood",shape="box"];108[label="ww4110/()",fontsize=10,color="white",style="solid",shape="box"];87 -> 108[label="",style="solid", color="burlywood", weight=9]; 13.73/5.32 108 -> 90[label="",style="solid", color="burlywood", weight=3]; 13.73/5.32 88[label="primPlusNat (Succ ww500) Zero",fontsize=16,color="black",shape="box"];88 -> 91[label="",style="solid", color="black", weight=3]; 13.73/5.32 89[label="primPlusNat Zero Zero",fontsize=16,color="black",shape="box"];89 -> 92[label="",style="solid", color="black", weight=3]; 13.73/5.32 90[label="(++) List.findIndices000 (Pos ww7) (() == ()) ww6",fontsize=16,color="black",shape="box"];90 -> 93[label="",style="solid", color="black", weight=3]; 13.73/5.32 91[label="Succ ww500",fontsize=16,color="green",shape="box"];92[label="Zero",fontsize=16,color="green",shape="box"];93[label="(++) List.findIndices000 (Pos ww7) True ww6",fontsize=16,color="black",shape="box"];93 -> 94[label="",style="solid", color="black", weight=3]; 13.73/5.32 94[label="(++) (Pos ww7 : []) ww6",fontsize=16,color="black",shape="box"];94 -> 95[label="",style="solid", color="black", weight=3]; 13.73/5.32 95[label="Pos ww7 : [] ++ ww6",fontsize=16,color="green",shape="box"];95 -> 96[label="",style="dashed", color="green", weight=3]; 13.73/5.32 96[label="[] ++ ww6",fontsize=16,color="black",shape="box"];96 -> 97[label="",style="solid", color="black", weight=3]; 13.73/5.32 97[label="ww6",fontsize=16,color="green",shape="box"];} 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (14) 13.73/5.32 Obligation: 13.73/5.32 Q DP problem: 13.73/5.32 The TRS P consists of the following rules: 13.73/5.32 13.73/5.32 new_foldr(:(ww4110, ww4111), ww5) -> new_foldr(ww4111, new_primPlusNat(ww5)) 13.73/5.32 13.73/5.32 The TRS R consists of the following rules: 13.73/5.32 13.73/5.32 new_primPlusNat(Succ(ww50)) -> Succ(Succ(new_primPlusNat0(ww50))) 13.73/5.32 new_primPlusNat(Zero) -> Succ(Zero) 13.73/5.32 new_primPlusNat0(Succ(ww500)) -> Succ(ww500) 13.73/5.32 new_primPlusNat0(Zero) -> Zero 13.73/5.32 13.73/5.32 The set Q consists of the following terms: 13.73/5.32 13.73/5.32 new_primPlusNat0(Succ(x0)) 13.73/5.32 new_primPlusNat0(Zero) 13.73/5.32 new_primPlusNat(Succ(x0)) 13.73/5.32 new_primPlusNat(Zero) 13.73/5.32 13.73/5.32 We have to consider all minimal (P,Q,R)-chains. 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (15) QDPSizeChangeProof (EQUIVALENT) 13.73/5.32 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 13.73/5.32 13.73/5.32 From the DPs we obtained the following set of size-change graphs: 13.73/5.32 *new_foldr(:(ww4110, ww4111), ww5) -> new_foldr(ww4111, new_primPlusNat(ww5)) 13.73/5.32 The graph contains the following edges 1 > 1 13.73/5.32 13.73/5.32 13.73/5.32 ---------------------------------------- 13.73/5.32 13.73/5.32 (16) 13.73/5.32 YES 13.73/5.37 EOF