35.71/9.88 YES 35.71/9.93 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 35.71/9.93 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 35.71/9.93 35.71/9.93 35.71/9.93 Termination of the given RelTRS could be proven: 35.71/9.93 35.71/9.93 (0) RelTRS 35.71/9.93 (1) FlatCCProof [EQUIVALENT, 0 ms] 35.71/9.93 (2) RelTRS 35.71/9.93 (3) RootLabelingProof [EQUIVALENT, 6 ms] 35.71/9.93 (4) RelTRS 35.71/9.93 (5) RelTRSRRRProof [EQUIVALENT, 169 ms] 35.71/9.93 (6) RelTRS 35.71/9.93 (7) RelTRSRRRProof [EQUIVALENT, 89 ms] 35.71/9.93 (8) RelTRS 35.71/9.93 (9) RelTRSRRRProof [EQUIVALENT, 60 ms] 35.71/9.93 (10) RelTRS 35.71/9.93 (11) RelTRSRRRProof [EQUIVALENT, 0 ms] 35.71/9.93 (12) RelTRS 35.71/9.93 (13) RelTRSRRRProof [EQUIVALENT, 0 ms] 35.71/9.93 (14) RelTRS 35.71/9.93 (15) RelTRSRRRProof [EQUIVALENT, 0 ms] 35.71/9.93 (16) RelTRS 35.71/9.93 (17) RelTRSRRRProof [EQUIVALENT, 14 ms] 35.71/9.93 (18) RelTRS 35.71/9.93 (19) RIsEmptyProof [EQUIVALENT, 0 ms] 35.71/9.93 (20) YES 35.71/9.93 35.71/9.93 35.71/9.93 ---------------------------------------- 35.71/9.93 35.71/9.93 (0) 35.71/9.93 Obligation: 35.71/9.93 Relative term rewrite system: 35.71/9.93 The relative TRS consists of the following R rules: 35.71/9.93 35.71/9.93 b(p(b(x1))) -> b(q(b(x1))) 35.71/9.93 35.71/9.93 The relative TRS consists of the following S rules: 35.71/9.93 35.71/9.93 1(p(0(1(0(x1))))) -> p(x1) 35.71/9.93 q(x1) -> 0(q(0(x1))) 35.71/9.93 q(x1) -> 1(q(1(x1))) 35.71/9.93 q(x1) -> 0(p(0(x1))) 35.71/9.93 q(x1) -> 1(p(1(x1))) 35.71/9.93 35.71/9.93 35.71/9.93 ---------------------------------------- 35.71/9.93 35.71/9.93 (1) FlatCCProof (EQUIVALENT) 35.71/9.93 We used flat context closure [ROOTLAB] 35.71/9.93 35.71/9.93 ---------------------------------------- 35.71/9.93 35.71/9.93 (2) 35.71/9.93 Obligation: 35.71/9.93 Relative term rewrite system: 35.71/9.93 The relative TRS consists of the following R rules: 35.71/9.93 35.71/9.93 b(p(b(x1))) -> b(q(b(x1))) 35.71/9.93 35.71/9.93 The relative TRS consists of the following S rules: 35.71/9.93 35.71/9.93 b(1(p(0(1(0(x1)))))) -> b(p(x1)) 35.71/9.93 p(1(p(0(1(0(x1)))))) -> p(p(x1)) 35.71/9.93 q(1(p(0(1(0(x1)))))) -> q(p(x1)) 35.71/9.93 1(1(p(0(1(0(x1)))))) -> 1(p(x1)) 35.71/9.93 0(1(p(0(1(0(x1)))))) -> 0(p(x1)) 35.71/9.93 b(q(x1)) -> b(0(q(0(x1)))) 35.71/9.93 p(q(x1)) -> p(0(q(0(x1)))) 35.71/9.93 q(q(x1)) -> q(0(q(0(x1)))) 35.71/9.93 1(q(x1)) -> 1(0(q(0(x1)))) 35.71/9.93 0(q(x1)) -> 0(0(q(0(x1)))) 35.71/9.93 b(q(x1)) -> b(1(q(1(x1)))) 35.71/9.93 p(q(x1)) -> p(1(q(1(x1)))) 35.71/9.93 q(q(x1)) -> q(1(q(1(x1)))) 35.71/9.93 1(q(x1)) -> 1(1(q(1(x1)))) 35.71/9.93 0(q(x1)) -> 0(1(q(1(x1)))) 35.71/9.93 b(q(x1)) -> b(0(p(0(x1)))) 35.71/9.93 p(q(x1)) -> p(0(p(0(x1)))) 35.71/9.93 q(q(x1)) -> q(0(p(0(x1)))) 35.71/9.93 1(q(x1)) -> 1(0(p(0(x1)))) 35.71/9.93 0(q(x1)) -> 0(0(p(0(x1)))) 35.71/9.93 b(q(x1)) -> b(1(p(1(x1)))) 35.71/9.93 p(q(x1)) -> p(1(p(1(x1)))) 35.71/9.93 q(q(x1)) -> q(1(p(1(x1)))) 35.71/9.93 1(q(x1)) -> 1(1(p(1(x1)))) 35.71/9.93 0(q(x1)) -> 0(1(p(1(x1)))) 35.71/9.93 35.71/9.93 35.71/9.93 ---------------------------------------- 35.71/9.93 35.71/9.93 (3) RootLabelingProof (EQUIVALENT) 35.71/9.93 We used plain root labeling [ROOTLAB] with the following heuristic: 35.71/9.93 LabelAll: All function symbols get labeled 35.71/9.93 35.71/9.93 35.71/9.93 ---------------------------------------- 35.71/9.93 35.71/9.93 (4) 35.71/9.93 Obligation: 35.71/9.93 Relative term rewrite system: 35.71/9.93 The relative TRS consists of the following R rules: 35.71/9.93 35.71/9.93 b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) 35.71/9.93 35.71/9.93 The relative TRS consists of the following S rules: 35.71/9.93 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{q_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{q_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 q_{q_1}(q_{b_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 q_{q_1}(q_{p_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 q_{q_1}(q_{q_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{1_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 q_{q_1}(q_{0_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{q_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{q_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{q_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{q_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 q_{q_1}(q_{b_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 q_{q_1}(q_{p_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 q_{q_1}(q_{q_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{1_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 q_{q_1}(q_{0_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{q_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{q_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{q_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{q_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 q_{q_1}(q_{b_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 q_{q_1}(q_{p_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 q_{q_1}(q_{q_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{1_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 q_{q_1}(q_{0_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{q_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{q_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{q_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{q_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 q_{q_1}(q_{b_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 q_{q_1}(q_{p_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 q_{q_1}(q_{q_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{1_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 q_{q_1}(q_{0_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{q_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{q_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 35.71/9.93 35.71/9.93 ---------------------------------------- 35.71/9.93 35.71/9.93 (5) RelTRSRRRProof (EQUIVALENT) 35.71/9.93 We used the following monotonic ordering for rule removal: 35.71/9.93 Polynomial interpretation [POLO]: 35.71/9.93 35.71/9.93 POL(0_{0_1}(x_1)) = x_1 35.71/9.93 POL(0_{1_1}(x_1)) = x_1 35.71/9.93 POL(0_{b_1}(x_1)) = x_1 35.71/9.93 POL(0_{p_1}(x_1)) = x_1 35.71/9.93 POL(0_{q_1}(x_1)) = x_1 35.71/9.93 POL(1_{0_1}(x_1)) = x_1 35.71/9.93 POL(1_{1_1}(x_1)) = x_1 35.71/9.93 POL(1_{b_1}(x_1)) = x_1 35.71/9.93 POL(1_{p_1}(x_1)) = x_1 35.71/9.93 POL(1_{q_1}(x_1)) = x_1 35.71/9.93 POL(b_{0_1}(x_1)) = x_1 35.71/9.93 POL(b_{1_1}(x_1)) = x_1 35.71/9.93 POL(b_{b_1}(x_1)) = x_1 35.71/9.93 POL(b_{p_1}(x_1)) = x_1 35.71/9.93 POL(b_{q_1}(x_1)) = x_1 35.71/9.93 POL(p_{0_1}(x_1)) = x_1 35.71/9.93 POL(p_{1_1}(x_1)) = x_1 35.71/9.93 POL(p_{b_1}(x_1)) = x_1 35.71/9.93 POL(p_{p_1}(x_1)) = x_1 35.71/9.93 POL(p_{q_1}(x_1)) = x_1 35.71/9.93 POL(q_{0_1}(x_1)) = x_1 35.71/9.93 POL(q_{1_1}(x_1)) = x_1 35.71/9.93 POL(q_{b_1}(x_1)) = x_1 35.71/9.93 POL(q_{p_1}(x_1)) = x_1 35.71/9.93 POL(q_{q_1}(x_1)) = 1 + x_1 35.71/9.93 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 35.71/9.93 Rules from R: 35.71/9.93 none 35.71/9.93 Rules from S: 35.71/9.93 35.71/9.93 b_{q_1}(q_{q_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 p_{q_1}(q_{q_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{b_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 q_{q_1}(q_{p_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 q_{q_1}(q_{q_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{1_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 q_{q_1}(q_{0_1}(x1)) -> q_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{q_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 0_{q_1}(q_{q_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{q_1}(x1)))) 35.71/9.93 b_{q_1}(q_{q_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 p_{q_1}(q_{q_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{b_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 q_{q_1}(q_{p_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 q_{q_1}(q_{q_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{1_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 q_{q_1}(q_{0_1}(x1)) -> q_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{q_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 0_{q_1}(q_{q_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{q_1}(x1)))) 35.71/9.93 b_{q_1}(q_{q_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 p_{q_1}(q_{q_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{b_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 q_{q_1}(q_{p_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 q_{q_1}(q_{q_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{1_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 q_{q_1}(q_{0_1}(x1)) -> q_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{q_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 0_{q_1}(q_{q_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{q_1}(x1)))) 35.71/9.93 b_{q_1}(q_{q_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 p_{q_1}(q_{q_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{b_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 q_{q_1}(q_{p_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 q_{q_1}(q_{q_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 q_{q_1}(q_{1_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 q_{q_1}(q_{0_1}(x1)) -> q_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{q_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 0_{q_1}(q_{q_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{q_1}(x1)))) 35.71/9.93 35.71/9.93 35.71/9.93 35.71/9.93 35.71/9.93 ---------------------------------------- 35.71/9.93 35.71/9.93 (6) 35.71/9.93 Obligation: 35.71/9.93 Relative term rewrite system: 35.71/9.93 The relative TRS consists of the following R rules: 35.71/9.93 35.71/9.93 b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) 35.71/9.93 35.71/9.93 The relative TRS consists of the following S rules: 35.71/9.93 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.93 35.71/9.93 35.71/9.93 ---------------------------------------- 35.71/9.93 35.71/9.93 (7) RelTRSRRRProof (EQUIVALENT) 35.71/9.93 We used the following monotonic ordering for rule removal: 35.71/9.93 Polynomial interpretation [POLO]: 35.71/9.93 35.71/9.93 POL(0_{0_1}(x_1)) = x_1 35.71/9.93 POL(0_{1_1}(x_1)) = x_1 35.71/9.93 POL(0_{b_1}(x_1)) = 1 + x_1 35.71/9.93 POL(0_{p_1}(x_1)) = x_1 35.71/9.93 POL(0_{q_1}(x_1)) = x_1 35.71/9.93 POL(1_{0_1}(x_1)) = x_1 35.71/9.93 POL(1_{1_1}(x_1)) = x_1 35.71/9.93 POL(1_{b_1}(x_1)) = x_1 35.71/9.93 POL(1_{p_1}(x_1)) = x_1 35.71/9.93 POL(1_{q_1}(x_1)) = x_1 35.71/9.93 POL(b_{0_1}(x_1)) = x_1 35.71/9.93 POL(b_{1_1}(x_1)) = x_1 35.71/9.93 POL(b_{b_1}(x_1)) = x_1 35.71/9.93 POL(b_{p_1}(x_1)) = x_1 35.71/9.93 POL(b_{q_1}(x_1)) = x_1 35.71/9.93 POL(p_{0_1}(x_1)) = x_1 35.71/9.93 POL(p_{1_1}(x_1)) = x_1 35.71/9.93 POL(p_{b_1}(x_1)) = 1 + x_1 35.71/9.93 POL(p_{p_1}(x_1)) = x_1 35.71/9.93 POL(p_{q_1}(x_1)) = x_1 35.71/9.93 POL(q_{0_1}(x_1)) = x_1 35.71/9.93 POL(q_{1_1}(x_1)) = x_1 35.71/9.93 POL(q_{b_1}(x_1)) = 1 + x_1 35.71/9.93 POL(q_{p_1}(x_1)) = x_1 35.71/9.93 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 35.71/9.93 Rules from R: 35.71/9.93 none 35.71/9.93 Rules from S: 35.71/9.93 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{b_1}(x1)))) 35.71/9.93 35.71/9.93 35.71/9.93 35.71/9.93 35.71/9.93 ---------------------------------------- 35.71/9.93 35.71/9.93 (8) 35.71/9.93 Obligation: 35.71/9.93 Relative term rewrite system: 35.71/9.93 The relative TRS consists of the following R rules: 35.71/9.93 35.71/9.93 b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) 35.71/9.93 b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) 35.71/9.93 35.71/9.93 The relative TRS consists of the following S rules: 35.71/9.93 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 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)) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.93 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.93 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.93 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.93 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.93 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.93 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.93 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.94 p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (9) RelTRSRRRProof (EQUIVALENT) 35.71/9.94 We used the following monotonic ordering for rule removal: 35.71/9.94 Polynomial interpretation [POLO]: 35.71/9.94 35.71/9.94 POL(0_{0_1}(x_1)) = x_1 35.71/9.94 POL(0_{1_1}(x_1)) = x_1 35.71/9.94 POL(0_{b_1}(x_1)) = x_1 35.71/9.94 POL(0_{p_1}(x_1)) = x_1 35.71/9.94 POL(0_{q_1}(x_1)) = x_1 35.71/9.94 POL(1_{0_1}(x_1)) = x_1 35.71/9.94 POL(1_{1_1}(x_1)) = x_1 35.71/9.94 POL(1_{p_1}(x_1)) = x_1 35.71/9.94 POL(1_{q_1}(x_1)) = x_1 35.71/9.94 POL(b_{0_1}(x_1)) = x_1 35.71/9.94 POL(b_{1_1}(x_1)) = x_1 35.71/9.94 POL(b_{b_1}(x_1)) = x_1 35.71/9.94 POL(b_{p_1}(x_1)) = x_1 35.71/9.94 POL(b_{q_1}(x_1)) = x_1 35.71/9.94 POL(p_{0_1}(x_1)) = 1 + x_1 35.71/9.94 POL(p_{1_1}(x_1)) = x_1 35.71/9.94 POL(p_{b_1}(x_1)) = 1 + x_1 35.71/9.94 POL(p_{p_1}(x_1)) = x_1 35.71/9.94 POL(p_{q_1}(x_1)) = 1 + x_1 35.71/9.94 POL(q_{0_1}(x_1)) = 1 + x_1 35.71/9.94 POL(q_{1_1}(x_1)) = 1 + x_1 35.71/9.94 POL(q_{b_1}(x_1)) = 1 + x_1 35.71/9.94 POL(q_{p_1}(x_1)) = 1 + x_1 35.71/9.94 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 35.71/9.94 Rules from R: 35.71/9.94 none 35.71/9.94 Rules from S: 35.71/9.94 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.94 p_{q_1}(q_{p_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{p_1}(p_{1_1}(1_{0_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (10) 35.71/9.94 Obligation: 35.71/9.94 Relative term rewrite system: 35.71/9.94 The relative TRS consists of the following R rules: 35.71/9.94 35.71/9.94 b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) 35.71/9.94 35.71/9.94 The relative TRS consists of the following S rules: 35.71/9.94 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (11) RelTRSRRRProof (EQUIVALENT) 35.71/9.94 We used the following monotonic ordering for rule removal: 35.71/9.94 Polynomial interpretation [POLO]: 35.71/9.94 35.71/9.94 POL(0_{0_1}(x_1)) = x_1 35.71/9.94 POL(0_{1_1}(x_1)) = x_1 35.71/9.94 POL(0_{b_1}(x_1)) = x_1 35.71/9.94 POL(0_{p_1}(x_1)) = x_1 35.71/9.94 POL(0_{q_1}(x_1)) = x_1 35.71/9.94 POL(1_{0_1}(x_1)) = x_1 35.71/9.94 POL(1_{1_1}(x_1)) = x_1 35.71/9.94 POL(1_{p_1}(x_1)) = 1 + x_1 35.71/9.94 POL(1_{q_1}(x_1)) = x_1 35.71/9.94 POL(b_{0_1}(x_1)) = x_1 35.71/9.94 POL(b_{1_1}(x_1)) = x_1 35.71/9.94 POL(b_{b_1}(x_1)) = x_1 35.71/9.94 POL(b_{p_1}(x_1)) = x_1 35.71/9.94 POL(b_{q_1}(x_1)) = x_1 35.71/9.94 POL(p_{0_1}(x_1)) = x_1 35.71/9.94 POL(p_{1_1}(x_1)) = 1 + x_1 35.71/9.94 POL(p_{b_1}(x_1)) = x_1 35.71/9.94 POL(p_{p_1}(x_1)) = 1 + x_1 35.71/9.94 POL(p_{q_1}(x_1)) = x_1 35.71/9.94 POL(q_{0_1}(x_1)) = x_1 35.71/9.94 POL(q_{1_1}(x_1)) = x_1 35.71/9.94 POL(q_{b_1}(x_1)) = x_1 35.71/9.94 POL(q_{p_1}(x_1)) = 1 + x_1 35.71/9.94 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 35.71/9.94 Rules from R: 35.71/9.94 none 35.71/9.94 Rules from S: 35.71/9.94 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.94 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.94 p_{q_1}(q_{p_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{p_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (12) 35.71/9.94 Obligation: 35.71/9.94 Relative term rewrite system: 35.71/9.94 The relative TRS consists of the following R rules: 35.71/9.94 35.71/9.94 b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) 35.71/9.94 35.71/9.94 The relative TRS consists of the following S rules: 35.71/9.94 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (13) RelTRSRRRProof (EQUIVALENT) 35.71/9.94 We used the following monotonic ordering for rule removal: 35.71/9.94 Polynomial interpretation [POLO]: 35.71/9.94 35.71/9.94 POL(0_{0_1}(x_1)) = x_1 35.71/9.94 POL(0_{1_1}(x_1)) = x_1 35.71/9.94 POL(0_{b_1}(x_1)) = x_1 35.71/9.94 POL(0_{p_1}(x_1)) = x_1 35.71/9.94 POL(0_{q_1}(x_1)) = 1 + x_1 35.71/9.94 POL(1_{0_1}(x_1)) = x_1 35.71/9.94 POL(1_{1_1}(x_1)) = x_1 35.71/9.94 POL(1_{p_1}(x_1)) = x_1 35.71/9.94 POL(1_{q_1}(x_1)) = 1 + x_1 35.71/9.94 POL(b_{0_1}(x_1)) = x_1 35.71/9.94 POL(b_{1_1}(x_1)) = x_1 35.71/9.94 POL(b_{b_1}(x_1)) = x_1 35.71/9.94 POL(b_{p_1}(x_1)) = 1 + x_1 35.71/9.94 POL(b_{q_1}(x_1)) = 1 + x_1 35.71/9.94 POL(p_{0_1}(x_1)) = x_1 35.71/9.94 POL(p_{b_1}(x_1)) = x_1 35.71/9.94 POL(p_{q_1}(x_1)) = 1 + x_1 35.71/9.94 POL(q_{0_1}(x_1)) = x_1 35.71/9.94 POL(q_{1_1}(x_1)) = x_1 35.71/9.94 POL(q_{b_1}(x_1)) = x_1 35.71/9.94 POL(q_{p_1}(x_1)) = x_1 35.71/9.94 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 35.71/9.94 Rules from R: 35.71/9.94 none 35.71/9.94 Rules from S: 35.71/9.94 35.71/9.94 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{b_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{p_1}(p_{0_1}(0_{0_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (14) 35.71/9.94 Obligation: 35.71/9.94 Relative term rewrite system: 35.71/9.94 The relative TRS consists of the following R rules: 35.71/9.94 35.71/9.94 b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) 35.71/9.94 35.71/9.94 The relative TRS consists of the following S rules: 35.71/9.94 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (15) RelTRSRRRProof (EQUIVALENT) 35.71/9.94 We used the following monotonic ordering for rule removal: 35.71/9.94 Polynomial interpretation [POLO]: 35.71/9.94 35.71/9.94 POL(0_{0_1}(x_1)) = x_1 35.71/9.94 POL(0_{1_1}(x_1)) = x_1 35.71/9.94 POL(0_{b_1}(x_1)) = 1 + x_1 35.71/9.94 POL(0_{q_1}(x_1)) = x_1 35.71/9.94 POL(1_{0_1}(x_1)) = x_1 35.71/9.94 POL(1_{1_1}(x_1)) = x_1 35.71/9.94 POL(1_{p_1}(x_1)) = x_1 35.71/9.94 POL(1_{q_1}(x_1)) = x_1 35.71/9.94 POL(b_{0_1}(x_1)) = x_1 35.71/9.94 POL(b_{1_1}(x_1)) = x_1 35.71/9.94 POL(b_{b_1}(x_1)) = x_1 35.71/9.94 POL(b_{p_1}(x_1)) = 1 + x_1 35.71/9.94 POL(b_{q_1}(x_1)) = x_1 35.71/9.94 POL(p_{0_1}(x_1)) = x_1 35.71/9.94 POL(p_{b_1}(x_1)) = x_1 35.71/9.94 POL(p_{q_1}(x_1)) = x_1 35.71/9.94 POL(q_{0_1}(x_1)) = x_1 35.71/9.94 POL(q_{1_1}(x_1)) = x_1 35.71/9.94 POL(q_{b_1}(x_1)) = 1 + x_1 35.71/9.94 POL(q_{p_1}(x_1)) = x_1 35.71/9.94 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 35.71/9.94 Rules from R: 35.71/9.94 none 35.71/9.94 Rules from S: 35.71/9.94 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (16) 35.71/9.94 Obligation: 35.71/9.94 Relative term rewrite system: 35.71/9.94 The relative TRS consists of the following R rules: 35.71/9.94 35.71/9.94 b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) 35.71/9.94 35.71/9.94 The relative TRS consists of the following S rules: 35.71/9.94 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (17) RelTRSRRRProof (EQUIVALENT) 35.71/9.94 We used the following monotonic ordering for rule removal: 35.71/9.94 Polynomial interpretation [POLO]: 35.71/9.94 35.71/9.94 POL(0_{0_1}(x_1)) = x_1 35.71/9.94 POL(0_{1_1}(x_1)) = x_1 35.71/9.94 POL(0_{b_1}(x_1)) = x_1 35.71/9.94 POL(0_{q_1}(x_1)) = x_1 35.71/9.94 POL(1_{0_1}(x_1)) = x_1 35.71/9.94 POL(1_{1_1}(x_1)) = x_1 35.71/9.94 POL(1_{p_1}(x_1)) = x_1 35.71/9.94 POL(1_{q_1}(x_1)) = x_1 35.71/9.94 POL(b_{0_1}(x_1)) = x_1 35.71/9.94 POL(b_{1_1}(x_1)) = x_1 35.71/9.94 POL(b_{b_1}(x_1)) = x_1 35.71/9.94 POL(b_{p_1}(x_1)) = 1 + x_1 35.71/9.94 POL(b_{q_1}(x_1)) = 1 + x_1 35.71/9.94 POL(p_{0_1}(x_1)) = x_1 35.71/9.94 POL(p_{b_1}(x_1)) = 1 + x_1 35.71/9.94 POL(p_{q_1}(x_1)) = x_1 35.71/9.94 POL(q_{0_1}(x_1)) = x_1 35.71/9.94 POL(q_{1_1}(x_1)) = x_1 35.71/9.94 POL(q_{b_1}(x_1)) = x_1 35.71/9.94 POL(q_{p_1}(x_1)) = x_1 35.71/9.94 With this ordering the following rules can be removed [MATRO] because they are oriented strictly: 35.71/9.94 Rules from R: 35.71/9.94 35.71/9.94 b_{p_1}(p_{b_1}(b_{b_1}(x1))) -> b_{q_1}(q_{b_1}(b_{b_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{p_1}(x1))) -> b_{q_1}(q_{b_1}(b_{p_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{q_1}(x1))) -> b_{q_1}(q_{b_1}(b_{q_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{1_1}(x1))) -> b_{q_1}(q_{b_1}(b_{1_1}(x1))) 35.71/9.94 b_{p_1}(p_{b_1}(b_{0_1}(x1))) -> b_{q_1}(q_{b_1}(b_{0_1}(x1))) 35.71/9.94 Rules from S: 35.71/9.94 35.71/9.94 b_{q_1}(q_{b_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 b_{q_1}(q_{p_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 b_{q_1}(q_{1_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 b_{q_1}(q_{0_1}(x1)) -> b_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (18) 35.71/9.94 Obligation: 35.71/9.94 Relative term rewrite system: 35.71/9.94 R is empty. 35.71/9.94 The relative TRS consists of the following S rules: 35.71/9.94 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 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)) 35.71/9.94 p_{q_1}(q_{b_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 p_{q_1}(q_{1_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 p_{q_1}(q_{0_1}(x1)) -> p_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{b_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{b_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{b_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{0_1}(0_{q_1}(q_{0_1}(0_{0_1}(x1)))) 35.71/9.94 1_{q_1}(q_{p_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 1_{q_1}(q_{1_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 1_{q_1}(q_{0_1}(x1)) -> 1_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 0_{q_1}(q_{p_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{p_1}(x1)))) 35.71/9.94 0_{q_1}(q_{1_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{1_1}(x1)))) 35.71/9.94 0_{q_1}(q_{0_1}(x1)) -> 0_{1_1}(1_{q_1}(q_{1_1}(1_{0_1}(x1)))) 35.71/9.94 35.71/9.94 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (19) RIsEmptyProof (EQUIVALENT) 35.71/9.94 The TRS R is empty. Hence, termination is trivially proven. 35.71/9.94 ---------------------------------------- 35.71/9.94 35.71/9.94 (20) 35.71/9.94 YES 36.24/10.07 EOF