YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) FlatCCProof [EQUIVALENT, 0 ms] (2) QTRS (3) RootLabelingProof [EQUIVALENT, 1 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 123 ms] (6) QTRS (7) QTRSRRRProof [EQUIVALENT, 42 ms] (8) QTRS (9) DependencyPairsProof [EQUIVALENT, 20 ms] (10) QDP (11) QDPOrderProof [EQUIVALENT, 138 ms] (12) QDP (13) DependencyGraphProof [EQUIVALENT, 0 ms] (14) TRUE ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: A(b(x1)) -> b(a(B(A(x1)))) B(a(x1)) -> a(b(A(B(x1)))) A(a(x1)) -> x1 B(b(x1)) -> x1 Q is empty. ---------------------------------------- (1) FlatCCProof (EQUIVALENT) We used flat context closure [ROOTLAB] As Q is empty the flat context closure was sound AND complete. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: A(A(b(x1))) -> A(b(a(B(A(x1))))) b(A(b(x1))) -> b(b(a(B(A(x1))))) a(A(b(x1))) -> a(b(a(B(A(x1))))) B(A(b(x1))) -> B(b(a(B(A(x1))))) A(B(a(x1))) -> A(a(b(A(B(x1))))) b(B(a(x1))) -> b(a(b(A(B(x1))))) a(B(a(x1))) -> a(a(b(A(B(x1))))) B(B(a(x1))) -> B(a(b(A(B(x1))))) A(A(a(x1))) -> A(x1) b(A(a(x1))) -> b(x1) a(A(a(x1))) -> a(x1) B(A(a(x1))) -> B(x1) A(B(b(x1))) -> A(x1) b(B(b(x1))) -> b(x1) a(B(b(x1))) -> a(x1) B(B(b(x1))) -> B(x1) Q is empty. ---------------------------------------- (3) RootLabelingProof (EQUIVALENT) We used plain root labeling [ROOTLAB] with the following heuristic: LabelAll: All function symbols get labeled As Q is empty the root labeling was sound AND complete. ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: A_{A_1}(A_{b_1}(b_{A_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) A_{A_1}(A_{b_1}(b_{b_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) A_{A_1}(A_{b_1}(b_{a_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) A_{A_1}(A_{b_1}(b_{B_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) b_{A_1}(A_{b_1}(b_{A_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) b_{A_1}(A_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) b_{A_1}(A_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) b_{A_1}(A_{b_1}(b_{B_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) a_{A_1}(A_{b_1}(b_{A_1}(x1))) -> a_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) a_{A_1}(A_{b_1}(b_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) a_{A_1}(A_{b_1}(b_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) a_{A_1}(A_{b_1}(b_{B_1}(x1))) -> a_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) B_{A_1}(A_{b_1}(b_{A_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) B_{A_1}(A_{b_1}(b_{b_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) B_{A_1}(A_{b_1}(b_{a_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) B_{A_1}(A_{b_1}(b_{B_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) A_{B_1}(B_{a_1}(a_{A_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{A_1}(x1))))) A_{B_1}(B_{a_1}(a_{b_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) A_{B_1}(B_{a_1}(a_{a_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) A_{B_1}(B_{a_1}(a_{B_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) b_{B_1}(B_{a_1}(a_{A_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{A_1}(x1))))) b_{B_1}(B_{a_1}(a_{b_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) b_{B_1}(B_{a_1}(a_{a_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) b_{B_1}(B_{a_1}(a_{B_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) a_{B_1}(B_{a_1}(a_{A_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{A_1}(x1))))) a_{B_1}(B_{a_1}(a_{b_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) a_{B_1}(B_{a_1}(a_{a_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) a_{B_1}(B_{a_1}(a_{B_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) B_{B_1}(B_{a_1}(a_{A_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{A_1}(x1))))) B_{B_1}(B_{a_1}(a_{b_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) B_{B_1}(B_{a_1}(a_{a_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) B_{B_1}(B_{a_1}(a_{B_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) A_{A_1}(A_{a_1}(a_{A_1}(x1))) -> A_{A_1}(x1) A_{A_1}(A_{a_1}(a_{b_1}(x1))) -> A_{b_1}(x1) A_{A_1}(A_{a_1}(a_{a_1}(x1))) -> A_{a_1}(x1) A_{A_1}(A_{a_1}(a_{B_1}(x1))) -> A_{B_1}(x1) b_{A_1}(A_{a_1}(a_{A_1}(x1))) -> b_{A_1}(x1) b_{A_1}(A_{a_1}(a_{b_1}(x1))) -> b_{b_1}(x1) b_{A_1}(A_{a_1}(a_{a_1}(x1))) -> b_{a_1}(x1) b_{A_1}(A_{a_1}(a_{B_1}(x1))) -> b_{B_1}(x1) a_{A_1}(A_{a_1}(a_{A_1}(x1))) -> a_{A_1}(x1) a_{A_1}(A_{a_1}(a_{b_1}(x1))) -> a_{b_1}(x1) a_{A_1}(A_{a_1}(a_{a_1}(x1))) -> a_{a_1}(x1) a_{A_1}(A_{a_1}(a_{B_1}(x1))) -> a_{B_1}(x1) B_{A_1}(A_{a_1}(a_{A_1}(x1))) -> B_{A_1}(x1) B_{A_1}(A_{a_1}(a_{b_1}(x1))) -> B_{b_1}(x1) B_{A_1}(A_{a_1}(a_{a_1}(x1))) -> B_{a_1}(x1) B_{A_1}(A_{a_1}(a_{B_1}(x1))) -> B_{B_1}(x1) A_{B_1}(B_{b_1}(b_{A_1}(x1))) -> A_{A_1}(x1) A_{B_1}(B_{b_1}(b_{b_1}(x1))) -> A_{b_1}(x1) A_{B_1}(B_{b_1}(b_{a_1}(x1))) -> A_{a_1}(x1) A_{B_1}(B_{b_1}(b_{B_1}(x1))) -> A_{B_1}(x1) b_{B_1}(B_{b_1}(b_{A_1}(x1))) -> b_{A_1}(x1) b_{B_1}(B_{b_1}(b_{b_1}(x1))) -> b_{b_1}(x1) b_{B_1}(B_{b_1}(b_{a_1}(x1))) -> b_{a_1}(x1) b_{B_1}(B_{b_1}(b_{B_1}(x1))) -> b_{B_1}(x1) a_{B_1}(B_{b_1}(b_{A_1}(x1))) -> a_{A_1}(x1) a_{B_1}(B_{b_1}(b_{b_1}(x1))) -> a_{b_1}(x1) a_{B_1}(B_{b_1}(b_{a_1}(x1))) -> a_{a_1}(x1) a_{B_1}(B_{b_1}(b_{B_1}(x1))) -> a_{B_1}(x1) B_{B_1}(B_{b_1}(b_{A_1}(x1))) -> B_{A_1}(x1) B_{B_1}(B_{b_1}(b_{b_1}(x1))) -> B_{b_1}(x1) B_{B_1}(B_{b_1}(b_{a_1}(x1))) -> B_{a_1}(x1) B_{B_1}(B_{b_1}(b_{B_1}(x1))) -> B_{B_1}(x1) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(A_{A_1}(x_1)) = 1 + x_1 POL(A_{B_1}(x_1)) = x_1 POL(A_{a_1}(x_1)) = x_1 POL(A_{b_1}(x_1)) = 1 + x_1 POL(B_{A_1}(x_1)) = x_1 POL(B_{B_1}(x_1)) = 1 + x_1 POL(B_{a_1}(x_1)) = 1 + x_1 POL(B_{b_1}(x_1)) = x_1 POL(a_{A_1}(x_1)) = 1 + x_1 POL(a_{B_1}(x_1)) = 1 + x_1 POL(a_{a_1}(x_1)) = 1 + x_1 POL(a_{b_1}(x_1)) = x_1 POL(b_{A_1}(x_1)) = 1 + x_1 POL(b_{B_1}(x_1)) = x_1 POL(b_{a_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = 1 + x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a_{A_1}(A_{b_1}(b_{A_1}(x1))) -> a_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) a_{A_1}(A_{b_1}(b_{b_1}(x1))) -> a_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) a_{A_1}(A_{b_1}(b_{a_1}(x1))) -> a_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) a_{A_1}(A_{b_1}(b_{B_1}(x1))) -> a_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) A_{B_1}(B_{a_1}(a_{A_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{A_1}(x1))))) b_{B_1}(B_{a_1}(a_{A_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{A_1}(x1))))) a_{B_1}(B_{a_1}(a_{A_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{A_1}(x1))))) B_{B_1}(B_{a_1}(a_{A_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{A_1}(x1))))) A_{A_1}(A_{a_1}(a_{A_1}(x1))) -> A_{A_1}(x1) A_{A_1}(A_{a_1}(a_{a_1}(x1))) -> A_{a_1}(x1) A_{A_1}(A_{a_1}(a_{B_1}(x1))) -> A_{B_1}(x1) b_{A_1}(A_{a_1}(a_{A_1}(x1))) -> b_{A_1}(x1) b_{A_1}(A_{a_1}(a_{a_1}(x1))) -> b_{a_1}(x1) b_{A_1}(A_{a_1}(a_{B_1}(x1))) -> b_{B_1}(x1) a_{A_1}(A_{a_1}(a_{A_1}(x1))) -> a_{A_1}(x1) a_{A_1}(A_{a_1}(a_{b_1}(x1))) -> a_{b_1}(x1) a_{A_1}(A_{a_1}(a_{a_1}(x1))) -> a_{a_1}(x1) a_{A_1}(A_{a_1}(a_{B_1}(x1))) -> a_{B_1}(x1) B_{A_1}(A_{a_1}(a_{A_1}(x1))) -> B_{A_1}(x1) a_{B_1}(B_{b_1}(b_{A_1}(x1))) -> a_{A_1}(x1) a_{B_1}(B_{b_1}(b_{b_1}(x1))) -> a_{b_1}(x1) B_{B_1}(B_{b_1}(b_{A_1}(x1))) -> B_{A_1}(x1) B_{B_1}(B_{b_1}(b_{b_1}(x1))) -> B_{b_1}(x1) ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: A_{A_1}(A_{b_1}(b_{A_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) A_{A_1}(A_{b_1}(b_{b_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) A_{A_1}(A_{b_1}(b_{a_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) A_{A_1}(A_{b_1}(b_{B_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) b_{A_1}(A_{b_1}(b_{A_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) b_{A_1}(A_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) b_{A_1}(A_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) b_{A_1}(A_{b_1}(b_{B_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) B_{A_1}(A_{b_1}(b_{A_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) B_{A_1}(A_{b_1}(b_{b_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) B_{A_1}(A_{b_1}(b_{a_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) B_{A_1}(A_{b_1}(b_{B_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) A_{B_1}(B_{a_1}(a_{b_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) A_{B_1}(B_{a_1}(a_{a_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) A_{B_1}(B_{a_1}(a_{B_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) b_{B_1}(B_{a_1}(a_{b_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) b_{B_1}(B_{a_1}(a_{a_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) b_{B_1}(B_{a_1}(a_{B_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) a_{B_1}(B_{a_1}(a_{b_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) a_{B_1}(B_{a_1}(a_{a_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) a_{B_1}(B_{a_1}(a_{B_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) B_{B_1}(B_{a_1}(a_{b_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) B_{B_1}(B_{a_1}(a_{a_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) B_{B_1}(B_{a_1}(a_{B_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) A_{A_1}(A_{a_1}(a_{b_1}(x1))) -> A_{b_1}(x1) b_{A_1}(A_{a_1}(a_{b_1}(x1))) -> b_{b_1}(x1) B_{A_1}(A_{a_1}(a_{b_1}(x1))) -> B_{b_1}(x1) B_{A_1}(A_{a_1}(a_{a_1}(x1))) -> B_{a_1}(x1) B_{A_1}(A_{a_1}(a_{B_1}(x1))) -> B_{B_1}(x1) A_{B_1}(B_{b_1}(b_{A_1}(x1))) -> A_{A_1}(x1) A_{B_1}(B_{b_1}(b_{b_1}(x1))) -> A_{b_1}(x1) A_{B_1}(B_{b_1}(b_{a_1}(x1))) -> A_{a_1}(x1) A_{B_1}(B_{b_1}(b_{B_1}(x1))) -> A_{B_1}(x1) b_{B_1}(B_{b_1}(b_{A_1}(x1))) -> b_{A_1}(x1) b_{B_1}(B_{b_1}(b_{b_1}(x1))) -> b_{b_1}(x1) b_{B_1}(B_{b_1}(b_{a_1}(x1))) -> b_{a_1}(x1) b_{B_1}(B_{b_1}(b_{B_1}(x1))) -> b_{B_1}(x1) a_{B_1}(B_{b_1}(b_{a_1}(x1))) -> a_{a_1}(x1) a_{B_1}(B_{b_1}(b_{B_1}(x1))) -> a_{B_1}(x1) B_{B_1}(B_{b_1}(b_{a_1}(x1))) -> B_{a_1}(x1) B_{B_1}(B_{b_1}(b_{B_1}(x1))) -> B_{B_1}(x1) Q is empty. ---------------------------------------- (7) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(A_{A_1}(x_1)) = x_1 POL(A_{B_1}(x_1)) = x_1 POL(A_{a_1}(x_1)) = x_1 POL(A_{b_1}(x_1)) = x_1 POL(B_{A_1}(x_1)) = x_1 POL(B_{B_1}(x_1)) = x_1 POL(B_{a_1}(x_1)) = x_1 POL(B_{b_1}(x_1)) = x_1 POL(a_{B_1}(x_1)) = x_1 POL(a_{a_1}(x_1)) = x_1 POL(a_{b_1}(x_1)) = x_1 POL(b_{A_1}(x_1)) = x_1 POL(b_{B_1}(x_1)) = 1 + x_1 POL(b_{a_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: A_{A_1}(A_{b_1}(b_{B_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) b_{A_1}(A_{b_1}(b_{B_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) B_{A_1}(A_{b_1}(b_{B_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{B_1}(x1))))) b_{B_1}(B_{a_1}(a_{b_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) b_{B_1}(B_{a_1}(a_{a_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) b_{B_1}(B_{a_1}(a_{B_1}(x1))) -> b_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) A_{B_1}(B_{b_1}(b_{B_1}(x1))) -> A_{B_1}(x1) b_{B_1}(B_{b_1}(b_{A_1}(x1))) -> b_{A_1}(x1) b_{B_1}(B_{b_1}(b_{b_1}(x1))) -> b_{b_1}(x1) b_{B_1}(B_{b_1}(b_{a_1}(x1))) -> b_{a_1}(x1) b_{B_1}(B_{b_1}(b_{B_1}(x1))) -> b_{B_1}(x1) a_{B_1}(B_{b_1}(b_{B_1}(x1))) -> a_{B_1}(x1) B_{B_1}(B_{b_1}(b_{B_1}(x1))) -> B_{B_1}(x1) ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: A_{A_1}(A_{b_1}(b_{A_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) A_{A_1}(A_{b_1}(b_{b_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) A_{A_1}(A_{b_1}(b_{a_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) b_{A_1}(A_{b_1}(b_{A_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) b_{A_1}(A_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) b_{A_1}(A_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) B_{A_1}(A_{b_1}(b_{A_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) B_{A_1}(A_{b_1}(b_{b_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) B_{A_1}(A_{b_1}(b_{a_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) A_{B_1}(B_{a_1}(a_{b_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) A_{B_1}(B_{a_1}(a_{a_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) A_{B_1}(B_{a_1}(a_{B_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) a_{B_1}(B_{a_1}(a_{b_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) a_{B_1}(B_{a_1}(a_{a_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) a_{B_1}(B_{a_1}(a_{B_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) B_{B_1}(B_{a_1}(a_{b_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) B_{B_1}(B_{a_1}(a_{a_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) B_{B_1}(B_{a_1}(a_{B_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) A_{A_1}(A_{a_1}(a_{b_1}(x1))) -> A_{b_1}(x1) b_{A_1}(A_{a_1}(a_{b_1}(x1))) -> b_{b_1}(x1) B_{A_1}(A_{a_1}(a_{b_1}(x1))) -> B_{b_1}(x1) B_{A_1}(A_{a_1}(a_{a_1}(x1))) -> B_{a_1}(x1) B_{A_1}(A_{a_1}(a_{B_1}(x1))) -> B_{B_1}(x1) A_{B_1}(B_{b_1}(b_{A_1}(x1))) -> A_{A_1}(x1) A_{B_1}(B_{b_1}(b_{b_1}(x1))) -> A_{b_1}(x1) A_{B_1}(B_{b_1}(b_{a_1}(x1))) -> A_{a_1}(x1) a_{B_1}(B_{b_1}(b_{a_1}(x1))) -> a_{a_1}(x1) B_{B_1}(B_{b_1}(b_{a_1}(x1))) -> B_{a_1}(x1) Q is empty. ---------------------------------------- (9) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: A_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{A_1}(x1))) A_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> B_{A_1}^1(A_{A_1}(x1)) A_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> A_{A_1}^1(x1) A_{A_1}^1(A_{b_1}(b_{b_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{b_1}(x1))) A_{A_1}^1(A_{b_1}(b_{b_1}(x1))) -> B_{A_1}^1(A_{b_1}(x1)) A_{A_1}^1(A_{b_1}(b_{a_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{a_1}(x1))) A_{A_1}^1(A_{b_1}(b_{a_1}(x1))) -> B_{A_1}^1(A_{a_1}(x1)) B_{A_1}^2(A_{b_1}(b_{A_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{A_1}(x1))) B_{A_1}^2(A_{b_1}(b_{A_1}(x1))) -> B_{A_1}^1(A_{A_1}(x1)) B_{A_1}^2(A_{b_1}(b_{A_1}(x1))) -> A_{A_1}^1(x1) B_{A_1}^2(A_{b_1}(b_{b_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{b_1}(x1))) B_{A_1}^2(A_{b_1}(b_{b_1}(x1))) -> B_{A_1}^1(A_{b_1}(x1)) B_{A_1}^2(A_{b_1}(b_{a_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{a_1}(x1))) B_{A_1}^2(A_{b_1}(b_{a_1}(x1))) -> B_{A_1}^1(A_{a_1}(x1)) B_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{A_1}(x1))) B_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> B_{A_1}^1(A_{A_1}(x1)) B_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> A_{A_1}^1(x1) B_{A_1}^1(A_{b_1}(b_{b_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{b_1}(x1))) B_{A_1}^1(A_{b_1}(b_{b_1}(x1))) -> B_{A_1}^1(A_{b_1}(x1)) B_{A_1}^1(A_{b_1}(b_{a_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{a_1}(x1))) B_{A_1}^1(A_{b_1}(b_{a_1}(x1))) -> B_{A_1}^1(A_{a_1}(x1)) A_{B_1}^2(B_{a_1}(a_{b_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{b_1}(x1))) A_{B_1}^2(B_{a_1}(a_{b_1}(x1))) -> A_{B_1}^2(B_{b_1}(x1)) A_{B_1}^2(B_{a_1}(a_{a_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{a_1}(x1))) A_{B_1}^2(B_{a_1}(a_{a_1}(x1))) -> A_{B_1}^2(B_{a_1}(x1)) A_{B_1}^2(B_{a_1}(a_{B_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{B_1}(x1))) A_{B_1}^2(B_{a_1}(a_{B_1}(x1))) -> A_{B_1}^2(B_{B_1}(x1)) A_{B_1}^2(B_{a_1}(a_{B_1}(x1))) -> B_{B_1}^1(x1) A_{B_1}^1(B_{a_1}(a_{b_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{b_1}(x1))) A_{B_1}^1(B_{a_1}(a_{b_1}(x1))) -> A_{B_1}^2(B_{b_1}(x1)) A_{B_1}^1(B_{a_1}(a_{a_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{a_1}(x1))) A_{B_1}^1(B_{a_1}(a_{a_1}(x1))) -> A_{B_1}^2(B_{a_1}(x1)) A_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{B_1}(x1))) A_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> A_{B_1}^2(B_{B_1}(x1)) A_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> B_{B_1}^1(x1) B_{B_1}^1(B_{a_1}(a_{b_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{b_1}(x1))) B_{B_1}^1(B_{a_1}(a_{b_1}(x1))) -> A_{B_1}^2(B_{b_1}(x1)) B_{B_1}^1(B_{a_1}(a_{a_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{a_1}(x1))) B_{B_1}^1(B_{a_1}(a_{a_1}(x1))) -> A_{B_1}^2(B_{a_1}(x1)) B_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{B_1}(x1))) B_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> A_{B_1}^2(B_{B_1}(x1)) B_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> B_{B_1}^1(x1) B_{A_1}^1(A_{a_1}(a_{B_1}(x1))) -> B_{B_1}^1(x1) A_{B_1}^2(B_{b_1}(b_{A_1}(x1))) -> A_{A_1}^1(x1) The TRS R consists of the following rules: A_{A_1}(A_{b_1}(b_{A_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) A_{A_1}(A_{b_1}(b_{b_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) A_{A_1}(A_{b_1}(b_{a_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) b_{A_1}(A_{b_1}(b_{A_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) b_{A_1}(A_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) b_{A_1}(A_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) B_{A_1}(A_{b_1}(b_{A_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) B_{A_1}(A_{b_1}(b_{b_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) B_{A_1}(A_{b_1}(b_{a_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) A_{B_1}(B_{a_1}(a_{b_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) A_{B_1}(B_{a_1}(a_{a_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) A_{B_1}(B_{a_1}(a_{B_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) a_{B_1}(B_{a_1}(a_{b_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) a_{B_1}(B_{a_1}(a_{a_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) a_{B_1}(B_{a_1}(a_{B_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) B_{B_1}(B_{a_1}(a_{b_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) B_{B_1}(B_{a_1}(a_{a_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) B_{B_1}(B_{a_1}(a_{B_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) A_{A_1}(A_{a_1}(a_{b_1}(x1))) -> A_{b_1}(x1) b_{A_1}(A_{a_1}(a_{b_1}(x1))) -> b_{b_1}(x1) B_{A_1}(A_{a_1}(a_{b_1}(x1))) -> B_{b_1}(x1) B_{A_1}(A_{a_1}(a_{a_1}(x1))) -> B_{a_1}(x1) B_{A_1}(A_{a_1}(a_{B_1}(x1))) -> B_{B_1}(x1) A_{B_1}(B_{b_1}(b_{A_1}(x1))) -> A_{A_1}(x1) A_{B_1}(B_{b_1}(b_{b_1}(x1))) -> A_{b_1}(x1) A_{B_1}(B_{b_1}(b_{a_1}(x1))) -> A_{a_1}(x1) a_{B_1}(B_{b_1}(b_{a_1}(x1))) -> a_{a_1}(x1) B_{B_1}(B_{b_1}(b_{a_1}(x1))) -> B_{a_1}(x1) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. A_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> B_{A_1}^1(A_{A_1}(x1)) A_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> A_{A_1}^1(x1) A_{A_1}^1(A_{b_1}(b_{b_1}(x1))) -> B_{A_1}^1(A_{b_1}(x1)) A_{A_1}^1(A_{b_1}(b_{a_1}(x1))) -> B_{A_1}^1(A_{a_1}(x1)) B_{A_1}^2(A_{b_1}(b_{A_1}(x1))) -> B_{A_1}^1(A_{A_1}(x1)) B_{A_1}^2(A_{b_1}(b_{A_1}(x1))) -> A_{A_1}^1(x1) B_{A_1}^2(A_{b_1}(b_{b_1}(x1))) -> B_{A_1}^1(A_{b_1}(x1)) B_{A_1}^2(A_{b_1}(b_{a_1}(x1))) -> B_{A_1}^1(A_{a_1}(x1)) B_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> B_{A_1}^1(A_{A_1}(x1)) B_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> A_{A_1}^1(x1) B_{A_1}^1(A_{b_1}(b_{b_1}(x1))) -> B_{A_1}^1(A_{b_1}(x1)) B_{A_1}^1(A_{b_1}(b_{a_1}(x1))) -> B_{A_1}^1(A_{a_1}(x1)) A_{B_1}^2(B_{a_1}(a_{b_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{b_1}(x1))) A_{B_1}^2(B_{a_1}(a_{b_1}(x1))) -> A_{B_1}^2(B_{b_1}(x1)) A_{B_1}^2(B_{a_1}(a_{a_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{a_1}(x1))) A_{B_1}^2(B_{a_1}(a_{a_1}(x1))) -> A_{B_1}^2(B_{a_1}(x1)) A_{B_1}^2(B_{a_1}(a_{B_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{B_1}(x1))) A_{B_1}^2(B_{a_1}(a_{B_1}(x1))) -> A_{B_1}^2(B_{B_1}(x1)) A_{B_1}^2(B_{a_1}(a_{B_1}(x1))) -> B_{B_1}^1(x1) A_{B_1}^1(B_{a_1}(a_{b_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{b_1}(x1))) A_{B_1}^1(B_{a_1}(a_{b_1}(x1))) -> A_{B_1}^2(B_{b_1}(x1)) A_{B_1}^1(B_{a_1}(a_{a_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{a_1}(x1))) A_{B_1}^1(B_{a_1}(a_{a_1}(x1))) -> A_{B_1}^2(B_{a_1}(x1)) A_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{B_1}(x1))) A_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> A_{B_1}^2(B_{B_1}(x1)) A_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> B_{B_1}^1(x1) B_{B_1}^1(B_{a_1}(a_{b_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{b_1}(x1))) B_{B_1}^1(B_{a_1}(a_{b_1}(x1))) -> A_{B_1}^2(B_{b_1}(x1)) B_{B_1}^1(B_{a_1}(a_{a_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{a_1}(x1))) B_{B_1}^1(B_{a_1}(a_{a_1}(x1))) -> A_{B_1}^2(B_{a_1}(x1)) B_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> B_{A_1}^2(A_{B_1}(B_{B_1}(x1))) B_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> A_{B_1}^2(B_{B_1}(x1)) B_{B_1}^1(B_{a_1}(a_{B_1}(x1))) -> B_{B_1}^1(x1) B_{A_1}^1(A_{a_1}(a_{B_1}(x1))) -> B_{B_1}^1(x1) A_{B_1}^2(B_{b_1}(b_{A_1}(x1))) -> A_{A_1}^1(x1) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(A_{A_1}(x_1)) = 1 + x_1 POL(A_{A_1}^1(x_1)) = x_1 POL(A_{B_1}(x_1)) = x_1 POL(A_{B_1}^1(x_1)) = 1 + x_1 POL(A_{B_1}^2(x_1)) = x_1 POL(A_{a_1}(x_1)) = x_1 POL(A_{b_1}(x_1)) = 1 + x_1 POL(B_{A_1}(x_1)) = x_1 POL(B_{A_1}^1(x_1)) = x_1 POL(B_{A_1}^2(x_1)) = x_1 POL(B_{B_1}(x_1)) = 1 + x_1 POL(B_{B_1}^1(x_1)) = x_1 POL(B_{a_1}(x_1)) = 1 + x_1 POL(B_{b_1}(x_1)) = x_1 POL(a_{B_1}(x_1)) = 1 + x_1 POL(a_{a_1}(x_1)) = 1 + x_1 POL(a_{b_1}(x_1)) = x_1 POL(b_{A_1}(x_1)) = 1 + x_1 POL(b_{a_1}(x_1)) = x_1 POL(b_{b_1}(x_1)) = 1 + x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: A_{A_1}(A_{b_1}(b_{A_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) A_{A_1}(A_{b_1}(b_{b_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) A_{A_1}(A_{b_1}(b_{a_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) A_{A_1}(A_{a_1}(a_{b_1}(x1))) -> A_{b_1}(x1) B_{A_1}(A_{b_1}(b_{A_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) B_{A_1}(A_{b_1}(b_{b_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) B_{A_1}(A_{b_1}(b_{a_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) B_{A_1}(A_{a_1}(a_{b_1}(x1))) -> B_{b_1}(x1) B_{A_1}(A_{a_1}(a_{a_1}(x1))) -> B_{a_1}(x1) B_{A_1}(A_{a_1}(a_{B_1}(x1))) -> B_{B_1}(x1) A_{B_1}(B_{b_1}(b_{A_1}(x1))) -> A_{A_1}(x1) A_{B_1}(B_{b_1}(b_{b_1}(x1))) -> A_{b_1}(x1) A_{B_1}(B_{b_1}(b_{a_1}(x1))) -> A_{a_1}(x1) A_{B_1}(B_{a_1}(a_{b_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) A_{B_1}(B_{a_1}(a_{a_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) A_{B_1}(B_{a_1}(a_{B_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) B_{B_1}(B_{a_1}(a_{b_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) B_{B_1}(B_{a_1}(a_{a_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) B_{B_1}(B_{a_1}(a_{B_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) B_{B_1}(B_{b_1}(b_{a_1}(x1))) -> B_{a_1}(x1) a_{B_1}(B_{a_1}(a_{b_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) a_{B_1}(B_{a_1}(a_{a_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) a_{B_1}(B_{a_1}(a_{B_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) b_{A_1}(A_{b_1}(b_{A_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) b_{A_1}(A_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) b_{A_1}(A_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) a_{B_1}(B_{b_1}(b_{a_1}(x1))) -> a_{a_1}(x1) b_{A_1}(A_{a_1}(a_{b_1}(x1))) -> b_{b_1}(x1) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: A_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{A_1}(x1))) A_{A_1}^1(A_{b_1}(b_{b_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{b_1}(x1))) A_{A_1}^1(A_{b_1}(b_{a_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{a_1}(x1))) B_{A_1}^2(A_{b_1}(b_{A_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{A_1}(x1))) B_{A_1}^2(A_{b_1}(b_{b_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{b_1}(x1))) B_{A_1}^2(A_{b_1}(b_{a_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{a_1}(x1))) B_{A_1}^1(A_{b_1}(b_{A_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{A_1}(x1))) B_{A_1}^1(A_{b_1}(b_{b_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{b_1}(x1))) B_{A_1}^1(A_{b_1}(b_{a_1}(x1))) -> A_{B_1}^1(B_{A_1}(A_{a_1}(x1))) The TRS R consists of the following rules: A_{A_1}(A_{b_1}(b_{A_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) A_{A_1}(A_{b_1}(b_{b_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) A_{A_1}(A_{b_1}(b_{a_1}(x1))) -> A_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) b_{A_1}(A_{b_1}(b_{A_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) b_{A_1}(A_{b_1}(b_{b_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) b_{A_1}(A_{b_1}(b_{a_1}(x1))) -> b_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) B_{A_1}(A_{b_1}(b_{A_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{A_1}(x1))))) B_{A_1}(A_{b_1}(b_{b_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{b_1}(x1))))) B_{A_1}(A_{b_1}(b_{a_1}(x1))) -> B_{b_1}(b_{a_1}(a_{B_1}(B_{A_1}(A_{a_1}(x1))))) A_{B_1}(B_{a_1}(a_{b_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) A_{B_1}(B_{a_1}(a_{a_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) A_{B_1}(B_{a_1}(a_{B_1}(x1))) -> A_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) a_{B_1}(B_{a_1}(a_{b_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) a_{B_1}(B_{a_1}(a_{a_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) a_{B_1}(B_{a_1}(a_{B_1}(x1))) -> a_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) B_{B_1}(B_{a_1}(a_{b_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{b_1}(x1))))) B_{B_1}(B_{a_1}(a_{a_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{a_1}(x1))))) B_{B_1}(B_{a_1}(a_{B_1}(x1))) -> B_{a_1}(a_{b_1}(b_{A_1}(A_{B_1}(B_{B_1}(x1))))) A_{A_1}(A_{a_1}(a_{b_1}(x1))) -> A_{b_1}(x1) b_{A_1}(A_{a_1}(a_{b_1}(x1))) -> b_{b_1}(x1) B_{A_1}(A_{a_1}(a_{b_1}(x1))) -> B_{b_1}(x1) B_{A_1}(A_{a_1}(a_{a_1}(x1))) -> B_{a_1}(x1) B_{A_1}(A_{a_1}(a_{B_1}(x1))) -> B_{B_1}(x1) A_{B_1}(B_{b_1}(b_{A_1}(x1))) -> A_{A_1}(x1) A_{B_1}(B_{b_1}(b_{b_1}(x1))) -> A_{b_1}(x1) A_{B_1}(B_{b_1}(b_{a_1}(x1))) -> A_{a_1}(x1) a_{B_1}(B_{b_1}(b_{a_1}(x1))) -> a_{a_1}(x1) B_{B_1}(B_{b_1}(b_{a_1}(x1))) -> B_{a_1}(x1) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 9 less nodes. ---------------------------------------- (14) TRUE