49.46/13.35 YES 49.46/13.37 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 49.46/13.37 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 49.46/13.37 49.46/13.37 49.46/13.37 Termination of the given RelTRS could be proven: 49.46/13.37 49.46/13.37 (0) RelTRS 49.46/13.37 (1) RelTRS Reverse [EQUIVALENT, 0 ms] 49.46/13.37 (2) RelTRS 49.46/13.37 (3) RelTRSRRRProof [EQUIVALENT, 1263 ms] 49.46/13.37 (4) RelTRS 49.46/13.37 (5) RelTRSRRRProof [EQUIVALENT, 69 ms] 49.46/13.37 (6) RelTRS 49.46/13.37 (7) RelTRSRRRProof [EQUIVALENT, 6 ms] 49.46/13.37 (8) RelTRS 49.46/13.37 (9) RelTRSRRRProof [EQUIVALENT, 0 ms] 49.46/13.37 (10) RelTRS 49.46/13.37 (11) SIsEmptyProof [EQUIVALENT, 0 ms] 49.46/13.37 (12) QTRS 49.46/13.37 (13) RFCMatchBoundsTRSProof [EQUIVALENT, 2 ms] 49.46/13.37 (14) YES 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (0) 49.46/13.37 Obligation: 49.46/13.37 Relative term rewrite system: 49.46/13.37 The relative TRS consists of the following R rules: 49.46/13.37 49.46/13.37 c(a(b(x1))) -> c(b(b(x1))) 49.46/13.37 b(c(c(x1))) -> c(c(c(x1))) 49.46/13.37 a(a(a(x1))) -> c(c(b(x1))) 49.46/13.37 49.46/13.37 The relative TRS consists of the following S rules: 49.46/13.37 49.46/13.37 c(b(b(x1))) -> c(c(c(x1))) 49.46/13.37 c(a(c(x1))) -> a(a(b(x1))) 49.46/13.37 b(c(b(x1))) -> b(b(b(x1))) 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (1) RelTRS Reverse (EQUIVALENT) 49.46/13.37 We have reversed the following relative TRS [REVERSE]: 49.46/13.37 The set of rules R is 49.46/13.37 c(a(b(x1))) -> c(b(b(x1))) 49.46/13.37 b(c(c(x1))) -> c(c(c(x1))) 49.46/13.37 a(a(a(x1))) -> c(c(b(x1))) 49.46/13.37 49.46/13.37 The set of rules S is 49.46/13.37 c(b(b(x1))) -> c(c(c(x1))) 49.46/13.37 c(a(c(x1))) -> a(a(b(x1))) 49.46/13.37 b(c(b(x1))) -> b(b(b(x1))) 49.46/13.37 49.46/13.37 We have obtained the following relative TRS: 49.46/13.37 The set of rules R is 49.46/13.37 b(a(c(x1))) -> b(b(c(x1))) 49.46/13.37 c(c(b(x1))) -> c(c(c(x1))) 49.46/13.37 a(a(a(x1))) -> b(c(c(x1))) 49.46/13.37 49.46/13.37 The set of rules S is 49.46/13.37 b(b(c(x1))) -> c(c(c(x1))) 49.46/13.37 c(a(c(x1))) -> b(a(a(x1))) 49.46/13.37 b(c(b(x1))) -> b(b(b(x1))) 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (2) 49.46/13.37 Obligation: 49.46/13.37 Relative term rewrite system: 49.46/13.37 The relative TRS consists of the following R rules: 49.46/13.37 49.46/13.37 b(a(c(x1))) -> b(b(c(x1))) 49.46/13.37 c(c(b(x1))) -> c(c(c(x1))) 49.46/13.37 a(a(a(x1))) -> b(c(c(x1))) 49.46/13.37 49.46/13.37 The relative TRS consists of the following S rules: 49.46/13.37 49.46/13.37 b(b(c(x1))) -> c(c(c(x1))) 49.46/13.37 c(a(c(x1))) -> b(a(a(x1))) 49.46/13.37 b(c(b(x1))) -> b(b(b(x1))) 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (3) RelTRSRRRProof (EQUIVALENT) 49.46/13.37 We used the following monotonic ordering for rule removal: 49.46/13.37 Matrix interpretation [MATRO] to (N^6, +, *, >=, >) : 49.46/13.37 49.46/13.37 <<< 49.46/13.37 POL(b(x_1)) = [[0], [0], [0], [0], [0], [0]] + [[1, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] * x_1 49.46/13.37 >>> 49.46/13.37 49.46/13.37 <<< 49.46/13.37 POL(a(x_1)) = [[0], [0], [0], [0], [1], [0]] + [[1, 1, 0, 1, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0], [0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 0, 0]] * x_1 49.46/13.37 >>> 49.46/13.37 49.46/13.37 <<< 49.46/13.37 POL(c(x_1)) = [[0], [0], [0], [0], [0], [0]] + [[1, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0], [0, 1, 0, 1, 1, 0]] * x_1 49.46/13.37 >>> 49.46/13.37 49.46/13.37 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 49.46/13.37 Rules from R: 49.46/13.37 49.46/13.37 a(a(a(x1))) -> b(c(c(x1))) 49.46/13.37 Rules from S: 49.46/13.37 none 49.46/13.37 49.46/13.37 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (4) 49.46/13.37 Obligation: 49.46/13.37 Relative term rewrite system: 49.46/13.37 The relative TRS consists of the following R rules: 49.46/13.37 49.46/13.37 b(a(c(x1))) -> b(b(c(x1))) 49.46/13.37 c(c(b(x1))) -> c(c(c(x1))) 49.46/13.37 49.46/13.37 The relative TRS consists of the following S rules: 49.46/13.37 49.46/13.37 b(b(c(x1))) -> c(c(c(x1))) 49.46/13.37 c(a(c(x1))) -> b(a(a(x1))) 49.46/13.37 b(c(b(x1))) -> b(b(b(x1))) 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (5) RelTRSRRRProof (EQUIVALENT) 49.46/13.37 We used the following monotonic ordering for rule removal: 49.46/13.37 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 49.46/13.37 49.46/13.37 <<< 49.46/13.37 POL(b(x_1)) = [[0], [0]] + [[2, 2], [0, 0]] * x_1 49.46/13.37 >>> 49.46/13.37 49.46/13.37 <<< 49.46/13.37 POL(a(x_1)) = [[0], [2]] + [[1, 0], [2, 0]] * x_1 49.46/13.37 >>> 49.46/13.37 49.46/13.37 <<< 49.46/13.37 POL(c(x_1)) = [[0], [0]] + [[2, 2], [0, 0]] * x_1 49.46/13.37 >>> 49.46/13.37 49.46/13.37 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 49.46/13.37 Rules from R: 49.46/13.37 49.46/13.37 b(a(c(x1))) -> b(b(c(x1))) 49.46/13.37 Rules from S: 49.46/13.37 none 49.46/13.37 49.46/13.37 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (6) 49.46/13.37 Obligation: 49.46/13.37 Relative term rewrite system: 49.46/13.37 The relative TRS consists of the following R rules: 49.46/13.37 49.46/13.37 c(c(b(x1))) -> c(c(c(x1))) 49.46/13.37 49.46/13.37 The relative TRS consists of the following S rules: 49.46/13.37 49.46/13.37 b(b(c(x1))) -> c(c(c(x1))) 49.46/13.37 c(a(c(x1))) -> b(a(a(x1))) 49.46/13.37 b(c(b(x1))) -> b(b(b(x1))) 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (7) RelTRSRRRProof (EQUIVALENT) 49.46/13.37 We used the following monotonic ordering for rule removal: 49.46/13.37 Polynomial interpretation [POLO]: 49.46/13.37 49.46/13.37 POL(a(x_1)) = x_1 49.46/13.37 POL(b(x_1)) = 1 + x_1 49.46/13.37 POL(c(x_1)) = 1 + x_1 49.46/13.37 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 49.46/13.37 Rules from R: 49.46/13.37 none 49.46/13.37 Rules from S: 49.46/13.37 49.46/13.37 c(a(c(x1))) -> b(a(a(x1))) 49.46/13.37 49.46/13.37 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (8) 49.46/13.37 Obligation: 49.46/13.37 Relative term rewrite system: 49.46/13.37 The relative TRS consists of the following R rules: 49.46/13.37 49.46/13.37 c(c(b(x1))) -> c(c(c(x1))) 49.46/13.37 49.46/13.37 The relative TRS consists of the following S rules: 49.46/13.37 49.46/13.37 b(b(c(x1))) -> c(c(c(x1))) 49.46/13.37 b(c(b(x1))) -> b(b(b(x1))) 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (9) RelTRSRRRProof (EQUIVALENT) 49.46/13.37 We used the following monotonic ordering for rule removal: 49.46/13.37 Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : 49.46/13.37 49.46/13.37 <<< 49.46/13.37 POL(c(x_1)) = [[0], [1]] + [[1, 0], [2, 0]] * x_1 49.46/13.37 >>> 49.46/13.37 49.46/13.37 <<< 49.46/13.37 POL(b(x_1)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 49.46/13.37 >>> 49.46/13.37 49.46/13.37 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 49.46/13.37 Rules from R: 49.46/13.37 none 49.46/13.37 Rules from S: 49.46/13.37 49.46/13.37 b(b(c(x1))) -> c(c(c(x1))) 49.46/13.37 b(c(b(x1))) -> b(b(b(x1))) 49.46/13.37 49.46/13.37 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (10) 49.46/13.37 Obligation: 49.46/13.37 Relative term rewrite system: 49.46/13.37 The relative TRS consists of the following R rules: 49.46/13.37 49.46/13.37 c(c(b(x1))) -> c(c(c(x1))) 49.46/13.37 49.46/13.37 S is empty. 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (11) SIsEmptyProof (EQUIVALENT) 49.46/13.37 The TRS S is empty. Hence, termination of R/S is equivalent to termination of R. 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (12) 49.46/13.37 Obligation: 49.46/13.37 Q restricted rewrite system: 49.46/13.37 The TRS R consists of the following rules: 49.46/13.37 49.46/13.37 c(c(b(x1))) -> c(c(c(x1))) 49.46/13.37 49.46/13.37 Q is empty. 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (13) RFCMatchBoundsTRSProof (EQUIVALENT) 49.46/13.37 Termination of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. This implies Q-termination of R. 49.46/13.37 The following rules were used to construct the certificate: 49.46/13.37 49.46/13.37 c(c(b(x1))) -> c(c(c(x1))) 49.46/13.37 49.46/13.37 The certificate found is represented by the following graph. 49.46/13.37 The certificate consists of the following enumerated nodes: 49.46/13.37 153, 154, 155, 156, 157, 158 49.46/13.37 49.46/13.37 Node 153 is start node and node 154 is final node. 49.46/13.37 49.46/13.37 Those nodes are connected through the following edges: 49.46/13.37 49.46/13.37 * 153 to 155 labelled c_1(0)* 154 to 154 labelled #_1(0)* 155 to 156 labelled c_1(0)* 155 to 157 labelled c_1(1)* 156 to 154 labelled c_1(0)* 156 to 157 labelled c_1(1)* 157 to 158 labelled c_1(1)* 157 to 157 labelled c_1(1)* 158 to 154 labelled c_1(1)* 158 to 157 labelled c_1(1) 49.46/13.37 49.46/13.37 49.46/13.37 ---------------------------------------- 49.46/13.37 49.46/13.37 (14) 49.46/13.37 YES 49.64/13.45 EOF