4.70/1.98 YES 4.70/1.99 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 4.70/1.99 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.70/1.99 4.70/1.99 4.70/1.99 Termination of the given RelTRS could be proven: 4.70/1.99 4.70/1.99 (0) RelTRS 4.70/1.99 (1) RelTRSRRRProof [EQUIVALENT, 50 ms] 4.70/1.99 (2) RelTRS 4.70/1.99 (3) RelTRSRRRProof [EQUIVALENT, 0 ms] 4.70/1.99 (4) RelTRS 4.70/1.99 (5) RelTRSRRRProof [EQUIVALENT, 6 ms] 4.70/1.99 (6) RelTRS 4.70/1.99 (7) RIsEmptyProof [EQUIVALENT, 0 ms] 4.70/1.99 (8) YES 4.70/1.99 4.70/1.99 4.70/1.99 ---------------------------------------- 4.70/1.99 4.70/1.99 (0) 4.70/1.99 Obligation: 4.70/1.99 Relative term rewrite system: 4.70/1.99 The relative TRS consists of the following R rules: 4.70/1.99 4.70/1.99 topB(i, N1, y) -> topA(1, T1, y) 4.70/1.99 topA(i, x, N2) -> topB(0, x, T2) 4.70/1.99 topB(i, S1, y) -> topA(i, N1, y) 4.70/1.99 topA(i, x, S2) -> topB(i, x, N2) 4.70/1.99 topA(i, N1, T2) -> topB(i, N1, S2) 4.70/1.99 topA(1, T1, T2) -> topB(1, T1, S2) 4.70/1.99 4.70/1.99 The relative TRS consists of the following S rules: 4.70/1.99 4.70/1.99 topA(i, N1, y) -> topA(1, T1, y) 4.70/1.99 topB(i, x, N2) -> topB(0, x, T2) 4.70/1.99 topA(i, S1, y) -> topA(i, N1, y) 4.70/1.99 topB(i, x, S2) -> topB(i, x, N2) 4.70/1.99 topB(i, N1, T2) -> topB(i, N1, S2) 4.70/1.99 topB(1, T1, T2) -> topB(1, T1, S2) 4.70/1.99 4.70/1.99 4.70/1.99 ---------------------------------------- 4.70/1.99 4.70/1.99 (1) RelTRSRRRProof (EQUIVALENT) 4.70/1.99 We used the following monotonic ordering for rule removal: 4.70/1.99 Polynomial interpretation [POLO]: 4.70/1.99 4.70/1.99 POL(0) = 0 4.70/1.99 POL(1) = 0 4.70/1.99 POL(N1) = 1 4.70/1.99 POL(N2) = 0 4.70/1.99 POL(S1) = 1 4.70/1.99 POL(S2) = 0 4.70/1.99 POL(T1) = 0 4.70/1.99 POL(T2) = 0 4.70/1.99 POL(topA(x_1, x_2, x_3)) = x_1 + x_2 + x_3 4.70/1.99 POL(topB(x_1, x_2, x_3)) = x_1 + x_2 + x_3 4.70/1.99 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 4.70/1.99 Rules from R: 4.70/1.99 4.70/1.99 topB(i, N1, y) -> topA(1, T1, y) 4.70/1.99 Rules from S: 4.70/1.99 4.70/1.99 topA(i, N1, y) -> topA(1, T1, y) 4.70/1.99 4.70/1.99 4.70/1.99 4.70/1.99 4.70/1.99 ---------------------------------------- 4.70/1.99 4.70/1.99 (2) 4.70/1.99 Obligation: 4.70/1.99 Relative term rewrite system: 4.70/1.99 The relative TRS consists of the following R rules: 4.70/1.99 4.70/1.99 topA(i, x, N2) -> topB(0, x, T2) 4.70/1.99 topB(i, S1, y) -> topA(i, N1, y) 4.70/1.99 topA(i, x, S2) -> topB(i, x, N2) 4.70/1.99 topA(i, N1, T2) -> topB(i, N1, S2) 4.70/1.99 topA(1, T1, T2) -> topB(1, T1, S2) 4.70/1.99 4.70/1.99 The relative TRS consists of the following S rules: 4.70/1.99 4.70/1.99 topB(i, x, N2) -> topB(0, x, T2) 4.70/1.99 topA(i, S1, y) -> topA(i, N1, y) 4.70/1.99 topB(i, x, S2) -> topB(i, x, N2) 4.70/1.99 topB(i, N1, T2) -> topB(i, N1, S2) 4.70/1.99 topB(1, T1, T2) -> topB(1, T1, S2) 4.70/1.99 4.70/1.99 4.70/1.99 ---------------------------------------- 4.70/1.99 4.70/1.99 (3) RelTRSRRRProof (EQUIVALENT) 4.70/1.99 We used the following monotonic ordering for rule removal: 4.70/1.99 Polynomial interpretation [POLO]: 4.70/1.99 4.70/1.99 POL(0) = 0 4.70/1.99 POL(1) = 0 4.70/1.99 POL(N1) = 0 4.70/1.99 POL(N2) = 0 4.70/1.99 POL(S1) = 1 4.70/1.99 POL(S2) = 0 4.70/1.99 POL(T1) = 0 4.70/1.99 POL(T2) = 0 4.70/1.99 POL(topA(x_1, x_2, x_3)) = x_1 + x_2 + x_3 4.70/1.99 POL(topB(x_1, x_2, x_3)) = x_1 + x_2 + x_3 4.70/1.99 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 4.70/1.99 Rules from R: 4.70/1.99 4.70/1.99 topB(i, S1, y) -> topA(i, N1, y) 4.70/1.99 Rules from S: 4.70/1.99 4.70/1.99 topA(i, S1, y) -> topA(i, N1, y) 4.70/1.99 4.70/1.99 4.70/1.99 4.70/1.99 4.70/1.99 ---------------------------------------- 4.70/1.99 4.70/1.99 (4) 4.70/1.99 Obligation: 4.70/1.99 Relative term rewrite system: 4.70/1.99 The relative TRS consists of the following R rules: 4.70/1.99 4.70/1.99 topA(i, x, N2) -> topB(0, x, T2) 4.70/1.99 topA(i, x, S2) -> topB(i, x, N2) 4.70/1.99 topA(i, N1, T2) -> topB(i, N1, S2) 4.70/1.99 topA(1, T1, T2) -> topB(1, T1, S2) 4.70/1.99 4.70/1.99 The relative TRS consists of the following S rules: 4.70/1.99 4.70/1.99 topB(i, x, N2) -> topB(0, x, T2) 4.70/1.99 topB(i, x, S2) -> topB(i, x, N2) 4.70/1.99 topB(i, N1, T2) -> topB(i, N1, S2) 4.70/1.99 topB(1, T1, T2) -> topB(1, T1, S2) 4.70/1.99 4.70/1.99 4.70/1.99 ---------------------------------------- 4.70/1.99 4.70/1.99 (5) RelTRSRRRProof (EQUIVALENT) 4.70/1.99 We used the following monotonic ordering for rule removal: 4.70/1.99 Polynomial interpretation [POLO]: 4.70/1.99 4.70/1.99 POL(0) = 0 4.70/1.99 POL(1) = 0 4.70/1.99 POL(N1) = 0 4.70/1.99 POL(N2) = 0 4.70/1.99 POL(S2) = 0 4.70/1.99 POL(T1) = 0 4.70/1.99 POL(T2) = 0 4.70/1.99 POL(topA(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 4.70/1.99 POL(topB(x_1, x_2, x_3)) = x_1 + x_2 + x_3 4.70/1.99 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 4.70/1.99 Rules from R: 4.70/1.99 4.70/1.99 topA(i, x, N2) -> topB(0, x, T2) 4.70/1.99 topA(i, x, S2) -> topB(i, x, N2) 4.70/1.99 topA(i, N1, T2) -> topB(i, N1, S2) 4.70/1.99 topA(1, T1, T2) -> topB(1, T1, S2) 4.70/1.99 Rules from S: 4.70/1.99 none 4.70/1.99 4.70/1.99 4.70/1.99 4.70/1.99 4.70/1.99 ---------------------------------------- 4.70/1.99 4.70/1.99 (6) 4.70/1.99 Obligation: 4.70/1.99 Relative term rewrite system: 4.70/1.99 R is empty. 4.70/1.99 The relative TRS consists of the following S rules: 4.70/1.99 4.70/1.99 topB(i, x, N2) -> topB(0, x, T2) 4.70/1.99 topB(i, x, S2) -> topB(i, x, N2) 4.70/1.99 topB(i, N1, T2) -> topB(i, N1, S2) 4.70/1.99 topB(1, T1, T2) -> topB(1, T1, S2) 4.70/1.99 4.70/1.99 4.70/1.99 ---------------------------------------- 4.70/1.99 4.70/1.99 (7) RIsEmptyProof (EQUIVALENT) 4.70/1.99 The TRS R is empty. Hence, termination is trivially proven. 4.70/1.99 ---------------------------------------- 4.70/1.99 4.70/1.99 (8) 4.70/1.99 YES 4.70/2.03 EOF