/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given RelTRS could be proven: (0) RelTRS (1) FlatCCProof [EQUIVALENT, 0 ms] (2) RelTRS (3) RootLabelingProof [EQUIVALENT, 64 ms] (4) RelTRS (5) RelTRSRRRProof [EQUIVALENT, 1007 ms] (6) RelTRS (7) RelTRSRRRProof [EQUIVALENT, 285 ms] (8) RelTRS (9) RelTRSRRRProof [EQUIVALENT, 142 ms] (10) RelTRS (11) RelTRSRRRProof [EQUIVALENT, 228 ms] (12) RelTRS (13) RelTRSRRRProof [EQUIVALENT, 31 ms] (14) RelTRS (15) RelTRSRRRProof [EQUIVALENT, 9 ms] (16) RelTRS (17) RelTRSRRRProof [EQUIVALENT, 15 ms] (18) RelTRS (19) RelTRSRRRProof [EQUIVALENT, 0 ms] (20) RelTRS (21) RelTRSRRRProof [EQUIVALENT, 10 ms] (22) RelTRS (23) RelTRSRRRProof [EQUIVALENT, 0 ms] (24) RelTRS (25) RelTRSRRRProof [EQUIVALENT, 9 ms] (26) RelTRS (27) RelTRSRRRProof [EQUIVALENT, 0 ms] (28) RelTRS (29) RelTRSRRRProof [EQUIVALENT, 2 ms] (30) RelTRS (31) RelTRSRRRProof [EQUIVALENT, 7 ms] (32) RelTRS (33) RelTRSRRRProof [EQUIVALENT, 0 ms] (34) RelTRS (35) RIsEmptyProof [EQUIVALENT, 0 ms] (36) YES ---------------------------------------- (0) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f(a, g(y), z) -> f(b, g(y), g(y)) f(b, g(y), z) -> f(a, y, z) a -> b The relative TRS consists of the following S rules: f(x, y, z) -> f(x, y, g(z)) ---------------------------------------- (1) FlatCCProof (EQUIVALENT) We used flat context closure [ROOTLAB] ---------------------------------------- (2) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f(a, g(y), z) -> f(b, g(y), g(y)) f(b, g(y), z) -> f(a, y, z) f(a, z1, z2) -> f(b, z1, z2) f(z0, a, z2) -> f(z0, b, z2) f(z0, z1, a) -> f(z0, z1, b) g(a) -> g(b) The relative TRS consists of the following S rules: f(x, y, z) -> f(x, y, g(z)) ---------------------------------------- (3) RootLabelingProof (EQUIVALENT) We used plain root labeling [ROOTLAB] with the following heuristic: LabelAll: All function symbols get labeled ---------------------------------------- (4) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,g_1,f_3}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,a}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,g_1}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,b}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,f_3}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,a}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,g_1}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,b}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,f_3}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,a}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,g_1}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,b}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,f_3}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,a}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,g_1}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,b}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{b,g_1,f_3}(b, g_{f_3}(y), z) -> f_{a,f_3,f_3}(a, y, z) f_{b,g_1,a}(b, g_{f_3}(y), z) -> f_{a,f_3,a}(a, y, z) f_{b,g_1,g_1}(b, g_{f_3}(y), z) -> f_{a,f_3,g_1}(a, y, z) f_{b,g_1,b}(b, g_{f_3}(y), z) -> f_{a,f_3,b}(a, y, z) f_{b,g_1,f_3}(b, g_{a}(y), z) -> f_{a,a,f_3}(a, y, z) f_{b,g_1,a}(b, g_{a}(y), z) -> f_{a,a,a}(a, y, z) f_{b,g_1,g_1}(b, g_{a}(y), z) -> f_{a,a,g_1}(a, y, z) f_{b,g_1,b}(b, g_{a}(y), z) -> f_{a,a,b}(a, y, z) f_{b,g_1,f_3}(b, g_{g_1}(y), z) -> f_{a,g_1,f_3}(a, y, z) f_{b,g_1,a}(b, g_{g_1}(y), z) -> f_{a,g_1,a}(a, y, z) f_{b,g_1,g_1}(b, g_{g_1}(y), z) -> f_{a,g_1,g_1}(a, y, z) f_{b,g_1,b}(b, g_{g_1}(y), z) -> f_{a,g_1,b}(a, y, z) f_{b,g_1,f_3}(b, g_{b}(y), z) -> f_{a,b,f_3}(a, y, z) f_{b,g_1,a}(b, g_{b}(y), z) -> f_{a,b,a}(a, y, z) f_{b,g_1,g_1}(b, g_{b}(y), z) -> f_{a,b,g_1}(a, y, z) f_{b,g_1,b}(b, g_{b}(y), z) -> f_{a,b,b}(a, y, z) f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) f_{a,f_3,a}(a, z1, z2) -> f_{b,f_3,a}(b, z1, z2) f_{a,f_3,g_1}(a, z1, z2) -> f_{b,f_3,g_1}(b, z1, z2) f_{a,f_3,b}(a, z1, z2) -> f_{b,f_3,b}(b, z1, z2) f_{a,a,f_3}(a, z1, z2) -> f_{b,a,f_3}(b, z1, z2) f_{a,a,a}(a, z1, z2) -> f_{b,a,a}(b, z1, z2) f_{a,a,g_1}(a, z1, z2) -> f_{b,a,g_1}(b, z1, z2) f_{a,a,b}(a, z1, z2) -> f_{b,a,b}(b, z1, z2) f_{a,g_1,f_3}(a, z1, z2) -> f_{b,g_1,f_3}(b, z1, z2) f_{a,g_1,a}(a, z1, z2) -> f_{b,g_1,a}(b, z1, z2) f_{a,g_1,g_1}(a, z1, z2) -> f_{b,g_1,g_1}(b, z1, z2) f_{a,g_1,b}(a, z1, z2) -> f_{b,g_1,b}(b, z1, z2) f_{a,b,f_3}(a, z1, z2) -> f_{b,b,f_3}(b, z1, z2) f_{a,b,a}(a, z1, z2) -> f_{b,b,a}(b, z1, z2) f_{a,b,g_1}(a, z1, z2) -> f_{b,b,g_1}(b, z1, z2) f_{a,b,b}(a, z1, z2) -> f_{b,b,b}(b, z1, z2) f_{f_3,a,f_3}(z0, a, z2) -> f_{f_3,b,f_3}(z0, b, z2) f_{f_3,a,a}(z0, a, z2) -> f_{f_3,b,a}(z0, b, z2) f_{f_3,a,g_1}(z0, a, z2) -> f_{f_3,b,g_1}(z0, b, z2) f_{f_3,a,b}(z0, a, z2) -> f_{f_3,b,b}(z0, b, z2) f_{a,a,f_3}(z0, a, z2) -> f_{a,b,f_3}(z0, b, z2) f_{a,a,a}(z0, a, z2) -> f_{a,b,a}(z0, b, z2) f_{a,a,g_1}(z0, a, z2) -> f_{a,b,g_1}(z0, b, z2) f_{a,a,b}(z0, a, z2) -> f_{a,b,b}(z0, b, z2) f_{g_1,a,f_3}(z0, a, z2) -> f_{g_1,b,f_3}(z0, b, z2) f_{g_1,a,a}(z0, a, z2) -> f_{g_1,b,a}(z0, b, z2) f_{g_1,a,g_1}(z0, a, z2) -> f_{g_1,b,g_1}(z0, b, z2) f_{g_1,a,b}(z0, a, z2) -> f_{g_1,b,b}(z0, b, z2) f_{b,a,f_3}(z0, a, z2) -> f_{b,b,f_3}(z0, b, z2) f_{b,a,a}(z0, a, z2) -> f_{b,b,a}(z0, b, z2) f_{b,a,g_1}(z0, a, z2) -> f_{b,b,g_1}(z0, b, z2) f_{b,a,b}(z0, a, z2) -> f_{b,b,b}(z0, b, z2) f_{f_3,f_3,a}(z0, z1, a) -> f_{f_3,f_3,b}(z0, z1, b) f_{f_3,a,a}(z0, z1, a) -> f_{f_3,a,b}(z0, z1, b) f_{f_3,g_1,a}(z0, z1, a) -> f_{f_3,g_1,b}(z0, z1, b) f_{f_3,b,a}(z0, z1, a) -> f_{f_3,b,b}(z0, z1, b) f_{a,f_3,a}(z0, z1, a) -> f_{a,f_3,b}(z0, z1, b) f_{a,a,a}(z0, z1, a) -> f_{a,a,b}(z0, z1, b) f_{a,g_1,a}(z0, z1, a) -> f_{a,g_1,b}(z0, z1, b) f_{a,b,a}(z0, z1, a) -> f_{a,b,b}(z0, z1, b) f_{g_1,f_3,a}(z0, z1, a) -> f_{g_1,f_3,b}(z0, z1, b) f_{g_1,a,a}(z0, z1, a) -> f_{g_1,a,b}(z0, z1, b) f_{g_1,g_1,a}(z0, z1, a) -> f_{g_1,g_1,b}(z0, z1, b) f_{g_1,b,a}(z0, z1, a) -> f_{g_1,b,b}(z0, z1, b) f_{b,f_3,a}(z0, z1, a) -> f_{b,f_3,b}(z0, z1, b) f_{b,a,a}(z0, z1, a) -> f_{b,a,b}(z0, z1, b) f_{b,g_1,a}(z0, z1, a) -> f_{b,g_1,b}(z0, z1, b) f_{b,b,a}(z0, z1, a) -> f_{b,b,b}(z0, z1, b) g_{a}(a) -> g_{b}(b) The relative TRS consists of the following S rules: f_{f_3,f_3,f_3}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{f_3}(z)) f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,f_3,b}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{b}(z)) f_{f_3,a,f_3}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{f_3}(z)) f_{f_3,a,a}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{a}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,b}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{b}(z)) f_{f_3,g_1,f_3}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{f_3}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) f_{f_3,b,f_3}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{f_3}(z)) f_{f_3,b,a}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{a}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,b}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{b}(z)) f_{a,f_3,f_3}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{f_3}(z)) f_{a,f_3,a}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{a}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,b}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{b}(z)) f_{a,a,f_3}(x, y, z) -> f_{a,a,g_1}(x, y, g_{f_3}(z)) f_{a,a,a}(x, y, z) -> f_{a,a,g_1}(x, y, g_{a}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,a,b}(x, y, z) -> f_{a,a,g_1}(x, y, g_{b}(z)) f_{a,g_1,f_3}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{f_3}(z)) f_{a,g_1,a}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{a}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,b}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{b}(z)) f_{a,b,f_3}(x, y, z) -> f_{a,b,g_1}(x, y, g_{f_3}(z)) f_{a,b,a}(x, y, z) -> f_{a,b,g_1}(x, y, g_{a}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{a,b,b}(x, y, z) -> f_{a,b,g_1}(x, y, g_{b}(z)) f_{g_1,f_3,f_3}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{f_3}(z)) f_{g_1,f_3,a}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{a}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,f_3}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{f_3}(z)) f_{g_1,a,a}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{a}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,a,b}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{b}(z)) f_{g_1,g_1,f_3}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{f_3}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,f_3}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{f_3}(z)) f_{g_1,b,a}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{a}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,b}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{b}(z)) f_{b,f_3,f_3}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{f_3}(z)) f_{b,f_3,a}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{a}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,b}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{b}(z)) f_{b,a,f_3}(x, y, z) -> f_{b,a,g_1}(x, y, g_{f_3}(z)) f_{b,a,a}(x, y, z) -> f_{b,a,g_1}(x, y, g_{a}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,a,b}(x, y, z) -> f_{b,a,g_1}(x, y, g_{b}(z)) f_{b,g_1,f_3}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{f_3}(z)) f_{b,g_1,a}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{a}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,b}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{b}(z)) f_{b,b,f_3}(x, y, z) -> f_{b,b,g_1}(x, y, g_{f_3}(z)) f_{b,b,a}(x, y, z) -> f_{b,b,g_1}(x, y, g_{a}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) f_{b,b,b}(x, y, z) -> f_{b,b,g_1}(x, y, g_{b}(z)) ---------------------------------------- (5) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(f_{a,g_1,f_3}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 1], [2, 1]] * x_1 + [[2, 1], [0, 2]] * x_2 + [[3, 0], [3, 3]] * x_3 >>> <<< POL(a) = [[0], [0]] >>> <<< POL(g_{f_3}(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(b) = [[0], [0]] >>> <<< POL(f_{a,g_1,a}(x_1, x_2, x_3)) = [[0], [2]] + [[2, 0], [0, 0]] * x_1 + [[3, 1], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 1], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,g_1,b}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[3, 1], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(g_{a}(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(g_{g_1}(x_1)) = [[0], [3]] + [[1, 0], [1, 1]] * x_1 >>> <<< POL(g_{b}(x_1)) = [[0], [0]] + [[1, 0], [0, 2]] * x_1 >>> <<< POL(f_{b,g_1,f_3}(x_1, x_2, x_3)) = [[0], [2]] + [[1, 2], [2, 2]] * x_1 + [[2, 1], [0, 2]] * x_2 + [[3, 0], [3, 3]] * x_3 >>> <<< POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 2], [2, 2]] * x_1 + [[3, 0], [2, 0]] * x_2 + [[3, 0], [3, 3]] * x_3 >>> <<< POL(f_{b,g_1,a}(x_1, x_2, x_3)) = [[0], [2]] + [[2, 0], [0, 0]] * x_1 + [[3, 1], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,f_3,a}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[3, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,g_1,b}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 1], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[3, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,a,f_3}(x_1, x_2, x_3)) = [[0], [2]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[3, 0], [3, 3]] * x_3 >>> <<< POL(f_{a,a,a}(x_1, x_2, x_3)) = [[0], [2]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[3, 0], [3, 3]] * x_3 >>> <<< POL(f_{a,b,a}(x_1, x_2, x_3)) = [[0], [2]] + [[1, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 2], [2, 2]] * x_1 + [[3, 0], [1, 0]] * x_2 + [[3, 0], [3, 3]] * x_3 >>> <<< POL(f_{b,f_3,a}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[3, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[3, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,a,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[3, 0], [3, 3]] * x_3 >>> <<< POL(f_{b,a,a}(x_1, x_2, x_3)) = [[0], [2]] + [[2, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[3, 0], [3, 3]] * x_3 >>> <<< POL(f_{b,b,a}(x_1, x_2, x_3)) = [[0], [1]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 0], [0, 0]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,a,f_3}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 3], [3, 3]] * x_1 + [[3, 1], [2, 2]] * x_2 + [[3, 3], [3, 3]] * x_3 >>> <<< POL(f_{f_3,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 1], [3, 3]] * x_1 + [[2, 1], [2, 2]] * x_2 + [[3, 3], [3, 3]] * x_3 >>> <<< POL(f_{f_3,a,a}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 3], [3, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,b,a}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 3], [3, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 2], [2, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 2], [2, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 2], [2, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{g_1,a,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 3]] * x_1 + [[2, 1], [2, 2]] * x_2 + [[3, 3], [3, 3]] * x_3 >>> <<< POL(f_{g_1,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 3]] * x_1 + [[3, 1], [2, 2]] * x_2 + [[3, 0], [3, 3]] * x_3 >>> <<< POL(f_{g_1,a,a}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 3], [3, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{g_1,b,a}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 3], [3, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 2], [1, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{g_1,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{g_1,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 2], [2, 3]] * x_1 + [[2, 0], [0, 0]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 3], [3, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[2, 2], [1, 0]] * x_3 >>> <<< POL(f_{f_3,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[2, 1], [1, 0]] * x_3 >>> <<< POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 3], [3, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[2, 2], [1, 0]] * x_3 >>> <<< POL(f_{f_3,g_1,b}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[2, 0], [1, 2]] * x_3 >>> <<< POL(f_{g_1,f_3,a}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 3], [3, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[2, 0], [2, 2]] * x_3 >>> <<< POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[2, 1], [1, 2]] * x_3 >>> <<< POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = [[0], [2]] + [[3, 3], [3, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[2, 0], [1, 2]] * x_3 >>> <<< POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[2, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,f_3,f_3}(x_1, x_2, x_3)) = [[3], [1]] + [[3, 3], [3, 2]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[3, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 2]] * x_1 + [[3, 3], [3, 2]] * x_2 + [[2, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,g_1,f_3}(x_1, x_2, x_3)) = [[1], [1]] + [[3, 3], [3, 2]] * x_1 + [[3, 2], [3, 3]] * x_2 + [[1, 1], [1, 3]] * x_3 >>> <<< POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 3], [3, 2]] * x_1 + [[3, 2], [3, 2]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{g_1,f_3,f_3}(x_1, x_2, x_3)) = [[3], [1]] + [[3, 2], [3, 3]] * x_1 + [[3, 3], [2, 3]] * x_2 + [[1, 3], [1, 1]] * x_3 >>> <<< POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[2, 2], [3, 3]] * x_1 + [[2, 3], [2, 3]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{g_1,g_1,f_3}(x_1, x_2, x_3)) = [[3], [1]] + [[3, 3], [3, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[3, 2], [2, 3]] * x_1 + [[3, 3], [3, 3]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: f_{b,g_1,f_3}(b, g_{g_1}(y), z) -> f_{a,g_1,f_3}(a, y, z) f_{b,g_1,a}(b, g_{g_1}(y), z) -> f_{a,g_1,a}(a, y, z) f_{b,g_1,g_1}(b, g_{g_1}(y), z) -> f_{a,g_1,g_1}(a, y, z) f_{b,g_1,b}(b, g_{g_1}(y), z) -> f_{a,g_1,b}(a, y, z) Rules from S: f_{f_3,f_3,f_3}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{f_3}(z)) f_{f_3,g_1,f_3}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{f_3}(z)) f_{g_1,f_3,f_3}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{f_3}(z)) f_{g_1,g_1,f_3}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{f_3}(z)) ---------------------------------------- (6) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,g_1,f_3}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,a}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,g_1}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,b}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,f_3}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,a}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,g_1}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,b}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,f_3}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,a}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,g_1}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,b}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,f_3}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,a}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,g_1}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,b}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{b,g_1,f_3}(b, g_{f_3}(y), z) -> f_{a,f_3,f_3}(a, y, z) f_{b,g_1,a}(b, g_{f_3}(y), z) -> f_{a,f_3,a}(a, y, z) f_{b,g_1,g_1}(b, g_{f_3}(y), z) -> f_{a,f_3,g_1}(a, y, z) f_{b,g_1,b}(b, g_{f_3}(y), z) -> f_{a,f_3,b}(a, y, z) f_{b,g_1,f_3}(b, g_{a}(y), z) -> f_{a,a,f_3}(a, y, z) f_{b,g_1,a}(b, g_{a}(y), z) -> f_{a,a,a}(a, y, z) f_{b,g_1,g_1}(b, g_{a}(y), z) -> f_{a,a,g_1}(a, y, z) f_{b,g_1,b}(b, g_{a}(y), z) -> f_{a,a,b}(a, y, z) f_{b,g_1,f_3}(b, g_{b}(y), z) -> f_{a,b,f_3}(a, y, z) f_{b,g_1,a}(b, g_{b}(y), z) -> f_{a,b,a}(a, y, z) f_{b,g_1,g_1}(b, g_{b}(y), z) -> f_{a,b,g_1}(a, y, z) f_{b,g_1,b}(b, g_{b}(y), z) -> f_{a,b,b}(a, y, z) f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) f_{a,f_3,a}(a, z1, z2) -> f_{b,f_3,a}(b, z1, z2) f_{a,f_3,g_1}(a, z1, z2) -> f_{b,f_3,g_1}(b, z1, z2) f_{a,f_3,b}(a, z1, z2) -> f_{b,f_3,b}(b, z1, z2) f_{a,a,f_3}(a, z1, z2) -> f_{b,a,f_3}(b, z1, z2) f_{a,a,a}(a, z1, z2) -> f_{b,a,a}(b, z1, z2) f_{a,a,g_1}(a, z1, z2) -> f_{b,a,g_1}(b, z1, z2) f_{a,a,b}(a, z1, z2) -> f_{b,a,b}(b, z1, z2) f_{a,g_1,f_3}(a, z1, z2) -> f_{b,g_1,f_3}(b, z1, z2) f_{a,g_1,a}(a, z1, z2) -> f_{b,g_1,a}(b, z1, z2) f_{a,g_1,g_1}(a, z1, z2) -> f_{b,g_1,g_1}(b, z1, z2) f_{a,g_1,b}(a, z1, z2) -> f_{b,g_1,b}(b, z1, z2) f_{a,b,f_3}(a, z1, z2) -> f_{b,b,f_3}(b, z1, z2) f_{a,b,a}(a, z1, z2) -> f_{b,b,a}(b, z1, z2) f_{a,b,g_1}(a, z1, z2) -> f_{b,b,g_1}(b, z1, z2) f_{a,b,b}(a, z1, z2) -> f_{b,b,b}(b, z1, z2) f_{f_3,a,f_3}(z0, a, z2) -> f_{f_3,b,f_3}(z0, b, z2) f_{f_3,a,a}(z0, a, z2) -> f_{f_3,b,a}(z0, b, z2) f_{f_3,a,g_1}(z0, a, z2) -> f_{f_3,b,g_1}(z0, b, z2) f_{f_3,a,b}(z0, a, z2) -> f_{f_3,b,b}(z0, b, z2) f_{a,a,f_3}(z0, a, z2) -> f_{a,b,f_3}(z0, b, z2) f_{a,a,a}(z0, a, z2) -> f_{a,b,a}(z0, b, z2) f_{a,a,g_1}(z0, a, z2) -> f_{a,b,g_1}(z0, b, z2) f_{a,a,b}(z0, a, z2) -> f_{a,b,b}(z0, b, z2) f_{g_1,a,f_3}(z0, a, z2) -> f_{g_1,b,f_3}(z0, b, z2) f_{g_1,a,a}(z0, a, z2) -> f_{g_1,b,a}(z0, b, z2) f_{g_1,a,g_1}(z0, a, z2) -> f_{g_1,b,g_1}(z0, b, z2) f_{g_1,a,b}(z0, a, z2) -> f_{g_1,b,b}(z0, b, z2) f_{b,a,f_3}(z0, a, z2) -> f_{b,b,f_3}(z0, b, z2) f_{b,a,a}(z0, a, z2) -> f_{b,b,a}(z0, b, z2) f_{b,a,g_1}(z0, a, z2) -> f_{b,b,g_1}(z0, b, z2) f_{b,a,b}(z0, a, z2) -> f_{b,b,b}(z0, b, z2) f_{f_3,f_3,a}(z0, z1, a) -> f_{f_3,f_3,b}(z0, z1, b) f_{f_3,a,a}(z0, z1, a) -> f_{f_3,a,b}(z0, z1, b) f_{f_3,g_1,a}(z0, z1, a) -> f_{f_3,g_1,b}(z0, z1, b) f_{f_3,b,a}(z0, z1, a) -> f_{f_3,b,b}(z0, z1, b) f_{a,f_3,a}(z0, z1, a) -> f_{a,f_3,b}(z0, z1, b) f_{a,a,a}(z0, z1, a) -> f_{a,a,b}(z0, z1, b) f_{a,g_1,a}(z0, z1, a) -> f_{a,g_1,b}(z0, z1, b) f_{a,b,a}(z0, z1, a) -> f_{a,b,b}(z0, z1, b) f_{g_1,f_3,a}(z0, z1, a) -> f_{g_1,f_3,b}(z0, z1, b) f_{g_1,a,a}(z0, z1, a) -> f_{g_1,a,b}(z0, z1, b) f_{g_1,g_1,a}(z0, z1, a) -> f_{g_1,g_1,b}(z0, z1, b) f_{g_1,b,a}(z0, z1, a) -> f_{g_1,b,b}(z0, z1, b) f_{b,f_3,a}(z0, z1, a) -> f_{b,f_3,b}(z0, z1, b) f_{b,a,a}(z0, z1, a) -> f_{b,a,b}(z0, z1, b) f_{b,g_1,a}(z0, z1, a) -> f_{b,g_1,b}(z0, z1, b) f_{b,b,a}(z0, z1, a) -> f_{b,b,b}(z0, z1, b) g_{a}(a) -> g_{b}(b) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,f_3,b}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{b}(z)) f_{f_3,a,f_3}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{f_3}(z)) f_{f_3,a,a}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{a}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,b}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{b}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) f_{f_3,b,f_3}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{f_3}(z)) f_{f_3,b,a}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{a}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,b}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{b}(z)) f_{a,f_3,f_3}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{f_3}(z)) f_{a,f_3,a}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{a}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,b}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{b}(z)) f_{a,a,f_3}(x, y, z) -> f_{a,a,g_1}(x, y, g_{f_3}(z)) f_{a,a,a}(x, y, z) -> f_{a,a,g_1}(x, y, g_{a}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,a,b}(x, y, z) -> f_{a,a,g_1}(x, y, g_{b}(z)) f_{a,g_1,f_3}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{f_3}(z)) f_{a,g_1,a}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{a}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,b}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{b}(z)) f_{a,b,f_3}(x, y, z) -> f_{a,b,g_1}(x, y, g_{f_3}(z)) f_{a,b,a}(x, y, z) -> f_{a,b,g_1}(x, y, g_{a}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{a,b,b}(x, y, z) -> f_{a,b,g_1}(x, y, g_{b}(z)) f_{g_1,f_3,a}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{a}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,f_3}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{f_3}(z)) f_{g_1,a,a}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{a}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,a,b}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{b}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,f_3}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{f_3}(z)) f_{g_1,b,a}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{a}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,b}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{b}(z)) f_{b,f_3,f_3}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{f_3}(z)) f_{b,f_3,a}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{a}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,b}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{b}(z)) f_{b,a,f_3}(x, y, z) -> f_{b,a,g_1}(x, y, g_{f_3}(z)) f_{b,a,a}(x, y, z) -> f_{b,a,g_1}(x, y, g_{a}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,a,b}(x, y, z) -> f_{b,a,g_1}(x, y, g_{b}(z)) f_{b,g_1,f_3}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{f_3}(z)) f_{b,g_1,a}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{a}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,b}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{b}(z)) f_{b,b,f_3}(x, y, z) -> f_{b,b,g_1}(x, y, g_{f_3}(z)) f_{b,b,a}(x, y, z) -> f_{b,b,g_1}(x, y, g_{a}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) f_{b,b,b}(x, y, z) -> f_{b,b,g_1}(x, y, g_{b}(z)) ---------------------------------------- (7) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(f_{a,g_1,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 0], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(a) = [[0], [1]] >>> <<< POL(g_{f_3}(x_1)) = [[0], [1]] + [[1, 0], [1, 1]] * x_1 >>> <<< POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(b) = [[0], [0]] >>> <<< POL(f_{a,g_1,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 0], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 0], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,g_1,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 0], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(g_{a}(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(g_{g_1}(x_1)) = [[0], [0]] + [[1, 0], [1, 1]] * x_1 >>> <<< POL(g_{b}(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(f_{b,g_1,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,g_1,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,f_3,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,g_1,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,a,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,f_3,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,a,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,a,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,b,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,a,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,b,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 0]] * x_3 >>> <<< POL(f_{g_1,a,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,g_1,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,f_3,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 0]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: f_{a,g_1,f_3}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,a}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,g_1}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) f_{a,g_1,b}(a, g_{f_3}(y), z) -> f_{b,g_1,g_1}(b, g_{f_3}(y), g_{f_3}(y)) Rules from S: none ---------------------------------------- (8) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,g_1,f_3}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,a}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,g_1}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,b}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,f_3}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,a}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,g_1}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,b}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,f_3}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,a}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,g_1}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,b}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{b,g_1,f_3}(b, g_{f_3}(y), z) -> f_{a,f_3,f_3}(a, y, z) f_{b,g_1,a}(b, g_{f_3}(y), z) -> f_{a,f_3,a}(a, y, z) f_{b,g_1,g_1}(b, g_{f_3}(y), z) -> f_{a,f_3,g_1}(a, y, z) f_{b,g_1,b}(b, g_{f_3}(y), z) -> f_{a,f_3,b}(a, y, z) f_{b,g_1,f_3}(b, g_{a}(y), z) -> f_{a,a,f_3}(a, y, z) f_{b,g_1,a}(b, g_{a}(y), z) -> f_{a,a,a}(a, y, z) f_{b,g_1,g_1}(b, g_{a}(y), z) -> f_{a,a,g_1}(a, y, z) f_{b,g_1,b}(b, g_{a}(y), z) -> f_{a,a,b}(a, y, z) f_{b,g_1,f_3}(b, g_{b}(y), z) -> f_{a,b,f_3}(a, y, z) f_{b,g_1,a}(b, g_{b}(y), z) -> f_{a,b,a}(a, y, z) f_{b,g_1,g_1}(b, g_{b}(y), z) -> f_{a,b,g_1}(a, y, z) f_{b,g_1,b}(b, g_{b}(y), z) -> f_{a,b,b}(a, y, z) f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) f_{a,f_3,a}(a, z1, z2) -> f_{b,f_3,a}(b, z1, z2) f_{a,f_3,g_1}(a, z1, z2) -> f_{b,f_3,g_1}(b, z1, z2) f_{a,f_3,b}(a, z1, z2) -> f_{b,f_3,b}(b, z1, z2) f_{a,a,f_3}(a, z1, z2) -> f_{b,a,f_3}(b, z1, z2) f_{a,a,a}(a, z1, z2) -> f_{b,a,a}(b, z1, z2) f_{a,a,g_1}(a, z1, z2) -> f_{b,a,g_1}(b, z1, z2) f_{a,a,b}(a, z1, z2) -> f_{b,a,b}(b, z1, z2) f_{a,g_1,f_3}(a, z1, z2) -> f_{b,g_1,f_3}(b, z1, z2) f_{a,g_1,a}(a, z1, z2) -> f_{b,g_1,a}(b, z1, z2) f_{a,g_1,g_1}(a, z1, z2) -> f_{b,g_1,g_1}(b, z1, z2) f_{a,g_1,b}(a, z1, z2) -> f_{b,g_1,b}(b, z1, z2) f_{a,b,f_3}(a, z1, z2) -> f_{b,b,f_3}(b, z1, z2) f_{a,b,a}(a, z1, z2) -> f_{b,b,a}(b, z1, z2) f_{a,b,g_1}(a, z1, z2) -> f_{b,b,g_1}(b, z1, z2) f_{a,b,b}(a, z1, z2) -> f_{b,b,b}(b, z1, z2) f_{f_3,a,f_3}(z0, a, z2) -> f_{f_3,b,f_3}(z0, b, z2) f_{f_3,a,a}(z0, a, z2) -> f_{f_3,b,a}(z0, b, z2) f_{f_3,a,g_1}(z0, a, z2) -> f_{f_3,b,g_1}(z0, b, z2) f_{f_3,a,b}(z0, a, z2) -> f_{f_3,b,b}(z0, b, z2) f_{a,a,f_3}(z0, a, z2) -> f_{a,b,f_3}(z0, b, z2) f_{a,a,a}(z0, a, z2) -> f_{a,b,a}(z0, b, z2) f_{a,a,g_1}(z0, a, z2) -> f_{a,b,g_1}(z0, b, z2) f_{a,a,b}(z0, a, z2) -> f_{a,b,b}(z0, b, z2) f_{g_1,a,f_3}(z0, a, z2) -> f_{g_1,b,f_3}(z0, b, z2) f_{g_1,a,a}(z0, a, z2) -> f_{g_1,b,a}(z0, b, z2) f_{g_1,a,g_1}(z0, a, z2) -> f_{g_1,b,g_1}(z0, b, z2) f_{g_1,a,b}(z0, a, z2) -> f_{g_1,b,b}(z0, b, z2) f_{b,a,f_3}(z0, a, z2) -> f_{b,b,f_3}(z0, b, z2) f_{b,a,a}(z0, a, z2) -> f_{b,b,a}(z0, b, z2) f_{b,a,g_1}(z0, a, z2) -> f_{b,b,g_1}(z0, b, z2) f_{b,a,b}(z0, a, z2) -> f_{b,b,b}(z0, b, z2) f_{f_3,f_3,a}(z0, z1, a) -> f_{f_3,f_3,b}(z0, z1, b) f_{f_3,a,a}(z0, z1, a) -> f_{f_3,a,b}(z0, z1, b) f_{f_3,g_1,a}(z0, z1, a) -> f_{f_3,g_1,b}(z0, z1, b) f_{f_3,b,a}(z0, z1, a) -> f_{f_3,b,b}(z0, z1, b) f_{a,f_3,a}(z0, z1, a) -> f_{a,f_3,b}(z0, z1, b) f_{a,a,a}(z0, z1, a) -> f_{a,a,b}(z0, z1, b) f_{a,g_1,a}(z0, z1, a) -> f_{a,g_1,b}(z0, z1, b) f_{a,b,a}(z0, z1, a) -> f_{a,b,b}(z0, z1, b) f_{g_1,f_3,a}(z0, z1, a) -> f_{g_1,f_3,b}(z0, z1, b) f_{g_1,a,a}(z0, z1, a) -> f_{g_1,a,b}(z0, z1, b) f_{g_1,g_1,a}(z0, z1, a) -> f_{g_1,g_1,b}(z0, z1, b) f_{g_1,b,a}(z0, z1, a) -> f_{g_1,b,b}(z0, z1, b) f_{b,f_3,a}(z0, z1, a) -> f_{b,f_3,b}(z0, z1, b) f_{b,a,a}(z0, z1, a) -> f_{b,a,b}(z0, z1, b) f_{b,g_1,a}(z0, z1, a) -> f_{b,g_1,b}(z0, z1, b) f_{b,b,a}(z0, z1, a) -> f_{b,b,b}(z0, z1, b) g_{a}(a) -> g_{b}(b) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,f_3,b}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{b}(z)) f_{f_3,a,f_3}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{f_3}(z)) f_{f_3,a,a}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{a}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,b}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{b}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) f_{f_3,b,f_3}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{f_3}(z)) f_{f_3,b,a}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{a}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,b}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{b}(z)) f_{a,f_3,f_3}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{f_3}(z)) f_{a,f_3,a}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{a}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,b}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{b}(z)) f_{a,a,f_3}(x, y, z) -> f_{a,a,g_1}(x, y, g_{f_3}(z)) f_{a,a,a}(x, y, z) -> f_{a,a,g_1}(x, y, g_{a}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,a,b}(x, y, z) -> f_{a,a,g_1}(x, y, g_{b}(z)) f_{a,g_1,f_3}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{f_3}(z)) f_{a,g_1,a}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{a}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,b}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{b}(z)) f_{a,b,f_3}(x, y, z) -> f_{a,b,g_1}(x, y, g_{f_3}(z)) f_{a,b,a}(x, y, z) -> f_{a,b,g_1}(x, y, g_{a}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{a,b,b}(x, y, z) -> f_{a,b,g_1}(x, y, g_{b}(z)) f_{g_1,f_3,a}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{a}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,f_3}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{f_3}(z)) f_{g_1,a,a}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{a}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,a,b}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{b}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,f_3}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{f_3}(z)) f_{g_1,b,a}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{a}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,b}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{b}(z)) f_{b,f_3,f_3}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{f_3}(z)) f_{b,f_3,a}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{a}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,b}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{b}(z)) f_{b,a,f_3}(x, y, z) -> f_{b,a,g_1}(x, y, g_{f_3}(z)) f_{b,a,a}(x, y, z) -> f_{b,a,g_1}(x, y, g_{a}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,a,b}(x, y, z) -> f_{b,a,g_1}(x, y, g_{b}(z)) f_{b,g_1,f_3}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{f_3}(z)) f_{b,g_1,a}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{a}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,b}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{b}(z)) f_{b,b,f_3}(x, y, z) -> f_{b,b,g_1}(x, y, g_{f_3}(z)) f_{b,b,a}(x, y, z) -> f_{b,b,g_1}(x, y, g_{a}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) f_{b,b,b}(x, y, z) -> f_{b,b,g_1}(x, y, g_{b}(z)) ---------------------------------------- (9) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(f_{a,g_1,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(a) = [[0], [1]] >>> <<< POL(g_{a}(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(b) = [[0], [1]] >>> <<< POL(f_{a,g_1,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,g_1,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(g_{g_1}(x_1)) = [[0], [0]] + [[1, 0], [1, 1]] * x_1 >>> <<< POL(g_{b}(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(f_{b,g_1,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(g_{f_3}(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,g_1,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,f_3,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,g_1,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,a,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{a,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,f_3,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,a,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [0, 1]] * x_3 >>> <<< POL(f_{b,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{b,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(f_{f_3,a,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,b,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,a,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,g_1,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,f_3,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [0, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 0], [1, 1]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: f_{b,g_1,f_3}(b, g_{f_3}(y), z) -> f_{a,f_3,f_3}(a, y, z) f_{b,g_1,a}(b, g_{f_3}(y), z) -> f_{a,f_3,a}(a, y, z) f_{b,g_1,g_1}(b, g_{f_3}(y), z) -> f_{a,f_3,g_1}(a, y, z) f_{b,g_1,b}(b, g_{f_3}(y), z) -> f_{a,f_3,b}(a, y, z) f_{b,g_1,f_3}(b, g_{a}(y), z) -> f_{a,a,f_3}(a, y, z) f_{b,g_1,a}(b, g_{a}(y), z) -> f_{a,a,a}(a, y, z) f_{b,g_1,g_1}(b, g_{a}(y), z) -> f_{a,a,g_1}(a, y, z) f_{b,g_1,b}(b, g_{a}(y), z) -> f_{a,a,b}(a, y, z) f_{b,g_1,f_3}(b, g_{b}(y), z) -> f_{a,b,f_3}(a, y, z) f_{b,g_1,a}(b, g_{b}(y), z) -> f_{a,b,a}(a, y, z) f_{b,g_1,g_1}(b, g_{b}(y), z) -> f_{a,b,g_1}(a, y, z) f_{b,g_1,b}(b, g_{b}(y), z) -> f_{a,b,b}(a, y, z) Rules from S: none ---------------------------------------- (10) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,g_1,f_3}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,a}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,g_1}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,b}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,f_3}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,a}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,g_1}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,b}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,f_3}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,a}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,g_1}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,b}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) f_{a,f_3,a}(a, z1, z2) -> f_{b,f_3,a}(b, z1, z2) f_{a,f_3,g_1}(a, z1, z2) -> f_{b,f_3,g_1}(b, z1, z2) f_{a,f_3,b}(a, z1, z2) -> f_{b,f_3,b}(b, z1, z2) f_{a,a,f_3}(a, z1, z2) -> f_{b,a,f_3}(b, z1, z2) f_{a,a,a}(a, z1, z2) -> f_{b,a,a}(b, z1, z2) f_{a,a,g_1}(a, z1, z2) -> f_{b,a,g_1}(b, z1, z2) f_{a,a,b}(a, z1, z2) -> f_{b,a,b}(b, z1, z2) f_{a,g_1,f_3}(a, z1, z2) -> f_{b,g_1,f_3}(b, z1, z2) f_{a,g_1,a}(a, z1, z2) -> f_{b,g_1,a}(b, z1, z2) f_{a,g_1,g_1}(a, z1, z2) -> f_{b,g_1,g_1}(b, z1, z2) f_{a,g_1,b}(a, z1, z2) -> f_{b,g_1,b}(b, z1, z2) f_{a,b,f_3}(a, z1, z2) -> f_{b,b,f_3}(b, z1, z2) f_{a,b,a}(a, z1, z2) -> f_{b,b,a}(b, z1, z2) f_{a,b,g_1}(a, z1, z2) -> f_{b,b,g_1}(b, z1, z2) f_{a,b,b}(a, z1, z2) -> f_{b,b,b}(b, z1, z2) f_{f_3,a,f_3}(z0, a, z2) -> f_{f_3,b,f_3}(z0, b, z2) f_{f_3,a,a}(z0, a, z2) -> f_{f_3,b,a}(z0, b, z2) f_{f_3,a,g_1}(z0, a, z2) -> f_{f_3,b,g_1}(z0, b, z2) f_{f_3,a,b}(z0, a, z2) -> f_{f_3,b,b}(z0, b, z2) f_{a,a,f_3}(z0, a, z2) -> f_{a,b,f_3}(z0, b, z2) f_{a,a,a}(z0, a, z2) -> f_{a,b,a}(z0, b, z2) f_{a,a,g_1}(z0, a, z2) -> f_{a,b,g_1}(z0, b, z2) f_{a,a,b}(z0, a, z2) -> f_{a,b,b}(z0, b, z2) f_{g_1,a,f_3}(z0, a, z2) -> f_{g_1,b,f_3}(z0, b, z2) f_{g_1,a,a}(z0, a, z2) -> f_{g_1,b,a}(z0, b, z2) f_{g_1,a,g_1}(z0, a, z2) -> f_{g_1,b,g_1}(z0, b, z2) f_{g_1,a,b}(z0, a, z2) -> f_{g_1,b,b}(z0, b, z2) f_{b,a,f_3}(z0, a, z2) -> f_{b,b,f_3}(z0, b, z2) f_{b,a,a}(z0, a, z2) -> f_{b,b,a}(z0, b, z2) f_{b,a,g_1}(z0, a, z2) -> f_{b,b,g_1}(z0, b, z2) f_{b,a,b}(z0, a, z2) -> f_{b,b,b}(z0, b, z2) f_{f_3,f_3,a}(z0, z1, a) -> f_{f_3,f_3,b}(z0, z1, b) f_{f_3,a,a}(z0, z1, a) -> f_{f_3,a,b}(z0, z1, b) f_{f_3,g_1,a}(z0, z1, a) -> f_{f_3,g_1,b}(z0, z1, b) f_{f_3,b,a}(z0, z1, a) -> f_{f_3,b,b}(z0, z1, b) f_{a,f_3,a}(z0, z1, a) -> f_{a,f_3,b}(z0, z1, b) f_{a,a,a}(z0, z1, a) -> f_{a,a,b}(z0, z1, b) f_{a,g_1,a}(z0, z1, a) -> f_{a,g_1,b}(z0, z1, b) f_{a,b,a}(z0, z1, a) -> f_{a,b,b}(z0, z1, b) f_{g_1,f_3,a}(z0, z1, a) -> f_{g_1,f_3,b}(z0, z1, b) f_{g_1,a,a}(z0, z1, a) -> f_{g_1,a,b}(z0, z1, b) f_{g_1,g_1,a}(z0, z1, a) -> f_{g_1,g_1,b}(z0, z1, b) f_{g_1,b,a}(z0, z1, a) -> f_{g_1,b,b}(z0, z1, b) f_{b,f_3,a}(z0, z1, a) -> f_{b,f_3,b}(z0, z1, b) f_{b,a,a}(z0, z1, a) -> f_{b,a,b}(z0, z1, b) f_{b,g_1,a}(z0, z1, a) -> f_{b,g_1,b}(z0, z1, b) f_{b,b,a}(z0, z1, a) -> f_{b,b,b}(z0, z1, b) g_{a}(a) -> g_{b}(b) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,f_3,b}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{b}(z)) f_{f_3,a,f_3}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{f_3}(z)) f_{f_3,a,a}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{a}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,b}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{b}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) f_{f_3,b,f_3}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{f_3}(z)) f_{f_3,b,a}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{a}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,b}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{b}(z)) f_{a,f_3,f_3}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{f_3}(z)) f_{a,f_3,a}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{a}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,b}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{b}(z)) f_{a,a,f_3}(x, y, z) -> f_{a,a,g_1}(x, y, g_{f_3}(z)) f_{a,a,a}(x, y, z) -> f_{a,a,g_1}(x, y, g_{a}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,a,b}(x, y, z) -> f_{a,a,g_1}(x, y, g_{b}(z)) f_{a,g_1,f_3}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{f_3}(z)) f_{a,g_1,a}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{a}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,b}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{b}(z)) f_{a,b,f_3}(x, y, z) -> f_{a,b,g_1}(x, y, g_{f_3}(z)) f_{a,b,a}(x, y, z) -> f_{a,b,g_1}(x, y, g_{a}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{a,b,b}(x, y, z) -> f_{a,b,g_1}(x, y, g_{b}(z)) f_{g_1,f_3,a}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{a}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,f_3}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{f_3}(z)) f_{g_1,a,a}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{a}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,a,b}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{b}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,f_3}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{f_3}(z)) f_{g_1,b,a}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{a}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,b}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{b}(z)) f_{b,f_3,f_3}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{f_3}(z)) f_{b,f_3,a}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{a}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,b}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{b}(z)) f_{b,a,f_3}(x, y, z) -> f_{b,a,g_1}(x, y, g_{f_3}(z)) f_{b,a,a}(x, y, z) -> f_{b,a,g_1}(x, y, g_{a}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,a,b}(x, y, z) -> f_{b,a,g_1}(x, y, g_{b}(z)) f_{b,g_1,f_3}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{f_3}(z)) f_{b,g_1,a}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{a}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,b}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{b}(z)) f_{b,b,f_3}(x, y, z) -> f_{b,b,g_1}(x, y, g_{f_3}(z)) f_{b,b,a}(x, y, z) -> f_{b,b,g_1}(x, y, g_{a}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) f_{b,b,b}(x, y, z) -> f_{b,b,g_1}(x, y, g_{b}(z)) ---------------------------------------- (11) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(f_{a,g_1,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 0], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(a) = [[0], [1]] >>> <<< POL(g_{a}(x_1)) = [[0], [1]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(b) = [[0], [0]] >>> <<< POL(f_{a,g_1,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,g_1,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [0, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(g_{g_1}(x_1)) = [[0], [1]] + [[1, 0], [1, 1]] * x_1 >>> <<< POL(g_{b}(x_1)) = [[0], [1]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,f_3,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{b,f_3,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,f_3,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,a,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,a,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{b,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{b,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,g_1,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,g_1,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [0, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{b,g_1,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [0, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{a,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{b,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{b,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{a,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{b,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,a,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,b,f_3}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{f_3,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,a,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,b,f_3}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,a,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,b,a}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,a,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,b,b}(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{f_3,g_1,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,f_3,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 1]] * x_3 >>> <<< POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [1, 1]] * x_3 >>> <<< POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(g_{f_3}(x_1)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [0, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: f_{a,g_1,f_3}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,a}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,g_1}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,b}(a, g_{a}(y), z) -> f_{b,g_1,g_1}(b, g_{a}(y), g_{a}(y)) f_{a,g_1,f_3}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,a}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,g_1}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,b}(a, g_{g_1}(y), z) -> f_{b,g_1,g_1}(b, g_{g_1}(y), g_{g_1}(y)) f_{a,g_1,f_3}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,a}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,g_1}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) f_{a,g_1,b}(a, g_{b}(y), z) -> f_{b,g_1,g_1}(b, g_{b}(y), g_{b}(y)) Rules from S: none ---------------------------------------- (12) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) f_{a,f_3,a}(a, z1, z2) -> f_{b,f_3,a}(b, z1, z2) f_{a,f_3,g_1}(a, z1, z2) -> f_{b,f_3,g_1}(b, z1, z2) f_{a,f_3,b}(a, z1, z2) -> f_{b,f_3,b}(b, z1, z2) f_{a,a,f_3}(a, z1, z2) -> f_{b,a,f_3}(b, z1, z2) f_{a,a,a}(a, z1, z2) -> f_{b,a,a}(b, z1, z2) f_{a,a,g_1}(a, z1, z2) -> f_{b,a,g_1}(b, z1, z2) f_{a,a,b}(a, z1, z2) -> f_{b,a,b}(b, z1, z2) f_{a,g_1,f_3}(a, z1, z2) -> f_{b,g_1,f_3}(b, z1, z2) f_{a,g_1,a}(a, z1, z2) -> f_{b,g_1,a}(b, z1, z2) f_{a,g_1,g_1}(a, z1, z2) -> f_{b,g_1,g_1}(b, z1, z2) f_{a,g_1,b}(a, z1, z2) -> f_{b,g_1,b}(b, z1, z2) f_{a,b,f_3}(a, z1, z2) -> f_{b,b,f_3}(b, z1, z2) f_{a,b,a}(a, z1, z2) -> f_{b,b,a}(b, z1, z2) f_{a,b,g_1}(a, z1, z2) -> f_{b,b,g_1}(b, z1, z2) f_{a,b,b}(a, z1, z2) -> f_{b,b,b}(b, z1, z2) f_{f_3,a,f_3}(z0, a, z2) -> f_{f_3,b,f_3}(z0, b, z2) f_{f_3,a,a}(z0, a, z2) -> f_{f_3,b,a}(z0, b, z2) f_{f_3,a,g_1}(z0, a, z2) -> f_{f_3,b,g_1}(z0, b, z2) f_{f_3,a,b}(z0, a, z2) -> f_{f_3,b,b}(z0, b, z2) f_{a,a,f_3}(z0, a, z2) -> f_{a,b,f_3}(z0, b, z2) f_{a,a,a}(z0, a, z2) -> f_{a,b,a}(z0, b, z2) f_{a,a,g_1}(z0, a, z2) -> f_{a,b,g_1}(z0, b, z2) f_{a,a,b}(z0, a, z2) -> f_{a,b,b}(z0, b, z2) f_{g_1,a,f_3}(z0, a, z2) -> f_{g_1,b,f_3}(z0, b, z2) f_{g_1,a,a}(z0, a, z2) -> f_{g_1,b,a}(z0, b, z2) f_{g_1,a,g_1}(z0, a, z2) -> f_{g_1,b,g_1}(z0, b, z2) f_{g_1,a,b}(z0, a, z2) -> f_{g_1,b,b}(z0, b, z2) f_{b,a,f_3}(z0, a, z2) -> f_{b,b,f_3}(z0, b, z2) f_{b,a,a}(z0, a, z2) -> f_{b,b,a}(z0, b, z2) f_{b,a,g_1}(z0, a, z2) -> f_{b,b,g_1}(z0, b, z2) f_{b,a,b}(z0, a, z2) -> f_{b,b,b}(z0, b, z2) f_{f_3,f_3,a}(z0, z1, a) -> f_{f_3,f_3,b}(z0, z1, b) f_{f_3,a,a}(z0, z1, a) -> f_{f_3,a,b}(z0, z1, b) f_{f_3,g_1,a}(z0, z1, a) -> f_{f_3,g_1,b}(z0, z1, b) f_{f_3,b,a}(z0, z1, a) -> f_{f_3,b,b}(z0, z1, b) f_{a,f_3,a}(z0, z1, a) -> f_{a,f_3,b}(z0, z1, b) f_{a,a,a}(z0, z1, a) -> f_{a,a,b}(z0, z1, b) f_{a,g_1,a}(z0, z1, a) -> f_{a,g_1,b}(z0, z1, b) f_{a,b,a}(z0, z1, a) -> f_{a,b,b}(z0, z1, b) f_{g_1,f_3,a}(z0, z1, a) -> f_{g_1,f_3,b}(z0, z1, b) f_{g_1,a,a}(z0, z1, a) -> f_{g_1,a,b}(z0, z1, b) f_{g_1,g_1,a}(z0, z1, a) -> f_{g_1,g_1,b}(z0, z1, b) f_{g_1,b,a}(z0, z1, a) -> f_{g_1,b,b}(z0, z1, b) f_{b,f_3,a}(z0, z1, a) -> f_{b,f_3,b}(z0, z1, b) f_{b,a,a}(z0, z1, a) -> f_{b,a,b}(z0, z1, b) f_{b,g_1,a}(z0, z1, a) -> f_{b,g_1,b}(z0, z1, b) f_{b,b,a}(z0, z1, a) -> f_{b,b,b}(z0, z1, b) g_{a}(a) -> g_{b}(b) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,f_3,b}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{b}(z)) f_{f_3,a,f_3}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{f_3}(z)) f_{f_3,a,a}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{a}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,b}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{b}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) f_{f_3,b,f_3}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{f_3}(z)) f_{f_3,b,a}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{a}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,b}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{b}(z)) f_{a,f_3,f_3}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{f_3}(z)) f_{a,f_3,a}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{a}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,b}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{b}(z)) f_{a,a,f_3}(x, y, z) -> f_{a,a,g_1}(x, y, g_{f_3}(z)) f_{a,a,a}(x, y, z) -> f_{a,a,g_1}(x, y, g_{a}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,a,b}(x, y, z) -> f_{a,a,g_1}(x, y, g_{b}(z)) f_{a,g_1,f_3}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{f_3}(z)) f_{a,g_1,a}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{a}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,b}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{b}(z)) f_{a,b,f_3}(x, y, z) -> f_{a,b,g_1}(x, y, g_{f_3}(z)) f_{a,b,a}(x, y, z) -> f_{a,b,g_1}(x, y, g_{a}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{a,b,b}(x, y, z) -> f_{a,b,g_1}(x, y, g_{b}(z)) f_{g_1,f_3,a}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{a}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,f_3}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{f_3}(z)) f_{g_1,a,a}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{a}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,a,b}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{b}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,f_3}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{f_3}(z)) f_{g_1,b,a}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{a}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,b}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{b}(z)) f_{b,f_3,f_3}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{f_3}(z)) f_{b,f_3,a}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{a}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,b}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{b}(z)) f_{b,a,f_3}(x, y, z) -> f_{b,a,g_1}(x, y, g_{f_3}(z)) f_{b,a,a}(x, y, z) -> f_{b,a,g_1}(x, y, g_{a}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,a,b}(x, y, z) -> f_{b,a,g_1}(x, y, g_{b}(z)) f_{b,g_1,f_3}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{f_3}(z)) f_{b,g_1,a}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{a}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,b}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{b}(z)) f_{b,b,f_3}(x, y, z) -> f_{b,b,g_1}(x, y, g_{f_3}(z)) f_{b,b,a}(x, y, z) -> f_{b,b,g_1}(x, y, g_{a}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) f_{b,b,b}(x, y, z) -> f_{b,b,g_1}(x, y, g_{b}(z)) ---------------------------------------- (13) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 0 POL(f_{a,a,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,a,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,a,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,b,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,b,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,g_1,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,a,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,a,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,b,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,b,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,g_1,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,a,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,a,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,b,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,b,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,b}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,a,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,a,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,a,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,b,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,b,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,a}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(g_{a}(x_1)) = x_1 POL(g_{b}(x_1)) = x_1 POL(g_{f_3}(x_1)) = x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: f_{a,f_3,a}(a, z1, z2) -> f_{b,f_3,a}(b, z1, z2) f_{a,f_3,g_1}(a, z1, z2) -> f_{b,f_3,g_1}(b, z1, z2) f_{a,f_3,b}(a, z1, z2) -> f_{b,f_3,b}(b, z1, z2) f_{a,a,f_3}(a, z1, z2) -> f_{b,a,f_3}(b, z1, z2) f_{a,a,a}(a, z1, z2) -> f_{b,a,a}(b, z1, z2) f_{a,a,g_1}(a, z1, z2) -> f_{b,a,g_1}(b, z1, z2) f_{a,a,b}(a, z1, z2) -> f_{b,a,b}(b, z1, z2) f_{a,g_1,f_3}(a, z1, z2) -> f_{b,g_1,f_3}(b, z1, z2) f_{a,g_1,a}(a, z1, z2) -> f_{b,g_1,a}(b, z1, z2) f_{a,g_1,g_1}(a, z1, z2) -> f_{b,g_1,g_1}(b, z1, z2) f_{a,g_1,b}(a, z1, z2) -> f_{b,g_1,b}(b, z1, z2) f_{a,b,f_3}(a, z1, z2) -> f_{b,b,f_3}(b, z1, z2) f_{a,b,a}(a, z1, z2) -> f_{b,b,a}(b, z1, z2) f_{a,b,g_1}(a, z1, z2) -> f_{b,b,g_1}(b, z1, z2) f_{a,b,b}(a, z1, z2) -> f_{b,b,b}(b, z1, z2) f_{f_3,a,f_3}(z0, a, z2) -> f_{f_3,b,f_3}(z0, b, z2) f_{f_3,a,a}(z0, a, z2) -> f_{f_3,b,a}(z0, b, z2) f_{f_3,a,g_1}(z0, a, z2) -> f_{f_3,b,g_1}(z0, b, z2) f_{f_3,a,b}(z0, a, z2) -> f_{f_3,b,b}(z0, b, z2) f_{a,a,f_3}(z0, a, z2) -> f_{a,b,f_3}(z0, b, z2) f_{a,a,a}(z0, a, z2) -> f_{a,b,a}(z0, b, z2) f_{a,a,g_1}(z0, a, z2) -> f_{a,b,g_1}(z0, b, z2) f_{a,a,b}(z0, a, z2) -> f_{a,b,b}(z0, b, z2) f_{g_1,a,f_3}(z0, a, z2) -> f_{g_1,b,f_3}(z0, b, z2) f_{g_1,a,a}(z0, a, z2) -> f_{g_1,b,a}(z0, b, z2) f_{g_1,a,g_1}(z0, a, z2) -> f_{g_1,b,g_1}(z0, b, z2) f_{g_1,a,b}(z0, a, z2) -> f_{g_1,b,b}(z0, b, z2) f_{b,a,f_3}(z0, a, z2) -> f_{b,b,f_3}(z0, b, z2) f_{b,a,a}(z0, a, z2) -> f_{b,b,a}(z0, b, z2) f_{b,a,g_1}(z0, a, z2) -> f_{b,b,g_1}(z0, b, z2) f_{b,a,b}(z0, a, z2) -> f_{b,b,b}(z0, b, z2) f_{f_3,f_3,a}(z0, z1, a) -> f_{f_3,f_3,b}(z0, z1, b) f_{f_3,a,a}(z0, z1, a) -> f_{f_3,a,b}(z0, z1, b) f_{f_3,g_1,a}(z0, z1, a) -> f_{f_3,g_1,b}(z0, z1, b) f_{f_3,b,a}(z0, z1, a) -> f_{f_3,b,b}(z0, z1, b) f_{a,f_3,a}(z0, z1, a) -> f_{a,f_3,b}(z0, z1, b) f_{a,a,a}(z0, z1, a) -> f_{a,a,b}(z0, z1, b) f_{a,g_1,a}(z0, z1, a) -> f_{a,g_1,b}(z0, z1, b) f_{a,b,a}(z0, z1, a) -> f_{a,b,b}(z0, z1, b) f_{g_1,f_3,a}(z0, z1, a) -> f_{g_1,f_3,b}(z0, z1, b) f_{g_1,a,a}(z0, z1, a) -> f_{g_1,a,b}(z0, z1, b) f_{g_1,g_1,a}(z0, z1, a) -> f_{g_1,g_1,b}(z0, z1, b) f_{g_1,b,a}(z0, z1, a) -> f_{g_1,b,b}(z0, z1, b) f_{b,f_3,a}(z0, z1, a) -> f_{b,f_3,b}(z0, z1, b) f_{b,a,a}(z0, z1, a) -> f_{b,a,b}(z0, z1, b) f_{b,g_1,a}(z0, z1, a) -> f_{b,g_1,b}(z0, z1, b) f_{b,b,a}(z0, z1, a) -> f_{b,b,b}(z0, z1, b) g_{a}(a) -> g_{b}(b) Rules from S: f_{f_3,a,f_3}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{f_3}(z)) f_{f_3,a,a}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{a}(z)) f_{f_3,a,b}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{b}(z)) f_{f_3,b,f_3}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{f_3}(z)) f_{f_3,b,a}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{a}(z)) f_{f_3,b,b}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{b}(z)) f_{a,f_3,a}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{a}(z)) f_{a,f_3,b}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{b}(z)) f_{a,a,f_3}(x, y, z) -> f_{a,a,g_1}(x, y, g_{f_3}(z)) f_{a,a,a}(x, y, z) -> f_{a,a,g_1}(x, y, g_{a}(z)) f_{a,a,b}(x, y, z) -> f_{a,a,g_1}(x, y, g_{b}(z)) f_{a,g_1,f_3}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{f_3}(z)) f_{a,g_1,a}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{a}(z)) f_{a,g_1,b}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{b}(z)) f_{a,b,f_3}(x, y, z) -> f_{a,b,g_1}(x, y, g_{f_3}(z)) f_{a,b,a}(x, y, z) -> f_{a,b,g_1}(x, y, g_{a}(z)) f_{a,b,b}(x, y, z) -> f_{a,b,g_1}(x, y, g_{b}(z)) f_{g_1,a,f_3}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{f_3}(z)) f_{g_1,a,a}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{a}(z)) f_{g_1,a,b}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{b}(z)) f_{g_1,b,f_3}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{f_3}(z)) f_{g_1,b,a}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{a}(z)) f_{g_1,b,b}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{b}(z)) f_{b,f_3,f_3}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{f_3}(z)) f_{b,f_3,a}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{a}(z)) f_{b,f_3,b}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{b}(z)) f_{b,a,f_3}(x, y, z) -> f_{b,a,g_1}(x, y, g_{f_3}(z)) f_{b,a,a}(x, y, z) -> f_{b,a,g_1}(x, y, g_{a}(z)) f_{b,a,b}(x, y, z) -> f_{b,a,g_1}(x, y, g_{b}(z)) f_{b,g_1,f_3}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{f_3}(z)) f_{b,g_1,a}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{a}(z)) f_{b,g_1,b}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{b}(z)) f_{b,b,f_3}(x, y, z) -> f_{b,b,g_1}(x, y, g_{f_3}(z)) f_{b,b,a}(x, y, z) -> f_{b,b,g_1}(x, y, g_{a}(z)) f_{b,b,b}(x, y, z) -> f_{b,b,g_1}(x, y, g_{b}(z)) ---------------------------------------- (14) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,f_3,b}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{b}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,f_3}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{f_3}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,a}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{a}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (15) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(g_{a}(x_1)) = 1 + x_1 POL(g_{b}(x_1)) = 1 + x_1 POL(g_{f_3}(x_1)) = x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: f_{a,f_3,f_3}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{f_3}(z)) ---------------------------------------- (16) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,f_3,b}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{b}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,a}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{a}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (17) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(g_{a}(x_1)) = x_1 POL(g_{b}(x_1)) = x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: f_{g_1,f_3,a}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{a}(z)) ---------------------------------------- (18) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,f_3,b}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{b}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (19) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(g_{a}(x_1)) = x_1 POL(g_{b}(x_1)) = x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: f_{f_3,f_3,b}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{b}(z)) ---------------------------------------- (20) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (21) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(g_{a}(x_1)) = 1 + x_1 POL(g_{b}(x_1)) = x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: f_{f_3,g_1,b}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{b}(z)) ---------------------------------------- (22) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (23) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(g_{a}(x_1)) = 1 + x_1 POL(g_{b}(x_1)) = x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: f_{g_1,g_1,b}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{b}(z)) ---------------------------------------- (24) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (25) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(g_{a}(x_1)) = x_1 POL(g_{b}(x_1)) = 1 + x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: f_{g_1,g_1,a}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{a}(z)) ---------------------------------------- (26) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (27) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,b}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(g_{a}(x_1)) = 1 + x_1 POL(g_{b}(x_1)) = x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: f_{g_1,f_3,b}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{b}(z)) ---------------------------------------- (28) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (29) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(g_{a}(x_1)) = x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: f_{f_3,g_1,a}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{a}(z)) ---------------------------------------- (30) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (31) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,a}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(g_{a}(x_1)) = x_1 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: none Rules from S: f_{f_3,f_3,a}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{a}(z)) ---------------------------------------- (32) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) The relative TRS consists of the following S rules: f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (33) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(a) = 1 POL(b) = 1 POL(f_{a,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,f_3,f_3}(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(f_{a,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{a,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,f_3}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{b,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{f_3,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,a,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,b,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,f_3,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(f_{g_1,g_1,g_1}(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(g_{g_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: f_{a,f_3,f_3}(a, z1, z2) -> f_{b,f_3,f_3}(b, z1, z2) Rules from S: none ---------------------------------------- (34) Obligation: Relative term rewrite system: R is empty. The relative TRS consists of the following S rules: f_{f_3,f_3,g_1}(x, y, z) -> f_{f_3,f_3,g_1}(x, y, g_{g_1}(z)) f_{f_3,a,g_1}(x, y, z) -> f_{f_3,a,g_1}(x, y, g_{g_1}(z)) f_{f_3,g_1,g_1}(x, y, z) -> f_{f_3,g_1,g_1}(x, y, g_{g_1}(z)) f_{f_3,b,g_1}(x, y, z) -> f_{f_3,b,g_1}(x, y, g_{g_1}(z)) f_{a,f_3,g_1}(x, y, z) -> f_{a,f_3,g_1}(x, y, g_{g_1}(z)) f_{a,a,g_1}(x, y, z) -> f_{a,a,g_1}(x, y, g_{g_1}(z)) f_{a,g_1,g_1}(x, y, z) -> f_{a,g_1,g_1}(x, y, g_{g_1}(z)) f_{a,b,g_1}(x, y, z) -> f_{a,b,g_1}(x, y, g_{g_1}(z)) f_{g_1,f_3,g_1}(x, y, z) -> f_{g_1,f_3,g_1}(x, y, g_{g_1}(z)) f_{g_1,a,g_1}(x, y, z) -> f_{g_1,a,g_1}(x, y, g_{g_1}(z)) f_{g_1,g_1,g_1}(x, y, z) -> f_{g_1,g_1,g_1}(x, y, g_{g_1}(z)) f_{g_1,b,g_1}(x, y, z) -> f_{g_1,b,g_1}(x, y, g_{g_1}(z)) f_{b,f_3,g_1}(x, y, z) -> f_{b,f_3,g_1}(x, y, g_{g_1}(z)) f_{b,a,g_1}(x, y, z) -> f_{b,a,g_1}(x, y, g_{g_1}(z)) f_{b,g_1,g_1}(x, y, z) -> f_{b,g_1,g_1}(x, y, g_{g_1}(z)) f_{b,b,g_1}(x, y, z) -> f_{b,b,g_1}(x, y, g_{g_1}(z)) ---------------------------------------- (35) RIsEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (36) YES