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