/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.hs /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.hs # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty H-Termination with start terms of the given HASKELL could be proven: (0) HASKELL (1) LR [EQUIVALENT, 0 ms] (2) HASKELL (3) CR [EQUIVALENT, 0 ms] (4) HASKELL (5) IFR [EQUIVALENT, 0 ms] (6) HASKELL (7) BR [EQUIVALENT, 0 ms] (8) HASKELL (9) COR [EQUIVALENT, 0 ms] (10) HASKELL (11) LetRed [EQUIVALENT, 0 ms] (12) HASKELL (13) NumRed [SOUND, 0 ms] (14) HASKELL (15) Narrow [SOUND, 0 ms] (16) QDP (17) TransformationProof [EQUIVALENT, 0 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) QDP (21) TransformationProof [EQUIVALENT, 0 ms] (22) QDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) QDP (25) UsableRulesProof [EQUIVALENT, 0 ms] (26) QDP (27) QReductionProof [EQUIVALENT, 0 ms] (28) QDP (29) QDPSizeChangeProof [EQUIVALENT, 0 ms] (30) YES ---------------------------------------- (0) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; genericSplitAt :: Integral b => b -> [a] -> ([a],[a]); genericSplitAt 0 xs = ([],xs); genericSplitAt _ [] = ([],[]); genericSplitAt n (x : xs) | n > 0 = (x : xs',xs'') where { vv9 = genericSplitAt (n - 1) xs; xs' = (\(xs',_) ->xs') vv9; xs'' = (\(_,xs'') ->xs'') vv9; }; genericSplitAt _ _ = error []; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (1) LR (EQUIVALENT) Lambda Reductions: The following Lambda expression "\(_,xs'')->xs''" is transformed to "xs''0 (_,xs'') = xs''; " The following Lambda expression "\(xs',_)->xs'" is transformed to "xs'0 (xs',_) = xs'; " ---------------------------------------- (2) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; genericSplitAt :: Integral b => b -> [a] -> ([a],[a]); genericSplitAt 0 xs = ([],xs); genericSplitAt _ [] = ([],[]); genericSplitAt n (x : xs) | n > 0 = (x : xs',xs'') where { vv9 = genericSplitAt (n - 1) xs; xs' = xs'0 vv9; xs'' = xs''0 vv9; xs''0 (_,xs'') = xs''; xs'0 (xs',_) = xs'; }; genericSplitAt _ _ = error []; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (3) CR (EQUIVALENT) Case Reductions: The following Case expression "case compare x y of { EQ -> o; LT -> LT; GT -> GT} " is transformed to "primCompAux0 o EQ = o; primCompAux0 o LT = LT; primCompAux0 o GT = GT; " ---------------------------------------- (4) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; genericSplitAt :: Integral b => b -> [a] -> ([a],[a]); genericSplitAt 0 xs = ([],xs); genericSplitAt _ [] = ([],[]); genericSplitAt n (x : xs) | n > 0 = (x : xs',xs'') where { vv9 = genericSplitAt (n - 1) xs; xs' = xs'0 vv9; xs'' = xs''0 vv9; xs''0 (_,xs'') = xs''; xs'0 (xs',_) = xs'; }; genericSplitAt _ _ = error []; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (5) IFR (EQUIVALENT) If Reductions: The following If expression "if primGEqNatS x y then Succ (primDivNatS (primMinusNatS x y) (Succ y)) else Zero" is transformed to "primDivNatS0 x y True = Succ (primDivNatS (primMinusNatS x y) (Succ y)); primDivNatS0 x y False = Zero; " The following If expression "if primGEqNatS x y then primModNatS (primMinusNatS x y) (Succ y) else Succ x" is transformed to "primModNatS0 x y True = primModNatS (primMinusNatS x y) (Succ y); primModNatS0 x y False = Succ x; " ---------------------------------------- (6) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; genericSplitAt :: Integral a => a -> [b] -> ([b],[b]); genericSplitAt 0 xs = ([],xs); genericSplitAt _ [] = ([],[]); genericSplitAt n (x : xs) | n > 0 = (x : xs',xs'') where { vv9 = genericSplitAt (n - 1) xs; xs' = xs'0 vv9; xs'' = xs''0 vv9; xs''0 (_,xs'') = xs''; xs'0 (xs',_) = xs'; }; genericSplitAt _ _ = error []; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (7) BR (EQUIVALENT) Replaced joker patterns by fresh variables and removed binding patterns. ---------------------------------------- (8) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; genericSplitAt :: Integral b => b -> [a] -> ([a],[a]); genericSplitAt 0 xs = ([],xs); genericSplitAt zy [] = ([],[]); genericSplitAt n (x : xs) | n > 0 = (x : xs',xs'') where { vv9 = genericSplitAt (n - 1) xs; xs' = xs'0 vv9; xs'' = xs''0 vv9; xs''0 (zz,xs'') = xs''; xs'0 (xs',vuu) = xs'; }; genericSplitAt vuv vuw = error []; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (9) COR (EQUIVALENT) Cond Reductions: The following Function with conditions "gcd' x 0 = x; gcd' x y = gcd' y (x `rem` y); " is transformed to "gcd' x vux = gcd'2 x vux; gcd' x y = gcd'0 x y; " "gcd'0 x y = gcd' y (x `rem` y); " "gcd'1 True x vux = x; gcd'1 vuy vuz vvu = gcd'0 vuz vvu; " "gcd'2 x vux = gcd'1 (vux == 0) x vux; gcd'2 vvv vvw = gcd'0 vvv vvw; " The following Function with conditions "gcd 0 0 = error []; gcd x y = gcd' (abs x) (abs y) where { gcd' x 0 = x; gcd' x y = gcd' y (x `rem` y); } ; " is transformed to "gcd vvx vvy = gcd3 vvx vvy; gcd x y = gcd0 x y; " "gcd0 x y = gcd' (abs x) (abs y) where { gcd' x vux = gcd'2 x vux; gcd' x y = gcd'0 x y; ; gcd'0 x y = gcd' y (x `rem` y); ; gcd'1 True x vux = x; gcd'1 vuy vuz vvu = gcd'0 vuz vvu; ; gcd'2 x vux = gcd'1 (vux == 0) x vux; gcd'2 vvv vvw = gcd'0 vvv vvw; } ; " "gcd1 True vvx vvy = error []; gcd1 vvz vwu vwv = gcd0 vwu vwv; " "gcd2 True vvx vvy = gcd1 (vvy == 0) vvx vvy; gcd2 vww vwx vwy = gcd0 vwx vwy; " "gcd3 vvx vvy = gcd2 (vvx == 0) vvx vvy; gcd3 vwz vxu = gcd0 vwz vxu; " The following Function with conditions "reduce x y|y == 0error []|otherwisex `quot` d :% (y `quot` d) where { d = gcd x y; } ; " is transformed to "reduce x y = reduce2 x y; " "reduce2 x y = reduce1 x y (y == 0) where { d = gcd x y; ; reduce0 x y True = x `quot` d :% (y `quot` d); ; reduce1 x y True = error []; reduce1 x y False = reduce0 x y otherwise; } ; " The following Function with conditions "absReal x|x >= 0x|otherwise`negate` x; " is transformed to "absReal x = absReal2 x; " "absReal0 x True = `negate` x; " "absReal1 x True = x; absReal1 x False = absReal0 x otherwise; " "absReal2 x = absReal1 x (x >= 0); " The following Function with conditions "undefined |Falseundefined; " is transformed to "undefined = undefined1; " "undefined0 True = undefined; " "undefined1 = undefined0 False; " The following Function with conditions "compare x y|x == yEQ|x <= yLT|otherwiseGT; " is transformed to "compare x y = compare3 x y; " "compare0 x y True = GT; " "compare2 x y True = EQ; compare2 x y False = compare1 x y (x <= y); " "compare1 x y True = LT; compare1 x y False = compare0 x y otherwise; " "compare3 x y = compare2 x y (x == y); " The following Function with conditions "genericSplitAt 0 xs = ([],xs); genericSplitAt zy [] = ([],[]); genericSplitAt n (x : xs)|n > 0(x : xs',xs'') where { vv9 = genericSplitAt (n - 1) xs; ; xs' = xs'0 vv9; ; xs'' = xs''0 vv9; ; xs''0 (zz,xs'') = xs''; ; xs'0 (xs',vuu) = xs'; } ; genericSplitAt vuv vuw = error []; " is transformed to "genericSplitAt vyv xs = genericSplitAt5 vyv xs; genericSplitAt zy [] = genericSplitAt3 zy []; genericSplitAt n (x : xs) = genericSplitAt2 n (x : xs); genericSplitAt vuv vuw = genericSplitAt0 vuv vuw; " "genericSplitAt0 vuv vuw = error []; " "genericSplitAt2 n (x : xs) = genericSplitAt1 n x xs (n > 0) where { genericSplitAt1 n x xs True = (x : xs',xs''); genericSplitAt1 n x xs False = genericSplitAt0 n (x : xs); ; vv9 = genericSplitAt (n - 1) xs; ; xs' = xs'0 vv9; ; xs'' = xs''0 vv9; ; xs''0 (zz,xs'') = xs''; ; xs'0 (xs',vuu) = xs'; } ; genericSplitAt2 vxw vxx = genericSplitAt0 vxw vxx; " "genericSplitAt3 zy [] = ([],[]); genericSplitAt3 vxz vyu = genericSplitAt2 vxz vyu; " "genericSplitAt4 True vyv xs = ([],xs); genericSplitAt4 vyw vyx vyy = genericSplitAt3 vyx vyy; " "genericSplitAt5 vyv xs = genericSplitAt4 (vyv == 0) vyv xs; genericSplitAt5 vyz vzu = genericSplitAt3 vyz vzu; " ---------------------------------------- (10) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; genericSplitAt :: Integral b => b -> [a] -> ([a],[a]); genericSplitAt vyv xs = genericSplitAt5 vyv xs; genericSplitAt zy [] = genericSplitAt3 zy []; genericSplitAt n (x : xs) = genericSplitAt2 n (x : xs); genericSplitAt vuv vuw = genericSplitAt0 vuv vuw; genericSplitAt0 vuv vuw = error []; genericSplitAt2 n (x : xs) = genericSplitAt1 n x xs (n > 0) where { genericSplitAt1 n x xs True = (x : xs',xs''); genericSplitAt1 n x xs False = genericSplitAt0 n (x : xs); vv9 = genericSplitAt (n - 1) xs; xs' = xs'0 vv9; xs'' = xs''0 vv9; xs''0 (zz,xs'') = xs''; xs'0 (xs',vuu) = xs'; }; genericSplitAt2 vxw vxx = genericSplitAt0 vxw vxx; genericSplitAt3 zy [] = ([],[]); genericSplitAt3 vxz vyu = genericSplitAt2 vxz vyu; genericSplitAt4 True vyv xs = ([],xs); genericSplitAt4 vyw vyx vyy = genericSplitAt3 vyx vyy; genericSplitAt5 vyv xs = genericSplitAt4 (vyv == 0) vyv xs; genericSplitAt5 vyz vzu = genericSplitAt3 vyz vzu; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (11) LetRed (EQUIVALENT) Let/Where Reductions: The bindings of the following Let/Where expression "gcd' (abs x) (abs y) where { gcd' x vux = gcd'2 x vux; gcd' x y = gcd'0 x y; ; gcd'0 x y = gcd' y (x `rem` y); ; gcd'1 True x vux = x; gcd'1 vuy vuz vvu = gcd'0 vuz vvu; ; gcd'2 x vux = gcd'1 (vux == 0) x vux; gcd'2 vvv vvw = gcd'0 vvv vvw; } " are unpacked to the following functions on top level "gcd0Gcd'0 x y = gcd0Gcd' y (x `rem` y); " "gcd0Gcd'2 x vux = gcd0Gcd'1 (vux == 0) x vux; gcd0Gcd'2 vvv vvw = gcd0Gcd'0 vvv vvw; " "gcd0Gcd'1 True x vux = x; gcd0Gcd'1 vuy vuz vvu = gcd0Gcd'0 vuz vvu; " "gcd0Gcd' x vux = gcd0Gcd'2 x vux; gcd0Gcd' x y = gcd0Gcd'0 x y; " The bindings of the following Let/Where expression "reduce1 x y (y == 0) where { d = gcd x y; ; reduce0 x y True = x `quot` d :% (y `quot` d); ; reduce1 x y True = error []; reduce1 x y False = reduce0 x y otherwise; } " are unpacked to the following functions on top level "reduce2D vzv vzw = gcd vzv vzw; " "reduce2Reduce1 vzv vzw x y True = error []; reduce2Reduce1 vzv vzw x y False = reduce2Reduce0 vzv vzw x y otherwise; " "reduce2Reduce0 vzv vzw x y True = x `quot` reduce2D vzv vzw :% (y `quot` reduce2D vzv vzw); " The bindings of the following Let/Where expression "genericSplitAt1 n x xs (n > 0) where { genericSplitAt1 n x xs True = (x : xs',xs''); genericSplitAt1 n x xs False = genericSplitAt0 n (x : xs); ; vv9 = genericSplitAt (n - 1) xs; ; xs' = xs'0 vv9; ; xs'' = xs''0 vv9; ; xs''0 (zz,xs'') = xs''; ; xs'0 (xs',vuu) = xs'; } " are unpacked to the following functions on top level "genericSplitAt2Vv9 vzx vzy = genericSplitAt (vzx - 1) vzy; " "genericSplitAt2Xs' vzx vzy = genericSplitAt2Xs'0 vzx vzy (genericSplitAt2Vv9 vzx vzy); " "genericSplitAt2Xs'' vzx vzy = genericSplitAt2Xs''0 vzx vzy (genericSplitAt2Vv9 vzx vzy); " "genericSplitAt2GenericSplitAt1 vzx vzy n x xs True = (x : genericSplitAt2Xs' vzx vzy,genericSplitAt2Xs'' vzx vzy); genericSplitAt2GenericSplitAt1 vzx vzy n x xs False = genericSplitAt0 n (x : xs); " "genericSplitAt2Xs''0 vzx vzy (zz,xs'') = xs''; " "genericSplitAt2Xs'0 vzx vzy (xs',vuu) = xs'; " ---------------------------------------- (12) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; genericSplitAt :: Integral b => b -> [a] -> ([a],[a]); genericSplitAt vyv xs = genericSplitAt5 vyv xs; genericSplitAt zy [] = genericSplitAt3 zy []; genericSplitAt n (x : xs) = genericSplitAt2 n (x : xs); genericSplitAt vuv vuw = genericSplitAt0 vuv vuw; genericSplitAt0 vuv vuw = error []; genericSplitAt2 n (x : xs) = genericSplitAt2GenericSplitAt1 n xs n x xs (n > 0); genericSplitAt2 vxw vxx = genericSplitAt0 vxw vxx; genericSplitAt2GenericSplitAt1 vzx vzy n x xs True = (x : genericSplitAt2Xs' vzx vzy,genericSplitAt2Xs'' vzx vzy); genericSplitAt2GenericSplitAt1 vzx vzy n x xs False = genericSplitAt0 n (x : xs); genericSplitAt2Vv9 vzx vzy = genericSplitAt (vzx - 1) vzy; genericSplitAt2Xs' vzx vzy = genericSplitAt2Xs'0 vzx vzy (genericSplitAt2Vv9 vzx vzy); genericSplitAt2Xs'' vzx vzy = genericSplitAt2Xs''0 vzx vzy (genericSplitAt2Vv9 vzx vzy); genericSplitAt2Xs''0 vzx vzy (zz,xs'') = xs''; genericSplitAt2Xs'0 vzx vzy (xs',vuu) = xs'; genericSplitAt3 zy [] = ([],[]); genericSplitAt3 vxz vyu = genericSplitAt2 vxz vyu; genericSplitAt4 True vyv xs = ([],xs); genericSplitAt4 vyw vyx vyy = genericSplitAt3 vyx vyy; genericSplitAt5 vyv xs = genericSplitAt4 (vyv == 0) vyv xs; genericSplitAt5 vyz vzu = genericSplitAt3 vyz vzu; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (13) NumRed (SOUND) Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero. ---------------------------------------- (14) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; genericSplitAt :: Integral b => b -> [a] -> ([a],[a]); genericSplitAt vyv xs = genericSplitAt5 vyv xs; genericSplitAt zy [] = genericSplitAt3 zy []; genericSplitAt n (x : xs) = genericSplitAt2 n (x : xs); genericSplitAt vuv vuw = genericSplitAt0 vuv vuw; genericSplitAt0 vuv vuw = error []; genericSplitAt2 n (x : xs) = genericSplitAt2GenericSplitAt1 n xs n x xs (n > fromInt (Pos Zero)); genericSplitAt2 vxw vxx = genericSplitAt0 vxw vxx; genericSplitAt2GenericSplitAt1 vzx vzy n x xs True = (x : genericSplitAt2Xs' vzx vzy,genericSplitAt2Xs'' vzx vzy); genericSplitAt2GenericSplitAt1 vzx vzy n x xs False = genericSplitAt0 n (x : xs); genericSplitAt2Vv9 vzx vzy = genericSplitAt (vzx - fromInt (Pos (Succ Zero))) vzy; genericSplitAt2Xs' vzx vzy = genericSplitAt2Xs'0 vzx vzy (genericSplitAt2Vv9 vzx vzy); genericSplitAt2Xs'' vzx vzy = genericSplitAt2Xs''0 vzx vzy (genericSplitAt2Vv9 vzx vzy); genericSplitAt2Xs''0 vzx vzy (zz,xs'') = xs''; genericSplitAt2Xs'0 vzx vzy (xs',vuu) = xs'; genericSplitAt3 zy [] = ([],[]); genericSplitAt3 vxz vyu = genericSplitAt2 vxz vyu; genericSplitAt4 True vyv xs = ([],xs); genericSplitAt4 vyw vyx vyy = genericSplitAt3 vyx vyy; genericSplitAt5 vyv xs = genericSplitAt4 (vyv == fromInt (Pos Zero)) vyv xs; genericSplitAt5 vyz vzu = genericSplitAt3 vyz vzu; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (15) Narrow (SOUND) Haskell To QDPs digraph dp_graph { node [outthreshold=100, inthreshold=100];1[label="List.genericSplitAt",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 3[label="List.genericSplitAt vzz3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 4[label="List.genericSplitAt vzz3 vzz4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 5[label="List.genericSplitAt5 vzz3 vzz4",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3]; 6[label="List.genericSplitAt4 (vzz3 == fromInt (Pos Zero)) vzz3 vzz4",fontsize=16,color="black",shape="box"];6 -> 7[label="",style="solid", color="black", weight=3]; 7[label="List.genericSplitAt4 (primEqInt vzz3 (fromInt (Pos Zero))) vzz3 vzz4",fontsize=16,color="burlywood",shape="box"];78[label="vzz3/Pos vzz30",fontsize=10,color="white",style="solid",shape="box"];7 -> 78[label="",style="solid", color="burlywood", weight=9]; 78 -> 8[label="",style="solid", color="burlywood", weight=3]; 79[label="vzz3/Neg vzz30",fontsize=10,color="white",style="solid",shape="box"];7 -> 79[label="",style="solid", color="burlywood", weight=9]; 79 -> 9[label="",style="solid", color="burlywood", weight=3]; 8[label="List.genericSplitAt4 (primEqInt (Pos vzz30) (fromInt (Pos Zero))) (Pos vzz30) vzz4",fontsize=16,color="burlywood",shape="box"];80[label="vzz30/Succ vzz300",fontsize=10,color="white",style="solid",shape="box"];8 -> 80[label="",style="solid", color="burlywood", weight=9]; 80 -> 10[label="",style="solid", color="burlywood", weight=3]; 81[label="vzz30/Zero",fontsize=10,color="white",style="solid",shape="box"];8 -> 81[label="",style="solid", color="burlywood", weight=9]; 81 -> 11[label="",style="solid", color="burlywood", weight=3]; 9[label="List.genericSplitAt4 (primEqInt (Neg vzz30) (fromInt (Pos Zero))) (Neg vzz30) vzz4",fontsize=16,color="burlywood",shape="box"];82[label="vzz30/Succ vzz300",fontsize=10,color="white",style="solid",shape="box"];9 -> 82[label="",style="solid", color="burlywood", weight=9]; 82 -> 12[label="",style="solid", color="burlywood", weight=3]; 83[label="vzz30/Zero",fontsize=10,color="white",style="solid",shape="box"];9 -> 83[label="",style="solid", color="burlywood", weight=9]; 83 -> 13[label="",style="solid", color="burlywood", weight=3]; 10[label="List.genericSplitAt4 (primEqInt (Pos (Succ vzz300)) (fromInt (Pos Zero))) (Pos (Succ vzz300)) vzz4",fontsize=16,color="black",shape="box"];10 -> 14[label="",style="solid", color="black", weight=3]; 11[label="List.genericSplitAt4 (primEqInt (Pos Zero) (fromInt (Pos Zero))) (Pos Zero) vzz4",fontsize=16,color="black",shape="box"];11 -> 15[label="",style="solid", color="black", weight=3]; 12[label="List.genericSplitAt4 (primEqInt (Neg (Succ vzz300)) (fromInt (Pos Zero))) (Neg (Succ vzz300)) vzz4",fontsize=16,color="black",shape="box"];12 -> 16[label="",style="solid", color="black", weight=3]; 13[label="List.genericSplitAt4 (primEqInt (Neg Zero) (fromInt (Pos Zero))) (Neg Zero) vzz4",fontsize=16,color="black",shape="box"];13 -> 17[label="",style="solid", color="black", weight=3]; 14[label="List.genericSplitAt4 (primEqInt (Pos (Succ vzz300)) (Pos Zero)) (Pos (Succ vzz300)) vzz4",fontsize=16,color="black",shape="box"];14 -> 18[label="",style="solid", color="black", weight=3]; 15[label="List.genericSplitAt4 (primEqInt (Pos Zero) (Pos Zero)) (Pos Zero) vzz4",fontsize=16,color="black",shape="box"];15 -> 19[label="",style="solid", color="black", weight=3]; 16[label="List.genericSplitAt4 (primEqInt (Neg (Succ vzz300)) (Pos Zero)) (Neg (Succ vzz300)) vzz4",fontsize=16,color="black",shape="box"];16 -> 20[label="",style="solid", color="black", weight=3]; 17[label="List.genericSplitAt4 (primEqInt (Neg Zero) (Pos Zero)) (Neg Zero) vzz4",fontsize=16,color="black",shape="box"];17 -> 21[label="",style="solid", color="black", weight=3]; 18[label="List.genericSplitAt4 False (Pos (Succ vzz300)) vzz4",fontsize=16,color="black",shape="box"];18 -> 22[label="",style="solid", color="black", weight=3]; 19[label="List.genericSplitAt4 True (Pos Zero) vzz4",fontsize=16,color="black",shape="box"];19 -> 23[label="",style="solid", color="black", weight=3]; 20[label="List.genericSplitAt4 False (Neg (Succ vzz300)) vzz4",fontsize=16,color="black",shape="box"];20 -> 24[label="",style="solid", color="black", weight=3]; 21[label="List.genericSplitAt4 True (Neg Zero) vzz4",fontsize=16,color="black",shape="box"];21 -> 25[label="",style="solid", color="black", weight=3]; 22[label="List.genericSplitAt3 (Pos (Succ vzz300)) vzz4",fontsize=16,color="burlywood",shape="box"];84[label="vzz4/vzz40 : vzz41",fontsize=10,color="white",style="solid",shape="box"];22 -> 84[label="",style="solid", color="burlywood", weight=9]; 84 -> 26[label="",style="solid", color="burlywood", weight=3]; 85[label="vzz4/[]",fontsize=10,color="white",style="solid",shape="box"];22 -> 85[label="",style="solid", color="burlywood", weight=9]; 85 -> 27[label="",style="solid", color="burlywood", weight=3]; 23[label="([],vzz4)",fontsize=16,color="green",shape="box"];24[label="List.genericSplitAt3 (Neg (Succ vzz300)) vzz4",fontsize=16,color="burlywood",shape="box"];86[label="vzz4/vzz40 : vzz41",fontsize=10,color="white",style="solid",shape="box"];24 -> 86[label="",style="solid", color="burlywood", weight=9]; 86 -> 28[label="",style="solid", color="burlywood", weight=3]; 87[label="vzz4/[]",fontsize=10,color="white",style="solid",shape="box"];24 -> 87[label="",style="solid", color="burlywood", weight=9]; 87 -> 29[label="",style="solid", color="burlywood", weight=3]; 25[label="([],vzz4)",fontsize=16,color="green",shape="box"];26[label="List.genericSplitAt3 (Pos (Succ vzz300)) (vzz40 : vzz41)",fontsize=16,color="black",shape="box"];26 -> 30[label="",style="solid", color="black", weight=3]; 27[label="List.genericSplitAt3 (Pos (Succ vzz300)) []",fontsize=16,color="black",shape="box"];27 -> 31[label="",style="solid", color="black", weight=3]; 28[label="List.genericSplitAt3 (Neg (Succ vzz300)) (vzz40 : vzz41)",fontsize=16,color="black",shape="box"];28 -> 32[label="",style="solid", color="black", weight=3]; 29[label="List.genericSplitAt3 (Neg (Succ vzz300)) []",fontsize=16,color="black",shape="box"];29 -> 33[label="",style="solid", color="black", weight=3]; 30[label="List.genericSplitAt2 (Pos (Succ vzz300)) (vzz40 : vzz41)",fontsize=16,color="black",shape="box"];30 -> 34[label="",style="solid", color="black", weight=3]; 31[label="([],[])",fontsize=16,color="green",shape="box"];32[label="List.genericSplitAt2 (Neg (Succ vzz300)) (vzz40 : vzz41)",fontsize=16,color="black",shape="box"];32 -> 35[label="",style="solid", color="black", weight=3]; 33[label="([],[])",fontsize=16,color="green",shape="box"];34[label="List.genericSplitAt2GenericSplitAt1 (Pos (Succ vzz300)) vzz41 (Pos (Succ vzz300)) vzz40 vzz41 (Pos (Succ vzz300) > fromInt (Pos Zero))",fontsize=16,color="black",shape="box"];34 -> 36[label="",style="solid", color="black", weight=3]; 35[label="List.genericSplitAt2GenericSplitAt1 (Neg (Succ vzz300)) vzz41 (Neg (Succ vzz300)) vzz40 vzz41 (Neg (Succ vzz300) > fromInt (Pos Zero))",fontsize=16,color="black",shape="box"];35 -> 37[label="",style="solid", color="black", weight=3]; 36[label="List.genericSplitAt2GenericSplitAt1 (Pos (Succ vzz300)) vzz41 (Pos (Succ vzz300)) vzz40 vzz41 (compare (Pos (Succ vzz300)) (fromInt (Pos Zero)) == GT)",fontsize=16,color="black",shape="box"];36 -> 38[label="",style="solid", color="black", weight=3]; 37[label="List.genericSplitAt2GenericSplitAt1 (Neg (Succ vzz300)) vzz41 (Neg (Succ vzz300)) vzz40 vzz41 (compare (Neg (Succ vzz300)) (fromInt (Pos Zero)) == GT)",fontsize=16,color="black",shape="box"];37 -> 39[label="",style="solid", color="black", weight=3]; 38[label="List.genericSplitAt2GenericSplitAt1 (Pos (Succ vzz300)) vzz41 (Pos (Succ vzz300)) vzz40 vzz41 (primCmpInt (Pos (Succ vzz300)) (fromInt (Pos Zero)) == GT)",fontsize=16,color="black",shape="box"];38 -> 40[label="",style="solid", color="black", weight=3]; 39[label="List.genericSplitAt2GenericSplitAt1 (Neg (Succ vzz300)) vzz41 (Neg (Succ vzz300)) vzz40 vzz41 (primCmpInt (Neg (Succ vzz300)) (fromInt (Pos Zero)) == GT)",fontsize=16,color="black",shape="box"];39 -> 41[label="",style="solid", color="black", weight=3]; 40[label="List.genericSplitAt2GenericSplitAt1 (Pos (Succ vzz300)) vzz41 (Pos (Succ vzz300)) vzz40 vzz41 (primCmpInt (Pos (Succ vzz300)) (Pos Zero) == GT)",fontsize=16,color="black",shape="box"];40 -> 42[label="",style="solid", color="black", weight=3]; 41[label="List.genericSplitAt2GenericSplitAt1 (Neg (Succ vzz300)) vzz41 (Neg (Succ vzz300)) vzz40 vzz41 (primCmpInt (Neg (Succ vzz300)) (Pos Zero) == GT)",fontsize=16,color="black",shape="box"];41 -> 43[label="",style="solid", color="black", weight=3]; 42[label="List.genericSplitAt2GenericSplitAt1 (Pos (Succ vzz300)) vzz41 (Pos (Succ vzz300)) vzz40 vzz41 (primCmpNat (Succ vzz300) Zero == GT)",fontsize=16,color="black",shape="box"];42 -> 44[label="",style="solid", color="black", weight=3]; 43[label="List.genericSplitAt2GenericSplitAt1 (Neg (Succ vzz300)) vzz41 (Neg (Succ vzz300)) vzz40 vzz41 (LT == GT)",fontsize=16,color="black",shape="box"];43 -> 45[label="",style="solid", color="black", weight=3]; 44[label="List.genericSplitAt2GenericSplitAt1 (Pos (Succ vzz300)) vzz41 (Pos (Succ vzz300)) vzz40 vzz41 (GT == GT)",fontsize=16,color="black",shape="box"];44 -> 46[label="",style="solid", color="black", weight=3]; 45[label="List.genericSplitAt2GenericSplitAt1 (Neg (Succ vzz300)) vzz41 (Neg (Succ vzz300)) vzz40 vzz41 False",fontsize=16,color="black",shape="box"];45 -> 47[label="",style="solid", color="black", weight=3]; 46[label="List.genericSplitAt2GenericSplitAt1 (Pos (Succ vzz300)) vzz41 (Pos (Succ vzz300)) vzz40 vzz41 True",fontsize=16,color="black",shape="box"];46 -> 48[label="",style="solid", color="black", weight=3]; 47[label="List.genericSplitAt0 (Neg (Succ vzz300)) (vzz40 : vzz41)",fontsize=16,color="black",shape="box"];47 -> 49[label="",style="solid", color="black", weight=3]; 48[label="(vzz40 : List.genericSplitAt2Xs' (Pos (Succ vzz300)) vzz41,List.genericSplitAt2Xs'' (Pos (Succ vzz300)) vzz41)",fontsize=16,color="green",shape="box"];48 -> 50[label="",style="dashed", color="green", weight=3]; 48 -> 51[label="",style="dashed", color="green", weight=3]; 49[label="error []",fontsize=16,color="black",shape="box"];49 -> 52[label="",style="solid", color="black", weight=3]; 50[label="List.genericSplitAt2Xs' (Pos (Succ vzz300)) vzz41",fontsize=16,color="black",shape="box"];50 -> 53[label="",style="solid", color="black", weight=3]; 51[label="List.genericSplitAt2Xs'' (Pos (Succ vzz300)) vzz41",fontsize=16,color="black",shape="box"];51 -> 54[label="",style="solid", color="black", weight=3]; 52[label="error []",fontsize=16,color="red",shape="box"];53 -> 57[label="",style="dashed", color="red", weight=0]; 53[label="List.genericSplitAt2Xs'0 (Pos (Succ vzz300)) vzz41 (List.genericSplitAt2Vv9 (Pos (Succ vzz300)) vzz41)",fontsize=16,color="magenta"];53 -> 58[label="",style="dashed", color="magenta", weight=3]; 54 -> 62[label="",style="dashed", color="red", weight=0]; 54[label="List.genericSplitAt2Xs''0 (Pos (Succ vzz300)) vzz41 (List.genericSplitAt2Vv9 (Pos (Succ vzz300)) vzz41)",fontsize=16,color="magenta"];54 -> 63[label="",style="dashed", color="magenta", weight=3]; 58[label="List.genericSplitAt2Vv9 (Pos (Succ vzz300)) vzz41",fontsize=16,color="black",shape="triangle"];58 -> 60[label="",style="solid", color="black", weight=3]; 57[label="List.genericSplitAt2Xs'0 (Pos (Succ vzz300)) vzz41 vzz5",fontsize=16,color="burlywood",shape="triangle"];88[label="vzz5/(vzz50,vzz51)",fontsize=10,color="white",style="solid",shape="box"];57 -> 88[label="",style="solid", color="burlywood", weight=9]; 88 -> 61[label="",style="solid", color="burlywood", weight=3]; 63 -> 58[label="",style="dashed", color="red", weight=0]; 63[label="List.genericSplitAt2Vv9 (Pos (Succ vzz300)) vzz41",fontsize=16,color="magenta"];62[label="List.genericSplitAt2Xs''0 (Pos (Succ vzz300)) vzz41 vzz6",fontsize=16,color="burlywood",shape="triangle"];89[label="vzz6/(vzz60,vzz61)",fontsize=10,color="white",style="solid",shape="box"];62 -> 89[label="",style="solid", color="burlywood", weight=9]; 89 -> 65[label="",style="solid", color="burlywood", weight=3]; 60 -> 4[label="",style="dashed", color="red", weight=0]; 60[label="List.genericSplitAt (Pos (Succ vzz300) - fromInt (Pos (Succ Zero))) vzz41",fontsize=16,color="magenta"];60 -> 66[label="",style="dashed", color="magenta", weight=3]; 60 -> 67[label="",style="dashed", color="magenta", weight=3]; 61[label="List.genericSplitAt2Xs'0 (Pos (Succ vzz300)) vzz41 (vzz50,vzz51)",fontsize=16,color="black",shape="box"];61 -> 68[label="",style="solid", color="black", weight=3]; 65[label="List.genericSplitAt2Xs''0 (Pos (Succ vzz300)) vzz41 (vzz60,vzz61)",fontsize=16,color="black",shape="box"];65 -> 69[label="",style="solid", color="black", weight=3]; 66[label="vzz41",fontsize=16,color="green",shape="box"];67[label="Pos (Succ vzz300) - fromInt (Pos (Succ Zero))",fontsize=16,color="black",shape="box"];67 -> 70[label="",style="solid", color="black", weight=3]; 68[label="vzz50",fontsize=16,color="green",shape="box"];69[label="vzz61",fontsize=16,color="green",shape="box"];70[label="primMinusInt (Pos (Succ vzz300)) (fromInt (Pos (Succ Zero)))",fontsize=16,color="black",shape="box"];70 -> 71[label="",style="solid", color="black", weight=3]; 71[label="primMinusInt (Pos (Succ vzz300)) (Pos (Succ Zero))",fontsize=16,color="black",shape="box"];71 -> 72[label="",style="solid", color="black", weight=3]; 72[label="primMinusNat (Succ vzz300) (Succ Zero)",fontsize=16,color="black",shape="box"];72 -> 73[label="",style="solid", color="black", weight=3]; 73[label="primMinusNat vzz300 Zero",fontsize=16,color="burlywood",shape="box"];90[label="vzz300/Succ vzz3000",fontsize=10,color="white",style="solid",shape="box"];73 -> 90[label="",style="solid", color="burlywood", weight=9]; 90 -> 74[label="",style="solid", color="burlywood", weight=3]; 91[label="vzz300/Zero",fontsize=10,color="white",style="solid",shape="box"];73 -> 91[label="",style="solid", color="burlywood", weight=9]; 91 -> 75[label="",style="solid", color="burlywood", weight=3]; 74[label="primMinusNat (Succ vzz3000) Zero",fontsize=16,color="black",shape="box"];74 -> 76[label="",style="solid", color="black", weight=3]; 75[label="primMinusNat Zero Zero",fontsize=16,color="black",shape="box"];75 -> 77[label="",style="solid", color="black", weight=3]; 76[label="Pos (Succ vzz3000)",fontsize=16,color="green",shape="box"];77[label="Pos Zero",fontsize=16,color="green",shape="box"];} ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: new_genericSplitAt2Vv9(vzz300, vzz41, ba) -> new_genericSplitAt(new_primMinusNat(vzz300), vzz41, ba) new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt2Vv9(vzz300, vzz41, ba) new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt(new_primMinusNat(vzz300), vzz41, ba) The TRS R consists of the following rules: new_primMinusNat(Succ(vzz3000)) -> Pos(Succ(vzz3000)) new_primMinusNat(Zero) -> Pos(Zero) The set Q consists of the following terms: new_primMinusNat(Succ(x0)) new_primMinusNat(Zero) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule new_genericSplitAt2Vv9(vzz300, vzz41, ba) -> new_genericSplitAt(new_primMinusNat(vzz300), vzz41, ba) at position [0] we obtained the following new rules [LPAR04]: (new_genericSplitAt2Vv9(Succ(x0), y1, y2) -> new_genericSplitAt(Pos(Succ(x0)), y1, y2),new_genericSplitAt2Vv9(Succ(x0), y1, y2) -> new_genericSplitAt(Pos(Succ(x0)), y1, y2)) (new_genericSplitAt2Vv9(Zero, y1, y2) -> new_genericSplitAt(Pos(Zero), y1, y2),new_genericSplitAt2Vv9(Zero, y1, y2) -> new_genericSplitAt(Pos(Zero), y1, y2)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt2Vv9(vzz300, vzz41, ba) new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt(new_primMinusNat(vzz300), vzz41, ba) new_genericSplitAt2Vv9(Succ(x0), y1, y2) -> new_genericSplitAt(Pos(Succ(x0)), y1, y2) new_genericSplitAt2Vv9(Zero, y1, y2) -> new_genericSplitAt(Pos(Zero), y1, y2) The TRS R consists of the following rules: new_primMinusNat(Succ(vzz3000)) -> Pos(Succ(vzz3000)) new_primMinusNat(Zero) -> Pos(Zero) The set Q consists of the following terms: new_primMinusNat(Succ(x0)) new_primMinusNat(Zero) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: new_genericSplitAt2Vv9(Succ(x0), y1, y2) -> new_genericSplitAt(Pos(Succ(x0)), y1, y2) new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt2Vv9(vzz300, vzz41, ba) new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt(new_primMinusNat(vzz300), vzz41, ba) The TRS R consists of the following rules: new_primMinusNat(Succ(vzz3000)) -> Pos(Succ(vzz3000)) new_primMinusNat(Zero) -> Pos(Zero) The set Q consists of the following terms: new_primMinusNat(Succ(x0)) new_primMinusNat(Zero) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt(new_primMinusNat(vzz300), vzz41, ba) at position [0] we obtained the following new rules [LPAR04]: (new_genericSplitAt(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericSplitAt(Pos(Succ(x0)), y2, y3),new_genericSplitAt(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericSplitAt(Pos(Succ(x0)), y2, y3)) (new_genericSplitAt(Pos(Succ(Zero)), :(y1, y2), y3) -> new_genericSplitAt(Pos(Zero), y2, y3),new_genericSplitAt(Pos(Succ(Zero)), :(y1, y2), y3) -> new_genericSplitAt(Pos(Zero), y2, y3)) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: new_genericSplitAt2Vv9(Succ(x0), y1, y2) -> new_genericSplitAt(Pos(Succ(x0)), y1, y2) new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt2Vv9(vzz300, vzz41, ba) new_genericSplitAt(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericSplitAt(Pos(Succ(x0)), y2, y3) new_genericSplitAt(Pos(Succ(Zero)), :(y1, y2), y3) -> new_genericSplitAt(Pos(Zero), y2, y3) The TRS R consists of the following rules: new_primMinusNat(Succ(vzz3000)) -> Pos(Succ(vzz3000)) new_primMinusNat(Zero) -> Pos(Zero) The set Q consists of the following terms: new_primMinusNat(Succ(x0)) new_primMinusNat(Zero) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt2Vv9(vzz300, vzz41, ba) new_genericSplitAt2Vv9(Succ(x0), y1, y2) -> new_genericSplitAt(Pos(Succ(x0)), y1, y2) new_genericSplitAt(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericSplitAt(Pos(Succ(x0)), y2, y3) The TRS R consists of the following rules: new_primMinusNat(Succ(vzz3000)) -> Pos(Succ(vzz3000)) new_primMinusNat(Zero) -> Pos(Zero) The set Q consists of the following terms: new_primMinusNat(Succ(x0)) new_primMinusNat(Zero) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt2Vv9(vzz300, vzz41, ba) new_genericSplitAt2Vv9(Succ(x0), y1, y2) -> new_genericSplitAt(Pos(Succ(x0)), y1, y2) new_genericSplitAt(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericSplitAt(Pos(Succ(x0)), y2, y3) R is empty. The set Q consists of the following terms: new_primMinusNat(Succ(x0)) new_primMinusNat(Zero) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. new_primMinusNat(Succ(x0)) new_primMinusNat(Zero) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt2Vv9(vzz300, vzz41, ba) new_genericSplitAt2Vv9(Succ(x0), y1, y2) -> new_genericSplitAt(Pos(Succ(x0)), y1, y2) new_genericSplitAt(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericSplitAt(Pos(Succ(x0)), y2, y3) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *new_genericSplitAt2Vv9(Succ(x0), y1, y2) -> new_genericSplitAt(Pos(Succ(x0)), y1, y2) The graph contains the following edges 2 >= 2, 3 >= 3 *new_genericSplitAt(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericSplitAt(Pos(Succ(x0)), y2, y3) The graph contains the following edges 2 > 2, 3 >= 3 *new_genericSplitAt(Pos(Succ(vzz300)), :(vzz40, vzz41), ba) -> new_genericSplitAt2Vv9(vzz300, vzz41, ba) The graph contains the following edges 1 > 1, 2 > 2, 3 >= 3 ---------------------------------------- (30) YES