/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Outermost Termination of the given OTRS could be disproven: (0) OTRS (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QReductionProof [EQUIVALENT, 0 ms] (11) QDP (12) UsableRulesReductionPairsProof [EQUIVALENT, 6 ms] (13) QDP (14) DependencyGraphProof [EQUIVALENT, 0 ms] (15) TRUE (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) QReductionProof [EQUIVALENT, 0 ms] (20) QDP (21) TransformationProof [EQUIVALENT, 0 ms] (22) QDP (23) UsableRulesProof [EQUIVALENT, 0 ms] (24) QDP (25) NonTerminationLoopProof [COMPLETE, 0 ms] (26) NO ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: b -> f(f(b)) f(b) -> b f(f(f(x))) -> b 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(b) -> go_up(f(f(b))) redex_f(b) -> result_f(b) redex_f(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(b) redex_f(b) redex_f(f(f(x0))) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) 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) CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1)) CHECK_F(redex_f(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(b) -> go_up(f(f(b))) redex_f(b) -> result_f(b) redex_f(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(b) redex_f(b) redex_f(f(f(x0))) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(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(b) -> go_up(f(f(b))) redex_f(b) -> result_f(b) redex_f(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(b) redex_f(b) redex_f(f(f(x0))) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) 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. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) The TRS R consists of the following rules: redex_f(b) -> result_f(b) redex_f(f(f(x))) -> result_f(b) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(b) redex_f(b) redex_f(f(f(x0))) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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(b) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) The TRS R consists of the following rules: redex_f(b) -> result_f(b) redex_f(f(f(x))) -> result_f(b) The set Q consists of the following terms: redex_f(b) redex_f(f(f(x0))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) 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(f(x_1)) -> CHECK_F(redex_f(x_1)) The following rules are removed from R: redex_f(f(f(x))) -> result_f(b) Used ordering: POLO with Polynomial interpretation [POLO]: POL(CHECK_F(x_1)) = x_1 POL(REDUCE(x_1)) = 2*x_1 POL(b) = 0 POL(f(x_1)) = 2*x_1 POL(redex_f(x_1)) = 2*x_1 POL(result_f(x_1)) = 2*x_1 ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: CHECK_F(redex_f(x_1)) -> REDUCE(x_1) The TRS R consists of the following rules: redex_f(b) -> result_f(b) The set Q consists of the following terms: redex_f(b) redex_f(f(f(x0))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (15) TRUE ---------------------------------------- (16) 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(b) -> go_up(f(f(b))) redex_f(b) -> result_f(b) redex_f(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(b) redex_f(b) redex_f(f(f(x0))) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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. ---------------------------------------- (18) 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(b) -> go_up(f(f(b))) redex_f(b) -> result_f(b) redex_f(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(b) redex_f(b) redex_f(f(f(x0))) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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)) ---------------------------------------- (20) 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(b) -> go_up(f(f(b))) redex_f(b) -> result_f(b) redex_f(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(b) redex_f(b) redex_f(f(f(x0))) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) TransformationProof (EQUIVALENT) 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(b)) -> TOP(go_up(f(f(b)))),TOP(go_up(b)) -> TOP(go_up(f(f(b))))) ---------------------------------------- (22) 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(b)) -> TOP(go_up(f(f(b)))) The TRS R consists of the following rules: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(b) -> go_up(f(f(b))) redex_f(b) -> result_f(b) redex_f(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(b) redex_f(b) redex_f(f(f(x0))) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) 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. ---------------------------------------- (24) 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(b)) -> TOP(go_up(f(f(b)))) The TRS R consists of the following rules: redex_f(b) -> result_f(b) redex_f(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)) reduce(f(x_1)) -> check_f(redex_f(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(b) redex_f(b) redex_f(f(f(x0))) check_f(result_f(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the right: s = TOP(go_up(f(f(b)))) evaluates to t =TOP(go_up(f(f(b)))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence TOP(go_up(f(f(b)))) -> TOP(check_f(redex_f(f(b)))) with rule TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) and matcher [x0 / f(b)]. TOP(check_f(redex_f(f(b)))) -> TOP(in_f_1(reduce(f(b)))) with rule check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) at position [0] and matcher [x_1 / f(b)] TOP(in_f_1(reduce(f(b)))) -> TOP(in_f_1(check_f(redex_f(b)))) with rule reduce(f(x_1')) -> check_f(redex_f(x_1')) at position [0,0] and matcher [x_1' / b] TOP(in_f_1(check_f(redex_f(b)))) -> TOP(in_f_1(check_f(result_f(b)))) with rule redex_f(b) -> result_f(b) at position [0,0,0] and matcher [ ] TOP(in_f_1(check_f(result_f(b)))) -> TOP(in_f_1(go_up(b))) with rule check_f(result_f(x)) -> go_up(x) at position [0,0] and matcher [x / b] TOP(in_f_1(go_up(b))) -> TOP(go_up(f(b))) with rule in_f_1(go_up(x_1)) -> go_up(f(x_1)) at position [0] and matcher [x_1 / b] TOP(go_up(f(b))) -> TOP(check_f(redex_f(b))) with rule TOP(go_up(f(x0))) -> TOP(check_f(redex_f(x0))) at position [] and matcher [x0 / b] TOP(check_f(redex_f(b))) -> TOP(check_f(result_f(b))) with rule redex_f(b) -> result_f(b) at position [0,0] and matcher [ ] TOP(check_f(result_f(b))) -> TOP(go_up(b)) with rule check_f(result_f(x)) -> go_up(x) at position [0] and matcher [x / b] TOP(go_up(b)) -> TOP(go_up(f(f(b)))) with rule TOP(go_up(b)) -> TOP(go_up(f(f(b)))) at position [] and matcher [ ] Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (26) NO