YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRS Reverse [EQUIVALENT, 0 ms] (2) QTRS (3) Strip Symbols Proof [SOUND, 0 ms] (4) QTRS (5) RFCMatchBoundsTRSProof [EQUIVALENT, 0 ms] (6) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(b(b(c(a(c(a(b(c(a(x1)))))))))) -> a(b(c(a(c(a(b(b(c(a(c(a(b(x1))))))))))))) Q is empty. ---------------------------------------- (1) QTRS Reverse (EQUIVALENT) We applied the QTRS Reverse Processor [REVERSE]. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(c(b(a(c(a(c(b(b(a(x1)))))))))) -> b(a(c(a(c(b(b(a(c(a(c(b(a(x1))))))))))))) Q is empty. ---------------------------------------- (3) Strip Symbols Proof (SOUND) We were given the following TRS: a(c(b(a(c(a(c(b(b(a(x1)))))))))) -> b(a(c(a(c(b(b(a(c(a(c(b(a(x1))))))))))))) By stripping symbols from the only rule of the system, we obtained the following TRS [ENDRULLIS]: a(c(b(a(c(a(c(b(b(x))))))))) -> b(a(c(a(c(b(b(a(c(a(c(b(x)))))))))))) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(c(b(a(c(a(c(b(b(x))))))))) -> b(a(c(a(c(b(b(a(c(a(c(b(x)))))))))))) Q is empty. ---------------------------------------- (5) RFCMatchBoundsTRSProof (EQUIVALENT) Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 2. This implies Q-termination of R. The following rules were used to construct the certificate: a(c(b(a(c(a(c(b(b(x))))))))) -> b(a(c(a(c(b(b(a(c(a(c(b(x)))))))))))) The certificate found is represented by the following graph. The certificate consists of the following enumerated nodes: 347, 348, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400, 401, 402, 403 Node 347 is start node and node 348 is final node. Those nodes are connected through the following edges: * 347 to 360 labelled b_1(0)* 348 to 348 labelled #_1(0)* 360 to 361 labelled a_1(0)* 361 to 362 labelled c_1(0)* 362 to 363 labelled a_1(0)* 363 to 364 labelled c_1(0)* 364 to 365 labelled b_1(0)* 365 to 366 labelled b_1(0)* 366 to 367 labelled a_1(0)* 366 to 382 labelled b_1(1)* 367 to 368 labelled c_1(0)* 368 to 369 labelled a_1(0)* 368 to 371 labelled b_1(1)* 369 to 370 labelled c_1(0)* 370 to 348 labelled b_1(0)* 371 to 372 labelled a_1(1)* 372 to 373 labelled c_1(1)* 373 to 374 labelled a_1(1)* 374 to 375 labelled c_1(1)* 375 to 376 labelled b_1(1)* 376 to 377 labelled b_1(1)* 377 to 378 labelled a_1(1)* 377 to 393 labelled b_1(2)* 378 to 379 labelled c_1(1)* 379 to 380 labelled a_1(1)* 379 to 371 labelled b_1(1)* 380 to 381 labelled c_1(1)* 381 to 348 labelled b_1(1)* 382 to 383 labelled a_1(1)* 383 to 384 labelled c_1(1)* 384 to 385 labelled a_1(1)* 385 to 386 labelled c_1(1)* 386 to 387 labelled b_1(1)* 387 to 388 labelled b_1(1)* 388 to 389 labelled a_1(1)* 388 to 393 labelled b_1(2)* 389 to 390 labelled c_1(1)* 390 to 391 labelled a_1(1)* 390 to 371 labelled b_1(1)* 391 to 392 labelled c_1(1)* 392 to 377 labelled b_1(1)* 393 to 394 labelled a_1(2)* 394 to 395 labelled c_1(2)* 395 to 396 labelled a_1(2)* 396 to 397 labelled c_1(2)* 397 to 398 labelled b_1(2)* 398 to 399 labelled b_1(2)* 399 to 400 labelled a_1(2)* 399 to 393 labelled b_1(2)* 400 to 401 labelled c_1(2)* 401 to 402 labelled a_1(2)* 401 to 371 labelled b_1(1)* 402 to 403 labelled c_1(2)* 403 to 377 labelled b_1(2) ---------------------------------------- (6) YES