5.82/2.23 YES 5.82/2.24 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 5.82/2.24 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.82/2.24 5.82/2.24 5.82/2.24 Outermost Termination of the given OTRS could be proven: 5.82/2.24 5.82/2.24 (0) OTRS 5.82/2.24 (1) Thiemann-SpecialC-Transformation [EQUIVALENT, 0 ms] 5.82/2.24 (2) QTRS 5.82/2.24 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 5.82/2.24 (4) QDP 5.82/2.24 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.82/2.24 (6) QDP 5.82/2.24 (7) UsableRulesProof [EQUIVALENT, 0 ms] 5.82/2.24 (8) QDP 5.82/2.24 (9) QReductionProof [EQUIVALENT, 0 ms] 5.82/2.24 (10) QDP 5.82/2.24 (11) RFCMatchBoundsDPProof [EQUIVALENT, 16 ms] 5.82/2.24 (12) YES 5.82/2.24 5.82/2.24 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (0) 5.82/2.24 Obligation: 5.82/2.24 Term rewrite system R: 5.82/2.24 The TRS R consists of the following rules: 5.82/2.24 5.82/2.24 f(g(x)) -> g(g(x)) 5.82/2.24 g(x) -> f(f(x)) 5.82/2.24 f(f(x)) -> x 5.82/2.24 5.82/2.24 5.82/2.24 5.82/2.24 Outermost Strategy. 5.82/2.24 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (1) Thiemann-SpecialC-Transformation (EQUIVALENT) 5.82/2.24 We applied the Thiemann-SpecialC transformation to transform the outermost TRS to an innermost TRS. 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (2) 5.82/2.24 Obligation: 5.82/2.24 Q restricted rewrite system: 5.82/2.24 The TRS R consists of the following rules: 5.82/2.24 5.82/2.24 top(go_up(x)) -> top(reduce(x)) 5.82/2.24 reduce(f(x_1)) -> check_f(redex_f(x_1)) 5.82/2.24 reduce(g(x_1)) -> check_g(redex_g(x_1)) 5.82/2.24 redex_f(g(x)) -> result_f(g(g(x))) 5.82/2.24 redex_g(x) -> result_g(f(f(x))) 5.82/2.24 redex_f(f(x)) -> result_f(x) 5.82/2.24 check_f(result_f(x)) -> go_up(x) 5.82/2.24 check_g(result_g(x)) -> go_up(x) 5.82/2.24 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 5.82/2.24 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 5.82/2.24 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 5.82/2.24 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 5.82/2.24 5.82/2.24 The set Q consists of the following terms: 5.82/2.24 5.82/2.24 top(go_up(x0)) 5.82/2.24 reduce(f(x0)) 5.82/2.24 reduce(g(x0)) 5.82/2.24 redex_f(g(x0)) 5.82/2.24 redex_g(x0) 5.82/2.24 redex_f(f(x0)) 5.82/2.24 check_f(result_f(x0)) 5.82/2.24 check_g(result_g(x0)) 5.82/2.24 check_f(redex_f(x0)) 5.82/2.24 in_f_1(go_up(x0)) 5.82/2.24 in_g_1(go_up(x0)) 5.82/2.24 5.82/2.24 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (3) DependencyPairsProof (EQUIVALENT) 5.82/2.24 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (4) 5.82/2.24 Obligation: 5.82/2.24 Q DP problem: 5.82/2.24 The TRS P consists of the following rules: 5.82/2.24 5.82/2.24 TOP(go_up(x)) -> TOP(reduce(x)) 5.82/2.24 TOP(go_up(x)) -> REDUCE(x) 5.82/2.24 REDUCE(f(x_1)) -> CHECK_F(redex_f(x_1)) 5.82/2.24 REDUCE(f(x_1)) -> REDEX_F(x_1) 5.82/2.24 REDUCE(g(x_1)) -> CHECK_G(redex_g(x_1)) 5.82/2.24 REDUCE(g(x_1)) -> REDEX_G(x_1) 5.82/2.24 CHECK_F(redex_f(x_1)) -> IN_F_1(reduce(x_1)) 5.82/2.24 CHECK_F(redex_f(x_1)) -> REDUCE(x_1) 5.82/2.24 CHECK_G(redex_g(x_1)) -> IN_G_1(reduce(x_1)) 5.82/2.24 CHECK_G(redex_g(x_1)) -> REDUCE(x_1) 5.82/2.24 5.82/2.24 The TRS R consists of the following rules: 5.82/2.24 5.82/2.24 top(go_up(x)) -> top(reduce(x)) 5.82/2.24 reduce(f(x_1)) -> check_f(redex_f(x_1)) 5.82/2.24 reduce(g(x_1)) -> check_g(redex_g(x_1)) 5.82/2.24 redex_f(g(x)) -> result_f(g(g(x))) 5.82/2.24 redex_g(x) -> result_g(f(f(x))) 5.82/2.24 redex_f(f(x)) -> result_f(x) 5.82/2.24 check_f(result_f(x)) -> go_up(x) 5.82/2.24 check_g(result_g(x)) -> go_up(x) 5.82/2.24 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 5.82/2.24 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 5.82/2.24 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 5.82/2.24 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 5.82/2.24 5.82/2.24 The set Q consists of the following terms: 5.82/2.24 5.82/2.24 top(go_up(x0)) 5.82/2.24 reduce(f(x0)) 5.82/2.24 reduce(g(x0)) 5.82/2.24 redex_f(g(x0)) 5.82/2.24 redex_g(x0) 5.82/2.24 redex_f(f(x0)) 5.82/2.24 check_f(result_f(x0)) 5.82/2.24 check_g(result_g(x0)) 5.82/2.24 check_f(redex_f(x0)) 5.82/2.24 in_f_1(go_up(x0)) 5.82/2.24 in_g_1(go_up(x0)) 5.82/2.24 5.82/2.24 We have to consider all minimal (P,Q,R)-chains. 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (5) DependencyGraphProof (EQUIVALENT) 5.82/2.24 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 9 less nodes. 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (6) 5.82/2.24 Obligation: 5.82/2.24 Q DP problem: 5.82/2.24 The TRS P consists of the following rules: 5.82/2.24 5.82/2.24 TOP(go_up(x)) -> TOP(reduce(x)) 5.82/2.24 5.82/2.24 The TRS R consists of the following rules: 5.82/2.24 5.82/2.24 top(go_up(x)) -> top(reduce(x)) 5.82/2.24 reduce(f(x_1)) -> check_f(redex_f(x_1)) 5.82/2.24 reduce(g(x_1)) -> check_g(redex_g(x_1)) 5.82/2.24 redex_f(g(x)) -> result_f(g(g(x))) 5.82/2.24 redex_g(x) -> result_g(f(f(x))) 5.82/2.24 redex_f(f(x)) -> result_f(x) 5.82/2.24 check_f(result_f(x)) -> go_up(x) 5.82/2.24 check_g(result_g(x)) -> go_up(x) 5.82/2.24 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 5.82/2.24 check_g(redex_g(x_1)) -> in_g_1(reduce(x_1)) 5.82/2.24 in_f_1(go_up(x_1)) -> go_up(f(x_1)) 5.82/2.24 in_g_1(go_up(x_1)) -> go_up(g(x_1)) 5.82/2.24 5.82/2.24 The set Q consists of the following terms: 5.82/2.24 5.82/2.24 top(go_up(x0)) 5.82/2.24 reduce(f(x0)) 5.82/2.24 reduce(g(x0)) 5.82/2.24 redex_f(g(x0)) 5.82/2.24 redex_g(x0) 5.82/2.24 redex_f(f(x0)) 5.82/2.24 check_f(result_f(x0)) 5.82/2.24 check_g(result_g(x0)) 5.82/2.24 check_f(redex_f(x0)) 5.82/2.24 in_f_1(go_up(x0)) 5.82/2.24 in_g_1(go_up(x0)) 5.82/2.24 5.82/2.24 We have to consider all minimal (P,Q,R)-chains. 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (7) UsableRulesProof (EQUIVALENT) 5.82/2.24 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. 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (8) 5.82/2.24 Obligation: 5.82/2.24 Q DP problem: 5.82/2.24 The TRS P consists of the following rules: 5.82/2.24 5.82/2.24 TOP(go_up(x)) -> TOP(reduce(x)) 5.82/2.24 5.82/2.24 The TRS R consists of the following rules: 5.82/2.24 5.82/2.24 reduce(f(x_1)) -> check_f(redex_f(x_1)) 5.82/2.24 reduce(g(x_1)) -> check_g(redex_g(x_1)) 5.82/2.24 redex_g(x) -> result_g(f(f(x))) 5.82/2.24 check_g(result_g(x)) -> go_up(x) 5.82/2.24 redex_f(g(x)) -> result_f(g(g(x))) 5.82/2.24 redex_f(f(x)) -> result_f(x) 5.82/2.24 check_f(result_f(x)) -> go_up(x) 5.82/2.24 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 5.82/2.24 5.82/2.24 The set Q consists of the following terms: 5.82/2.24 5.82/2.24 top(go_up(x0)) 5.82/2.24 reduce(f(x0)) 5.82/2.24 reduce(g(x0)) 5.82/2.24 redex_f(g(x0)) 5.82/2.24 redex_g(x0) 5.82/2.24 redex_f(f(x0)) 5.82/2.24 check_f(result_f(x0)) 5.82/2.24 check_g(result_g(x0)) 5.82/2.24 check_f(redex_f(x0)) 5.82/2.24 in_f_1(go_up(x0)) 5.82/2.24 in_g_1(go_up(x0)) 5.82/2.24 5.82/2.24 We have to consider all minimal (P,Q,R)-chains. 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (9) QReductionProof (EQUIVALENT) 5.82/2.24 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.82/2.24 5.82/2.24 top(go_up(x0)) 5.82/2.24 in_g_1(go_up(x0)) 5.82/2.24 5.82/2.24 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (10) 5.82/2.24 Obligation: 5.82/2.24 Q DP problem: 5.82/2.24 The TRS P consists of the following rules: 5.82/2.24 5.82/2.24 TOP(go_up(x)) -> TOP(reduce(x)) 5.82/2.24 5.82/2.24 The TRS R consists of the following rules: 5.82/2.24 5.82/2.24 reduce(f(x_1)) -> check_f(redex_f(x_1)) 5.82/2.24 reduce(g(x_1)) -> check_g(redex_g(x_1)) 5.82/2.24 redex_g(x) -> result_g(f(f(x))) 5.82/2.24 check_g(result_g(x)) -> go_up(x) 5.82/2.24 redex_f(g(x)) -> result_f(g(g(x))) 5.82/2.24 redex_f(f(x)) -> result_f(x) 5.82/2.24 check_f(result_f(x)) -> go_up(x) 5.82/2.24 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 5.82/2.24 5.82/2.24 The set Q consists of the following terms: 5.82/2.24 5.82/2.24 reduce(f(x0)) 5.82/2.24 reduce(g(x0)) 5.82/2.24 redex_f(g(x0)) 5.82/2.24 redex_g(x0) 5.82/2.24 redex_f(f(x0)) 5.82/2.24 check_f(result_f(x0)) 5.82/2.24 check_g(result_g(x0)) 5.82/2.24 check_f(redex_f(x0)) 5.82/2.24 in_f_1(go_up(x0)) 5.82/2.24 5.82/2.24 We have to consider all minimal (P,Q,R)-chains. 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (11) RFCMatchBoundsDPProof (EQUIVALENT) 5.82/2.24 Finiteness of the DP problem can be shown by a matchbound of 5. 5.82/2.24 As the DP problem is minimal we only have to initialize the certificate graph by the rules of P: 5.82/2.24 5.82/2.24 TOP(go_up(x)) -> TOP(reduce(x)) 5.82/2.24 5.82/2.24 To find matches we regarded all rules of R and P: 5.82/2.24 5.82/2.24 reduce(f(x_1)) -> check_f(redex_f(x_1)) 5.82/2.24 reduce(g(x_1)) -> check_g(redex_g(x_1)) 5.82/2.24 redex_g(x) -> result_g(f(f(x))) 5.82/2.24 check_g(result_g(x)) -> go_up(x) 5.82/2.24 redex_f(g(x)) -> result_f(g(g(x))) 5.82/2.24 redex_f(f(x)) -> result_f(x) 5.82/2.24 check_f(result_f(x)) -> go_up(x) 5.82/2.24 check_f(redex_f(x_1)) -> in_f_1(reduce(x_1)) 5.82/2.24 TOP(go_up(x)) -> TOP(reduce(x)) 5.82/2.24 5.82/2.24 The certificate found is represented by the following graph. 5.82/2.24 The certificate consists of the following enumerated nodes: 5.82/2.24 124, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191 5.82/2.24 5.82/2.24 Node 124 is start node and node 145 is final node. 5.82/2.24 5.82/2.24 Those nodes are connected through the following edges: 5.82/2.24 5.82/2.24 * 124 to 146 labelled TOP_1(0)* 124 to 154 labelled TOP_1(1)* 124 to 153 labelled TOP_1(2)* 124 to 182 labelled TOP_1(3)* 124 to 184 labelled TOP_1(4)* 124 to 189 labelled TOP_1(5)* 145 to 145 labelled #_1(0)* 146 to 145 labelled reduce_1(0), go_up_1(2)* 146 to 147 labelled check_f_1(1)* 146 to 148 labelled check_g_1(1)* 146 to 153 labelled in_f_1_1(2)* 146 to 151 labelled go_up_1(2)* 146 to 149 labelled go_up_1(2)* 147 to 145 labelled redex_f_1(1), result_f_1(1)* 147 to 151 labelled result_f_1(1)* 148 to 145 labelled redex_g_1(1)* 148 to 149 labelled result_g_1(2)* 149 to 150 labelled f_1(2)* 150 to 145 labelled f_1(2)* 151 to 152 labelled g_1(1)* 152 to 145 labelled g_1(1)* 153 to 145 labelled reduce_1(2), go_up_1(2), go_up_1(4)* 153 to 147 labelled check_f_1(1)* 153 to 148 labelled check_g_1(1)* 153 to 153 labelled in_f_1_1(2)* 153 to 151 labelled go_up_1(2), reduce_1(2)* 153 to 149 labelled go_up_1(2), reduce_1(2)* 153 to 157 labelled reduce_1(2), go_up_1(3)* 153 to 155 labelled check_g_1(2)* 153 to 183 labelled check_f_1(3)* 153 to 185 labelled in_f_1_1(4)* 153 to 152 labelled go_up_1(4)* 154 to 145 labelled reduce_1(1), go_up_1(2), go_up_1(3)* 154 to 151 labelled reduce_1(1), go_up_1(2)* 154 to 149 labelled reduce_1(1), go_up_1(2)* 154 to 147 labelled check_f_1(1)* 154 to 148 labelled check_g_1(1)* 154 to 155 labelled check_g_1(2)* 154 to 156 labelled check_f_1(2)* 154 to 153 labelled in_f_1_1(2)* 154 to 159 labelled in_f_1_1(3)* 154 to 157 labelled go_up_1(3)* 155 to 152 labelled redex_g_1(2)* 155 to 157 labelled result_g_1(3)* 155 to 145 labelled redex_g_1(2)* 156 to 150 labelled redex_f_1(2)* 156 to 145 labelled result_f_1(3)* 157 to 158 labelled f_1(3)* 158 to 152 labelled f_1(3)* 158 to 145 labelled f_1(3)* 159 to 150 labelled reduce_1(3)* 159 to 160 labelled check_f_1(3)* 159 to 184 labelled in_f_1_1(4)* 159 to 145 labelled go_up_1(2)* 159 to 151 labelled go_up_1(2)* 160 to 145 labelled redex_f_1(3), result_f_1(1)* 160 to 151 labelled result_f_1(1)* 182 to 145 labelled reduce_1(3), go_up_1(2), go_up_1(4), go_up_1(5)* 182 to 151 labelled reduce_1(3), go_up_1(2)* 182 to 149 labelled reduce_1(3), go_up_1(2)* 182 to 147 labelled check_f_1(1)* 182 to 148 labelled check_g_1(1)* 182 to 155 labelled check_g_1(2)* 182 to 183 labelled check_f_1(3)* 182 to 157 labelled reduce_1(3), go_up_1(3)* 182 to 153 labelled in_f_1_1(2)* 182 to 185 labelled in_f_1_1(4)* 182 to 186 labelled check_f_1(4)* 182 to 152 labelled go_up_1(4), reduce_1(3), go_up_1(5)* 182 to 188 labelled in_f_1_1(5)* 183 to 150 labelled redex_f_1(3)* 183 to 158 labelled redex_f_1(3)* 183 to 145 labelled result_f_1(3), result_f_1(4)* 183 to 152 labelled result_f_1(4)* 184 to 145 labelled reduce_1(4), go_up_1(2), go_up_1(5)* 184 to 147 labelled check_f_1(1)* 184 to 148 labelled check_g_1(1)* 184 to 153 labelled in_f_1_1(2)* 184 to 151 labelled go_up_1(2)* 184 to 149 labelled go_up_1(2)* 184 to 157 labelled reduce_1(4), go_up_1(3)* 184 to 152 labelled reduce_1(4), go_up_1(5)* 184 to 186 labelled check_f_1(4)* 184 to 188 labelled in_f_1_1(5)* 184 to 155 labelled check_g_1(2)* 185 to 150 labelled reduce_1(4)* 185 to 158 labelled reduce_1(4)* 185 to 160 labelled check_f_1(3)* 185 to 184 labelled in_f_1_1(4)* 185 to 145 labelled go_up_1(2)* 185 to 151 labelled go_up_1(2)* 185 to 187 labelled check_f_1(4)* 185 to 189 labelled in_f_1_1(5)* 185 to 190 labelled go_up_1(3)* 186 to 158 labelled redex_f_1(4)* 186 to 152 labelled result_f_1(4)* 186 to 145 labelled result_f_1(4)* 187 to 152 labelled redex_f_1(4)* 187 to 190 labelled result_f_1(2)* 187 to 145 labelled redex_f_1(4), result_f_1(1)* 187 to 151 labelled result_f_1(1)* 188 to 158 labelled reduce_1(5)* 188 to 187 labelled check_f_1(4)* 188 to 189 labelled in_f_1_1(5)* 188 to 190 labelled go_up_1(3)* 188 to 145 labelled go_up_1(2)* 188 to 151 labelled go_up_1(2)* 189 to 152 labelled reduce_1(5)* 189 to 155 labelled check_g_1(2)* 189 to 157 labelled go_up_1(3)* 189 to 145 labelled reduce_1(5), go_up_1(2)* 189 to 147 labelled check_f_1(1)* 189 to 148 labelled check_g_1(1)* 189 to 153 labelled in_f_1_1(2)* 189 to 151 labelled go_up_1(2)* 189 to 149 labelled go_up_1(2)* 190 to 191 labelled g_1(2)* 191 to 145 labelled g_1(2) 5.82/2.24 5.82/2.24 5.82/2.24 ---------------------------------------- 5.82/2.24 5.82/2.24 (12) 5.82/2.24 YES 6.17/2.42 EOF