3.62/1.84 YES 3.99/1.90 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.99/1.90 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.99/1.90 3.99/1.90 3.99/1.90 Termination w.r.t. Q of the given QTRS could be proven: 3.99/1.90 3.99/1.90 (0) QTRS 3.99/1.90 (1) QTRS Reverse [EQUIVALENT, 0 ms] 3.99/1.90 (2) QTRS 3.99/1.90 (3) Strip Symbols Proof [SOUND, 0 ms] 3.99/1.90 (4) QTRS 3.99/1.90 (5) RFCMatchBoundsTRSProof [EQUIVALENT, 4 ms] 3.99/1.90 (6) YES 3.99/1.90 3.99/1.90 3.99/1.90 ---------------------------------------- 3.99/1.90 3.99/1.90 (0) 3.99/1.90 Obligation: 3.99/1.90 Q restricted rewrite system: 3.99/1.90 The TRS R consists of the following rules: 3.99/1.90 3.99/1.90 a(b(c(b(a(a(a(a(x1)))))))) -> a(a(a(a(a(b(c(b(a(a(a(b(c(b(x1)))))))))))))) 3.99/1.90 3.99/1.90 Q is empty. 3.99/1.90 3.99/1.90 ---------------------------------------- 3.99/1.90 3.99/1.90 (1) QTRS Reverse (EQUIVALENT) 3.99/1.90 We applied the QTRS Reverse Processor [REVERSE]. 3.99/1.90 ---------------------------------------- 3.99/1.90 3.99/1.90 (2) 3.99/1.90 Obligation: 3.99/1.90 Q restricted rewrite system: 3.99/1.90 The TRS R consists of the following rules: 3.99/1.90 3.99/1.90 a(a(a(a(b(c(b(a(x1)))))))) -> b(c(b(a(a(a(b(c(b(a(a(a(a(a(x1)))))))))))))) 3.99/1.90 3.99/1.90 Q is empty. 3.99/1.90 3.99/1.90 ---------------------------------------- 3.99/1.90 3.99/1.90 (3) Strip Symbols Proof (SOUND) 3.99/1.90 We were given the following TRS: 3.99/1.90 3.99/1.90 a(a(a(a(b(c(b(a(x1)))))))) -> b(c(b(a(a(a(b(c(b(a(a(a(a(a(x1)))))))))))))) 3.99/1.90 3.99/1.90 By stripping symbols from the only rule of the system, we obtained the following TRS [ENDRULLIS]: 3.99/1.90 3.99/1.90 a(a(a(a(b(c(b(x))))))) -> b(c(b(a(a(a(b(c(b(a(a(a(a(x))))))))))))) 3.99/1.90 3.99/1.90 ---------------------------------------- 3.99/1.90 3.99/1.90 (4) 3.99/1.90 Obligation: 3.99/1.90 Q restricted rewrite system: 3.99/1.90 The TRS R consists of the following rules: 3.99/1.90 3.99/1.90 a(a(a(a(b(c(b(x))))))) -> b(c(b(a(a(a(b(c(b(a(a(a(a(x))))))))))))) 3.99/1.90 3.99/1.90 Q is empty. 3.99/1.90 3.99/1.90 ---------------------------------------- 3.99/1.90 3.99/1.90 (5) RFCMatchBoundsTRSProof (EQUIVALENT) 3.99/1.90 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. This implies Q-termination of R. 3.99/1.90 The following rules were used to construct the certificate: 3.99/1.90 3.99/1.90 a(a(a(a(b(c(b(x))))))) -> b(c(b(a(a(a(b(c(b(a(a(a(a(x))))))))))))) 3.99/1.90 3.99/1.90 The certificate found is represented by the following graph. 3.99/1.90 The certificate consists of the following enumerated nodes: 3.99/1.90 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316 3.99/1.90 3.99/1.90 Node 291 is start node and node 292 is final node. 3.99/1.90 3.99/1.90 Those nodes are connected through the following edges: 3.99/1.90 3.99/1.90 * 291 to 293 labelled b_1(0)* 292 to 292 labelled #_1(0)* 293 to 294 labelled c_1(0)* 294 to 295 labelled b_1(0)* 295 to 296 labelled a_1(0)* 296 to 297 labelled a_1(0)* 297 to 298 labelled a_1(0)* 298 to 299 labelled b_1(0)* 299 to 300 labelled c_1(0)* 300 to 301 labelled b_1(0)* 301 to 302 labelled a_1(0)* 301 to 305 labelled b_1(1)* 302 to 303 labelled a_1(0)* 302 to 305 labelled b_1(1)* 303 to 304 labelled a_1(0)* 303 to 305 labelled b_1(1)* 304 to 292 labelled a_1(0)* 304 to 305 labelled b_1(1)* 305 to 306 labelled c_1(1)* 306 to 307 labelled b_1(1)* 307 to 308 labelled a_1(1)* 308 to 309 labelled a_1(1)* 309 to 310 labelled a_1(1)* 310 to 311 labelled b_1(1)* 311 to 312 labelled c_1(1)* 312 to 313 labelled b_1(1)* 313 to 314 labelled a_1(1)* 313 to 305 labelled b_1(1)* 314 to 315 labelled a_1(1)* 314 to 305 labelled b_1(1)* 315 to 316 labelled a_1(1)* 315 to 305 labelled b_1(1)* 316 to 292 labelled a_1(1)* 316 to 305 labelled b_1(1) 3.99/1.90 3.99/1.90 3.99/1.90 ---------------------------------------- 3.99/1.90 3.99/1.90 (6) 3.99/1.90 YES 4.02/1.92 EOF