/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Outermost Termination of the given OTRS could be proven: (0) OTRS (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 3 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) QDP (9) QReductionProof [EQUIVALENT, 0 ms] (10) QDP (11) RFCMatchBoundsDPProof [EQUIVALENT, 1 ms] (12) YES ---------------------------------------- (0) Obligation: Term rewrite system R: The TRS R consists of the following rules: f(g(x)) -> g(g(x)) g(x) -> f(f(x)) f(f(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)) -> check_g(redex_g(x_1)) redex_f(g(x)) -> result_f(g(g(x))) redex_g(x) -> result_g(f(f(x))) redex_f(f(x)) -> result_f(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)) -> in_g_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) redex_f(g(x0)) redex_g(x0) redex_f(f(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) in_g_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) REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) REDUCE(g(x_1)) -> REDEX_G(x_1) 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)) -> IN_G_1(reduce(x_1)) CHECK_G(redex_g(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)) -> check_g(redex_g(x_1)) redex_f(g(x)) -> result_f(g(g(x))) redex_g(x) -> result_g(f(f(x))) redex_f(f(x)) -> result_f(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)) -> in_g_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) redex_f(g(x0)) redex_g(x0) redex_f(f(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) in_g_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 1 SCC with 9 less nodes. ---------------------------------------- (6) 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)) -> check_g(redex_g(x_1)) redex_f(g(x)) -> result_f(g(g(x))) redex_g(x) -> result_g(f(f(x))) redex_f(f(x)) -> result_f(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)) -> in_g_1(reduce(x_1)) in_f_1(go_up(x_1)) -> go_up(f(x_1)) in_g_1(go_up(x_1)) -> go_up(g(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) redex_f(g(x0)) redex_g(x0) redex_f(f(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) 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. ---------------------------------------- (8) 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)) -> check_g(redex_g(x_1)) redex_g(x) -> result_g(f(f(x))) check_g(result_g(x)) -> go_up(x) redex_f(g(x)) -> result_f(g(g(x))) redex_f(f(x)) -> result_f(x) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) The set Q consists of the following terms: top(go_up(x0)) reduce(f(x0)) reduce(g(x0)) redex_f(g(x0)) redex_g(x0) redex_f(f(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) in_g_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) 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)) in_g_1(go_up(x0)) ---------------------------------------- (10) 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)) -> check_g(redex_g(x_1)) redex_g(x) -> result_g(f(f(x))) check_g(result_g(x)) -> go_up(x) redex_f(g(x)) -> result_f(g(g(x))) redex_f(f(x)) -> result_f(x) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) The set Q consists of the following terms: reduce(f(x0)) reduce(g(x0)) redex_f(g(x0)) redex_g(x0) redex_f(f(x0)) check_f(result_f(x0)) check_g(result_g(x0)) check_f(redex_f(x0)) in_f_1(go_up(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) RFCMatchBoundsDPProof (EQUIVALENT) Finiteness of the DP problem can be shown by a matchbound of 5. As the DP problem is minimal we only have to initialize the certificate graph by the rules of P: TOP(go_up(x)) -> TOP(reduce(x)) To find matches we regarded all rules of R and P: reduce(f(x_1)) -> check_f(redex_f(x_1)) reduce(g(x_1)) -> check_g(redex_g(x_1)) redex_g(x) -> result_g(f(f(x))) check_g(result_g(x)) -> go_up(x) redex_f(g(x)) -> result_f(g(g(x))) redex_f(f(x)) -> result_f(x) check_f(result_f(x)) -> go_up(x) check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) TOP(go_up(x)) -> TOP(reduce(x)) The certificate found is represented by the following graph. The certificate consists of the following enumerated nodes: 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163 Node 137 is start node and node 138 is final node. Those nodes are connected through the following edges: * 137 to 139 labelled TOP_1(0)* 137 to 147 labelled TOP_1(1)* 137 to 146 labelled TOP_1(2)* 137 to 154 labelled TOP_1(3)* 137 to 156 labelled TOP_1(4)* 137 to 161 labelled TOP_1(5)* 138 to 138 labelled #_1(0)* 139 to 138 labelled reduce_1(0), go_up_1(2)* 139 to 140 labelled check_f_1(1)* 139 to 141 labelled check_g_1(1)* 139 to 146 labelled in_f_1_1(2)* 139 to 144 labelled go_up_1(2)* 139 to 142 labelled go_up_1(2)* 140 to 138 labelled redex_f_1(1), result_f_1(1)* 140 to 144 labelled result_f_1(1)* 141 to 138 labelled redex_g_1(1)* 141 to 142 labelled result_g_1(2)* 142 to 143 labelled f_1(2)* 143 to 138 labelled f_1(2)* 144 to 145 labelled g_1(1)* 145 to 138 labelled g_1(1)* 146 to 138 labelled reduce_1(2), go_up_1(2), go_up_1(4)* 146 to 140 labelled check_f_1(1)* 146 to 141 labelled check_g_1(1)* 146 to 146 labelled in_f_1_1(2)* 146 to 144 labelled go_up_1(2), reduce_1(2)* 146 to 142 labelled go_up_1(2), reduce_1(2)* 146 to 150 labelled reduce_1(2), go_up_1(3)* 146 to 148 labelled check_g_1(2)* 146 to 155 labelled check_f_1(3)* 146 to 157 labelled in_f_1_1(4)* 146 to 145 labelled go_up_1(4)* 147 to 138 labelled reduce_1(1), go_up_1(2), go_up_1(3)* 147 to 144 labelled reduce_1(1), go_up_1(2)* 147 to 142 labelled reduce_1(1), go_up_1(2)* 147 to 140 labelled check_f_1(1)* 147 to 141 labelled check_g_1(1)* 147 to 148 labelled check_g_1(2)* 147 to 149 labelled check_f_1(2)* 147 to 146 labelled in_f_1_1(2)* 147 to 152 labelled in_f_1_1(3)* 147 to 150 labelled go_up_1(3)* 148 to 145 labelled redex_g_1(2)* 148 to 150 labelled result_g_1(3)* 148 to 138 labelled redex_g_1(2)* 149 to 143 labelled redex_f_1(2)* 149 to 138 labelled result_f_1(3)* 150 to 151 labelled f_1(3)* 151 to 145 labelled f_1(3)* 151 to 138 labelled f_1(3)* 152 to 143 labelled reduce_1(3)* 152 to 153 labelled check_f_1(3)* 152 to 156 labelled in_f_1_1(4)* 152 to 138 labelled go_up_1(2)* 152 to 144 labelled go_up_1(2)* 153 to 138 labelled redex_f_1(3), result_f_1(1)* 153 to 144 labelled result_f_1(1)* 154 to 138 labelled reduce_1(3), go_up_1(2), go_up_1(4), go_up_1(5)* 154 to 144 labelled reduce_1(3), go_up_1(2)* 154 to 142 labelled reduce_1(3), go_up_1(2)* 154 to 140 labelled check_f_1(1)* 154 to 141 labelled check_g_1(1)* 154 to 148 labelled check_g_1(2)* 154 to 155 labelled check_f_1(3)* 154 to 150 labelled reduce_1(3), go_up_1(3)* 154 to 146 labelled in_f_1_1(2)* 154 to 157 labelled in_f_1_1(4)* 154 to 158 labelled check_f_1(4)* 154 to 145 labelled go_up_1(4), reduce_1(3), go_up_1(5)* 154 to 160 labelled in_f_1_1(5)* 155 to 143 labelled redex_f_1(3)* 155 to 151 labelled redex_f_1(3)* 155 to 138 labelled result_f_1(3), result_f_1(4)* 155 to 145 labelled result_f_1(4)* 156 to 138 labelled reduce_1(4), go_up_1(2), go_up_1(5)* 156 to 140 labelled check_f_1(1)* 156 to 141 labelled check_g_1(1)* 156 to 146 labelled in_f_1_1(2)* 156 to 144 labelled go_up_1(2)* 156 to 142 labelled go_up_1(2)* 156 to 150 labelled reduce_1(4), go_up_1(3)* 156 to 145 labelled reduce_1(4), go_up_1(5)* 156 to 158 labelled check_f_1(4)* 156 to 160 labelled in_f_1_1(5)* 156 to 148 labelled check_g_1(2)* 157 to 143 labelled reduce_1(4)* 157 to 151 labelled reduce_1(4)* 157 to 153 labelled check_f_1(3)* 157 to 156 labelled in_f_1_1(4)* 157 to 138 labelled go_up_1(2)* 157 to 144 labelled go_up_1(2)* 157 to 159 labelled check_f_1(4)* 157 to 161 labelled in_f_1_1(5)* 157 to 162 labelled go_up_1(3)* 158 to 151 labelled redex_f_1(4)* 158 to 145 labelled result_f_1(4)* 158 to 138 labelled result_f_1(4)* 159 to 145 labelled redex_f_1(4)* 159 to 162 labelled result_f_1(2)* 159 to 138 labelled redex_f_1(4), result_f_1(1)* 159 to 144 labelled result_f_1(1)* 160 to 151 labelled reduce_1(5)* 160 to 159 labelled check_f_1(4)* 160 to 161 labelled in_f_1_1(5)* 160 to 162 labelled go_up_1(3)* 160 to 138 labelled go_up_1(2)* 160 to 144 labelled go_up_1(2)* 161 to 145 labelled reduce_1(5)* 161 to 148 labelled check_g_1(2)* 161 to 150 labelled go_up_1(3)* 161 to 138 labelled reduce_1(5), go_up_1(2)* 161 to 140 labelled check_f_1(1)* 161 to 141 labelled check_g_1(1)* 161 to 146 labelled in_f_1_1(2)* 161 to 144 labelled go_up_1(2)* 161 to 142 labelled go_up_1(2)* 162 to 163 labelled g_1(2)* 163 to 138 labelled g_1(2) ---------------------------------------- (12) YES