4.01/1.79 YES 4.10/1.81 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.10/1.81 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.10/1.81 4.10/1.81 4.10/1.81 Termination w.r.t. Q of the given QTRS could be proven: 4.10/1.81 4.10/1.81 (0) QTRS 4.10/1.81 (1) QTRS Reverse [EQUIVALENT, 0 ms] 4.10/1.81 (2) QTRS 4.10/1.81 (3) Strip Symbols Proof [SOUND, 0 ms] 4.10/1.81 (4) QTRS 4.10/1.81 (5) RFCMatchBoundsTRSProof [EQUIVALENT, 0 ms] 4.10/1.81 (6) YES 4.10/1.81 4.10/1.81 4.10/1.81 ---------------------------------------- 4.10/1.81 4.10/1.81 (0) 4.10/1.81 Obligation: 4.10/1.81 Q restricted rewrite system: 4.10/1.81 The TRS R consists of the following rules: 4.10/1.81 4.10/1.81 a(b(b(b(a(a(a(a(x1)))))))) -> a(a(a(a(a(b(b(b(a(a(a(b(b(b(x1)))))))))))))) 4.10/1.81 4.10/1.81 Q is empty. 4.10/1.81 4.10/1.81 ---------------------------------------- 4.10/1.81 4.10/1.81 (1) QTRS Reverse (EQUIVALENT) 4.10/1.81 We applied the QTRS Reverse Processor [REVERSE]. 4.10/1.81 ---------------------------------------- 4.10/1.81 4.10/1.81 (2) 4.10/1.81 Obligation: 4.10/1.81 Q restricted rewrite system: 4.10/1.81 The TRS R consists of the following rules: 4.10/1.81 4.10/1.81 a(a(a(a(b(b(b(a(x1)))))))) -> b(b(b(a(a(a(b(b(b(a(a(a(a(a(x1)))))))))))))) 4.10/1.81 4.10/1.81 Q is empty. 4.10/1.81 4.10/1.81 ---------------------------------------- 4.10/1.81 4.10/1.81 (3) Strip Symbols Proof (SOUND) 4.10/1.81 We were given the following TRS: 4.10/1.81 4.10/1.81 a(a(a(a(b(b(b(a(x1)))))))) -> b(b(b(a(a(a(b(b(b(a(a(a(a(a(x1)))))))))))))) 4.10/1.81 4.10/1.81 By stripping symbols from the only rule of the system, we obtained the following TRS [ENDRULLIS]: 4.10/1.81 4.10/1.81 a(a(a(a(b(b(b(x))))))) -> b(b(b(a(a(a(b(b(b(a(a(a(a(x))))))))))))) 4.10/1.81 4.10/1.81 ---------------------------------------- 4.10/1.81 4.10/1.81 (4) 4.10/1.81 Obligation: 4.10/1.81 Q restricted rewrite system: 4.10/1.81 The TRS R consists of the following rules: 4.10/1.81 4.10/1.81 a(a(a(a(b(b(b(x))))))) -> b(b(b(a(a(a(b(b(b(a(a(a(a(x))))))))))))) 4.10/1.81 4.10/1.81 Q is empty. 4.10/1.81 4.10/1.81 ---------------------------------------- 4.10/1.81 4.10/1.81 (5) RFCMatchBoundsTRSProof (EQUIVALENT) 4.10/1.81 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. This implies Q-termination of R. 4.10/1.81 The following rules were used to construct the certificate: 4.10/1.81 4.10/1.81 a(a(a(a(b(b(b(x))))))) -> b(b(b(a(a(a(b(b(b(a(a(a(a(x))))))))))))) 4.10/1.81 4.10/1.81 The certificate found is represented by the following graph. 4.10/1.81 The certificate consists of the following enumerated nodes: 4.10/1.81 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302 4.10/1.81 4.10/1.81 Node 277 is start node and node 278 is final node. 4.10/1.81 4.10/1.81 Those nodes are connected through the following edges: 4.10/1.81 4.10/1.81 * 277 to 279 labelled b_1(0)* 278 to 278 labelled #_1(0)* 279 to 280 labelled b_1(0)* 280 to 281 labelled b_1(0)* 281 to 282 labelled a_1(0)* 282 to 283 labelled a_1(0)* 283 to 284 labelled a_1(0)* 284 to 285 labelled b_1(0)* 285 to 286 labelled b_1(0)* 286 to 287 labelled b_1(0)* 287 to 288 labelled a_1(0)* 287 to 291 labelled b_1(1)* 288 to 289 labelled a_1(0)* 288 to 291 labelled b_1(1)* 289 to 290 labelled a_1(0)* 289 to 291 labelled b_1(1)* 290 to 278 labelled a_1(0)* 290 to 291 labelled b_1(1)* 291 to 292 labelled b_1(1)* 292 to 293 labelled b_1(1)* 293 to 294 labelled a_1(1)* 294 to 295 labelled a_1(1)* 295 to 296 labelled a_1(1)* 296 to 297 labelled b_1(1)* 297 to 298 labelled b_1(1)* 298 to 299 labelled b_1(1)* 299 to 300 labelled a_1(1)* 299 to 291 labelled b_1(1)* 300 to 301 labelled a_1(1)* 300 to 291 labelled b_1(1)* 301 to 302 labelled a_1(1)* 301 to 291 labelled b_1(1)* 302 to 278 labelled a_1(1)* 302 to 291 labelled b_1(1) 4.10/1.81 4.10/1.81 4.10/1.81 ---------------------------------------- 4.10/1.81 4.10/1.81 (6) 4.10/1.81 YES 4.16/1.84 EOF