14.14/4.35 YES 14.34/4.41 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 14.34/4.41 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.34/4.41 14.34/4.41 14.34/4.41 Termination of the given RelTRS could be proven: 14.34/4.41 14.34/4.41 (0) RelTRS 14.34/4.41 (1) RelTRSRRRProof [EQUIVALENT, 425 ms] 14.34/4.41 (2) RelTRS 14.34/4.41 (3) SIsEmptyProof [EQUIVALENT, 0 ms] 14.34/4.41 (4) QTRS 14.34/4.41 (5) RFCMatchBoundsTRSProof [EQUIVALENT, 7 ms] 14.34/4.41 (6) YES 14.34/4.41 14.34/4.41 14.34/4.41 ---------------------------------------- 14.34/4.41 14.34/4.41 (0) 14.34/4.41 Obligation: 14.34/4.41 Relative term rewrite system: 14.34/4.41 The relative TRS consists of the following R rules: 14.34/4.41 14.34/4.41 c(b(c(x1))) -> c(a(b(x1))) 14.34/4.41 c(b(b(x1))) -> a(a(c(x1))) 14.34/4.41 a(a(b(x1))) -> b(b(c(x1))) 14.34/4.41 b(b(c(x1))) -> a(b(c(x1))) 14.34/4.41 b(b(b(x1))) -> b(a(b(x1))) 14.34/4.41 14.34/4.41 The relative TRS consists of the following S rules: 14.34/4.41 14.34/4.41 c(b(a(x1))) -> b(a(c(x1))) 14.34/4.41 14.34/4.41 14.34/4.41 ---------------------------------------- 14.34/4.41 14.34/4.41 (1) RelTRSRRRProof (EQUIVALENT) 14.34/4.41 We used the following monotonic ordering for rule removal: 14.34/4.41 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 14.34/4.41 14.34/4.41 <<< 14.34/4.41 POL(c(x_1)) = [[0], [2]] + [[2, 0], [0, 2]] * x_1 14.34/4.41 >>> 14.34/4.41 14.34/4.41 <<< 14.34/4.41 POL(b(x_1)) = [[2], [0]] + [[2, 2], [0, 0]] * x_1 14.34/4.41 >>> 14.34/4.41 14.34/4.41 <<< 14.34/4.41 POL(a(x_1)) = [[2], [0]] + [[2, 0], [0, 0]] * x_1 14.34/4.41 >>> 14.34/4.41 14.34/4.41 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 14.34/4.41 Rules from R: 14.34/4.41 14.34/4.41 c(b(b(x1))) -> a(a(c(x1))) 14.34/4.41 Rules from S: 14.34/4.41 14.34/4.41 c(b(a(x1))) -> b(a(c(x1))) 14.34/4.41 14.34/4.41 14.34/4.41 14.34/4.41 14.34/4.41 ---------------------------------------- 14.34/4.41 14.34/4.41 (2) 14.34/4.41 Obligation: 14.34/4.41 Relative term rewrite system: 14.34/4.41 The relative TRS consists of the following R rules: 14.34/4.41 14.34/4.41 c(b(c(x1))) -> c(a(b(x1))) 14.34/4.41 a(a(b(x1))) -> b(b(c(x1))) 14.34/4.41 b(b(c(x1))) -> a(b(c(x1))) 14.34/4.41 b(b(b(x1))) -> b(a(b(x1))) 14.34/4.41 14.34/4.41 S is empty. 14.34/4.41 14.34/4.41 ---------------------------------------- 14.34/4.41 14.34/4.41 (3) SIsEmptyProof (EQUIVALENT) 14.34/4.41 The TRS S is empty. Hence, termination of R/S is equivalent to termination of R. 14.34/4.41 ---------------------------------------- 14.34/4.41 14.34/4.41 (4) 14.34/4.41 Obligation: 14.34/4.41 Q restricted rewrite system: 14.34/4.41 The TRS R consists of the following rules: 14.34/4.41 14.34/4.41 c(b(c(x1))) -> c(a(b(x1))) 14.34/4.41 a(a(b(x1))) -> b(b(c(x1))) 14.34/4.41 b(b(c(x1))) -> a(b(c(x1))) 14.34/4.41 b(b(b(x1))) -> b(a(b(x1))) 14.34/4.41 14.34/4.41 Q is empty. 14.34/4.41 14.34/4.41 ---------------------------------------- 14.34/4.41 14.34/4.41 (5) RFCMatchBoundsTRSProof (EQUIVALENT) 14.34/4.41 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 3. This implies Q-termination of R. 14.34/4.41 The following rules were used to construct the certificate: 14.34/4.41 14.34/4.41 c(b(c(x1))) -> c(a(b(x1))) 14.34/4.41 a(a(b(x1))) -> b(b(c(x1))) 14.34/4.41 b(b(c(x1))) -> a(b(c(x1))) 14.34/4.41 b(b(b(x1))) -> b(a(b(x1))) 14.34/4.41 14.34/4.41 The certificate found is represented by the following graph. 14.34/4.41 The certificate consists of the following enumerated nodes: 14.34/4.41 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162 14.34/4.41 14.34/4.41 Node 143 is start node and node 144 is final node. 14.34/4.41 14.34/4.41 Those nodes are connected through the following edges: 14.34/4.41 14.34/4.41 * 143 to 145 labelled c_1(0), b_1(0)* 143 to 147 labelled b_1(0), a_1(0)* 143 to 149 labelled a_1(1)* 143 to 155 labelled b_1(1)* 144 to 144 labelled #_1(0)* 145 to 146 labelled a_1(0)* 145 to 153 labelled b_1(1)* 145 to 157 labelled a_1(2)* 146 to 144 labelled b_1(0)* 146 to 149 labelled a_1(1)* 146 to 151 labelled b_1(1), b_1(2)* 146 to 145 labelled b_1(2)* 146 to 161 labelled b_1(3)* 147 to 148 labelled b_1(0)* 148 to 144 labelled c_1(0)* 148 to 151 labelled c_1(1)* 149 to 150 labelled b_1(1)* 150 to 144 labelled c_1(1)* 150 to 151 labelled c_1(1)* 151 to 152 labelled a_1(1)* 151 to 157 labelled b_1(2), a_1(2)* 151 to 159 labelled a_1(3)* 152 to 144 labelled b_1(1)* 152 to 149 labelled a_1(1)* 152 to 151 labelled b_1(1), b_1(2)* 152 to 145 labelled b_1(2)* 152 to 161 labelled b_1(3)* 153 to 154 labelled b_1(1)* 154 to 150 labelled c_1(1)* 155 to 156 labelled a_1(1)* 156 to 154 labelled b_1(1)* 157 to 158 labelled b_1(2)* 157 to 154 labelled b_1(2)* 158 to 150 labelled c_1(2)* 159 to 160 labelled b_1(3)* 160 to 150 labelled c_1(3)* 161 to 162 labelled a_1(3)* 162 to 158 labelled b_1(3)* 162 to 154 labelled b_1(3) 14.34/4.41 14.34/4.41 14.34/4.41 ---------------------------------------- 14.34/4.41 14.34/4.41 (6) 14.34/4.41 YES 14.49/4.51 EOF