4.04/1.78 YES 4.09/1.79 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.09/1.79 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.09/1.79 4.09/1.79 4.09/1.79 Termination w.r.t. Q of the given QTRS could be proven: 4.09/1.79 4.09/1.79 (0) QTRS 4.09/1.79 (1) QTRS Reverse [EQUIVALENT, 0 ms] 4.09/1.79 (2) QTRS 4.09/1.79 (3) Strip Symbols Proof [SOUND, 0 ms] 4.09/1.79 (4) QTRS 4.09/1.79 (5) RFCMatchBoundsTRSProof [EQUIVALENT, 0 ms] 4.09/1.79 (6) YES 4.09/1.79 4.09/1.79 4.09/1.79 ---------------------------------------- 4.09/1.79 4.09/1.79 (0) 4.09/1.79 Obligation: 4.09/1.79 Q restricted rewrite system: 4.09/1.79 The TRS R consists of the following rules: 4.09/1.79 4.09/1.79 a(b(b(c(a(a(a(a(a(x1))))))))) -> a(a(a(a(a(a(b(b(c(a(b(b(c(x1))))))))))))) 4.09/1.79 4.09/1.79 Q is empty. 4.09/1.79 4.09/1.79 ---------------------------------------- 4.09/1.79 4.09/1.79 (1) QTRS Reverse (EQUIVALENT) 4.09/1.79 We applied the QTRS Reverse Processor [REVERSE]. 4.09/1.79 ---------------------------------------- 4.09/1.79 4.09/1.79 (2) 4.09/1.79 Obligation: 4.09/1.79 Q restricted rewrite system: 4.09/1.79 The TRS R consists of the following rules: 4.09/1.79 4.09/1.79 a(a(a(a(a(c(b(b(a(x1))))))))) -> c(b(b(a(c(b(b(a(a(a(a(a(a(x1))))))))))))) 4.09/1.79 4.09/1.79 Q is empty. 4.09/1.79 4.09/1.79 ---------------------------------------- 4.09/1.79 4.09/1.79 (3) Strip Symbols Proof (SOUND) 4.09/1.79 We were given the following TRS: 4.09/1.79 4.09/1.79 a(a(a(a(a(c(b(b(a(x1))))))))) -> c(b(b(a(c(b(b(a(a(a(a(a(a(x1))))))))))))) 4.09/1.79 4.09/1.79 By stripping symbols from the only rule of the system, we obtained the following TRS [ENDRULLIS]: 4.09/1.79 4.09/1.79 a(a(a(a(a(c(b(b(x)))))))) -> c(b(b(a(c(b(b(a(a(a(a(a(x)))))))))))) 4.09/1.79 4.09/1.79 ---------------------------------------- 4.09/1.79 4.09/1.79 (4) 4.09/1.79 Obligation: 4.09/1.79 Q restricted rewrite system: 4.09/1.79 The TRS R consists of the following rules: 4.09/1.79 4.09/1.79 a(a(a(a(a(c(b(b(x)))))))) -> c(b(b(a(c(b(b(a(a(a(a(a(x)))))))))))) 4.09/1.79 4.09/1.79 Q is empty. 4.09/1.79 4.09/1.79 ---------------------------------------- 4.09/1.79 4.09/1.79 (5) RFCMatchBoundsTRSProof (EQUIVALENT) 4.09/1.79 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. This implies Q-termination of R. 4.09/1.79 The following rules were used to construct the certificate: 4.09/1.79 4.09/1.79 a(a(a(a(a(c(b(b(x)))))))) -> c(b(b(a(c(b(b(a(a(a(a(a(x)))))))))))) 4.09/1.79 4.09/1.79 The certificate found is represented by the following graph. 4.09/1.79 The certificate consists of the following enumerated nodes: 4.09/1.79 388, 389, 498, 499, 500, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513, 514, 515, 516, 517, 518, 519 4.09/1.79 4.09/1.79 Node 388 is start node and node 389 is final node. 4.09/1.79 4.09/1.79 Those nodes are connected through the following edges: 4.09/1.79 4.09/1.79 * 388 to 498 labelled c_1(0)* 389 to 389 labelled #_1(0)* 498 to 499 labelled b_1(0)* 499 to 500 labelled b_1(0)* 500 to 501 labelled a_1(0)* 501 to 502 labelled c_1(0)* 502 to 503 labelled b_1(0)* 503 to 504 labelled b_1(0)* 504 to 505 labelled a_1(0)* 504 to 509 labelled c_1(1)* 505 to 506 labelled a_1(0)* 505 to 509 labelled c_1(1)* 506 to 507 labelled a_1(0)* 506 to 509 labelled c_1(1)* 507 to 508 labelled a_1(0)* 507 to 509 labelled c_1(1)* 508 to 389 labelled a_1(0)* 508 to 509 labelled c_1(1)* 509 to 510 labelled b_1(1)* 510 to 511 labelled b_1(1)* 511 to 512 labelled a_1(1)* 512 to 513 labelled c_1(1)* 513 to 514 labelled b_1(1)* 514 to 515 labelled b_1(1)* 515 to 516 labelled a_1(1)* 515 to 509 labelled c_1(1)* 516 to 517 labelled a_1(1)* 516 to 509 labelled c_1(1)* 517 to 518 labelled a_1(1)* 517 to 509 labelled c_1(1)* 518 to 519 labelled a_1(1)* 518 to 509 labelled c_1(1)* 519 to 389 labelled a_1(1)* 519 to 509 labelled c_1(1) 4.09/1.79 4.09/1.79 4.09/1.79 ---------------------------------------- 4.09/1.79 4.09/1.79 (6) 4.09/1.79 YES 4.16/1.83 EOF