/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/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, 16 ms] (4) RelTRS (5) RelTRSRRRProof [EQUIVALENT, 138 ms] (6) RelTRS (7) RelTRSRRRProof [EQUIVALENT, 68 ms] (8) RelTRS (9) RelTRSRRRProof [EQUIVALENT, 70 ms] (10) RelTRS (11) RelTRSRRRProof [EQUIVALENT, 0 ms] (12) RelTRS (13) RelTRSRRRProof [EQUIVALENT, 19 ms] (14) RelTRS (15) RelTRSRRRProof [EQUIVALENT, 24 ms] (16) RelTRS (17) RelTRSRRRProof [EQUIVALENT, 13 ms] (18) RelTRS (19) RIsEmptyProof [EQUIVALENT, 0 ms] (20) YES ---------------------------------------- (0) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: b(p(b(x1))) -> b(q(b(x1))) The relative TRS consists of the following S rules: 1(p(0(1(0(x1))))) -> p(x1) q(x1) -> 0(q(0(x1))) q(x1) -> 1(q(1(x1))) q(x1) -> 0(p(0(x1))) q(x1) -> 1(p(1(x1))) ---------------------------------------- (1) FlatCCProof (EQUIVALENT) We used flat context closure [ROOTLAB] ---------------------------------------- (2) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: b(p(b(x1))) -> b(q(b(x1))) The relative TRS consists of the following S rules: b(1(p(0(1(0(x1)))))) -> b(p(x1)) p(1(p(0(1(0(x1)))))) -> p(p(x1)) q(1(p(0(1(0(x1)))))) -> q(p(x1)) 1(1(p(0(1(0(x1)))))) -> 1(p(x1)) 0(1(p(0(1(0(x1)))))) -> 0(p(x1)) b(q(x1)) -> b(0(q(0(x1)))) p(q(x1)) -> p(0(q(0(x1)))) q(q(x1)) -> q(0(q(0(x1)))) 1(q(x1)) -> 1(0(q(0(x1)))) 0(q(x1)) -> 0(0(q(0(x1)))) b(q(x1)) -> b(1(q(1(x1)))) p(q(x1)) -> p(1(q(1(x1)))) q(q(x1)) -> q(1(q(1(x1)))) 1(q(x1)) -> 1(1(q(1(x1)))) 0(q(x1)) -> 0(1(q(1(x1)))) b(q(x1)) -> b(0(p(0(x1)))) p(q(x1)) -> p(0(p(0(x1)))) q(q(x1)) -> q(0(p(0(x1)))) 1(q(x1)) -> 1(0(p(0(x1)))) 0(q(x1)) -> 0(0(p(0(x1)))) b(q(x1)) -> b(1(p(1(x1)))) p(q(x1)) -> p(1(p(1(x1)))) q(q(x1)) -> q(1(p(1(x1)))) 1(q(x1)) -> 1(1(p(1(x1)))) 0(q(x1)) -> 0(1(p(1(x1)))) ---------------------------------------- (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: b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) The relative TRS consists of the following S rules: b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> b_{p_1}(p_{b_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> b_{p_1}(p_{p_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> b_{p_1}(p_{q_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> b_{p_1}(p_{1_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> b_{p_1}(p_{0_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> p_{p_1}(p_{b_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> p_{p_1}(p_{p_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> p_{p_1}(p_{q_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> p_{p_1}(p_{1_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> p_{p_1}(p_{0_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> q_{p_1}(p_{b_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> q_{p_1}(p_{p_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> q_{p_1}(p_{q_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> q_{p_1}(p_{1_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> q_{p_1}(p_{0_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 1_{p_1}(p_{b_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> 1_{p_1}(p_{p_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 1_{p_1}(p_{q_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> 1_{p_1}(p_{1_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 1_{p_1}(p_{0_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 0_{p_1}(p_{b_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> 0_{p_1}(p_{p_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 0_{p_1}(p_{q_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> 0_{p_1}(p_{1_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 0_{p_1}(p_{0_1}(x1)) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) b_{q_1}(q_{q_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{q_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) q_{q_1}(q_{b_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) q_{q_1}(q_{p_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) q_{q_1}(q_{q_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) q_{q_1}(q_{1_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) q_{q_1}(q_{0_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{q_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{q_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{q_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) p_{q_1}(q_{q_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) q_{q_1}(q_{b_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) q_{q_1}(q_{p_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) q_{q_1}(q_{q_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) q_{q_1}(q_{1_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) q_{q_1}(q_{0_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{q_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{q_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) b_{q_1}(q_{q_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{q_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) q_{q_1}(q_{b_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) q_{q_1}(q_{p_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) q_{q_1}(q_{q_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) q_{q_1}(q_{1_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) q_{q_1}(q_{0_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{q_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{q_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{q_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) p_{q_1}(q_{q_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) q_{q_1}(q_{b_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) q_{q_1}(q_{p_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) q_{q_1}(q_{q_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) q_{q_1}(q_{1_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) q_{q_1}(q_{0_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{q_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{q_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) ---------------------------------------- (5) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(0_{0_1}(x_1)) = x_1 POL(0_{1_1}(x_1)) = x_1 POL(0_{b_1}(x_1)) = x_1 POL(0_{p_1}(x_1)) = x_1 POL(0_{q_1}(x_1)) = x_1 POL(1_{0_1}(x_1)) = x_1 POL(1_{1_1}(x_1)) = x_1 POL(1_{b_1}(x_1)) = x_1 POL(1_{p_1}(x_1)) = x_1 POL(1_{q_1}(x_1)) = x_1 POL(b_{0_1}(x_1)) = x_1 POL(b_{1_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = x_1 POL(b_{p_1}(x_1)) = x_1 POL(b_{q_1}(x_1)) = x_1 POL(p_{0_1}(x_1)) = x_1 POL(p_{1_1}(x_1)) = x_1 POL(p_{b_1}(x_1)) = x_1 POL(p_{p_1}(x_1)) = x_1 POL(p_{q_1}(x_1)) = x_1 POL(q_{0_1}(x_1)) = x_1 POL(q_{1_1}(x_1)) = x_1 POL(q_{b_1}(x_1)) = x_1 POL(q_{p_1}(x_1)) = x_1 POL(q_{q_1}(x_1)) = 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: b_{q_1}(q_{q_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) p_{q_1}(q_{q_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) q_{q_1}(q_{b_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) q_{q_1}(q_{p_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) q_{q_1}(q_{q_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) q_{q_1}(q_{1_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) q_{q_1}(q_{0_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{q_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 0_{q_1}(q_{q_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) b_{q_1}(q_{q_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) p_{q_1}(q_{q_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) q_{q_1}(q_{b_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) q_{q_1}(q_{p_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) q_{q_1}(q_{q_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) q_{q_1}(q_{1_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) q_{q_1}(q_{0_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{q_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 0_{q_1}(q_{q_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) b_{q_1}(q_{q_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) p_{q_1}(q_{q_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) q_{q_1}(q_{b_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) q_{q_1}(q_{p_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) q_{q_1}(q_{q_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) q_{q_1}(q_{1_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) q_{q_1}(q_{0_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{q_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 0_{q_1}(q_{q_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) b_{q_1}(q_{q_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) p_{q_1}(q_{q_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) q_{q_1}(q_{b_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) q_{q_1}(q_{p_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) q_{q_1}(q_{q_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) q_{q_1}(q_{1_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) q_{q_1}(q_{0_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{q_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 0_{q_1}(q_{q_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) ---------------------------------------- (6) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) The relative TRS consists of the following S rules: b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> b_{p_1}(p_{b_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> b_{p_1}(p_{p_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> b_{p_1}(p_{q_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> b_{p_1}(p_{1_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> b_{p_1}(p_{0_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> p_{p_1}(p_{b_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> p_{p_1}(p_{p_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> p_{p_1}(p_{q_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> p_{p_1}(p_{1_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> p_{p_1}(p_{0_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> q_{p_1}(p_{b_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> q_{p_1}(p_{p_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> q_{p_1}(p_{q_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> q_{p_1}(p_{1_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> q_{p_1}(p_{0_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 1_{p_1}(p_{b_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> 1_{p_1}(p_{p_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 1_{p_1}(p_{q_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> 1_{p_1}(p_{1_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 1_{p_1}(p_{0_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 0_{p_1}(p_{b_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> 0_{p_1}(p_{p_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 0_{p_1}(p_{q_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> 0_{p_1}(p_{1_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 0_{p_1}(p_{0_1}(x1)) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) ---------------------------------------- (7) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(0_{0_1}(x_1)) = x_1 POL(0_{1_1}(x_1)) = x_1 POL(0_{b_1}(x_1)) = 1 + x_1 POL(0_{p_1}(x_1)) = x_1 POL(0_{q_1}(x_1)) = x_1 POL(1_{0_1}(x_1)) = x_1 POL(1_{1_1}(x_1)) = x_1 POL(1_{b_1}(x_1)) = x_1 POL(1_{p_1}(x_1)) = x_1 POL(1_{q_1}(x_1)) = x_1 POL(b_{0_1}(x_1)) = x_1 POL(b_{1_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = x_1 POL(b_{p_1}(x_1)) = x_1 POL(b_{q_1}(x_1)) = x_1 POL(p_{0_1}(x_1)) = x_1 POL(p_{1_1}(x_1)) = x_1 POL(p_{b_1}(x_1)) = 1 + x_1 POL(p_{p_1}(x_1)) = x_1 POL(p_{q_1}(x_1)) = x_1 POL(q_{0_1}(x_1)) = x_1 POL(q_{1_1}(x_1)) = x_1 POL(q_{b_1}(x_1)) = 1 + x_1 POL(q_{p_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: b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) ---------------------------------------- (8) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) The relative TRS consists of the following S rules: b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> b_{p_1}(p_{b_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> b_{p_1}(p_{p_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> b_{p_1}(p_{q_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> b_{p_1}(p_{1_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> b_{p_1}(p_{0_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> p_{p_1}(p_{b_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> p_{p_1}(p_{p_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> p_{p_1}(p_{q_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> p_{p_1}(p_{1_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> p_{p_1}(p_{0_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> q_{p_1}(p_{b_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> q_{p_1}(p_{p_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> q_{p_1}(p_{q_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> q_{p_1}(p_{1_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> q_{p_1}(p_{0_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 1_{p_1}(p_{b_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> 1_{p_1}(p_{p_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 1_{p_1}(p_{q_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> 1_{p_1}(p_{1_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 1_{p_1}(p_{0_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 0_{p_1}(p_{b_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> 0_{p_1}(p_{p_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 0_{p_1}(p_{q_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> 0_{p_1}(p_{1_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 0_{p_1}(p_{0_1}(x1)) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) ---------------------------------------- (9) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(0_{0_1}(x_1)) = x_1 POL(0_{1_1}(x_1)) = x_1 POL(0_{b_1}(x_1)) = x_1 POL(0_{p_1}(x_1)) = x_1 POL(0_{q_1}(x_1)) = x_1 POL(1_{0_1}(x_1)) = x_1 POL(1_{1_1}(x_1)) = x_1 POL(1_{p_1}(x_1)) = x_1 POL(1_{q_1}(x_1)) = x_1 POL(b_{0_1}(x_1)) = x_1 POL(b_{1_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = x_1 POL(b_{p_1}(x_1)) = x_1 POL(b_{q_1}(x_1)) = x_1 POL(p_{0_1}(x_1)) = 1 + x_1 POL(p_{1_1}(x_1)) = x_1 POL(p_{b_1}(x_1)) = 1 + x_1 POL(p_{p_1}(x_1)) = x_1 POL(p_{q_1}(x_1)) = 1 + x_1 POL(q_{0_1}(x_1)) = 1 + x_1 POL(q_{1_1}(x_1)) = 1 + x_1 POL(q_{b_1}(x_1)) = 1 + x_1 POL(q_{p_1}(x_1)) = 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: b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> b_{p_1}(p_{p_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> b_{p_1}(p_{1_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> p_{p_1}(p_{p_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> p_{p_1}(p_{1_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> q_{p_1}(p_{p_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> q_{p_1}(p_{1_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> 1_{p_1}(p_{p_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> 1_{p_1}(p_{1_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{p_1}(x1)))))) -> 0_{p_1}(p_{p_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{1_1}(x1)))))) -> 0_{p_1}(p_{1_1}(x1)) p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) ---------------------------------------- (10) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) The relative TRS consists of the following S rules: b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> b_{p_1}(p_{b_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> b_{p_1}(p_{q_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> b_{p_1}(p_{0_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> p_{p_1}(p_{b_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> p_{p_1}(p_{q_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> p_{p_1}(p_{0_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> q_{p_1}(p_{b_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> q_{p_1}(p_{q_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> q_{p_1}(p_{0_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 1_{p_1}(p_{b_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 1_{p_1}(p_{q_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 1_{p_1}(p_{0_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 0_{p_1}(p_{b_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 0_{p_1}(p_{q_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 0_{p_1}(p_{0_1}(x1)) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) ---------------------------------------- (11) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(0_{0_1}(x_1)) = x_1 POL(0_{1_1}(x_1)) = x_1 POL(0_{b_1}(x_1)) = x_1 POL(0_{p_1}(x_1)) = x_1 POL(0_{q_1}(x_1)) = x_1 POL(1_{0_1}(x_1)) = x_1 POL(1_{1_1}(x_1)) = x_1 POL(1_{p_1}(x_1)) = 1 + x_1 POL(1_{q_1}(x_1)) = x_1 POL(b_{0_1}(x_1)) = x_1 POL(b_{1_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = x_1 POL(b_{p_1}(x_1)) = x_1 POL(b_{q_1}(x_1)) = x_1 POL(p_{0_1}(x_1)) = x_1 POL(p_{1_1}(x_1)) = 1 + x_1 POL(p_{b_1}(x_1)) = x_1 POL(p_{p_1}(x_1)) = 1 + x_1 POL(p_{q_1}(x_1)) = x_1 POL(q_{0_1}(x_1)) = x_1 POL(q_{1_1}(x_1)) = x_1 POL(q_{b_1}(x_1)) = x_1 POL(q_{p_1}(x_1)) = 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: b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> b_{p_1}(p_{b_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> b_{p_1}(p_{q_1}(x1)) b_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> b_{p_1}(p_{0_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> p_{p_1}(p_{b_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> p_{p_1}(p_{q_1}(x1)) p_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> p_{p_1}(p_{0_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 0_{p_1}(p_{b_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 0_{p_1}(p_{q_1}(x1)) 0_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 0_{p_1}(p_{0_1}(x1)) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) ---------------------------------------- (12) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) The relative TRS consists of the following S rules: q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> q_{p_1}(p_{b_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> q_{p_1}(p_{q_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> q_{p_1}(p_{0_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 1_{p_1}(p_{b_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 1_{p_1}(p_{q_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 1_{p_1}(p_{0_1}(x1)) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) ---------------------------------------- (13) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(0_{0_1}(x_1)) = x_1 POL(0_{1_1}(x_1)) = x_1 POL(0_{b_1}(x_1)) = x_1 POL(0_{p_1}(x_1)) = x_1 POL(0_{q_1}(x_1)) = 1 + x_1 POL(1_{0_1}(x_1)) = x_1 POL(1_{1_1}(x_1)) = x_1 POL(1_{p_1}(x_1)) = x_1 POL(1_{q_1}(x_1)) = 1 + x_1 POL(b_{0_1}(x_1)) = x_1 POL(b_{1_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = x_1 POL(b_{p_1}(x_1)) = 1 + x_1 POL(b_{q_1}(x_1)) = 1 + x_1 POL(p_{0_1}(x_1)) = x_1 POL(p_{b_1}(x_1)) = x_1 POL(p_{q_1}(x_1)) = 1 + x_1 POL(q_{0_1}(x_1)) = x_1 POL(q_{1_1}(x_1)) = x_1 POL(q_{b_1}(x_1)) = x_1 POL(q_{p_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: b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) ---------------------------------------- (14) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) The relative TRS consists of the following S rules: q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> q_{p_1}(p_{b_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> q_{p_1}(p_{q_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> q_{p_1}(p_{0_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 1_{p_1}(p_{b_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 1_{p_1}(p_{q_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 1_{p_1}(p_{0_1}(x1)) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) ---------------------------------------- (15) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(0_{0_1}(x_1)) = x_1 POL(0_{1_1}(x_1)) = x_1 POL(0_{b_1}(x_1)) = 1 + x_1 POL(0_{q_1}(x_1)) = x_1 POL(1_{0_1}(x_1)) = x_1 POL(1_{1_1}(x_1)) = x_1 POL(1_{p_1}(x_1)) = x_1 POL(1_{q_1}(x_1)) = x_1 POL(b_{0_1}(x_1)) = x_1 POL(b_{1_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = x_1 POL(b_{p_1}(x_1)) = 1 + x_1 POL(b_{q_1}(x_1)) = x_1 POL(p_{0_1}(x_1)) = x_1 POL(p_{b_1}(x_1)) = x_1 POL(p_{q_1}(x_1)) = x_1 POL(q_{0_1}(x_1)) = x_1 POL(q_{1_1}(x_1)) = x_1 POL(q_{b_1}(x_1)) = 1 + x_1 POL(q_{p_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: q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> q_{p_1}(p_{b_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{b_1}(x1)))))) -> 1_{p_1}(p_{b_1}(x1)) ---------------------------------------- (16) Obligation: Relative term rewrite system: The relative TRS consists of the following R rules: b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) The relative TRS consists of the following S rules: q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> q_{p_1}(p_{q_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> q_{p_1}(p_{0_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 1_{p_1}(p_{q_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 1_{p_1}(p_{0_1}(x1)) b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) ---------------------------------------- (17) RelTRSRRRProof (EQUIVALENT) We used the following monotonic ordering for rule removal: Polynomial interpretation [POLO]: POL(0_{0_1}(x_1)) = x_1 POL(0_{1_1}(x_1)) = x_1 POL(0_{b_1}(x_1)) = x_1 POL(0_{q_1}(x_1)) = x_1 POL(1_{0_1}(x_1)) = x_1 POL(1_{1_1}(x_1)) = x_1 POL(1_{p_1}(x_1)) = x_1 POL(1_{q_1}(x_1)) = x_1 POL(b_{0_1}(x_1)) = x_1 POL(b_{1_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = x_1 POL(b_{p_1}(x_1)) = 1 + x_1 POL(b_{q_1}(x_1)) = 1 + x_1 POL(p_{0_1}(x_1)) = x_1 POL(p_{b_1}(x_1)) = 1 + x_1 POL(p_{q_1}(x_1)) = x_1 POL(q_{0_1}(x_1)) = x_1 POL(q_{1_1}(x_1)) = x_1 POL(q_{b_1}(x_1)) = x_1 POL(q_{p_1}(x_1)) = x_1 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: Rules from R: b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) Rules from S: b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) ---------------------------------------- (18) Obligation: Relative term rewrite system: R is empty. The relative TRS consists of the following S rules: q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> q_{p_1}(p_{q_1}(x1)) q_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> q_{p_1}(p_{0_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{q_1}(x1)))))) -> 1_{p_1}(p_{q_1}(x1)) 1_{1_1}(1_{p_1}(p_{0_1}(0_{1_1}(1_{0_1}(0_{0_1}(x1)))))) -> 1_{p_1}(p_{0_1}(x1)) p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) ---------------------------------------- (19) RIsEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (20) YES