/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.hs /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.hs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty H-Termination with start terms of the given HASKELL could be proven: (0) HASKELL (1) BR [EQUIVALENT, 0 ms] (2) HASKELL (3) COR [EQUIVALENT, 19 ms] (4) HASKELL (5) Narrow [SOUND, 0 ms] (6) AND (7) QDP (8) TransformationProof [EQUIVALENT, 0 ms] (9) QDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) QDP (12) QReductionProof [EQUIVALENT, 0 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] (15) YES (16) QDP (17) TransformationProof [EQUIVALENT, 0 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) QReductionProof [EQUIVALENT, 0 ms] (24) QDP (25) TransformationProof [EQUIVALENT, 0 ms] (26) QDP (27) DependencyGraphProof [EQUIVALENT, 0 ms] (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] (34) YES (35) QDP (36) TransformationProof [EQUIVALENT, 0 ms] (37) QDP (38) UsableRulesProof [EQUIVALENT, 0 ms] (39) QDP (40) QReductionProof [EQUIVALENT, 0 ms] (41) QDP (42) QDPSizeChangeProof [EQUIVALENT, 0 ms] (43) YES ---------------------------------------- (0) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; isPrefixOf :: Eq a => [a] -> [a] -> Bool; isPrefixOf [] _ = True; isPrefixOf _ [] = False; isPrefixOf (x : xs) (y : ys) = x == y && isPrefixOf xs ys; isSuffixOf :: Eq a => [a] -> [a] -> Bool; isSuffixOf x y = reverse x `isPrefixOf` reverse y; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (1) BR (EQUIVALENT) Replaced joker patterns by fresh variables and removed binding patterns. ---------------------------------------- (2) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; isPrefixOf :: Eq a => [a] -> [a] -> Bool; isPrefixOf [] vy = True; isPrefixOf vz [] = False; isPrefixOf (x : xs) (y : ys) = x == y && isPrefixOf xs ys; isSuffixOf :: Eq a => [a] -> [a] -> Bool; isSuffixOf x y = reverse x `isPrefixOf` reverse y; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (3) COR (EQUIVALENT) Cond Reductions: The following Function with conditions "undefined |Falseundefined; " is transformed to "undefined = undefined1; " "undefined0 True = undefined; " "undefined1 = undefined0 False; " ---------------------------------------- (4) Obligation: mainModule Main module Maybe where { import qualified List; import qualified Main; import qualified Prelude; } module List where { import qualified Main; import qualified Maybe; import qualified Prelude; isPrefixOf :: Eq a => [a] -> [a] -> Bool; isPrefixOf [] vy = True; isPrefixOf vz [] = False; isPrefixOf (x : xs) (y : ys) = x == y && isPrefixOf xs ys; isSuffixOf :: Eq a => [a] -> [a] -> Bool; isSuffixOf x y = reverse x `isPrefixOf` reverse y; } module Main where { import qualified List; import qualified Maybe; import qualified Prelude; } ---------------------------------------- (5) Narrow (SOUND) Haskell To QDPs digraph dp_graph { node [outthreshold=100, inthreshold=100];1[label="List.isSuffixOf",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 3[label="List.isSuffixOf wu3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 4[label="List.isSuffixOf wu3 wu4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 5[label="List.isPrefixOf (reverse wu3) (reverse wu4)",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3]; 6[label="List.isPrefixOf (foldl (flip (:)) [] wu3) (reverse wu4)",fontsize=16,color="burlywood",shape="box"];441[label="wu3/wu30 : wu31",fontsize=10,color="white",style="solid",shape="box"];6 -> 441[label="",style="solid", color="burlywood", weight=9]; 441 -> 7[label="",style="solid", color="burlywood", weight=3]; 442[label="wu3/[]",fontsize=10,color="white",style="solid",shape="box"];6 -> 442[label="",style="solid", color="burlywood", weight=9]; 442 -> 8[label="",style="solid", color="burlywood", weight=3]; 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]; 8[label="List.isPrefixOf (foldl (flip (:)) [] []) (reverse wu4)",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3]; 9 -> 277[label="",style="dashed", color="red", weight=0]; 9[label="List.isPrefixOf (foldl (flip (:)) (flip (:) [] wu30) wu31) (reverse wu4)",fontsize=16,color="magenta"];9 -> 278[label="",style="dashed", color="magenta", weight=3]; 9 -> 279[label="",style="dashed", color="magenta", weight=3]; 9 -> 280[label="",style="dashed", color="magenta", weight=3]; 9 -> 281[label="",style="dashed", color="magenta", weight=3]; 10[label="List.isPrefixOf [] (reverse wu4)",fontsize=16,color="black",shape="box"];10 -> 13[label="",style="solid", color="black", weight=3]; 278[label="[]",fontsize=16,color="green",shape="box"];279[label="wu30",fontsize=16,color="green",shape="box"];280[label="wu31",fontsize=16,color="green",shape="box"];281[label="wu4",fontsize=16,color="green",shape="box"];277[label="List.isPrefixOf (foldl (flip (:)) (flip (:) wu16 wu17) wu18) (reverse wu19)",fontsize=16,color="burlywood",shape="triangle"];443[label="wu18/wu180 : wu181",fontsize=10,color="white",style="solid",shape="box"];277 -> 443[label="",style="solid", color="burlywood", weight=9]; 443 -> 314[label="",style="solid", color="burlywood", weight=3]; 444[label="wu18/[]",fontsize=10,color="white",style="solid",shape="box"];277 -> 444[label="",style="solid", color="burlywood", weight=9]; 444 -> 315[label="",style="solid", color="burlywood", weight=3]; 13[label="True",fontsize=16,color="green",shape="box"];314[label="List.isPrefixOf (foldl (flip (:)) (flip (:) wu16 wu17) (wu180 : wu181)) (reverse wu19)",fontsize=16,color="black",shape="box"];314 -> 316[label="",style="solid", color="black", weight=3]; 315[label="List.isPrefixOf (foldl (flip (:)) (flip (:) wu16 wu17) []) (reverse wu19)",fontsize=16,color="black",shape="box"];315 -> 317[label="",style="solid", color="black", weight=3]; 316 -> 277[label="",style="dashed", color="red", weight=0]; 316[label="List.isPrefixOf (foldl (flip (:)) (flip (:) (flip (:) wu16 wu17) wu180) wu181) (reverse wu19)",fontsize=16,color="magenta"];316 -> 318[label="",style="dashed", color="magenta", weight=3]; 316 -> 319[label="",style="dashed", color="magenta", weight=3]; 316 -> 320[label="",style="dashed", color="magenta", weight=3]; 317[label="List.isPrefixOf (flip (:) wu16 wu17) (reverse wu19)",fontsize=16,color="black",shape="box"];317 -> 321[label="",style="solid", color="black", weight=3]; 318[label="flip (:) wu16 wu17",fontsize=16,color="black",shape="triangle"];318 -> 322[label="",style="solid", color="black", weight=3]; 319[label="wu180",fontsize=16,color="green",shape="box"];320[label="wu181",fontsize=16,color="green",shape="box"];321[label="List.isPrefixOf ((:) wu17 wu16) (reverse wu19)",fontsize=16,color="black",shape="box"];321 -> 323[label="",style="solid", color="black", weight=3]; 322[label="(:) wu17 wu16",fontsize=16,color="green",shape="box"];323 -> 328[label="",style="dashed", color="red", weight=0]; 323[label="List.isPrefixOf ((:) wu17 wu16) (foldl (flip (:)) [] wu19)",fontsize=16,color="magenta"];323 -> 329[label="",style="dashed", color="magenta", weight=3]; 323 -> 330[label="",style="dashed", color="magenta", weight=3]; 329[label="wu19",fontsize=16,color="green",shape="box"];330[label="[]",fontsize=16,color="green",shape="box"];328[label="List.isPrefixOf ((:) wu17 wu16) (foldl (flip (:)) wu20 wu191)",fontsize=16,color="burlywood",shape="triangle"];445[label="wu191/wu1910 : wu1911",fontsize=10,color="white",style="solid",shape="box"];328 -> 445[label="",style="solid", color="burlywood", weight=9]; 445 -> 332[label="",style="solid", color="burlywood", weight=3]; 446[label="wu191/[]",fontsize=10,color="white",style="solid",shape="box"];328 -> 446[label="",style="solid", color="burlywood", weight=9]; 446 -> 333[label="",style="solid", color="burlywood", weight=3]; 332[label="List.isPrefixOf ((:) wu17 wu16) (foldl (flip (:)) wu20 (wu1910 : wu1911))",fontsize=16,color="black",shape="box"];332 -> 334[label="",style="solid", color="black", weight=3]; 333[label="List.isPrefixOf ((:) wu17 wu16) (foldl (flip (:)) wu20 [])",fontsize=16,color="black",shape="box"];333 -> 335[label="",style="solid", color="black", weight=3]; 334 -> 328[label="",style="dashed", color="red", weight=0]; 334[label="List.isPrefixOf ((:) wu17 wu16) (foldl (flip (:)) (flip (:) wu20 wu1910) wu1911)",fontsize=16,color="magenta"];334 -> 336[label="",style="dashed", color="magenta", weight=3]; 334 -> 337[label="",style="dashed", color="magenta", weight=3]; 335[label="List.isPrefixOf ((:) wu17 wu16) wu20",fontsize=16,color="burlywood",shape="box"];447[label="wu20/wu200 : wu201",fontsize=10,color="white",style="solid",shape="box"];335 -> 447[label="",style="solid", color="burlywood", weight=9]; 447 -> 338[label="",style="solid", color="burlywood", weight=3]; 448[label="wu20/[]",fontsize=10,color="white",style="solid",shape="box"];335 -> 448[label="",style="solid", color="burlywood", weight=9]; 448 -> 339[label="",style="solid", color="burlywood", weight=3]; 336[label="wu1911",fontsize=16,color="green",shape="box"];337 -> 318[label="",style="dashed", color="red", weight=0]; 337[label="flip (:) wu20 wu1910",fontsize=16,color="magenta"];337 -> 340[label="",style="dashed", color="magenta", weight=3]; 337 -> 341[label="",style="dashed", color="magenta", weight=3]; 338[label="List.isPrefixOf ((:) wu17 wu16) (wu200 : wu201)",fontsize=16,color="black",shape="box"];338 -> 342[label="",style="solid", color="black", weight=3]; 339[label="List.isPrefixOf ((:) wu17 wu16) []",fontsize=16,color="black",shape="box"];339 -> 343[label="",style="solid", color="black", weight=3]; 340[label="wu20",fontsize=16,color="green",shape="box"];341[label="wu1910",fontsize=16,color="green",shape="box"];342 -> 344[label="",style="dashed", color="red", weight=0]; 342[label="wu17 == wu200 && List.isPrefixOf wu16 wu201",fontsize=16,color="magenta"];342 -> 345[label="",style="dashed", color="magenta", weight=3]; 342 -> 346[label="",style="dashed", color="magenta", weight=3]; 342 -> 347[label="",style="dashed", color="magenta", weight=3]; 343[label="False",fontsize=16,color="green",shape="box"];345[label="wu17 == wu200",fontsize=16,color="blue",shape="box"];449[label="== :: Bool -> Bool -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 449[label="",style="solid", color="blue", weight=9]; 449 -> 348[label="",style="solid", color="blue", weight=3]; 450[label="== :: ((@3) a b c) -> ((@3) a b c) -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 450[label="",style="solid", color="blue", weight=9]; 450 -> 349[label="",style="solid", color="blue", weight=3]; 451[label="== :: () -> () -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 451[label="",style="solid", color="blue", weight=9]; 451 -> 350[label="",style="solid", color="blue", weight=3]; 452[label="== :: (Maybe a) -> (Maybe a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 452[label="",style="solid", color="blue", weight=9]; 452 -> 351[label="",style="solid", color="blue", weight=3]; 453[label="== :: Integer -> Integer -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 453[label="",style="solid", color="blue", weight=9]; 453 -> 352[label="",style="solid", color="blue", weight=3]; 454[label="== :: ([] a) -> ([] a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 454[label="",style="solid", color="blue", weight=9]; 454 -> 353[label="",style="solid", color="blue", weight=3]; 455[label="== :: (Either a b) -> (Either a b) -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 455[label="",style="solid", color="blue", weight=9]; 455 -> 354[label="",style="solid", color="blue", weight=3]; 456[label="== :: Ordering -> Ordering -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 456[label="",style="solid", color="blue", weight=9]; 456 -> 355[label="",style="solid", color="blue", weight=3]; 457[label="== :: Float -> Float -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 457[label="",style="solid", color="blue", weight=9]; 457 -> 356[label="",style="solid", color="blue", weight=3]; 458[label="== :: ((@2) a b) -> ((@2) a b) -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 458[label="",style="solid", color="blue", weight=9]; 458 -> 357[label="",style="solid", color="blue", weight=3]; 459[label="== :: Int -> Int -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 459[label="",style="solid", color="blue", weight=9]; 459 -> 358[label="",style="solid", color="blue", weight=3]; 460[label="== :: (Ratio a) -> (Ratio a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 460[label="",style="solid", color="blue", weight=9]; 460 -> 359[label="",style="solid", color="blue", weight=3]; 461[label="== :: Double -> Double -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 461[label="",style="solid", color="blue", weight=9]; 461 -> 360[label="",style="solid", color="blue", weight=3]; 462[label="== :: Char -> Char -> Bool",fontsize=10,color="white",style="solid",shape="box"];345 -> 462[label="",style="solid", color="blue", weight=9]; 462 -> 361[label="",style="solid", color="blue", weight=3]; 346[label="wu201",fontsize=16,color="green",shape="box"];347[label="wu16",fontsize=16,color="green",shape="box"];344[label="wu25 && List.isPrefixOf wu26 wu27",fontsize=16,color="burlywood",shape="triangle"];463[label="wu25/False",fontsize=10,color="white",style="solid",shape="box"];344 -> 463[label="",style="solid", color="burlywood", weight=9]; 463 -> 362[label="",style="solid", color="burlywood", weight=3]; 464[label="wu25/True",fontsize=10,color="white",style="solid",shape="box"];344 -> 464[label="",style="solid", color="burlywood", weight=9]; 464 -> 363[label="",style="solid", color="burlywood", weight=3]; 348[label="wu17 == wu200",fontsize=16,color="burlywood",shape="triangle"];465[label="wu17/False",fontsize=10,color="white",style="solid",shape="box"];348 -> 465[label="",style="solid", color="burlywood", weight=9]; 465 -> 364[label="",style="solid", color="burlywood", weight=3]; 466[label="wu17/True",fontsize=10,color="white",style="solid",shape="box"];348 -> 466[label="",style="solid", color="burlywood", weight=9]; 466 -> 365[label="",style="solid", color="burlywood", weight=3]; 349[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];349 -> 366[label="",style="solid", color="black", weight=3]; 350[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];350 -> 367[label="",style="solid", color="black", weight=3]; 351[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];351 -> 368[label="",style="solid", color="black", weight=3]; 352[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];352 -> 369[label="",style="solid", color="black", weight=3]; 353[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];353 -> 370[label="",style="solid", color="black", weight=3]; 354[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];354 -> 371[label="",style="solid", color="black", weight=3]; 355[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];355 -> 372[label="",style="solid", color="black", weight=3]; 356[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];356 -> 373[label="",style="solid", color="black", weight=3]; 357[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];357 -> 374[label="",style="solid", color="black", weight=3]; 358[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];358 -> 375[label="",style="solid", color="black", weight=3]; 359[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];359 -> 376[label="",style="solid", color="black", weight=3]; 360[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];360 -> 377[label="",style="solid", color="black", weight=3]; 361[label="wu17 == wu200",fontsize=16,color="black",shape="triangle"];361 -> 378[label="",style="solid", color="black", weight=3]; 362[label="False && List.isPrefixOf wu26 wu27",fontsize=16,color="black",shape="box"];362 -> 379[label="",style="solid", color="black", weight=3]; 363[label="True && List.isPrefixOf wu26 wu27",fontsize=16,color="black",shape="box"];363 -> 380[label="",style="solid", color="black", weight=3]; 364[label="False == wu200",fontsize=16,color="burlywood",shape="box"];467[label="wu200/False",fontsize=10,color="white",style="solid",shape="box"];364 -> 467[label="",style="solid", color="burlywood", weight=9]; 467 -> 381[label="",style="solid", color="burlywood", weight=3]; 468[label="wu200/True",fontsize=10,color="white",style="solid",shape="box"];364 -> 468[label="",style="solid", color="burlywood", weight=9]; 468 -> 382[label="",style="solid", color="burlywood", weight=3]; 365[label="True == wu200",fontsize=16,color="burlywood",shape="box"];469[label="wu200/False",fontsize=10,color="white",style="solid",shape="box"];365 -> 469[label="",style="solid", color="burlywood", weight=9]; 469 -> 383[label="",style="solid", color="burlywood", weight=3]; 470[label="wu200/True",fontsize=10,color="white",style="solid",shape="box"];365 -> 470[label="",style="solid", color="burlywood", weight=9]; 470 -> 384[label="",style="solid", color="burlywood", weight=3]; 366[label="error []",fontsize=16,color="red",shape="box"];367[label="error []",fontsize=16,color="red",shape="box"];368[label="error []",fontsize=16,color="red",shape="box"];369[label="error []",fontsize=16,color="red",shape="box"];370[label="error []",fontsize=16,color="red",shape="box"];371[label="error []",fontsize=16,color="red",shape="box"];372[label="error []",fontsize=16,color="red",shape="box"];373[label="error []",fontsize=16,color="red",shape="box"];374[label="error []",fontsize=16,color="red",shape="box"];375[label="error []",fontsize=16,color="red",shape="box"];376[label="error []",fontsize=16,color="red",shape="box"];377[label="error []",fontsize=16,color="red",shape="box"];378[label="error []",fontsize=16,color="red",shape="box"];379[label="False",fontsize=16,color="green",shape="box"];380[label="List.isPrefixOf wu26 wu27",fontsize=16,color="burlywood",shape="box"];471[label="wu26/wu260 : wu261",fontsize=10,color="white",style="solid",shape="box"];380 -> 471[label="",style="solid", color="burlywood", weight=9]; 471 -> 385[label="",style="solid", color="burlywood", weight=3]; 472[label="wu26/[]",fontsize=10,color="white",style="solid",shape="box"];380 -> 472[label="",style="solid", color="burlywood", weight=9]; 472 -> 386[label="",style="solid", color="burlywood", weight=3]; 381[label="False == False",fontsize=16,color="black",shape="box"];381 -> 387[label="",style="solid", color="black", weight=3]; 382[label="False == True",fontsize=16,color="black",shape="box"];382 -> 388[label="",style="solid", color="black", weight=3]; 383[label="True == False",fontsize=16,color="black",shape="box"];383 -> 389[label="",style="solid", color="black", weight=3]; 384[label="True == True",fontsize=16,color="black",shape="box"];384 -> 390[label="",style="solid", color="black", weight=3]; 385[label="List.isPrefixOf (wu260 : wu261) wu27",fontsize=16,color="burlywood",shape="box"];473[label="wu27/wu270 : wu271",fontsize=10,color="white",style="solid",shape="box"];385 -> 473[label="",style="solid", color="burlywood", weight=9]; 473 -> 391[label="",style="solid", color="burlywood", weight=3]; 474[label="wu27/[]",fontsize=10,color="white",style="solid",shape="box"];385 -> 474[label="",style="solid", color="burlywood", weight=9]; 474 -> 392[label="",style="solid", color="burlywood", weight=3]; 386[label="List.isPrefixOf [] wu27",fontsize=16,color="black",shape="box"];386 -> 393[label="",style="solid", color="black", weight=3]; 387[label="True",fontsize=16,color="green",shape="box"];388[label="False",fontsize=16,color="green",shape="box"];389[label="False",fontsize=16,color="green",shape="box"];390[label="True",fontsize=16,color="green",shape="box"];391[label="List.isPrefixOf (wu260 : wu261) (wu270 : wu271)",fontsize=16,color="black",shape="box"];391 -> 394[label="",style="solid", color="black", weight=3]; 392[label="List.isPrefixOf (wu260 : wu261) []",fontsize=16,color="black",shape="box"];392 -> 395[label="",style="solid", color="black", weight=3]; 393[label="True",fontsize=16,color="green",shape="box"];394 -> 344[label="",style="dashed", color="red", weight=0]; 394[label="wu260 == wu270 && List.isPrefixOf wu261 wu271",fontsize=16,color="magenta"];394 -> 396[label="",style="dashed", color="magenta", weight=3]; 394 -> 397[label="",style="dashed", color="magenta", weight=3]; 394 -> 398[label="",style="dashed", color="magenta", weight=3]; 395[label="False",fontsize=16,color="green",shape="box"];396[label="wu260 == wu270",fontsize=16,color="blue",shape="box"];475[label="== :: Bool -> Bool -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 475[label="",style="solid", color="blue", weight=9]; 475 -> 399[label="",style="solid", color="blue", weight=3]; 476[label="== :: ((@3) a b c) -> ((@3) a b c) -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 476[label="",style="solid", color="blue", weight=9]; 476 -> 400[label="",style="solid", color="blue", weight=3]; 477[label="== :: () -> () -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 477[label="",style="solid", color="blue", weight=9]; 477 -> 401[label="",style="solid", color="blue", weight=3]; 478[label="== :: (Maybe a) -> (Maybe a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 478[label="",style="solid", color="blue", weight=9]; 478 -> 402[label="",style="solid", color="blue", weight=3]; 479[label="== :: Integer -> Integer -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 479[label="",style="solid", color="blue", weight=9]; 479 -> 403[label="",style="solid", color="blue", weight=3]; 480[label="== :: ([] a) -> ([] a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 480[label="",style="solid", color="blue", weight=9]; 480 -> 404[label="",style="solid", color="blue", weight=3]; 481[label="== :: (Either a b) -> (Either a b) -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 481[label="",style="solid", color="blue", weight=9]; 481 -> 405[label="",style="solid", color="blue", weight=3]; 482[label="== :: Ordering -> Ordering -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 482[label="",style="solid", color="blue", weight=9]; 482 -> 406[label="",style="solid", color="blue", weight=3]; 483[label="== :: Float -> Float -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 483[label="",style="solid", color="blue", weight=9]; 483 -> 407[label="",style="solid", color="blue", weight=3]; 484[label="== :: ((@2) a b) -> ((@2) a b) -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 484[label="",style="solid", color="blue", weight=9]; 484 -> 408[label="",style="solid", color="blue", weight=3]; 485[label="== :: Int -> Int -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 485[label="",style="solid", color="blue", weight=9]; 485 -> 409[label="",style="solid", color="blue", weight=3]; 486[label="== :: (Ratio a) -> (Ratio a) -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 486[label="",style="solid", color="blue", weight=9]; 486 -> 410[label="",style="solid", color="blue", weight=3]; 487[label="== :: Double -> Double -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 487[label="",style="solid", color="blue", weight=9]; 487 -> 411[label="",style="solid", color="blue", weight=3]; 488[label="== :: Char -> Char -> Bool",fontsize=10,color="white",style="solid",shape="box"];396 -> 488[label="",style="solid", color="blue", weight=9]; 488 -> 412[label="",style="solid", color="blue", weight=3]; 397[label="wu271",fontsize=16,color="green",shape="box"];398[label="wu261",fontsize=16,color="green",shape="box"];399 -> 348[label="",style="dashed", color="red", weight=0]; 399[label="wu260 == wu270",fontsize=16,color="magenta"];399 -> 413[label="",style="dashed", color="magenta", weight=3]; 399 -> 414[label="",style="dashed", color="magenta", weight=3]; 400 -> 349[label="",style="dashed", color="red", weight=0]; 400[label="wu260 == wu270",fontsize=16,color="magenta"];400 -> 415[label="",style="dashed", color="magenta", weight=3]; 400 -> 416[label="",style="dashed", color="magenta", weight=3]; 401 -> 350[label="",style="dashed", color="red", weight=0]; 401[label="wu260 == wu270",fontsize=16,color="magenta"];401 -> 417[label="",style="dashed", color="magenta", weight=3]; 401 -> 418[label="",style="dashed", color="magenta", weight=3]; 402 -> 351[label="",style="dashed", color="red", weight=0]; 402[label="wu260 == wu270",fontsize=16,color="magenta"];402 -> 419[label="",style="dashed", color="magenta", weight=3]; 402 -> 420[label="",style="dashed", color="magenta", weight=3]; 403 -> 352[label="",style="dashed", color="red", weight=0]; 403[label="wu260 == wu270",fontsize=16,color="magenta"];403 -> 421[label="",style="dashed", color="magenta", weight=3]; 403 -> 422[label="",style="dashed", color="magenta", weight=3]; 404 -> 353[label="",style="dashed", color="red", weight=0]; 404[label="wu260 == wu270",fontsize=16,color="magenta"];404 -> 423[label="",style="dashed", color="magenta", weight=3]; 404 -> 424[label="",style="dashed", color="magenta", weight=3]; 405 -> 354[label="",style="dashed", color="red", weight=0]; 405[label="wu260 == wu270",fontsize=16,color="magenta"];405 -> 425[label="",style="dashed", color="magenta", weight=3]; 405 -> 426[label="",style="dashed", color="magenta", weight=3]; 406 -> 355[label="",style="dashed", color="red", weight=0]; 406[label="wu260 == wu270",fontsize=16,color="magenta"];406 -> 427[label="",style="dashed", color="magenta", weight=3]; 406 -> 428[label="",style="dashed", color="magenta", weight=3]; 407 -> 356[label="",style="dashed", color="red", weight=0]; 407[label="wu260 == wu270",fontsize=16,color="magenta"];407 -> 429[label="",style="dashed", color="magenta", weight=3]; 407 -> 430[label="",style="dashed", color="magenta", weight=3]; 408 -> 357[label="",style="dashed", color="red", weight=0]; 408[label="wu260 == wu270",fontsize=16,color="magenta"];408 -> 431[label="",style="dashed", color="magenta", weight=3]; 408 -> 432[label="",style="dashed", color="magenta", weight=3]; 409 -> 358[label="",style="dashed", color="red", weight=0]; 409[label="wu260 == wu270",fontsize=16,color="magenta"];409 -> 433[label="",style="dashed", color="magenta", weight=3]; 409 -> 434[label="",style="dashed", color="magenta", weight=3]; 410 -> 359[label="",style="dashed", color="red", weight=0]; 410[label="wu260 == wu270",fontsize=16,color="magenta"];410 -> 435[label="",style="dashed", color="magenta", weight=3]; 410 -> 436[label="",style="dashed", color="magenta", weight=3]; 411 -> 360[label="",style="dashed", color="red", weight=0]; 411[label="wu260 == wu270",fontsize=16,color="magenta"];411 -> 437[label="",style="dashed", color="magenta", weight=3]; 411 -> 438[label="",style="dashed", color="magenta", weight=3]; 412 -> 361[label="",style="dashed", color="red", weight=0]; 412[label="wu260 == wu270",fontsize=16,color="magenta"];412 -> 439[label="",style="dashed", color="magenta", weight=3]; 412 -> 440[label="",style="dashed", color="magenta", weight=3]; 413[label="wu260",fontsize=16,color="green",shape="box"];414[label="wu270",fontsize=16,color="green",shape="box"];415[label="wu260",fontsize=16,color="green",shape="box"];416[label="wu270",fontsize=16,color="green",shape="box"];417[label="wu260",fontsize=16,color="green",shape="box"];418[label="wu270",fontsize=16,color="green",shape="box"];419[label="wu260",fontsize=16,color="green",shape="box"];420[label="wu270",fontsize=16,color="green",shape="box"];421[label="wu260",fontsize=16,color="green",shape="box"];422[label="wu270",fontsize=16,color="green",shape="box"];423[label="wu260",fontsize=16,color="green",shape="box"];424[label="wu270",fontsize=16,color="green",shape="box"];425[label="wu260",fontsize=16,color="green",shape="box"];426[label="wu270",fontsize=16,color="green",shape="box"];427[label="wu260",fontsize=16,color="green",shape="box"];428[label="wu270",fontsize=16,color="green",shape="box"];429[label="wu260",fontsize=16,color="green",shape="box"];430[label="wu270",fontsize=16,color="green",shape="box"];431[label="wu260",fontsize=16,color="green",shape="box"];432[label="wu270",fontsize=16,color="green",shape="box"];433[label="wu260",fontsize=16,color="green",shape="box"];434[label="wu270",fontsize=16,color="green",shape="box"];435[label="wu260",fontsize=16,color="green",shape="box"];436[label="wu270",fontsize=16,color="green",shape="box"];437[label="wu260",fontsize=16,color="green",shape="box"];438[label="wu270",fontsize=16,color="green",shape="box"];439[label="wu260",fontsize=16,color="green",shape="box"];440[label="wu270",fontsize=16,color="green",shape="box"];} ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: new_isPrefixOf(wu17, wu16, wu20, :(wu1910, wu1911), ba) -> new_isPrefixOf(wu17, wu16, new_flip(wu20, wu1910, ba), wu1911, ba) The TRS R consists of the following rules: new_flip(wu16, wu17, ba) -> :(wu17, wu16) The set Q consists of the following terms: new_flip(x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule new_isPrefixOf(wu17, wu16, wu20, :(wu1910, wu1911), ba) -> new_isPrefixOf(wu17, wu16, new_flip(wu20, wu1910, ba), wu1911, ba) at position [2] we obtained the following new rules [LPAR04]: (new_isPrefixOf(wu17, wu16, wu20, :(wu1910, wu1911), ba) -> new_isPrefixOf(wu17, wu16, :(wu1910, wu20), wu1911, ba),new_isPrefixOf(wu17, wu16, wu20, :(wu1910, wu1911), ba) -> new_isPrefixOf(wu17, wu16, :(wu1910, wu20), wu1911, ba)) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: new_isPrefixOf(wu17, wu16, wu20, :(wu1910, wu1911), ba) -> new_isPrefixOf(wu17, wu16, :(wu1910, wu20), wu1911, ba) The TRS R consists of the following rules: new_flip(wu16, wu17, ba) -> :(wu17, wu16) The set Q consists of the following terms: new_flip(x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: new_isPrefixOf(wu17, wu16, wu20, :(wu1910, wu1911), ba) -> new_isPrefixOf(wu17, wu16, :(wu1910, wu20), wu1911, ba) R is empty. The set Q consists of the following terms: new_flip(x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. new_flip(x0, x1, x2) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: new_isPrefixOf(wu17, wu16, wu20, :(wu1910, wu1911), ba) -> new_isPrefixOf(wu17, wu16, :(wu1910, wu20), wu1911, ba) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *new_isPrefixOf(wu17, wu16, wu20, :(wu1910, wu1911), ba) -> new_isPrefixOf(wu17, wu16, :(wu1910, wu20), wu1911, ba) The graph contains the following edges 1 >= 1, 2 >= 2, 4 > 4, 5 >= 5 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: new_asAs(True, :(wu260, wu261), :(wu270, wu271), ba) -> new_asAs(new_esEs(wu260, wu270, ba), wu261, wu271, ba) The TRS R consists of the following rules: new_esEs(wu260, wu270, app(ty_Ratio, df)) -> new_esEs3(wu260, wu270, df) new_esEs10(wu17, wu200, bg, bh, ca) -> error([]) new_esEs(wu260, wu270, ty_@0) -> new_esEs2(wu260, wu270) new_esEs(wu260, wu270, ty_Integer) -> new_esEs7(wu260, wu270) new_esEs5(wu17, wu200) -> error([]) new_esEs13(wu17, wu200) -> error([]) new_esEs(wu260, wu270, ty_Float) -> new_esEs12(wu260, wu270) new_esEs(wu260, wu270, app(app(ty_@2, dd), de)) -> new_esEs11(wu260, wu270, dd, de) new_esEs7(wu17, wu200) -> error([]) new_esEs(wu260, wu270, ty_Bool) -> new_esEs1(wu260, wu270) new_esEs6(wu17, wu200, bd) -> error([]) new_esEs(wu260, wu270, app(ty_Maybe, cg)) -> new_esEs6(wu260, wu270, cg) new_esEs1(True, True) -> True new_esEs12(wu17, wu200) -> error([]) new_esEs0(wu17, wu200, bb) -> error([]) new_esEs1(False, False) -> True new_esEs4(wu17, wu200) -> error([]) new_esEs(wu260, wu270, app(app(ty_Either, db), dc)) -> new_esEs9(wu260, wu270, db, dc) new_esEs(wu260, wu270, app(app(app(ty_@3, cd), ce), cf)) -> new_esEs10(wu260, wu270, cd, ce, cf) new_esEs2(wu17, wu200) -> error([]) new_esEs(wu260, wu270, ty_Double) -> new_esEs8(wu260, wu270) new_esEs11(wu17, wu200, cb, cc) -> error([]) new_esEs(wu260, wu270, ty_Ordering) -> new_esEs5(wu260, wu270) new_esEs(wu260, wu270, ty_Char) -> new_esEs4(wu260, wu270) new_esEs3(wu17, wu200, bc) -> error([]) new_esEs1(False, True) -> False new_esEs1(True, False) -> False new_esEs8(wu17, wu200) -> error([]) new_esEs9(wu17, wu200, be, bf) -> error([]) new_esEs(wu260, wu270, app(ty_[], da)) -> new_esEs0(wu260, wu270, da) new_esEs(wu260, wu270, ty_Int) -> new_esEs13(wu260, wu270) The set Q consists of the following terms: new_esEs(x0, x1, ty_Int) new_esEs1(True, True) new_esEs1(False, True) new_esEs1(True, False) new_esEs(x0, x1, ty_Float) new_esEs4(x0, x1) new_esEs(x0, x1, ty_Integer) new_esEs10(x0, x1, x2, x3, x4) new_esEs(x0, x1, app(app(app(ty_@3, x2), x3), x4)) new_esEs8(x0, x1) new_esEs(x0, x1, app(app(ty_Either, x2), x3)) new_esEs7(x0, x1) new_esEs(x0, x1, app(app(ty_@2, x2), x3)) new_esEs(x0, x1, ty_Bool) new_esEs9(x0, x1, x2, x3) new_esEs12(x0, x1) new_esEs0(x0, x1, x2) new_esEs11(x0, x1, x2, x3) new_esEs(x0, x1, app(ty_Ratio, x2)) new_esEs2(x0, x1) new_esEs3(x0, x1, x2) new_esEs(x0, x1, ty_Char) new_esEs13(x0, x1) new_esEs(x0, x1, app(ty_Maybe, x2)) new_esEs(x0, x1, app(ty_[], x2)) new_esEs6(x0, x1, x2) new_esEs(x0, x1, ty_Ordering) new_esEs(x0, x1, ty_Double) new_esEs(x0, x1, ty_@0) new_esEs1(False, False) new_esEs5(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule new_asAs(True, :(wu260, wu261), :(wu270, wu271), ba) -> new_asAs(new_esEs(wu260, wu270, ba), wu261, wu271, ba) at position [0] we obtained the following new rules [LPAR04]: (new_asAs(True, :(x0, y1), :(x1, y3), app(ty_Ratio, x2)) -> new_asAs(new_esEs3(x0, x1, x2), y1, y3, app(ty_Ratio, x2)),new_asAs(True, :(x0, y1), :(x1, y3), app(ty_Ratio, x2)) -> new_asAs(new_esEs3(x0, x1, x2), y1, y3, app(ty_Ratio, x2))) (new_asAs(True, :(x0, y1), :(x1, y3), ty_@0) -> new_asAs(new_esEs2(x0, x1), y1, y3, ty_@0),new_asAs(True, :(x0, y1), :(x1, y3), ty_@0) -> new_asAs(new_esEs2(x0, x1), y1, y3, ty_@0)) (new_asAs(True, :(x0, y1), :(x1, y3), ty_Integer) -> new_asAs(new_esEs7(x0, x1), y1, y3, ty_Integer),new_asAs(True, :(x0, y1), :(x1, y3), ty_Integer) -> new_asAs(new_esEs7(x0, x1), y1, y3, ty_Integer)) (new_asAs(True, :(x0, y1), :(x1, y3), ty_Float) -> new_asAs(new_esEs12(x0, x1), y1, y3, ty_Float),new_asAs(True, :(x0, y1), :(x1, y3), ty_Float) -> new_asAs(new_esEs12(x0, x1), y1, y3, ty_Float)) (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))) (new_asAs(True, :(x0, y1), :(x1, y3), ty_Bool) -> new_asAs(new_esEs1(x0, x1), y1, y3, ty_Bool),new_asAs(True, :(x0, y1), :(x1, y3), ty_Bool) -> new_asAs(new_esEs1(x0, x1), y1, y3, ty_Bool)) (new_asAs(True, :(x0, y1), :(x1, y3), app(ty_Maybe, x2)) -> new_asAs(new_esEs6(x0, x1, x2), y1, y3, app(ty_Maybe, x2)),new_asAs(True, :(x0, y1), :(x1, y3), app(ty_Maybe, x2)) -> new_asAs(new_esEs6(x0, x1, x2), y1, y3, app(ty_Maybe, x2))) (new_asAs(True, :(x0, y1), :(x1, y3), app(app(ty_Either, x2), x3)) -> new_asAs(new_esEs9(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_esEs9(x0, x1, x2, x3), y1, y3, app(app(ty_Either, x2), x3))) (new_asAs(True, :(x0, y1), :(x1, y3), app(app(app(ty_@3, x2), x3), x4)) -> new_asAs(new_esEs10(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_esEs10(x0, x1, x2, x3, x4), y1, y3, app(app(app(ty_@3, x2), x3), x4))) (new_asAs(True, :(x0, y1), :(x1, y3), ty_Double) -> new_asAs(new_esEs8(x0, x1), y1, y3, ty_Double),new_asAs(True, :(x0, y1), :(x1, y3), ty_Double) -> new_asAs(new_esEs8(x0, x1), y1, y3, ty_Double)) (new_asAs(True, :(x0, y1), :(x1, y3), ty_Ordering) -> new_asAs(new_esEs5(x0, x1), y1, y3, ty_Ordering),new_asAs(True, :(x0, y1), :(x1, y3), ty_Ordering) -> new_asAs(new_esEs5(x0, x1), y1, y3, ty_Ordering)) (new_asAs(True, :(x0, y1), :(x1, y3), ty_Char) -> new_asAs(new_esEs4(x0, x1), y1, y3, ty_Char),new_asAs(True, :(x0, y1), :(x1, y3), ty_Char) -> new_asAs(new_esEs4(x0, x1), y1, y3, ty_Char)) (new_asAs(True, :(x0, y1), :(x1, y3), app(ty_[], x2)) -> new_asAs(new_esEs0(x0, x1, x2), y1, y3, app(ty_[], x2)),new_asAs(True, :(x0, y1), :(x1, y3), app(ty_[], x2)) -> new_asAs(new_esEs0(x0, x1, x2), y1, y3, app(ty_[], x2))) (new_asAs(True, :(x0, y1), :(x1, y3), ty_Int) -> new_asAs(new_esEs13(x0, x1), y1, y3, ty_Int),new_asAs(True, :(x0, y1), :(x1, y3), ty_Int) -> new_asAs(new_esEs13(x0, x1), y1, y3, ty_Int)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: new_asAs(True, :(x0, y1), :(x1, y3), app(ty_Ratio, x2)) -> new_asAs(new_esEs3(x0, x1, x2), y1, y3, app(ty_Ratio, x2)) new_asAs(True, :(x0, y1), :(x1, y3), ty_@0) -> new_asAs(new_esEs2(x0, x1), y1, y3, ty_@0) new_asAs(True, :(x0, y1), :(x1, y3), ty_Integer) -> new_asAs(new_esEs7(x0, x1), y1, y3, ty_Integer) new_asAs(True, :(x0, y1), :(x1, y3), ty_Float) -> new_asAs(new_esEs12(x0, x1), y1, y3, ty_Float) 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), ty_Bool) -> new_asAs(new_esEs1(x0, x1), y1, y3, ty_Bool) new_asAs(True, :(x0, y1), :(x1, y3), app(ty_Maybe, x2)) -> new_asAs(new_esEs6(x0, x1, x2), y1, y3, app(ty_Maybe, x2)) new_asAs(True, :(x0, y1), :(x1, y3), app(app(ty_Either, x2), x3)) -> new_asAs(new_esEs9(x0, x1, x2, x3), y1, y3, app(app(ty_Either, x2), x3)) new_asAs(True, :(x0, y1), :(x1, y3), app(app(app(ty_@3, x2), x3), x4)) -> new_asAs(new_esEs10(x0, x1, x2, x3, x4), y1, y3, app(app(app(ty_@3, x2), x3), x4)) new_asAs(True, :(x0, y1), :(x1, y3), ty_Double) -> new_asAs(new_esEs8(x0, x1), y1, y3, ty_Double) new_asAs(True, :(x0, y1), :(x1, y3), ty_Ordering) -> new_asAs(new_esEs5(x0, x1), y1, y3, ty_Ordering) new_asAs(True, :(x0, y1), :(x1, y3), ty_Char) -> new_asAs(new_esEs4(x0, x1), y1, y3, ty_Char) new_asAs(True, :(x0, y1), :(x1, y3), app(ty_[], x2)) -> new_asAs(new_esEs0(x0, x1, x2), y1, y3, app(ty_[], x2)) new_asAs(True, :(x0, y1), :(x1, y3), ty_Int) -> new_asAs(new_esEs13(x0, x1), y1, y3, ty_Int) The TRS R consists of the following rules: new_esEs(wu260, wu270, app(ty_Ratio, df)) -> new_esEs3(wu260, wu270, df) new_esEs10(wu17, wu200, bg, bh, ca) -> error([]) new_esEs(wu260, wu270, ty_@0) -> new_esEs2(wu260, wu270) new_esEs(wu260, wu270, ty_Integer) -> new_esEs7(wu260, wu270) new_esEs5(wu17, wu200) -> error([]) new_esEs13(wu17, wu200) -> error([]) new_esEs(wu260, wu270, ty_Float) -> new_esEs12(wu260, wu270) new_esEs(wu260, wu270, app(app(ty_@2, dd), de)) -> new_esEs11(wu260, wu270, dd, de) new_esEs7(wu17, wu200) -> error([]) new_esEs(wu260, wu270, ty_Bool) -> new_esEs1(wu260, wu270) new_esEs6(wu17, wu200, bd) -> error([]) new_esEs(wu260, wu270, app(ty_Maybe, cg)) -> new_esEs6(wu260, wu270, cg) new_esEs1(True, True) -> True new_esEs12(wu17, wu200) -> error([]) new_esEs0(wu17, wu200, bb) -> error([]) new_esEs1(False, False) -> True new_esEs4(wu17, wu200) -> error([]) new_esEs(wu260, wu270, app(app(ty_Either, db), dc)) -> new_esEs9(wu260, wu270, db, dc) new_esEs(wu260, wu270, app(app(app(ty_@3, cd), ce), cf)) -> new_esEs10(wu260, wu270, cd, ce, cf) new_esEs2(wu17, wu200) -> error([]) new_esEs(wu260, wu270, ty_Double) -> new_esEs8(wu260, wu270) new_esEs11(wu17, wu200, cb, cc) -> error([]) new_esEs(wu260, wu270, ty_Ordering) -> new_esEs5(wu260, wu270) new_esEs(wu260, wu270, ty_Char) -> new_esEs4(wu260, wu270) new_esEs3(wu17, wu200, bc) -> error([]) new_esEs1(False, True) -> False new_esEs1(True, False) -> False new_esEs8(wu17, wu200) -> error([]) new_esEs9(wu17, wu200, be, bf) -> error([]) new_esEs(wu260, wu270, app(ty_[], da)) -> new_esEs0(wu260, wu270, da) new_esEs(wu260, wu270, ty_Int) -> new_esEs13(wu260, wu270) The set Q consists of the following terms: new_esEs(x0, x1, ty_Int) new_esEs1(True, True) new_esEs1(False, True) new_esEs1(True, False) new_esEs(x0, x1, ty_Float) new_esEs4(x0, x1) new_esEs(x0, x1, ty_Integer) new_esEs10(x0, x1, x2, x3, x4) new_esEs(x0, x1, app(app(app(ty_@3, x2), x3), x4)) new_esEs8(x0, x1) new_esEs(x0, x1, app(app(ty_Either, x2), x3)) new_esEs7(x0, x1) new_esEs(x0, x1, app(app(ty_@2, x2), x3)) new_esEs(x0, x1, ty_Bool) new_esEs9(x0, x1, x2, x3) new_esEs12(x0, x1) new_esEs0(x0, x1, x2) new_esEs11(x0, x1, x2, x3) new_esEs(x0, x1, app(ty_Ratio, x2)) new_esEs2(x0, x1) new_esEs3(x0, x1, x2) new_esEs(x0, x1, ty_Char) new_esEs13(x0, x1) new_esEs(x0, x1, app(ty_Maybe, x2)) new_esEs(x0, x1, app(ty_[], x2)) new_esEs6(x0, x1, x2) new_esEs(x0, x1, ty_Ordering) new_esEs(x0, x1, ty_Double) new_esEs(x0, x1, ty_@0) new_esEs1(False, False) new_esEs5(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 13 less nodes. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: new_asAs(True, :(x0, y1), :(x1, y3), ty_Bool) -> new_asAs(new_esEs1(x0, x1), y1, y3, ty_Bool) The TRS R consists of the following rules: new_esEs(wu260, wu270, app(ty_Ratio, df)) -> new_esEs3(wu260, wu270, df) new_esEs10(wu17, wu200, bg, bh, ca) -> error([]) new_esEs(wu260, wu270, ty_@0) -> new_esEs2(wu260, wu270) new_esEs(wu260, wu270, ty_Integer) -> new_esEs7(wu260, wu270) new_esEs5(wu17, wu200) -> error([]) new_esEs13(wu17, wu200) -> error([]) new_esEs(wu260, wu270, ty_Float) -> new_esEs12(wu260, wu270) new_esEs(wu260, wu270, app(app(ty_@2, dd), de)) -> new_esEs11(wu260, wu270, dd, de) new_esEs7(wu17, wu200) -> error([]) new_esEs(wu260, wu270, ty_Bool) -> new_esEs1(wu260, wu270) new_esEs6(wu17, wu200, bd) -> error([]) new_esEs(wu260, wu270, app(ty_Maybe, cg)) -> new_esEs6(wu260, wu270, cg) new_esEs1(True, True) -> True new_esEs12(wu17, wu200) -> error([]) new_esEs0(wu17, wu200, bb) -> error([]) new_esEs1(False, False) -> True new_esEs4(wu17, wu200) -> error([]) new_esEs(wu260, wu270, app(app(ty_Either, db), dc)) -> new_esEs9(wu260, wu270, db, dc) new_esEs(wu260, wu270, app(app(app(ty_@3, cd), ce), cf)) -> new_esEs10(wu260, wu270, cd, ce, cf) new_esEs2(wu17, wu200) -> error([]) new_esEs(wu260, wu270, ty_Double) -> new_esEs8(wu260, wu270) new_esEs11(wu17, wu200, cb, cc) -> error([]) new_esEs(wu260, wu270, ty_Ordering) -> new_esEs5(wu260, wu270) new_esEs(wu260, wu270, ty_Char) -> new_esEs4(wu260, wu270) new_esEs3(wu17, wu200, bc) -> error([]) new_esEs1(False, True) -> False new_esEs1(True, False) -> False new_esEs8(wu17, wu200) -> error([]) new_esEs9(wu17, wu200, be, bf) -> error([]) new_esEs(wu260, wu270, app(ty_[], da)) -> new_esEs0(wu260, wu270, da) new_esEs(wu260, wu270, ty_Int) -> new_esEs13(wu260, wu270) The set Q consists of the following terms: new_esEs(x0, x1, ty_Int) new_esEs1(True, True) new_esEs1(False, True) new_esEs1(True, False) new_esEs(x0, x1, ty_Float) new_esEs4(x0, x1) new_esEs(x0, x1, ty_Integer) new_esEs10(x0, x1, x2, x3, x4) new_esEs(x0, x1, app(app(app(ty_@3, x2), x3), x4)) new_esEs8(x0, x1) new_esEs(x0, x1, app(app(ty_Either, x2), x3)) new_esEs7(x0, x1) new_esEs(x0, x1, app(app(ty_@2, x2), x3)) new_esEs(x0, x1, ty_Bool) new_esEs9(x0, x1, x2, x3) new_esEs12(x0, x1) new_esEs0(x0, x1, x2) new_esEs11(x0, x1, x2, x3) new_esEs(x0, x1, app(ty_Ratio, x2)) new_esEs2(x0, x1) new_esEs3(x0, x1, x2) new_esEs(x0, x1, ty_Char) new_esEs13(x0, x1) new_esEs(x0, x1, app(ty_Maybe, x2)) new_esEs(x0, x1, app(ty_[], x2)) new_esEs6(x0, x1, x2) new_esEs(x0, x1, ty_Ordering) new_esEs(x0, x1, ty_Double) new_esEs(x0, x1, ty_@0) new_esEs1(False, False) new_esEs5(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: new_asAs(True, :(x0, y1), :(x1, y3), ty_Bool) -> new_asAs(new_esEs1(x0, x1), y1, y3, ty_Bool) The TRS R consists of the following rules: new_esEs1(True, True) -> True new_esEs1(False, False) -> True new_esEs1(False, True) -> False new_esEs1(True, False) -> False The set Q consists of the following terms: new_esEs(x0, x1, ty_Int) new_esEs1(True, True) new_esEs1(False, True) new_esEs1(True, False) new_esEs(x0, x1, ty_Float) new_esEs4(x0, x1) new_esEs(x0, x1, ty_Integer) new_esEs10(x0, x1, x2, x3, x4) new_esEs(x0, x1, app(app(app(ty_@3, x2), x3), x4)) new_esEs8(x0, x1) new_esEs(x0, x1, app(app(ty_Either, x2), x3)) new_esEs7(x0, x1) new_esEs(x0, x1, app(app(ty_@2, x2), x3)) new_esEs(x0, x1, ty_Bool) new_esEs9(x0, x1, x2, x3) new_esEs12(x0, x1) new_esEs0(x0, x1, x2) new_esEs11(x0, x1, x2, x3) new_esEs(x0, x1, app(ty_Ratio, x2)) new_esEs2(x0, x1) new_esEs3(x0, x1, x2) new_esEs(x0, x1, ty_Char) new_esEs13(x0, x1) new_esEs(x0, x1, app(ty_Maybe, x2)) new_esEs(x0, x1, app(ty_[], x2)) new_esEs6(x0, x1, x2) new_esEs(x0, x1, ty_Ordering) new_esEs(x0, x1, ty_Double) new_esEs(x0, x1, ty_@0) new_esEs1(False, False) new_esEs5(x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. new_esEs(x0, x1, ty_Int) new_esEs(x0, x1, ty_Float) new_esEs4(x0, x1) new_esEs(x0, x1, ty_Integer) new_esEs10(x0, x1, x2, x3, x4) new_esEs(x0, x1, app(app(app(ty_@3, x2), x3), x4)) new_esEs8(x0, x1) new_esEs(x0, x1, app(app(ty_Either, x2), x3)) new_esEs7(x0, x1) new_esEs(x0, x1, app(app(ty_@2, x2), x3)) new_esEs(x0, x1, ty_Bool) new_esEs9(x0, x1, x2, x3) new_esEs12(x0, x1) new_esEs0(x0, x1, x2) new_esEs11(x0, x1, x2, x3) new_esEs(x0, x1, app(ty_Ratio, x2)) new_esEs2(x0, x1) new_esEs3(x0, x1, x2) new_esEs(x0, x1, ty_Char) new_esEs13(x0, x1) new_esEs(x0, x1, app(ty_Maybe, x2)) new_esEs(x0, x1, app(ty_[], x2)) new_esEs6(x0, x1, x2) new_esEs(x0, x1, ty_Ordering) new_esEs(x0, x1, ty_Double) new_esEs(x0, x1, ty_@0) new_esEs5(x0, x1) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: new_asAs(True, :(x0, y1), :(x1, y3), ty_Bool) -> new_asAs(new_esEs1(x0, x1), y1, y3, ty_Bool) The TRS R consists of the following rules: new_esEs1(True, True) -> True new_esEs1(False, False) -> True new_esEs1(False, True) -> False new_esEs1(True, False) -> False The set Q consists of the following terms: new_esEs1(True, True) new_esEs1(False, True) new_esEs1(True, False) new_esEs1(False, False) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule new_asAs(True, :(x0, y1), :(x1, y3), ty_Bool) -> new_asAs(new_esEs1(x0, x1), y1, y3, ty_Bool) at position [0] we obtained the following new rules [LPAR04]: (new_asAs(True, :(True, y1), :(True, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool),new_asAs(True, :(True, y1), :(True, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool)) (new_asAs(True, :(False, y1), :(False, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool),new_asAs(True, :(False, y1), :(False, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool)) (new_asAs(True, :(False, y1), :(True, y3), ty_Bool) -> new_asAs(False, y1, y3, ty_Bool),new_asAs(True, :(False, y1), :(True, y3), ty_Bool) -> new_asAs(False, y1, y3, ty_Bool)) (new_asAs(True, :(True, y1), :(False, y3), ty_Bool) -> new_asAs(False, y1, y3, ty_Bool),new_asAs(True, :(True, y1), :(False, y3), ty_Bool) -> new_asAs(False, y1, y3, ty_Bool)) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: new_asAs(True, :(True, y1), :(True, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) new_asAs(True, :(False, y1), :(False, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) new_asAs(True, :(False, y1), :(True, y3), ty_Bool) -> new_asAs(False, y1, y3, ty_Bool) new_asAs(True, :(True, y1), :(False, y3), ty_Bool) -> new_asAs(False, y1, y3, ty_Bool) The TRS R consists of the following rules: new_esEs1(True, True) -> True new_esEs1(False, False) -> True new_esEs1(False, True) -> False new_esEs1(True, False) -> False The set Q consists of the following terms: new_esEs1(True, True) new_esEs1(False, True) new_esEs1(True, False) new_esEs1(False, False) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: new_asAs(True, :(True, y1), :(True, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) new_asAs(True, :(False, y1), :(False, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) The TRS R consists of the following rules: new_esEs1(True, True) -> True new_esEs1(False, False) -> True new_esEs1(False, True) -> False new_esEs1(True, False) -> False The set Q consists of the following terms: new_esEs1(True, True) new_esEs1(False, True) new_esEs1(True, False) new_esEs1(False, False) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: new_asAs(True, :(True, y1), :(True, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) new_asAs(True, :(False, y1), :(False, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) R is empty. The set Q consists of the following terms: new_esEs1(True, True) new_esEs1(False, True) new_esEs1(True, False) new_esEs1(False, False) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. new_esEs1(True, True) new_esEs1(False, True) new_esEs1(True, False) new_esEs1(False, False) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: new_asAs(True, :(True, y1), :(True, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) new_asAs(True, :(False, y1), :(False, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *new_asAs(True, :(True, y1), :(True, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) The graph contains the following edges 1 >= 1, 2 > 1, 3 > 1, 2 > 2, 3 > 3, 4 >= 4 *new_asAs(True, :(False, y1), :(False, y3), ty_Bool) -> new_asAs(True, y1, y3, ty_Bool) The graph contains the following edges 1 >= 1, 2 > 2, 3 > 3, 4 >= 4 ---------------------------------------- (34) YES ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: new_isPrefixOf0(wu16, wu17, :(wu180, wu181), wu19, ba) -> new_isPrefixOf0(new_flip(wu16, wu17, ba), wu180, wu181, wu19, ba) The TRS R consists of the following rules: new_flip(wu16, wu17, ba) -> :(wu17, wu16) The set Q consists of the following terms: new_flip(x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule new_isPrefixOf0(wu16, wu17, :(wu180, wu181), wu19, ba) -> new_isPrefixOf0(new_flip(wu16, wu17, ba), wu180, wu181, wu19, ba) at position [0] we obtained the following new rules [LPAR04]: (new_isPrefixOf0(wu16, wu17, :(wu180, wu181), wu19, ba) -> new_isPrefixOf0(:(wu17, wu16), wu180, wu181, wu19, ba),new_isPrefixOf0(wu16, wu17, :(wu180, wu181), wu19, ba) -> new_isPrefixOf0(:(wu17, wu16), wu180, wu181, wu19, ba)) ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: new_isPrefixOf0(wu16, wu17, :(wu180, wu181), wu19, ba) -> new_isPrefixOf0(:(wu17, wu16), wu180, wu181, wu19, ba) The TRS R consists of the following rules: new_flip(wu16, wu17, ba) -> :(wu17, wu16) The set Q consists of the following terms: new_flip(x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: new_isPrefixOf0(wu16, wu17, :(wu180, wu181), wu19, ba) -> new_isPrefixOf0(:(wu17, wu16), wu180, wu181, wu19, ba) R is empty. The set Q consists of the following terms: new_flip(x0, x1, x2) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. new_flip(x0, x1, x2) ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: new_isPrefixOf0(wu16, wu17, :(wu180, wu181), wu19, ba) -> new_isPrefixOf0(:(wu17, wu16), wu180, wu181, wu19, ba) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *new_isPrefixOf0(wu16, wu17, :(wu180, wu181), wu19, ba) -> new_isPrefixOf0(:(wu17, wu16), wu180, wu181, wu19, ba) The graph contains the following edges 3 > 2, 3 > 3, 4 >= 4, 5 >= 5 ---------------------------------------- (43) YES