10.96/4.53 YES 13.55/5.24 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 13.55/5.24 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.55/5.24 13.55/5.24 13.55/5.24 H-Termination with start terms of the given HASKELL could be proven: 13.55/5.24 13.55/5.24 (0) HASKELL 13.55/5.24 (1) LR [EQUIVALENT, 0 ms] 13.55/5.24 (2) HASKELL 13.55/5.24 (3) CR [EQUIVALENT, 0 ms] 13.55/5.24 (4) HASKELL 13.55/5.24 (5) IFR [EQUIVALENT, 0 ms] 13.55/5.24 (6) HASKELL 13.55/5.24 (7) BR [EQUIVALENT, 0 ms] 13.55/5.24 (8) HASKELL 13.55/5.24 (9) COR [EQUIVALENT, 18 ms] 13.55/5.24 (10) HASKELL 13.55/5.24 (11) NumRed [SOUND, 0 ms] 13.55/5.24 (12) HASKELL 13.55/5.24 (13) Narrow [SOUND, 0 ms] 13.55/5.24 (14) QDP 13.55/5.24 (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.55/5.24 (16) YES 13.55/5.24 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (0) 13.55/5.24 Obligation: 13.55/5.24 mainModule Main 13.55/5.24 module Maybe where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Prelude; 13.55/5.24 listToMaybe :: [a] -> Maybe a; 13.55/5.24 listToMaybe [] = Nothing; 13.55/5.24 listToMaybe (a : _) = Just a; 13.55/5.24 13.55/5.24 } 13.55/5.24 module List where { 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 findIndex :: (a -> Bool) -> [a] -> Maybe Int; 13.55/5.24 findIndex p = Maybe.listToMaybe . findIndices p; 13.55/5.24 13.55/5.24 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.55/5.24 findIndices p xs = concatMap (\vv1 ->case vv1 of { 13.55/5.24 (x,i)-> if p x then i : [] else []; 13.55/5.24 _-> []; 13.55/5.24 } ) (zip xs (enumFrom 0)); 13.55/5.24 13.55/5.24 } 13.55/5.24 module Main where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 } 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (1) LR (EQUIVALENT) 13.55/5.24 Lambda Reductions: 13.55/5.24 The following Lambda expression 13.55/5.24 "\ab->(a,b)" 13.55/5.24 is transformed to 13.55/5.24 "zip0 a b = (a,b); 13.55/5.24 " 13.55/5.24 The following Lambda expression 13.55/5.24 "\vv1->case vv1 of { 13.55/5.24 (x,i) -> if p x then i : [] else []; 13.55/5.24 _ -> []} 13.55/5.24 " 13.55/5.24 is transformed to 13.55/5.24 "findIndices0 p vv1 = case vv1 of { 13.55/5.24 (x,i) -> if p x then i : [] else []; 13.55/5.24 _ -> []} 13.55/5.24 ; 13.55/5.24 " 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (2) 13.55/5.24 Obligation: 13.55/5.24 mainModule Main 13.55/5.24 module Maybe where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Prelude; 13.55/5.24 listToMaybe :: [a] -> Maybe a; 13.55/5.24 listToMaybe [] = Nothing; 13.55/5.24 listToMaybe (a : _) = Just a; 13.55/5.24 13.55/5.24 } 13.55/5.24 module List where { 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 findIndex :: (a -> Bool) -> [a] -> Maybe Int; 13.55/5.24 findIndex p = Maybe.listToMaybe . findIndices p; 13.55/5.24 13.55/5.24 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.55/5.24 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.55/5.24 13.55/5.24 findIndices0 p vv1 = case vv1 of { 13.55/5.24 (x,i)-> if p x then i : [] else []; 13.55/5.24 _-> []; 13.55/5.24 } ; 13.55/5.24 13.55/5.24 } 13.55/5.24 module Main where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 } 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (3) CR (EQUIVALENT) 13.55/5.24 Case Reductions: 13.55/5.24 The following Case expression 13.55/5.24 "case vv1 of { 13.55/5.24 (x,i) -> if p x then i : [] else []; 13.55/5.24 _ -> []} 13.55/5.24 " 13.55/5.24 is transformed to 13.55/5.24 "findIndices00 p (x,i) = if p x then i : [] else []; 13.55/5.24 findIndices00 p _ = []; 13.55/5.24 " 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (4) 13.55/5.24 Obligation: 13.55/5.24 mainModule Main 13.55/5.24 module Maybe where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Prelude; 13.55/5.24 listToMaybe :: [a] -> Maybe a; 13.55/5.24 listToMaybe [] = Nothing; 13.55/5.24 listToMaybe (a : _) = Just a; 13.55/5.24 13.55/5.24 } 13.55/5.24 module List where { 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 findIndex :: (a -> Bool) -> [a] -> Maybe Int; 13.55/5.24 findIndex p = Maybe.listToMaybe . findIndices p; 13.55/5.24 13.55/5.24 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.55/5.24 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.55/5.24 13.55/5.24 findIndices0 p vv1 = findIndices00 p vv1; 13.55/5.24 13.55/5.24 findIndices00 p (x,i) = if p x then i : [] else []; 13.55/5.24 findIndices00 p _ = []; 13.55/5.24 13.55/5.24 } 13.55/5.24 module Main where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 } 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (5) IFR (EQUIVALENT) 13.55/5.24 If Reductions: 13.55/5.24 The following If expression 13.55/5.24 "if p x then i : [] else []" 13.55/5.24 is transformed to 13.55/5.24 "findIndices000 i True = i : []; 13.55/5.24 findIndices000 i False = []; 13.55/5.24 " 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (6) 13.55/5.24 Obligation: 13.55/5.24 mainModule Main 13.55/5.24 module Maybe where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Prelude; 13.55/5.24 listToMaybe :: [a] -> Maybe a; 13.55/5.24 listToMaybe [] = Nothing; 13.55/5.24 listToMaybe (a : _) = Just a; 13.55/5.24 13.55/5.24 } 13.55/5.24 module List where { 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 findIndex :: (a -> Bool) -> [a] -> Maybe Int; 13.55/5.24 findIndex p = Maybe.listToMaybe . findIndices p; 13.55/5.24 13.55/5.24 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.55/5.24 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.55/5.24 13.55/5.24 findIndices0 p vv1 = findIndices00 p vv1; 13.55/5.24 13.55/5.24 findIndices00 p (x,i) = findIndices000 i (p x); 13.55/5.24 findIndices00 p _ = []; 13.55/5.24 13.55/5.24 findIndices000 i True = i : []; 13.55/5.24 findIndices000 i False = []; 13.55/5.24 13.55/5.24 } 13.55/5.24 module Main where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 } 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (7) BR (EQUIVALENT) 13.55/5.24 Replaced joker patterns by fresh variables and removed binding patterns. 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (8) 13.55/5.24 Obligation: 13.55/5.24 mainModule Main 13.55/5.24 module Maybe where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Prelude; 13.55/5.24 listToMaybe :: [a] -> Maybe a; 13.55/5.24 listToMaybe [] = Nothing; 13.55/5.24 listToMaybe (a : wv) = Just a; 13.55/5.24 13.55/5.24 } 13.55/5.24 module List where { 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 findIndex :: (a -> Bool) -> [a] -> Maybe Int; 13.55/5.24 findIndex p = Maybe.listToMaybe . findIndices p; 13.55/5.24 13.55/5.24 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.55/5.24 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.55/5.24 13.55/5.24 findIndices0 p vv1 = findIndices00 p vv1; 13.55/5.24 13.55/5.24 findIndices00 p (x,i) = findIndices000 i (p x); 13.55/5.24 findIndices00 p ww = []; 13.55/5.24 13.55/5.24 findIndices000 i True = i : []; 13.55/5.24 findIndices000 i False = []; 13.55/5.24 13.55/5.24 } 13.55/5.24 module Main where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 } 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (9) COR (EQUIVALENT) 13.55/5.24 Cond Reductions: 13.55/5.24 The following Function with conditions 13.55/5.24 "undefined |Falseundefined; 13.55/5.24 " 13.55/5.24 is transformed to 13.55/5.24 "undefined = undefined1; 13.55/5.24 " 13.55/5.24 "undefined0 True = undefined; 13.55/5.24 " 13.55/5.24 "undefined1 = undefined0 False; 13.55/5.24 " 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (10) 13.55/5.24 Obligation: 13.55/5.24 mainModule Main 13.55/5.24 module Maybe where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Prelude; 13.55/5.24 listToMaybe :: [a] -> Maybe a; 13.55/5.24 listToMaybe [] = Nothing; 13.55/5.24 listToMaybe (a : wv) = Just a; 13.55/5.24 13.55/5.24 } 13.55/5.24 module List where { 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 findIndex :: (a -> Bool) -> [a] -> Maybe Int; 13.55/5.24 findIndex p = Maybe.listToMaybe . findIndices p; 13.55/5.24 13.55/5.24 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.55/5.24 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom 0)); 13.55/5.24 13.55/5.24 findIndices0 p vv1 = findIndices00 p vv1; 13.55/5.24 13.55/5.24 findIndices00 p (x,i) = findIndices000 i (p x); 13.55/5.24 findIndices00 p ww = []; 13.55/5.24 13.55/5.24 findIndices000 i True = i : []; 13.55/5.24 findIndices000 i False = []; 13.55/5.24 13.55/5.24 } 13.55/5.24 module Main where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 } 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (11) NumRed (SOUND) 13.55/5.24 Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero. 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (12) 13.55/5.24 Obligation: 13.55/5.24 mainModule Main 13.55/5.24 module Maybe where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Prelude; 13.55/5.24 listToMaybe :: [a] -> Maybe a; 13.55/5.24 listToMaybe [] = Nothing; 13.55/5.24 listToMaybe (a : wv) = Just a; 13.55/5.24 13.55/5.24 } 13.55/5.24 module List where { 13.55/5.24 import qualified Main; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 findIndex :: (a -> Bool) -> [a] -> Maybe Int; 13.55/5.24 findIndex p = Maybe.listToMaybe . findIndices p; 13.55/5.24 13.55/5.24 findIndices :: (a -> Bool) -> [a] -> [Int]; 13.55/5.24 findIndices p xs = concatMap (findIndices0 p) (zip xs (enumFrom (Pos Zero))); 13.55/5.24 13.55/5.24 findIndices0 p vv1 = findIndices00 p vv1; 13.55/5.24 13.55/5.24 findIndices00 p (x,i) = findIndices000 i (p x); 13.55/5.24 findIndices00 p ww = []; 13.55/5.24 13.55/5.24 findIndices000 i True = i : []; 13.55/5.24 findIndices000 i False = []; 13.55/5.24 13.55/5.24 } 13.55/5.24 module Main where { 13.55/5.24 import qualified List; 13.55/5.24 import qualified Maybe; 13.55/5.24 import qualified Prelude; 13.55/5.24 } 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (13) Narrow (SOUND) 13.55/5.24 Haskell To QDPs 13.55/5.24 13.55/5.24 digraph dp_graph { 13.55/5.24 node [outthreshold=100, inthreshold=100];1[label="List.findIndex",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 13.55/5.24 3[label="List.findIndex wx3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 13.55/5.24 4[label="List.findIndex wx3 wx4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 13.55/5.24 5[label="Maybe.listToMaybe . List.findIndices wx3",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3]; 13.55/5.24 6[label="Maybe.listToMaybe (List.findIndices wx3 wx4)",fontsize=16,color="black",shape="box"];6 -> 7[label="",style="solid", color="black", weight=3]; 13.55/5.24 7[label="Maybe.listToMaybe (concatMap (List.findIndices0 wx3) (zip wx4 (enumFrom (Pos Zero))))",fontsize=16,color="black",shape="box"];7 -> 8[label="",style="solid", color="black", weight=3]; 13.55/5.24 8[label="Maybe.listToMaybe (concat . map (List.findIndices0 wx3))",fontsize=16,color="black",shape="box"];8 -> 9[label="",style="solid", color="black", weight=3]; 13.55/5.24 9[label="Maybe.listToMaybe (concat (map (List.findIndices0 wx3) (zip wx4 (enumFrom (Pos Zero)))))",fontsize=16,color="black",shape="box"];9 -> 10[label="",style="solid", color="black", weight=3]; 13.55/5.24 10[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zip wx4 (enumFrom (Pos Zero)))))",fontsize=16,color="black",shape="box"];10 -> 11[label="",style="solid", color="black", weight=3]; 13.55/5.24 11[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4 (enumFrom (Pos Zero)))))",fontsize=16,color="burlywood",shape="box"];119[label="wx4/wx40 : wx41",fontsize=10,color="white",style="solid",shape="box"];11 -> 119[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 119 -> 12[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 120[label="wx4/[]",fontsize=10,color="white",style="solid",shape="box"];11 -> 120[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 120 -> 13[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 12[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx40 : wx41) (enumFrom (Pos Zero)))))",fontsize=16,color="black",shape="box"];12 -> 14[label="",style="solid", color="black", weight=3]; 13.55/5.24 13[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 [] (enumFrom (Pos Zero)))))",fontsize=16,color="black",shape="box"];13 -> 15[label="",style="solid", color="black", weight=3]; 13.55/5.24 14[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx40 : wx41) (numericEnumFrom (Pos Zero)))))",fontsize=16,color="black",shape="box"];14 -> 16[label="",style="solid", color="black", weight=3]; 13.55/5.24 15[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) []))",fontsize=16,color="black",shape="triangle"];15 -> 17[label="",style="solid", color="black", weight=3]; 13.55/5.24 16[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx40 : wx41) (Pos Zero : (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero)))))))",fontsize=16,color="black",shape="box"];16 -> 18[label="",style="solid", color="black", weight=3]; 13.55/5.24 17[label="Maybe.listToMaybe (foldr (++) [] [])",fontsize=16,color="black",shape="box"];17 -> 19[label="",style="solid", color="black", weight=3]; 13.55/5.24 18[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zip0 wx40 (Pos Zero) : zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];18 -> 20[label="",style="solid", color="black", weight=3]; 13.55/5.24 19[label="Maybe.listToMaybe []",fontsize=16,color="black",shape="box"];19 -> 21[label="",style="solid", color="black", weight=3]; 13.55/5.24 20[label="Maybe.listToMaybe (foldr (++) [] (List.findIndices0 wx3 (zip0 wx40 (Pos Zero)) : map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];20 -> 22[label="",style="solid", color="black", weight=3]; 13.55/5.24 21[label="Nothing",fontsize=16,color="green",shape="box"];22[label="Maybe.listToMaybe ((++) List.findIndices0 wx3 (zip0 wx40 (Pos Zero)) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];22 -> 23[label="",style="solid", color="black", weight=3]; 13.55/5.24 23[label="Maybe.listToMaybe ((++) List.findIndices00 wx3 (zip0 wx40 (Pos Zero)) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];23 -> 24[label="",style="solid", color="black", weight=3]; 13.55/5.24 24[label="Maybe.listToMaybe ((++) List.findIndices00 wx3 (wx40,Pos Zero) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];24 -> 25[label="",style="solid", color="black", weight=3]; 13.55/5.24 25 -> 26[label="",style="dashed", color="red", weight=0]; 13.55/5.24 25[label="Maybe.listToMaybe ((++) List.findIndices000 (Pos Zero) (wx3 wx40) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="magenta"];25 -> 27[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 27[label="wx3 wx40",fontsize=16,color="green",shape="box"];27 -> 31[label="",style="dashed", color="green", weight=3]; 13.55/5.24 26[label="Maybe.listToMaybe ((++) List.findIndices000 (Pos Zero) wx5 foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="burlywood",shape="triangle"];121[label="wx5/False",fontsize=10,color="white",style="solid",shape="box"];26 -> 121[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 121 -> 29[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 122[label="wx5/True",fontsize=10,color="white",style="solid",shape="box"];26 -> 122[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 122 -> 30[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 31[label="wx40",fontsize=16,color="green",shape="box"];29[label="Maybe.listToMaybe ((++) List.findIndices000 (Pos Zero) False foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];29 -> 32[label="",style="solid", color="black", weight=3]; 13.55/5.24 30[label="Maybe.listToMaybe ((++) List.findIndices000 (Pos Zero) True foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];30 -> 33[label="",style="solid", color="black", weight=3]; 13.55/5.24 32[label="Maybe.listToMaybe ((++) [] foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];32 -> 34[label="",style="solid", color="black", weight=3]; 13.55/5.24 33[label="Maybe.listToMaybe ((++) (Pos Zero : []) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];33 -> 35[label="",style="solid", color="black", weight=3]; 13.55/5.24 34[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="burlywood",shape="box"];123[label="wx41/wx410 : wx411",fontsize=10,color="white",style="solid",shape="box"];34 -> 123[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 123 -> 36[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 124[label="wx41/[]",fontsize=10,color="white",style="solid",shape="box"];34 -> 124[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 124 -> 37[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 35[label="Maybe.listToMaybe (Pos Zero : [] ++ foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx41 (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];35 -> 38[label="",style="solid", color="black", weight=3]; 13.55/5.24 36[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx410 : wx411) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];36 -> 39[label="",style="solid", color="black", weight=3]; 13.55/5.24 37[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 [] (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];37 -> 40[label="",style="solid", color="black", weight=3]; 13.55/5.24 38[label="Just (Pos Zero)",fontsize=16,color="green",shape="box"];39[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx410 : wx411) (Pos Zero + fromInt (Pos (Succ Zero)) `seq` numericEnumFrom (Pos Zero + fromInt (Pos (Succ Zero)))))))",fontsize=16,color="black",shape="box"];39 -> 41[label="",style="solid", color="black", weight=3]; 13.55/5.24 40 -> 15[label="",style="dashed", color="red", weight=0]; 13.55/5.24 40[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) []))",fontsize=16,color="magenta"];41 -> 71[label="",style="dashed", color="red", weight=0]; 13.55/5.24 41[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx410 : wx411) (enforceWHNF (WHNF (Pos Zero + fromInt (Pos (Succ Zero)))) (numericEnumFrom (Pos Zero + fromInt (Pos (Succ Zero))))))))",fontsize=16,color="magenta"];41 -> 72[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 41 -> 73[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 41 -> 74[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 41 -> 75[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 72[label="wx410",fontsize=16,color="green",shape="box"];73[label="Zero",fontsize=16,color="green",shape="box"];74[label="wx411",fontsize=16,color="green",shape="box"];75[label="Zero",fontsize=16,color="green",shape="box"];71[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx4110 : wx4111) (enforceWHNF (WHNF (Pos wx8 + fromInt (Pos (Succ Zero)))) (numericEnumFrom (Pos wx7 + fromInt (Pos (Succ Zero))))))))",fontsize=16,color="black",shape="triangle"];71 -> 78[label="",style="solid", color="black", weight=3]; 13.55/5.24 78[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx4110 : wx4111) (enforceWHNF (WHNF (primPlusInt (Pos wx8) (fromInt (Pos (Succ Zero))))) (numericEnumFrom (primPlusInt (Pos wx7) (fromInt (Pos (Succ Zero)))))))))",fontsize=16,color="black",shape="box"];78 -> 79[label="",style="solid", color="black", weight=3]; 13.55/5.24 79[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx4110 : wx4111) (enforceWHNF (WHNF (primPlusInt (Pos wx8) (Pos (Succ Zero)))) (numericEnumFrom (primPlusInt (Pos wx7) (Pos (Succ Zero))))))))",fontsize=16,color="black",shape="box"];79 -> 80[label="",style="solid", color="black", weight=3]; 13.55/5.24 80[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx4110 : wx4111) (enforceWHNF (WHNF (Pos (primPlusNat wx8 (Succ Zero)))) (numericEnumFrom (Pos (primPlusNat wx8 (Succ Zero))))))))",fontsize=16,color="black",shape="box"];80 -> 81[label="",style="solid", color="black", weight=3]; 13.55/5.24 81[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx4110 : wx4111) (numericEnumFrom (Pos (primPlusNat wx8 (Succ Zero)))))))",fontsize=16,color="black",shape="box"];81 -> 82[label="",style="solid", color="black", weight=3]; 13.55/5.24 82[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx4110 : wx4111) (Pos (primPlusNat wx8 (Succ Zero)) : (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero)))))))",fontsize=16,color="black",shape="box"];82 -> 83[label="",style="solid", color="black", weight=3]; 13.55/5.24 83[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zip0 wx4110 (Pos (primPlusNat wx8 (Succ Zero))) : zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];83 -> 84[label="",style="solid", color="black", weight=3]; 13.55/5.24 84[label="Maybe.listToMaybe (foldr (++) [] (List.findIndices0 wx3 (zip0 wx4110 (Pos (primPlusNat wx8 (Succ Zero)))) : map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];84 -> 85[label="",style="solid", color="black", weight=3]; 13.55/5.24 85[label="Maybe.listToMaybe ((++) List.findIndices0 wx3 (zip0 wx4110 (Pos (primPlusNat wx8 (Succ Zero)))) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];85 -> 86[label="",style="solid", color="black", weight=3]; 13.55/5.24 86[label="Maybe.listToMaybe ((++) List.findIndices00 wx3 (zip0 wx4110 (Pos (primPlusNat wx8 (Succ Zero)))) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];86 -> 87[label="",style="solid", color="black", weight=3]; 13.55/5.24 87[label="Maybe.listToMaybe ((++) List.findIndices00 wx3 (wx4110,Pos (primPlusNat wx8 (Succ Zero))) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];87 -> 88[label="",style="solid", color="black", weight=3]; 13.55/5.24 88 -> 89[label="",style="dashed", color="red", weight=0]; 13.55/5.24 88[label="Maybe.listToMaybe ((++) List.findIndices000 (Pos (primPlusNat wx8 (Succ Zero))) (wx3 wx4110) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="magenta"];88 -> 90[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 90[label="wx3 wx4110",fontsize=16,color="green",shape="box"];90 -> 94[label="",style="dashed", color="green", weight=3]; 13.55/5.24 89[label="Maybe.listToMaybe ((++) List.findIndices000 (Pos (primPlusNat wx8 (Succ Zero))) wx9 foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="burlywood",shape="triangle"];125[label="wx9/False",fontsize=10,color="white",style="solid",shape="box"];89 -> 125[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 125 -> 92[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 126[label="wx9/True",fontsize=10,color="white",style="solid",shape="box"];89 -> 126[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 126 -> 93[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 94[label="wx4110",fontsize=16,color="green",shape="box"];92[label="Maybe.listToMaybe ((++) List.findIndices000 (Pos (primPlusNat wx8 (Succ Zero))) False foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];92 -> 95[label="",style="solid", color="black", weight=3]; 13.55/5.24 93[label="Maybe.listToMaybe ((++) List.findIndices000 (Pos (primPlusNat wx8 (Succ Zero))) True foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];93 -> 96[label="",style="solid", color="black", weight=3]; 13.55/5.24 95[label="Maybe.listToMaybe ((++) [] foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];95 -> 97[label="",style="solid", color="black", weight=3]; 13.55/5.24 96[label="Maybe.listToMaybe ((++) (Pos (primPlusNat wx8 (Succ Zero)) : []) foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];96 -> 98[label="",style="solid", color="black", weight=3]; 13.55/5.24 97[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="burlywood",shape="box"];127[label="wx4111/wx41110 : wx41111",fontsize=10,color="white",style="solid",shape="box"];97 -> 127[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 127 -> 99[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 128[label="wx4111/[]",fontsize=10,color="white",style="solid",shape="box"];97 -> 128[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 128 -> 100[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 98[label="Maybe.listToMaybe (Pos (primPlusNat wx8 (Succ Zero)) : [] ++ foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 wx4111 (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];98 -> 101[label="",style="solid", color="black", weight=3]; 13.55/5.24 99[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx41110 : wx41111) (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];99 -> 102[label="",style="solid", color="black", weight=3]; 13.55/5.24 100[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 [] (numericEnumFrom $! Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];100 -> 103[label="",style="solid", color="black", weight=3]; 13.55/5.24 101[label="Just (Pos (primPlusNat wx8 (Succ Zero)))",fontsize=16,color="green",shape="box"];101 -> 104[label="",style="dashed", color="green", weight=3]; 13.55/5.24 102[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx41110 : wx41111) (Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero)) `seq` numericEnumFrom (Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero)))))))",fontsize=16,color="black",shape="box"];102 -> 105[label="",style="solid", color="black", weight=3]; 13.55/5.24 103 -> 15[label="",style="dashed", color="red", weight=0]; 13.55/5.24 103[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) []))",fontsize=16,color="magenta"];104[label="primPlusNat wx8 (Succ Zero)",fontsize=16,color="burlywood",shape="triangle"];129[label="wx8/Succ wx80",fontsize=10,color="white",style="solid",shape="box"];104 -> 129[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 129 -> 106[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 130[label="wx8/Zero",fontsize=10,color="white",style="solid",shape="box"];104 -> 130[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 130 -> 107[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 105 -> 71[label="",style="dashed", color="red", weight=0]; 13.55/5.24 105[label="Maybe.listToMaybe (foldr (++) [] (map (List.findIndices0 wx3) (zipWith zip0 (wx41110 : wx41111) (enforceWHNF (WHNF (Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero)))) (numericEnumFrom (Pos (primPlusNat wx8 (Succ Zero)) + fromInt (Pos (Succ Zero))))))))",fontsize=16,color="magenta"];105 -> 108[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 105 -> 109[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 105 -> 110[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 105 -> 111[label="",style="dashed", color="magenta", weight=3]; 13.55/5.24 106[label="primPlusNat (Succ wx80) (Succ Zero)",fontsize=16,color="black",shape="box"];106 -> 112[label="",style="solid", color="black", weight=3]; 13.55/5.24 107[label="primPlusNat Zero (Succ Zero)",fontsize=16,color="black",shape="box"];107 -> 113[label="",style="solid", color="black", weight=3]; 13.55/5.24 108[label="wx41110",fontsize=16,color="green",shape="box"];109 -> 104[label="",style="dashed", color="red", weight=0]; 13.55/5.24 109[label="primPlusNat wx8 (Succ Zero)",fontsize=16,color="magenta"];110[label="wx41111",fontsize=16,color="green",shape="box"];111 -> 104[label="",style="dashed", color="red", weight=0]; 13.55/5.24 111[label="primPlusNat wx8 (Succ Zero)",fontsize=16,color="magenta"];112[label="Succ (Succ (primPlusNat wx80 Zero))",fontsize=16,color="green",shape="box"];112 -> 114[label="",style="dashed", color="green", weight=3]; 13.55/5.24 113[label="Succ Zero",fontsize=16,color="green",shape="box"];114[label="primPlusNat wx80 Zero",fontsize=16,color="burlywood",shape="box"];131[label="wx80/Succ wx800",fontsize=10,color="white",style="solid",shape="box"];114 -> 131[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 131 -> 115[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 132[label="wx80/Zero",fontsize=10,color="white",style="solid",shape="box"];114 -> 132[label="",style="solid", color="burlywood", weight=9]; 13.55/5.24 132 -> 116[label="",style="solid", color="burlywood", weight=3]; 13.55/5.24 115[label="primPlusNat (Succ wx800) Zero",fontsize=16,color="black",shape="box"];115 -> 117[label="",style="solid", color="black", weight=3]; 13.55/5.24 116[label="primPlusNat Zero Zero",fontsize=16,color="black",shape="box"];116 -> 118[label="",style="solid", color="black", weight=3]; 13.55/5.24 117[label="Succ wx800",fontsize=16,color="green",shape="box"];118[label="Zero",fontsize=16,color="green",shape="box"];} 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (14) 13.55/5.24 Obligation: 13.55/5.24 Q DP problem: 13.55/5.24 The TRS P consists of the following rules: 13.55/5.24 13.55/5.24 new_listToMaybe(wx8, wx3, :(wx41110, wx41111), ba) -> new_listToMaybe0(wx3, wx41110, wx41111, new_primPlusNat(wx8), new_primPlusNat(wx8), ba) 13.55/5.24 new_listToMaybe0(wx3, wx4110, wx4111, wx8, wx7, ba) -> new_listToMaybe(wx8, wx3, wx4111, ba) 13.55/5.24 13.55/5.24 The TRS R consists of the following rules: 13.55/5.24 13.55/5.24 new_primPlusNat(Succ(wx80)) -> Succ(Succ(new_primPlusNat0(wx80))) 13.55/5.24 new_primPlusNat(Zero) -> Succ(Zero) 13.55/5.24 new_primPlusNat0(Succ(wx800)) -> Succ(wx800) 13.55/5.24 new_primPlusNat0(Zero) -> Zero 13.55/5.24 13.55/5.24 The set Q consists of the following terms: 13.55/5.24 13.55/5.24 new_primPlusNat0(Zero) 13.55/5.24 new_primPlusNat0(Succ(x0)) 13.55/5.24 new_primPlusNat(Succ(x0)) 13.55/5.24 new_primPlusNat(Zero) 13.55/5.24 13.55/5.24 We have to consider all minimal (P,Q,R)-chains. 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (15) QDPSizeChangeProof (EQUIVALENT) 13.55/5.24 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.55/5.24 13.55/5.24 From the DPs we obtained the following set of size-change graphs: 13.55/5.24 *new_listToMaybe0(wx3, wx4110, wx4111, wx8, wx7, ba) -> new_listToMaybe(wx8, wx3, wx4111, ba) 13.55/5.24 The graph contains the following edges 4 >= 1, 1 >= 2, 3 >= 3, 6 >= 4 13.55/5.24 13.55/5.24 13.55/5.24 *new_listToMaybe(wx8, wx3, :(wx41110, wx41111), ba) -> new_listToMaybe0(wx3, wx41110, wx41111, new_primPlusNat(wx8), new_primPlusNat(wx8), ba) 13.55/5.24 The graph contains the following edges 2 >= 1, 3 > 2, 3 > 3, 4 >= 6 13.55/5.24 13.55/5.24 13.55/5.24 ---------------------------------------- 13.55/5.24 13.55/5.24 (16) 13.55/5.24 YES 13.81/7.27 EOF