/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern ss(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, 9 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 1 ms] (18) QDP (19) UsableRulesReductionPairsProof [EQUIVALENT, 31 ms] (20) QDP (21) MRRProof [EQUIVALENT, 9 ms] (22) QDP (23) PisEmptyProof [EQUIVALENT, 0 ms] (24) YES (25) PiDP (26) UsableRulesProof [EQUIVALENT, 0 ms] (27) PiDP (28) PiDPToQDPProof [SOUND, 0 ms] (29) QDP (30) QDPSizeChangeProof [EQUIVALENT, 0 ms] (31) YES (32) PiDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) PiDP (35) PiDPToQDPProof [SOUND, 0 ms] (36) QDP (37) QDPSizeChangeProof [EQUIVALENT, 0 ms] (38) YES (39) PiDP (40) UsableRulesProof [EQUIVALENT, 0 ms] (41) PiDP (42) PiDPToQDPProof [SOUND, 0 ms] (43) QDP (44) MRRProof [EQUIVALENT, 0 ms] (45) QDP (46) PisEmptyProof [EQUIVALENT, 0 ms] (47) YES ---------------------------------------- (0) Obligation: Clauses: ss(Xs, Ys) :- ','(perm(Xs, Ys), ordered(Ys)). perm([], []). perm(Xs, .(X, Ys)) :- ','(app(X1s, .(X, X2s), Xs), ','(app(X1s, X2s, Zs), perm(Zs, Ys))). app([], X, X). app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). ordered([]). ordered(.(X1, [])). ordered(.(X, .(Y, Xs))) :- ','(less(X, s(Y)), ordered(.(Y, Xs))). less(0, s(X2)). less(s(X), s(Y)) :- less(X, Y). Query: ss(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: ss_in_2: (b,f) perm_in_2: (b,f) app_in_3: (f,f,b) (b,b,f) ordered_in_1: (b) less_in_2: (b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: ss_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, perm_in_ga(Xs, Ys)) perm_in_ga([], []) -> perm_out_ga([], []) perm_in_ga(Xs, .(X, Ys)) -> U3_ga(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) U3_ga(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_ga(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U4_ga(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_ga(Xs, X, Ys, perm_in_ga(Zs, Ys)) U5_ga(Xs, X, Ys, perm_out_ga(Zs, Ys)) -> perm_out_ga(Xs, .(X, Ys)) U1_ga(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_ga(Xs, Ys, ordered_in_g(Ys)) ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(.(X, .(Y, Xs))) -> U7_g(X, Y, Xs, less_in_gg(X, s(Y))) less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U7_g(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs))) U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs))) U2_ga(Xs, Ys, ordered_out_g(Ys)) -> ss_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: ss_in_ga(x1, x2) = ss_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x3) perm_in_ga(x1, x2) = perm_in_ga(x1) [] = [] perm_out_ga(x1, x2) = perm_out_ga(x2) U3_ga(x1, x2, x3, x4) = U3_ga(x4) app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) U2_ga(x1, x2, x3) = U2_ga(x2, x3) ordered_in_g(x1) = ordered_in_g(x1) ordered_out_g(x1) = ordered_out_g U7_g(x1, x2, x3, x4) = U7_g(x2, x3, x4) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) U8_g(x1, x2, x3, x4) = U8_g(x4) ss_out_ga(x1, x2) = ss_out_ga(x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: ss_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, perm_in_ga(Xs, Ys)) perm_in_ga([], []) -> perm_out_ga([], []) perm_in_ga(Xs, .(X, Ys)) -> U3_ga(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) U3_ga(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_ga(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U4_ga(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_ga(Xs, X, Ys, perm_in_ga(Zs, Ys)) U5_ga(Xs, X, Ys, perm_out_ga(Zs, Ys)) -> perm_out_ga(Xs, .(X, Ys)) U1_ga(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_ga(Xs, Ys, ordered_in_g(Ys)) ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(.(X, .(Y, Xs))) -> U7_g(X, Y, Xs, less_in_gg(X, s(Y))) less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U7_g(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs))) U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs))) U2_ga(Xs, Ys, ordered_out_g(Ys)) -> ss_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: ss_in_ga(x1, x2) = ss_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x3) perm_in_ga(x1, x2) = perm_in_ga(x1) [] = [] perm_out_ga(x1, x2) = perm_out_ga(x2) U3_ga(x1, x2, x3, x4) = U3_ga(x4) app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) U2_ga(x1, x2, x3) = U2_ga(x2, x3) ordered_in_g(x1) = ordered_in_g(x1) ordered_out_g(x1) = ordered_out_g U7_g(x1, x2, x3, x4) = U7_g(x2, x3, x4) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) U8_g(x1, x2, x3, x4) = U8_g(x4) ss_out_ga(x1, x2) = ss_out_ga(x2) ---------------------------------------- (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: SS_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, perm_in_ga(Xs, Ys)) SS_IN_GA(Xs, Ys) -> PERM_IN_GA(Xs, Ys) PERM_IN_GA(Xs, .(X, Ys)) -> U3_GA(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) PERM_IN_GA(Xs, .(X, Ys)) -> APP_IN_AAG(X1s, .(X, X2s), Xs) APP_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U6_AAG(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) APP_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAG(Xs, Ys, Zs) U3_GA(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_GA(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) U3_GA(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> APP_IN_GGA(X1s, X2s, Zs) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U6_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U4_GA(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_GA(Xs, X, Ys, perm_in_ga(Zs, Ys)) U4_GA(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> PERM_IN_GA(Zs, Ys) U1_GA(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_GA(Xs, Ys, ordered_in_g(Ys)) U1_GA(Xs, Ys, perm_out_ga(Xs, Ys)) -> ORDERED_IN_G(Ys) ORDERED_IN_G(.(X, .(Y, Xs))) -> U7_G(X, Y, Xs, less_in_gg(X, s(Y))) ORDERED_IN_G(.(X, .(Y, Xs))) -> LESS_IN_GG(X, s(Y)) LESS_IN_GG(s(X), s(Y)) -> U9_GG(X, Y, less_in_gg(X, Y)) LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) U7_G(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_G(X, Y, Xs, ordered_in_g(.(Y, Xs))) U7_G(X, Y, Xs, less_out_gg(X, s(Y))) -> ORDERED_IN_G(.(Y, Xs)) The TRS R consists of the following rules: ss_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, perm_in_ga(Xs, Ys)) perm_in_ga([], []) -> perm_out_ga([], []) perm_in_ga(Xs, .(X, Ys)) -> U3_ga(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) U3_ga(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_ga(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U4_ga(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_ga(Xs, X, Ys, perm_in_ga(Zs, Ys)) U5_ga(Xs, X, Ys, perm_out_ga(Zs, Ys)) -> perm_out_ga(Xs, .(X, Ys)) U1_ga(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_ga(Xs, Ys, ordered_in_g(Ys)) ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(.(X, .(Y, Xs))) -> U7_g(X, Y, Xs, less_in_gg(X, s(Y))) less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U7_g(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs))) U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs))) U2_ga(Xs, Ys, ordered_out_g(Ys)) -> ss_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: ss_in_ga(x1, x2) = ss_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x3) perm_in_ga(x1, x2) = perm_in_ga(x1) [] = [] perm_out_ga(x1, x2) = perm_out_ga(x2) U3_ga(x1, x2, x3, x4) = U3_ga(x4) app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) U2_ga(x1, x2, x3) = U2_ga(x2, x3) ordered_in_g(x1) = ordered_in_g(x1) ordered_out_g(x1) = ordered_out_g U7_g(x1, x2, x3, x4) = U7_g(x2, x3, x4) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) U8_g(x1, x2, x3, x4) = U8_g(x4) ss_out_ga(x1, x2) = ss_out_ga(x2) SS_IN_GA(x1, x2) = SS_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x3) PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) U3_GA(x1, x2, x3, x4) = U3_GA(x4) APP_IN_AAG(x1, x2, x3) = APP_IN_AAG(x3) U6_AAG(x1, x2, x3, x4, x5) = U6_AAG(x1, x5) U4_GA(x1, x2, x3, x4) = U4_GA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x1, x5) U5_GA(x1, x2, x3, x4) = U5_GA(x2, x4) U2_GA(x1, x2, x3) = U2_GA(x2, x3) ORDERED_IN_G(x1) = ORDERED_IN_G(x1) U7_G(x1, x2, x3, x4) = U7_G(x2, x3, x4) LESS_IN_GG(x1, x2) = LESS_IN_GG(x1, x2) U9_GG(x1, x2, x3) = U9_GG(x3) U8_G(x1, x2, x3, x4) = U8_G(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: SS_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, perm_in_ga(Xs, Ys)) SS_IN_GA(Xs, Ys) -> PERM_IN_GA(Xs, Ys) PERM_IN_GA(Xs, .(X, Ys)) -> U3_GA(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) PERM_IN_GA(Xs, .(X, Ys)) -> APP_IN_AAG(X1s, .(X, X2s), Xs) APP_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U6_AAG(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) APP_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAG(Xs, Ys, Zs) U3_GA(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_GA(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) U3_GA(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> APP_IN_GGA(X1s, X2s, Zs) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U6_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U4_GA(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_GA(Xs, X, Ys, perm_in_ga(Zs, Ys)) U4_GA(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> PERM_IN_GA(Zs, Ys) U1_GA(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_GA(Xs, Ys, ordered_in_g(Ys)) U1_GA(Xs, Ys, perm_out_ga(Xs, Ys)) -> ORDERED_IN_G(Ys) ORDERED_IN_G(.(X, .(Y, Xs))) -> U7_G(X, Y, Xs, less_in_gg(X, s(Y))) ORDERED_IN_G(.(X, .(Y, Xs))) -> LESS_IN_GG(X, s(Y)) LESS_IN_GG(s(X), s(Y)) -> U9_GG(X, Y, less_in_gg(X, Y)) LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) U7_G(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_G(X, Y, Xs, ordered_in_g(.(Y, Xs))) U7_G(X, Y, Xs, less_out_gg(X, s(Y))) -> ORDERED_IN_G(.(Y, Xs)) The TRS R consists of the following rules: ss_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, perm_in_ga(Xs, Ys)) perm_in_ga([], []) -> perm_out_ga([], []) perm_in_ga(Xs, .(X, Ys)) -> U3_ga(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) U3_ga(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_ga(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U4_ga(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_ga(Xs, X, Ys, perm_in_ga(Zs, Ys)) U5_ga(Xs, X, Ys, perm_out_ga(Zs, Ys)) -> perm_out_ga(Xs, .(X, Ys)) U1_ga(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_ga(Xs, Ys, ordered_in_g(Ys)) ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(.(X, .(Y, Xs))) -> U7_g(X, Y, Xs, less_in_gg(X, s(Y))) less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U7_g(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs))) U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs))) U2_ga(Xs, Ys, ordered_out_g(Ys)) -> ss_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: ss_in_ga(x1, x2) = ss_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x3) perm_in_ga(x1, x2) = perm_in_ga(x1) [] = [] perm_out_ga(x1, x2) = perm_out_ga(x2) U3_ga(x1, x2, x3, x4) = U3_ga(x4) app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) U2_ga(x1, x2, x3) = U2_ga(x2, x3) ordered_in_g(x1) = ordered_in_g(x1) ordered_out_g(x1) = ordered_out_g U7_g(x1, x2, x3, x4) = U7_g(x2, x3, x4) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) U8_g(x1, x2, x3, x4) = U8_g(x4) ss_out_ga(x1, x2) = ss_out_ga(x2) SS_IN_GA(x1, x2) = SS_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x3) PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) U3_GA(x1, x2, x3, x4) = U3_GA(x4) APP_IN_AAG(x1, x2, x3) = APP_IN_AAG(x3) U6_AAG(x1, x2, x3, x4, x5) = U6_AAG(x1, x5) U4_GA(x1, x2, x3, x4) = U4_GA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x1, x5) U5_GA(x1, x2, x3, x4) = U5_GA(x2, x4) U2_GA(x1, x2, x3) = U2_GA(x2, x3) ORDERED_IN_G(x1) = ORDERED_IN_G(x1) U7_G(x1, x2, x3, x4) = U7_G(x2, x3, x4) LESS_IN_GG(x1, x2) = LESS_IN_GG(x1, x2) U9_GG(x1, x2, x3) = U9_GG(x3) U8_G(x1, x2, x3, x4) = U8_G(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 12 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) The TRS R consists of the following rules: ss_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, perm_in_ga(Xs, Ys)) perm_in_ga([], []) -> perm_out_ga([], []) perm_in_ga(Xs, .(X, Ys)) -> U3_ga(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) U3_ga(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_ga(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U4_ga(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_ga(Xs, X, Ys, perm_in_ga(Zs, Ys)) U5_ga(Xs, X, Ys, perm_out_ga(Zs, Ys)) -> perm_out_ga(Xs, .(X, Ys)) U1_ga(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_ga(Xs, Ys, ordered_in_g(Ys)) ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(.(X, .(Y, Xs))) -> U7_g(X, Y, Xs, less_in_gg(X, s(Y))) less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U7_g(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs))) U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs))) U2_ga(Xs, Ys, ordered_out_g(Ys)) -> ss_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: ss_in_ga(x1, x2) = ss_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x3) perm_in_ga(x1, x2) = perm_in_ga(x1) [] = [] perm_out_ga(x1, x2) = perm_out_ga(x2) U3_ga(x1, x2, x3, x4) = U3_ga(x4) app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) U2_ga(x1, x2, x3) = U2_ga(x2, x3) ordered_in_g(x1) = ordered_in_g(x1) ordered_out_g(x1) = ordered_out_g U7_g(x1, x2, x3, x4) = U7_g(x2, x3, x4) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) U8_g(x1, x2, x3, x4) = U8_g(x4) ss_out_ga(x1, x2) = ss_out_ga(x2) LESS_IN_GG(x1, x2) = LESS_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: LESS_IN_GG(s(X), s(Y)) -> LESS_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: LESS_IN_GG(s(X), s(Y)) -> LESS_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: *LESS_IN_GG(s(X), s(Y)) -> LESS_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: U7_G(X, Y, Xs, less_out_gg(X, s(Y))) -> ORDERED_IN_G(.(Y, Xs)) ORDERED_IN_G(.(X, .(Y, Xs))) -> U7_G(X, Y, Xs, less_in_gg(X, s(Y))) The TRS R consists of the following rules: ss_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, perm_in_ga(Xs, Ys)) perm_in_ga([], []) -> perm_out_ga([], []) perm_in_ga(Xs, .(X, Ys)) -> U3_ga(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) U3_ga(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_ga(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U4_ga(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_ga(Xs, X, Ys, perm_in_ga(Zs, Ys)) U5_ga(Xs, X, Ys, perm_out_ga(Zs, Ys)) -> perm_out_ga(Xs, .(X, Ys)) U1_ga(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_ga(Xs, Ys, ordered_in_g(Ys)) ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(.(X, .(Y, Xs))) -> U7_g(X, Y, Xs, less_in_gg(X, s(Y))) less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U7_g(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs))) U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs))) U2_ga(Xs, Ys, ordered_out_g(Ys)) -> ss_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: ss_in_ga(x1, x2) = ss_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x3) perm_in_ga(x1, x2) = perm_in_ga(x1) [] = [] perm_out_ga(x1, x2) = perm_out_ga(x2) U3_ga(x1, x2, x3, x4) = U3_ga(x4) app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) U2_ga(x1, x2, x3) = U2_ga(x2, x3) ordered_in_g(x1) = ordered_in_g(x1) ordered_out_g(x1) = ordered_out_g U7_g(x1, x2, x3, x4) = U7_g(x2, x3, x4) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) U8_g(x1, x2, x3, x4) = U8_g(x4) ss_out_ga(x1, x2) = ss_out_ga(x2) ORDERED_IN_G(x1) = ORDERED_IN_G(x1) U7_G(x1, x2, x3, x4) = U7_G(x2, x3, x4) 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: U7_G(X, Y, Xs, less_out_gg(X, s(Y))) -> ORDERED_IN_G(.(Y, Xs)) ORDERED_IN_G(.(X, .(Y, Xs))) -> U7_G(X, Y, Xs, less_in_gg(X, s(Y))) The TRS R consists of the following rules: less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) ORDERED_IN_G(x1) = ORDERED_IN_G(x1) U7_G(x1, x2, x3, x4) = U7_G(x2, x3, x4) 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: U7_G(Y, Xs, less_out_gg) -> ORDERED_IN_G(.(Y, Xs)) ORDERED_IN_G(.(X, .(Y, Xs))) -> U7_G(Y, Xs, less_in_gg(X, s(Y))) The TRS R consists of the following rules: less_in_gg(0, s(X2)) -> less_out_gg less_in_gg(s(X), s(Y)) -> U9_gg(less_in_gg(X, Y)) U9_gg(less_out_gg) -> less_out_gg The set Q consists of the following terms: less_in_gg(x0, x1) U9_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: less_in_gg(0, s(X2)) -> less_out_gg Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2*x_1 + 2*x_2 POL(0) = 0 POL(ORDERED_IN_G(x_1)) = x_1 POL(U7_G(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(U9_gg(x_1)) = x_1 POL(less_in_gg(x_1, x_2)) = x_1 + x_2 POL(less_out_gg) = 0 POL(s(x_1)) = x_1 ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U7_G(Y, Xs, less_out_gg) -> ORDERED_IN_G(.(Y, Xs)) ORDERED_IN_G(.(X, .(Y, Xs))) -> U7_G(Y, Xs, less_in_gg(X, s(Y))) The TRS R consists of the following rules: less_in_gg(s(X), s(Y)) -> U9_gg(less_in_gg(X, Y)) U9_gg(less_out_gg) -> less_out_gg The set Q consists of the following terms: less_in_gg(x0, x1) U9_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: U7_G(Y, Xs, less_out_gg) -> ORDERED_IN_G(.(Y, Xs)) ORDERED_IN_G(.(X, .(Y, Xs))) -> U7_G(Y, Xs, less_in_gg(X, s(Y))) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2*x_1 + 2*x_2 POL(ORDERED_IN_G(x_1)) = 2 + x_1 POL(U7_G(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(U9_gg(x_1)) = x_1 POL(less_in_gg(x_1, x_2)) = x_1 + x_2 POL(less_out_gg) = 2 POL(s(x_1)) = x_1 ---------------------------------------- (22) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: less_in_gg(s(X), s(Y)) -> U9_gg(less_in_gg(X, Y)) U9_gg(less_out_gg) -> less_out_gg The set Q consists of the following terms: less_in_gg(x0, x1) U9_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (23) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (24) YES ---------------------------------------- (25) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) The TRS R consists of the following rules: ss_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, perm_in_ga(Xs, Ys)) perm_in_ga([], []) -> perm_out_ga([], []) perm_in_ga(Xs, .(X, Ys)) -> U3_ga(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) U3_ga(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_ga(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U4_ga(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_ga(Xs, X, Ys, perm_in_ga(Zs, Ys)) U5_ga(Xs, X, Ys, perm_out_ga(Zs, Ys)) -> perm_out_ga(Xs, .(X, Ys)) U1_ga(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_ga(Xs, Ys, ordered_in_g(Ys)) ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(.(X, .(Y, Xs))) -> U7_g(X, Y, Xs, less_in_gg(X, s(Y))) less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U7_g(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs))) U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs))) U2_ga(Xs, Ys, ordered_out_g(Ys)) -> ss_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: ss_in_ga(x1, x2) = ss_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x3) perm_in_ga(x1, x2) = perm_in_ga(x1) [] = [] perm_out_ga(x1, x2) = perm_out_ga(x2) U3_ga(x1, x2, x3, x4) = U3_ga(x4) app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) U2_ga(x1, x2, x3) = U2_ga(x2, x3) ordered_in_g(x1) = ordered_in_g(x1) ordered_out_g(x1) = ordered_out_g U7_g(x1, x2, x3, x4) = U7_g(x2, x3, x4) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) U8_g(x1, x2, x3, x4) = U8_g(x4) ss_out_ga(x1, x2) = ss_out_ga(x2) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (26) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (27) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (28) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(X, Xs), Ys) -> APP_IN_GGA(Xs, Ys) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (30) 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: *APP_IN_GGA(.(X, Xs), Ys) -> APP_IN_GGA(Xs, Ys) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (31) YES ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAG(Xs, Ys, Zs) The TRS R consists of the following rules: ss_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, perm_in_ga(Xs, Ys)) perm_in_ga([], []) -> perm_out_ga([], []) perm_in_ga(Xs, .(X, Ys)) -> U3_ga(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) U3_ga(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_ga(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U4_ga(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_ga(Xs, X, Ys, perm_in_ga(Zs, Ys)) U5_ga(Xs, X, Ys, perm_out_ga(Zs, Ys)) -> perm_out_ga(Xs, .(X, Ys)) U1_ga(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_ga(Xs, Ys, ordered_in_g(Ys)) ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(.(X, .(Y, Xs))) -> U7_g(X, Y, Xs, less_in_gg(X, s(Y))) less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U7_g(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs))) U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs))) U2_ga(Xs, Ys, ordered_out_g(Ys)) -> ss_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: ss_in_ga(x1, x2) = ss_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x3) perm_in_ga(x1, x2) = perm_in_ga(x1) [] = [] perm_out_ga(x1, x2) = perm_out_ga(x2) U3_ga(x1, x2, x3, x4) = U3_ga(x4) app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) U2_ga(x1, x2, x3) = U2_ga(x2, x3) ordered_in_g(x1) = ordered_in_g(x1) ordered_out_g(x1) = ordered_out_g U7_g(x1, x2, x3, x4) = U7_g(x2, x3, x4) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) U8_g(x1, x2, x3, x4) = U8_g(x4) ss_out_ga(x1, x2) = ss_out_ga(x2) APP_IN_AAG(x1, x2, x3) = APP_IN_AAG(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAG(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APP_IN_AAG(x1, x2, x3) = APP_IN_AAG(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_AAG(.(X, Zs)) -> APP_IN_AAG(Zs) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) 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: *APP_IN_AAG(.(X, Zs)) -> APP_IN_AAG(Zs) The graph contains the following edges 1 > 1 ---------------------------------------- (38) YES ---------------------------------------- (39) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_GA(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_GA(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) U4_GA(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> PERM_IN_GA(Zs, Ys) PERM_IN_GA(Xs, .(X, Ys)) -> U3_GA(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) The TRS R consists of the following rules: ss_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, perm_in_ga(Xs, Ys)) perm_in_ga([], []) -> perm_out_ga([], []) perm_in_ga(Xs, .(X, Ys)) -> U3_ga(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) U3_ga(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_ga(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U4_ga(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> U5_ga(Xs, X, Ys, perm_in_ga(Zs, Ys)) U5_ga(Xs, X, Ys, perm_out_ga(Zs, Ys)) -> perm_out_ga(Xs, .(X, Ys)) U1_ga(Xs, Ys, perm_out_ga(Xs, Ys)) -> U2_ga(Xs, Ys, ordered_in_g(Ys)) ordered_in_g([]) -> ordered_out_g([]) ordered_in_g(.(X1, [])) -> ordered_out_g(.(X1, [])) ordered_in_g(.(X, .(Y, Xs))) -> U7_g(X, Y, Xs, less_in_gg(X, s(Y))) less_in_gg(0, s(X2)) -> less_out_gg(0, s(X2)) less_in_gg(s(X), s(Y)) -> U9_gg(X, Y, less_in_gg(X, Y)) U9_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U7_g(X, Y, Xs, less_out_gg(X, s(Y))) -> U8_g(X, Y, Xs, ordered_in_g(.(Y, Xs))) U8_g(X, Y, Xs, ordered_out_g(.(Y, Xs))) -> ordered_out_g(.(X, .(Y, Xs))) U2_ga(Xs, Ys, ordered_out_g(Ys)) -> ss_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: ss_in_ga(x1, x2) = ss_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x3) perm_in_ga(x1, x2) = perm_in_ga(x1) [] = [] perm_out_ga(x1, x2) = perm_out_ga(x2) U3_ga(x1, x2, x3, x4) = U3_ga(x4) app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) U4_ga(x1, x2, x3, x4) = U4_ga(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) U5_ga(x1, x2, x3, x4) = U5_ga(x2, x4) U2_ga(x1, x2, x3) = U2_ga(x2, x3) ordered_in_g(x1) = ordered_in_g(x1) ordered_out_g(x1) = ordered_out_g U7_g(x1, x2, x3, x4) = U7_g(x2, x3, x4) less_in_gg(x1, x2) = less_in_gg(x1, x2) 0 = 0 s(x1) = s(x1) less_out_gg(x1, x2) = less_out_gg U9_gg(x1, x2, x3) = U9_gg(x3) U8_g(x1, x2, x3, x4) = U8_g(x4) ss_out_ga(x1, x2) = ss_out_ga(x2) PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) U3_GA(x1, x2, x3, x4) = U3_GA(x4) U4_GA(x1, x2, x3, x4) = U4_GA(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (40) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (41) Obligation: Pi DP problem: The TRS P consists of the following rules: U3_GA(Xs, X, Ys, app_out_aag(X1s, .(X, X2s), Xs)) -> U4_GA(Xs, X, Ys, app_in_gga(X1s, X2s, Zs)) U4_GA(Xs, X, Ys, app_out_gga(X1s, X2s, Zs)) -> PERM_IN_GA(Zs, Ys) PERM_IN_GA(Xs, .(X, Ys)) -> U3_GA(Xs, X, Ys, app_in_aag(X1s, .(X, X2s), Xs)) The TRS R consists of the following rules: app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U6_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_aag([], X, X) -> app_out_aag([], X, X) app_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U6_aag(X, Xs, Ys, Zs, app_in_aag(Xs, Ys, Zs)) U6_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U6_aag(X, Xs, Ys, Zs, app_out_aag(Xs, Ys, Zs)) -> app_out_aag(.(X, Xs), Ys, .(X, Zs)) The argument filtering Pi contains the following mapping: [] = [] app_in_aag(x1, x2, x3) = app_in_aag(x3) app_out_aag(x1, x2, x3) = app_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U6_aag(x1, x2, x3, x4, x5) = U6_aag(x1, x5) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x5) PERM_IN_GA(x1, x2) = PERM_IN_GA(x1) U3_GA(x1, x2, x3, x4) = U3_GA(x4) U4_GA(x1, x2, x3, x4) = U4_GA(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (42) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: U3_GA(app_out_aag(X1s, .(X, X2s))) -> U4_GA(X, app_in_gga(X1s, X2s)) U4_GA(X, app_out_gga(Zs)) -> PERM_IN_GA(Zs) PERM_IN_GA(Xs) -> U3_GA(app_in_aag(Xs)) The TRS R consists of the following rules: app_in_gga([], X) -> app_out_gga(X) app_in_gga(.(X, Xs), Ys) -> U6_gga(X, app_in_gga(Xs, Ys)) app_in_aag(X) -> app_out_aag([], X) app_in_aag(.(X, Zs)) -> U6_aag(X, app_in_aag(Zs)) U6_gga(X, app_out_gga(Zs)) -> app_out_gga(.(X, Zs)) U6_aag(X, app_out_aag(Xs, Ys)) -> app_out_aag(.(X, Xs), Ys) The set Q consists of the following terms: app_in_gga(x0, x1) app_in_aag(x0) U6_gga(x0, x1) U6_aag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (44) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: U3_GA(app_out_aag(X1s, .(X, X2s))) -> U4_GA(X, app_in_gga(X1s, X2s)) U4_GA(X, app_out_gga(Zs)) -> PERM_IN_GA(Zs) PERM_IN_GA(Xs) -> U3_GA(app_in_aag(Xs)) Strictly oriented rules of the TRS R: app_in_gga([], X) -> app_out_gga(X) app_in_gga(.(X, Xs), Ys) -> U6_gga(X, app_in_gga(Xs, Ys)) app_in_aag(X) -> app_out_aag([], X) app_in_aag(.(X, Zs)) -> U6_aag(X, app_in_aag(Zs)) U6_gga(X, app_out_gga(Zs)) -> app_out_gga(.(X, Zs)) U6_aag(X, app_out_aag(Xs, Ys)) -> app_out_aag(.(X, Xs), Ys) Used ordering: Knuth-Bendix order [KBO] with precedence:PERM_IN_GA_1 > U4_GA_2 > app_in_aag_1 > ._2 > app_in_gga_2 > [] > U3_GA_1 > U6_aag_2 > app_out_aag_2 > U6_gga_2 > app_out_gga_1 and weight map: []=3 app_out_gga_1=3 app_in_aag_1=3 U3_GA_1=1 PERM_IN_GA_1=4 app_in_gga_2=0 ._2=1 U6_gga_2=1 app_out_aag_2=0 U6_aag_2=1 U4_GA_2=1 The variable weight is 1 ---------------------------------------- (45) Obligation: Q DP problem: P is empty. R is empty. The set Q consists of the following terms: app_in_gga(x0, x1) app_in_aag(x0) U6_gga(x0, x1) U6_aag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (46) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (47) YES