8.87/3.85 YES 11.09/4.47 proof of /export/starexec/sandbox2/benchmark/theBenchmark.hs 11.09/4.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 11.09/4.47 11.09/4.47 11.09/4.47 H-Termination with start terms of the given HASKELL could be proven: 11.09/4.47 11.09/4.47 (0) HASKELL 11.09/4.47 (1) LR [EQUIVALENT, 0 ms] 11.09/4.47 (2) HASKELL 11.09/4.47 (3) IFR [EQUIVALENT, 0 ms] 11.09/4.47 (4) HASKELL 11.09/4.47 (5) BR [EQUIVALENT, 0 ms] 11.09/4.47 (6) HASKELL 11.09/4.47 (7) COR [EQUIVALENT, 0 ms] 11.09/4.47 (8) HASKELL 11.09/4.47 (9) LetRed [EQUIVALENT, 10 ms] 11.09/4.47 (10) HASKELL 11.09/4.47 (11) NumRed [SOUND, 0 ms] 11.09/4.47 (12) HASKELL 11.09/4.47 (13) Narrow [SOUND, 0 ms] 11.09/4.47 (14) AND 11.09/4.47 (15) QDP 11.09/4.47 (16) DependencyGraphProof [EQUIVALENT, 0 ms] 11.09/4.47 (17) AND 11.09/4.47 (18) QDP 11.09/4.47 (19) MRRProof [EQUIVALENT, 4 ms] 11.09/4.47 (20) QDP 11.09/4.47 (21) PisEmptyProof [EQUIVALENT, 0 ms] 11.09/4.47 (22) YES 11.09/4.47 (23) QDP 11.09/4.47 (24) QDPSizeChangeProof [EQUIVALENT, 20 ms] 11.09/4.47 (25) YES 11.09/4.47 (26) QDP 11.09/4.47 (27) QDPSizeChangeProof [EQUIVALENT, 0 ms] 11.09/4.47 (28) YES 11.09/4.47 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (0) 11.09/4.47 Obligation: 11.09/4.47 mainModule Main 11.09/4.47 module Main where { 11.09/4.47 import qualified Prelude; 11.09/4.47 } 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (1) LR (EQUIVALENT) 11.09/4.47 Lambda Reductions: 11.09/4.47 The following Lambda expression 11.09/4.47 "\(m,_)->m" 11.09/4.47 is transformed to 11.09/4.47 "m0 (m,_) = m; 11.09/4.47 " 11.09/4.47 The following Lambda expression 11.09/4.47 "\(q,_)->q" 11.09/4.47 is transformed to 11.09/4.47 "q1 (q,_) = q; 11.09/4.47 " 11.09/4.47 The following Lambda expression 11.09/4.47 "\(_,r)->r" 11.09/4.47 is transformed to 11.09/4.47 "r0 (_,r) = r; 11.09/4.47 " 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (2) 11.09/4.47 Obligation: 11.09/4.47 mainModule Main 11.09/4.47 module Main where { 11.09/4.47 import qualified Prelude; 11.09/4.47 } 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (3) IFR (EQUIVALENT) 11.09/4.47 If Reductions: 11.09/4.47 The following If expression 11.09/4.47 "if primGEqNatS x y then Succ (primDivNatS (primMinusNatS x y) (Succ y)) else Zero" 11.09/4.47 is transformed to 11.09/4.47 "primDivNatS0 x y True = Succ (primDivNatS (primMinusNatS x y) (Succ y)); 11.09/4.47 primDivNatS0 x y False = Zero; 11.09/4.47 " 11.09/4.47 The following If expression 11.09/4.47 "if primGEqNatS x y then primModNatS (primMinusNatS x y) (Succ y) else Succ x" 11.09/4.47 is transformed to 11.09/4.47 "primModNatS0 x y True = primModNatS (primMinusNatS x y) (Succ y); 11.09/4.47 primModNatS0 x y False = Succ x; 11.09/4.47 " 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (4) 11.09/4.47 Obligation: 11.09/4.47 mainModule Main 11.09/4.47 module Main where { 11.09/4.47 import qualified Prelude; 11.09/4.47 } 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (5) BR (EQUIVALENT) 11.09/4.47 Replaced joker patterns by fresh variables and removed binding patterns. 11.09/4.47 11.09/4.47 Binding Reductions: 11.09/4.47 The bind variable of the following binding Pattern 11.09/4.47 "frac@(Float vz wu)" 11.09/4.47 is replaced by the following term 11.09/4.47 "Float vz wu" 11.09/4.47 The bind variable of the following binding Pattern 11.09/4.47 "frac@(Double xu xv)" 11.09/4.47 is replaced by the following term 11.09/4.47 "Double xu xv" 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (6) 11.09/4.47 Obligation: 11.09/4.47 mainModule Main 11.09/4.47 module Main where { 11.09/4.47 import qualified Prelude; 11.09/4.47 } 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (7) COR (EQUIVALENT) 11.09/4.47 Cond Reductions: 11.09/4.47 The following Function with conditions 11.09/4.47 "undefined |Falseundefined; 11.09/4.47 " 11.09/4.47 is transformed to 11.09/4.47 "undefined = undefined1; 11.09/4.47 " 11.09/4.47 "undefined0 True = undefined; 11.09/4.47 " 11.09/4.47 "undefined1 = undefined0 False; 11.09/4.47 " 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (8) 11.09/4.47 Obligation: 11.09/4.47 mainModule Main 11.09/4.47 module Main where { 11.09/4.47 import qualified Prelude; 11.09/4.47 } 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (9) LetRed (EQUIVALENT) 11.09/4.47 Let/Where Reductions: 11.09/4.47 The bindings of the following Let/Where expression 11.09/4.47 "m where { 11.09/4.47 m = m0 vu6; 11.09/4.47 ; 11.09/4.47 m0 (m,vv) = m; 11.09/4.47 ; 11.09/4.47 vu6 = properFraction x; 11.09/4.47 } 11.09/4.47 " 11.09/4.47 are unpacked to the following functions on top level 11.09/4.47 "truncateM0 xw (m,vv) = m; 11.09/4.47 " 11.09/4.47 "truncateVu6 xw = properFraction xw; 11.09/4.47 " 11.09/4.47 "truncateM xw = truncateM0 xw (truncateVu6 xw); 11.09/4.47 " 11.09/4.47 The bindings of the following Let/Where expression 11.09/4.47 "(fromIntegral q,r :% y) where { 11.09/4.47 q = q1 vu30; 11.09/4.47 ; 11.09/4.47 q1 (q,vw) = q; 11.09/4.47 ; 11.09/4.47 r = r0 vu30; 11.09/4.47 ; 11.09/4.47 r0 (vx,r) = r; 11.09/4.47 ; 11.09/4.47 vu30 = quotRem x y; 11.09/4.47 } 11.09/4.47 " 11.09/4.47 are unpacked to the following functions on top level 11.09/4.47 "properFractionR xx xy = properFractionR0 xx xy (properFractionVu30 xx xy); 11.09/4.47 " 11.09/4.47 "properFractionVu30 xx xy = quotRem xx xy; 11.09/4.47 " 11.09/4.47 "properFractionQ xx xy = properFractionQ1 xx xy (properFractionVu30 xx xy); 11.09/4.47 " 11.09/4.47 "properFractionR0 xx xy (vx,r) = r; 11.09/4.47 " 11.09/4.47 "properFractionQ1 xx xy (q,vw) = q; 11.09/4.47 " 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (10) 11.09/4.47 Obligation: 11.09/4.47 mainModule Main 11.09/4.47 module Main where { 11.09/4.47 import qualified Prelude; 11.09/4.47 } 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (11) NumRed (SOUND) 11.09/4.47 Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero. 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (12) 11.09/4.47 Obligation: 11.09/4.47 mainModule Main 11.09/4.47 module Main where { 11.09/4.47 import qualified Prelude; 11.09/4.47 } 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (13) Narrow (SOUND) 11.09/4.47 Haskell To QDPs 11.09/4.47 11.09/4.47 digraph dp_graph { 11.09/4.47 node [outthreshold=100, inthreshold=100];1[label="truncate",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 11.09/4.47 3[label="truncate xz3",fontsize=16,color="blue",shape="box"];326[label="truncate :: (Ratio a) -> Int",fontsize=10,color="white",style="solid",shape="box"];3 -> 326[label="",style="solid", color="blue", weight=9]; 11.09/4.47 326 -> 4[label="",style="solid", color="blue", weight=3]; 11.09/4.47 327[label="truncate :: Float -> Int",fontsize=10,color="white",style="solid",shape="box"];3 -> 327[label="",style="solid", color="blue", weight=9]; 11.09/4.47 327 -> 5[label="",style="solid", color="blue", weight=3]; 11.09/4.47 328[label="truncate :: Double -> Int",fontsize=10,color="white",style="solid",shape="box"];3 -> 328[label="",style="solid", color="blue", weight=9]; 11.09/4.47 328 -> 6[label="",style="solid", color="blue", weight=3]; 11.09/4.47 4[label="truncate xz3",fontsize=16,color="black",shape="box"];4 -> 7[label="",style="solid", color="black", weight=3]; 11.09/4.47 5[label="truncate xz3",fontsize=16,color="black",shape="box"];5 -> 8[label="",style="solid", color="black", weight=3]; 11.09/4.47 6[label="truncate xz3",fontsize=16,color="black",shape="box"];6 -> 9[label="",style="solid", color="black", weight=3]; 11.09/4.47 7[label="truncateM xz3",fontsize=16,color="black",shape="box"];7 -> 10[label="",style="solid", color="black", weight=3]; 11.09/4.47 8[label="truncateM xz3",fontsize=16,color="black",shape="box"];8 -> 11[label="",style="solid", color="black", weight=3]; 11.09/4.47 9[label="truncateM xz3",fontsize=16,color="black",shape="box"];9 -> 12[label="",style="solid", color="black", weight=3]; 11.09/4.47 10[label="truncateM0 xz3 (truncateVu6 xz3)",fontsize=16,color="black",shape="box"];10 -> 13[label="",style="solid", color="black", weight=3]; 11.09/4.47 11[label="truncateM0 xz3 (truncateVu6 xz3)",fontsize=16,color="black",shape="box"];11 -> 14[label="",style="solid", color="black", weight=3]; 11.09/4.47 12[label="truncateM0 xz3 (truncateVu6 xz3)",fontsize=16,color="black",shape="box"];12 -> 15[label="",style="solid", color="black", weight=3]; 11.09/4.47 13[label="truncateM0 xz3 (properFraction xz3)",fontsize=16,color="burlywood",shape="box"];329[label="xz3/xz30 :% xz31",fontsize=10,color="white",style="solid",shape="box"];13 -> 329[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 329 -> 16[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 14[label="truncateM0 xz3 (properFraction xz3)",fontsize=16,color="black",shape="box"];14 -> 17[label="",style="solid", color="black", weight=3]; 11.09/4.47 15[label="truncateM0 xz3 (properFraction xz3)",fontsize=16,color="black",shape="box"];15 -> 18[label="",style="solid", color="black", weight=3]; 11.09/4.47 16[label="truncateM0 (xz30 :% xz31) (properFraction (xz30 :% xz31))",fontsize=16,color="black",shape="box"];16 -> 19[label="",style="solid", color="black", weight=3]; 11.09/4.47 17[label="truncateM0 xz3 (floatProperFractionFloat xz3)",fontsize=16,color="burlywood",shape="box"];330[label="xz3/Float xz30 xz31",fontsize=10,color="white",style="solid",shape="box"];17 -> 330[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 330 -> 20[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 18[label="truncateM0 xz3 (floatProperFractionDouble xz3)",fontsize=16,color="burlywood",shape="box"];331[label="xz3/Double xz30 xz31",fontsize=10,color="white",style="solid",shape="box"];18 -> 331[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 331 -> 21[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 19[label="truncateM0 (xz30 :% xz31) (fromIntegral (properFractionQ xz30 xz31),properFractionR xz30 xz31 :% xz31)",fontsize=16,color="black",shape="box"];19 -> 22[label="",style="solid", color="black", weight=3]; 11.09/4.47 20[label="truncateM0 (Float xz30 xz31) (floatProperFractionFloat (Float xz30 xz31))",fontsize=16,color="black",shape="box"];20 -> 23[label="",style="solid", color="black", weight=3]; 11.09/4.47 21[label="truncateM0 (Double xz30 xz31) (floatProperFractionDouble (Double xz30 xz31))",fontsize=16,color="black",shape="box"];21 -> 24[label="",style="solid", color="black", weight=3]; 11.09/4.47 22[label="fromIntegral (properFractionQ xz30 xz31)",fontsize=16,color="black",shape="box"];22 -> 25[label="",style="solid", color="black", weight=3]; 11.09/4.47 23[label="truncateM0 (Float xz30 xz31) (fromInt (xz30 `quot` xz31),Float xz30 xz31 - fromInt (xz30 `quot` xz31))",fontsize=16,color="black",shape="box"];23 -> 26[label="",style="solid", color="black", weight=3]; 11.09/4.47 24[label="truncateM0 (Double xz30 xz31) (fromInt (xz30 `quot` xz31),Double xz30 xz31 - fromInt (xz30 `quot` xz31))",fontsize=16,color="black",shape="box"];24 -> 27[label="",style="solid", color="black", weight=3]; 11.09/4.47 25[label="fromInteger . toInteger",fontsize=16,color="black",shape="box"];25 -> 28[label="",style="solid", color="black", weight=3]; 11.09/4.47 26[label="fromInt (xz30 `quot` xz31)",fontsize=16,color="black",shape="triangle"];26 -> 29[label="",style="solid", color="black", weight=3]; 11.09/4.47 27 -> 26[label="",style="dashed", color="red", weight=0]; 11.09/4.47 27[label="fromInt (xz30 `quot` xz31)",fontsize=16,color="magenta"];27 -> 30[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 27 -> 31[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 28[label="fromInteger (toInteger (properFractionQ xz30 xz31))",fontsize=16,color="blue",shape="box"];332[label="toInteger :: Integer -> Integer",fontsize=10,color="white",style="solid",shape="box"];28 -> 332[label="",style="solid", color="blue", weight=9]; 11.09/4.47 332 -> 32[label="",style="solid", color="blue", weight=3]; 11.09/4.47 333[label="toInteger :: Int -> Integer",fontsize=10,color="white",style="solid",shape="box"];28 -> 333[label="",style="solid", color="blue", weight=9]; 11.09/4.47 333 -> 33[label="",style="solid", color="blue", weight=3]; 11.09/4.47 29[label="xz30 `quot` xz31",fontsize=16,color="black",shape="box"];29 -> 34[label="",style="solid", color="black", weight=3]; 11.09/4.47 30[label="xz30",fontsize=16,color="green",shape="box"];31[label="xz31",fontsize=16,color="green",shape="box"];32[label="fromInteger (toInteger (properFractionQ xz30 xz31))",fontsize=16,color="black",shape="box"];32 -> 35[label="",style="solid", color="black", weight=3]; 11.09/4.47 33[label="fromInteger (toInteger (properFractionQ xz30 xz31))",fontsize=16,color="black",shape="box"];33 -> 36[label="",style="solid", color="black", weight=3]; 11.09/4.47 34[label="primQuotInt xz30 xz31",fontsize=16,color="burlywood",shape="triangle"];334[label="xz30/Pos xz300",fontsize=10,color="white",style="solid",shape="box"];34 -> 334[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 334 -> 37[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 335[label="xz30/Neg xz300",fontsize=10,color="white",style="solid",shape="box"];34 -> 335[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 335 -> 38[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 35[label="fromInteger (properFractionQ xz30 xz31)",fontsize=16,color="black",shape="box"];35 -> 39[label="",style="solid", color="black", weight=3]; 11.09/4.47 36[label="fromInteger (Integer (properFractionQ xz30 xz31))",fontsize=16,color="black",shape="box"];36 -> 40[label="",style="solid", color="black", weight=3]; 11.09/4.47 37[label="primQuotInt (Pos xz300) xz31",fontsize=16,color="burlywood",shape="box"];336[label="xz31/Pos xz310",fontsize=10,color="white",style="solid",shape="box"];37 -> 336[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 336 -> 41[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 337[label="xz31/Neg xz310",fontsize=10,color="white",style="solid",shape="box"];37 -> 337[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 337 -> 42[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 38[label="primQuotInt (Neg xz300) xz31",fontsize=16,color="burlywood",shape="box"];338[label="xz31/Pos xz310",fontsize=10,color="white",style="solid",shape="box"];38 -> 338[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 338 -> 43[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 339[label="xz31/Neg xz310",fontsize=10,color="white",style="solid",shape="box"];38 -> 339[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 339 -> 44[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 39[label="fromInteger (properFractionQ1 xz30 xz31 (properFractionVu30 xz30 xz31))",fontsize=16,color="black",shape="box"];39 -> 45[label="",style="solid", color="black", weight=3]; 11.09/4.47 40[label="properFractionQ xz30 xz31",fontsize=16,color="black",shape="box"];40 -> 46[label="",style="solid", color="black", weight=3]; 11.09/4.47 41[label="primQuotInt (Pos xz300) (Pos xz310)",fontsize=16,color="burlywood",shape="box"];340[label="xz310/Succ xz3100",fontsize=10,color="white",style="solid",shape="box"];41 -> 340[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 340 -> 47[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 341[label="xz310/Zero",fontsize=10,color="white",style="solid",shape="box"];41 -> 341[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 341 -> 48[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 42[label="primQuotInt (Pos xz300) (Neg xz310)",fontsize=16,color="burlywood",shape="box"];342[label="xz310/Succ xz3100",fontsize=10,color="white",style="solid",shape="box"];42 -> 342[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 342 -> 49[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 343[label="xz310/Zero",fontsize=10,color="white",style="solid",shape="box"];42 -> 343[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 343 -> 50[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 43[label="primQuotInt (Neg xz300) (Pos xz310)",fontsize=16,color="burlywood",shape="box"];344[label="xz310/Succ xz3100",fontsize=10,color="white",style="solid",shape="box"];43 -> 344[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 344 -> 51[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 345[label="xz310/Zero",fontsize=10,color="white",style="solid",shape="box"];43 -> 345[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 345 -> 52[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 44[label="primQuotInt (Neg xz300) (Neg xz310)",fontsize=16,color="burlywood",shape="box"];346[label="xz310/Succ xz3100",fontsize=10,color="white",style="solid",shape="box"];44 -> 346[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 346 -> 53[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 347[label="xz310/Zero",fontsize=10,color="white",style="solid",shape="box"];44 -> 347[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 347 -> 54[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 45[label="fromInteger (properFractionQ1 xz30 xz31 (quotRem xz30 xz31))",fontsize=16,color="burlywood",shape="box"];348[label="xz30/Integer xz300",fontsize=10,color="white",style="solid",shape="box"];45 -> 348[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 348 -> 55[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 46[label="properFractionQ1 xz30 xz31 (properFractionVu30 xz30 xz31)",fontsize=16,color="black",shape="box"];46 -> 56[label="",style="solid", color="black", weight=3]; 11.09/4.47 47[label="primQuotInt (Pos xz300) (Pos (Succ xz3100))",fontsize=16,color="black",shape="box"];47 -> 57[label="",style="solid", color="black", weight=3]; 11.09/4.47 48[label="primQuotInt (Pos xz300) (Pos Zero)",fontsize=16,color="black",shape="box"];48 -> 58[label="",style="solid", color="black", weight=3]; 11.09/4.47 49[label="primQuotInt (Pos xz300) (Neg (Succ xz3100))",fontsize=16,color="black",shape="box"];49 -> 59[label="",style="solid", color="black", weight=3]; 11.09/4.47 50[label="primQuotInt (Pos xz300) (Neg Zero)",fontsize=16,color="black",shape="box"];50 -> 60[label="",style="solid", color="black", weight=3]; 11.09/4.47 51[label="primQuotInt (Neg xz300) (Pos (Succ xz3100))",fontsize=16,color="black",shape="box"];51 -> 61[label="",style="solid", color="black", weight=3]; 11.09/4.47 52[label="primQuotInt (Neg xz300) (Pos Zero)",fontsize=16,color="black",shape="box"];52 -> 62[label="",style="solid", color="black", weight=3]; 11.09/4.47 53[label="primQuotInt (Neg xz300) (Neg (Succ xz3100))",fontsize=16,color="black",shape="box"];53 -> 63[label="",style="solid", color="black", weight=3]; 11.09/4.47 54[label="primQuotInt (Neg xz300) (Neg Zero)",fontsize=16,color="black",shape="box"];54 -> 64[label="",style="solid", color="black", weight=3]; 11.09/4.47 55[label="fromInteger (properFractionQ1 (Integer xz300) xz31 (quotRem (Integer xz300) xz31))",fontsize=16,color="burlywood",shape="box"];349[label="xz31/Integer xz310",fontsize=10,color="white",style="solid",shape="box"];55 -> 349[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 349 -> 65[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 56[label="properFractionQ1 xz30 xz31 (quotRem xz30 xz31)",fontsize=16,color="black",shape="box"];56 -> 66[label="",style="solid", color="black", weight=3]; 11.09/4.47 57[label="Pos (primDivNatS xz300 (Succ xz3100))",fontsize=16,color="green",shape="box"];57 -> 67[label="",style="dashed", color="green", weight=3]; 11.09/4.47 58[label="error []",fontsize=16,color="black",shape="triangle"];58 -> 68[label="",style="solid", color="black", weight=3]; 11.09/4.47 59[label="Neg (primDivNatS xz300 (Succ xz3100))",fontsize=16,color="green",shape="box"];59 -> 69[label="",style="dashed", color="green", weight=3]; 11.09/4.47 60 -> 58[label="",style="dashed", color="red", weight=0]; 11.09/4.47 60[label="error []",fontsize=16,color="magenta"];61[label="Neg (primDivNatS xz300 (Succ xz3100))",fontsize=16,color="green",shape="box"];61 -> 70[label="",style="dashed", color="green", weight=3]; 11.09/4.47 62 -> 58[label="",style="dashed", color="red", weight=0]; 11.09/4.47 62[label="error []",fontsize=16,color="magenta"];63[label="Pos (primDivNatS xz300 (Succ xz3100))",fontsize=16,color="green",shape="box"];63 -> 71[label="",style="dashed", color="green", weight=3]; 11.09/4.47 64 -> 58[label="",style="dashed", color="red", weight=0]; 11.09/4.47 64[label="error []",fontsize=16,color="magenta"];65[label="fromInteger (properFractionQ1 (Integer xz300) (Integer xz310) (quotRem (Integer xz300) (Integer xz310)))",fontsize=16,color="black",shape="box"];65 -> 72[label="",style="solid", color="black", weight=3]; 11.09/4.47 66[label="properFractionQ1 xz30 xz31 (primQrmInt xz30 xz31)",fontsize=16,color="black",shape="box"];66 -> 73[label="",style="solid", color="black", weight=3]; 11.09/4.47 67[label="primDivNatS xz300 (Succ xz3100)",fontsize=16,color="burlywood",shape="triangle"];350[label="xz300/Succ xz3000",fontsize=10,color="white",style="solid",shape="box"];67 -> 350[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 350 -> 74[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 351[label="xz300/Zero",fontsize=10,color="white",style="solid",shape="box"];67 -> 351[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 351 -> 75[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 68[label="error []",fontsize=16,color="red",shape="box"];69 -> 67[label="",style="dashed", color="red", weight=0]; 11.09/4.47 69[label="primDivNatS xz300 (Succ xz3100)",fontsize=16,color="magenta"];69 -> 76[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 70 -> 67[label="",style="dashed", color="red", weight=0]; 11.09/4.47 70[label="primDivNatS xz300 (Succ xz3100)",fontsize=16,color="magenta"];70 -> 77[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 71 -> 67[label="",style="dashed", color="red", weight=0]; 11.09/4.47 71[label="primDivNatS xz300 (Succ xz3100)",fontsize=16,color="magenta"];71 -> 78[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 71 -> 79[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 72 -> 80[label="",style="dashed", color="red", weight=0]; 11.09/4.47 72[label="fromInteger (properFractionQ1 (Integer xz300) (Integer xz310) (Integer (primQuotInt xz300 xz310),Integer (primRemInt xz300 xz310)))",fontsize=16,color="magenta"];72 -> 81[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 73 -> 82[label="",style="dashed", color="red", weight=0]; 11.09/4.47 73[label="properFractionQ1 xz30 xz31 (primQuotInt xz30 xz31,primRemInt xz30 xz31)",fontsize=16,color="magenta"];73 -> 83[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 74[label="primDivNatS (Succ xz3000) (Succ xz3100)",fontsize=16,color="black",shape="box"];74 -> 84[label="",style="solid", color="black", weight=3]; 11.09/4.47 75[label="primDivNatS Zero (Succ xz3100)",fontsize=16,color="black",shape="box"];75 -> 85[label="",style="solid", color="black", weight=3]; 11.09/4.47 76[label="xz3100",fontsize=16,color="green",shape="box"];77[label="xz300",fontsize=16,color="green",shape="box"];78[label="xz300",fontsize=16,color="green",shape="box"];79[label="xz3100",fontsize=16,color="green",shape="box"];81 -> 34[label="",style="dashed", color="red", weight=0]; 11.09/4.47 81[label="primQuotInt xz300 xz310",fontsize=16,color="magenta"];81 -> 86[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 81 -> 87[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 80[label="fromInteger (properFractionQ1 (Integer xz300) (Integer xz310) (Integer xz6,Integer (primRemInt xz300 xz310)))",fontsize=16,color="black",shape="triangle"];80 -> 88[label="",style="solid", color="black", weight=3]; 11.09/4.47 83 -> 34[label="",style="dashed", color="red", weight=0]; 11.09/4.47 83[label="primQuotInt xz30 xz31",fontsize=16,color="magenta"];83 -> 89[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 83 -> 90[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 82[label="properFractionQ1 xz30 xz31 (xz7,primRemInt xz30 xz31)",fontsize=16,color="black",shape="triangle"];82 -> 91[label="",style="solid", color="black", weight=3]; 11.09/4.47 84[label="primDivNatS0 xz3000 xz3100 (primGEqNatS xz3000 xz3100)",fontsize=16,color="burlywood",shape="box"];352[label="xz3000/Succ xz30000",fontsize=10,color="white",style="solid",shape="box"];84 -> 352[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 352 -> 92[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 353[label="xz3000/Zero",fontsize=10,color="white",style="solid",shape="box"];84 -> 353[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 353 -> 93[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 85[label="Zero",fontsize=16,color="green",shape="box"];86[label="xz300",fontsize=16,color="green",shape="box"];87[label="xz310",fontsize=16,color="green",shape="box"];88[label="fromInteger (Integer xz6)",fontsize=16,color="black",shape="box"];88 -> 94[label="",style="solid", color="black", weight=3]; 11.09/4.47 89[label="xz30",fontsize=16,color="green",shape="box"];90[label="xz31",fontsize=16,color="green",shape="box"];91[label="xz7",fontsize=16,color="green",shape="box"];92[label="primDivNatS0 (Succ xz30000) xz3100 (primGEqNatS (Succ xz30000) xz3100)",fontsize=16,color="burlywood",shape="box"];354[label="xz3100/Succ xz31000",fontsize=10,color="white",style="solid",shape="box"];92 -> 354[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 354 -> 95[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 355[label="xz3100/Zero",fontsize=10,color="white",style="solid",shape="box"];92 -> 355[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 355 -> 96[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 93[label="primDivNatS0 Zero xz3100 (primGEqNatS Zero xz3100)",fontsize=16,color="burlywood",shape="box"];356[label="xz3100/Succ xz31000",fontsize=10,color="white",style="solid",shape="box"];93 -> 356[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 356 -> 97[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 357[label="xz3100/Zero",fontsize=10,color="white",style="solid",shape="box"];93 -> 357[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 357 -> 98[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 94[label="xz6",fontsize=16,color="green",shape="box"];95[label="primDivNatS0 (Succ xz30000) (Succ xz31000) (primGEqNatS (Succ xz30000) (Succ xz31000))",fontsize=16,color="black",shape="box"];95 -> 99[label="",style="solid", color="black", weight=3]; 11.09/4.47 96[label="primDivNatS0 (Succ xz30000) Zero (primGEqNatS (Succ xz30000) Zero)",fontsize=16,color="black",shape="box"];96 -> 100[label="",style="solid", color="black", weight=3]; 11.09/4.47 97[label="primDivNatS0 Zero (Succ xz31000) (primGEqNatS Zero (Succ xz31000))",fontsize=16,color="black",shape="box"];97 -> 101[label="",style="solid", color="black", weight=3]; 11.09/4.47 98[label="primDivNatS0 Zero Zero (primGEqNatS Zero Zero)",fontsize=16,color="black",shape="box"];98 -> 102[label="",style="solid", color="black", weight=3]; 11.09/4.47 99 -> 263[label="",style="dashed", color="red", weight=0]; 11.09/4.47 99[label="primDivNatS0 (Succ xz30000) (Succ xz31000) (primGEqNatS xz30000 xz31000)",fontsize=16,color="magenta"];99 -> 264[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 99 -> 265[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 99 -> 266[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 99 -> 267[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 100[label="primDivNatS0 (Succ xz30000) Zero True",fontsize=16,color="black",shape="box"];100 -> 105[label="",style="solid", color="black", weight=3]; 11.09/4.47 101[label="primDivNatS0 Zero (Succ xz31000) False",fontsize=16,color="black",shape="box"];101 -> 106[label="",style="solid", color="black", weight=3]; 11.09/4.47 102[label="primDivNatS0 Zero Zero True",fontsize=16,color="black",shape="box"];102 -> 107[label="",style="solid", color="black", weight=3]; 11.09/4.47 264[label="xz30000",fontsize=16,color="green",shape="box"];265[label="xz30000",fontsize=16,color="green",shape="box"];266[label="xz31000",fontsize=16,color="green",shape="box"];267[label="xz31000",fontsize=16,color="green",shape="box"];263[label="primDivNatS0 (Succ xz24) (Succ xz25) (primGEqNatS xz26 xz27)",fontsize=16,color="burlywood",shape="triangle"];358[label="xz26/Succ xz260",fontsize=10,color="white",style="solid",shape="box"];263 -> 358[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 358 -> 296[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 359[label="xz26/Zero",fontsize=10,color="white",style="solid",shape="box"];263 -> 359[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 359 -> 297[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 105[label="Succ (primDivNatS (primMinusNatS (Succ xz30000) Zero) (Succ Zero))",fontsize=16,color="green",shape="box"];105 -> 112[label="",style="dashed", color="green", weight=3]; 11.09/4.47 106[label="Zero",fontsize=16,color="green",shape="box"];107[label="Succ (primDivNatS (primMinusNatS Zero Zero) (Succ Zero))",fontsize=16,color="green",shape="box"];107 -> 113[label="",style="dashed", color="green", weight=3]; 11.09/4.47 296[label="primDivNatS0 (Succ xz24) (Succ xz25) (primGEqNatS (Succ xz260) xz27)",fontsize=16,color="burlywood",shape="box"];360[label="xz27/Succ xz270",fontsize=10,color="white",style="solid",shape="box"];296 -> 360[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 360 -> 298[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 361[label="xz27/Zero",fontsize=10,color="white",style="solid",shape="box"];296 -> 361[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 361 -> 299[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 297[label="primDivNatS0 (Succ xz24) (Succ xz25) (primGEqNatS Zero xz27)",fontsize=16,color="burlywood",shape="box"];362[label="xz27/Succ xz270",fontsize=10,color="white",style="solid",shape="box"];297 -> 362[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 362 -> 300[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 363[label="xz27/Zero",fontsize=10,color="white",style="solid",shape="box"];297 -> 363[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 363 -> 301[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 112 -> 67[label="",style="dashed", color="red", weight=0]; 11.09/4.47 112[label="primDivNatS (primMinusNatS (Succ xz30000) Zero) (Succ Zero)",fontsize=16,color="magenta"];112 -> 118[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 112 -> 119[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 113 -> 67[label="",style="dashed", color="red", weight=0]; 11.09/4.47 113[label="primDivNatS (primMinusNatS Zero Zero) (Succ Zero)",fontsize=16,color="magenta"];113 -> 120[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 113 -> 121[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 298[label="primDivNatS0 (Succ xz24) (Succ xz25) (primGEqNatS (Succ xz260) (Succ xz270))",fontsize=16,color="black",shape="box"];298 -> 302[label="",style="solid", color="black", weight=3]; 11.09/4.47 299[label="primDivNatS0 (Succ xz24) (Succ xz25) (primGEqNatS (Succ xz260) Zero)",fontsize=16,color="black",shape="box"];299 -> 303[label="",style="solid", color="black", weight=3]; 11.09/4.47 300[label="primDivNatS0 (Succ xz24) (Succ xz25) (primGEqNatS Zero (Succ xz270))",fontsize=16,color="black",shape="box"];300 -> 304[label="",style="solid", color="black", weight=3]; 11.09/4.47 301[label="primDivNatS0 (Succ xz24) (Succ xz25) (primGEqNatS Zero Zero)",fontsize=16,color="black",shape="box"];301 -> 305[label="",style="solid", color="black", weight=3]; 11.09/4.47 118[label="primMinusNatS (Succ xz30000) Zero",fontsize=16,color="black",shape="triangle"];118 -> 127[label="",style="solid", color="black", weight=3]; 11.09/4.47 119[label="Zero",fontsize=16,color="green",shape="box"];120[label="primMinusNatS Zero Zero",fontsize=16,color="black",shape="triangle"];120 -> 128[label="",style="solid", color="black", weight=3]; 11.09/4.47 121[label="Zero",fontsize=16,color="green",shape="box"];302 -> 263[label="",style="dashed", color="red", weight=0]; 11.09/4.47 302[label="primDivNatS0 (Succ xz24) (Succ xz25) (primGEqNatS xz260 xz270)",fontsize=16,color="magenta"];302 -> 306[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 302 -> 307[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 303[label="primDivNatS0 (Succ xz24) (Succ xz25) True",fontsize=16,color="black",shape="triangle"];303 -> 308[label="",style="solid", color="black", weight=3]; 11.09/4.47 304[label="primDivNatS0 (Succ xz24) (Succ xz25) False",fontsize=16,color="black",shape="box"];304 -> 309[label="",style="solid", color="black", weight=3]; 11.09/4.47 305 -> 303[label="",style="dashed", color="red", weight=0]; 11.09/4.47 305[label="primDivNatS0 (Succ xz24) (Succ xz25) True",fontsize=16,color="magenta"];127[label="Succ xz30000",fontsize=16,color="green",shape="box"];128[label="Zero",fontsize=16,color="green",shape="box"];306[label="xz260",fontsize=16,color="green",shape="box"];307[label="xz270",fontsize=16,color="green",shape="box"];308[label="Succ (primDivNatS (primMinusNatS (Succ xz24) (Succ xz25)) (Succ (Succ xz25)))",fontsize=16,color="green",shape="box"];308 -> 310[label="",style="dashed", color="green", weight=3]; 11.09/4.47 309[label="Zero",fontsize=16,color="green",shape="box"];310 -> 67[label="",style="dashed", color="red", weight=0]; 11.09/4.47 310[label="primDivNatS (primMinusNatS (Succ xz24) (Succ xz25)) (Succ (Succ xz25))",fontsize=16,color="magenta"];310 -> 311[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 310 -> 312[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 311[label="primMinusNatS (Succ xz24) (Succ xz25)",fontsize=16,color="black",shape="box"];311 -> 313[label="",style="solid", color="black", weight=3]; 11.09/4.47 312[label="Succ xz25",fontsize=16,color="green",shape="box"];313[label="primMinusNatS xz24 xz25",fontsize=16,color="burlywood",shape="triangle"];364[label="xz24/Succ xz240",fontsize=10,color="white",style="solid",shape="box"];313 -> 364[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 364 -> 314[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 365[label="xz24/Zero",fontsize=10,color="white",style="solid",shape="box"];313 -> 365[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 365 -> 315[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 314[label="primMinusNatS (Succ xz240) xz25",fontsize=16,color="burlywood",shape="box"];366[label="xz25/Succ xz250",fontsize=10,color="white",style="solid",shape="box"];314 -> 366[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 366 -> 316[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 367[label="xz25/Zero",fontsize=10,color="white",style="solid",shape="box"];314 -> 367[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 367 -> 317[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 315[label="primMinusNatS Zero xz25",fontsize=16,color="burlywood",shape="box"];368[label="xz25/Succ xz250",fontsize=10,color="white",style="solid",shape="box"];315 -> 368[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 368 -> 318[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 369[label="xz25/Zero",fontsize=10,color="white",style="solid",shape="box"];315 -> 369[label="",style="solid", color="burlywood", weight=9]; 11.09/4.47 369 -> 319[label="",style="solid", color="burlywood", weight=3]; 11.09/4.47 316[label="primMinusNatS (Succ xz240) (Succ xz250)",fontsize=16,color="black",shape="box"];316 -> 320[label="",style="solid", color="black", weight=3]; 11.09/4.47 317[label="primMinusNatS (Succ xz240) Zero",fontsize=16,color="black",shape="box"];317 -> 321[label="",style="solid", color="black", weight=3]; 11.09/4.47 318[label="primMinusNatS Zero (Succ xz250)",fontsize=16,color="black",shape="box"];318 -> 322[label="",style="solid", color="black", weight=3]; 11.09/4.47 319[label="primMinusNatS Zero Zero",fontsize=16,color="black",shape="box"];319 -> 323[label="",style="solid", color="black", weight=3]; 11.09/4.47 320 -> 313[label="",style="dashed", color="red", weight=0]; 11.09/4.47 320[label="primMinusNatS xz240 xz250",fontsize=16,color="magenta"];320 -> 324[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 320 -> 325[label="",style="dashed", color="magenta", weight=3]; 11.09/4.47 321[label="Succ xz240",fontsize=16,color="green",shape="box"];322[label="Zero",fontsize=16,color="green",shape="box"];323[label="Zero",fontsize=16,color="green",shape="box"];324[label="xz240",fontsize=16,color="green",shape="box"];325[label="xz250",fontsize=16,color="green",shape="box"];} 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (14) 11.09/4.47 Complex Obligation (AND) 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (15) 11.09/4.47 Obligation: 11.09/4.47 Q DP problem: 11.09/4.47 The TRS P consists of the following rules: 11.09/4.47 11.09/4.47 new_primDivNatS(Succ(Succ(xz30000)), Succ(xz31000)) -> new_primDivNatS0(xz30000, xz31000, xz30000, xz31000) 11.09/4.47 new_primDivNatS0(xz24, xz25, Succ(xz260), Zero) -> new_primDivNatS(new_primMinusNatS0(xz24, xz25), Succ(xz25)) 11.09/4.47 new_primDivNatS0(xz24, xz25, Zero, Zero) -> new_primDivNatS00(xz24, xz25) 11.09/4.47 new_primDivNatS0(xz24, xz25, Succ(xz260), Succ(xz270)) -> new_primDivNatS0(xz24, xz25, xz260, xz270) 11.09/4.47 new_primDivNatS(Succ(Zero), Zero) -> new_primDivNatS(new_primMinusNatS2, Zero) 11.09/4.47 new_primDivNatS(Succ(Succ(xz30000)), Zero) -> new_primDivNatS(new_primMinusNatS1(xz30000), Zero) 11.09/4.47 new_primDivNatS00(xz24, xz25) -> new_primDivNatS(new_primMinusNatS0(xz24, xz25), Succ(xz25)) 11.09/4.47 11.09/4.47 The TRS R consists of the following rules: 11.09/4.47 11.09/4.47 new_primMinusNatS0(Zero, Succ(xz250)) -> Zero 11.09/4.47 new_primMinusNatS0(Zero, Zero) -> Zero 11.09/4.47 new_primMinusNatS1(xz30000) -> Succ(xz30000) 11.09/4.47 new_primMinusNatS0(Succ(xz240), Succ(xz250)) -> new_primMinusNatS0(xz240, xz250) 11.09/4.47 new_primMinusNatS2 -> Zero 11.09/4.47 new_primMinusNatS0(Succ(xz240), Zero) -> Succ(xz240) 11.09/4.47 11.09/4.47 The set Q consists of the following terms: 11.09/4.47 11.09/4.47 new_primMinusNatS0(Zero, Succ(x0)) 11.09/4.47 new_primMinusNatS0(Zero, Zero) 11.09/4.47 new_primMinusNatS2 11.09/4.47 new_primMinusNatS1(x0) 11.09/4.47 new_primMinusNatS0(Succ(x0), Succ(x1)) 11.09/4.47 new_primMinusNatS0(Succ(x0), Zero) 11.09/4.47 11.09/4.47 We have to consider all minimal (P,Q,R)-chains. 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (16) DependencyGraphProof (EQUIVALENT) 11.09/4.47 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (17) 11.09/4.47 Complex Obligation (AND) 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (18) 11.09/4.47 Obligation: 11.09/4.47 Q DP problem: 11.09/4.47 The TRS P consists of the following rules: 11.09/4.47 11.09/4.47 new_primDivNatS(Succ(Succ(xz30000)), Zero) -> new_primDivNatS(new_primMinusNatS1(xz30000), Zero) 11.09/4.47 11.09/4.47 The TRS R consists of the following rules: 11.09/4.47 11.09/4.47 new_primMinusNatS0(Zero, Succ(xz250)) -> Zero 11.09/4.47 new_primMinusNatS0(Zero, Zero) -> Zero 11.09/4.47 new_primMinusNatS1(xz30000) -> Succ(xz30000) 11.09/4.47 new_primMinusNatS0(Succ(xz240), Succ(xz250)) -> new_primMinusNatS0(xz240, xz250) 11.09/4.47 new_primMinusNatS2 -> Zero 11.09/4.47 new_primMinusNatS0(Succ(xz240), Zero) -> Succ(xz240) 11.09/4.47 11.09/4.47 The set Q consists of the following terms: 11.09/4.47 11.09/4.47 new_primMinusNatS0(Zero, Succ(x0)) 11.09/4.47 new_primMinusNatS0(Zero, Zero) 11.09/4.47 new_primMinusNatS2 11.09/4.47 new_primMinusNatS1(x0) 11.09/4.47 new_primMinusNatS0(Succ(x0), Succ(x1)) 11.09/4.47 new_primMinusNatS0(Succ(x0), Zero) 11.09/4.47 11.09/4.47 We have to consider all minimal (P,Q,R)-chains. 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (19) MRRProof (EQUIVALENT) 11.09/4.47 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 11.09/4.47 11.09/4.47 Strictly oriented dependency pairs: 11.09/4.47 11.09/4.47 new_primDivNatS(Succ(Succ(xz30000)), Zero) -> new_primDivNatS(new_primMinusNatS1(xz30000), Zero) 11.09/4.47 11.09/4.47 Strictly oriented rules of the TRS R: 11.09/4.47 11.09/4.47 new_primMinusNatS0(Zero, Succ(xz250)) -> Zero 11.09/4.47 new_primMinusNatS0(Zero, Zero) -> Zero 11.09/4.47 new_primMinusNatS1(xz30000) -> Succ(xz30000) 11.09/4.47 new_primMinusNatS0(Succ(xz240), Succ(xz250)) -> new_primMinusNatS0(xz240, xz250) 11.09/4.47 new_primMinusNatS2 -> Zero 11.09/4.47 new_primMinusNatS0(Succ(xz240), Zero) -> Succ(xz240) 11.09/4.47 11.09/4.47 Used ordering: Polynomial interpretation [POLO]: 11.09/4.47 11.09/4.47 POL(Succ(x_1)) = 1 + 2*x_1 11.09/4.47 POL(Zero) = 1 11.09/4.47 POL(new_primDivNatS(x_1, x_2)) = x_1 + x_2 11.09/4.47 POL(new_primMinusNatS0(x_1, x_2)) = x_1 + x_2 11.09/4.47 POL(new_primMinusNatS1(x_1)) = 2 + 2*x_1 11.09/4.47 POL(new_primMinusNatS2) = 2 11.09/4.47 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (20) 11.09/4.47 Obligation: 11.09/4.47 Q DP problem: 11.09/4.47 P is empty. 11.09/4.47 R is empty. 11.09/4.47 The set Q consists of the following terms: 11.09/4.47 11.09/4.47 new_primMinusNatS0(Zero, Succ(x0)) 11.09/4.47 new_primMinusNatS0(Zero, Zero) 11.09/4.47 new_primMinusNatS2 11.09/4.47 new_primMinusNatS1(x0) 11.09/4.47 new_primMinusNatS0(Succ(x0), Succ(x1)) 11.09/4.47 new_primMinusNatS0(Succ(x0), Zero) 11.09/4.47 11.09/4.47 We have to consider all minimal (P,Q,R)-chains. 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (21) PisEmptyProof (EQUIVALENT) 11.09/4.47 The TRS P is empty. Hence, there is no (P,Q,R) chain. 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (22) 11.09/4.47 YES 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (23) 11.09/4.47 Obligation: 11.09/4.47 Q DP problem: 11.09/4.47 The TRS P consists of the following rules: 11.09/4.47 11.09/4.47 new_primDivNatS0(xz24, xz25, Succ(xz260), Zero) -> new_primDivNatS(new_primMinusNatS0(xz24, xz25), Succ(xz25)) 11.09/4.47 new_primDivNatS(Succ(Succ(xz30000)), Succ(xz31000)) -> new_primDivNatS0(xz30000, xz31000, xz30000, xz31000) 11.09/4.47 new_primDivNatS0(xz24, xz25, Zero, Zero) -> new_primDivNatS00(xz24, xz25) 11.09/4.47 new_primDivNatS00(xz24, xz25) -> new_primDivNatS(new_primMinusNatS0(xz24, xz25), Succ(xz25)) 11.09/4.47 new_primDivNatS0(xz24, xz25, Succ(xz260), Succ(xz270)) -> new_primDivNatS0(xz24, xz25, xz260, xz270) 11.09/4.47 11.09/4.47 The TRS R consists of the following rules: 11.09/4.47 11.09/4.47 new_primMinusNatS0(Zero, Succ(xz250)) -> Zero 11.09/4.47 new_primMinusNatS0(Zero, Zero) -> Zero 11.09/4.47 new_primMinusNatS1(xz30000) -> Succ(xz30000) 11.09/4.47 new_primMinusNatS0(Succ(xz240), Succ(xz250)) -> new_primMinusNatS0(xz240, xz250) 11.09/4.47 new_primMinusNatS2 -> Zero 11.09/4.47 new_primMinusNatS0(Succ(xz240), Zero) -> Succ(xz240) 11.09/4.47 11.09/4.47 The set Q consists of the following terms: 11.09/4.47 11.09/4.47 new_primMinusNatS0(Zero, Succ(x0)) 11.09/4.47 new_primMinusNatS0(Zero, Zero) 11.09/4.47 new_primMinusNatS2 11.09/4.47 new_primMinusNatS1(x0) 11.09/4.47 new_primMinusNatS0(Succ(x0), Succ(x1)) 11.09/4.47 new_primMinusNatS0(Succ(x0), Zero) 11.09/4.47 11.09/4.47 We have to consider all minimal (P,Q,R)-chains. 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (24) QDPSizeChangeProof (EQUIVALENT) 11.09/4.47 We used the following order together with the size-change analysis [AAECC05] to show that there are no infinite chains for this DP problem. 11.09/4.47 11.09/4.47 Order:Polynomial interpretation [POLO]: 11.09/4.47 11.09/4.47 POL(Succ(x_1)) = 1 + x_1 11.09/4.47 POL(Zero) = 1 11.09/4.47 POL(new_primMinusNatS0(x_1, x_2)) = x_1 11.09/4.47 11.09/4.47 11.09/4.47 11.09/4.47 11.09/4.47 From the DPs we obtained the following set of size-change graphs: 11.09/4.47 *new_primDivNatS(Succ(Succ(xz30000)), Succ(xz31000)) -> new_primDivNatS0(xz30000, xz31000, xz30000, xz31000) (allowed arguments on rhs = {1, 2, 3, 4}) 11.09/4.47 The graph contains the following edges 1 > 1, 2 > 2, 1 > 3, 2 > 4 11.09/4.47 11.09/4.47 11.09/4.47 *new_primDivNatS0(xz24, xz25, Succ(xz260), Succ(xz270)) -> new_primDivNatS0(xz24, xz25, xz260, xz270) (allowed arguments on rhs = {1, 2, 3, 4}) 11.09/4.47 The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3, 4 > 4 11.09/4.47 11.09/4.47 11.09/4.47 *new_primDivNatS0(xz24, xz25, Succ(xz260), Zero) -> new_primDivNatS(new_primMinusNatS0(xz24, xz25), Succ(xz25)) (allowed arguments on rhs = {1, 2}) 11.09/4.47 The graph contains the following edges 1 >= 1 11.09/4.47 11.09/4.47 11.09/4.47 *new_primDivNatS0(xz24, xz25, Zero, Zero) -> new_primDivNatS00(xz24, xz25) (allowed arguments on rhs = {1, 2}) 11.09/4.47 The graph contains the following edges 1 >= 1, 2 >= 2 11.09/4.47 11.09/4.47 11.09/4.47 *new_primDivNatS00(xz24, xz25) -> new_primDivNatS(new_primMinusNatS0(xz24, xz25), Succ(xz25)) (allowed arguments on rhs = {1, 2}) 11.09/4.47 The graph contains the following edges 1 >= 1 11.09/4.47 11.09/4.47 11.09/4.47 11.09/4.47 We oriented the following set of usable rules [AAECC05,FROCOS05]. 11.09/4.47 11.09/4.47 new_primMinusNatS0(Zero, Zero) -> Zero 11.09/4.47 new_primMinusNatS0(Zero, Succ(xz250)) -> Zero 11.09/4.47 new_primMinusNatS0(Succ(xz240), Zero) -> Succ(xz240) 11.09/4.47 new_primMinusNatS0(Succ(xz240), Succ(xz250)) -> new_primMinusNatS0(xz240, xz250) 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (25) 11.09/4.47 YES 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (26) 11.09/4.47 Obligation: 11.09/4.47 Q DP problem: 11.09/4.47 The TRS P consists of the following rules: 11.09/4.47 11.09/4.47 new_primMinusNatS(Succ(xz240), Succ(xz250)) -> new_primMinusNatS(xz240, xz250) 11.09/4.47 11.09/4.47 R is empty. 11.09/4.47 Q is empty. 11.09/4.47 We have to consider all minimal (P,Q,R)-chains. 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (27) QDPSizeChangeProof (EQUIVALENT) 11.09/4.47 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. 11.09/4.47 11.09/4.47 From the DPs we obtained the following set of size-change graphs: 11.09/4.47 *new_primMinusNatS(Succ(xz240), Succ(xz250)) -> new_primMinusNatS(xz240, xz250) 11.09/4.47 The graph contains the following edges 1 > 1, 2 > 2 11.09/4.47 11.09/4.47 11.09/4.47 ---------------------------------------- 11.09/4.47 11.09/4.47 (28) 11.09/4.47 YES 11.30/8.25 EOF