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