10.55/3.59 YES 10.66/3.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 10.66/3.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.66/3.61 10.66/3.61 10.66/3.61 Left Termination of the query pattern 10.66/3.61 10.66/3.61 mergesort(g,a) 10.66/3.61 10.66/3.61 w.r.t. the given Prolog program could successfully be proven: 10.66/3.61 10.66/3.61 (0) Prolog 10.66/3.61 (1) PrologToPiTRSProof [SOUND, 0 ms] 10.66/3.61 (2) PiTRS 10.66/3.61 (3) DependencyPairsProof [EQUIVALENT, 5 ms] 10.66/3.61 (4) PiDP 10.66/3.61 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 10.66/3.61 (6) AND 10.66/3.61 (7) PiDP 10.66/3.61 (8) UsableRulesProof [EQUIVALENT, 0 ms] 10.66/3.61 (9) PiDP 10.66/3.61 (10) PiDPToQDPProof [EQUIVALENT, 0 ms] 10.66/3.61 (11) QDP 10.66/3.61 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.66/3.61 (13) YES 10.66/3.61 (14) PiDP 10.66/3.61 (15) UsableRulesProof [EQUIVALENT, 0 ms] 10.66/3.61 (16) PiDP 10.66/3.61 (17) PiDPToQDPProof [EQUIVALENT, 0 ms] 10.66/3.61 (18) QDP 10.66/3.61 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.66/3.61 (20) YES 10.66/3.61 (21) PiDP 10.66/3.61 (22) UsableRulesProof [EQUIVALENT, 0 ms] 10.66/3.61 (23) PiDP 10.66/3.61 (24) PiDPToQDPProof [SOUND, 0 ms] 10.66/3.61 (25) QDP 10.66/3.61 (26) QDPOrderProof [EQUIVALENT, 29 ms] 10.66/3.61 (27) QDP 10.66/3.61 (28) PisEmptyProof [EQUIVALENT, 0 ms] 10.66/3.61 (29) YES 10.66/3.61 (30) PiDP 10.66/3.61 (31) UsableRulesProof [EQUIVALENT, 0 ms] 10.66/3.61 (32) PiDP 10.66/3.61 (33) PiDPToQDPProof [SOUND, 0 ms] 10.66/3.61 (34) QDP 10.66/3.61 (35) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.66/3.61 (36) YES 10.66/3.61 (37) PiDP 10.66/3.61 (38) UsableRulesProof [EQUIVALENT, 0 ms] 10.66/3.61 (39) PiDP 10.66/3.61 (40) PiDPToQDPProof [SOUND, 0 ms] 10.66/3.61 (41) QDP 10.66/3.61 (42) QDPQMonotonicMRRProof [EQUIVALENT, 95 ms] 10.66/3.61 (43) QDP 10.66/3.61 (44) DependencyGraphProof [EQUIVALENT, 0 ms] 10.66/3.61 (45) TRUE 10.66/3.61 10.66/3.61 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (0) 10.66/3.61 Obligation: 10.66/3.61 Clauses: 10.66/3.61 10.66/3.61 mergesort([], []). 10.66/3.61 mergesort(.(E, []), .(E, [])). 10.66/3.61 mergesort(.(E, .(F, U)), V) :- ','(split(U, L2, L1), ','(mergesort(.(E, L2), X), ','(mergesort(.(F, L1), Z), merge(X, Z, V)))). 10.66/3.61 merge(X, [], X). 10.66/3.61 merge([], X, X). 10.66/3.61 merge(.(A, X), .(B, Y), .(A, Z)) :- ','(le(A, B), merge(X, .(B, Y), Z)). 10.66/3.61 merge(.(A, X), .(B, Y), .(B, Z)) :- ','(gt(A, B), merge(.(A, X), Y, Z)). 10.66/3.61 split([], [], []). 10.66/3.61 split(.(E, U), .(E, V), W) :- split(U, W, V). 10.66/3.61 gt(s(X), s(Y)) :- gt(X, Y). 10.66/3.61 gt(s(X), 0). 10.66/3.61 le(s(X), s(Y)) :- le(X, Y). 10.66/3.61 le(0, s(Y)). 10.66/3.61 le(0, 0). 10.66/3.61 10.66/3.61 10.66/3.61 Query: mergesort(g,a) 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (1) PrologToPiTRSProof (SOUND) 10.66/3.61 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 10.66/3.61 10.66/3.61 mergesort_in_2: (b,f) 10.66/3.61 10.66/3.61 split_in_3: (b,f,f) 10.66/3.61 10.66/3.61 merge_in_3: (b,b,f) 10.66/3.61 10.66/3.61 le_in_2: (b,b) 10.66/3.61 10.66/3.61 gt_in_2: (b,b) 10.66/3.61 10.66/3.61 Transforming Prolog into the following Term Rewriting System: 10.66/3.61 10.66/3.61 Pi-finite rewrite system: 10.66/3.61 The TRS R consists of the following rules: 10.66/3.61 10.66/3.61 mergesort_in_ga([], []) -> mergesort_out_ga([], []) 10.66/3.61 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.61 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.61 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.61 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.61 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.61 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.61 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.61 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.61 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.61 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.61 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.61 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.61 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.61 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.61 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.61 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.61 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.61 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.61 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.61 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.61 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.61 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.61 10.66/3.61 The argument filtering Pi contains the following mapping: 10.66/3.61 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.61 10.66/3.61 [] = [] 10.66/3.61 10.66/3.61 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.61 10.66/3.61 .(x1, x2) = .(x1, x2) 10.66/3.61 10.66/3.61 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.61 10.66/3.61 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.61 10.66/3.61 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.61 10.66/3.61 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.61 10.66/3.61 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.61 10.66/3.61 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.61 10.66/3.61 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.61 10.66/3.61 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.61 10.66/3.61 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.61 10.66/3.61 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.61 10.66/3.61 s(x1) = s(x1) 10.66/3.61 10.66/3.61 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.61 10.66/3.61 0 = 0 10.66/3.61 10.66/3.61 le_out_gg(x1, x2) = le_out_gg 10.66/3.61 10.66/3.61 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.61 10.66/3.61 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.61 10.66/3.61 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.61 10.66/3.61 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.61 10.66/3.61 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.61 10.66/3.61 10.66/3.61 10.66/3.61 10.66/3.61 10.66/3.61 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 10.66/3.61 10.66/3.61 10.66/3.61 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (2) 10.66/3.61 Obligation: 10.66/3.61 Pi-finite rewrite system: 10.66/3.61 The TRS R consists of the following rules: 10.66/3.61 10.66/3.61 mergesort_in_ga([], []) -> mergesort_out_ga([], []) 10.66/3.61 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.61 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.61 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.61 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.61 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.61 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.61 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.61 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.61 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.61 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.61 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.61 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.61 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.61 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.61 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.61 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.61 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.61 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.61 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.61 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.61 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.61 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.61 10.66/3.61 The argument filtering Pi contains the following mapping: 10.66/3.61 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.61 10.66/3.61 [] = [] 10.66/3.61 10.66/3.61 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.61 10.66/3.61 .(x1, x2) = .(x1, x2) 10.66/3.61 10.66/3.61 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.61 10.66/3.61 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.61 10.66/3.61 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.61 10.66/3.61 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.61 10.66/3.61 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.61 10.66/3.61 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.61 10.66/3.61 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.61 10.66/3.61 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.61 10.66/3.61 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.61 10.66/3.61 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.61 10.66/3.61 s(x1) = s(x1) 10.66/3.61 10.66/3.61 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.61 10.66/3.61 0 = 0 10.66/3.61 10.66/3.61 le_out_gg(x1, x2) = le_out_gg 10.66/3.61 10.66/3.61 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.61 10.66/3.61 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.61 10.66/3.61 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.61 10.66/3.61 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.61 10.66/3.61 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.61 10.66/3.61 10.66/3.61 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (3) DependencyPairsProof (EQUIVALENT) 10.66/3.61 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 10.66/3.61 Pi DP problem: 10.66/3.61 The TRS P consists of the following rules: 10.66/3.61 10.66/3.61 MERGESORT_IN_GA(.(E, .(F, U)), V) -> U1_GA(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.61 MERGESORT_IN_GA(.(E, .(F, U)), V) -> SPLIT_IN_GAA(U, L2, L1) 10.66/3.61 SPLIT_IN_GAA(.(E, U), .(E, V), W) -> U9_GAA(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.61 SPLIT_IN_GAA(.(E, U), .(E, V), W) -> SPLIT_IN_GAA(U, W, V) 10.66/3.61 U1_GA(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_GA(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.61 U1_GA(E, F, U, V, split_out_gaa(U, L2, L1)) -> MERGESORT_IN_GA(.(E, L2), X) 10.66/3.61 U2_GA(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_GA(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.61 U2_GA(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> MERGESORT_IN_GA(.(F, L1), Z) 10.66/3.61 U3_GA(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_GA(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.61 U3_GA(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> MERGE_IN_GGA(X, Z, V) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(A, Z)) -> U5_GGA(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(A, Z)) -> LE_IN_GG(A, B) 10.66/3.61 LE_IN_GG(s(X), s(Y)) -> U11_GG(X, Y, le_in_gg(X, Y)) 10.66/3.61 LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) 10.66/3.61 U5_GGA(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_GGA(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.61 U5_GGA(A, X, B, Y, Z, le_out_gg(A, B)) -> MERGE_IN_GGA(X, .(B, Y), Z) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(B, Z)) -> U7_GGA(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(B, Z)) -> GT_IN_GG(A, B) 10.66/3.61 GT_IN_GG(s(X), s(Y)) -> U10_GG(X, Y, gt_in_gg(X, Y)) 10.66/3.61 GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) 10.66/3.61 U7_GGA(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_GGA(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.61 U7_GGA(A, X, B, Y, Z, gt_out_gg(A, B)) -> MERGE_IN_GGA(.(A, X), Y, Z) 10.66/3.61 10.66/3.61 The TRS R consists of the following rules: 10.66/3.61 10.66/3.61 mergesort_in_ga([], []) -> mergesort_out_ga([], []) 10.66/3.61 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.61 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.61 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.61 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.61 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.61 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.61 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.61 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.61 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.61 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.61 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.61 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.61 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.61 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.61 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.61 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.61 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.61 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.61 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.61 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.61 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.61 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.61 10.66/3.61 The argument filtering Pi contains the following mapping: 10.66/3.61 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.61 10.66/3.61 [] = [] 10.66/3.61 10.66/3.61 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.61 10.66/3.61 .(x1, x2) = .(x1, x2) 10.66/3.61 10.66/3.61 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.61 10.66/3.61 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.61 10.66/3.61 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.61 10.66/3.61 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.61 10.66/3.61 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.61 10.66/3.61 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.61 10.66/3.61 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.61 10.66/3.61 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.61 10.66/3.61 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.61 10.66/3.61 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.61 10.66/3.61 s(x1) = s(x1) 10.66/3.61 10.66/3.61 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.61 10.66/3.61 0 = 0 10.66/3.61 10.66/3.61 le_out_gg(x1, x2) = le_out_gg 10.66/3.61 10.66/3.61 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.61 10.66/3.61 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.61 10.66/3.61 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.61 10.66/3.61 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.61 10.66/3.61 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.61 10.66/3.61 MERGESORT_IN_GA(x1, x2) = MERGESORT_IN_GA(x1) 10.66/3.61 10.66/3.61 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x5) 10.66/3.61 10.66/3.61 SPLIT_IN_GAA(x1, x2, x3) = SPLIT_IN_GAA(x1) 10.66/3.61 10.66/3.61 U9_GAA(x1, x2, x3, x4, x5) = U9_GAA(x1, x5) 10.66/3.61 10.66/3.61 U2_GA(x1, x2, x3, x4, x5, x6) = U2_GA(x2, x5, x6) 10.66/3.61 10.66/3.61 U3_GA(x1, x2, x3, x4, x5, x6) = U3_GA(x5, x6) 10.66/3.61 10.66/3.61 U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) 10.66/3.61 10.66/3.61 MERGE_IN_GGA(x1, x2, x3) = MERGE_IN_GGA(x1, x2) 10.66/3.61 10.66/3.61 U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) 10.66/3.61 10.66/3.61 U11_GG(x1, x2, x3) = U11_GG(x3) 10.66/3.61 10.66/3.61 U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x6) 10.66/3.61 10.66/3.61 U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 GT_IN_GG(x1, x2) = GT_IN_GG(x1, x2) 10.66/3.61 10.66/3.61 U10_GG(x1, x2, x3) = U10_GG(x3) 10.66/3.61 10.66/3.61 U8_GGA(x1, x2, x3, x4, x5, x6) = U8_GGA(x3, x6) 10.66/3.61 10.66/3.61 10.66/3.61 We have to consider all (P,R,Pi)-chains 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (4) 10.66/3.61 Obligation: 10.66/3.61 Pi DP problem: 10.66/3.61 The TRS P consists of the following rules: 10.66/3.61 10.66/3.61 MERGESORT_IN_GA(.(E, .(F, U)), V) -> U1_GA(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.61 MERGESORT_IN_GA(.(E, .(F, U)), V) -> SPLIT_IN_GAA(U, L2, L1) 10.66/3.61 SPLIT_IN_GAA(.(E, U), .(E, V), W) -> U9_GAA(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.61 SPLIT_IN_GAA(.(E, U), .(E, V), W) -> SPLIT_IN_GAA(U, W, V) 10.66/3.61 U1_GA(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_GA(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.61 U1_GA(E, F, U, V, split_out_gaa(U, L2, L1)) -> MERGESORT_IN_GA(.(E, L2), X) 10.66/3.61 U2_GA(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_GA(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.61 U2_GA(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> MERGESORT_IN_GA(.(F, L1), Z) 10.66/3.61 U3_GA(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_GA(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.61 U3_GA(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> MERGE_IN_GGA(X, Z, V) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(A, Z)) -> U5_GGA(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(A, Z)) -> LE_IN_GG(A, B) 10.66/3.61 LE_IN_GG(s(X), s(Y)) -> U11_GG(X, Y, le_in_gg(X, Y)) 10.66/3.61 LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) 10.66/3.61 U5_GGA(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_GGA(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.61 U5_GGA(A, X, B, Y, Z, le_out_gg(A, B)) -> MERGE_IN_GGA(X, .(B, Y), Z) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(B, Z)) -> U7_GGA(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(B, Z)) -> GT_IN_GG(A, B) 10.66/3.61 GT_IN_GG(s(X), s(Y)) -> U10_GG(X, Y, gt_in_gg(X, Y)) 10.66/3.61 GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) 10.66/3.61 U7_GGA(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_GGA(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.61 U7_GGA(A, X, B, Y, Z, gt_out_gg(A, B)) -> MERGE_IN_GGA(.(A, X), Y, Z) 10.66/3.61 10.66/3.61 The TRS R consists of the following rules: 10.66/3.61 10.66/3.61 mergesort_in_ga([], []) -> mergesort_out_ga([], []) 10.66/3.61 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.61 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.61 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.61 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.61 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.61 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.61 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.61 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.61 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.61 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.61 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.61 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.61 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.61 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.61 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.61 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.61 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.61 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.61 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.61 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.61 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.61 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.61 10.66/3.61 The argument filtering Pi contains the following mapping: 10.66/3.61 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.61 10.66/3.61 [] = [] 10.66/3.61 10.66/3.61 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.61 10.66/3.61 .(x1, x2) = .(x1, x2) 10.66/3.61 10.66/3.61 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.61 10.66/3.61 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.61 10.66/3.61 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.61 10.66/3.61 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.61 10.66/3.61 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.61 10.66/3.61 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.61 10.66/3.61 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.61 10.66/3.61 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.61 10.66/3.61 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.61 10.66/3.61 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.61 10.66/3.61 s(x1) = s(x1) 10.66/3.61 10.66/3.61 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.61 10.66/3.61 0 = 0 10.66/3.61 10.66/3.61 le_out_gg(x1, x2) = le_out_gg 10.66/3.61 10.66/3.61 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.61 10.66/3.61 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.61 10.66/3.61 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.61 10.66/3.61 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.61 10.66/3.61 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.61 10.66/3.61 MERGESORT_IN_GA(x1, x2) = MERGESORT_IN_GA(x1) 10.66/3.61 10.66/3.61 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x5) 10.66/3.61 10.66/3.61 SPLIT_IN_GAA(x1, x2, x3) = SPLIT_IN_GAA(x1) 10.66/3.61 10.66/3.61 U9_GAA(x1, x2, x3, x4, x5) = U9_GAA(x1, x5) 10.66/3.61 10.66/3.61 U2_GA(x1, x2, x3, x4, x5, x6) = U2_GA(x2, x5, x6) 10.66/3.61 10.66/3.61 U3_GA(x1, x2, x3, x4, x5, x6) = U3_GA(x5, x6) 10.66/3.61 10.66/3.61 U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) 10.66/3.61 10.66/3.61 MERGE_IN_GGA(x1, x2, x3) = MERGE_IN_GGA(x1, x2) 10.66/3.61 10.66/3.61 U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) 10.66/3.61 10.66/3.61 U11_GG(x1, x2, x3) = U11_GG(x3) 10.66/3.61 10.66/3.61 U6_GGA(x1, x2, x3, x4, x5, x6) = U6_GGA(x1, x6) 10.66/3.61 10.66/3.61 U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 GT_IN_GG(x1, x2) = GT_IN_GG(x1, x2) 10.66/3.61 10.66/3.61 U10_GG(x1, x2, x3) = U10_GG(x3) 10.66/3.61 10.66/3.61 U8_GGA(x1, x2, x3, x4, x5, x6) = U8_GGA(x3, x6) 10.66/3.61 10.66/3.61 10.66/3.61 We have to consider all (P,R,Pi)-chains 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (5) DependencyGraphProof (EQUIVALENT) 10.66/3.61 The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 11 less nodes. 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (6) 10.66/3.61 Complex Obligation (AND) 10.66/3.61 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (7) 10.66/3.61 Obligation: 10.66/3.61 Pi DP problem: 10.66/3.61 The TRS P consists of the following rules: 10.66/3.61 10.66/3.61 GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) 10.66/3.61 10.66/3.61 The TRS R consists of the following rules: 10.66/3.61 10.66/3.61 mergesort_in_ga([], []) -> mergesort_out_ga([], []) 10.66/3.61 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.61 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.61 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.61 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.61 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.61 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.61 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.61 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.61 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.61 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.61 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.61 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.61 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.61 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.61 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.61 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.61 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.61 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.61 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.61 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.61 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.61 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.61 10.66/3.61 The argument filtering Pi contains the following mapping: 10.66/3.61 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.61 10.66/3.61 [] = [] 10.66/3.61 10.66/3.61 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.61 10.66/3.61 .(x1, x2) = .(x1, x2) 10.66/3.61 10.66/3.61 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.61 10.66/3.61 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.61 10.66/3.61 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.61 10.66/3.61 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.61 10.66/3.61 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.61 10.66/3.61 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.61 10.66/3.61 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.61 10.66/3.61 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.61 10.66/3.61 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.61 10.66/3.61 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.61 10.66/3.61 s(x1) = s(x1) 10.66/3.61 10.66/3.61 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.61 10.66/3.61 0 = 0 10.66/3.61 10.66/3.61 le_out_gg(x1, x2) = le_out_gg 10.66/3.61 10.66/3.61 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.61 10.66/3.61 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.61 10.66/3.61 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.61 10.66/3.61 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.61 10.66/3.61 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.61 10.66/3.61 GT_IN_GG(x1, x2) = GT_IN_GG(x1, x2) 10.66/3.61 10.66/3.61 10.66/3.61 We have to consider all (P,R,Pi)-chains 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (8) UsableRulesProof (EQUIVALENT) 10.66/3.61 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (9) 10.66/3.61 Obligation: 10.66/3.61 Pi DP problem: 10.66/3.61 The TRS P consists of the following rules: 10.66/3.61 10.66/3.61 GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) 10.66/3.61 10.66/3.61 R is empty. 10.66/3.61 Pi is empty. 10.66/3.61 We have to consider all (P,R,Pi)-chains 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (10) PiDPToQDPProof (EQUIVALENT) 10.66/3.61 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (11) 10.66/3.61 Obligation: 10.66/3.61 Q DP problem: 10.66/3.61 The TRS P consists of the following rules: 10.66/3.61 10.66/3.61 GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) 10.66/3.61 10.66/3.61 R is empty. 10.66/3.61 Q is empty. 10.66/3.61 We have to consider all (P,Q,R)-chains. 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (12) QDPSizeChangeProof (EQUIVALENT) 10.66/3.61 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 10.66/3.61 10.66/3.61 From the DPs we obtained the following set of size-change graphs: 10.66/3.61 *GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) 10.66/3.61 The graph contains the following edges 1 > 1, 2 > 2 10.66/3.61 10.66/3.61 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (13) 10.66/3.61 YES 10.66/3.61 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (14) 10.66/3.61 Obligation: 10.66/3.61 Pi DP problem: 10.66/3.61 The TRS P consists of the following rules: 10.66/3.61 10.66/3.61 LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) 10.66/3.61 10.66/3.61 The TRS R consists of the following rules: 10.66/3.61 10.66/3.61 mergesort_in_ga([], []) -> mergesort_out_ga([], []) 10.66/3.61 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.61 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.61 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.61 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.61 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.61 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.61 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.61 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.61 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.61 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.61 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.61 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.61 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.61 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.61 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.61 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.61 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.61 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.61 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.61 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.61 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.61 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.61 10.66/3.61 The argument filtering Pi contains the following mapping: 10.66/3.61 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.61 10.66/3.61 [] = [] 10.66/3.61 10.66/3.61 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.61 10.66/3.61 .(x1, x2) = .(x1, x2) 10.66/3.61 10.66/3.61 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.61 10.66/3.61 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.61 10.66/3.61 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.61 10.66/3.61 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.61 10.66/3.61 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.61 10.66/3.61 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.61 10.66/3.61 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.61 10.66/3.61 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.61 10.66/3.61 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.61 10.66/3.61 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.61 10.66/3.61 s(x1) = s(x1) 10.66/3.61 10.66/3.61 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.61 10.66/3.61 0 = 0 10.66/3.61 10.66/3.61 le_out_gg(x1, x2) = le_out_gg 10.66/3.61 10.66/3.61 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.61 10.66/3.61 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.61 10.66/3.61 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.61 10.66/3.61 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.61 10.66/3.61 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.61 10.66/3.61 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.61 10.66/3.61 LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) 10.66/3.61 10.66/3.61 10.66/3.61 We have to consider all (P,R,Pi)-chains 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (15) UsableRulesProof (EQUIVALENT) 10.66/3.61 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (16) 10.66/3.61 Obligation: 10.66/3.61 Pi DP problem: 10.66/3.61 The TRS P consists of the following rules: 10.66/3.61 10.66/3.61 LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) 10.66/3.61 10.66/3.61 R is empty. 10.66/3.61 Pi is empty. 10.66/3.61 We have to consider all (P,R,Pi)-chains 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (17) PiDPToQDPProof (EQUIVALENT) 10.66/3.61 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (18) 10.66/3.61 Obligation: 10.66/3.61 Q DP problem: 10.66/3.61 The TRS P consists of the following rules: 10.66/3.61 10.66/3.61 LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) 10.66/3.61 10.66/3.61 R is empty. 10.66/3.61 Q is empty. 10.66/3.61 We have to consider all (P,Q,R)-chains. 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (19) QDPSizeChangeProof (EQUIVALENT) 10.66/3.61 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 10.66/3.61 10.66/3.61 From the DPs we obtained the following set of size-change graphs: 10.66/3.61 *LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) 10.66/3.61 The graph contains the following edges 1 > 1, 2 > 2 10.66/3.61 10.66/3.61 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (20) 10.66/3.61 YES 10.66/3.61 10.66/3.61 ---------------------------------------- 10.66/3.61 10.66/3.61 (21) 10.66/3.61 Obligation: 10.66/3.61 Pi DP problem: 10.66/3.61 The TRS P consists of the following rules: 10.66/3.61 10.66/3.61 U5_GGA(A, X, B, Y, Z, le_out_gg(A, B)) -> MERGE_IN_GGA(X, .(B, Y), Z) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(A, Z)) -> U5_GGA(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.61 MERGE_IN_GGA(.(A, X), .(B, Y), .(B, Z)) -> U7_GGA(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.61 U7_GGA(A, X, B, Y, Z, gt_out_gg(A, B)) -> MERGE_IN_GGA(.(A, X), Y, Z) 10.66/3.61 10.66/3.61 The TRS R consists of the following rules: 10.66/3.61 10.66/3.61 mergesort_in_ga([], []) -> mergesort_out_ga([], []) 10.66/3.61 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.61 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.61 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.61 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.61 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.61 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.61 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.61 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.61 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.61 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.61 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.62 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.62 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.62 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.62 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.62 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.62 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.62 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.62 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.62 10.66/3.62 The argument filtering Pi contains the following mapping: 10.66/3.62 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.62 10.66/3.62 [] = [] 10.66/3.62 10.66/3.62 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.62 10.66/3.62 .(x1, x2) = .(x1, x2) 10.66/3.62 10.66/3.62 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.62 10.66/3.62 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.62 10.66/3.62 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.62 10.66/3.62 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.62 10.66/3.62 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.62 10.66/3.62 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.62 10.66/3.62 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.62 10.66/3.62 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.62 10.66/3.62 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.62 10.66/3.62 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.62 10.66/3.62 s(x1) = s(x1) 10.66/3.62 10.66/3.62 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.62 10.66/3.62 0 = 0 10.66/3.62 10.66/3.62 le_out_gg(x1, x2) = le_out_gg 10.66/3.62 10.66/3.62 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.62 10.66/3.62 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.62 10.66/3.62 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.62 10.66/3.62 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.62 10.66/3.62 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.62 10.66/3.62 MERGE_IN_GGA(x1, x2, x3) = MERGE_IN_GGA(x1, x2) 10.66/3.62 10.66/3.62 U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 10.66/3.62 We have to consider all (P,R,Pi)-chains 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (22) UsableRulesProof (EQUIVALENT) 10.66/3.62 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (23) 10.66/3.62 Obligation: 10.66/3.62 Pi DP problem: 10.66/3.62 The TRS P consists of the following rules: 10.66/3.62 10.66/3.62 U5_GGA(A, X, B, Y, Z, le_out_gg(A, B)) -> MERGE_IN_GGA(X, .(B, Y), Z) 10.66/3.62 MERGE_IN_GGA(.(A, X), .(B, Y), .(A, Z)) -> U5_GGA(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.62 MERGE_IN_GGA(.(A, X), .(B, Y), .(B, Z)) -> U7_GGA(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.62 U7_GGA(A, X, B, Y, Z, gt_out_gg(A, B)) -> MERGE_IN_GGA(.(A, X), Y, Z) 10.66/3.62 10.66/3.62 The TRS R consists of the following rules: 10.66/3.62 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.62 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.62 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.62 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.62 10.66/3.62 The argument filtering Pi contains the following mapping: 10.66/3.62 .(x1, x2) = .(x1, x2) 10.66/3.62 10.66/3.62 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.62 10.66/3.62 s(x1) = s(x1) 10.66/3.62 10.66/3.62 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.62 10.66/3.62 0 = 0 10.66/3.62 10.66/3.62 le_out_gg(x1, x2) = le_out_gg 10.66/3.62 10.66/3.62 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.62 10.66/3.62 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.62 10.66/3.62 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.62 10.66/3.62 MERGE_IN_GGA(x1, x2, x3) = MERGE_IN_GGA(x1, x2) 10.66/3.62 10.66/3.62 U5_GGA(x1, x2, x3, x4, x5, x6) = U5_GGA(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 U7_GGA(x1, x2, x3, x4, x5, x6) = U7_GGA(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 10.66/3.62 We have to consider all (P,R,Pi)-chains 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (24) PiDPToQDPProof (SOUND) 10.66/3.62 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (25) 10.66/3.62 Obligation: 10.66/3.62 Q DP problem: 10.66/3.62 The TRS P consists of the following rules: 10.66/3.62 10.66/3.62 U5_GGA(A, X, B, Y, le_out_gg) -> MERGE_IN_GGA(X, .(B, Y)) 10.66/3.62 MERGE_IN_GGA(.(A, X), .(B, Y)) -> U5_GGA(A, X, B, Y, le_in_gg(A, B)) 10.66/3.62 MERGE_IN_GGA(.(A, X), .(B, Y)) -> U7_GGA(A, X, B, Y, gt_in_gg(A, B)) 10.66/3.62 U7_GGA(A, X, B, Y, gt_out_gg) -> MERGE_IN_GGA(.(A, X), Y) 10.66/3.62 10.66/3.62 The TRS R consists of the following rules: 10.66/3.62 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg 10.66/3.62 le_in_gg(0, 0) -> le_out_gg 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg 10.66/3.62 U11_gg(le_out_gg) -> le_out_gg 10.66/3.62 U10_gg(gt_out_gg) -> gt_out_gg 10.66/3.62 10.66/3.62 The set Q consists of the following terms: 10.66/3.62 10.66/3.62 le_in_gg(x0, x1) 10.66/3.62 gt_in_gg(x0, x1) 10.66/3.62 U11_gg(x0) 10.66/3.62 U10_gg(x0) 10.66/3.62 10.66/3.62 We have to consider all (P,Q,R)-chains. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (26) QDPOrderProof (EQUIVALENT) 10.66/3.62 We use the reduction pair processor [LPAR04,JAR06]. 10.66/3.62 10.66/3.62 10.66/3.62 The following pairs can be oriented strictly and are deleted. 10.66/3.62 10.66/3.62 U5_GGA(A, X, B, Y, le_out_gg) -> MERGE_IN_GGA(X, .(B, Y)) 10.66/3.62 MERGE_IN_GGA(.(A, X), .(B, Y)) -> U5_GGA(A, X, B, Y, le_in_gg(A, B)) 10.66/3.62 MERGE_IN_GGA(.(A, X), .(B, Y)) -> U7_GGA(A, X, B, Y, gt_in_gg(A, B)) 10.66/3.62 U7_GGA(A, X, B, Y, gt_out_gg) -> MERGE_IN_GGA(.(A, X), Y) 10.66/3.62 The remaining pairs can at least be oriented weakly. 10.66/3.62 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 10.66/3.62 10.66/3.62 POL( U5_GGA_5(x_1, ..., x_5) ) = 2x_2 + x_4 + 2x_5 + 2 10.66/3.62 POL( le_in_gg_2(x_1, x_2) ) = 2 10.66/3.62 POL( s_1(x_1) ) = 0 10.66/3.62 POL( U11_gg_1(x_1) ) = x_1 10.66/3.62 POL( 0 ) = 0 10.66/3.62 POL( le_out_gg ) = 2 10.66/3.62 POL( U7_GGA_5(x_1, ..., x_5) ) = 2x_2 + x_4 + 2x_5 + 2 10.66/3.62 POL( gt_in_gg_2(x_1, x_2) ) = 2 10.66/3.62 POL( U10_gg_1(x_1) ) = max{0, 2x_1 - 2} 10.66/3.62 POL( gt_out_gg ) = 2 10.66/3.62 POL( MERGE_IN_GGA_2(x_1, x_2) ) = 2x_1 + x_2 + 1 10.66/3.62 POL( ._2(x_1, x_2) ) = x_2 + 2 10.66/3.62 10.66/3.62 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 10.66/3.62 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg 10.66/3.62 le_in_gg(0, 0) -> le_out_gg 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg 10.66/3.62 U11_gg(le_out_gg) -> le_out_gg 10.66/3.62 U10_gg(gt_out_gg) -> gt_out_gg 10.66/3.62 10.66/3.62 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (27) 10.66/3.62 Obligation: 10.66/3.62 Q DP problem: 10.66/3.62 P is empty. 10.66/3.62 The TRS R consists of the following rules: 10.66/3.62 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg 10.66/3.62 le_in_gg(0, 0) -> le_out_gg 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg 10.66/3.62 U11_gg(le_out_gg) -> le_out_gg 10.66/3.62 U10_gg(gt_out_gg) -> gt_out_gg 10.66/3.62 10.66/3.62 The set Q consists of the following terms: 10.66/3.62 10.66/3.62 le_in_gg(x0, x1) 10.66/3.62 gt_in_gg(x0, x1) 10.66/3.62 U11_gg(x0) 10.66/3.62 U10_gg(x0) 10.66/3.62 10.66/3.62 We have to consider all (P,Q,R)-chains. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (28) PisEmptyProof (EQUIVALENT) 10.66/3.62 The TRS P is empty. Hence, there is no (P,Q,R) chain. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (29) 10.66/3.62 YES 10.66/3.62 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (30) 10.66/3.62 Obligation: 10.66/3.62 Pi DP problem: 10.66/3.62 The TRS P consists of the following rules: 10.66/3.62 10.66/3.62 SPLIT_IN_GAA(.(E, U), .(E, V), W) -> SPLIT_IN_GAA(U, W, V) 10.66/3.62 10.66/3.62 The TRS R consists of the following rules: 10.66/3.62 10.66/3.62 mergesort_in_ga([], []) -> mergesort_out_ga([], []) 10.66/3.62 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.62 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.62 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.62 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.62 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.62 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.62 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.62 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.62 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.62 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.62 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.62 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.62 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.62 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.62 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.62 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.62 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.62 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.62 10.66/3.62 The argument filtering Pi contains the following mapping: 10.66/3.62 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.62 10.66/3.62 [] = [] 10.66/3.62 10.66/3.62 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.62 10.66/3.62 .(x1, x2) = .(x1, x2) 10.66/3.62 10.66/3.62 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.62 10.66/3.62 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.62 10.66/3.62 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.62 10.66/3.62 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.62 10.66/3.62 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.62 10.66/3.62 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.62 10.66/3.62 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.62 10.66/3.62 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.62 10.66/3.62 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.62 10.66/3.62 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.62 10.66/3.62 s(x1) = s(x1) 10.66/3.62 10.66/3.62 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.62 10.66/3.62 0 = 0 10.66/3.62 10.66/3.62 le_out_gg(x1, x2) = le_out_gg 10.66/3.62 10.66/3.62 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.62 10.66/3.62 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.62 10.66/3.62 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.62 10.66/3.62 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.62 10.66/3.62 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.62 10.66/3.62 SPLIT_IN_GAA(x1, x2, x3) = SPLIT_IN_GAA(x1) 10.66/3.62 10.66/3.62 10.66/3.62 We have to consider all (P,R,Pi)-chains 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (31) UsableRulesProof (EQUIVALENT) 10.66/3.62 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (32) 10.66/3.62 Obligation: 10.66/3.62 Pi DP problem: 10.66/3.62 The TRS P consists of the following rules: 10.66/3.62 10.66/3.62 SPLIT_IN_GAA(.(E, U), .(E, V), W) -> SPLIT_IN_GAA(U, W, V) 10.66/3.62 10.66/3.62 R is empty. 10.66/3.62 The argument filtering Pi contains the following mapping: 10.66/3.62 .(x1, x2) = .(x1, x2) 10.66/3.62 10.66/3.62 SPLIT_IN_GAA(x1, x2, x3) = SPLIT_IN_GAA(x1) 10.66/3.62 10.66/3.62 10.66/3.62 We have to consider all (P,R,Pi)-chains 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (33) PiDPToQDPProof (SOUND) 10.66/3.62 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (34) 10.66/3.62 Obligation: 10.66/3.62 Q DP problem: 10.66/3.62 The TRS P consists of the following rules: 10.66/3.62 10.66/3.62 SPLIT_IN_GAA(.(E, U)) -> SPLIT_IN_GAA(U) 10.66/3.62 10.66/3.62 R is empty. 10.66/3.62 Q is empty. 10.66/3.62 We have to consider all (P,Q,R)-chains. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (35) QDPSizeChangeProof (EQUIVALENT) 10.66/3.62 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 10.66/3.62 10.66/3.62 From the DPs we obtained the following set of size-change graphs: 10.66/3.62 *SPLIT_IN_GAA(.(E, U)) -> SPLIT_IN_GAA(U) 10.66/3.62 The graph contains the following edges 1 > 1 10.66/3.62 10.66/3.62 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (36) 10.66/3.62 YES 10.66/3.62 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (37) 10.66/3.62 Obligation: 10.66/3.62 Pi DP problem: 10.66/3.62 The TRS P consists of the following rules: 10.66/3.62 10.66/3.62 U1_GA(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_GA(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.62 U2_GA(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> MERGESORT_IN_GA(.(F, L1), Z) 10.66/3.62 MERGESORT_IN_GA(.(E, .(F, U)), V) -> U1_GA(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.62 U1_GA(E, F, U, V, split_out_gaa(U, L2, L1)) -> MERGESORT_IN_GA(.(E, L2), X) 10.66/3.62 10.66/3.62 The TRS R consists of the following rules: 10.66/3.62 10.66/3.62 mergesort_in_ga([], []) -> mergesort_out_ga([], []) 10.66/3.62 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.62 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.62 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.62 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.62 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.62 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.62 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.62 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.62 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.62 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.62 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.62 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.62 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.62 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.62 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.62 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.62 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.62 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.62 10.66/3.62 The argument filtering Pi contains the following mapping: 10.66/3.62 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.62 10.66/3.62 [] = [] 10.66/3.62 10.66/3.62 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.62 10.66/3.62 .(x1, x2) = .(x1, x2) 10.66/3.62 10.66/3.62 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.62 10.66/3.62 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.62 10.66/3.62 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.62 10.66/3.62 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.62 10.66/3.62 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.62 10.66/3.62 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.62 10.66/3.62 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.62 10.66/3.62 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.62 10.66/3.62 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.62 10.66/3.62 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.62 10.66/3.62 s(x1) = s(x1) 10.66/3.62 10.66/3.62 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.62 10.66/3.62 0 = 0 10.66/3.62 10.66/3.62 le_out_gg(x1, x2) = le_out_gg 10.66/3.62 10.66/3.62 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.62 10.66/3.62 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.62 10.66/3.62 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.62 10.66/3.62 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.62 10.66/3.62 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.62 10.66/3.62 MERGESORT_IN_GA(x1, x2) = MERGESORT_IN_GA(x1) 10.66/3.62 10.66/3.62 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x5) 10.66/3.62 10.66/3.62 U2_GA(x1, x2, x3, x4, x5, x6) = U2_GA(x2, x5, x6) 10.66/3.62 10.66/3.62 10.66/3.62 We have to consider all (P,R,Pi)-chains 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (38) UsableRulesProof (EQUIVALENT) 10.66/3.62 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (39) 10.66/3.62 Obligation: 10.66/3.62 Pi DP problem: 10.66/3.62 The TRS P consists of the following rules: 10.66/3.62 10.66/3.62 U1_GA(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_GA(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.62 U2_GA(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> MERGESORT_IN_GA(.(F, L1), Z) 10.66/3.62 MERGESORT_IN_GA(.(E, .(F, U)), V) -> U1_GA(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.62 U1_GA(E, F, U, V, split_out_gaa(U, L2, L1)) -> MERGESORT_IN_GA(.(E, L2), X) 10.66/3.62 10.66/3.62 The TRS R consists of the following rules: 10.66/3.62 10.66/3.62 mergesort_in_ga(.(E, []), .(E, [])) -> mergesort_out_ga(.(E, []), .(E, [])) 10.66/3.62 mergesort_in_ga(.(E, .(F, U)), V) -> U1_ga(E, F, U, V, split_in_gaa(U, L2, L1)) 10.66/3.62 split_in_gaa([], [], []) -> split_out_gaa([], [], []) 10.66/3.62 split_in_gaa(.(E, U), .(E, V), W) -> U9_gaa(E, U, V, W, split_in_gaa(U, W, V)) 10.66/3.62 U1_ga(E, F, U, V, split_out_gaa(U, L2, L1)) -> U2_ga(E, F, U, V, L1, mergesort_in_ga(.(E, L2), X)) 10.66/3.62 U9_gaa(E, U, V, W, split_out_gaa(U, W, V)) -> split_out_gaa(.(E, U), .(E, V), W) 10.66/3.62 U2_ga(E, F, U, V, L1, mergesort_out_ga(.(E, L2), X)) -> U3_ga(E, F, U, V, X, mergesort_in_ga(.(F, L1), Z)) 10.66/3.62 U3_ga(E, F, U, V, X, mergesort_out_ga(.(F, L1), Z)) -> U4_ga(E, F, U, V, merge_in_gga(X, Z, V)) 10.66/3.62 U4_ga(E, F, U, V, merge_out_gga(X, Z, V)) -> mergesort_out_ga(.(E, .(F, U)), V) 10.66/3.62 merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) 10.66/3.62 merge_in_gga([], X, X) -> merge_out_gga([], X, X) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y), .(A, Z)) -> U5_gga(A, X, B, Y, Z, le_in_gg(A, B)) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y), .(B, Z)) -> U7_gga(A, X, B, Y, Z, gt_in_gg(A, B)) 10.66/3.62 U5_gga(A, X, B, Y, Z, le_out_gg(A, B)) -> U6_gga(A, X, B, Y, Z, merge_in_gga(X, .(B, Y), Z)) 10.66/3.62 U7_gga(A, X, B, Y, Z, gt_out_gg(A, B)) -> U8_gga(A, X, B, Y, Z, merge_in_gga(.(A, X), Y, Z)) 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(X, Y, le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) 10.66/3.62 le_in_gg(0, 0) -> le_out_gg(0, 0) 10.66/3.62 U6_gga(A, X, B, Y, Z, merge_out_gga(X, .(B, Y), Z)) -> merge_out_gga(.(A, X), .(B, Y), .(A, Z)) 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(X, Y, gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) 10.66/3.62 U8_gga(A, X, B, Y, Z, merge_out_gga(.(A, X), Y, Z)) -> merge_out_gga(.(A, X), .(B, Y), .(B, Z)) 10.66/3.62 U11_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) 10.66/3.62 U10_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) 10.66/3.62 10.66/3.62 The argument filtering Pi contains the following mapping: 10.66/3.62 mergesort_in_ga(x1, x2) = mergesort_in_ga(x1) 10.66/3.62 10.66/3.62 [] = [] 10.66/3.62 10.66/3.62 mergesort_out_ga(x1, x2) = mergesort_out_ga(x2) 10.66/3.62 10.66/3.62 .(x1, x2) = .(x1, x2) 10.66/3.62 10.66/3.62 U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) 10.66/3.62 10.66/3.62 split_in_gaa(x1, x2, x3) = split_in_gaa(x1) 10.66/3.62 10.66/3.62 split_out_gaa(x1, x2, x3) = split_out_gaa(x2, x3) 10.66/3.62 10.66/3.62 U9_gaa(x1, x2, x3, x4, x5) = U9_gaa(x1, x5) 10.66/3.62 10.66/3.62 U2_ga(x1, x2, x3, x4, x5, x6) = U2_ga(x2, x5, x6) 10.66/3.62 10.66/3.62 U3_ga(x1, x2, x3, x4, x5, x6) = U3_ga(x5, x6) 10.66/3.62 10.66/3.62 U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) 10.66/3.62 10.66/3.62 merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) 10.66/3.62 10.66/3.62 merge_out_gga(x1, x2, x3) = merge_out_gga(x3) 10.66/3.62 10.66/3.62 U5_gga(x1, x2, x3, x4, x5, x6) = U5_gga(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 le_in_gg(x1, x2) = le_in_gg(x1, x2) 10.66/3.62 10.66/3.62 s(x1) = s(x1) 10.66/3.62 10.66/3.62 U11_gg(x1, x2, x3) = U11_gg(x3) 10.66/3.62 10.66/3.62 0 = 0 10.66/3.62 10.66/3.62 le_out_gg(x1, x2) = le_out_gg 10.66/3.62 10.66/3.62 U6_gga(x1, x2, x3, x4, x5, x6) = U6_gga(x1, x6) 10.66/3.62 10.66/3.62 U7_gga(x1, x2, x3, x4, x5, x6) = U7_gga(x1, x2, x3, x4, x6) 10.66/3.62 10.66/3.62 gt_in_gg(x1, x2) = gt_in_gg(x1, x2) 10.66/3.62 10.66/3.62 U10_gg(x1, x2, x3) = U10_gg(x3) 10.66/3.62 10.66/3.62 gt_out_gg(x1, x2) = gt_out_gg 10.66/3.62 10.66/3.62 U8_gga(x1, x2, x3, x4, x5, x6) = U8_gga(x3, x6) 10.66/3.62 10.66/3.62 MERGESORT_IN_GA(x1, x2) = MERGESORT_IN_GA(x1) 10.66/3.62 10.66/3.62 U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x5) 10.66/3.62 10.66/3.62 U2_GA(x1, x2, x3, x4, x5, x6) = U2_GA(x2, x5, x6) 10.66/3.62 10.66/3.62 10.66/3.62 We have to consider all (P,R,Pi)-chains 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (40) PiDPToQDPProof (SOUND) 10.66/3.62 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (41) 10.66/3.62 Obligation: 10.66/3.62 Q DP problem: 10.66/3.62 The TRS P consists of the following rules: 10.66/3.62 10.66/3.62 U1_GA(E, F, split_out_gaa(L2, L1)) -> U2_GA(F, L1, mergesort_in_ga(.(E, L2))) 10.66/3.62 U2_GA(F, L1, mergesort_out_ga(X)) -> MERGESORT_IN_GA(.(F, L1)) 10.66/3.62 MERGESORT_IN_GA(.(E, .(F, U))) -> U1_GA(E, F, split_in_gaa(U)) 10.66/3.62 U1_GA(E, F, split_out_gaa(L2, L1)) -> MERGESORT_IN_GA(.(E, L2)) 10.66/3.62 10.66/3.62 The TRS R consists of the following rules: 10.66/3.62 10.66/3.62 mergesort_in_ga(.(E, [])) -> mergesort_out_ga(.(E, [])) 10.66/3.62 mergesort_in_ga(.(E, .(F, U))) -> U1_ga(E, F, split_in_gaa(U)) 10.66/3.62 split_in_gaa([]) -> split_out_gaa([], []) 10.66/3.62 split_in_gaa(.(E, U)) -> U9_gaa(E, split_in_gaa(U)) 10.66/3.62 U1_ga(E, F, split_out_gaa(L2, L1)) -> U2_ga(F, L1, mergesort_in_ga(.(E, L2))) 10.66/3.62 U9_gaa(E, split_out_gaa(W, V)) -> split_out_gaa(.(E, V), W) 10.66/3.62 U2_ga(F, L1, mergesort_out_ga(X)) -> U3_ga(X, mergesort_in_ga(.(F, L1))) 10.66/3.62 U3_ga(X, mergesort_out_ga(Z)) -> U4_ga(merge_in_gga(X, Z)) 10.66/3.62 U4_ga(merge_out_gga(V)) -> mergesort_out_ga(V) 10.66/3.62 merge_in_gga(X, []) -> merge_out_gga(X) 10.66/3.62 merge_in_gga([], X) -> merge_out_gga(X) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y)) -> U5_gga(A, X, B, Y, le_in_gg(A, B)) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y)) -> U7_gga(A, X, B, Y, gt_in_gg(A, B)) 10.66/3.62 U5_gga(A, X, B, Y, le_out_gg) -> U6_gga(A, merge_in_gga(X, .(B, Y))) 10.66/3.62 U7_gga(A, X, B, Y, gt_out_gg) -> U8_gga(B, merge_in_gga(.(A, X), Y)) 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg 10.66/3.62 le_in_gg(0, 0) -> le_out_gg 10.66/3.62 U6_gga(A, merge_out_gga(Z)) -> merge_out_gga(.(A, Z)) 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg 10.66/3.62 U8_gga(B, merge_out_gga(Z)) -> merge_out_gga(.(B, Z)) 10.66/3.62 U11_gg(le_out_gg) -> le_out_gg 10.66/3.62 U10_gg(gt_out_gg) -> gt_out_gg 10.66/3.62 10.66/3.62 The set Q consists of the following terms: 10.66/3.62 10.66/3.62 mergesort_in_ga(x0) 10.66/3.62 split_in_gaa(x0) 10.66/3.62 U1_ga(x0, x1, x2) 10.66/3.62 U9_gaa(x0, x1) 10.66/3.62 U2_ga(x0, x1, x2) 10.66/3.62 U3_ga(x0, x1) 10.66/3.62 U4_ga(x0) 10.66/3.62 merge_in_gga(x0, x1) 10.66/3.62 U5_gga(x0, x1, x2, x3, x4) 10.66/3.62 U7_gga(x0, x1, x2, x3, x4) 10.66/3.62 le_in_gg(x0, x1) 10.66/3.62 U6_gga(x0, x1) 10.66/3.62 gt_in_gg(x0, x1) 10.66/3.62 U8_gga(x0, x1) 10.66/3.62 U11_gg(x0) 10.66/3.62 U10_gg(x0) 10.66/3.62 10.66/3.62 We have to consider all (P,Q,R)-chains. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (42) QDPQMonotonicMRRProof (EQUIVALENT) 10.66/3.62 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 10.66/3.62 10.66/3.62 Strictly oriented dependency pairs: 10.66/3.62 10.66/3.62 U1_GA(E, F, split_out_gaa(L2, L1)) -> U2_GA(F, L1, mergesort_in_ga(.(E, L2))) 10.66/3.62 MERGESORT_IN_GA(.(E, .(F, U))) -> U1_GA(E, F, split_in_gaa(U)) 10.66/3.62 U1_GA(E, F, split_out_gaa(L2, L1)) -> MERGESORT_IN_GA(.(E, L2)) 10.66/3.62 10.66/3.62 10.66/3.62 Used ordering: Polynomial interpretation [POLO]: 10.66/3.62 10.66/3.62 POL(.(x_1, x_2)) = 2 + 2*x_2 10.66/3.62 POL(0) = 0 10.66/3.62 POL(MERGESORT_IN_GA(x_1)) = x_1 10.66/3.62 POL(U10_gg(x_1)) = 2 10.66/3.62 POL(U11_gg(x_1)) = 1 10.66/3.62 POL(U1_GA(x_1, x_2, x_3)) = 1 + x_3 10.66/3.62 POL(U1_ga(x_1, x_2, x_3)) = 0 10.66/3.62 POL(U2_GA(x_1, x_2, x_3)) = 2 + 2*x_2 10.66/3.62 POL(U2_ga(x_1, x_2, x_3)) = 0 10.66/3.62 POL(U3_ga(x_1, x_2)) = 0 10.66/3.62 POL(U4_ga(x_1)) = 0 10.66/3.62 POL(U5_gga(x_1, x_2, x_3, x_4, x_5)) = 0 10.66/3.62 POL(U6_gga(x_1, x_2)) = 0 10.66/3.62 POL(U7_gga(x_1, x_2, x_3, x_4, x_5)) = 0 10.66/3.62 POL(U8_gga(x_1, x_2)) = 0 10.66/3.62 POL(U9_gaa(x_1, x_2)) = 2 + 2*x_2 10.66/3.62 POL([]) = 0 10.66/3.62 POL(gt_in_gg(x_1, x_2)) = 2 + 2*x_1 10.66/3.62 POL(gt_out_gg) = 0 10.66/3.62 POL(le_in_gg(x_1, x_2)) = 2*x_2 10.66/3.62 POL(le_out_gg) = 0 10.66/3.62 POL(merge_in_gga(x_1, x_2)) = 2 10.66/3.62 POL(merge_out_gga(x_1)) = 0 10.66/3.62 POL(mergesort_in_ga(x_1)) = 0 10.66/3.62 POL(mergesort_out_ga(x_1)) = 0 10.66/3.62 POL(s(x_1)) = 1 10.66/3.62 POL(split_in_gaa(x_1)) = 2 + 2*x_1 10.66/3.62 POL(split_out_gaa(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 10.66/3.62 10.66/3.62 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (43) 10.66/3.62 Obligation: 10.66/3.62 Q DP problem: 10.66/3.62 The TRS P consists of the following rules: 10.66/3.62 10.66/3.62 U2_GA(F, L1, mergesort_out_ga(X)) -> MERGESORT_IN_GA(.(F, L1)) 10.66/3.62 10.66/3.62 The TRS R consists of the following rules: 10.66/3.62 10.66/3.62 mergesort_in_ga(.(E, [])) -> mergesort_out_ga(.(E, [])) 10.66/3.62 mergesort_in_ga(.(E, .(F, U))) -> U1_ga(E, F, split_in_gaa(U)) 10.66/3.62 split_in_gaa([]) -> split_out_gaa([], []) 10.66/3.62 split_in_gaa(.(E, U)) -> U9_gaa(E, split_in_gaa(U)) 10.66/3.62 U1_ga(E, F, split_out_gaa(L2, L1)) -> U2_ga(F, L1, mergesort_in_ga(.(E, L2))) 10.66/3.62 U9_gaa(E, split_out_gaa(W, V)) -> split_out_gaa(.(E, V), W) 10.66/3.62 U2_ga(F, L1, mergesort_out_ga(X)) -> U3_ga(X, mergesort_in_ga(.(F, L1))) 10.66/3.62 U3_ga(X, mergesort_out_ga(Z)) -> U4_ga(merge_in_gga(X, Z)) 10.66/3.62 U4_ga(merge_out_gga(V)) -> mergesort_out_ga(V) 10.66/3.62 merge_in_gga(X, []) -> merge_out_gga(X) 10.66/3.62 merge_in_gga([], X) -> merge_out_gga(X) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y)) -> U5_gga(A, X, B, Y, le_in_gg(A, B)) 10.66/3.62 merge_in_gga(.(A, X), .(B, Y)) -> U7_gga(A, X, B, Y, gt_in_gg(A, B)) 10.66/3.62 U5_gga(A, X, B, Y, le_out_gg) -> U6_gga(A, merge_in_gga(X, .(B, Y))) 10.66/3.62 U7_gga(A, X, B, Y, gt_out_gg) -> U8_gga(B, merge_in_gga(.(A, X), Y)) 10.66/3.62 le_in_gg(s(X), s(Y)) -> U11_gg(le_in_gg(X, Y)) 10.66/3.62 le_in_gg(0, s(Y)) -> le_out_gg 10.66/3.62 le_in_gg(0, 0) -> le_out_gg 10.66/3.62 U6_gga(A, merge_out_gga(Z)) -> merge_out_gga(.(A, Z)) 10.66/3.62 gt_in_gg(s(X), s(Y)) -> U10_gg(gt_in_gg(X, Y)) 10.66/3.62 gt_in_gg(s(X), 0) -> gt_out_gg 10.66/3.62 U8_gga(B, merge_out_gga(Z)) -> merge_out_gga(.(B, Z)) 10.66/3.62 U11_gg(le_out_gg) -> le_out_gg 10.66/3.62 U10_gg(gt_out_gg) -> gt_out_gg 10.66/3.62 10.66/3.62 The set Q consists of the following terms: 10.66/3.62 10.66/3.62 mergesort_in_ga(x0) 10.66/3.62 split_in_gaa(x0) 10.66/3.62 U1_ga(x0, x1, x2) 10.66/3.62 U9_gaa(x0, x1) 10.66/3.62 U2_ga(x0, x1, x2) 10.66/3.62 U3_ga(x0, x1) 10.66/3.62 U4_ga(x0) 10.66/3.62 merge_in_gga(x0, x1) 10.66/3.62 U5_gga(x0, x1, x2, x3, x4) 10.66/3.62 U7_gga(x0, x1, x2, x3, x4) 10.66/3.62 le_in_gg(x0, x1) 10.66/3.62 U6_gga(x0, x1) 10.66/3.62 gt_in_gg(x0, x1) 10.66/3.62 U8_gga(x0, x1) 10.66/3.62 U11_gg(x0) 10.66/3.62 U10_gg(x0) 10.66/3.62 10.66/3.62 We have to consider all (P,Q,R)-chains. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (44) DependencyGraphProof (EQUIVALENT) 10.66/3.62 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 10.66/3.62 ---------------------------------------- 10.66/3.62 10.66/3.62 (45) 10.66/3.62 TRUE 10.76/3.67 EOF