YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern merge(g,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, 17 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 [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 1 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) QDPOrderProof [EQUIVALENT, 24 ms] (27) QDP (28) DependencyGraphProof [EQUIVALENT, 0 ms] (29) TRUE ---------------------------------------- (0) Obligation: Clauses: merge([], X, X). merge(X, [], X). merge(.(X, Xs), .(Y, Ys), .(X, Zs)) :- ','(leq(X, Y), merge(Xs, .(Y, Ys), Zs)). merge(.(X, Xs), .(Y, Ys), .(Y, Zs)) :- ','(less(Y, X), merge(.(X, Xs), Ys, Zs)). less(0, s(0)). less(s(X), s(Y)) :- less(X, Y). leq(0, 0). leq(0, s(0)). leq(s(X), s(Y)) :- leq(X, Y). Query: merge(g,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: merge_in_3: (b,b,f) leq_in_2: (b,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: merge_in_gga([], X, X) -> merge_out_gga([], X, X) merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) merge_in_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_gga(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) leq_in_gg(0, 0) -> leq_out_gg(0, 0) leq_in_gg(0, s(0)) -> leq_out_gg(0, s(0)) leq_in_gg(s(X), s(Y)) -> U6_gg(X, Y, leq_in_gg(X, Y)) U6_gg(X, Y, leq_out_gg(X, Y)) -> leq_out_gg(s(X), s(Y)) U1_gga(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> U2_gga(X, Xs, Y, Ys, Zs, merge_in_gga(Xs, .(Y, Ys), Zs)) merge_in_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_gga(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) less_in_gg(0, s(0)) -> less_out_gg(0, s(0)) less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y)) U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U3_gga(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> U4_gga(X, Xs, Y, Ys, Zs, merge_in_gga(.(X, Xs), Ys, Zs)) U4_gga(X, Xs, Y, Ys, Zs, merge_out_gga(.(X, Xs), Ys, Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) U2_gga(X, Xs, Y, Ys, Zs, merge_out_gga(Xs, .(Y, Ys), Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) The argument filtering Pi contains the following mapping: merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) [] = [] merge_out_gga(x1, x2, x3) = merge_out_gga(x3) .(x1, x2) = .(x1, x2) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x1, x2, x3, x4, x6) leq_in_gg(x1, x2) = leq_in_gg(x1, x2) 0 = 0 leq_out_gg(x1, x2) = leq_out_gg s(x1) = s(x1) U6_gg(x1, x2, x3) = U6_gg(x3) U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x1, x6) U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x1, x2, x3, x4, x6) less_in_gg(x1, x2) = less_in_gg(x1, x2) less_out_gg(x1, x2) = less_out_gg U5_gg(x1, x2, x3) = U5_gg(x3) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x3, x6) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: merge_in_gga([], X, X) -> merge_out_gga([], X, X) merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) merge_in_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_gga(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) leq_in_gg(0, 0) -> leq_out_gg(0, 0) leq_in_gg(0, s(0)) -> leq_out_gg(0, s(0)) leq_in_gg(s(X), s(Y)) -> U6_gg(X, Y, leq_in_gg(X, Y)) U6_gg(X, Y, leq_out_gg(X, Y)) -> leq_out_gg(s(X), s(Y)) U1_gga(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> U2_gga(X, Xs, Y, Ys, Zs, merge_in_gga(Xs, .(Y, Ys), Zs)) merge_in_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_gga(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) less_in_gg(0, s(0)) -> less_out_gg(0, s(0)) less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y)) U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U3_gga(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> U4_gga(X, Xs, Y, Ys, Zs, merge_in_gga(.(X, Xs), Ys, Zs)) U4_gga(X, Xs, Y, Ys, Zs, merge_out_gga(.(X, Xs), Ys, Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) U2_gga(X, Xs, Y, Ys, Zs, merge_out_gga(Xs, .(Y, Ys), Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) The argument filtering Pi contains the following mapping: merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) [] = [] merge_out_gga(x1, x2, x3) = merge_out_gga(x3) .(x1, x2) = .(x1, x2) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x1, x2, x3, x4, x6) leq_in_gg(x1, x2) = leq_in_gg(x1, x2) 0 = 0 leq_out_gg(x1, x2) = leq_out_gg s(x1) = s(x1) U6_gg(x1, x2, x3) = U6_gg(x3) U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x1, x6) U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x1, x2, x3, x4, x6) less_in_gg(x1, x2) = less_in_gg(x1, x2) less_out_gg(x1, x2) = less_out_gg U5_gg(x1, x2, x3) = U5_gg(x3) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x3, x6) ---------------------------------------- (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: MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_GGA(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(X, Zs)) -> LEQ_IN_GG(X, Y) LEQ_IN_GG(s(X), s(Y)) -> U6_GG(X, Y, leq_in_gg(X, Y)) LEQ_IN_GG(s(X), s(Y)) -> LEQ_IN_GG(X, Y) U1_GGA(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> U2_GGA(X, Xs, Y, Ys, Zs, merge_in_gga(Xs, .(Y, Ys), Zs)) U1_GGA(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> MERGE_IN_GGA(Xs, .(Y, Ys), Zs) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_GGA(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> LESS_IN_GG(Y, X) LESS_IN_GG(s(X), s(Y)) -> U5_GG(X, Y, less_in_gg(X, Y)) LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) U3_GGA(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> U4_GGA(X, Xs, Y, Ys, Zs, merge_in_gga(.(X, Xs), Ys, Zs)) U3_GGA(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> MERGE_IN_GGA(.(X, Xs), Ys, Zs) The TRS R consists of the following rules: merge_in_gga([], X, X) -> merge_out_gga([], X, X) merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) merge_in_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_gga(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) leq_in_gg(0, 0) -> leq_out_gg(0, 0) leq_in_gg(0, s(0)) -> leq_out_gg(0, s(0)) leq_in_gg(s(X), s(Y)) -> U6_gg(X, Y, leq_in_gg(X, Y)) U6_gg(X, Y, leq_out_gg(X, Y)) -> leq_out_gg(s(X), s(Y)) U1_gga(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> U2_gga(X, Xs, Y, Ys, Zs, merge_in_gga(Xs, .(Y, Ys), Zs)) merge_in_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_gga(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) less_in_gg(0, s(0)) -> less_out_gg(0, s(0)) less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y)) U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U3_gga(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> U4_gga(X, Xs, Y, Ys, Zs, merge_in_gga(.(X, Xs), Ys, Zs)) U4_gga(X, Xs, Y, Ys, Zs, merge_out_gga(.(X, Xs), Ys, Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) U2_gga(X, Xs, Y, Ys, Zs, merge_out_gga(Xs, .(Y, Ys), Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) The argument filtering Pi contains the following mapping: merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) [] = [] merge_out_gga(x1, x2, x3) = merge_out_gga(x3) .(x1, x2) = .(x1, x2) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x1, x2, x3, x4, x6) leq_in_gg(x1, x2) = leq_in_gg(x1, x2) 0 = 0 leq_out_gg(x1, x2) = leq_out_gg s(x1) = s(x1) U6_gg(x1, x2, x3) = U6_gg(x3) U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x1, x6) U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x1, x2, x3, x4, x6) less_in_gg(x1, x2) = less_in_gg(x1, x2) less_out_gg(x1, x2) = less_out_gg U5_gg(x1, x2, x3) = U5_gg(x3) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x3, x6) MERGE_IN_GGA(x1, x2, x3) = MERGE_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5, x6) = U1_GGA(x1, x2, x3, x4, x6) LEQ_IN_GG(x1, x2) = LEQ_IN_GG(x1, x2) U6_GG(x1, x2, x3) = U6_GG(x3) U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x1, x6) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) LESS_IN_GG(x1, x2) = LESS_IN_GG(x1, x2) U5_GG(x1, x2, x3) = U5_GG(x3) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x3, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_GGA(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(X, Zs)) -> LEQ_IN_GG(X, Y) LEQ_IN_GG(s(X), s(Y)) -> U6_GG(X, Y, leq_in_gg(X, Y)) LEQ_IN_GG(s(X), s(Y)) -> LEQ_IN_GG(X, Y) U1_GGA(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> U2_GGA(X, Xs, Y, Ys, Zs, merge_in_gga(Xs, .(Y, Ys), Zs)) U1_GGA(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> MERGE_IN_GGA(Xs, .(Y, Ys), Zs) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_GGA(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> LESS_IN_GG(Y, X) LESS_IN_GG(s(X), s(Y)) -> U5_GG(X, Y, less_in_gg(X, Y)) LESS_IN_GG(s(X), s(Y)) -> LESS_IN_GG(X, Y) U3_GGA(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> U4_GGA(X, Xs, Y, Ys, Zs, merge_in_gga(.(X, Xs), Ys, Zs)) U3_GGA(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> MERGE_IN_GGA(.(X, Xs), Ys, Zs) The TRS R consists of the following rules: merge_in_gga([], X, X) -> merge_out_gga([], X, X) merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) merge_in_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_gga(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) leq_in_gg(0, 0) -> leq_out_gg(0, 0) leq_in_gg(0, s(0)) -> leq_out_gg(0, s(0)) leq_in_gg(s(X), s(Y)) -> U6_gg(X, Y, leq_in_gg(X, Y)) U6_gg(X, Y, leq_out_gg(X, Y)) -> leq_out_gg(s(X), s(Y)) U1_gga(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> U2_gga(X, Xs, Y, Ys, Zs, merge_in_gga(Xs, .(Y, Ys), Zs)) merge_in_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_gga(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) less_in_gg(0, s(0)) -> less_out_gg(0, s(0)) less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y)) U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U3_gga(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> U4_gga(X, Xs, Y, Ys, Zs, merge_in_gga(.(X, Xs), Ys, Zs)) U4_gga(X, Xs, Y, Ys, Zs, merge_out_gga(.(X, Xs), Ys, Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) U2_gga(X, Xs, Y, Ys, Zs, merge_out_gga(Xs, .(Y, Ys), Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) The argument filtering Pi contains the following mapping: merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) [] = [] merge_out_gga(x1, x2, x3) = merge_out_gga(x3) .(x1, x2) = .(x1, x2) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x1, x2, x3, x4, x6) leq_in_gg(x1, x2) = leq_in_gg(x1, x2) 0 = 0 leq_out_gg(x1, x2) = leq_out_gg s(x1) = s(x1) U6_gg(x1, x2, x3) = U6_gg(x3) U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x1, x6) U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x1, x2, x3, x4, x6) less_in_gg(x1, x2) = less_in_gg(x1, x2) less_out_gg(x1, x2) = less_out_gg U5_gg(x1, x2, x3) = U5_gg(x3) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x3, x6) MERGE_IN_GGA(x1, x2, x3) = MERGE_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5, x6) = U1_GGA(x1, x2, x3, x4, x6) LEQ_IN_GG(x1, x2) = LEQ_IN_GG(x1, x2) U6_GG(x1, x2, x3) = U6_GG(x3) U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x1, x6) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) LESS_IN_GG(x1, x2) = LESS_IN_GG(x1, x2) U5_GG(x1, x2, x3) = U5_GG(x3) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x3, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 6 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: merge_in_gga([], X, X) -> merge_out_gga([], X, X) merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) merge_in_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_gga(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) leq_in_gg(0, 0) -> leq_out_gg(0, 0) leq_in_gg(0, s(0)) -> leq_out_gg(0, s(0)) leq_in_gg(s(X), s(Y)) -> U6_gg(X, Y, leq_in_gg(X, Y)) U6_gg(X, Y, leq_out_gg(X, Y)) -> leq_out_gg(s(X), s(Y)) U1_gga(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> U2_gga(X, Xs, Y, Ys, Zs, merge_in_gga(Xs, .(Y, Ys), Zs)) merge_in_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_gga(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) less_in_gg(0, s(0)) -> less_out_gg(0, s(0)) less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y)) U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U3_gga(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> U4_gga(X, Xs, Y, Ys, Zs, merge_in_gga(.(X, Xs), Ys, Zs)) U4_gga(X, Xs, Y, Ys, Zs, merge_out_gga(.(X, Xs), Ys, Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) U2_gga(X, Xs, Y, Ys, Zs, merge_out_gga(Xs, .(Y, Ys), Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) The argument filtering Pi contains the following mapping: merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) [] = [] merge_out_gga(x1, x2, x3) = merge_out_gga(x3) .(x1, x2) = .(x1, x2) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x1, x2, x3, x4, x6) leq_in_gg(x1, x2) = leq_in_gg(x1, x2) 0 = 0 leq_out_gg(x1, x2) = leq_out_gg s(x1) = s(x1) U6_gg(x1, x2, x3) = U6_gg(x3) U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x1, x6) U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x1, x2, x3, x4, x6) less_in_gg(x1, x2) = less_in_gg(x1, x2) less_out_gg(x1, x2) = less_out_gg U5_gg(x1, x2, x3) = U5_gg(x3) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x3, x6) 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: LEQ_IN_GG(s(X), s(Y)) -> LEQ_IN_GG(X, Y) The TRS R consists of the following rules: merge_in_gga([], X, X) -> merge_out_gga([], X, X) merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) merge_in_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_gga(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) leq_in_gg(0, 0) -> leq_out_gg(0, 0) leq_in_gg(0, s(0)) -> leq_out_gg(0, s(0)) leq_in_gg(s(X), s(Y)) -> U6_gg(X, Y, leq_in_gg(X, Y)) U6_gg(X, Y, leq_out_gg(X, Y)) -> leq_out_gg(s(X), s(Y)) U1_gga(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> U2_gga(X, Xs, Y, Ys, Zs, merge_in_gga(Xs, .(Y, Ys), Zs)) merge_in_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_gga(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) less_in_gg(0, s(0)) -> less_out_gg(0, s(0)) less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y)) U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U3_gga(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> U4_gga(X, Xs, Y, Ys, Zs, merge_in_gga(.(X, Xs), Ys, Zs)) U4_gga(X, Xs, Y, Ys, Zs, merge_out_gga(.(X, Xs), Ys, Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) U2_gga(X, Xs, Y, Ys, Zs, merge_out_gga(Xs, .(Y, Ys), Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) The argument filtering Pi contains the following mapping: merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) [] = [] merge_out_gga(x1, x2, x3) = merge_out_gga(x3) .(x1, x2) = .(x1, x2) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x1, x2, x3, x4, x6) leq_in_gg(x1, x2) = leq_in_gg(x1, x2) 0 = 0 leq_out_gg(x1, x2) = leq_out_gg s(x1) = s(x1) U6_gg(x1, x2, x3) = U6_gg(x3) U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x1, x6) U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x1, x2, x3, x4, x6) less_in_gg(x1, x2) = less_in_gg(x1, x2) less_out_gg(x1, x2) = less_out_gg U5_gg(x1, x2, x3) = U5_gg(x3) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x3, x6) LEQ_IN_GG(x1, x2) = LEQ_IN_GG(x1, x2) 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: LEQ_IN_GG(s(X), s(Y)) -> LEQ_IN_GG(X, Y) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (EQUIVALENT) 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: LEQ_IN_GG(s(X), s(Y)) -> LEQ_IN_GG(X, Y) R is empty. Q is empty. 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: *LEQ_IN_GG(s(X), s(Y)) -> LEQ_IN_GG(X, Y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GGA(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> MERGE_IN_GGA(Xs, .(Y, Ys), Zs) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_GGA(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_GGA(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) U3_GGA(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> MERGE_IN_GGA(.(X, Xs), Ys, Zs) The TRS R consists of the following rules: merge_in_gga([], X, X) -> merge_out_gga([], X, X) merge_in_gga(X, [], X) -> merge_out_gga(X, [], X) merge_in_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_gga(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) leq_in_gg(0, 0) -> leq_out_gg(0, 0) leq_in_gg(0, s(0)) -> leq_out_gg(0, s(0)) leq_in_gg(s(X), s(Y)) -> U6_gg(X, Y, leq_in_gg(X, Y)) U6_gg(X, Y, leq_out_gg(X, Y)) -> leq_out_gg(s(X), s(Y)) U1_gga(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> U2_gga(X, Xs, Y, Ys, Zs, merge_in_gga(Xs, .(Y, Ys), Zs)) merge_in_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_gga(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) less_in_gg(0, s(0)) -> less_out_gg(0, s(0)) less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y)) U5_gg(X, Y, less_out_gg(X, Y)) -> less_out_gg(s(X), s(Y)) U3_gga(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> U4_gga(X, Xs, Y, Ys, Zs, merge_in_gga(.(X, Xs), Ys, Zs)) U4_gga(X, Xs, Y, Ys, Zs, merge_out_gga(.(X, Xs), Ys, Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(Y, Zs)) U2_gga(X, Xs, Y, Ys, Zs, merge_out_gga(Xs, .(Y, Ys), Zs)) -> merge_out_gga(.(X, Xs), .(Y, Ys), .(X, Zs)) The argument filtering Pi contains the following mapping: merge_in_gga(x1, x2, x3) = merge_in_gga(x1, x2) [] = [] merge_out_gga(x1, x2, x3) = merge_out_gga(x3) .(x1, x2) = .(x1, x2) U1_gga(x1, x2, x3, x4, x5, x6) = U1_gga(x1, x2, x3, x4, x6) leq_in_gg(x1, x2) = leq_in_gg(x1, x2) 0 = 0 leq_out_gg(x1, x2) = leq_out_gg s(x1) = s(x1) U6_gg(x1, x2, x3) = U6_gg(x3) U2_gga(x1, x2, x3, x4, x5, x6) = U2_gga(x1, x6) U3_gga(x1, x2, x3, x4, x5, x6) = U3_gga(x1, x2, x3, x4, x6) less_in_gg(x1, x2) = less_in_gg(x1, x2) less_out_gg(x1, x2) = less_out_gg U5_gg(x1, x2, x3) = U5_gg(x3) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x3, x6) MERGE_IN_GGA(x1, x2, x3) = MERGE_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5, x6) = U1_GGA(x1, x2, x3, x4, x6) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) 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: U1_GGA(X, Xs, Y, Ys, Zs, leq_out_gg(X, Y)) -> MERGE_IN_GGA(Xs, .(Y, Ys), Zs) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(X, Zs)) -> U1_GGA(X, Xs, Y, Ys, Zs, leq_in_gg(X, Y)) MERGE_IN_GGA(.(X, Xs), .(Y, Ys), .(Y, Zs)) -> U3_GGA(X, Xs, Y, Ys, Zs, less_in_gg(Y, X)) U3_GGA(X, Xs, Y, Ys, Zs, less_out_gg(Y, X)) -> MERGE_IN_GGA(.(X, Xs), Ys, Zs) The TRS R consists of the following rules: leq_in_gg(0, 0) -> leq_out_gg(0, 0) leq_in_gg(0, s(0)) -> leq_out_gg(0, s(0)) leq_in_gg(s(X), s(Y)) -> U6_gg(X, Y, leq_in_gg(X, Y)) less_in_gg(0, s(0)) -> less_out_gg(0, s(0)) less_in_gg(s(X), s(Y)) -> U5_gg(X, Y, less_in_gg(X, Y)) U6_gg(X, Y, leq_out_gg(X, Y)) -> leq_out_gg(s(X), s(Y)) U5_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) leq_in_gg(x1, x2) = leq_in_gg(x1, x2) 0 = 0 leq_out_gg(x1, x2) = leq_out_gg s(x1) = s(x1) U6_gg(x1, x2, x3) = U6_gg(x3) less_in_gg(x1, x2) = less_in_gg(x1, x2) less_out_gg(x1, x2) = less_out_gg U5_gg(x1, x2, x3) = U5_gg(x3) MERGE_IN_GGA(x1, x2, x3) = MERGE_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5, x6) = U1_GGA(x1, x2, x3, x4, x6) U3_GGA(x1, x2, x3, x4, x5, x6) = U3_GGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) 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: U1_GGA(X, Xs, Y, Ys, leq_out_gg) -> MERGE_IN_GGA(Xs, .(Y, Ys)) MERGE_IN_GGA(.(X, Xs), .(Y, Ys)) -> U1_GGA(X, Xs, Y, Ys, leq_in_gg(X, Y)) MERGE_IN_GGA(.(X, Xs), .(Y, Ys)) -> U3_GGA(X, Xs, Y, Ys, less_in_gg(Y, X)) U3_GGA(X, Xs, Y, Ys, less_out_gg) -> MERGE_IN_GGA(.(X, Xs), Ys) The TRS R consists of the following rules: leq_in_gg(0, 0) -> leq_out_gg leq_in_gg(0, s(0)) -> leq_out_gg leq_in_gg(s(X), s(Y)) -> U6_gg(leq_in_gg(X, Y)) less_in_gg(0, s(0)) -> less_out_gg less_in_gg(s(X), s(Y)) -> U5_gg(less_in_gg(X, Y)) U6_gg(leq_out_gg) -> leq_out_gg U5_gg(less_out_gg) -> less_out_gg The set Q consists of the following terms: leq_in_gg(x0, x1) less_in_gg(x0, x1) U6_gg(x0) U5_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MERGE_IN_GGA(.(X, Xs), .(Y, Ys)) -> U1_GGA(X, Xs, Y, Ys, leq_in_gg(X, Y)) MERGE_IN_GGA(.(X, Xs), .(Y, Ys)) -> U3_GGA(X, Xs, Y, Ys, less_in_gg(Y, X)) U3_GGA(X, Xs, Y, Ys, less_out_gg) -> MERGE_IN_GGA(.(X, Xs), Ys) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U1_GGA_5(x_1, ..., x_5) ) = max{0, 2x_2 + 2x_3 + 2x_4 + 2x_5 - 1} POL( leq_in_gg_2(x_1, x_2) ) = x_1 POL( 0 ) = 2 POL( leq_out_gg ) = 1 POL( s_1(x_1) ) = 2x_1 + 2 POL( U6_gg_1(x_1) ) = x_1 + 1 POL( U3_GGA_5(x_1, ..., x_5) ) = 2x_1 + 2x_2 + 2x_4 + 2x_5 + 2 POL( less_in_gg_2(x_1, x_2) ) = x_1 POL( less_out_gg ) = 2 POL( U5_gg_1(x_1) ) = x_1 + 2 POL( MERGE_IN_GGA_2(x_1, x_2) ) = max{0, 2x_1 + 2x_2 - 1} POL( ._2(x_1, x_2) ) = x_1 + x_2 + 1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: leq_in_gg(0, 0) -> leq_out_gg leq_in_gg(0, s(0)) -> leq_out_gg leq_in_gg(s(X), s(Y)) -> U6_gg(leq_in_gg(X, Y)) less_in_gg(0, s(0)) -> less_out_gg less_in_gg(s(X), s(Y)) -> U5_gg(less_in_gg(X, Y)) U6_gg(leq_out_gg) -> leq_out_gg U5_gg(less_out_gg) -> less_out_gg ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GGA(X, Xs, Y, Ys, leq_out_gg) -> MERGE_IN_GGA(Xs, .(Y, Ys)) The TRS R consists of the following rules: leq_in_gg(0, 0) -> leq_out_gg leq_in_gg(0, s(0)) -> leq_out_gg leq_in_gg(s(X), s(Y)) -> U6_gg(leq_in_gg(X, Y)) less_in_gg(0, s(0)) -> less_out_gg less_in_gg(s(X), s(Y)) -> U5_gg(less_in_gg(X, Y)) U6_gg(leq_out_gg) -> leq_out_gg U5_gg(less_out_gg) -> less_out_gg The set Q consists of the following terms: leq_in_gg(x0, x1) less_in_gg(x0, x1) U6_gg(x0) U5_gg(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (29) TRUE