3.75/1.72 YES 3.93/1.82 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.93/1.82 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.93/1.82 3.93/1.82 3.93/1.82 Termination w.r.t. Q of the given QTRS could be proven: 3.93/1.82 3.93/1.82 (0) QTRS 3.93/1.82 (1) RFCMatchBoundsTRSProof [EQUIVALENT, 36 ms] 3.93/1.82 (2) YES 3.93/1.82 3.93/1.82 3.93/1.82 ---------------------------------------- 3.93/1.82 3.93/1.82 (0) 3.93/1.82 Obligation: 3.93/1.82 Q restricted rewrite system: 3.93/1.82 The TRS R consists of the following rules: 3.93/1.82 3.93/1.82 a(d(x1)) -> d(b(c(b(d(x1))))) 3.93/1.82 a(x1) -> b(b(f(b(b(x1))))) 3.93/1.82 b(d(b(x1))) -> a(d(x1)) 3.93/1.82 d(f(x1)) -> b(d(x1)) 3.93/1.82 3.93/1.82 Q is empty. 3.93/1.82 3.93/1.82 ---------------------------------------- 3.93/1.82 3.93/1.82 (1) RFCMatchBoundsTRSProof (EQUIVALENT) 3.93/1.82 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 4. This implies Q-termination of R. 3.93/1.82 The following rules were used to construct the certificate: 3.93/1.82 3.93/1.82 a(d(x1)) -> d(b(c(b(d(x1))))) 3.93/1.82 a(x1) -> b(b(f(b(b(x1))))) 3.93/1.82 b(d(b(x1))) -> a(d(x1)) 3.93/1.82 d(f(x1)) -> b(d(x1)) 3.93/1.82 3.93/1.82 The certificate found is represented by the following graph. 3.93/1.82 The certificate consists of the following enumerated nodes: 3.93/1.82 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 37, 38, 39, 40, 41, 42, 43, 44, 45, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155 3.93/1.82 3.93/1.82 Node 1 is start node and node 2 is final node. 3.93/1.82 3.93/1.82 Those nodes are connected through the following edges: 3.93/1.82 3.93/1.82 * 1 to 3 labelled d_1(0)* 1 to 7 labelled b_1(0)* 1 to 6 labelled a_1(0), b_1(0)* 1 to 11 labelled b_1(1)* 1 to 15 labelled d_1(1)* 1 to 18 labelled a_1(1)* 1 to 37 labelled b_1(2)* 1 to 41 labelled d_1(2)* 1 to 45 labelled a_1(1)* 1 to 83 labelled b_1(2)* 1 to 87 labelled d_1(2)* 2 to 2 labelled #_1(0)* 3 to 4 labelled b_1(0)* 4 to 5 labelled c_1(0)* 5 to 6 labelled b_1(0)* 5 to 18 labelled a_1(1)* 5 to 37 labelled b_1(2)* 5 to 41 labelled d_1(2)* 5 to 45 labelled a_1(1)* 5 to 83 labelled b_1(2)* 5 to 87 labelled d_1(2)* 6 to 2 labelled d_1(0)* 6 to 18 labelled b_1(1), a_1(1)* 6 to 37 labelled b_1(2)* 6 to 41 labelled d_1(2)* 6 to 90 labelled a_1(2)* 6 to 91 labelled b_1(3)* 6 to 144 labelled d_1(3)* 6 to 87 labelled d_1(2)* 7 to 8 labelled b_1(0)* 8 to 9 labelled f_1(0)* 9 to 10 labelled b_1(0)* 9 to 45 labelled a_1(1)* 9 to 83 labelled b_1(2)* 9 to 87 labelled d_1(2)* 9 to 18 labelled a_1(1)* 9 to 37 labelled b_1(2)* 9 to 41 labelled d_1(2)* 10 to 2 labelled b_1(0)* 10 to 18 labelled a_1(1)* 10 to 37 labelled b_1(2)* 10 to 41 labelled d_1(2)* 10 to 87 labelled d_1(2)* 11 to 12 labelled b_1(1)* 12 to 13 labelled f_1(1)* 13 to 14 labelled b_1(1)* 13 to 90 labelled a_1(2)* 13 to 91 labelled b_1(3)* 13 to 144 labelled d_1(3)* 14 to 6 labelled b_1(1)* 14 to 18 labelled a_1(1)* 14 to 37 labelled b_1(2)* 14 to 41 labelled d_1(2)* 14 to 90 labelled a_1(2)* 14 to 91 labelled b_1(3)* 14 to 144 labelled d_1(3)* 14 to 87 labelled d_1(2)* 15 to 16 labelled b_1(1)* 16 to 17 labelled c_1(1)* 17 to 18 labelled b_1(1), a_1(1)* 17 to 37 labelled b_1(2)* 17 to 41 labelled d_1(2)* 17 to 90 labelled a_1(2)* 17 to 91 labelled b_1(3)* 17 to 144 labelled d_1(3)* 17 to 87 labelled d_1(2)* 18 to 2 labelled d_1(1)* 18 to 18 labelled b_1(1), a_1(1)* 18 to 37 labelled b_1(2)* 18 to 41 labelled d_1(1), d_1(2)* 18 to 90 labelled a_1(2)* 18 to 91 labelled b_1(3)* 18 to 144 labelled d_1(3), d_1(1)* 18 to 145 labelled d_1(1)* 18 to 87 labelled d_1(2), d_1(1)* 18 to 88 labelled d_1(1)* 37 to 38 labelled b_1(2)* 38 to 39 labelled f_1(2)* 39 to 40 labelled b_1(2)* 39 to 147 labelled a_1(3)* 39 to 148 labelled b_1(4)* 39 to 152 labelled d_1(4)* 40 to 18 labelled b_1(2), a_1(1)* 40 to 37 labelled b_1(2)* 40 to 41 labelled d_1(2)* 40 to 90 labelled a_1(2)* 40 to 147 labelled a_1(3)* 40 to 91 labelled b_1(3)* 40 to 148 labelled b_1(4)* 40 to 144 labelled d_1(3)* 40 to 152 labelled d_1(4)* 40 to 87 labelled d_1(2)* 41 to 42 labelled b_1(2)* 42 to 43 labelled c_1(2)* 43 to 44 labelled b_1(2)* 43 to 18 labelled a_1(1)* 43 to 37 labelled b_1(2)* 43 to 41 labelled d_1(2)* 43 to 147 labelled a_1(3)* 43 to 148 labelled b_1(4)* 43 to 152 labelled d_1(4)* 43 to 87 labelled d_1(2)* 44 to 2 labelled d_1(2)* 44 to 18 labelled b_1(1), a_1(1)* 44 to 37 labelled b_1(2)* 44 to 41 labelled d_1(2)* 44 to 90 labelled a_1(2)* 44 to 91 labelled b_1(3)* 44 to 144 labelled d_1(3), d_1(2)* 44 to 87 labelled d_1(2)* 45 to 42 labelled d_1(1)* 83 to 84 labelled b_1(2)* 84 to 85 labelled f_1(2)* 85 to 86 labelled b_1(2)* 86 to 45 labelled b_1(2)* 87 to 88 labelled b_1(2)* 88 to 89 labelled c_1(2)* 89 to 90 labelled b_1(2)* 90 to 42 labelled d_1(2)* 90 to 145 labelled d_1(2)* 90 to 88 labelled d_1(2)* 91 to 92 labelled b_1(3)* 92 to 93 labelled f_1(3)* 93 to 94 labelled b_1(3)* 94 to 90 labelled b_1(3)* 144 to 145 labelled b_1(3)* 145 to 146 labelled c_1(3)* 146 to 147 labelled b_1(3)* 147 to 42 labelled d_1(3)* 147 to 145 labelled d_1(3)* 147 to 153 labelled d_1(3)* 147 to 88 labelled d_1(3)* 148 to 149 labelled b_1(4)* 149 to 150 labelled f_1(4)* 150 to 151 labelled b_1(4)* 151 to 147 labelled b_1(4)* 152 to 153 labelled b_1(4)* 153 to 154 labelled c_1(4)* 154 to 155 labelled b_1(4)* 155 to 42 labelled d_1(4)* 155 to 145 labelled d_1(4)* 155 to 153 labelled d_1(4)* 155 to 88 labelled d_1(4) 3.93/1.82 3.93/1.82 3.93/1.82 ---------------------------------------- 3.93/1.82 3.93/1.82 (2) 3.93/1.82 YES 3.94/1.93 EOF