3.85/1.71 YES 3.85/1.74 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 3.85/1.74 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.85/1.74 3.85/1.74 3.85/1.74 Termination w.r.t. Q of the given QTRS could be proven: 3.85/1.74 3.85/1.74 (0) QTRS 3.85/1.74 (1) QTRS Reverse [EQUIVALENT, 0 ms] 3.85/1.74 (2) QTRS 3.85/1.74 (3) RFCMatchBoundsTRSProof [EQUIVALENT, 45 ms] 3.85/1.74 (4) YES 3.85/1.74 3.85/1.74 3.85/1.74 ---------------------------------------- 3.85/1.74 3.85/1.74 (0) 3.85/1.74 Obligation: 3.85/1.74 Q restricted rewrite system: 3.85/1.74 The TRS R consists of the following rules: 3.85/1.74 3.85/1.74 a(c(a(x1))) -> c(a(c(x1))) 3.85/1.74 a(a(b(x1))) -> a(d(b(x1))) 3.85/1.74 a(b(x1)) -> b(a(a(x1))) 3.85/1.74 d(d(x1)) -> a(d(b(x1))) 3.85/1.74 b(b(x1)) -> b(c(x1)) 3.85/1.74 a(d(c(x1))) -> c(a(x1)) 3.85/1.74 b(c(x1)) -> a(a(a(x1))) 3.85/1.74 3.85/1.74 Q is empty. 3.85/1.74 3.85/1.74 ---------------------------------------- 3.85/1.74 3.85/1.74 (1) QTRS Reverse (EQUIVALENT) 3.85/1.74 We applied the QTRS Reverse Processor [REVERSE]. 3.85/1.74 ---------------------------------------- 3.85/1.74 3.85/1.74 (2) 3.85/1.74 Obligation: 3.85/1.74 Q restricted rewrite system: 3.85/1.74 The TRS R consists of the following rules: 3.85/1.74 3.85/1.74 a(c(a(x1))) -> c(a(c(x1))) 3.85/1.74 b(a(a(x1))) -> b(d(a(x1))) 3.85/1.74 b(a(x1)) -> a(a(b(x1))) 3.85/1.74 d(d(x1)) -> b(d(a(x1))) 3.85/1.75 b(b(x1)) -> c(b(x1)) 3.85/1.75 c(d(a(x1))) -> a(c(x1)) 3.85/1.75 c(b(x1)) -> a(a(a(x1))) 3.85/1.75 3.85/1.75 Q is empty. 3.85/1.75 3.85/1.75 ---------------------------------------- 3.85/1.75 3.85/1.75 (3) RFCMatchBoundsTRSProof (EQUIVALENT) 3.85/1.75 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 4. This implies Q-termination of R. 3.85/1.75 The following rules were used to construct the certificate: 3.85/1.75 3.85/1.75 a(c(a(x1))) -> c(a(c(x1))) 3.85/1.75 b(a(a(x1))) -> b(d(a(x1))) 3.85/1.75 b(a(x1)) -> a(a(b(x1))) 3.85/1.75 d(d(x1)) -> b(d(a(x1))) 3.85/1.75 b(b(x1)) -> c(b(x1)) 3.85/1.75 c(d(a(x1))) -> a(c(x1)) 3.85/1.75 c(b(x1)) -> a(a(a(x1))) 3.85/1.75 3.85/1.75 The certificate found is represented by the following graph. 3.85/1.75 The certificate consists of the following enumerated nodes: 3.85/1.75 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 57, 58, 59, 60, 61, 62, 63, 64, 103, 104, 105, 106, 107, 108, 140, 141 3.85/1.75 3.85/1.75 Node 1 is start node and node 3 is final node. 3.85/1.75 3.85/1.75 Those nodes are connected through the following edges: 3.85/1.75 3.85/1.75 * 1 to 4 labelled c_1(0)* 1 to 6 labelled b_1(0)* 1 to 8 labelled a_1(0)* 1 to 9 labelled c_1(0)* 1 to 5 labelled a_1(0), c_1(1)* 1 to 10 labelled a_1(1)* 1 to 19 labelled c_1(1)* 1 to 61 labelled c_1(2)* 3 to 3 labelled #_1(0)* 4 to 5 labelled a_1(0), c_1(1)* 4 to 19 labelled c_1(1)* 5 to 3 labelled c_1(0)* 5 to 12 labelled a_1(1)* 5 to 10 labelled a_1(1)* 5 to 5 labelled c_1(1)* 5 to 57 labelled c_1(2)* 5 to 61 labelled c_1(2)* 5 to 59 labelled c_1(2)* 5 to 63 labelled c_1(2)* 6 to 7 labelled d_1(0)* 7 to 3 labelled a_1(0)* 7 to 5 labelled c_1(1)* 8 to 9 labelled a_1(0)* 8 to 19 labelled c_1(1)* 9 to 3 labelled b_1(0), a_1(0)* 9 to 13 labelled b_1(1)* 9 to 15 labelled a_1(1)* 9 to 16 labelled c_1(1)* 9 to 5 labelled c_1(1)* 9 to 17 labelled a_1(2)* 9 to 63 labelled c_1(2)* 9 to 103 labelled c_1(3)* 10 to 11 labelled a_1(1)* 10 to 57 labelled c_1(2)* 11 to 3 labelled a_1(1)* 11 to 13 labelled a_1(1)* 11 to 5 labelled c_1(1)* 12 to 3 labelled c_1(1)* 12 to 12 labelled a_1(1)* 12 to 10 labelled a_1(1)* 12 to 20 labelled c_1(1)* 12 to 5 labelled c_1(1)* 12 to 57 labelled c_1(2)* 12 to 61 labelled c_1(2)* 12 to 58 labelled c_1(1)* 12 to 62 labelled c_1(1)* 12 to 59 labelled c_1(2)* 12 to 60 labelled c_1(1)* 12 to 63 labelled c_1(2)* 13 to 14 labelled d_1(1)* 14 to 3 labelled a_1(1)* 14 to 5 labelled c_1(1)* 15 to 16 labelled a_1(1)* 15 to 59 labelled c_1(2)* 16 to 3 labelled b_1(1)* 16 to 13 labelled b_1(1)* 16 to 15 labelled a_1(1)* 16 to 16 labelled c_1(1)* 16 to 17 labelled a_1(2)* 16 to 63 labelled c_1(2)* 16 to 103 labelled c_1(3)* 17 to 18 labelled a_1(2)* 17 to 57 labelled c_1(2)* 18 to 3 labelled a_1(2)* 18 to 5 labelled c_1(1)* 18 to 13 labelled a_1(2)* 19 to 20 labelled a_1(1)* 19 to 57 labelled c_1(2)* 20 to 12 labelled c_1(1)* 20 to 10 labelled c_1(1)* 20 to 15 labelled c_1(1)* 20 to 17 labelled c_1(1)* 20 to 64 labelled c_1(1)* 20 to 104 labelled c_1(1)* 57 to 58 labelled a_1(2)* 57 to 57 labelled c_1(2)* 57 to 5 labelled c_1(1)* 57 to 59 labelled c_1(2)* 57 to 105 labelled c_1(3)* 57 to 103 labelled c_1(3)* 58 to 12 labelled c_1(2), a_1(1)* 58 to 10 labelled c_1(2), a_1(1)* 58 to 11 labelled c_1(2)* 58 to 16 labelled c_1(2)* 58 to 3 labelled c_1(2)* 58 to 13 labelled c_1(2)* 58 to 17 labelled a_1(2)* 58 to 62 labelled c_1(2)* 58 to 18 labelled c_1(2)* 58 to 58 labelled a_1(2)* 58 to 5 labelled c_1(1)* 58 to 57 labelled c_1(2)* 58 to 61 labelled c_1(2)* 58 to 103 labelled c_1(3)* 58 to 59 labelled c_1(2)* 58 to 105 labelled c_1(3)* 58 to 63 labelled c_1(2)* 59 to 60 labelled a_1(2)* 59 to 57 labelled c_1(2)* 59 to 107 labelled c_1(3)* 60 to 15 labelled c_1(2)* 60 to 17 labelled c_1(2)* 60 to 64 labelled c_1(2)* 60 to 104 labelled c_1(2)* 61 to 62 labelled a_1(2)* 61 to 57 labelled c_1(2)* 61 to 105 labelled c_1(3)* 61 to 103 labelled c_1(3)* 62 to 58 labelled c_1(2)* 63 to 64 labelled a_1(2)* 64 to 60 labelled c_1(2)* 103 to 104 labelled a_1(3)* 103 to 57 labelled c_1(2)* 103 to 105 labelled c_1(3)* 103 to 103 labelled c_1(3)* 104 to 58 labelled c_1(3)* 105 to 106 labelled a_1(3)* 105 to 107 labelled c_1(3)* 105 to 5 labelled c_1(1)* 105 to 57 labelled c_1(2)* 105 to 103 labelled c_1(3)* 105 to 105 labelled c_1(3)* 105 to 140 labelled c_1(4)* 106 to 17 labelled c_1(3)* 106 to 3 labelled c_1(3)* 106 to 13 labelled c_1(3)* 106 to 12 labelled a_1(1)* 106 to 10 labelled a_1(1)* 106 to 62 labelled c_1(3)* 106 to 60 labelled c_1(3)* 106 to 104 labelled c_1(3)* 106 to 106 labelled c_1(3)* 106 to 58 labelled a_1(2)* 106 to 5 labelled c_1(1)* 106 to 57 labelled c_1(2)* 106 to 61 labelled c_1(2)* 106 to 103 labelled c_1(3)* 106 to 105 labelled c_1(3)* 106 to 63 labelled c_1(2)* 106 to 59 labelled c_1(2)* 106 to 64 labelled c_1(3)* 107 to 108 labelled a_1(3)* 107 to 105 labelled c_1(3)* 108 to 18 labelled c_1(3)* 140 to 141 labelled a_1(4)* 140 to 57 labelled c_1(2)* 140 to 103 labelled c_1(3)* 141 to 104 labelled c_1(4)* 141 to 106 labelled c_1(4) 3.85/1.75 3.85/1.75 3.85/1.75 ---------------------------------------- 3.85/1.75 3.85/1.75 (4) 3.85/1.75 YES 4.10/1.77 EOF