10.61/4.54 YES 12.53/5.06 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 12.53/5.06 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 12.53/5.06 12.53/5.06 12.53/5.06 H-Termination with start terms of the given HASKELL could be proven: 12.53/5.06 12.53/5.06 (0) HASKELL 12.53/5.06 (1) BR [EQUIVALENT, 0 ms] 12.53/5.06 (2) HASKELL 12.53/5.06 (3) COR [EQUIVALENT, 0 ms] 12.53/5.06 (4) HASKELL 12.53/5.06 (5) Narrow [SOUND, 0 ms] 12.53/5.06 (6) AND 12.53/5.06 (7) QDP 12.53/5.06 (8) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.53/5.06 (9) YES 12.53/5.06 (10) QDP 12.53/5.06 (11) TransformationProof [EQUIVALENT, 0 ms] 12.53/5.06 (12) QDP 12.53/5.06 (13) UsableRulesProof [EQUIVALENT, 0 ms] 12.53/5.06 (14) QDP 12.53/5.06 (15) QReductionProof [EQUIVALENT, 0 ms] 12.53/5.06 (16) QDP 12.53/5.06 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.53/5.06 (18) YES 12.53/5.06 (19) QDP 12.53/5.06 (20) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.53/5.06 (21) YES 12.53/5.06 (22) QDP 12.53/5.06 (23) TransformationProof [EQUIVALENT, 0 ms] 12.53/5.06 (24) QDP 12.53/5.06 (25) UsableRulesProof [EQUIVALENT, 0 ms] 12.53/5.06 (26) QDP 12.53/5.06 (27) QReductionProof [EQUIVALENT, 0 ms] 12.53/5.06 (28) QDP 12.53/5.06 (29) QDPSizeChangeProof [EQUIVALENT, 0 ms] 12.53/5.06 (30) YES 12.53/5.06 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (0) 12.53/5.06 Obligation: 12.53/5.06 mainModule Main 12.53/5.06 module Maybe where { 12.53/5.06 import qualified List; 12.53/5.06 import qualified Main; 12.53/5.06 import qualified Prelude; 12.53/5.06 } 12.53/5.06 module List where { 12.53/5.06 import qualified Main; 12.53/5.06 import qualified Maybe; 12.53/5.06 import qualified Prelude; 12.53/5.06 isPrefixOf :: Eq a => [a] -> [a] -> Bool; 12.53/5.06 isPrefixOf [] _ = True; 12.53/5.06 isPrefixOf _ [] = False; 12.53/5.06 isPrefixOf (x : xs) (y : ys) = x == y && isPrefixOf xs ys; 12.53/5.06 12.53/5.06 isSuffixOf :: Eq a => [a] -> [a] -> Bool; 12.53/5.06 isSuffixOf x y = reverse x `isPrefixOf` reverse y; 12.53/5.06 12.53/5.06 } 12.53/5.06 module Main where { 12.53/5.06 import qualified List; 12.53/5.06 import qualified Maybe; 12.53/5.06 import qualified Prelude; 12.53/5.06 } 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (1) BR (EQUIVALENT) 12.53/5.06 Replaced joker patterns by fresh variables and removed binding patterns. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (2) 12.53/5.06 Obligation: 12.53/5.06 mainModule Main 12.53/5.06 module Maybe where { 12.53/5.06 import qualified List; 12.53/5.06 import qualified Main; 12.53/5.06 import qualified Prelude; 12.53/5.06 } 12.53/5.06 module List where { 12.53/5.06 import qualified Main; 12.53/5.06 import qualified Maybe; 12.53/5.06 import qualified Prelude; 12.53/5.06 isPrefixOf :: Eq a => [a] -> [a] -> Bool; 12.53/5.06 isPrefixOf [] vy = True; 12.53/5.06 isPrefixOf vz [] = False; 12.53/5.06 isPrefixOf (x : xs) (y : ys) = x == y && isPrefixOf xs ys; 12.53/5.06 12.53/5.06 isSuffixOf :: Eq a => [a] -> [a] -> Bool; 12.53/5.06 isSuffixOf x y = reverse x `isPrefixOf` reverse y; 12.53/5.06 12.53/5.06 } 12.53/5.06 module Main where { 12.53/5.06 import qualified List; 12.53/5.06 import qualified Maybe; 12.53/5.06 import qualified Prelude; 12.53/5.06 } 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (3) COR (EQUIVALENT) 12.53/5.06 Cond Reductions: 12.53/5.06 The following Function with conditions 12.53/5.06 "undefined |Falseundefined; 12.53/5.06 " 12.53/5.06 is transformed to 12.53/5.06 "undefined = undefined1; 12.53/5.06 " 12.53/5.06 "undefined0 True = undefined; 12.53/5.06 " 12.53/5.06 "undefined1 = undefined0 False; 12.53/5.06 " 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (4) 12.53/5.06 Obligation: 12.53/5.06 mainModule Main 12.53/5.06 module Maybe where { 12.53/5.06 import qualified List; 12.53/5.06 import qualified Main; 12.53/5.06 import qualified Prelude; 12.53/5.06 } 12.53/5.06 module List where { 12.53/5.06 import qualified Main; 12.53/5.06 import qualified Maybe; 12.53/5.06 import qualified Prelude; 12.53/5.06 isPrefixOf :: Eq a => [a] -> [a] -> Bool; 12.53/5.06 isPrefixOf [] vy = True; 12.53/5.06 isPrefixOf vz [] = False; 12.53/5.06 isPrefixOf (x : xs) (y : ys) = x == y && isPrefixOf xs ys; 12.53/5.06 12.53/5.06 isSuffixOf :: Eq a => [a] -> [a] -> Bool; 12.53/5.06 isSuffixOf x y = reverse x `isPrefixOf` reverse y; 12.53/5.06 12.53/5.06 } 12.53/5.06 module Main where { 12.53/5.06 import qualified List; 12.53/5.06 import qualified Maybe; 12.53/5.06 import qualified Prelude; 12.53/5.06 } 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (5) Narrow (SOUND) 12.53/5.06 Haskell To QDPs 12.53/5.06 12.53/5.06 digraph dp_graph { 12.53/5.06 node [outthreshold=100, inthreshold=100];1[label="List.isSuffixOf",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 12.53/5.06 3[label="List.isSuffixOf wu3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 12.53/5.06 4[label="List.isSuffixOf wu3 wu4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 12.53/5.06 5[label="List.isPrefixOf (reverse wu3) (reverse wu4)",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3]; 12.53/5.06 6[label="List.isPrefixOf (foldl (flip (:)) [] wu3) (reverse wu4)",fontsize=16,color="burlywood",shape="box"];404[label="wu3/wu30 : wu31",fontsize=10,color="white",style="solid",shape="box"];6 -> 404[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 404 -> 7[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 405[label="wu3/[]",fontsize=10,color="white",style="solid",shape="box"];6 -> 405[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 405 -> 8[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 7[label="List.isPrefixOf (foldl (flip (:)) [] (wu30 : wu31)) (reverse wu4)",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3]; 12.53/5.06 8[label="List.isPrefixOf (foldl (flip (:)) [] []) (reverse wu4)",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3]; 12.53/5.06 9 -> 234[label="",style="dashed", color="red", weight=0]; 12.53/5.06 9[label="List.isPrefixOf (foldl (flip (:)) (flip (:) [] wu30) wu31) (reverse wu4)",fontsize=16,color="magenta"];9 -> 235[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 9 -> 236[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 9 -> 237[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 9 -> 238[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 10[label="List.isPrefixOf [] (reverse wu4)",fontsize=16,color="black",shape="box"];10 -> 13[label="",style="solid", color="black", weight=3]; 12.53/5.06 235[label="wu31",fontsize=16,color="green",shape="box"];236[label="wu4",fontsize=16,color="green",shape="box"];237[label="[]",fontsize=16,color="green",shape="box"];238[label="wu30",fontsize=16,color="green",shape="box"];234[label="List.isPrefixOf (foldl (flip (:)) (flip (:) wu14 wu15) wu16) (reverse wu17)",fontsize=16,color="burlywood",shape="triangle"];406[label="wu16/wu160 : wu161",fontsize=10,color="white",style="solid",shape="box"];234 -> 406[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 406 -> 271[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 407[label="wu16/[]",fontsize=10,color="white",style="solid",shape="box"];234 -> 407[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 407 -> 272[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 13[label="True",fontsize=16,color="green",shape="box"];271[label="List.isPrefixOf (foldl (flip (:)) (flip (:) wu14 wu15) (wu160 : wu161)) (reverse wu17)",fontsize=16,color="black",shape="box"];271 -> 273[label="",style="solid", color="black", weight=3]; 12.53/5.06 272[label="List.isPrefixOf (foldl (flip (:)) (flip (:) wu14 wu15) []) (reverse wu17)",fontsize=16,color="black",shape="box"];272 -> 274[label="",style="solid", color="black", weight=3]; 12.53/5.06 273 -> 234[label="",style="dashed", color="red", weight=0]; 12.53/5.06 273[label="List.isPrefixOf (foldl (flip (:)) (flip (:) (flip (:) wu14 wu15) wu160) wu161) (reverse wu17)",fontsize=16,color="magenta"];273 -> 275[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 273 -> 276[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 273 -> 277[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 274[label="List.isPrefixOf (flip (:) wu14 wu15) (reverse wu17)",fontsize=16,color="black",shape="box"];274 -> 278[label="",style="solid", color="black", weight=3]; 12.53/5.06 275[label="wu161",fontsize=16,color="green",shape="box"];276[label="flip (:) wu14 wu15",fontsize=16,color="black",shape="triangle"];276 -> 279[label="",style="solid", color="black", weight=3]; 12.53/5.06 277[label="wu160",fontsize=16,color="green",shape="box"];278[label="List.isPrefixOf ((:) wu15 wu14) (reverse wu17)",fontsize=16,color="black",shape="box"];278 -> 280[label="",style="solid", color="black", weight=3]; 12.53/5.06 279[label="(:) wu15 wu14",fontsize=16,color="green",shape="box"];280 -> 285[label="",style="dashed", color="red", weight=0]; 12.53/5.06 280[label="List.isPrefixOf ((:) wu15 wu14) (foldl (flip (:)) [] wu17)",fontsize=16,color="magenta"];280 -> 286[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 280 -> 287[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 286[label="wu17",fontsize=16,color="green",shape="box"];287[label="[]",fontsize=16,color="green",shape="box"];285[label="List.isPrefixOf ((:) wu15 wu14) (foldl (flip (:)) wu18 wu171)",fontsize=16,color="burlywood",shape="triangle"];408[label="wu171/wu1710 : wu1711",fontsize=10,color="white",style="solid",shape="box"];285 -> 408[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 408 -> 289[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 409[label="wu171/[]",fontsize=10,color="white",style="solid",shape="box"];285 -> 409[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 409 -> 290[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 289[label="List.isPrefixOf ((:) wu15 wu14) (foldl (flip (:)) wu18 (wu1710 : wu1711))",fontsize=16,color="black",shape="box"];289 -> 291[label="",style="solid", color="black", weight=3]; 12.53/5.06 290[label="List.isPrefixOf ((:) wu15 wu14) (foldl (flip (:)) wu18 [])",fontsize=16,color="black",shape="box"];290 -> 292[label="",style="solid", color="black", weight=3]; 12.53/5.06 291 -> 285[label="",style="dashed", color="red", weight=0]; 12.53/5.06 291[label="List.isPrefixOf ((:) wu15 wu14) (foldl (flip (:)) (flip (:) wu18 wu1710) wu1711)",fontsize=16,color="magenta"];291 -> 293[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 291 -> 294[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 292[label="List.isPrefixOf ((:) wu15 wu14) wu18",fontsize=16,color="burlywood",shape="box"];410[label="wu18/wu180 : wu181",fontsize=10,color="white",style="solid",shape="box"];292 -> 410[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 410 -> 295[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 411[label="wu18/[]",fontsize=10,color="white",style="solid",shape="box"];292 -> 411[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 411 -> 296[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 293[label="wu1711",fontsize=16,color="green",shape="box"];294 -> 276[label="",style="dashed", color="red", weight=0]; 12.53/5.06 294[label="flip (:) wu18 wu1710",fontsize=16,color="magenta"];294 -> 297[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 294 -> 298[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 295[label="List.isPrefixOf ((:) wu15 wu14) (wu180 : wu181)",fontsize=16,color="black",shape="box"];295 -> 299[label="",style="solid", color="black", weight=3]; 12.53/5.06 296[label="List.isPrefixOf ((:) wu15 wu14) []",fontsize=16,color="black",shape="box"];296 -> 300[label="",style="solid", color="black", weight=3]; 12.53/5.06 297[label="wu18",fontsize=16,color="green",shape="box"];298[label="wu1710",fontsize=16,color="green",shape="box"];299 -> 301[label="",style="dashed", color="red", weight=0]; 12.53/5.06 299[label="wu15 == wu180 && List.isPrefixOf wu14 wu181",fontsize=16,color="magenta"];299 -> 302[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 299 -> 303[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 299 -> 304[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 300[label="False",fontsize=16,color="green",shape="box"];302[label="wu14",fontsize=16,color="green",shape="box"];303[label="wu15 == wu180",fontsize=16,color="blue",shape="box"];412[label="== :: (Ratio a) -> (Ratio a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 412[label="",style="solid", color="blue", weight=9]; 12.53/5.06 412 -> 305[label="",style="solid", color="blue", weight=3]; 12.53/5.06 413[label="== :: ([] a) -> ([] a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 413[label="",style="solid", color="blue", weight=9]; 12.53/5.06 413 -> 306[label="",style="solid", color="blue", weight=3]; 12.53/5.06 414[label="== :: () -> () -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 414[label="",style="solid", color="blue", weight=9]; 12.53/5.06 414 -> 307[label="",style="solid", color="blue", weight=3]; 12.53/5.06 415[label="== :: ((@2) a b) -> ((@2) a b) -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 415[label="",style="solid", color="blue", weight=9]; 12.53/5.06 415 -> 308[label="",style="solid", color="blue", weight=3]; 12.53/5.06 416[label="== :: (Maybe a) -> (Maybe a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 416[label="",style="solid", color="blue", weight=9]; 12.53/5.06 416 -> 309[label="",style="solid", color="blue", weight=3]; 12.53/5.06 417[label="== :: ((@3) a b c) -> ((@3) a b c) -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 417[label="",style="solid", color="blue", weight=9]; 12.53/5.06 417 -> 310[label="",style="solid", color="blue", weight=3]; 12.53/5.06 418[label="== :: Char -> Char -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 418[label="",style="solid", color="blue", weight=9]; 12.53/5.06 418 -> 311[label="",style="solid", color="blue", weight=3]; 12.53/5.06 419[label="== :: Float -> Float -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 419[label="",style="solid", color="blue", weight=9]; 12.53/5.06 419 -> 312[label="",style="solid", color="blue", weight=3]; 12.53/5.06 420[label="== :: Ordering -> Ordering -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 420[label="",style="solid", color="blue", weight=9]; 12.53/5.06 420 -> 313[label="",style="solid", color="blue", weight=3]; 12.53/5.06 421[label="== :: Integer -> Integer -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 421[label="",style="solid", color="blue", weight=9]; 12.53/5.06 421 -> 314[label="",style="solid", color="blue", weight=3]; 12.53/5.06 422[label="== :: Bool -> Bool -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 422[label="",style="solid", color="blue", weight=9]; 12.53/5.06 422 -> 315[label="",style="solid", color="blue", weight=3]; 12.53/5.06 423[label="== :: (Either a b) -> (Either a b) -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 423[label="",style="solid", color="blue", weight=9]; 12.53/5.06 423 -> 316[label="",style="solid", color="blue", weight=3]; 12.53/5.06 424[label="== :: Double -> Double -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 424[label="",style="solid", color="blue", weight=9]; 12.53/5.06 424 -> 317[label="",style="solid", color="blue", weight=3]; 12.53/5.06 425[label="== :: Int -> Int -> Bool",fontsize=10,color="white",style="solid",shape="box"];303 -> 425[label="",style="solid", color="blue", weight=9]; 12.53/5.06 425 -> 318[label="",style="solid", color="blue", weight=3]; 12.53/5.06 304[label="wu181",fontsize=16,color="green",shape="box"];301[label="wu23 && List.isPrefixOf wu24 wu25",fontsize=16,color="burlywood",shape="triangle"];426[label="wu23/False",fontsize=10,color="white",style="solid",shape="box"];301 -> 426[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 426 -> 319[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 427[label="wu23/True",fontsize=10,color="white",style="solid",shape="box"];301 -> 427[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 427 -> 320[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 305[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];305 -> 321[label="",style="solid", color="black", weight=3]; 12.53/5.06 306[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];306 -> 322[label="",style="solid", color="black", weight=3]; 12.53/5.06 307[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];307 -> 323[label="",style="solid", color="black", weight=3]; 12.53/5.06 308[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];308 -> 324[label="",style="solid", color="black", weight=3]; 12.53/5.06 309[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];309 -> 325[label="",style="solid", color="black", weight=3]; 12.53/5.06 310[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];310 -> 326[label="",style="solid", color="black", weight=3]; 12.53/5.06 311[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];311 -> 327[label="",style="solid", color="black", weight=3]; 12.53/5.06 312[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];312 -> 328[label="",style="solid", color="black", weight=3]; 12.53/5.06 313[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];313 -> 329[label="",style="solid", color="black", weight=3]; 12.53/5.06 314[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];314 -> 330[label="",style="solid", color="black", weight=3]; 12.53/5.06 315[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];315 -> 331[label="",style="solid", color="black", weight=3]; 12.53/5.06 316[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];316 -> 332[label="",style="solid", color="black", weight=3]; 12.53/5.06 317[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];317 -> 333[label="",style="solid", color="black", weight=3]; 12.53/5.06 318[label="wu15 == wu180",fontsize=16,color="black",shape="triangle"];318 -> 334[label="",style="solid", color="black", weight=3]; 12.53/5.06 319[label="False && List.isPrefixOf wu24 wu25",fontsize=16,color="black",shape="box"];319 -> 335[label="",style="solid", color="black", weight=3]; 12.53/5.06 320[label="True && List.isPrefixOf wu24 wu25",fontsize=16,color="black",shape="box"];320 -> 336[label="",style="solid", color="black", weight=3]; 12.53/5.06 321[label="error []",fontsize=16,color="red",shape="box"];322[label="error []",fontsize=16,color="red",shape="box"];323[label="error []",fontsize=16,color="red",shape="box"];324[label="error []",fontsize=16,color="red",shape="box"];325[label="error []",fontsize=16,color="red",shape="box"];326[label="error []",fontsize=16,color="red",shape="box"];327[label="primEqChar wu15 wu180",fontsize=16,color="burlywood",shape="box"];428[label="wu15/Char wu150",fontsize=10,color="white",style="solid",shape="box"];327 -> 428[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 428 -> 337[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 328[label="error []",fontsize=16,color="red",shape="box"];329[label="error []",fontsize=16,color="red",shape="box"];330[label="error []",fontsize=16,color="red",shape="box"];331[label="error []",fontsize=16,color="red",shape="box"];332[label="error []",fontsize=16,color="red",shape="box"];333[label="error []",fontsize=16,color="red",shape="box"];334[label="error []",fontsize=16,color="red",shape="box"];335[label="False",fontsize=16,color="green",shape="box"];336[label="List.isPrefixOf wu24 wu25",fontsize=16,color="burlywood",shape="box"];429[label="wu24/wu240 : wu241",fontsize=10,color="white",style="solid",shape="box"];336 -> 429[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 429 -> 338[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 430[label="wu24/[]",fontsize=10,color="white",style="solid",shape="box"];336 -> 430[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 430 -> 339[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 337[label="primEqChar (Char wu150) wu180",fontsize=16,color="burlywood",shape="box"];431[label="wu180/Char wu1800",fontsize=10,color="white",style="solid",shape="box"];337 -> 431[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 431 -> 340[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 338[label="List.isPrefixOf (wu240 : wu241) wu25",fontsize=16,color="burlywood",shape="box"];432[label="wu25/wu250 : wu251",fontsize=10,color="white",style="solid",shape="box"];338 -> 432[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 432 -> 341[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 433[label="wu25/[]",fontsize=10,color="white",style="solid",shape="box"];338 -> 433[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 433 -> 342[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 339[label="List.isPrefixOf [] wu25",fontsize=16,color="black",shape="box"];339 -> 343[label="",style="solid", color="black", weight=3]; 12.53/5.06 340[label="primEqChar (Char wu150) (Char wu1800)",fontsize=16,color="black",shape="box"];340 -> 344[label="",style="solid", color="black", weight=3]; 12.53/5.06 341[label="List.isPrefixOf (wu240 : wu241) (wu250 : wu251)",fontsize=16,color="black",shape="box"];341 -> 345[label="",style="solid", color="black", weight=3]; 12.53/5.06 342[label="List.isPrefixOf (wu240 : wu241) []",fontsize=16,color="black",shape="box"];342 -> 346[label="",style="solid", color="black", weight=3]; 12.53/5.06 343[label="True",fontsize=16,color="green",shape="box"];344[label="primEqNat wu150 wu1800",fontsize=16,color="burlywood",shape="triangle"];434[label="wu150/Succ wu1500",fontsize=10,color="white",style="solid",shape="box"];344 -> 434[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 434 -> 347[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 435[label="wu150/Zero",fontsize=10,color="white",style="solid",shape="box"];344 -> 435[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 435 -> 348[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 345 -> 301[label="",style="dashed", color="red", weight=0]; 12.53/5.06 345[label="wu240 == wu250 && List.isPrefixOf wu241 wu251",fontsize=16,color="magenta"];345 -> 349[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 345 -> 350[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 345 -> 351[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 346[label="False",fontsize=16,color="green",shape="box"];347[label="primEqNat (Succ wu1500) wu1800",fontsize=16,color="burlywood",shape="box"];436[label="wu1800/Succ wu18000",fontsize=10,color="white",style="solid",shape="box"];347 -> 436[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 436 -> 352[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 437[label="wu1800/Zero",fontsize=10,color="white",style="solid",shape="box"];347 -> 437[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 437 -> 353[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 348[label="primEqNat Zero wu1800",fontsize=16,color="burlywood",shape="box"];438[label="wu1800/Succ wu18000",fontsize=10,color="white",style="solid",shape="box"];348 -> 438[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 438 -> 354[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 439[label="wu1800/Zero",fontsize=10,color="white",style="solid",shape="box"];348 -> 439[label="",style="solid", color="burlywood", weight=9]; 12.53/5.06 439 -> 355[label="",style="solid", color="burlywood", weight=3]; 12.53/5.06 349[label="wu241",fontsize=16,color="green",shape="box"];350[label="wu240 == wu250",fontsize=16,color="blue",shape="box"];440[label="== :: (Ratio a) -> (Ratio a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 440[label="",style="solid", color="blue", weight=9]; 12.53/5.06 440 -> 356[label="",style="solid", color="blue", weight=3]; 12.53/5.06 441[label="== :: ([] a) -> ([] a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 441[label="",style="solid", color="blue", weight=9]; 12.53/5.06 441 -> 357[label="",style="solid", color="blue", weight=3]; 12.53/5.06 442[label="== :: () -> () -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 442[label="",style="solid", color="blue", weight=9]; 12.53/5.06 442 -> 358[label="",style="solid", color="blue", weight=3]; 12.53/5.06 443[label="== :: ((@2) a b) -> ((@2) a b) -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 443[label="",style="solid", color="blue", weight=9]; 12.53/5.06 443 -> 359[label="",style="solid", color="blue", weight=3]; 12.53/5.06 444[label="== :: (Maybe a) -> (Maybe a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 444[label="",style="solid", color="blue", weight=9]; 12.53/5.06 444 -> 360[label="",style="solid", color="blue", weight=3]; 12.53/5.06 445[label="== :: ((@3) a b c) -> ((@3) a b c) -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 445[label="",style="solid", color="blue", weight=9]; 12.53/5.06 445 -> 361[label="",style="solid", color="blue", weight=3]; 12.53/5.06 446[label="== :: Char -> Char -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 446[label="",style="solid", color="blue", weight=9]; 12.53/5.06 446 -> 362[label="",style="solid", color="blue", weight=3]; 12.53/5.06 447[label="== :: Float -> Float -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 447[label="",style="solid", color="blue", weight=9]; 12.53/5.06 447 -> 363[label="",style="solid", color="blue", weight=3]; 12.53/5.06 448[label="== :: Ordering -> Ordering -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 448[label="",style="solid", color="blue", weight=9]; 12.53/5.06 448 -> 364[label="",style="solid", color="blue", weight=3]; 12.53/5.06 449[label="== :: Integer -> Integer -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 449[label="",style="solid", color="blue", weight=9]; 12.53/5.06 449 -> 365[label="",style="solid", color="blue", weight=3]; 12.53/5.06 450[label="== :: Bool -> Bool -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 450[label="",style="solid", color="blue", weight=9]; 12.53/5.06 450 -> 366[label="",style="solid", color="blue", weight=3]; 12.53/5.06 451[label="== :: (Either a b) -> (Either a b) -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 451[label="",style="solid", color="blue", weight=9]; 12.53/5.06 451 -> 367[label="",style="solid", color="blue", weight=3]; 12.53/5.06 452[label="== :: Double -> Double -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 452[label="",style="solid", color="blue", weight=9]; 12.53/5.06 452 -> 368[label="",style="solid", color="blue", weight=3]; 12.53/5.06 453[label="== :: Int -> Int -> Bool",fontsize=10,color="white",style="solid",shape="box"];350 -> 453[label="",style="solid", color="blue", weight=9]; 12.53/5.06 453 -> 369[label="",style="solid", color="blue", weight=3]; 12.53/5.06 351[label="wu251",fontsize=16,color="green",shape="box"];352[label="primEqNat (Succ wu1500) (Succ wu18000)",fontsize=16,color="black",shape="box"];352 -> 370[label="",style="solid", color="black", weight=3]; 12.53/5.06 353[label="primEqNat (Succ wu1500) Zero",fontsize=16,color="black",shape="box"];353 -> 371[label="",style="solid", color="black", weight=3]; 12.53/5.06 354[label="primEqNat Zero (Succ wu18000)",fontsize=16,color="black",shape="box"];354 -> 372[label="",style="solid", color="black", weight=3]; 12.53/5.06 355[label="primEqNat Zero Zero",fontsize=16,color="black",shape="box"];355 -> 373[label="",style="solid", color="black", weight=3]; 12.53/5.06 356 -> 305[label="",style="dashed", color="red", weight=0]; 12.53/5.06 356[label="wu240 == wu250",fontsize=16,color="magenta"];356 -> 374[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 356 -> 375[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 357 -> 306[label="",style="dashed", color="red", weight=0]; 12.53/5.06 357[label="wu240 == wu250",fontsize=16,color="magenta"];357 -> 376[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 357 -> 377[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 358 -> 307[label="",style="dashed", color="red", weight=0]; 12.53/5.06 358[label="wu240 == wu250",fontsize=16,color="magenta"];358 -> 378[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 358 -> 379[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 359 -> 308[label="",style="dashed", color="red", weight=0]; 12.53/5.06 359[label="wu240 == wu250",fontsize=16,color="magenta"];359 -> 380[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 359 -> 381[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 360 -> 309[label="",style="dashed", color="red", weight=0]; 12.53/5.06 360[label="wu240 == wu250",fontsize=16,color="magenta"];360 -> 382[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 360 -> 383[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 361 -> 310[label="",style="dashed", color="red", weight=0]; 12.53/5.06 361[label="wu240 == wu250",fontsize=16,color="magenta"];361 -> 384[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 361 -> 385[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 362 -> 311[label="",style="dashed", color="red", weight=0]; 12.53/5.06 362[label="wu240 == wu250",fontsize=16,color="magenta"];362 -> 386[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 362 -> 387[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 363 -> 312[label="",style="dashed", color="red", weight=0]; 12.53/5.06 363[label="wu240 == wu250",fontsize=16,color="magenta"];363 -> 388[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 363 -> 389[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 364 -> 313[label="",style="dashed", color="red", weight=0]; 12.53/5.06 364[label="wu240 == wu250",fontsize=16,color="magenta"];364 -> 390[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 364 -> 391[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 365 -> 314[label="",style="dashed", color="red", weight=0]; 12.53/5.06 365[label="wu240 == wu250",fontsize=16,color="magenta"];365 -> 392[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 365 -> 393[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 366 -> 315[label="",style="dashed", color="red", weight=0]; 12.53/5.06 366[label="wu240 == wu250",fontsize=16,color="magenta"];366 -> 394[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 366 -> 395[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 367 -> 316[label="",style="dashed", color="red", weight=0]; 12.53/5.06 367[label="wu240 == wu250",fontsize=16,color="magenta"];367 -> 396[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 367 -> 397[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 368 -> 317[label="",style="dashed", color="red", weight=0]; 12.53/5.06 368[label="wu240 == wu250",fontsize=16,color="magenta"];368 -> 398[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 368 -> 399[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 369 -> 318[label="",style="dashed", color="red", weight=0]; 12.53/5.06 369[label="wu240 == wu250",fontsize=16,color="magenta"];369 -> 400[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 369 -> 401[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 370 -> 344[label="",style="dashed", color="red", weight=0]; 12.53/5.06 370[label="primEqNat wu1500 wu18000",fontsize=16,color="magenta"];370 -> 402[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 370 -> 403[label="",style="dashed", color="magenta", weight=3]; 12.53/5.06 371[label="False",fontsize=16,color="green",shape="box"];372[label="False",fontsize=16,color="green",shape="box"];373[label="True",fontsize=16,color="green",shape="box"];374[label="wu250",fontsize=16,color="green",shape="box"];375[label="wu240",fontsize=16,color="green",shape="box"];376[label="wu250",fontsize=16,color="green",shape="box"];377[label="wu240",fontsize=16,color="green",shape="box"];378[label="wu250",fontsize=16,color="green",shape="box"];379[label="wu240",fontsize=16,color="green",shape="box"];380[label="wu250",fontsize=16,color="green",shape="box"];381[label="wu240",fontsize=16,color="green",shape="box"];382[label="wu250",fontsize=16,color="green",shape="box"];383[label="wu240",fontsize=16,color="green",shape="box"];384[label="wu250",fontsize=16,color="green",shape="box"];385[label="wu240",fontsize=16,color="green",shape="box"];386[label="wu250",fontsize=16,color="green",shape="box"];387[label="wu240",fontsize=16,color="green",shape="box"];388[label="wu250",fontsize=16,color="green",shape="box"];389[label="wu240",fontsize=16,color="green",shape="box"];390[label="wu250",fontsize=16,color="green",shape="box"];391[label="wu240",fontsize=16,color="green",shape="box"];392[label="wu250",fontsize=16,color="green",shape="box"];393[label="wu240",fontsize=16,color="green",shape="box"];394[label="wu250",fontsize=16,color="green",shape="box"];395[label="wu240",fontsize=16,color="green",shape="box"];396[label="wu250",fontsize=16,color="green",shape="box"];397[label="wu240",fontsize=16,color="green",shape="box"];398[label="wu250",fontsize=16,color="green",shape="box"];399[label="wu240",fontsize=16,color="green",shape="box"];400[label="wu250",fontsize=16,color="green",shape="box"];401[label="wu240",fontsize=16,color="green",shape="box"];402[label="wu18000",fontsize=16,color="green",shape="box"];403[label="wu1500",fontsize=16,color="green",shape="box"];} 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (6) 12.53/5.06 Complex Obligation (AND) 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (7) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_asAs(True, :(wu240, wu241), :(wu250, wu251), ba) -> new_asAs(new_esEs(wu240, wu250, ba), wu241, wu251, ba) 12.53/5.06 12.53/5.06 The TRS R consists of the following rules: 12.53/5.06 12.53/5.06 new_esEs0(wu15, wu180, bb, bc) -> error([]) 12.53/5.06 new_esEs(wu240, wu250, ty_Float) -> new_esEs8(wu240, wu250) 12.53/5.06 new_esEs(wu240, wu250, ty_Bool) -> new_esEs2(wu240, wu250) 12.53/5.06 new_esEs(wu240, wu250, app(ty_Maybe, cd)) -> new_esEs3(wu240, wu250, cd) 12.53/5.06 new_primEqNat0(Zero, Zero) -> True 12.53/5.06 new_esEs11(wu15, wu180) -> error([]) 12.53/5.06 new_esEs5(wu15, wu180, be, bf) -> error([]) 12.53/5.06 new_esEs1(wu15, wu180) -> error([]) 12.53/5.06 new_esEs13(Char(wu150), Char(wu1800)) -> new_primEqNat0(wu150, wu1800) 12.53/5.06 new_esEs(wu240, wu250, ty_Integer) -> new_esEs4(wu240, wu250) 12.53/5.06 new_esEs(wu240, wu250, app(app(ty_@2, cb), cc)) -> new_esEs0(wu240, wu250, cb, cc) 12.53/5.06 new_esEs(wu240, wu250, app(ty_Ratio, bh)) -> new_esEs7(wu240, wu250, bh) 12.53/5.06 new_esEs9(wu15, wu180) -> error([]) 12.53/5.06 new_esEs(wu240, wu250, ty_@0) -> new_esEs11(wu240, wu250) 12.53/5.06 new_esEs4(wu15, wu180) -> error([]) 12.53/5.06 new_esEs10(wu15, wu180, dc) -> error([]) 12.53/5.06 new_primEqNat0(Succ(wu1500), Zero) -> False 12.53/5.06 new_primEqNat0(Zero, Succ(wu18000)) -> False 12.53/5.06 new_esEs2(wu15, wu180) -> error([]) 12.53/5.06 new_primEqNat0(Succ(wu1500), Succ(wu18000)) -> new_primEqNat0(wu1500, wu18000) 12.53/5.06 new_esEs(wu240, wu250, app(app(app(ty_@3, ce), cf), cg)) -> new_esEs12(wu240, wu250, ce, cf, cg) 12.53/5.06 new_esEs(wu240, wu250, ty_Char) -> new_esEs13(wu240, wu250) 12.53/5.06 new_esEs(wu240, wu250, ty_Double) -> new_esEs6(wu240, wu250) 12.53/5.06 new_esEs(wu240, wu250, app(ty_[], ca)) -> new_esEs10(wu240, wu250, ca) 12.53/5.06 new_esEs12(wu15, wu180, dd, de, df) -> error([]) 12.53/5.06 new_esEs3(wu15, wu180, bd) -> error([]) 12.53/5.06 new_esEs6(wu15, wu180) -> error([]) 12.53/5.06 new_esEs(wu240, wu250, app(app(ty_Either, da), db)) -> new_esEs5(wu240, wu250, da, db) 12.53/5.06 new_esEs8(wu15, wu180) -> error([]) 12.53/5.06 new_esEs(wu240, wu250, ty_Int) -> new_esEs9(wu240, wu250) 12.53/5.06 new_esEs7(wu15, wu180, bg) -> error([]) 12.53/5.06 new_esEs(wu240, wu250, ty_Ordering) -> new_esEs1(wu240, wu250) 12.53/5.06 12.53/5.06 The set Q consists of the following terms: 12.53/5.06 12.53/5.06 new_primEqNat0(Zero, Zero) 12.53/5.06 new_esEs10(x0, x1, x2) 12.53/5.06 new_esEs(x0, x1, ty_Double) 12.53/5.06 new_esEs(x0, x1, ty_Float) 12.53/5.06 new_esEs0(x0, x1, x2, x3) 12.53/5.06 new_esEs(x0, x1, ty_Char) 12.53/5.06 new_esEs(x0, x1, app(ty_[], x2)) 12.53/5.06 new_esEs(x0, x1, ty_Int) 12.53/5.06 new_esEs(x0, x1, app(ty_Ratio, x2)) 12.53/5.06 new_esEs9(x0, x1) 12.53/5.06 new_esEs12(x0, x1, x2, x3, x4) 12.53/5.06 new_esEs(x0, x1, app(app(ty_Either, x2), x3)) 12.53/5.06 new_esEs1(x0, x1) 12.53/5.06 new_esEs4(x0, x1) 12.53/5.06 new_primEqNat0(Succ(x0), Zero) 12.53/5.06 new_esEs(x0, x1, ty_Bool) 12.53/5.06 new_esEs(x0, x1, app(app(ty_@2, x2), x3)) 12.53/5.06 new_esEs2(x0, x1) 12.53/5.06 new_esEs(x0, x1, ty_Integer) 12.53/5.06 new_esEs(x0, x1, app(ty_Maybe, x2)) 12.53/5.06 new_primEqNat0(Zero, Succ(x0)) 12.53/5.06 new_esEs3(x0, x1, x2) 12.53/5.06 new_esEs8(x0, x1) 12.53/5.06 new_esEs5(x0, x1, x2, x3) 12.53/5.06 new_esEs(x0, x1, ty_@0) 12.53/5.06 new_esEs7(x0, x1, x2) 12.53/5.06 new_primEqNat0(Succ(x0), Succ(x1)) 12.53/5.06 new_esEs(x0, x1, app(app(app(ty_@3, x2), x3), x4)) 12.53/5.06 new_esEs6(x0, x1) 12.53/5.06 new_esEs11(x0, x1) 12.53/5.06 new_esEs(x0, x1, ty_Ordering) 12.53/5.06 new_esEs13(Char(x0), Char(x1)) 12.53/5.06 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (8) QDPSizeChangeProof (EQUIVALENT) 12.53/5.06 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.53/5.06 12.53/5.06 From the DPs we obtained the following set of size-change graphs: 12.53/5.06 *new_asAs(True, :(wu240, wu241), :(wu250, wu251), ba) -> new_asAs(new_esEs(wu240, wu250, ba), wu241, wu251, ba) 12.53/5.06 The graph contains the following edges 2 > 2, 3 > 3, 4 >= 4 12.53/5.06 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (9) 12.53/5.06 YES 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (10) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_isPrefixOf(wu15, wu14, wu18, :(wu1710, wu1711), ba) -> new_isPrefixOf(wu15, wu14, new_flip(wu18, wu1710, ba), wu1711, ba) 12.53/5.06 12.53/5.06 The TRS R consists of the following rules: 12.53/5.06 12.53/5.06 new_flip(wu14, wu15, ba) -> :(wu15, wu14) 12.53/5.06 12.53/5.06 The set Q consists of the following terms: 12.53/5.06 12.53/5.06 new_flip(x0, x1, x2) 12.53/5.06 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (11) TransformationProof (EQUIVALENT) 12.53/5.06 By rewriting [LPAR04] the rule new_isPrefixOf(wu15, wu14, wu18, :(wu1710, wu1711), ba) -> new_isPrefixOf(wu15, wu14, new_flip(wu18, wu1710, ba), wu1711, ba) at position [2] we obtained the following new rules [LPAR04]: 12.53/5.06 12.53/5.06 (new_isPrefixOf(wu15, wu14, wu18, :(wu1710, wu1711), ba) -> new_isPrefixOf(wu15, wu14, :(wu1710, wu18), wu1711, ba),new_isPrefixOf(wu15, wu14, wu18, :(wu1710, wu1711), ba) -> new_isPrefixOf(wu15, wu14, :(wu1710, wu18), wu1711, ba)) 12.53/5.06 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (12) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_isPrefixOf(wu15, wu14, wu18, :(wu1710, wu1711), ba) -> new_isPrefixOf(wu15, wu14, :(wu1710, wu18), wu1711, ba) 12.53/5.06 12.53/5.06 The TRS R consists of the following rules: 12.53/5.06 12.53/5.06 new_flip(wu14, wu15, ba) -> :(wu15, wu14) 12.53/5.06 12.53/5.06 The set Q consists of the following terms: 12.53/5.06 12.53/5.06 new_flip(x0, x1, x2) 12.53/5.06 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (13) UsableRulesProof (EQUIVALENT) 12.53/5.06 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.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (14) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_isPrefixOf(wu15, wu14, wu18, :(wu1710, wu1711), ba) -> new_isPrefixOf(wu15, wu14, :(wu1710, wu18), wu1711, ba) 12.53/5.06 12.53/5.06 R is empty. 12.53/5.06 The set Q consists of the following terms: 12.53/5.06 12.53/5.06 new_flip(x0, x1, x2) 12.53/5.06 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (15) QReductionProof (EQUIVALENT) 12.53/5.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 12.53/5.06 12.53/5.06 new_flip(x0, x1, x2) 12.53/5.06 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (16) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_isPrefixOf(wu15, wu14, wu18, :(wu1710, wu1711), ba) -> new_isPrefixOf(wu15, wu14, :(wu1710, wu18), wu1711, ba) 12.53/5.06 12.53/5.06 R is empty. 12.53/5.06 Q is empty. 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (17) QDPSizeChangeProof (EQUIVALENT) 12.53/5.06 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.53/5.06 12.53/5.06 From the DPs we obtained the following set of size-change graphs: 12.53/5.06 *new_isPrefixOf(wu15, wu14, wu18, :(wu1710, wu1711), ba) -> new_isPrefixOf(wu15, wu14, :(wu1710, wu18), wu1711, ba) 12.53/5.06 The graph contains the following edges 1 >= 1, 2 >= 2, 4 > 4, 5 >= 5 12.53/5.06 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (18) 12.53/5.06 YES 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (19) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_primEqNat(Succ(wu1500), Succ(wu18000)) -> new_primEqNat(wu1500, wu18000) 12.53/5.06 12.53/5.06 R is empty. 12.53/5.06 Q is empty. 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (20) QDPSizeChangeProof (EQUIVALENT) 12.53/5.06 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.53/5.06 12.53/5.06 From the DPs we obtained the following set of size-change graphs: 12.53/5.06 *new_primEqNat(Succ(wu1500), Succ(wu18000)) -> new_primEqNat(wu1500, wu18000) 12.53/5.06 The graph contains the following edges 1 > 1, 2 > 2 12.53/5.06 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (21) 12.53/5.06 YES 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (22) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_isPrefixOf0(wu14, wu15, :(wu160, wu161), wu17, ba) -> new_isPrefixOf0(new_flip(wu14, wu15, ba), wu160, wu161, wu17, ba) 12.53/5.06 12.53/5.06 The TRS R consists of the following rules: 12.53/5.06 12.53/5.06 new_flip(wu14, wu15, ba) -> :(wu15, wu14) 12.53/5.06 12.53/5.06 The set Q consists of the following terms: 12.53/5.06 12.53/5.06 new_flip(x0, x1, x2) 12.53/5.06 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (23) TransformationProof (EQUIVALENT) 12.53/5.06 By rewriting [LPAR04] the rule new_isPrefixOf0(wu14, wu15, :(wu160, wu161), wu17, ba) -> new_isPrefixOf0(new_flip(wu14, wu15, ba), wu160, wu161, wu17, ba) at position [0] we obtained the following new rules [LPAR04]: 12.53/5.06 12.53/5.06 (new_isPrefixOf0(wu14, wu15, :(wu160, wu161), wu17, ba) -> new_isPrefixOf0(:(wu15, wu14), wu160, wu161, wu17, ba),new_isPrefixOf0(wu14, wu15, :(wu160, wu161), wu17, ba) -> new_isPrefixOf0(:(wu15, wu14), wu160, wu161, wu17, ba)) 12.53/5.06 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (24) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_isPrefixOf0(wu14, wu15, :(wu160, wu161), wu17, ba) -> new_isPrefixOf0(:(wu15, wu14), wu160, wu161, wu17, ba) 12.53/5.06 12.53/5.06 The TRS R consists of the following rules: 12.53/5.06 12.53/5.06 new_flip(wu14, wu15, ba) -> :(wu15, wu14) 12.53/5.06 12.53/5.06 The set Q consists of the following terms: 12.53/5.06 12.53/5.06 new_flip(x0, x1, x2) 12.53/5.06 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (25) UsableRulesProof (EQUIVALENT) 12.53/5.06 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.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (26) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_isPrefixOf0(wu14, wu15, :(wu160, wu161), wu17, ba) -> new_isPrefixOf0(:(wu15, wu14), wu160, wu161, wu17, ba) 12.53/5.06 12.53/5.06 R is empty. 12.53/5.06 The set Q consists of the following terms: 12.53/5.06 12.53/5.06 new_flip(x0, x1, x2) 12.53/5.06 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (27) QReductionProof (EQUIVALENT) 12.53/5.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 12.53/5.06 12.53/5.06 new_flip(x0, x1, x2) 12.53/5.06 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (28) 12.53/5.06 Obligation: 12.53/5.06 Q DP problem: 12.53/5.06 The TRS P consists of the following rules: 12.53/5.06 12.53/5.06 new_isPrefixOf0(wu14, wu15, :(wu160, wu161), wu17, ba) -> new_isPrefixOf0(:(wu15, wu14), wu160, wu161, wu17, ba) 12.53/5.06 12.53/5.06 R is empty. 12.53/5.06 Q is empty. 12.53/5.06 We have to consider all minimal (P,Q,R)-chains. 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (29) QDPSizeChangeProof (EQUIVALENT) 12.53/5.06 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.53/5.06 12.53/5.06 From the DPs we obtained the following set of size-change graphs: 12.53/5.06 *new_isPrefixOf0(wu14, wu15, :(wu160, wu161), wu17, ba) -> new_isPrefixOf0(:(wu15, wu14), wu160, wu161, wu17, ba) 12.53/5.06 The graph contains the following edges 3 > 2, 3 > 3, 4 >= 4, 5 >= 5 12.53/5.06 12.53/5.06 12.53/5.06 ---------------------------------------- 12.53/5.06 12.53/5.06 (30) 12.53/5.06 YES 12.72/5.11 EOF