YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern minsort(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 6 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 14 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [EQUIVALENT, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) PiDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) PiDP (31) PiDPToQDPProof [EQUIVALENT, 0 ms] (32) QDP (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] (34) YES (35) PiDP (36) UsableRulesProof [EQUIVALENT, 0 ms] (37) PiDP (38) PiDPToQDPProof [SOUND, 0 ms] (39) QDP (40) QDPSizeChangeProof [EQUIVALENT, 0 ms] (41) YES (42) PiDP (43) UsableRulesProof [EQUIVALENT, 0 ms] (44) PiDP (45) PiDPToQDPProof [SOUND, 2 ms] (46) QDP (47) QDPOrderProof [EQUIVALENT, 38 ms] (48) QDP (49) DependencyGraphProof [EQUIVALENT, 0 ms] (50) TRUE ---------------------------------------- (0) Obligation: Clauses: minsort([], []). minsort(L, .(X, L1)) :- ','(min1(X, L), ','(remove(X, L, L2), minsort(L2, L1))). min1(M, .(X, L)) :- min2(X, M, L). min2(X, X, []). min2(X, A, .(M, L)) :- ','(min(X, M, B), min2(B, A, L)). min(X, Y, X) :- le(X, Y). min(X, Y, Y) :- gt(X, Y). remove(N, .(N, L), L). remove(N, .(M, L), .(M, L1)) :- ','(notEq(N, M), remove(N, L, L1)). gt(s(X), s(Y)) :- gt(X, Y). gt(s(X), 0). le(s(X), s(Y)) :- le(X, Y). le(0, s(Y)). le(0, 0). notEq(s(X), s(Y)) :- notEq(X, Y). notEq(s(X), 0). notEq(0, s(X)). Query: minsort(g,a) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: minsort_in_2: (b,f) min1_in_2: (f,b) min2_in_3: (b,f,b) min_in_3: (b,b,f) le_in_2: (b,b) gt_in_2: (b,b) remove_in_3: (b,b,f) notEq_in_2: (b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: MINSORT_IN_GA(L, .(X, L1)) -> U1_GA(L, X, L1, min1_in_ag(X, L)) MINSORT_IN_GA(L, .(X, L1)) -> MIN1_IN_AG(X, L) MIN1_IN_AG(M, .(X, L)) -> U4_AG(M, X, L, min2_in_gag(X, M, L)) MIN1_IN_AG(M, .(X, L)) -> MIN2_IN_GAG(X, M, L) MIN2_IN_GAG(X, A, .(M, L)) -> U5_GAG(X, A, M, L, min_in_gga(X, M, B)) MIN2_IN_GAG(X, A, .(M, L)) -> MIN_IN_GGA(X, M, B) MIN_IN_GGA(X, Y, X) -> U7_GGA(X, Y, le_in_gg(X, Y)) MIN_IN_GGA(X, Y, X) -> LE_IN_GG(X, Y) LE_IN_GG(s(X), s(Y)) -> U12_GG(X, Y, le_in_gg(X, Y)) LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) MIN_IN_GGA(X, Y, Y) -> U8_GGA(X, Y, gt_in_gg(X, Y)) MIN_IN_GGA(X, Y, Y) -> GT_IN_GG(X, Y) GT_IN_GG(s(X), s(Y)) -> U11_GG(X, Y, gt_in_gg(X, Y)) GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) U5_GAG(X, A, M, L, min_out_gga(X, M, B)) -> U6_GAG(X, A, M, L, min2_in_gag(B, A, L)) U5_GAG(X, A, M, L, min_out_gga(X, M, B)) -> MIN2_IN_GAG(B, A, L) U1_GA(L, X, L1, min1_out_ag(X, L)) -> U2_GA(L, X, L1, remove_in_gga(X, L, L2)) U1_GA(L, X, L1, min1_out_ag(X, L)) -> REMOVE_IN_GGA(X, L, L2) REMOVE_IN_GGA(N, .(M, L), .(M, L1)) -> U9_GGA(N, M, L, L1, notEq_in_gg(N, M)) REMOVE_IN_GGA(N, .(M, L), .(M, L1)) -> NOTEQ_IN_GG(N, M) NOTEQ_IN_GG(s(X), s(Y)) -> U13_GG(X, Y, notEq_in_gg(X, Y)) NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) U9_GGA(N, M, L, L1, notEq_out_gg(N, M)) -> U10_GGA(N, M, L, L1, remove_in_gga(N, L, L1)) U9_GGA(N, M, L, L1, notEq_out_gg(N, M)) -> REMOVE_IN_GGA(N, L, L1) U2_GA(L, X, L1, remove_out_gga(X, L, L2)) -> U3_GA(L, X, L1, minsort_in_ga(L2, L1)) U2_GA(L, X, L1, remove_out_gga(X, L, L2)) -> MINSORT_IN_GA(L2, L1) The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) MINSORT_IN_GA(x1, x2) = MINSORT_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) MIN1_IN_AG(x1, x2) = MIN1_IN_AG(x2) U4_AG(x1, x2, x3, x4) = U4_AG(x4) MIN2_IN_GAG(x1, x2, x3) = MIN2_IN_GAG(x1, x3) U5_GAG(x1, x2, x3, x4, x5) = U5_GAG(x4, x5) MIN_IN_GGA(x1, x2, x3) = MIN_IN_GGA(x1, x2) U7_GGA(x1, x2, x3) = U7_GGA(x1, x3) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) U12_GG(x1, x2, x3) = U12_GG(x3) U8_GGA(x1, x2, x3) = U8_GGA(x2, x3) GT_IN_GG(x1, x2) = GT_IN_GG(x1, x2) U11_GG(x1, x2, x3) = U11_GG(x3) U6_GAG(x1, x2, x3, x4, x5) = U6_GAG(x5) U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) REMOVE_IN_GGA(x1, x2, x3) = REMOVE_IN_GGA(x1, x2) U9_GGA(x1, x2, x3, x4, x5) = U9_GGA(x1, x2, x3, x5) NOTEQ_IN_GG(x1, x2) = NOTEQ_IN_GG(x1, x2) U13_GG(x1, x2, x3) = U13_GG(x3) U10_GGA(x1, x2, x3, x4, x5) = U10_GGA(x2, x5) U3_GA(x1, x2, x3, x4) = U3_GA(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: MINSORT_IN_GA(L, .(X, L1)) -> U1_GA(L, X, L1, min1_in_ag(X, L)) MINSORT_IN_GA(L, .(X, L1)) -> MIN1_IN_AG(X, L) MIN1_IN_AG(M, .(X, L)) -> U4_AG(M, X, L, min2_in_gag(X, M, L)) MIN1_IN_AG(M, .(X, L)) -> MIN2_IN_GAG(X, M, L) MIN2_IN_GAG(X, A, .(M, L)) -> U5_GAG(X, A, M, L, min_in_gga(X, M, B)) MIN2_IN_GAG(X, A, .(M, L)) -> MIN_IN_GGA(X, M, B) MIN_IN_GGA(X, Y, X) -> U7_GGA(X, Y, le_in_gg(X, Y)) MIN_IN_GGA(X, Y, X) -> LE_IN_GG(X, Y) LE_IN_GG(s(X), s(Y)) -> U12_GG(X, Y, le_in_gg(X, Y)) LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) MIN_IN_GGA(X, Y, Y) -> U8_GGA(X, Y, gt_in_gg(X, Y)) MIN_IN_GGA(X, Y, Y) -> GT_IN_GG(X, Y) GT_IN_GG(s(X), s(Y)) -> U11_GG(X, Y, gt_in_gg(X, Y)) GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) U5_GAG(X, A, M, L, min_out_gga(X, M, B)) -> U6_GAG(X, A, M, L, min2_in_gag(B, A, L)) U5_GAG(X, A, M, L, min_out_gga(X, M, B)) -> MIN2_IN_GAG(B, A, L) U1_GA(L, X, L1, min1_out_ag(X, L)) -> U2_GA(L, X, L1, remove_in_gga(X, L, L2)) U1_GA(L, X, L1, min1_out_ag(X, L)) -> REMOVE_IN_GGA(X, L, L2) REMOVE_IN_GGA(N, .(M, L), .(M, L1)) -> U9_GGA(N, M, L, L1, notEq_in_gg(N, M)) REMOVE_IN_GGA(N, .(M, L), .(M, L1)) -> NOTEQ_IN_GG(N, M) NOTEQ_IN_GG(s(X), s(Y)) -> U13_GG(X, Y, notEq_in_gg(X, Y)) NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) U9_GGA(N, M, L, L1, notEq_out_gg(N, M)) -> U10_GGA(N, M, L, L1, remove_in_gga(N, L, L1)) U9_GGA(N, M, L, L1, notEq_out_gg(N, M)) -> REMOVE_IN_GGA(N, L, L1) U2_GA(L, X, L1, remove_out_gga(X, L, L2)) -> U3_GA(L, X, L1, minsort_in_ga(L2, L1)) U2_GA(L, X, L1, remove_out_gga(X, L, L2)) -> MINSORT_IN_GA(L2, L1) The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) MINSORT_IN_GA(x1, x2) = MINSORT_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) MIN1_IN_AG(x1, x2) = MIN1_IN_AG(x2) U4_AG(x1, x2, x3, x4) = U4_AG(x4) MIN2_IN_GAG(x1, x2, x3) = MIN2_IN_GAG(x1, x3) U5_GAG(x1, x2, x3, x4, x5) = U5_GAG(x4, x5) MIN_IN_GGA(x1, x2, x3) = MIN_IN_GGA(x1, x2) U7_GGA(x1, x2, x3) = U7_GGA(x1, x3) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) U12_GG(x1, x2, x3) = U12_GG(x3) U8_GGA(x1, x2, x3) = U8_GGA(x2, x3) GT_IN_GG(x1, x2) = GT_IN_GG(x1, x2) U11_GG(x1, x2, x3) = U11_GG(x3) U6_GAG(x1, x2, x3, x4, x5) = U6_GAG(x5) U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) REMOVE_IN_GGA(x1, x2, x3) = REMOVE_IN_GGA(x1, x2) U9_GGA(x1, x2, x3, x4, x5) = U9_GGA(x1, x2, x3, x5) NOTEQ_IN_GG(x1, x2) = NOTEQ_IN_GG(x1, x2) U13_GG(x1, x2, x3) = U13_GG(x3) U10_GGA(x1, x2, x3, x4, x5) = U10_GGA(x2, x5) U3_GA(x1, x2, x3, x4) = U3_GA(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 6 SCCs with 16 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) NOTEQ_IN_GG(x1, x2) = NOTEQ_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *NOTEQ_IN_GG(s(X), s(Y)) -> NOTEQ_IN_GG(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: U9_GGA(N, M, L, L1, notEq_out_gg(N, M)) -> REMOVE_IN_GGA(N, L, L1) REMOVE_IN_GGA(N, .(M, L), .(M, L1)) -> U9_GGA(N, M, L, L1, notEq_in_gg(N, M)) The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) REMOVE_IN_GGA(x1, x2, x3) = REMOVE_IN_GGA(x1, x2) U9_GGA(x1, x2, x3, x4, x5) = U9_GGA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: U9_GGA(N, M, L, L1, notEq_out_gg(N, M)) -> REMOVE_IN_GGA(N, L, L1) REMOVE_IN_GGA(N, .(M, L), .(M, L1)) -> U9_GGA(N, M, L, L1, notEq_in_gg(N, M)) The TRS R consists of the following rules: notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) s(x1) = s(x1) 0 = 0 notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg REMOVE_IN_GGA(x1, x2, x3) = REMOVE_IN_GGA(x1, x2) U9_GGA(x1, x2, x3, x4, x5) = U9_GGA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: U9_GGA(N, M, L, notEq_out_gg) -> REMOVE_IN_GGA(N, L) REMOVE_IN_GGA(N, .(M, L)) -> U9_GGA(N, M, L, notEq_in_gg(N, M)) The TRS R consists of the following rules: notEq_in_gg(s(X), s(Y)) -> U13_gg(notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg notEq_in_gg(0, s(X)) -> notEq_out_gg U13_gg(notEq_out_gg) -> notEq_out_gg The set Q consists of the following terms: notEq_in_gg(x0, x1) U13_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *REMOVE_IN_GGA(N, .(M, L)) -> U9_GGA(N, M, L, notEq_in_gg(N, M)) The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3 *U9_GGA(N, M, L, notEq_out_gg) -> REMOVE_IN_GGA(N, L) The graph contains the following edges 1 >= 1, 3 >= 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) GT_IN_GG(x1, x2) = GT_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *GT_IN_GG(s(X), s(Y)) -> GT_IN_GG(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Pi DP problem: The TRS P consists of the following rules: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) LE_IN_GG(x1, x2) = LE_IN_GG(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LE_IN_GG(s(X), s(Y)) -> LE_IN_GG(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (34) YES ---------------------------------------- (35) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_GAG(X, A, M, L, min_out_gga(X, M, B)) -> MIN2_IN_GAG(B, A, L) MIN2_IN_GAG(X, A, .(M, L)) -> U5_GAG(X, A, M, L, min_in_gga(X, M, B)) The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) MIN2_IN_GAG(x1, x2, x3) = MIN2_IN_GAG(x1, x3) U5_GAG(x1, x2, x3, x4, x5) = U5_GAG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (36) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (37) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_GAG(X, A, M, L, min_out_gga(X, M, B)) -> MIN2_IN_GAG(B, A, L) MIN2_IN_GAG(X, A, .(M, L)) -> U5_GAG(X, A, M, L, min_in_gga(X, M, B)) The TRS R consists of the following rules: min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg MIN2_IN_GAG(x1, x2, x3) = MIN2_IN_GAG(x1, x3) U5_GAG(x1, x2, x3, x4, x5) = U5_GAG(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (38) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: U5_GAG(L, min_out_gga(B)) -> MIN2_IN_GAG(B, L) MIN2_IN_GAG(X, .(M, L)) -> U5_GAG(L, min_in_gga(X, M)) The TRS R consists of the following rules: min_in_gga(X, Y) -> U7_gga(X, le_in_gg(X, Y)) min_in_gga(X, Y) -> U8_gga(Y, gt_in_gg(X, Y)) U7_gga(X, le_out_gg) -> min_out_gga(X) U8_gga(Y, gt_out_gg) -> min_out_gga(Y) le_in_gg(s(X), s(Y)) -> U12_gg(le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg le_in_gg(0, 0) -> le_out_gg gt_in_gg(s(X), s(Y)) -> U11_gg(gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg U12_gg(le_out_gg) -> le_out_gg U11_gg(gt_out_gg) -> gt_out_gg The set Q consists of the following terms: min_in_gga(x0, x1) U7_gga(x0, x1) U8_gga(x0, x1) le_in_gg(x0, x1) gt_in_gg(x0, x1) U12_gg(x0) U11_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (40) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MIN2_IN_GAG(X, .(M, L)) -> U5_GAG(L, min_in_gga(X, M)) The graph contains the following edges 2 > 1 *U5_GAG(L, min_out_gga(B)) -> MIN2_IN_GAG(B, L) The graph contains the following edges 2 > 1, 1 >= 2 ---------------------------------------- (41) YES ---------------------------------------- (42) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GA(L, X, L1, min1_out_ag(X, L)) -> U2_GA(L, X, L1, remove_in_gga(X, L, L2)) U2_GA(L, X, L1, remove_out_gga(X, L, L2)) -> MINSORT_IN_GA(L2, L1) MINSORT_IN_GA(L, .(X, L1)) -> U1_GA(L, X, L1, min1_in_ag(X, L)) The TRS R consists of the following rules: minsort_in_ga([], []) -> minsort_out_ga([], []) minsort_in_ga(L, .(X, L1)) -> U1_ga(L, X, L1, min1_in_ag(X, L)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) U1_ga(L, X, L1, min1_out_ag(X, L)) -> U2_ga(L, X, L1, remove_in_gga(X, L, L2)) remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) U2_ga(L, X, L1, remove_out_gga(X, L, L2)) -> U3_ga(L, X, L1, minsort_in_ga(L2, L1)) U3_ga(L, X, L1, minsort_out_ga(L2, L1)) -> minsort_out_ga(L, .(X, L1)) The argument filtering Pi contains the following mapping: minsort_in_ga(x1, x2) = minsort_in_ga(x1) [] = [] minsort_out_ga(x1, x2) = minsort_out_ga(x2) U1_ga(x1, x2, x3, x4) = U1_ga(x1, x4) min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) U2_ga(x1, x2, x3, x4) = U2_ga(x2, x4) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) U3_ga(x1, x2, x3, x4) = U3_ga(x2, x4) MINSORT_IN_GA(x1, x2) = MINSORT_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (43) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (44) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GA(L, X, L1, min1_out_ag(X, L)) -> U2_GA(L, X, L1, remove_in_gga(X, L, L2)) U2_GA(L, X, L1, remove_out_gga(X, L, L2)) -> MINSORT_IN_GA(L2, L1) MINSORT_IN_GA(L, .(X, L1)) -> U1_GA(L, X, L1, min1_in_ag(X, L)) The TRS R consists of the following rules: remove_in_gga(N, .(N, L), L) -> remove_out_gga(N, .(N, L), L) remove_in_gga(N, .(M, L), .(M, L1)) -> U9_gga(N, M, L, L1, notEq_in_gg(N, M)) min1_in_ag(M, .(X, L)) -> U4_ag(M, X, L, min2_in_gag(X, M, L)) U9_gga(N, M, L, L1, notEq_out_gg(N, M)) -> U10_gga(N, M, L, L1, remove_in_gga(N, L, L1)) U4_ag(M, X, L, min2_out_gag(X, M, L)) -> min1_out_ag(M, .(X, L)) notEq_in_gg(s(X), s(Y)) -> U13_gg(X, Y, notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg(s(X), 0) notEq_in_gg(0, s(X)) -> notEq_out_gg(0, s(X)) U10_gga(N, M, L, L1, remove_out_gga(N, L, L1)) -> remove_out_gga(N, .(M, L), .(M, L1)) min2_in_gag(X, X, []) -> min2_out_gag(X, X, []) min2_in_gag(X, A, .(M, L)) -> U5_gag(X, A, M, L, min_in_gga(X, M, B)) U13_gg(X, Y, notEq_out_gg(X, Y)) -> notEq_out_gg(s(X), s(Y)) U5_gag(X, A, M, L, min_out_gga(X, M, B)) -> U6_gag(X, A, M, L, min2_in_gag(B, A, L)) min_in_gga(X, Y, X) -> U7_gga(X, Y, le_in_gg(X, Y)) min_in_gga(X, Y, Y) -> U8_gga(X, Y, gt_in_gg(X, Y)) U6_gag(X, A, M, L, min2_out_gag(B, A, L)) -> min2_out_gag(X, A, .(M, L)) U7_gga(X, Y, le_out_gg(X, Y)) -> min_out_gga(X, Y, X) U8_gga(X, Y, gt_out_gg(X, Y)) -> min_out_gga(X, Y, Y) le_in_gg(s(X), s(Y)) -> U12_gg(X, Y, le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg(0, s(Y)) le_in_gg(0, 0) -> le_out_gg(0, 0) gt_in_gg(s(X), s(Y)) -> U11_gg(X, Y, gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg(s(X), 0) U12_gg(X, Y, le_out_gg(X, Y)) -> le_out_gg(s(X), s(Y)) U11_gg(X, Y, gt_out_gg(X, Y)) -> gt_out_gg(s(X), s(Y)) The argument filtering Pi contains the following mapping: [] = [] min1_in_ag(x1, x2) = min1_in_ag(x2) .(x1, x2) = .(x1, x2) U4_ag(x1, x2, x3, x4) = U4_ag(x4) min2_in_gag(x1, x2, x3) = min2_in_gag(x1, x3) min2_out_gag(x1, x2, x3) = min2_out_gag(x2) U5_gag(x1, x2, x3, x4, x5) = U5_gag(x4, x5) min_in_gga(x1, x2, x3) = min_in_gga(x1, x2) U7_gga(x1, x2, x3) = U7_gga(x1, x3) le_in_gg(x1, x2) = le_in_gg(x1, x2) s(x1) = s(x1) U12_gg(x1, x2, x3) = U12_gg(x3) 0 = 0 le_out_gg(x1, x2) = le_out_gg min_out_gga(x1, x2, x3) = min_out_gga(x3) U8_gga(x1, x2, x3) = U8_gga(x2, x3) gt_in_gg(x1, x2) = gt_in_gg(x1, x2) U11_gg(x1, x2, x3) = U11_gg(x3) gt_out_gg(x1, x2) = gt_out_gg U6_gag(x1, x2, x3, x4, x5) = U6_gag(x5) min1_out_ag(x1, x2) = min1_out_ag(x1) remove_in_gga(x1, x2, x3) = remove_in_gga(x1, x2) remove_out_gga(x1, x2, x3) = remove_out_gga(x3) U9_gga(x1, x2, x3, x4, x5) = U9_gga(x1, x2, x3, x5) notEq_in_gg(x1, x2) = notEq_in_gg(x1, x2) U13_gg(x1, x2, x3) = U13_gg(x3) notEq_out_gg(x1, x2) = notEq_out_gg U10_gga(x1, x2, x3, x4, x5) = U10_gga(x2, x5) MINSORT_IN_GA(x1, x2) = MINSORT_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (45) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GA(L, min1_out_ag(X)) -> U2_GA(X, remove_in_gga(X, L)) U2_GA(X, remove_out_gga(L2)) -> MINSORT_IN_GA(L2) MINSORT_IN_GA(L) -> U1_GA(L, min1_in_ag(L)) The TRS R consists of the following rules: remove_in_gga(N, .(N, L)) -> remove_out_gga(L) remove_in_gga(N, .(M, L)) -> U9_gga(N, M, L, notEq_in_gg(N, M)) min1_in_ag(.(X, L)) -> U4_ag(min2_in_gag(X, L)) U9_gga(N, M, L, notEq_out_gg) -> U10_gga(M, remove_in_gga(N, L)) U4_ag(min2_out_gag(M)) -> min1_out_ag(M) notEq_in_gg(s(X), s(Y)) -> U13_gg(notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg notEq_in_gg(0, s(X)) -> notEq_out_gg U10_gga(M, remove_out_gga(L1)) -> remove_out_gga(.(M, L1)) min2_in_gag(X, []) -> min2_out_gag(X) min2_in_gag(X, .(M, L)) -> U5_gag(L, min_in_gga(X, M)) U13_gg(notEq_out_gg) -> notEq_out_gg U5_gag(L, min_out_gga(B)) -> U6_gag(min2_in_gag(B, L)) min_in_gga(X, Y) -> U7_gga(X, le_in_gg(X, Y)) min_in_gga(X, Y) -> U8_gga(Y, gt_in_gg(X, Y)) U6_gag(min2_out_gag(A)) -> min2_out_gag(A) U7_gga(X, le_out_gg) -> min_out_gga(X) U8_gga(Y, gt_out_gg) -> min_out_gga(Y) le_in_gg(s(X), s(Y)) -> U12_gg(le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg le_in_gg(0, 0) -> le_out_gg gt_in_gg(s(X), s(Y)) -> U11_gg(gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg U12_gg(le_out_gg) -> le_out_gg U11_gg(gt_out_gg) -> gt_out_gg The set Q consists of the following terms: remove_in_gga(x0, x1) min1_in_ag(x0) U9_gga(x0, x1, x2, x3) U4_ag(x0) notEq_in_gg(x0, x1) U10_gga(x0, x1) min2_in_gag(x0, x1) U13_gg(x0) U5_gag(x0, x1) min_in_gga(x0, x1) U6_gag(x0) U7_gga(x0, x1) U8_gga(x0, x1) le_in_gg(x0, x1) gt_in_gg(x0, x1) U12_gg(x0) U11_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (47) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U1_GA(L, min1_out_ag(X)) -> U2_GA(X, remove_in_gga(X, L)) MINSORT_IN_GA(L) -> U1_GA(L, min1_in_ag(L)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U2_GA_2(x_1, x_2) ) = max{0, 2x_2 - 2} POL( remove_in_gga_2(x_1, x_2) ) = x_2 POL( ._2(x_1, x_2) ) = 2x_2 + 2 POL( remove_out_gga_1(x_1) ) = 2x_1 + 2 POL( U9_gga_4(x_1, ..., x_4) ) = 2x_3 + 2 POL( notEq_in_gg_2(x_1, x_2) ) = x_1 + 2x_2 POL( U1_GA_2(x_1, x_2) ) = 2x_1 + 1 POL( min1_in_ag_1(x_1) ) = x_1 + 2 POL( U4_ag_1(x_1) ) = max{0, 2x_1 - 2} POL( min2_in_gag_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( s_1(x_1) ) = 2x_1 POL( U13_gg_1(x_1) ) = max{0, -2} POL( 0 ) = 0 POL( notEq_out_gg ) = 2 POL( U10_gga_2(x_1, x_2) ) = 2x_2 + 2 POL( [] ) = 0 POL( min2_out_gag_1(x_1) ) = x_1 POL( U5_gag_2(x_1, x_2) ) = 2x_1 + 2 POL( min_in_gga_2(x_1, x_2) ) = x_2 + 1 POL( min1_out_ag_1(x_1) ) = 2x_1 POL( U7_gga_2(x_1, x_2) ) = max{0, x_1 + 2x_2 - 2} POL( le_in_gg_2(x_1, x_2) ) = 2x_1 + x_2 + 2 POL( U8_gga_2(x_1, x_2) ) = max{0, x_2 - 2} POL( gt_in_gg_2(x_1, x_2) ) = 2x_1 POL( min_out_gga_1(x_1) ) = 1 POL( U6_gag_1(x_1) ) = max{0, -2} POL( U12_gg_1(x_1) ) = 2 POL( le_out_gg ) = 0 POL( U11_gg_1(x_1) ) = max{0, -2} POL( gt_out_gg ) = 2 POL( MINSORT_IN_GA_1(x_1) ) = 2x_1 + 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: remove_in_gga(N, .(N, L)) -> remove_out_gga(L) remove_in_gga(N, .(M, L)) -> U9_gga(N, M, L, notEq_in_gg(N, M)) U9_gga(N, M, L, notEq_out_gg) -> U10_gga(M, remove_in_gga(N, L)) U10_gga(M, remove_out_gga(L1)) -> remove_out_gga(.(M, L1)) ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GA(X, remove_out_gga(L2)) -> MINSORT_IN_GA(L2) The TRS R consists of the following rules: remove_in_gga(N, .(N, L)) -> remove_out_gga(L) remove_in_gga(N, .(M, L)) -> U9_gga(N, M, L, notEq_in_gg(N, M)) min1_in_ag(.(X, L)) -> U4_ag(min2_in_gag(X, L)) U9_gga(N, M, L, notEq_out_gg) -> U10_gga(M, remove_in_gga(N, L)) U4_ag(min2_out_gag(M)) -> min1_out_ag(M) notEq_in_gg(s(X), s(Y)) -> U13_gg(notEq_in_gg(X, Y)) notEq_in_gg(s(X), 0) -> notEq_out_gg notEq_in_gg(0, s(X)) -> notEq_out_gg U10_gga(M, remove_out_gga(L1)) -> remove_out_gga(.(M, L1)) min2_in_gag(X, []) -> min2_out_gag(X) min2_in_gag(X, .(M, L)) -> U5_gag(L, min_in_gga(X, M)) U13_gg(notEq_out_gg) -> notEq_out_gg U5_gag(L, min_out_gga(B)) -> U6_gag(min2_in_gag(B, L)) min_in_gga(X, Y) -> U7_gga(X, le_in_gg(X, Y)) min_in_gga(X, Y) -> U8_gga(Y, gt_in_gg(X, Y)) U6_gag(min2_out_gag(A)) -> min2_out_gag(A) U7_gga(X, le_out_gg) -> min_out_gga(X) U8_gga(Y, gt_out_gg) -> min_out_gga(Y) le_in_gg(s(X), s(Y)) -> U12_gg(le_in_gg(X, Y)) le_in_gg(0, s(Y)) -> le_out_gg le_in_gg(0, 0) -> le_out_gg gt_in_gg(s(X), s(Y)) -> U11_gg(gt_in_gg(X, Y)) gt_in_gg(s(X), 0) -> gt_out_gg U12_gg(le_out_gg) -> le_out_gg U11_gg(gt_out_gg) -> gt_out_gg The set Q consists of the following terms: remove_in_gga(x0, x1) min1_in_ag(x0) U9_gga(x0, x1, x2, x3) U4_ag(x0) notEq_in_gg(x0, x1) U10_gga(x0, x1) min2_in_gag(x0, x1) U13_gg(x0) U5_gag(x0, x1) min_in_gga(x0, x1) U6_gag(x0) U7_gga(x0, x1) U8_gga(x0, x1) le_in_gg(x0, x1) gt_in_gg(x0, x1) U12_gg(x0) U11_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (49) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (50) TRUE