3.59/1.65 YES 3.77/1.70 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 3.77/1.70 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.77/1.70 3.77/1.70 3.77/1.70 Termination w.r.t. Q of the given QTRS could be proven: 3.77/1.70 3.77/1.70 (0) QTRS 3.77/1.70 (1) QTRS Reverse [EQUIVALENT, 0 ms] 3.77/1.70 (2) QTRS 3.77/1.70 (3) Strip Symbols Proof [SOUND, 0 ms] 3.77/1.70 (4) QTRS 3.77/1.70 (5) RFCMatchBoundsTRSProof [EQUIVALENT, 2 ms] 3.77/1.70 (6) YES 3.77/1.70 3.77/1.70 3.77/1.70 ---------------------------------------- 3.77/1.70 3.77/1.70 (0) 3.77/1.70 Obligation: 3.77/1.70 Q restricted rewrite system: 3.77/1.70 The TRS R consists of the following rules: 3.77/1.70 3.77/1.70 a(b(a(c(a(a(a(a(a(x1))))))))) -> a(a(a(a(a(a(b(a(c(a(b(a(c(x1))))))))))))) 3.77/1.70 3.77/1.70 Q is empty. 3.77/1.70 3.77/1.70 ---------------------------------------- 3.77/1.70 3.77/1.70 (1) QTRS Reverse (EQUIVALENT) 3.77/1.70 We applied the QTRS Reverse Processor [REVERSE]. 3.77/1.70 ---------------------------------------- 3.77/1.70 3.77/1.70 (2) 3.77/1.70 Obligation: 3.77/1.70 Q restricted rewrite system: 3.77/1.70 The TRS R consists of the following rules: 3.77/1.70 3.77/1.70 a(a(a(a(a(c(a(b(a(x1))))))))) -> c(a(b(a(c(a(b(a(a(a(a(a(a(x1))))))))))))) 3.77/1.70 3.77/1.70 Q is empty. 3.77/1.70 3.77/1.70 ---------------------------------------- 3.77/1.70 3.77/1.70 (3) Strip Symbols Proof (SOUND) 3.77/1.70 We were given the following TRS: 3.77/1.70 3.77/1.70 a(a(a(a(a(c(a(b(a(x1))))))))) -> c(a(b(a(c(a(b(a(a(a(a(a(a(x1))))))))))))) 3.77/1.70 3.77/1.70 By stripping symbols from the only rule of the system, we obtained the following TRS [ENDRULLIS]: 3.77/1.70 3.77/1.70 a(a(a(a(a(c(a(b(x)))))))) -> c(a(b(a(c(a(b(a(a(a(a(a(x)))))))))))) 3.77/1.70 3.77/1.70 ---------------------------------------- 3.77/1.70 3.77/1.70 (4) 3.77/1.70 Obligation: 3.77/1.70 Q restricted rewrite system: 3.77/1.70 The TRS R consists of the following rules: 3.77/1.70 3.77/1.70 a(a(a(a(a(c(a(b(x)))))))) -> c(a(b(a(c(a(b(a(a(a(a(a(x)))))))))))) 3.77/1.70 3.77/1.70 Q is empty. 3.77/1.70 3.77/1.70 ---------------------------------------- 3.77/1.70 3.77/1.70 (5) RFCMatchBoundsTRSProof (EQUIVALENT) 3.77/1.70 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. This implies Q-termination of R. 3.77/1.70 The following rules were used to construct the certificate: 3.77/1.70 3.77/1.70 a(a(a(a(a(c(a(b(x)))))))) -> c(a(b(a(c(a(b(a(a(a(a(a(x)))))))))))) 3.77/1.70 3.77/1.70 The certificate found is represented by the following graph. 3.77/1.70 The certificate consists of the following enumerated nodes: 3.77/1.70 256, 257, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301 3.77/1.70 3.77/1.70 Node 256 is start node and node 257 is final node. 3.77/1.70 3.77/1.70 Those nodes are connected through the following edges: 3.77/1.70 3.77/1.70 * 256 to 269 labelled c_1(0)* 257 to 257 labelled #_1(0)* 269 to 270 labelled a_1(0)* 270 to 271 labelled b_1(0)* 271 to 272 labelled a_1(0)* 272 to 273 labelled c_1(0)* 273 to 274 labelled a_1(0)* 274 to 275 labelled b_1(0)* 275 to 276 labelled a_1(0)* 275 to 291 labelled c_1(1)* 276 to 277 labelled a_1(0)* 276 to 291 labelled c_1(1)* 277 to 278 labelled a_1(0)* 277 to 291 labelled c_1(1)* 278 to 279 labelled a_1(0)* 278 to 291 labelled c_1(1)* 279 to 257 labelled a_1(0)* 279 to 291 labelled c_1(1)* 291 to 292 labelled a_1(1)* 292 to 293 labelled b_1(1)* 293 to 294 labelled a_1(1)* 294 to 295 labelled c_1(1)* 295 to 296 labelled a_1(1)* 296 to 297 labelled b_1(1)* 297 to 298 labelled a_1(1)* 297 to 291 labelled c_1(1)* 298 to 299 labelled a_1(1)* 298 to 291 labelled c_1(1)* 299 to 300 labelled a_1(1)* 299 to 291 labelled c_1(1)* 300 to 301 labelled a_1(1)* 300 to 291 labelled c_1(1)* 301 to 257 labelled a_1(1)* 301 to 291 labelled c_1(1) 3.77/1.70 3.77/1.70 3.77/1.70 ---------------------------------------- 3.77/1.70 3.77/1.70 (6) 3.77/1.70 YES 3.77/1.73 EOF