8.36/3.69 YES 10.22/4.23 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 10.22/4.23 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.22/4.23 10.22/4.23 10.22/4.23 H-Termination with start terms of the given HASKELL could be proven: 10.22/4.23 10.22/4.23 (0) HASKELL 10.22/4.23 (1) BR [EQUIVALENT, 0 ms] 10.22/4.23 (2) HASKELL 10.22/4.23 (3) COR [EQUIVALENT, 0 ms] 10.22/4.23 (4) HASKELL 10.22/4.23 (5) Narrow [SOUND, 0 ms] 10.22/4.23 (6) QDP 10.22/4.23 (7) TransformationProof [EQUIVALENT, 0 ms] 10.22/4.23 (8) QDP 10.22/4.23 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 10.22/4.23 (10) QDP 10.22/4.23 (11) UsableRulesProof [EQUIVALENT, 0 ms] 10.22/4.23 (12) QDP 10.22/4.23 (13) QReductionProof [EQUIVALENT, 0 ms] 10.22/4.23 (14) QDP 10.22/4.23 (15) QDPSizeChangeProof [EQUIVALENT, 1 ms] 10.22/4.23 (16) YES 10.22/4.23 10.22/4.23 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (0) 10.22/4.23 Obligation: 10.22/4.23 mainModule Main 10.22/4.23 module Main where { 10.22/4.23 import qualified Prelude; 10.22/4.23 data List a = Cons a (List a) | Nil ; 10.22/4.23 10.22/4.23 data MyBool = MyTrue | MyFalse ; 10.22/4.23 10.22/4.23 data MyInt = Pos Main.Nat | Neg Main.Nat ; 10.22/4.23 10.22/4.23 data Main.Nat = Succ Main.Nat | Zero ; 10.22/4.23 10.22/4.23 data Ordering = LT | EQ | GT ; 10.22/4.23 10.22/4.23 compareMyInt :: MyInt -> MyInt -> Ordering; 10.22/4.23 compareMyInt = primCmpInt; 10.22/4.23 10.22/4.23 emEm :: List a -> MyInt -> a; 10.22/4.23 emEm (Cons x vv) xz = emEm5 (Cons x vv) xz; 10.22/4.23 emEm (Cons vw xs) n = emEm3 (Cons vw xs) n; 10.22/4.23 emEm (Cons vx vy) vz = emEm1 (Cons vx vy) vz; 10.22/4.23 emEm Nil wu = emEm0 Nil wu; 10.22/4.23 10.22/4.23 emEm0 Nil wu = Main.error; 10.22/4.23 10.22/4.23 emEm1 (Cons vx vy) vz = Main.error; 10.22/4.23 emEm1 wz xu = emEm0 wz xu; 10.22/4.23 10.22/4.23 emEm2 vw xs n MyTrue = emEm xs (msMyInt n (Main.Pos (Main.Succ Main.Zero))); 10.22/4.23 emEm2 vw xs n MyFalse = emEm1 (Cons vw xs) n; 10.22/4.23 10.22/4.23 emEm3 (Cons vw xs) n = emEm2 vw xs n (gtMyInt n (Main.Pos Main.Zero)); 10.22/4.23 emEm3 xw xx = emEm1 xw xx; 10.22/4.23 10.22/4.23 emEm4 MyTrue (Cons x vv) xz = x; 10.22/4.23 emEm4 yu yv yw = emEm3 yv yw; 10.22/4.23 10.22/4.23 emEm5 (Cons x vv) xz = emEm4 (esEsMyInt xz (Main.Pos Main.Zero)) (Cons x vv) xz; 10.22/4.23 emEm5 yx yy = emEm3 yx yy; 10.22/4.23 10.22/4.23 error :: a; 10.22/4.23 error = stop MyTrue; 10.22/4.23 10.22/4.23 esEsMyInt :: MyInt -> MyInt -> MyBool; 10.22/4.23 esEsMyInt = primEqInt; 10.22/4.23 10.22/4.23 esEsOrdering :: Ordering -> Ordering -> MyBool; 10.22/4.23 esEsOrdering LT LT = MyTrue; 10.22/4.23 esEsOrdering LT EQ = MyFalse; 10.22/4.23 esEsOrdering LT GT = MyFalse; 10.22/4.23 esEsOrdering EQ LT = MyFalse; 10.22/4.23 esEsOrdering EQ EQ = MyTrue; 10.22/4.23 esEsOrdering EQ GT = MyFalse; 10.22/4.23 esEsOrdering GT LT = MyFalse; 10.22/4.23 esEsOrdering GT EQ = MyFalse; 10.22/4.23 esEsOrdering GT GT = MyTrue; 10.22/4.23 10.22/4.23 gtMyInt :: MyInt -> MyInt -> MyBool; 10.22/4.23 gtMyInt x y = esEsOrdering (compareMyInt x y) GT; 10.22/4.23 10.22/4.23 msMyInt :: MyInt -> MyInt -> MyInt; 10.22/4.23 msMyInt = primMinusInt; 10.22/4.23 10.22/4.23 primCmpInt :: MyInt -> MyInt -> Ordering; 10.22/4.23 primCmpInt (Main.Pos Main.Zero) (Main.Pos Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Pos Main.Zero) (Main.Neg Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Neg Main.Zero) (Main.Pos Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Neg Main.Zero) (Main.Neg Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Pos x) (Main.Pos y) = primCmpNat x y; 10.22/4.23 primCmpInt (Main.Pos x) (Main.Neg y) = GT; 10.22/4.23 primCmpInt (Main.Neg x) (Main.Pos y) = LT; 10.22/4.23 primCmpInt (Main.Neg x) (Main.Neg y) = primCmpNat y x; 10.22/4.23 10.22/4.23 primCmpNat :: Main.Nat -> Main.Nat -> Ordering; 10.22/4.23 primCmpNat Main.Zero Main.Zero = EQ; 10.22/4.23 primCmpNat Main.Zero (Main.Succ y) = LT; 10.22/4.23 primCmpNat (Main.Succ x) Main.Zero = GT; 10.22/4.23 primCmpNat (Main.Succ x) (Main.Succ y) = primCmpNat x y; 10.22/4.23 10.22/4.23 primEqInt :: MyInt -> MyInt -> MyBool; 10.22/4.23 primEqInt (Main.Pos (Main.Succ x)) (Main.Pos (Main.Succ y)) = primEqNat x y; 10.22/4.23 primEqInt (Main.Neg (Main.Succ x)) (Main.Neg (Main.Succ y)) = primEqNat x y; 10.22/4.23 primEqInt (Main.Pos Main.Zero) (Main.Neg Main.Zero) = MyTrue; 10.22/4.23 primEqInt (Main.Neg Main.Zero) (Main.Pos Main.Zero) = MyTrue; 10.22/4.23 primEqInt (Main.Neg Main.Zero) (Main.Neg Main.Zero) = MyTrue; 10.22/4.23 primEqInt (Main.Pos Main.Zero) (Main.Pos Main.Zero) = MyTrue; 10.22/4.23 primEqInt wv ww = MyFalse; 10.22/4.23 10.22/4.23 primEqNat :: Main.Nat -> Main.Nat -> MyBool; 10.22/4.23 primEqNat Main.Zero Main.Zero = MyTrue; 10.22/4.23 primEqNat Main.Zero (Main.Succ y) = MyFalse; 10.22/4.23 primEqNat (Main.Succ x) Main.Zero = MyFalse; 10.22/4.23 primEqNat (Main.Succ x) (Main.Succ y) = primEqNat x y; 10.22/4.23 10.22/4.23 primMinusInt :: MyInt -> MyInt -> MyInt; 10.22/4.23 primMinusInt (Main.Pos x) (Main.Neg y) = Main.Pos (primPlusNat x y); 10.22/4.23 primMinusInt (Main.Neg x) (Main.Pos y) = Main.Neg (primPlusNat x y); 10.22/4.23 primMinusInt (Main.Neg x) (Main.Neg y) = primMinusNat y x; 10.22/4.23 primMinusInt (Main.Pos x) (Main.Pos y) = primMinusNat x y; 10.22/4.23 10.22/4.23 primMinusNat :: Main.Nat -> Main.Nat -> MyInt; 10.22/4.23 primMinusNat Main.Zero Main.Zero = Main.Pos Main.Zero; 10.22/4.23 primMinusNat Main.Zero (Main.Succ y) = Main.Neg (Main.Succ y); 10.22/4.23 primMinusNat (Main.Succ x) Main.Zero = Main.Pos (Main.Succ x); 10.22/4.23 primMinusNat (Main.Succ x) (Main.Succ y) = primMinusNat x y; 10.22/4.23 10.22/4.23 primPlusNat :: Main.Nat -> Main.Nat -> Main.Nat; 10.22/4.23 primPlusNat Main.Zero Main.Zero = Main.Zero; 10.22/4.23 primPlusNat Main.Zero (Main.Succ y) = Main.Succ y; 10.22/4.23 primPlusNat (Main.Succ x) Main.Zero = Main.Succ x; 10.22/4.23 primPlusNat (Main.Succ x) (Main.Succ y) = Main.Succ (Main.Succ (primPlusNat x y)); 10.22/4.23 10.22/4.23 stop :: MyBool -> a; 10.22/4.23 stop MyFalse = stop MyFalse; 10.22/4.23 10.22/4.23 } 10.22/4.23 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (1) BR (EQUIVALENT) 10.22/4.23 Replaced joker patterns by fresh variables and removed binding patterns. 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (2) 10.22/4.23 Obligation: 10.22/4.23 mainModule Main 10.22/4.23 module Main where { 10.22/4.23 import qualified Prelude; 10.22/4.23 data List a = Cons a (List a) | Nil ; 10.22/4.23 10.22/4.23 data MyBool = MyTrue | MyFalse ; 10.22/4.23 10.22/4.23 data MyInt = Pos Main.Nat | Neg Main.Nat ; 10.22/4.23 10.22/4.23 data Main.Nat = Succ Main.Nat | Zero ; 10.22/4.23 10.22/4.23 data Ordering = LT | EQ | GT ; 10.22/4.23 10.22/4.23 compareMyInt :: MyInt -> MyInt -> Ordering; 10.22/4.23 compareMyInt = primCmpInt; 10.22/4.23 10.22/4.23 emEm :: List a -> MyInt -> a; 10.22/4.23 emEm (Cons x vv) xz = emEm5 (Cons x vv) xz; 10.22/4.23 emEm (Cons vw xs) n = emEm3 (Cons vw xs) n; 10.22/4.23 emEm (Cons vx vy) vz = emEm1 (Cons vx vy) vz; 10.22/4.23 emEm Nil wu = emEm0 Nil wu; 10.22/4.23 10.22/4.23 emEm0 Nil wu = Main.error; 10.22/4.23 10.22/4.23 emEm1 (Cons vx vy) vz = Main.error; 10.22/4.23 emEm1 wz xu = emEm0 wz xu; 10.22/4.23 10.22/4.23 emEm2 vw xs n MyTrue = emEm xs (msMyInt n (Main.Pos (Main.Succ Main.Zero))); 10.22/4.23 emEm2 vw xs n MyFalse = emEm1 (Cons vw xs) n; 10.22/4.23 10.22/4.23 emEm3 (Cons vw xs) n = emEm2 vw xs n (gtMyInt n (Main.Pos Main.Zero)); 10.22/4.23 emEm3 xw xx = emEm1 xw xx; 10.22/4.23 10.22/4.23 emEm4 MyTrue (Cons x vv) xz = x; 10.22/4.23 emEm4 yu yv yw = emEm3 yv yw; 10.22/4.23 10.22/4.23 emEm5 (Cons x vv) xz = emEm4 (esEsMyInt xz (Main.Pos Main.Zero)) (Cons x vv) xz; 10.22/4.23 emEm5 yx yy = emEm3 yx yy; 10.22/4.23 10.22/4.23 error :: a; 10.22/4.23 error = stop MyTrue; 10.22/4.23 10.22/4.23 esEsMyInt :: MyInt -> MyInt -> MyBool; 10.22/4.23 esEsMyInt = primEqInt; 10.22/4.23 10.22/4.23 esEsOrdering :: Ordering -> Ordering -> MyBool; 10.22/4.23 esEsOrdering LT LT = MyTrue; 10.22/4.23 esEsOrdering LT EQ = MyFalse; 10.22/4.23 esEsOrdering LT GT = MyFalse; 10.22/4.23 esEsOrdering EQ LT = MyFalse; 10.22/4.23 esEsOrdering EQ EQ = MyTrue; 10.22/4.23 esEsOrdering EQ GT = MyFalse; 10.22/4.23 esEsOrdering GT LT = MyFalse; 10.22/4.23 esEsOrdering GT EQ = MyFalse; 10.22/4.23 esEsOrdering GT GT = MyTrue; 10.22/4.23 10.22/4.23 gtMyInt :: MyInt -> MyInt -> MyBool; 10.22/4.23 gtMyInt x y = esEsOrdering (compareMyInt x y) GT; 10.22/4.23 10.22/4.23 msMyInt :: MyInt -> MyInt -> MyInt; 10.22/4.23 msMyInt = primMinusInt; 10.22/4.23 10.22/4.23 primCmpInt :: MyInt -> MyInt -> Ordering; 10.22/4.23 primCmpInt (Main.Pos Main.Zero) (Main.Pos Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Pos Main.Zero) (Main.Neg Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Neg Main.Zero) (Main.Pos Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Neg Main.Zero) (Main.Neg Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Pos x) (Main.Pos y) = primCmpNat x y; 10.22/4.23 primCmpInt (Main.Pos x) (Main.Neg y) = GT; 10.22/4.23 primCmpInt (Main.Neg x) (Main.Pos y) = LT; 10.22/4.23 primCmpInt (Main.Neg x) (Main.Neg y) = primCmpNat y x; 10.22/4.23 10.22/4.23 primCmpNat :: Main.Nat -> Main.Nat -> Ordering; 10.22/4.23 primCmpNat Main.Zero Main.Zero = EQ; 10.22/4.23 primCmpNat Main.Zero (Main.Succ y) = LT; 10.22/4.23 primCmpNat (Main.Succ x) Main.Zero = GT; 10.22/4.23 primCmpNat (Main.Succ x) (Main.Succ y) = primCmpNat x y; 10.22/4.23 10.22/4.23 primEqInt :: MyInt -> MyInt -> MyBool; 10.22/4.23 primEqInt (Main.Pos (Main.Succ x)) (Main.Pos (Main.Succ y)) = primEqNat x y; 10.22/4.23 primEqInt (Main.Neg (Main.Succ x)) (Main.Neg (Main.Succ y)) = primEqNat x y; 10.22/4.23 primEqInt (Main.Pos Main.Zero) (Main.Neg Main.Zero) = MyTrue; 10.22/4.23 primEqInt (Main.Neg Main.Zero) (Main.Pos Main.Zero) = MyTrue; 10.22/4.23 primEqInt (Main.Neg Main.Zero) (Main.Neg Main.Zero) = MyTrue; 10.22/4.23 primEqInt (Main.Pos Main.Zero) (Main.Pos Main.Zero) = MyTrue; 10.22/4.23 primEqInt wv ww = MyFalse; 10.22/4.23 10.22/4.23 primEqNat :: Main.Nat -> Main.Nat -> MyBool; 10.22/4.23 primEqNat Main.Zero Main.Zero = MyTrue; 10.22/4.23 primEqNat Main.Zero (Main.Succ y) = MyFalse; 10.22/4.23 primEqNat (Main.Succ x) Main.Zero = MyFalse; 10.22/4.23 primEqNat (Main.Succ x) (Main.Succ y) = primEqNat x y; 10.22/4.23 10.22/4.23 primMinusInt :: MyInt -> MyInt -> MyInt; 10.22/4.23 primMinusInt (Main.Pos x) (Main.Neg y) = Main.Pos (primPlusNat x y); 10.22/4.23 primMinusInt (Main.Neg x) (Main.Pos y) = Main.Neg (primPlusNat x y); 10.22/4.23 primMinusInt (Main.Neg x) (Main.Neg y) = primMinusNat y x; 10.22/4.23 primMinusInt (Main.Pos x) (Main.Pos y) = primMinusNat x y; 10.22/4.23 10.22/4.23 primMinusNat :: Main.Nat -> Main.Nat -> MyInt; 10.22/4.23 primMinusNat Main.Zero Main.Zero = Main.Pos Main.Zero; 10.22/4.23 primMinusNat Main.Zero (Main.Succ y) = Main.Neg (Main.Succ y); 10.22/4.23 primMinusNat (Main.Succ x) Main.Zero = Main.Pos (Main.Succ x); 10.22/4.23 primMinusNat (Main.Succ x) (Main.Succ y) = primMinusNat x y; 10.22/4.23 10.22/4.23 primPlusNat :: Main.Nat -> Main.Nat -> Main.Nat; 10.22/4.23 primPlusNat Main.Zero Main.Zero = Main.Zero; 10.22/4.23 primPlusNat Main.Zero (Main.Succ y) = Main.Succ y; 10.22/4.23 primPlusNat (Main.Succ x) Main.Zero = Main.Succ x; 10.22/4.23 primPlusNat (Main.Succ x) (Main.Succ y) = Main.Succ (Main.Succ (primPlusNat x y)); 10.22/4.23 10.22/4.23 stop :: MyBool -> a; 10.22/4.23 stop MyFalse = stop MyFalse; 10.22/4.23 10.22/4.23 } 10.22/4.23 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (3) COR (EQUIVALENT) 10.22/4.23 Cond Reductions: 10.22/4.23 The following Function with conditions 10.22/4.23 "undefined |Falseundefined; 10.22/4.23 " 10.22/4.23 is transformed to 10.22/4.23 "undefined = undefined1; 10.22/4.23 " 10.22/4.23 "undefined0 True = undefined; 10.22/4.23 " 10.22/4.23 "undefined1 = undefined0 False; 10.22/4.23 " 10.22/4.23 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (4) 10.22/4.23 Obligation: 10.22/4.23 mainModule Main 10.22/4.23 module Main where { 10.22/4.23 import qualified Prelude; 10.22/4.23 data List a = Cons a (List a) | Nil ; 10.22/4.23 10.22/4.23 data MyBool = MyTrue | MyFalse ; 10.22/4.23 10.22/4.23 data MyInt = Pos Main.Nat | Neg Main.Nat ; 10.22/4.23 10.22/4.23 data Main.Nat = Succ Main.Nat | Zero ; 10.22/4.23 10.22/4.23 data Ordering = LT | EQ | GT ; 10.22/4.23 10.22/4.23 compareMyInt :: MyInt -> MyInt -> Ordering; 10.22/4.23 compareMyInt = primCmpInt; 10.22/4.23 10.22/4.23 emEm :: List a -> MyInt -> a; 10.22/4.23 emEm (Cons x vv) xz = emEm5 (Cons x vv) xz; 10.22/4.23 emEm (Cons vw xs) n = emEm3 (Cons vw xs) n; 10.22/4.23 emEm (Cons vx vy) vz = emEm1 (Cons vx vy) vz; 10.22/4.23 emEm Nil wu = emEm0 Nil wu; 10.22/4.23 10.22/4.23 emEm0 Nil wu = Main.error; 10.22/4.23 10.22/4.23 emEm1 (Cons vx vy) vz = Main.error; 10.22/4.23 emEm1 wz xu = emEm0 wz xu; 10.22/4.23 10.22/4.23 emEm2 vw xs n MyTrue = emEm xs (msMyInt n (Main.Pos (Main.Succ Main.Zero))); 10.22/4.23 emEm2 vw xs n MyFalse = emEm1 (Cons vw xs) n; 10.22/4.23 10.22/4.23 emEm3 (Cons vw xs) n = emEm2 vw xs n (gtMyInt n (Main.Pos Main.Zero)); 10.22/4.23 emEm3 xw xx = emEm1 xw xx; 10.22/4.23 10.22/4.23 emEm4 MyTrue (Cons x vv) xz = x; 10.22/4.23 emEm4 yu yv yw = emEm3 yv yw; 10.22/4.23 10.22/4.23 emEm5 (Cons x vv) xz = emEm4 (esEsMyInt xz (Main.Pos Main.Zero)) (Cons x vv) xz; 10.22/4.23 emEm5 yx yy = emEm3 yx yy; 10.22/4.23 10.22/4.23 error :: a; 10.22/4.23 error = stop MyTrue; 10.22/4.23 10.22/4.23 esEsMyInt :: MyInt -> MyInt -> MyBool; 10.22/4.23 esEsMyInt = primEqInt; 10.22/4.23 10.22/4.23 esEsOrdering :: Ordering -> Ordering -> MyBool; 10.22/4.23 esEsOrdering LT LT = MyTrue; 10.22/4.23 esEsOrdering LT EQ = MyFalse; 10.22/4.23 esEsOrdering LT GT = MyFalse; 10.22/4.23 esEsOrdering EQ LT = MyFalse; 10.22/4.23 esEsOrdering EQ EQ = MyTrue; 10.22/4.23 esEsOrdering EQ GT = MyFalse; 10.22/4.23 esEsOrdering GT LT = MyFalse; 10.22/4.23 esEsOrdering GT EQ = MyFalse; 10.22/4.23 esEsOrdering GT GT = MyTrue; 10.22/4.23 10.22/4.23 gtMyInt :: MyInt -> MyInt -> MyBool; 10.22/4.23 gtMyInt x y = esEsOrdering (compareMyInt x y) GT; 10.22/4.23 10.22/4.23 msMyInt :: MyInt -> MyInt -> MyInt; 10.22/4.23 msMyInt = primMinusInt; 10.22/4.23 10.22/4.23 primCmpInt :: MyInt -> MyInt -> Ordering; 10.22/4.23 primCmpInt (Main.Pos Main.Zero) (Main.Pos Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Pos Main.Zero) (Main.Neg Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Neg Main.Zero) (Main.Pos Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Neg Main.Zero) (Main.Neg Main.Zero) = EQ; 10.22/4.23 primCmpInt (Main.Pos x) (Main.Pos y) = primCmpNat x y; 10.22/4.23 primCmpInt (Main.Pos x) (Main.Neg y) = GT; 10.22/4.23 primCmpInt (Main.Neg x) (Main.Pos y) = LT; 10.22/4.23 primCmpInt (Main.Neg x) (Main.Neg y) = primCmpNat y x; 10.22/4.23 10.22/4.23 primCmpNat :: Main.Nat -> Main.Nat -> Ordering; 10.22/4.23 primCmpNat Main.Zero Main.Zero = EQ; 10.22/4.23 primCmpNat Main.Zero (Main.Succ y) = LT; 10.22/4.23 primCmpNat (Main.Succ x) Main.Zero = GT; 10.22/4.23 primCmpNat (Main.Succ x) (Main.Succ y) = primCmpNat x y; 10.22/4.23 10.22/4.23 primEqInt :: MyInt -> MyInt -> MyBool; 10.22/4.23 primEqInt (Main.Pos (Main.Succ x)) (Main.Pos (Main.Succ y)) = primEqNat x y; 10.22/4.23 primEqInt (Main.Neg (Main.Succ x)) (Main.Neg (Main.Succ y)) = primEqNat x y; 10.22/4.23 primEqInt (Main.Pos Main.Zero) (Main.Neg Main.Zero) = MyTrue; 10.22/4.23 primEqInt (Main.Neg Main.Zero) (Main.Pos Main.Zero) = MyTrue; 10.22/4.23 primEqInt (Main.Neg Main.Zero) (Main.Neg Main.Zero) = MyTrue; 10.22/4.23 primEqInt (Main.Pos Main.Zero) (Main.Pos Main.Zero) = MyTrue; 10.22/4.23 primEqInt wv ww = MyFalse; 10.22/4.23 10.22/4.23 primEqNat :: Main.Nat -> Main.Nat -> MyBool; 10.22/4.23 primEqNat Main.Zero Main.Zero = MyTrue; 10.22/4.23 primEqNat Main.Zero (Main.Succ y) = MyFalse; 10.22/4.23 primEqNat (Main.Succ x) Main.Zero = MyFalse; 10.22/4.23 primEqNat (Main.Succ x) (Main.Succ y) = primEqNat x y; 10.22/4.23 10.22/4.23 primMinusInt :: MyInt -> MyInt -> MyInt; 10.22/4.23 primMinusInt (Main.Pos x) (Main.Neg y) = Main.Pos (primPlusNat x y); 10.22/4.23 primMinusInt (Main.Neg x) (Main.Pos y) = Main.Neg (primPlusNat x y); 10.22/4.23 primMinusInt (Main.Neg x) (Main.Neg y) = primMinusNat y x; 10.22/4.23 primMinusInt (Main.Pos x) (Main.Pos y) = primMinusNat x y; 10.22/4.23 10.22/4.23 primMinusNat :: Main.Nat -> Main.Nat -> MyInt; 10.22/4.23 primMinusNat Main.Zero Main.Zero = Main.Pos Main.Zero; 10.22/4.23 primMinusNat Main.Zero (Main.Succ y) = Main.Neg (Main.Succ y); 10.22/4.23 primMinusNat (Main.Succ x) Main.Zero = Main.Pos (Main.Succ x); 10.22/4.23 primMinusNat (Main.Succ x) (Main.Succ y) = primMinusNat x y; 10.22/4.23 10.22/4.23 primPlusNat :: Main.Nat -> Main.Nat -> Main.Nat; 10.22/4.23 primPlusNat Main.Zero Main.Zero = Main.Zero; 10.22/4.23 primPlusNat Main.Zero (Main.Succ y) = Main.Succ y; 10.22/4.23 primPlusNat (Main.Succ x) Main.Zero = Main.Succ x; 10.22/4.23 primPlusNat (Main.Succ x) (Main.Succ y) = Main.Succ (Main.Succ (primPlusNat x y)); 10.22/4.23 10.22/4.23 stop :: MyBool -> a; 10.22/4.23 stop MyFalse = stop MyFalse; 10.22/4.23 10.22/4.23 } 10.22/4.23 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (5) Narrow (SOUND) 10.22/4.23 Haskell To QDPs 10.22/4.23 10.22/4.23 digraph dp_graph { 10.22/4.23 node [outthreshold=100, inthreshold=100];1[label="emEm",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 10.22/4.23 3[label="emEm xv3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 10.22/4.23 4[label="emEm xv3 xv4",fontsize=16,color="burlywood",shape="triangle"];51[label="xv3/Cons xv30 xv31",fontsize=10,color="white",style="solid",shape="box"];4 -> 51[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 51 -> 5[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 52[label="xv3/Nil",fontsize=10,color="white",style="solid",shape="box"];4 -> 52[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 52 -> 6[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 5[label="emEm (Cons xv30 xv31) xv4",fontsize=16,color="black",shape="box"];5 -> 7[label="",style="solid", color="black", weight=3]; 10.22/4.23 6[label="emEm Nil xv4",fontsize=16,color="black",shape="box"];6 -> 8[label="",style="solid", color="black", weight=3]; 10.22/4.23 7[label="emEm5 (Cons xv30 xv31) xv4",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3]; 10.22/4.23 8[label="emEm0 Nil xv4",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3]; 10.22/4.23 9[label="emEm4 (esEsMyInt xv4 (Pos Zero)) (Cons xv30 xv31) xv4",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3]; 10.22/4.23 10[label="error",fontsize=16,color="black",shape="triangle"];10 -> 12[label="",style="solid", color="black", weight=3]; 10.22/4.23 11[label="emEm4 (primEqInt xv4 (Pos Zero)) (Cons xv30 xv31) xv4",fontsize=16,color="burlywood",shape="box"];53[label="xv4/Pos xv40",fontsize=10,color="white",style="solid",shape="box"];11 -> 53[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 53 -> 13[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 54[label="xv4/Neg xv40",fontsize=10,color="white",style="solid",shape="box"];11 -> 54[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 54 -> 14[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 12[label="stop MyTrue",fontsize=16,color="black",shape="box"];12 -> 15[label="",style="solid", color="black", weight=3]; 10.22/4.23 13[label="emEm4 (primEqInt (Pos xv40) (Pos Zero)) (Cons xv30 xv31) (Pos xv40)",fontsize=16,color="burlywood",shape="box"];55[label="xv40/Succ xv400",fontsize=10,color="white",style="solid",shape="box"];13 -> 55[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 55 -> 16[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 56[label="xv40/Zero",fontsize=10,color="white",style="solid",shape="box"];13 -> 56[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 56 -> 17[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 14[label="emEm4 (primEqInt (Neg xv40) (Pos Zero)) (Cons xv30 xv31) (Neg xv40)",fontsize=16,color="burlywood",shape="box"];57[label="xv40/Succ xv400",fontsize=10,color="white",style="solid",shape="box"];14 -> 57[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 57 -> 18[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 58[label="xv40/Zero",fontsize=10,color="white",style="solid",shape="box"];14 -> 58[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 58 -> 19[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 15[label="error []",fontsize=16,color="red",shape="box"];16[label="emEm4 (primEqInt (Pos (Succ xv400)) (Pos Zero)) (Cons xv30 xv31) (Pos (Succ xv400))",fontsize=16,color="black",shape="box"];16 -> 20[label="",style="solid", color="black", weight=3]; 10.22/4.23 17[label="emEm4 (primEqInt (Pos Zero) (Pos Zero)) (Cons xv30 xv31) (Pos Zero)",fontsize=16,color="black",shape="box"];17 -> 21[label="",style="solid", color="black", weight=3]; 10.22/4.23 18[label="emEm4 (primEqInt (Neg (Succ xv400)) (Pos Zero)) (Cons xv30 xv31) (Neg (Succ xv400))",fontsize=16,color="black",shape="box"];18 -> 22[label="",style="solid", color="black", weight=3]; 10.22/4.23 19[label="emEm4 (primEqInt (Neg Zero) (Pos Zero)) (Cons xv30 xv31) (Neg Zero)",fontsize=16,color="black",shape="box"];19 -> 23[label="",style="solid", color="black", weight=3]; 10.22/4.23 20[label="emEm4 MyFalse (Cons xv30 xv31) (Pos (Succ xv400))",fontsize=16,color="black",shape="box"];20 -> 24[label="",style="solid", color="black", weight=3]; 10.22/4.23 21[label="emEm4 MyTrue (Cons xv30 xv31) (Pos Zero)",fontsize=16,color="black",shape="box"];21 -> 25[label="",style="solid", color="black", weight=3]; 10.22/4.23 22[label="emEm4 MyFalse (Cons xv30 xv31) (Neg (Succ xv400))",fontsize=16,color="black",shape="box"];22 -> 26[label="",style="solid", color="black", weight=3]; 10.22/4.23 23[label="emEm4 MyTrue (Cons xv30 xv31) (Neg Zero)",fontsize=16,color="black",shape="box"];23 -> 27[label="",style="solid", color="black", weight=3]; 10.22/4.23 24[label="emEm3 (Cons xv30 xv31) (Pos (Succ xv400))",fontsize=16,color="black",shape="box"];24 -> 28[label="",style="solid", color="black", weight=3]; 10.22/4.23 25[label="xv30",fontsize=16,color="green",shape="box"];26[label="emEm3 (Cons xv30 xv31) (Neg (Succ xv400))",fontsize=16,color="black",shape="box"];26 -> 29[label="",style="solid", color="black", weight=3]; 10.22/4.23 27[label="xv30",fontsize=16,color="green",shape="box"];28[label="emEm2 xv30 xv31 (Pos (Succ xv400)) (gtMyInt (Pos (Succ xv400)) (Pos Zero))",fontsize=16,color="black",shape="box"];28 -> 30[label="",style="solid", color="black", weight=3]; 10.22/4.23 29[label="emEm2 xv30 xv31 (Neg (Succ xv400)) (gtMyInt (Neg (Succ xv400)) (Pos Zero))",fontsize=16,color="black",shape="box"];29 -> 31[label="",style="solid", color="black", weight=3]; 10.22/4.23 30[label="emEm2 xv30 xv31 (Pos (Succ xv400)) (esEsOrdering (compareMyInt (Pos (Succ xv400)) (Pos Zero)) GT)",fontsize=16,color="black",shape="box"];30 -> 32[label="",style="solid", color="black", weight=3]; 10.22/4.23 31[label="emEm2 xv30 xv31 (Neg (Succ xv400)) (esEsOrdering (compareMyInt (Neg (Succ xv400)) (Pos Zero)) GT)",fontsize=16,color="black",shape="box"];31 -> 33[label="",style="solid", color="black", weight=3]; 10.22/4.23 32[label="emEm2 xv30 xv31 (Pos (Succ xv400)) (esEsOrdering (primCmpInt (Pos (Succ xv400)) (Pos Zero)) GT)",fontsize=16,color="black",shape="box"];32 -> 34[label="",style="solid", color="black", weight=3]; 10.22/4.23 33[label="emEm2 xv30 xv31 (Neg (Succ xv400)) (esEsOrdering (primCmpInt (Neg (Succ xv400)) (Pos Zero)) GT)",fontsize=16,color="black",shape="box"];33 -> 35[label="",style="solid", color="black", weight=3]; 10.22/4.23 34[label="emEm2 xv30 xv31 (Pos (Succ xv400)) (esEsOrdering (primCmpNat (Succ xv400) Zero) GT)",fontsize=16,color="black",shape="box"];34 -> 36[label="",style="solid", color="black", weight=3]; 10.22/4.23 35[label="emEm2 xv30 xv31 (Neg (Succ xv400)) (esEsOrdering LT GT)",fontsize=16,color="black",shape="box"];35 -> 37[label="",style="solid", color="black", weight=3]; 10.22/4.23 36[label="emEm2 xv30 xv31 (Pos (Succ xv400)) (esEsOrdering GT GT)",fontsize=16,color="black",shape="box"];36 -> 38[label="",style="solid", color="black", weight=3]; 10.22/4.23 37[label="emEm2 xv30 xv31 (Neg (Succ xv400)) MyFalse",fontsize=16,color="black",shape="box"];37 -> 39[label="",style="solid", color="black", weight=3]; 10.22/4.23 38[label="emEm2 xv30 xv31 (Pos (Succ xv400)) MyTrue",fontsize=16,color="black",shape="box"];38 -> 40[label="",style="solid", color="black", weight=3]; 10.22/4.23 39[label="emEm1 (Cons xv30 xv31) (Neg (Succ xv400))",fontsize=16,color="black",shape="box"];39 -> 41[label="",style="solid", color="black", weight=3]; 10.22/4.23 40 -> 4[label="",style="dashed", color="red", weight=0]; 10.22/4.23 40[label="emEm xv31 (msMyInt (Pos (Succ xv400)) (Pos (Succ Zero)))",fontsize=16,color="magenta"];40 -> 42[label="",style="dashed", color="magenta", weight=3]; 10.22/4.23 40 -> 43[label="",style="dashed", color="magenta", weight=3]; 10.22/4.23 41 -> 10[label="",style="dashed", color="red", weight=0]; 10.22/4.23 41[label="error",fontsize=16,color="magenta"];42[label="xv31",fontsize=16,color="green",shape="box"];43[label="msMyInt (Pos (Succ xv400)) (Pos (Succ Zero))",fontsize=16,color="black",shape="box"];43 -> 44[label="",style="solid", color="black", weight=3]; 10.22/4.23 44[label="primMinusInt (Pos (Succ xv400)) (Pos (Succ Zero))",fontsize=16,color="black",shape="box"];44 -> 45[label="",style="solid", color="black", weight=3]; 10.22/4.23 45[label="primMinusNat (Succ xv400) (Succ Zero)",fontsize=16,color="black",shape="box"];45 -> 46[label="",style="solid", color="black", weight=3]; 10.22/4.23 46[label="primMinusNat xv400 Zero",fontsize=16,color="burlywood",shape="box"];59[label="xv400/Succ xv4000",fontsize=10,color="white",style="solid",shape="box"];46 -> 59[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 59 -> 47[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 60[label="xv400/Zero",fontsize=10,color="white",style="solid",shape="box"];46 -> 60[label="",style="solid", color="burlywood", weight=9]; 10.22/4.23 60 -> 48[label="",style="solid", color="burlywood", weight=3]; 10.22/4.23 47[label="primMinusNat (Succ xv4000) Zero",fontsize=16,color="black",shape="box"];47 -> 49[label="",style="solid", color="black", weight=3]; 10.22/4.23 48[label="primMinusNat Zero Zero",fontsize=16,color="black",shape="box"];48 -> 50[label="",style="solid", color="black", weight=3]; 10.22/4.23 49[label="Pos (Succ xv4000)",fontsize=16,color="green",shape="box"];50[label="Pos Zero",fontsize=16,color="green",shape="box"];} 10.22/4.23 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (6) 10.22/4.23 Obligation: 10.22/4.23 Q DP problem: 10.22/4.23 The TRS P consists of the following rules: 10.22/4.23 10.22/4.23 new_emEm(Cons(xv30, xv31), Main.Pos(Main.Succ(xv400)), h) -> new_emEm(xv31, new_primMinusNat(xv400), h) 10.22/4.23 10.22/4.23 The TRS R consists of the following rules: 10.22/4.23 10.22/4.23 new_primMinusNat(Main.Succ(xv4000)) -> Main.Pos(Main.Succ(xv4000)) 10.22/4.23 new_primMinusNat(Main.Zero) -> Main.Pos(Main.Zero) 10.22/4.23 10.22/4.23 The set Q consists of the following terms: 10.22/4.23 10.22/4.23 new_primMinusNat(Main.Zero) 10.22/4.23 new_primMinusNat(Main.Succ(x0)) 10.22/4.23 10.22/4.23 We have to consider all minimal (P,Q,R)-chains. 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (7) TransformationProof (EQUIVALENT) 10.22/4.23 By narrowing [LPAR04] the rule new_emEm(Cons(xv30, xv31), Main.Pos(Main.Succ(xv400)), h) -> new_emEm(xv31, new_primMinusNat(xv400), h) at position [1] we obtained the following new rules [LPAR04]: 10.22/4.23 10.22/4.23 (new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Succ(x0))), y3) -> new_emEm(y1, Main.Pos(Main.Succ(x0)), y3),new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Succ(x0))), y3) -> new_emEm(y1, Main.Pos(Main.Succ(x0)), y3)) 10.22/4.23 (new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Zero)), y3) -> new_emEm(y1, Main.Pos(Main.Zero), y3),new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Zero)), y3) -> new_emEm(y1, Main.Pos(Main.Zero), y3)) 10.22/4.23 10.22/4.23 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (8) 10.22/4.23 Obligation: 10.22/4.23 Q DP problem: 10.22/4.23 The TRS P consists of the following rules: 10.22/4.23 10.22/4.23 new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Succ(x0))), y3) -> new_emEm(y1, Main.Pos(Main.Succ(x0)), y3) 10.22/4.23 new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Zero)), y3) -> new_emEm(y1, Main.Pos(Main.Zero), y3) 10.22/4.23 10.22/4.23 The TRS R consists of the following rules: 10.22/4.23 10.22/4.23 new_primMinusNat(Main.Succ(xv4000)) -> Main.Pos(Main.Succ(xv4000)) 10.22/4.23 new_primMinusNat(Main.Zero) -> Main.Pos(Main.Zero) 10.22/4.23 10.22/4.23 The set Q consists of the following terms: 10.22/4.23 10.22/4.23 new_primMinusNat(Main.Zero) 10.22/4.23 new_primMinusNat(Main.Succ(x0)) 10.22/4.23 10.22/4.23 We have to consider all minimal (P,Q,R)-chains. 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (9) DependencyGraphProof (EQUIVALENT) 10.22/4.23 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (10) 10.22/4.23 Obligation: 10.22/4.23 Q DP problem: 10.22/4.23 The TRS P consists of the following rules: 10.22/4.23 10.22/4.23 new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Succ(x0))), y3) -> new_emEm(y1, Main.Pos(Main.Succ(x0)), y3) 10.22/4.23 10.22/4.23 The TRS R consists of the following rules: 10.22/4.23 10.22/4.23 new_primMinusNat(Main.Succ(xv4000)) -> Main.Pos(Main.Succ(xv4000)) 10.22/4.23 new_primMinusNat(Main.Zero) -> Main.Pos(Main.Zero) 10.22/4.23 10.22/4.23 The set Q consists of the following terms: 10.22/4.23 10.22/4.23 new_primMinusNat(Main.Zero) 10.22/4.23 new_primMinusNat(Main.Succ(x0)) 10.22/4.23 10.22/4.23 We have to consider all minimal (P,Q,R)-chains. 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (11) UsableRulesProof (EQUIVALENT) 10.22/4.23 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. 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (12) 10.22/4.23 Obligation: 10.22/4.23 Q DP problem: 10.22/4.23 The TRS P consists of the following rules: 10.22/4.23 10.22/4.23 new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Succ(x0))), y3) -> new_emEm(y1, Main.Pos(Main.Succ(x0)), y3) 10.22/4.23 10.22/4.23 R is empty. 10.22/4.23 The set Q consists of the following terms: 10.22/4.23 10.22/4.23 new_primMinusNat(Main.Zero) 10.22/4.23 new_primMinusNat(Main.Succ(x0)) 10.22/4.23 10.22/4.23 We have to consider all minimal (P,Q,R)-chains. 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (13) QReductionProof (EQUIVALENT) 10.22/4.23 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.22/4.23 10.22/4.23 new_primMinusNat(Main.Zero) 10.22/4.23 new_primMinusNat(Main.Succ(x0)) 10.22/4.23 10.22/4.23 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (14) 10.22/4.23 Obligation: 10.22/4.23 Q DP problem: 10.22/4.23 The TRS P consists of the following rules: 10.22/4.23 10.22/4.23 new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Succ(x0))), y3) -> new_emEm(y1, Main.Pos(Main.Succ(x0)), y3) 10.22/4.23 10.22/4.23 R is empty. 10.22/4.23 Q is empty. 10.22/4.23 We have to consider all minimal (P,Q,R)-chains. 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (15) QDPSizeChangeProof (EQUIVALENT) 10.22/4.23 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. 10.22/4.23 10.22/4.23 From the DPs we obtained the following set of size-change graphs: 10.22/4.23 *new_emEm(Cons(y0, y1), Main.Pos(Main.Succ(Main.Succ(x0))), y3) -> new_emEm(y1, Main.Pos(Main.Succ(x0)), y3) 10.22/4.23 The graph contains the following edges 1 > 1, 3 >= 3 10.22/4.23 10.22/4.23 10.22/4.23 ---------------------------------------- 10.22/4.23 10.22/4.23 (16) 10.22/4.23 YES 10.46/4.50 EOF