/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Outermost Termination of the given OTRS could not be shown: (0) OTRS (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 52 ms] (4) QTRS (5) DependencyPairsProof [EQUIVALENT, 0 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) QDP (12) QReductionProof [EQUIVALENT, 0 ms] (13) QDP (14) UsableRulesReductionPairsProof [EQUIVALENT, 6 ms] (15) QDP (16) MRRProof [EQUIVALENT, 0 ms] (17) QDP (18) MRRProof [EQUIVALENT, 0 ms] (19) QDP (20) DependencyGraphProof [EQUIVALENT, 0 ms] (21) QDP (22) QReductionProof [EQUIVALENT, 0 ms] (23) QDP (24) MRRProof [EQUIVALENT, 9 ms] (25) QDP (26) PisEmptyProof [EQUIVALENT, 0 ms] (27) YES (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [SOUND, 0 ms] (34) QDP (35) QReductionProof [EQUIVALENT, 0 ms] (36) QDP (37) UsableRulesProof [EQUIVALENT, 0 ms] (38) QDP (39) QReductionProof [EQUIVALENT, 0 ms] (40) QDP (41) QReductionProof [EQUIVALENT, 0 ms] (42) QDP (43) Trivial-Transformation [SOUND, 0 ms] (44) QTRS (45) QTRSRRRProof [EQUIVALENT, 58 ms] (46) QTRS (47) DependencyPairsProof [EQUIVALENT, 0 ms] (48) QDP (49) DependencyGraphProof [EQUIVALENT, 4 ms] (50) QDP (51) UsableRulesProof [EQUIVALENT, 0 ms] (52) QDP (53) NonTerminationLoopProof [COMPLETE, 0 ms] (54) NO ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: f(g(a, a)) -> f(s(g(b, b))) f(f(x)) -> b g(x, x) -> f(g(x, x)) Outermost Strategy. ---------------------------------------- (1) Thiemann-SpecialC-Transformation (EQUIVALENT) We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_f(g(a, a)) -> result_f(f(s(g(b, b)))) redex_f(f(x)) -> result_f(b) redex_g(x, x) -> result_g(f(g(x, x))) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(a) = 2 POL(b) = 0 POL(check_f(x_1)) = x_1 POL(check_g(x_1)) = x_1 POL(f(x_1)) = x_1 POL(g(x_1, x_2)) = 2*x_1 + x_2 POL(go_up(x_1)) = x_1 POL(in_f_1(x_1)) = x_1 POL(in_g_1(x_1, x_2)) = 2*x_1 + x_2 POL(in_g_2(x_1, x_2)) = 2*x_1 + x_2 POL(in_s_1(x_1)) = 2*x_1 POL(redex_f(x_1)) = x_1 POL(redex_g(x_1, x_2)) = 2*x_1 + x_2 POL(reduce(x_1)) = x_1 POL(result_f(x_1)) = 2*x_1 POL(result_g(x_1)) = x_1 POL(s(x_1)) = 2*x_1 POL(top(x_1)) = 2*x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: redex_f(g(a, a)) -> result_f(f(s(g(b, b)))) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_f(f(x)) -> result_f(b) redex_g(x, x) -> result_g(f(g(x, x))) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) ---------------------------------------- (5) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) TOP(go_up(x)) -> REDUCE(x) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) REDUCE(f(x_1)) -> REDEX_F(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) REDUCE(g(x_1, x_2)) -> REDEX_G(x_1, x_2) CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1)) CHECK_F(redex_f(x_1)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2)) -> IN_G_1(reduce(x_1), x_2) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2)) -> IN_G_2(x_1, reduce(x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) REDUCE(s(x_1)) -> IN_S_1(reduce(x_1)) REDUCE(s(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_f(f(x)) -> result_f(b) redex_g(x, x) -> result_g(f(g(x, x))) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 7 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) REDUCE(s(x_1)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_f(f(x)) -> result_f(b) redex_g(x, x) -> result_g(f(g(x, x))) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) REDUCE(s(x_1)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: redex_f(f(x)) -> result_f(b) redex_g(x, x) -> result_g(f(g(x, x))) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(go_up(x0)) reduce(f(x0)) reduce(g(x0, x1)) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) REDUCE(s(x_1)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: redex_f(f(x)) -> result_f(b) redex_g(x, x) -> result_g(f(g(x, x))) The set Q consists of the following terms: redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) 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. The following dependency pairs can be deleted: REDUCE(s(x_1)) -> REDUCE(x_1) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_F(x_1)) = 2*x_1 POL(CHECK_G(x_1)) = x_1 POL(REDUCE(x_1)) = 2*x_1 POL(b) = 0 POL(f(x_1)) = 2*x_1 POL(g(x_1, x_2)) = x_1 + x_2 POL(redex_f(x_1)) = x_1 POL(redex_g(x_1, x_2)) = 2*x_1 + 2*x_2 POL(result_f(x_1)) = x_1 POL(result_g(x_1)) = x_1 POL(s(x_1)) = 2*x_1 ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: redex_f(f(x)) -> result_f(b) redex_g(x, x) -> result_g(f(g(x, x))) The set Q consists of the following terms: redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) 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 rules of the TRS R: redex_f(f(x)) -> result_f(b) Used ordering: Polynomial interpretation [POLO]: POL(CHECK_F(x_1)) = x_1 POL(CHECK_G(x_1)) = 1 + x_1 POL(REDUCE(x_1)) = 1 + 2*x_1 POL(b) = 0 POL(f(x_1)) = x_1 POL(g(x_1, x_2)) = x_1 + x_2 POL(redex_f(x_1)) = 1 + 2*x_1 POL(redex_g(x_1, x_2)) = 2*x_1 + 2*x_2 POL(result_f(x_1)) = x_1 POL(result_g(x_1)) = 2*x_1 ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: redex_g(x, x) -> result_g(f(g(x, x))) The set Q consists of the following terms: redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) 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: REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) Used ordering: Polynomial interpretation [POLO]: POL(CHECK_F(x_1)) = x_1 POL(CHECK_G(x_1)) = x_1 POL(REDUCE(x_1)) = 2 + 2*x_1 POL(f(x_1)) = 1 + x_1 POL(g(x_1, x_2)) = x_1 + x_2 POL(redex_f(x_1)) = 2 + 2*x_1 POL(redex_g(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(result_g(x_1)) = 2*x_1 ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: redex_g(x, x) -> result_g(f(g(x, x))) The set Q consists of the following terms: redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: redex_g(x, x) -> result_g(f(g(x, x))) The set Q consists of the following terms: redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. redex_f(g(a, a)) redex_f(f(x0)) ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) The TRS R consists of the following rules: redex_g(x, x) -> result_g(f(g(x, x))) The set Q consists of the following terms: redex_g(x0, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) 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: CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_1) REDUCE(g(x_1, x_2)) -> CHECK_G(redex_g(x_1, x_2)) CHECK_G(redex_g(x_1, x_2)) -> REDUCE(x_2) Used ordering: Polynomial interpretation [POLO]: POL(CHECK_G(x_1)) = 1 + x_1 POL(REDUCE(x_1)) = 2*x_1 POL(f(x_1)) = x_1 POL(g(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(redex_g(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(result_g(x_1)) = x_1 ---------------------------------------- (25) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: redex_g(x, x) -> result_g(f(g(x, x))) The set Q consists of the following terms: redex_g(x0, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: top(go_up(x)) -> top(reduce(x)) reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) redex_f(f(x)) -> result_f(b) redex_g(x, x) -> result_g(f(g(x, x))) check_f(result_f(x)) -> go_up(x) check_g(result_g(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) redex_g(x, x) -> result_g(f(g(x, x))) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) redex_f(f(x)) -> result_f(b) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(go_up(x0)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) redex_g(x, x) -> result_g(f(g(x, x))) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) redex_f(f(x)) -> result_f(b) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (SOUND) By narrowing [LPAR04] the rule TOP(go_up(x)) -> TOP(reduce(x)) at position [0] we obtained the following new rules [LPAR04]: (TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))),TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0)))) (TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))),TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1)))) (TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))),TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0)))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) redex_g(x, x) -> result_g(f(g(x, x))) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) redex_f(f(x)) -> result_f(b) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) QReductionProof (EQUIVALENT) We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. redex_f(g(a, a)) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) TOP(go_up(g(x0, x1))) -> TOP(check_g(redex_g(x0, x1))) TOP(go_up(s(x0))) -> TOP(in_s_1(reduce(x0))) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) redex_g(x, x) -> result_g(f(g(x, x))) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) redex_f(f(x)) -> result_f(b) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0, x1)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) redex_g(x, x) -> result_g(f(g(x, x))) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) redex_f(f(x)) -> result_f(b) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. top(go_up(x0)) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) redex_g(x, x) -> result_g(f(g(x, x))) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) redex_f(f(x)) -> result_f(b) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0, x1)) redex_f(g(a, a)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) QReductionProof (EQUIVALENT) We deleted the following terms from Q as they contain symbols which do neither occur in P nor in R.[THIEMANN]. redex_f(g(a, a)) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: TOP(go_up(x)) -> TOP(reduce(x)) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1, x_2)) -> check_g(redex_g(x_1, x_2)) reduce(s(x_1)) -> in_s_1(reduce(x_1)) in_s_1(go_up(x_1)) -> go_up(s(x_1)) redex_g(x, x) -> result_g(f(g(x, x))) check_g(result_g(x)) -> go_up(x) check_g(redex_g(x_1, x_2)) -> in_g_1(reduce(x_1), x_2) check_g(redex_g(x_1, x_2)) -> in_g_2(x_1, reduce(x_2)) in_g_2(x_1, go_up(x_2)) -> go_up(g(x_1, x_2)) in_g_1(go_up(x_1), x_2) -> go_up(g(x_1, x_2)) redex_f(f(x)) -> result_f(b) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0, x1)) redex_f(f(x0)) redex_g(x0, x0) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) check_g(redex_g(x0, x1)) reduce(s(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0), x1) in_g_2(x0, go_up(x1)) in_s_1(go_up(x0)) We have to consider all (P,Q,R)-chains. ---------------------------------------- (43) Trivial-Transformation (SOUND) We applied the Trivial transformation to transform the outermost TRS to a standard TRS. ---------------------------------------- (44) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f(g(a, a)) -> f(s(g(b, b))) f(f(x)) -> b g(x, x) -> f(g(x, x)) Q is empty. ---------------------------------------- (45) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(a) = 2 POL(b) = 0 POL(f(x_1)) = x_1 POL(g(x_1, x_2)) = x_1 + 2*x_2 POL(s(x_1)) = 1 + x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f(g(a, a)) -> f(s(g(b, b))) ---------------------------------------- (46) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f(f(x)) -> b g(x, x) -> f(g(x, x)) Q is empty. ---------------------------------------- (47) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: G(x, x) -> F(g(x, x)) G(x, x) -> G(x, x) The TRS R consists of the following rules: f(f(x)) -> b g(x, x) -> f(g(x, x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: G(x, x) -> G(x, x) The TRS R consists of the following rules: f(f(x)) -> b g(x, x) -> f(g(x, x)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: G(x, x) -> G(x, x) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = G(x, x) evaluates to t =G(x, x) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from G(x, x) to G(x, x). ---------------------------------------- (54) NO