10.90/4.44 YES 12.78/4.96 proof of /export/starexec/sandbox2/benchmark/theBenchmark.hs 12.78/4.96 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 12.78/4.96 12.78/4.96 12.78/4.96 H-Termination with start terms of the given HASKELL could be proven: 12.78/4.96 12.78/4.96 (0) HASKELL 12.78/4.96 (1) BR [EQUIVALENT, 0 ms] 12.78/4.96 (2) HASKELL 12.78/4.96 (3) COR [EQUIVALENT, 11 ms] 12.78/4.96 (4) HASKELL 12.78/4.96 (5) NumRed [SOUND, 0 ms] 12.78/4.96 (6) HASKELL 12.78/4.96 (7) Narrow [SOUND, 0 ms] 12.78/4.96 (8) QDP 12.78/4.96 (9) TransformationProof [EQUIVALENT, 0 ms] 12.78/4.96 (10) QDP 12.78/4.96 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 12.78/4.96 (12) QDP 12.78/4.96 (13) UsableRulesProof [EQUIVALENT, 0 ms] 12.78/4.96 (14) QDP 12.78/4.96 (15) QReductionProof [EQUIVALENT, 0 ms] 12.78/4.96 (16) QDP 12.78/4.96 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.78/4.96 (18) YES 12.78/4.96 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (0) 12.78/4.96 Obligation: 12.78/4.96 mainModule Main 12.78/4.96 module Maybe where { 12.78/4.96 import qualified List; 12.78/4.96 import qualified Main; 12.78/4.96 import qualified Prelude; 12.78/4.96 } 12.78/4.96 module List where { 12.78/4.96 import qualified Main; 12.78/4.96 import qualified Maybe; 12.78/4.96 import qualified Prelude; 12.78/4.96 genericDrop :: Integral b => b -> [a] -> [a]; 12.78/4.96 genericDrop 0 xs = xs; 12.78/4.96 genericDrop _ [] = []; 12.78/4.96 genericDrop n (_ : xs) | n > 0 = genericDrop (n - 1) xs; 12.78/4.96 genericDrop _ _ = error []; 12.78/4.96 12.78/4.96 } 12.78/4.96 module Main where { 12.78/4.96 import qualified List; 12.78/4.96 import qualified Maybe; 12.78/4.96 import qualified Prelude; 12.78/4.96 } 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (1) BR (EQUIVALENT) 12.78/4.96 Replaced joker patterns by fresh variables and removed binding patterns. 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (2) 12.78/4.96 Obligation: 12.78/4.96 mainModule Main 12.78/4.96 module Maybe where { 12.78/4.96 import qualified List; 12.78/4.96 import qualified Main; 12.78/4.96 import qualified Prelude; 12.78/4.96 } 12.78/4.96 module List where { 12.78/4.96 import qualified Main; 12.78/4.96 import qualified Maybe; 12.78/4.96 import qualified Prelude; 12.78/4.96 genericDrop :: Integral a => a -> [b] -> [b]; 12.78/4.96 genericDrop 0 xs = xs; 12.78/4.96 genericDrop xw [] = []; 12.78/4.96 genericDrop n (xx : xs) | n > 0 = genericDrop (n - 1) xs; 12.78/4.96 genericDrop xy xz = error []; 12.78/4.96 12.78/4.96 } 12.78/4.96 module Main where { 12.78/4.96 import qualified List; 12.78/4.96 import qualified Maybe; 12.78/4.96 import qualified Prelude; 12.78/4.96 } 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (3) COR (EQUIVALENT) 12.78/4.96 Cond Reductions: 12.78/4.96 The following Function with conditions 12.78/4.96 "undefined |Falseundefined; 12.78/4.96 " 12.78/4.96 is transformed to 12.78/4.96 "undefined = undefined1; 12.78/4.96 " 12.78/4.96 "undefined0 True = undefined; 12.78/4.96 " 12.78/4.96 "undefined1 = undefined0 False; 12.78/4.96 " 12.78/4.96 The following Function with conditions 12.78/4.96 "genericDrop 0 xs = xs; 12.78/4.96 genericDrop xw [] = []; 12.78/4.96 genericDrop n (xx : xs)|n > 0genericDrop (n - 1) xs; 12.78/4.96 genericDrop xy xz = error []; 12.78/4.96 " 12.78/4.96 is transformed to 12.78/4.96 "genericDrop zu xs = genericDrop5 zu xs; 12.78/4.96 genericDrop xw [] = genericDrop3 xw []; 12.78/4.96 genericDrop n (xx : xs) = genericDrop2 n (xx : xs); 12.78/4.96 genericDrop xy xz = genericDrop0 xy xz; 12.78/4.96 " 12.78/4.96 "genericDrop0 xy xz = error []; 12.78/4.96 " 12.78/4.96 "genericDrop1 n xx xs True = genericDrop (n - 1) xs; 12.78/4.96 genericDrop1 n xx xs False = genericDrop0 n (xx : xs); 12.78/4.96 " 12.78/4.96 "genericDrop2 n (xx : xs) = genericDrop1 n xx xs (n > 0); 12.78/4.96 genericDrop2 yv yw = genericDrop0 yv yw; 12.78/4.96 " 12.78/4.96 "genericDrop3 xw [] = []; 12.78/4.96 genericDrop3 yy yz = genericDrop2 yy yz; 12.78/4.96 " 12.78/4.96 "genericDrop4 True zu xs = xs; 12.78/4.96 genericDrop4 zv zw zx = genericDrop3 zw zx; 12.78/4.96 " 12.78/4.96 "genericDrop5 zu xs = genericDrop4 (zu == 0) zu xs; 12.78/4.96 genericDrop5 zy zz = genericDrop3 zy zz; 12.78/4.96 " 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (4) 12.78/4.96 Obligation: 12.78/4.96 mainModule Main 12.78/4.96 module Maybe where { 12.78/4.96 import qualified List; 12.78/4.96 import qualified Main; 12.78/4.96 import qualified Prelude; 12.78/4.96 } 12.78/4.96 module List where { 12.78/4.96 import qualified Main; 12.78/4.96 import qualified Maybe; 12.78/4.96 import qualified Prelude; 12.78/4.96 genericDrop :: Integral a => a -> [b] -> [b]; 12.78/4.96 genericDrop zu xs = genericDrop5 zu xs; 12.78/4.96 genericDrop xw [] = genericDrop3 xw []; 12.78/4.96 genericDrop n (xx : xs) = genericDrop2 n (xx : xs); 12.78/4.96 genericDrop xy xz = genericDrop0 xy xz; 12.78/4.96 12.78/4.96 genericDrop0 xy xz = error []; 12.78/4.96 12.78/4.96 genericDrop1 n xx xs True = genericDrop (n - 1) xs; 12.78/4.96 genericDrop1 n xx xs False = genericDrop0 n (xx : xs); 12.78/4.96 12.78/4.96 genericDrop2 n (xx : xs) = genericDrop1 n xx xs (n > 0); 12.78/4.96 genericDrop2 yv yw = genericDrop0 yv yw; 12.78/4.96 12.78/4.96 genericDrop3 xw [] = []; 12.78/4.96 genericDrop3 yy yz = genericDrop2 yy yz; 12.78/4.96 12.78/4.96 genericDrop4 True zu xs = xs; 12.78/4.96 genericDrop4 zv zw zx = genericDrop3 zw zx; 12.78/4.96 12.78/4.96 genericDrop5 zu xs = genericDrop4 (zu == 0) zu xs; 12.78/4.96 genericDrop5 zy zz = genericDrop3 zy zz; 12.78/4.96 12.78/4.96 } 12.78/4.96 module Main where { 12.78/4.96 import qualified List; 12.78/4.96 import qualified Maybe; 12.78/4.96 import qualified Prelude; 12.78/4.96 } 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (5) NumRed (SOUND) 12.78/4.96 Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero. 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (6) 12.78/4.96 Obligation: 12.78/4.96 mainModule Main 12.78/4.96 module Maybe where { 12.78/4.96 import qualified List; 12.78/4.96 import qualified Main; 12.78/4.96 import qualified Prelude; 12.78/4.96 } 12.78/4.96 module List where { 12.78/4.96 import qualified Main; 12.78/4.96 import qualified Maybe; 12.78/4.96 import qualified Prelude; 12.78/4.96 genericDrop :: Integral a => a -> [b] -> [b]; 12.78/4.96 genericDrop zu xs = genericDrop5 zu xs; 12.78/4.96 genericDrop xw [] = genericDrop3 xw []; 12.78/4.96 genericDrop n (xx : xs) = genericDrop2 n (xx : xs); 12.78/4.96 genericDrop xy xz = genericDrop0 xy xz; 12.78/4.96 12.78/4.96 genericDrop0 xy xz = error []; 12.78/4.96 12.78/4.96 genericDrop1 n xx xs True = genericDrop (n - fromInt (Pos (Succ Zero))) xs; 12.78/4.96 genericDrop1 n xx xs False = genericDrop0 n (xx : xs); 12.78/4.96 12.78/4.96 genericDrop2 n (xx : xs) = genericDrop1 n xx xs (n > fromInt (Pos Zero)); 12.78/4.96 genericDrop2 yv yw = genericDrop0 yv yw; 12.78/4.96 12.78/4.96 genericDrop3 xw [] = []; 12.78/4.96 genericDrop3 yy yz = genericDrop2 yy yz; 12.78/4.96 12.78/4.96 genericDrop4 True zu xs = xs; 12.78/4.96 genericDrop4 zv zw zx = genericDrop3 zw zx; 12.78/4.96 12.78/4.96 genericDrop5 zu xs = genericDrop4 (zu == fromInt (Pos Zero)) zu xs; 12.78/4.96 genericDrop5 zy zz = genericDrop3 zy zz; 12.78/4.96 12.78/4.96 } 12.78/4.96 module Main where { 12.78/4.96 import qualified List; 12.78/4.96 import qualified Maybe; 12.78/4.96 import qualified Prelude; 12.78/4.96 } 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (7) Narrow (SOUND) 12.78/4.96 Haskell To QDPs 12.78/4.96 12.78/4.96 digraph dp_graph { 12.78/4.96 node [outthreshold=100, inthreshold=100];1[label="List.genericDrop",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 12.78/4.96 3[label="List.genericDrop vuu3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 12.78/4.96 4[label="List.genericDrop vuu3 vuu4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 12.78/4.96 5[label="List.genericDrop5 vuu3 vuu4",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3]; 12.78/4.96 6[label="List.genericDrop4 (vuu3 == fromInt (Pos Zero)) vuu3 vuu4",fontsize=16,color="black",shape="box"];6 -> 7[label="",style="solid", color="black", weight=3]; 12.78/4.96 7[label="List.genericDrop4 (primEqInt vuu3 (fromInt (Pos Zero))) vuu3 vuu4",fontsize=16,color="burlywood",shape="box"];61[label="vuu3/Pos vuu30",fontsize=10,color="white",style="solid",shape="box"];7 -> 61[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 61 -> 8[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 62[label="vuu3/Neg vuu30",fontsize=10,color="white",style="solid",shape="box"];7 -> 62[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 62 -> 9[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 8[label="List.genericDrop4 (primEqInt (Pos vuu30) (fromInt (Pos Zero))) (Pos vuu30) vuu4",fontsize=16,color="burlywood",shape="box"];63[label="vuu30/Succ vuu300",fontsize=10,color="white",style="solid",shape="box"];8 -> 63[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 63 -> 10[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 64[label="vuu30/Zero",fontsize=10,color="white",style="solid",shape="box"];8 -> 64[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 64 -> 11[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 9[label="List.genericDrop4 (primEqInt (Neg vuu30) (fromInt (Pos Zero))) (Neg vuu30) vuu4",fontsize=16,color="burlywood",shape="box"];65[label="vuu30/Succ vuu300",fontsize=10,color="white",style="solid",shape="box"];9 -> 65[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 65 -> 12[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 66[label="vuu30/Zero",fontsize=10,color="white",style="solid",shape="box"];9 -> 66[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 66 -> 13[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 10[label="List.genericDrop4 (primEqInt (Pos (Succ vuu300)) (fromInt (Pos Zero))) (Pos (Succ vuu300)) vuu4",fontsize=16,color="black",shape="box"];10 -> 14[label="",style="solid", color="black", weight=3]; 12.78/4.96 11[label="List.genericDrop4 (primEqInt (Pos Zero) (fromInt (Pos Zero))) (Pos Zero) vuu4",fontsize=16,color="black",shape="box"];11 -> 15[label="",style="solid", color="black", weight=3]; 12.78/4.96 12[label="List.genericDrop4 (primEqInt (Neg (Succ vuu300)) (fromInt (Pos Zero))) (Neg (Succ vuu300)) vuu4",fontsize=16,color="black",shape="box"];12 -> 16[label="",style="solid", color="black", weight=3]; 12.78/4.96 13[label="List.genericDrop4 (primEqInt (Neg Zero) (fromInt (Pos Zero))) (Neg Zero) vuu4",fontsize=16,color="black",shape="box"];13 -> 17[label="",style="solid", color="black", weight=3]; 12.78/4.96 14[label="List.genericDrop4 (primEqInt (Pos (Succ vuu300)) (Pos Zero)) (Pos (Succ vuu300)) vuu4",fontsize=16,color="black",shape="box"];14 -> 18[label="",style="solid", color="black", weight=3]; 12.78/4.96 15[label="List.genericDrop4 (primEqInt (Pos Zero) (Pos Zero)) (Pos Zero) vuu4",fontsize=16,color="black",shape="box"];15 -> 19[label="",style="solid", color="black", weight=3]; 12.78/4.96 16[label="List.genericDrop4 (primEqInt (Neg (Succ vuu300)) (Pos Zero)) (Neg (Succ vuu300)) vuu4",fontsize=16,color="black",shape="box"];16 -> 20[label="",style="solid", color="black", weight=3]; 12.78/4.96 17[label="List.genericDrop4 (primEqInt (Neg Zero) (Pos Zero)) (Neg Zero) vuu4",fontsize=16,color="black",shape="box"];17 -> 21[label="",style="solid", color="black", weight=3]; 12.78/4.96 18[label="List.genericDrop4 False (Pos (Succ vuu300)) vuu4",fontsize=16,color="black",shape="box"];18 -> 22[label="",style="solid", color="black", weight=3]; 12.78/4.96 19[label="List.genericDrop4 True (Pos Zero) vuu4",fontsize=16,color="black",shape="box"];19 -> 23[label="",style="solid", color="black", weight=3]; 12.78/4.96 20[label="List.genericDrop4 False (Neg (Succ vuu300)) vuu4",fontsize=16,color="black",shape="box"];20 -> 24[label="",style="solid", color="black", weight=3]; 12.78/4.96 21[label="List.genericDrop4 True (Neg Zero) vuu4",fontsize=16,color="black",shape="box"];21 -> 25[label="",style="solid", color="black", weight=3]; 12.78/4.96 22[label="List.genericDrop3 (Pos (Succ vuu300)) vuu4",fontsize=16,color="burlywood",shape="box"];67[label="vuu4/vuu40 : vuu41",fontsize=10,color="white",style="solid",shape="box"];22 -> 67[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 67 -> 26[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 68[label="vuu4/[]",fontsize=10,color="white",style="solid",shape="box"];22 -> 68[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 68 -> 27[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 23[label="vuu4",fontsize=16,color="green",shape="box"];24[label="List.genericDrop3 (Neg (Succ vuu300)) vuu4",fontsize=16,color="burlywood",shape="box"];69[label="vuu4/vuu40 : vuu41",fontsize=10,color="white",style="solid",shape="box"];24 -> 69[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 69 -> 28[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 70[label="vuu4/[]",fontsize=10,color="white",style="solid",shape="box"];24 -> 70[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 70 -> 29[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 25[label="vuu4",fontsize=16,color="green",shape="box"];26[label="List.genericDrop3 (Pos (Succ vuu300)) (vuu40 : vuu41)",fontsize=16,color="black",shape="box"];26 -> 30[label="",style="solid", color="black", weight=3]; 12.78/4.96 27[label="List.genericDrop3 (Pos (Succ vuu300)) []",fontsize=16,color="black",shape="box"];27 -> 31[label="",style="solid", color="black", weight=3]; 12.78/4.96 28[label="List.genericDrop3 (Neg (Succ vuu300)) (vuu40 : vuu41)",fontsize=16,color="black",shape="box"];28 -> 32[label="",style="solid", color="black", weight=3]; 12.78/4.96 29[label="List.genericDrop3 (Neg (Succ vuu300)) []",fontsize=16,color="black",shape="box"];29 -> 33[label="",style="solid", color="black", weight=3]; 12.78/4.96 30[label="List.genericDrop2 (Pos (Succ vuu300)) (vuu40 : vuu41)",fontsize=16,color="black",shape="box"];30 -> 34[label="",style="solid", color="black", weight=3]; 12.78/4.96 31[label="[]",fontsize=16,color="green",shape="box"];32[label="List.genericDrop2 (Neg (Succ vuu300)) (vuu40 : vuu41)",fontsize=16,color="black",shape="box"];32 -> 35[label="",style="solid", color="black", weight=3]; 12.78/4.96 33[label="[]",fontsize=16,color="green",shape="box"];34[label="List.genericDrop1 (Pos (Succ vuu300)) vuu40 vuu41 (Pos (Succ vuu300) > fromInt (Pos Zero))",fontsize=16,color="black",shape="box"];34 -> 36[label="",style="solid", color="black", weight=3]; 12.78/4.96 35[label="List.genericDrop1 (Neg (Succ vuu300)) vuu40 vuu41 (Neg (Succ vuu300) > fromInt (Pos Zero))",fontsize=16,color="black",shape="box"];35 -> 37[label="",style="solid", color="black", weight=3]; 12.78/4.96 36[label="List.genericDrop1 (Pos (Succ vuu300)) vuu40 vuu41 (compare (Pos (Succ vuu300)) (fromInt (Pos Zero)) == GT)",fontsize=16,color="black",shape="box"];36 -> 38[label="",style="solid", color="black", weight=3]; 12.78/4.96 37[label="List.genericDrop1 (Neg (Succ vuu300)) vuu40 vuu41 (compare (Neg (Succ vuu300)) (fromInt (Pos Zero)) == GT)",fontsize=16,color="black",shape="box"];37 -> 39[label="",style="solid", color="black", weight=3]; 12.78/4.96 38[label="List.genericDrop1 (Pos (Succ vuu300)) vuu40 vuu41 (primCmpInt (Pos (Succ vuu300)) (fromInt (Pos Zero)) == GT)",fontsize=16,color="black",shape="box"];38 -> 40[label="",style="solid", color="black", weight=3]; 12.78/4.96 39[label="List.genericDrop1 (Neg (Succ vuu300)) vuu40 vuu41 (primCmpInt (Neg (Succ vuu300)) (fromInt (Pos Zero)) == GT)",fontsize=16,color="black",shape="box"];39 -> 41[label="",style="solid", color="black", weight=3]; 12.78/4.96 40[label="List.genericDrop1 (Pos (Succ vuu300)) vuu40 vuu41 (primCmpInt (Pos (Succ vuu300)) (Pos Zero) == GT)",fontsize=16,color="black",shape="box"];40 -> 42[label="",style="solid", color="black", weight=3]; 12.78/4.96 41[label="List.genericDrop1 (Neg (Succ vuu300)) vuu40 vuu41 (primCmpInt (Neg (Succ vuu300)) (Pos Zero) == GT)",fontsize=16,color="black",shape="box"];41 -> 43[label="",style="solid", color="black", weight=3]; 12.78/4.96 42[label="List.genericDrop1 (Pos (Succ vuu300)) vuu40 vuu41 (primCmpNat (Succ vuu300) Zero == GT)",fontsize=16,color="black",shape="box"];42 -> 44[label="",style="solid", color="black", weight=3]; 12.78/4.96 43[label="List.genericDrop1 (Neg (Succ vuu300)) vuu40 vuu41 (LT == GT)",fontsize=16,color="black",shape="box"];43 -> 45[label="",style="solid", color="black", weight=3]; 12.78/4.96 44[label="List.genericDrop1 (Pos (Succ vuu300)) vuu40 vuu41 (GT == GT)",fontsize=16,color="black",shape="box"];44 -> 46[label="",style="solid", color="black", weight=3]; 12.78/4.96 45[label="List.genericDrop1 (Neg (Succ vuu300)) vuu40 vuu41 False",fontsize=16,color="black",shape="box"];45 -> 47[label="",style="solid", color="black", weight=3]; 12.78/4.96 46[label="List.genericDrop1 (Pos (Succ vuu300)) vuu40 vuu41 True",fontsize=16,color="black",shape="box"];46 -> 48[label="",style="solid", color="black", weight=3]; 12.78/4.96 47[label="List.genericDrop0 (Neg (Succ vuu300)) (vuu40 : vuu41)",fontsize=16,color="black",shape="box"];47 -> 49[label="",style="solid", color="black", weight=3]; 12.78/4.96 48 -> 4[label="",style="dashed", color="red", weight=0]; 12.78/4.96 48[label="List.genericDrop (Pos (Succ vuu300) - fromInt (Pos (Succ Zero))) vuu41",fontsize=16,color="magenta"];48 -> 50[label="",style="dashed", color="magenta", weight=3]; 12.78/4.96 48 -> 51[label="",style="dashed", color="magenta", weight=3]; 12.78/4.96 49[label="error []",fontsize=16,color="black",shape="box"];49 -> 52[label="",style="solid", color="black", weight=3]; 12.78/4.96 50[label="Pos (Succ vuu300) - fromInt (Pos (Succ Zero))",fontsize=16,color="black",shape="box"];50 -> 53[label="",style="solid", color="black", weight=3]; 12.78/4.96 51[label="vuu41",fontsize=16,color="green",shape="box"];52[label="error []",fontsize=16,color="red",shape="box"];53[label="primMinusInt (Pos (Succ vuu300)) (fromInt (Pos (Succ Zero)))",fontsize=16,color="black",shape="box"];53 -> 54[label="",style="solid", color="black", weight=3]; 12.78/4.96 54[label="primMinusInt (Pos (Succ vuu300)) (Pos (Succ Zero))",fontsize=16,color="black",shape="box"];54 -> 55[label="",style="solid", color="black", weight=3]; 12.78/4.96 55[label="primMinusNat (Succ vuu300) (Succ Zero)",fontsize=16,color="black",shape="box"];55 -> 56[label="",style="solid", color="black", weight=3]; 12.78/4.96 56[label="primMinusNat vuu300 Zero",fontsize=16,color="burlywood",shape="box"];71[label="vuu300/Succ vuu3000",fontsize=10,color="white",style="solid",shape="box"];56 -> 71[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 71 -> 57[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 72[label="vuu300/Zero",fontsize=10,color="white",style="solid",shape="box"];56 -> 72[label="",style="solid", color="burlywood", weight=9]; 12.78/4.96 72 -> 58[label="",style="solid", color="burlywood", weight=3]; 12.78/4.96 57[label="primMinusNat (Succ vuu3000) Zero",fontsize=16,color="black",shape="box"];57 -> 59[label="",style="solid", color="black", weight=3]; 12.78/4.96 58[label="primMinusNat Zero Zero",fontsize=16,color="black",shape="box"];58 -> 60[label="",style="solid", color="black", weight=3]; 12.78/4.96 59[label="Pos (Succ vuu3000)",fontsize=16,color="green",shape="box"];60[label="Pos Zero",fontsize=16,color="green",shape="box"];} 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (8) 12.78/4.96 Obligation: 12.78/4.96 Q DP problem: 12.78/4.96 The TRS P consists of the following rules: 12.78/4.96 12.78/4.96 new_genericDrop(Pos(Succ(vuu300)), :(vuu40, vuu41), ba) -> new_genericDrop(new_primMinusNat(vuu300), vuu41, ba) 12.78/4.96 12.78/4.96 The TRS R consists of the following rules: 12.78/4.96 12.78/4.96 new_primMinusNat(Succ(vuu3000)) -> Pos(Succ(vuu3000)) 12.78/4.96 new_primMinusNat(Zero) -> Pos(Zero) 12.78/4.96 12.78/4.96 The set Q consists of the following terms: 12.78/4.96 12.78/4.96 new_primMinusNat(Succ(x0)) 12.78/4.96 new_primMinusNat(Zero) 12.78/4.96 12.78/4.96 We have to consider all minimal (P,Q,R)-chains. 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (9) TransformationProof (EQUIVALENT) 12.78/4.96 By narrowing [LPAR04] the rule new_genericDrop(Pos(Succ(vuu300)), :(vuu40, vuu41), ba) -> new_genericDrop(new_primMinusNat(vuu300), vuu41, ba) at position [0] we obtained the following new rules [LPAR04]: 12.78/4.96 12.78/4.96 (new_genericDrop(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericDrop(Pos(Succ(x0)), y2, y3),new_genericDrop(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericDrop(Pos(Succ(x0)), y2, y3)) 12.78/4.96 (new_genericDrop(Pos(Succ(Zero)), :(y1, y2), y3) -> new_genericDrop(Pos(Zero), y2, y3),new_genericDrop(Pos(Succ(Zero)), :(y1, y2), y3) -> new_genericDrop(Pos(Zero), y2, y3)) 12.78/4.96 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (10) 12.78/4.96 Obligation: 12.78/4.96 Q DP problem: 12.78/4.96 The TRS P consists of the following rules: 12.78/4.96 12.78/4.96 new_genericDrop(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericDrop(Pos(Succ(x0)), y2, y3) 12.78/4.96 new_genericDrop(Pos(Succ(Zero)), :(y1, y2), y3) -> new_genericDrop(Pos(Zero), y2, y3) 12.78/4.96 12.78/4.96 The TRS R consists of the following rules: 12.78/4.96 12.78/4.96 new_primMinusNat(Succ(vuu3000)) -> Pos(Succ(vuu3000)) 12.78/4.96 new_primMinusNat(Zero) -> Pos(Zero) 12.78/4.96 12.78/4.96 The set Q consists of the following terms: 12.78/4.96 12.78/4.96 new_primMinusNat(Succ(x0)) 12.78/4.96 new_primMinusNat(Zero) 12.78/4.96 12.78/4.96 We have to consider all minimal (P,Q,R)-chains. 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (11) DependencyGraphProof (EQUIVALENT) 12.78/4.96 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (12) 12.78/4.96 Obligation: 12.78/4.96 Q DP problem: 12.78/4.96 The TRS P consists of the following rules: 12.78/4.96 12.78/4.96 new_genericDrop(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericDrop(Pos(Succ(x0)), y2, y3) 12.78/4.96 12.78/4.96 The TRS R consists of the following rules: 12.78/4.96 12.78/4.96 new_primMinusNat(Succ(vuu3000)) -> Pos(Succ(vuu3000)) 12.78/4.96 new_primMinusNat(Zero) -> Pos(Zero) 12.78/4.96 12.78/4.96 The set Q consists of the following terms: 12.78/4.96 12.78/4.96 new_primMinusNat(Succ(x0)) 12.78/4.96 new_primMinusNat(Zero) 12.78/4.96 12.78/4.96 We have to consider all minimal (P,Q,R)-chains. 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (13) UsableRulesProof (EQUIVALENT) 12.78/4.96 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. 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (14) 12.78/4.96 Obligation: 12.78/4.96 Q DP problem: 12.78/4.96 The TRS P consists of the following rules: 12.78/4.96 12.78/4.96 new_genericDrop(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericDrop(Pos(Succ(x0)), y2, y3) 12.78/4.96 12.78/4.96 R is empty. 12.78/4.96 The set Q consists of the following terms: 12.78/4.96 12.78/4.96 new_primMinusNat(Succ(x0)) 12.78/4.96 new_primMinusNat(Zero) 12.78/4.96 12.78/4.96 We have to consider all minimal (P,Q,R)-chains. 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (15) QReductionProof (EQUIVALENT) 12.78/4.96 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 12.78/4.96 12.78/4.96 new_primMinusNat(Succ(x0)) 12.78/4.96 new_primMinusNat(Zero) 12.78/4.96 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (16) 12.78/4.96 Obligation: 12.78/4.96 Q DP problem: 12.78/4.96 The TRS P consists of the following rules: 12.78/4.96 12.78/4.96 new_genericDrop(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericDrop(Pos(Succ(x0)), y2, y3) 12.78/4.96 12.78/4.96 R is empty. 12.78/4.96 Q is empty. 12.78/4.96 We have to consider all minimal (P,Q,R)-chains. 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (17) QDPSizeChangeProof (EQUIVALENT) 12.78/4.96 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 12.78/4.96 12.78/4.96 From the DPs we obtained the following set of size-change graphs: 12.78/4.96 *new_genericDrop(Pos(Succ(Succ(x0))), :(y1, y2), y3) -> new_genericDrop(Pos(Succ(x0)), y2, y3) 12.78/4.96 The graph contains the following edges 2 > 2, 3 >= 3 12.78/4.96 12.78/4.96 12.78/4.96 ---------------------------------------- 12.78/4.96 12.78/4.96 (18) 12.78/4.96 YES 12.84/5.01 EOF