3.56/1.76 YES 3.92/1.79 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.92/1.79 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.92/1.79 3.92/1.79 3.92/1.79 Termination w.r.t. Q of the given QTRS could be proven: 3.92/1.79 3.92/1.79 (0) QTRS 3.92/1.79 (1) Strip Symbols Proof [SOUND, 0 ms] 3.92/1.79 (2) QTRS 3.92/1.79 (3) RFCMatchBoundsTRSProof [EQUIVALENT, 11 ms] 3.92/1.79 (4) YES 3.92/1.79 3.92/1.79 3.92/1.79 ---------------------------------------- 3.92/1.79 3.92/1.79 (0) 3.92/1.79 Obligation: 3.92/1.79 Q restricted rewrite system: 3.92/1.79 The TRS R consists of the following rules: 3.92/1.79 3.92/1.79 b(a(b(a(a(a(x1)))))) -> a(a(a(b(a(b(a(b(a(x1))))))))) 3.92/1.79 3.92/1.79 Q is empty. 3.92/1.79 3.92/1.79 ---------------------------------------- 3.92/1.79 3.92/1.79 (1) Strip Symbols Proof (SOUND) 3.92/1.79 We were given the following TRS: 3.92/1.79 3.92/1.79 b(a(b(a(a(a(x1)))))) -> a(a(a(b(a(b(a(b(a(x1))))))))) 3.92/1.79 3.92/1.79 By stripping symbols from the only rule of the system, we obtained the following TRS [ENDRULLIS]: 3.92/1.79 3.92/1.79 b(a(b(a(a(x))))) -> a(a(a(b(a(b(a(b(x)))))))) 3.92/1.79 3.92/1.79 ---------------------------------------- 3.92/1.79 3.92/1.79 (2) 3.92/1.79 Obligation: 3.92/1.79 Q restricted rewrite system: 3.92/1.79 The TRS R consists of the following rules: 3.92/1.79 3.92/1.79 b(a(b(a(a(x))))) -> a(a(a(b(a(b(a(b(x)))))))) 3.92/1.79 3.92/1.79 Q is empty. 3.92/1.79 3.92/1.79 ---------------------------------------- 3.92/1.79 3.92/1.79 (3) RFCMatchBoundsTRSProof (EQUIVALENT) 3.92/1.79 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 4. This implies Q-termination of R. 3.92/1.79 The following rules were used to construct the certificate: 3.92/1.79 3.92/1.79 b(a(b(a(a(x))))) -> a(a(a(b(a(b(a(b(x)))))))) 3.92/1.79 3.92/1.79 The certificate found is represented by the following graph. 3.92/1.79 The certificate consists of the following enumerated nodes: 3.92/1.79 5, 6, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276 3.92/1.79 3.92/1.79 Node 5 is start node and node 6 is final node. 3.92/1.79 3.92/1.79 Those nodes are connected through the following edges: 3.92/1.79 3.92/1.79 * 5 to 207 labelled a_1(0)* 6 to 6 labelled #_1(0)* 207 to 208 labelled a_1(0)* 208 to 209 labelled a_1(0)* 209 to 210 labelled b_1(0)* 209 to 221 labelled a_1(1)* 210 to 211 labelled a_1(0)* 211 to 212 labelled b_1(0)* 211 to 214 labelled a_1(1)* 212 to 213 labelled a_1(0)* 213 to 6 labelled b_1(0)* 213 to 214 labelled a_1(1)* 214 to 215 labelled a_1(1)* 215 to 216 labelled a_1(1)* 216 to 217 labelled b_1(1)* 216 to 228 labelled a_1(2)* 217 to 218 labelled a_1(1)* 218 to 219 labelled b_1(1)* 218 to 214 labelled a_1(1)* 219 to 220 labelled a_1(1)* 220 to 6 labelled b_1(1)* 220 to 214 labelled a_1(1)* 221 to 222 labelled a_1(1)* 222 to 223 labelled a_1(1)* 223 to 224 labelled b_1(1)* 224 to 225 labelled a_1(1)* 225 to 226 labelled b_1(1)* 225 to 235 labelled a_1(2)* 226 to 227 labelled a_1(1)* 227 to 214 labelled b_1(1)* 228 to 229 labelled a_1(2)* 229 to 230 labelled a_1(2)* 230 to 231 labelled b_1(2)* 231 to 232 labelled a_1(2)* 232 to 233 labelled b_1(2)* 232 to 235 labelled a_1(2)* 233 to 234 labelled a_1(2)* 234 to 214 labelled b_1(2)* 235 to 236 labelled a_1(2)* 236 to 237 labelled a_1(2)* 237 to 238 labelled b_1(2)* 238 to 239 labelled a_1(2)* 239 to 240 labelled b_1(2)* 239 to 242 labelled a_1(3)* 240 to 241 labelled a_1(2)* 241 to 216 labelled b_1(2)* 242 to 243 labelled a_1(3)* 243 to 244 labelled a_1(3)* 244 to 245 labelled b_1(3)* 244 to 256 labelled a_1(4)* 245 to 246 labelled a_1(3)* 246 to 247 labelled b_1(3)* 247 to 248 labelled a_1(3)* 248 to 229 labelled b_1(3)* 248 to 249 labelled a_1(3)* 249 to 250 labelled a_1(3)* 250 to 251 labelled a_1(3)* 251 to 252 labelled b_1(3)* 252 to 253 labelled a_1(3)* 253 to 254 labelled b_1(3)* 253 to 263 labelled a_1(3)* 254 to 255 labelled a_1(3)* 255 to 235 labelled b_1(3)* 256 to 257 labelled a_1(4)* 257 to 258 labelled a_1(4)* 258 to 259 labelled b_1(4)* 259 to 260 labelled a_1(4)* 260 to 261 labelled b_1(4)* 260 to 270 labelled a_1(4)* 261 to 262 labelled a_1(4)* 262 to 249 labelled b_1(4)* 263 to 264 labelled a_1(3)* 264 to 265 labelled a_1(3)* 265 to 266 labelled b_1(3)* 266 to 267 labelled a_1(3)* 267 to 268 labelled b_1(3)* 268 to 269 labelled a_1(3)* 269 to 237 labelled b_1(3)* 270 to 271 labelled a_1(4)* 271 to 272 labelled a_1(4)* 272 to 273 labelled b_1(4)* 273 to 274 labelled a_1(4)* 274 to 275 labelled b_1(4)* 275 to 276 labelled a_1(4)* 276 to 251 labelled b_1(4) 3.92/1.79 3.92/1.79 3.92/1.79 ---------------------------------------- 3.92/1.79 3.92/1.79 (4) 3.92/1.79 YES 3.98/1.80 EOF