3.57/1.67 YES 3.70/1.74 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.70/1.74 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.70/1.74 3.70/1.74 3.70/1.74 Termination w.r.t. Q of the given QTRS could be proven: 3.70/1.74 3.70/1.74 (0) QTRS 3.70/1.74 (1) QTRS Reverse [EQUIVALENT, 0 ms] 3.70/1.74 (2) QTRS 3.70/1.74 (3) Strip Symbols Proof [SOUND, 0 ms] 3.70/1.74 (4) QTRS 3.70/1.74 (5) RFCMatchBoundsTRSProof [EQUIVALENT, 0 ms] 3.70/1.74 (6) YES 3.70/1.74 3.70/1.74 3.70/1.74 ---------------------------------------- 3.70/1.74 3.70/1.74 (0) 3.70/1.74 Obligation: 3.70/1.74 Q restricted rewrite system: 3.70/1.74 The TRS R consists of the following rules: 3.70/1.74 3.70/1.74 a(b(b(b(a(a(a(a(a(x1))))))))) -> a(a(a(a(a(a(b(b(b(a(a(b(b(b(x1)))))))))))))) 3.70/1.74 3.70/1.74 Q is empty. 3.70/1.74 3.70/1.74 ---------------------------------------- 3.70/1.74 3.70/1.74 (1) QTRS Reverse (EQUIVALENT) 3.70/1.74 We applied the QTRS Reverse Processor [REVERSE]. 3.70/1.74 ---------------------------------------- 3.70/1.74 3.70/1.74 (2) 3.70/1.74 Obligation: 3.70/1.74 Q restricted rewrite system: 3.70/1.74 The TRS R consists of the following rules: 3.70/1.74 3.70/1.74 a(a(a(a(a(b(b(b(a(x1))))))))) -> b(b(b(a(a(b(b(b(a(a(a(a(a(a(x1)))))))))))))) 3.70/1.74 3.70/1.74 Q is empty. 3.70/1.74 3.70/1.74 ---------------------------------------- 3.70/1.74 3.70/1.74 (3) Strip Symbols Proof (SOUND) 3.70/1.74 We were given the following TRS: 3.70/1.74 3.70/1.74 a(a(a(a(a(b(b(b(a(x1))))))))) -> b(b(b(a(a(b(b(b(a(a(a(a(a(a(x1)))))))))))))) 3.70/1.74 3.70/1.74 By stripping symbols from the only rule of the system, we obtained the following TRS [ENDRULLIS]: 3.70/1.74 3.70/1.74 a(a(a(a(a(b(b(b(x)))))))) -> b(b(b(a(a(b(b(b(a(a(a(a(a(x))))))))))))) 3.70/1.74 3.70/1.74 ---------------------------------------- 3.70/1.74 3.70/1.74 (4) 3.70/1.74 Obligation: 3.70/1.74 Q restricted rewrite system: 3.70/1.74 The TRS R consists of the following rules: 3.70/1.74 3.70/1.74 a(a(a(a(a(b(b(b(x)))))))) -> b(b(b(a(a(b(b(b(a(a(a(a(a(x))))))))))))) 3.70/1.74 3.70/1.74 Q is empty. 3.70/1.74 3.70/1.74 ---------------------------------------- 3.70/1.74 3.70/1.74 (5) RFCMatchBoundsTRSProof (EQUIVALENT) 3.70/1.74 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. This implies Q-termination of R. 3.70/1.74 The following rules were used to construct the certificate: 3.70/1.74 3.70/1.74 a(a(a(a(a(b(b(b(x)))))))) -> b(b(b(a(a(b(b(b(a(a(a(a(a(x))))))))))))) 3.70/1.74 3.70/1.74 The certificate found is represented by the following graph. 3.70/1.74 The certificate consists of the following enumerated nodes: 3.70/1.74 136, 137, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173 3.70/1.74 3.70/1.74 Node 136 is start node and node 137 is final node. 3.70/1.74 3.70/1.74 Those nodes are connected through the following edges: 3.70/1.74 3.70/1.74 * 136 to 150 labelled b_1(0)* 137 to 137 labelled #_1(0)* 150 to 151 labelled b_1(0)* 151 to 152 labelled b_1(0)* 152 to 153 labelled a_1(0)* 153 to 154 labelled a_1(0)* 154 to 155 labelled b_1(0)* 155 to 156 labelled b_1(0)* 156 to 157 labelled b_1(0)* 157 to 158 labelled a_1(0)* 157 to 162 labelled b_1(1)* 158 to 159 labelled a_1(0)* 158 to 162 labelled b_1(1)* 159 to 160 labelled a_1(0)* 159 to 162 labelled b_1(1)* 160 to 161 labelled a_1(0)* 160 to 162 labelled b_1(1)* 161 to 137 labelled a_1(0)* 161 to 162 labelled b_1(1)* 162 to 163 labelled b_1(1)* 163 to 164 labelled b_1(1)* 164 to 165 labelled a_1(1)* 165 to 166 labelled a_1(1)* 166 to 167 labelled b_1(1)* 167 to 168 labelled b_1(1)* 168 to 169 labelled b_1(1)* 169 to 170 labelled a_1(1)* 169 to 162 labelled b_1(1)* 170 to 171 labelled a_1(1)* 170 to 162 labelled b_1(1)* 171 to 172 labelled a_1(1)* 171 to 162 labelled b_1(1)* 172 to 173 labelled a_1(1)* 172 to 162 labelled b_1(1)* 173 to 137 labelled a_1(1)* 173 to 162 labelled b_1(1) 3.70/1.74 3.70/1.74 3.70/1.74 ---------------------------------------- 3.70/1.74 3.70/1.74 (6) 3.70/1.74 YES 3.92/1.77 EOF