/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern rev(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, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) PiDPToQDPProof [SOUND, 0 ms] (16) QDP (17) QDPOrderProof [EQUIVALENT, 227 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) TRUE ---------------------------------------- (0) Obligation: Clauses: rev([], []). rev(.(X, XS), .(Y, YS)) :- ','(rev1(X, XS, Y), rev2(X, XS, YS)). rev1(X, [], X). rev1(X, .(Y, YS), Z) :- rev1(Y, YS, Z). rev2(X, [], []). rev2(X, .(Y, YS), ZS) :- ','(rev2(Y, YS, US), ','(rev(US, VS), rev(.(X, VS), ZS))). Query: rev(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: rev_in_2: (b,f) rev1_in_3: (b,b,f) rev2_in_3: (b,b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: rev_in_ga([], []) -> rev_out_ga([], []) rev_in_ga(.(X, XS), .(Y, YS)) -> U1_ga(X, XS, Y, YS, rev1_in_gga(X, XS, Y)) rev1_in_gga(X, [], X) -> rev1_out_gga(X, [], X) rev1_in_gga(X, .(Y, YS), Z) -> U3_gga(X, Y, YS, Z, rev1_in_gga(Y, YS, Z)) U3_gga(X, Y, YS, Z, rev1_out_gga(Y, YS, Z)) -> rev1_out_gga(X, .(Y, YS), Z) U1_ga(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> U2_ga(X, XS, Y, YS, rev2_in_gga(X, XS, YS)) rev2_in_gga(X, [], []) -> rev2_out_gga(X, [], []) rev2_in_gga(X, .(Y, YS), ZS) -> U4_gga(X, Y, YS, ZS, rev2_in_gga(Y, YS, US)) U4_gga(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> U5_gga(X, Y, YS, ZS, rev_in_ga(US, VS)) U5_gga(X, Y, YS, ZS, rev_out_ga(US, VS)) -> U6_gga(X, Y, YS, ZS, rev_in_ga(.(X, VS), ZS)) U6_gga(X, Y, YS, ZS, rev_out_ga(.(X, VS), ZS)) -> rev2_out_gga(X, .(Y, YS), ZS) U2_ga(X, XS, Y, YS, rev2_out_gga(X, XS, YS)) -> rev_out_ga(.(X, XS), .(Y, YS)) The argument filtering Pi contains the following mapping: rev_in_ga(x1, x2) = rev_in_ga(x1) [] = [] rev_out_ga(x1, x2) = rev_out_ga(x1, x2) .(x1, x2) = .(x1, x2) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) rev1_in_gga(x1, x2, x3) = rev1_in_gga(x1, x2) rev1_out_gga(x1, x2, x3) = rev1_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) rev2_in_gga(x1, x2, x3) = rev2_in_gga(x1, x2) rev2_out_gga(x1, x2, x3) = rev2_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x5) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: rev_in_ga([], []) -> rev_out_ga([], []) rev_in_ga(.(X, XS), .(Y, YS)) -> U1_ga(X, XS, Y, YS, rev1_in_gga(X, XS, Y)) rev1_in_gga(X, [], X) -> rev1_out_gga(X, [], X) rev1_in_gga(X, .(Y, YS), Z) -> U3_gga(X, Y, YS, Z, rev1_in_gga(Y, YS, Z)) U3_gga(X, Y, YS, Z, rev1_out_gga(Y, YS, Z)) -> rev1_out_gga(X, .(Y, YS), Z) U1_ga(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> U2_ga(X, XS, Y, YS, rev2_in_gga(X, XS, YS)) rev2_in_gga(X, [], []) -> rev2_out_gga(X, [], []) rev2_in_gga(X, .(Y, YS), ZS) -> U4_gga(X, Y, YS, ZS, rev2_in_gga(Y, YS, US)) U4_gga(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> U5_gga(X, Y, YS, ZS, rev_in_ga(US, VS)) U5_gga(X, Y, YS, ZS, rev_out_ga(US, VS)) -> U6_gga(X, Y, YS, ZS, rev_in_ga(.(X, VS), ZS)) U6_gga(X, Y, YS, ZS, rev_out_ga(.(X, VS), ZS)) -> rev2_out_gga(X, .(Y, YS), ZS) U2_ga(X, XS, Y, YS, rev2_out_gga(X, XS, YS)) -> rev_out_ga(.(X, XS), .(Y, YS)) The argument filtering Pi contains the following mapping: rev_in_ga(x1, x2) = rev_in_ga(x1) [] = [] rev_out_ga(x1, x2) = rev_out_ga(x1, x2) .(x1, x2) = .(x1, x2) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) rev1_in_gga(x1, x2, x3) = rev1_in_gga(x1, x2) rev1_out_gga(x1, x2, x3) = rev1_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) rev2_in_gga(x1, x2, x3) = rev2_in_gga(x1, x2) rev2_out_gga(x1, x2, x3) = rev2_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x5) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x5) ---------------------------------------- (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: REV_IN_GA(.(X, XS), .(Y, YS)) -> U1_GA(X, XS, Y, YS, rev1_in_gga(X, XS, Y)) REV_IN_GA(.(X, XS), .(Y, YS)) -> REV1_IN_GGA(X, XS, Y) REV1_IN_GGA(X, .(Y, YS), Z) -> U3_GGA(X, Y, YS, Z, rev1_in_gga(Y, YS, Z)) REV1_IN_GGA(X, .(Y, YS), Z) -> REV1_IN_GGA(Y, YS, Z) U1_GA(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> U2_GA(X, XS, Y, YS, rev2_in_gga(X, XS, YS)) U1_GA(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> REV2_IN_GGA(X, XS, YS) REV2_IN_GGA(X, .(Y, YS), ZS) -> U4_GGA(X, Y, YS, ZS, rev2_in_gga(Y, YS, US)) REV2_IN_GGA(X, .(Y, YS), ZS) -> REV2_IN_GGA(Y, YS, US) U4_GGA(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> U5_GGA(X, Y, YS, ZS, rev_in_ga(US, VS)) U4_GGA(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> REV_IN_GA(US, VS) U5_GGA(X, Y, YS, ZS, rev_out_ga(US, VS)) -> U6_GGA(X, Y, YS, ZS, rev_in_ga(.(X, VS), ZS)) U5_GGA(X, Y, YS, ZS, rev_out_ga(US, VS)) -> REV_IN_GA(.(X, VS), ZS) The TRS R consists of the following rules: rev_in_ga([], []) -> rev_out_ga([], []) rev_in_ga(.(X, XS), .(Y, YS)) -> U1_ga(X, XS, Y, YS, rev1_in_gga(X, XS, Y)) rev1_in_gga(X, [], X) -> rev1_out_gga(X, [], X) rev1_in_gga(X, .(Y, YS), Z) -> U3_gga(X, Y, YS, Z, rev1_in_gga(Y, YS, Z)) U3_gga(X, Y, YS, Z, rev1_out_gga(Y, YS, Z)) -> rev1_out_gga(X, .(Y, YS), Z) U1_ga(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> U2_ga(X, XS, Y, YS, rev2_in_gga(X, XS, YS)) rev2_in_gga(X, [], []) -> rev2_out_gga(X, [], []) rev2_in_gga(X, .(Y, YS), ZS) -> U4_gga(X, Y, YS, ZS, rev2_in_gga(Y, YS, US)) U4_gga(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> U5_gga(X, Y, YS, ZS, rev_in_ga(US, VS)) U5_gga(X, Y, YS, ZS, rev_out_ga(US, VS)) -> U6_gga(X, Y, YS, ZS, rev_in_ga(.(X, VS), ZS)) U6_gga(X, Y, YS, ZS, rev_out_ga(.(X, VS), ZS)) -> rev2_out_gga(X, .(Y, YS), ZS) U2_ga(X, XS, Y, YS, rev2_out_gga(X, XS, YS)) -> rev_out_ga(.(X, XS), .(Y, YS)) The argument filtering Pi contains the following mapping: rev_in_ga(x1, x2) = rev_in_ga(x1) [] = [] rev_out_ga(x1, x2) = rev_out_ga(x1, x2) .(x1, x2) = .(x1, x2) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) rev1_in_gga(x1, x2, x3) = rev1_in_gga(x1, x2) rev1_out_gga(x1, x2, x3) = rev1_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) rev2_in_gga(x1, x2, x3) = rev2_in_gga(x1, x2) rev2_out_gga(x1, x2, x3) = rev2_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x5) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x5) REV_IN_GA(x1, x2) = REV_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x5) REV1_IN_GGA(x1, x2, x3) = REV1_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x1, x2, x3, x5) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) REV2_IN_GGA(x1, x2, x3) = REV2_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x1, x2, x3, x5) U5_GGA(x1, x2, x3, x4, x5) = U5_GGA(x1, x2, x3, x5) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: REV_IN_GA(.(X, XS), .(Y, YS)) -> U1_GA(X, XS, Y, YS, rev1_in_gga(X, XS, Y)) REV_IN_GA(.(X, XS), .(Y, YS)) -> REV1_IN_GGA(X, XS, Y) REV1_IN_GGA(X, .(Y, YS), Z) -> U3_GGA(X, Y, YS, Z, rev1_in_gga(Y, YS, Z)) REV1_IN_GGA(X, .(Y, YS), Z) -> REV1_IN_GGA(Y, YS, Z) U1_GA(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> U2_GA(X, XS, Y, YS, rev2_in_gga(X, XS, YS)) U1_GA(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> REV2_IN_GGA(X, XS, YS) REV2_IN_GGA(X, .(Y, YS), ZS) -> U4_GGA(X, Y, YS, ZS, rev2_in_gga(Y, YS, US)) REV2_IN_GGA(X, .(Y, YS), ZS) -> REV2_IN_GGA(Y, YS, US) U4_GGA(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> U5_GGA(X, Y, YS, ZS, rev_in_ga(US, VS)) U4_GGA(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> REV_IN_GA(US, VS) U5_GGA(X, Y, YS, ZS, rev_out_ga(US, VS)) -> U6_GGA(X, Y, YS, ZS, rev_in_ga(.(X, VS), ZS)) U5_GGA(X, Y, YS, ZS, rev_out_ga(US, VS)) -> REV_IN_GA(.(X, VS), ZS) The TRS R consists of the following rules: rev_in_ga([], []) -> rev_out_ga([], []) rev_in_ga(.(X, XS), .(Y, YS)) -> U1_ga(X, XS, Y, YS, rev1_in_gga(X, XS, Y)) rev1_in_gga(X, [], X) -> rev1_out_gga(X, [], X) rev1_in_gga(X, .(Y, YS), Z) -> U3_gga(X, Y, YS, Z, rev1_in_gga(Y, YS, Z)) U3_gga(X, Y, YS, Z, rev1_out_gga(Y, YS, Z)) -> rev1_out_gga(X, .(Y, YS), Z) U1_ga(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> U2_ga(X, XS, Y, YS, rev2_in_gga(X, XS, YS)) rev2_in_gga(X, [], []) -> rev2_out_gga(X, [], []) rev2_in_gga(X, .(Y, YS), ZS) -> U4_gga(X, Y, YS, ZS, rev2_in_gga(Y, YS, US)) U4_gga(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> U5_gga(X, Y, YS, ZS, rev_in_ga(US, VS)) U5_gga(X, Y, YS, ZS, rev_out_ga(US, VS)) -> U6_gga(X, Y, YS, ZS, rev_in_ga(.(X, VS), ZS)) U6_gga(X, Y, YS, ZS, rev_out_ga(.(X, VS), ZS)) -> rev2_out_gga(X, .(Y, YS), ZS) U2_ga(X, XS, Y, YS, rev2_out_gga(X, XS, YS)) -> rev_out_ga(.(X, XS), .(Y, YS)) The argument filtering Pi contains the following mapping: rev_in_ga(x1, x2) = rev_in_ga(x1) [] = [] rev_out_ga(x1, x2) = rev_out_ga(x1, x2) .(x1, x2) = .(x1, x2) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) rev1_in_gga(x1, x2, x3) = rev1_in_gga(x1, x2) rev1_out_gga(x1, x2, x3) = rev1_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) rev2_in_gga(x1, x2, x3) = rev2_in_gga(x1, x2) rev2_out_gga(x1, x2, x3) = rev2_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x5) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x5) REV_IN_GA(x1, x2) = REV_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x5) REV1_IN_GGA(x1, x2, x3) = REV1_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x1, x2, x3, x5) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x2, x3, x5) REV2_IN_GGA(x1, x2, x3) = REV2_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x1, x2, x3, x5) U5_GGA(x1, x2, x3, x4, x5) = U5_GGA(x1, x2, x3, x5) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: REV1_IN_GGA(X, .(Y, YS), Z) -> REV1_IN_GGA(Y, YS, Z) The TRS R consists of the following rules: rev_in_ga([], []) -> rev_out_ga([], []) rev_in_ga(.(X, XS), .(Y, YS)) -> U1_ga(X, XS, Y, YS, rev1_in_gga(X, XS, Y)) rev1_in_gga(X, [], X) -> rev1_out_gga(X, [], X) rev1_in_gga(X, .(Y, YS), Z) -> U3_gga(X, Y, YS, Z, rev1_in_gga(Y, YS, Z)) U3_gga(X, Y, YS, Z, rev1_out_gga(Y, YS, Z)) -> rev1_out_gga(X, .(Y, YS), Z) U1_ga(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> U2_ga(X, XS, Y, YS, rev2_in_gga(X, XS, YS)) rev2_in_gga(X, [], []) -> rev2_out_gga(X, [], []) rev2_in_gga(X, .(Y, YS), ZS) -> U4_gga(X, Y, YS, ZS, rev2_in_gga(Y, YS, US)) U4_gga(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> U5_gga(X, Y, YS, ZS, rev_in_ga(US, VS)) U5_gga(X, Y, YS, ZS, rev_out_ga(US, VS)) -> U6_gga(X, Y, YS, ZS, rev_in_ga(.(X, VS), ZS)) U6_gga(X, Y, YS, ZS, rev_out_ga(.(X, VS), ZS)) -> rev2_out_gga(X, .(Y, YS), ZS) U2_ga(X, XS, Y, YS, rev2_out_gga(X, XS, YS)) -> rev_out_ga(.(X, XS), .(Y, YS)) The argument filtering Pi contains the following mapping: rev_in_ga(x1, x2) = rev_in_ga(x1) [] = [] rev_out_ga(x1, x2) = rev_out_ga(x1, x2) .(x1, x2) = .(x1, x2) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) rev1_in_gga(x1, x2, x3) = rev1_in_gga(x1, x2) rev1_out_gga(x1, x2, x3) = rev1_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) rev2_in_gga(x1, x2, x3) = rev2_in_gga(x1, x2) rev2_out_gga(x1, x2, x3) = rev2_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x5) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x5) REV1_IN_GGA(x1, x2, x3) = REV1_IN_GGA(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: REV1_IN_GGA(X, .(Y, YS), Z) -> REV1_IN_GGA(Y, YS, Z) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) REV1_IN_GGA(x1, x2, x3) = REV1_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) 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: REV1_IN_GGA(X, .(Y, YS)) -> REV1_IN_GGA(Y, YS) 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: *REV1_IN_GGA(X, .(Y, YS)) -> REV1_IN_GGA(Y, YS) The graph contains the following edges 2 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_GA(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> REV2_IN_GGA(X, XS, YS) REV2_IN_GGA(X, .(Y, YS), ZS) -> U4_GGA(X, Y, YS, ZS, rev2_in_gga(Y, YS, US)) U4_GGA(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> U5_GGA(X, Y, YS, ZS, rev_in_ga(US, VS)) U5_GGA(X, Y, YS, ZS, rev_out_ga(US, VS)) -> REV_IN_GA(.(X, VS), ZS) REV_IN_GA(.(X, XS), .(Y, YS)) -> U1_GA(X, XS, Y, YS, rev1_in_gga(X, XS, Y)) U4_GGA(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> REV_IN_GA(US, VS) REV2_IN_GGA(X, .(Y, YS), ZS) -> REV2_IN_GGA(Y, YS, US) The TRS R consists of the following rules: rev_in_ga([], []) -> rev_out_ga([], []) rev_in_ga(.(X, XS), .(Y, YS)) -> U1_ga(X, XS, Y, YS, rev1_in_gga(X, XS, Y)) rev1_in_gga(X, [], X) -> rev1_out_gga(X, [], X) rev1_in_gga(X, .(Y, YS), Z) -> U3_gga(X, Y, YS, Z, rev1_in_gga(Y, YS, Z)) U3_gga(X, Y, YS, Z, rev1_out_gga(Y, YS, Z)) -> rev1_out_gga(X, .(Y, YS), Z) U1_ga(X, XS, Y, YS, rev1_out_gga(X, XS, Y)) -> U2_ga(X, XS, Y, YS, rev2_in_gga(X, XS, YS)) rev2_in_gga(X, [], []) -> rev2_out_gga(X, [], []) rev2_in_gga(X, .(Y, YS), ZS) -> U4_gga(X, Y, YS, ZS, rev2_in_gga(Y, YS, US)) U4_gga(X, Y, YS, ZS, rev2_out_gga(Y, YS, US)) -> U5_gga(X, Y, YS, ZS, rev_in_ga(US, VS)) U5_gga(X, Y, YS, ZS, rev_out_ga(US, VS)) -> U6_gga(X, Y, YS, ZS, rev_in_ga(.(X, VS), ZS)) U6_gga(X, Y, YS, ZS, rev_out_ga(.(X, VS), ZS)) -> rev2_out_gga(X, .(Y, YS), ZS) U2_ga(X, XS, Y, YS, rev2_out_gga(X, XS, YS)) -> rev_out_ga(.(X, XS), .(Y, YS)) The argument filtering Pi contains the following mapping: rev_in_ga(x1, x2) = rev_in_ga(x1) [] = [] rev_out_ga(x1, x2) = rev_out_ga(x1, x2) .(x1, x2) = .(x1, x2) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x2, x5) rev1_in_gga(x1, x2, x3) = rev1_in_gga(x1, x2) rev1_out_gga(x1, x2, x3) = rev1_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x2, x3, x5) rev2_in_gga(x1, x2, x3) = rev2_in_gga(x1, x2) rev2_out_gga(x1, x2, x3) = rev2_out_gga(x1, x2, x3) U4_gga(x1, x2, x3, x4, x5) = U4_gga(x1, x2, x3, x5) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x5) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x5) REV_IN_GA(x1, x2) = REV_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x5) REV2_IN_GGA(x1, x2, x3) = REV2_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4, x5) = U4_GGA(x1, x2, x3, x5) U5_GGA(x1, x2, x3, x4, x5) = U5_GGA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: U1_GA(X, XS, rev1_out_gga(X, XS, Y)) -> REV2_IN_GGA(X, XS) REV2_IN_GGA(X, .(Y, YS)) -> U4_GGA(X, Y, YS, rev2_in_gga(Y, YS)) U4_GGA(X, Y, YS, rev2_out_gga(Y, YS, US)) -> U5_GGA(X, Y, YS, rev_in_ga(US)) U5_GGA(X, Y, YS, rev_out_ga(US, VS)) -> REV_IN_GA(.(X, VS)) REV_IN_GA(.(X, XS)) -> U1_GA(X, XS, rev1_in_gga(X, XS)) U4_GGA(X, Y, YS, rev2_out_gga(Y, YS, US)) -> REV_IN_GA(US) REV2_IN_GGA(X, .(Y, YS)) -> REV2_IN_GGA(Y, YS) The TRS R consists of the following rules: rev_in_ga([]) -> rev_out_ga([], []) rev_in_ga(.(X, XS)) -> U1_ga(X, XS, rev1_in_gga(X, XS)) rev1_in_gga(X, []) -> rev1_out_gga(X, [], X) rev1_in_gga(X, .(Y, YS)) -> U3_gga(X, Y, YS, rev1_in_gga(Y, YS)) U3_gga(X, Y, YS, rev1_out_gga(Y, YS, Z)) -> rev1_out_gga(X, .(Y, YS), Z) U1_ga(X, XS, rev1_out_gga(X, XS, Y)) -> U2_ga(X, XS, Y, rev2_in_gga(X, XS)) rev2_in_gga(X, []) -> rev2_out_gga(X, [], []) rev2_in_gga(X, .(Y, YS)) -> U4_gga(X, Y, YS, rev2_in_gga(Y, YS)) U4_gga(X, Y, YS, rev2_out_gga(Y, YS, US)) -> U5_gga(X, Y, YS, rev_in_ga(US)) U5_gga(X, Y, YS, rev_out_ga(US, VS)) -> U6_gga(X, Y, YS, rev_in_ga(.(X, VS))) U6_gga(X, Y, YS, rev_out_ga(.(X, VS), ZS)) -> rev2_out_gga(X, .(Y, YS), ZS) U2_ga(X, XS, Y, rev2_out_gga(X, XS, YS)) -> rev_out_ga(.(X, XS), .(Y, YS)) The set Q consists of the following terms: rev_in_ga(x0) rev1_in_gga(x0, x1) U3_gga(x0, x1, x2, x3) U1_ga(x0, x1, x2) rev2_in_gga(x0, x1) U4_gga(x0, x1, x2, x3) U5_gga(x0, x1, x2, x3) U6_gga(x0, x1, x2, x3) U2_ga(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (17) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U1_GA(X, XS, rev1_out_gga(X, XS, Y)) -> REV2_IN_GGA(X, XS) REV2_IN_GGA(X, .(Y, YS)) -> U4_GGA(X, Y, YS, rev2_in_gga(Y, YS)) REV_IN_GA(.(X, XS)) -> U1_GA(X, XS, rev1_in_gga(X, XS)) U4_GGA(X, Y, YS, rev2_out_gga(Y, YS, US)) -> REV_IN_GA(US) REV2_IN_GGA(X, .(Y, YS)) -> REV2_IN_GGA(Y, YS) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U4_GGA_4(x_1, ..., x_4) ) = 2x_4 + 2 POL( U2_ga_4(x_1, ..., x_4) ) = x_4 + 2 POL( U5_GGA_4(x_1, ..., x_4) ) = 2x_4 + 2 POL( U4_gga_4(x_1, ..., x_4) ) = x_4 + 2 POL( rev2_in_gga_2(x_1, x_2) ) = x_2 POL( [] ) = 0 POL( rev2_out_gga_3(x_1, ..., x_3) ) = x_3 POL( ._2(x_1, x_2) ) = x_2 + 2 POL( U5_gga_4(x_1, ..., x_4) ) = x_4 + 2 POL( rev_in_ga_1(x_1) ) = x_1 POL( rev_out_ga_2(x_1, x_2) ) = x_2 POL( U1_ga_3(x_1, ..., x_3) ) = x_2 + 2 POL( rev1_in_gga_2(x_1, x_2) ) = 0 POL( U1_GA_3(x_1, ..., x_3) ) = 2x_2 + 1 POL( rev1_out_gga_3(x_1, ..., x_3) ) = max{0, 2x_3 - 2} POL( U3_gga_4(x_1, ..., x_4) ) = max{0, 2x_1 + 2x_2 - 2} POL( U6_gga_4(x_1, ..., x_4) ) = x_4 POL( REV2_IN_GGA_2(x_1, x_2) ) = 2x_2 POL( REV_IN_GA_1(x_1) ) = max{0, 2x_1 - 2} The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: rev2_in_gga(X, []) -> rev2_out_gga(X, [], []) rev2_in_gga(X, .(Y, YS)) -> U4_gga(X, Y, YS, rev2_in_gga(Y, YS)) rev_in_ga([]) -> rev_out_ga([], []) rev_in_ga(.(X, XS)) -> U1_ga(X, XS, rev1_in_gga(X, XS)) U1_ga(X, XS, rev1_out_gga(X, XS, Y)) -> U2_ga(X, XS, Y, rev2_in_gga(X, XS)) U2_ga(X, XS, Y, rev2_out_gga(X, XS, YS)) -> rev_out_ga(.(X, XS), .(Y, YS)) U4_gga(X, Y, YS, rev2_out_gga(Y, YS, US)) -> U5_gga(X, Y, YS, rev_in_ga(US)) U5_gga(X, Y, YS, rev_out_ga(US, VS)) -> U6_gga(X, Y, YS, rev_in_ga(.(X, VS))) U6_gga(X, Y, YS, rev_out_ga(.(X, VS), ZS)) -> rev2_out_gga(X, .(Y, YS), ZS) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: U4_GGA(X, Y, YS, rev2_out_gga(Y, YS, US)) -> U5_GGA(X, Y, YS, rev_in_ga(US)) U5_GGA(X, Y, YS, rev_out_ga(US, VS)) -> REV_IN_GA(.(X, VS)) The TRS R consists of the following rules: rev_in_ga([]) -> rev_out_ga([], []) rev_in_ga(.(X, XS)) -> U1_ga(X, XS, rev1_in_gga(X, XS)) rev1_in_gga(X, []) -> rev1_out_gga(X, [], X) rev1_in_gga(X, .(Y, YS)) -> U3_gga(X, Y, YS, rev1_in_gga(Y, YS)) U3_gga(X, Y, YS, rev1_out_gga(Y, YS, Z)) -> rev1_out_gga(X, .(Y, YS), Z) U1_ga(X, XS, rev1_out_gga(X, XS, Y)) -> U2_ga(X, XS, Y, rev2_in_gga(X, XS)) rev2_in_gga(X, []) -> rev2_out_gga(X, [], []) rev2_in_gga(X, .(Y, YS)) -> U4_gga(X, Y, YS, rev2_in_gga(Y, YS)) U4_gga(X, Y, YS, rev2_out_gga(Y, YS, US)) -> U5_gga(X, Y, YS, rev_in_ga(US)) U5_gga(X, Y, YS, rev_out_ga(US, VS)) -> U6_gga(X, Y, YS, rev_in_ga(.(X, VS))) U6_gga(X, Y, YS, rev_out_ga(.(X, VS), ZS)) -> rev2_out_gga(X, .(Y, YS), ZS) U2_ga(X, XS, Y, rev2_out_gga(X, XS, YS)) -> rev_out_ga(.(X, XS), .(Y, YS)) The set Q consists of the following terms: rev_in_ga(x0) rev1_in_gga(x0, x1) U3_gga(x0, x1, x2, x3) U1_ga(x0, x1, x2) rev2_in_gga(x0, x1) U4_gga(x0, x1, x2, x3) U5_gga(x0, x1, x2, x3) U6_gga(x0, x1, x2, x3) U2_ga(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (20) TRUE