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) QTRSRRRProof [EQUIVALENT, 104 ms] (2) QTRS (3) Overlay + Local Confluence [EQUIVALENT, 0 ms] (4) QTRS (5) DependencyPairsProof [EQUIVALENT, 25 ms] (6) QDP (7) MRRProof [EQUIVALENT, 139 ms] (8) QDP (9) PisEmptyProof [EQUIVALENT, 0 ms] (10) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(b(x1)) -> C(x1) b(c(x1)) -> A(x1) c(a(x1)) -> B(x1) A(C(x1)) -> b(x1) C(B(x1)) -> a(x1) B(A(x1)) -> c(x1) a(a(a(a(a(x1))))) -> A(A(A(x1))) A(A(A(A(x1)))) -> a(a(a(a(x1)))) b(b(b(b(b(x1))))) -> B(B(B(x1))) B(B(B(B(x1)))) -> b(b(b(b(x1)))) c(c(c(c(c(x1))))) -> C(C(C(x1))) C(C(C(C(x1)))) -> c(c(c(c(x1)))) B(a(a(a(a(x1))))) -> c(A(A(A(x1)))) A(A(A(b(x1)))) -> a(a(a(a(C(x1))))) C(b(b(b(b(x1))))) -> a(B(B(B(x1)))) B(B(B(c(x1)))) -> b(b(b(b(A(x1))))) A(c(c(c(c(x1))))) -> b(C(C(C(x1)))) C(C(C(a(x1)))) -> c(c(c(c(B(x1))))) a(A(x1)) -> x1 A(a(x1)) -> x1 b(B(x1)) -> x1 B(b(x1)) -> x1 c(C(x1)) -> x1 C(c(x1)) -> x1 Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(A(x_1)) = 3 + x_1 POL(B(x_1)) = 3 + x_1 POL(C(x_1)) = 3 + x_1 POL(a(x_1)) = 2 + x_1 POL(b(x_1)) = 2 + x_1 POL(c(x_1)) = 2 + x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: a(b(x1)) -> C(x1) b(c(x1)) -> A(x1) c(a(x1)) -> B(x1) A(C(x1)) -> b(x1) C(B(x1)) -> a(x1) B(A(x1)) -> c(x1) a(a(a(a(a(x1))))) -> A(A(A(x1))) A(A(A(A(x1)))) -> a(a(a(a(x1)))) b(b(b(b(b(x1))))) -> B(B(B(x1))) B(B(B(B(x1)))) -> b(b(b(b(x1)))) c(c(c(c(c(x1))))) -> C(C(C(x1))) C(C(C(C(x1)))) -> c(c(c(c(x1)))) a(A(x1)) -> x1 A(a(x1)) -> x1 b(B(x1)) -> x1 B(b(x1)) -> x1 c(C(x1)) -> x1 C(c(x1)) -> x1 ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: B(a(a(a(a(x1))))) -> c(A(A(A(x1)))) A(A(A(b(x1)))) -> a(a(a(a(C(x1))))) C(b(b(b(b(x1))))) -> a(B(B(B(x1)))) B(B(B(c(x1)))) -> b(b(b(b(A(x1))))) A(c(c(c(c(x1))))) -> b(C(C(C(x1)))) C(C(C(a(x1)))) -> c(c(c(c(B(x1))))) Q is empty. ---------------------------------------- (3) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: B(a(a(a(a(x1))))) -> c(A(A(A(x1)))) A(A(A(b(x1)))) -> a(a(a(a(C(x1))))) C(b(b(b(b(x1))))) -> a(B(B(B(x1)))) B(B(B(c(x1)))) -> b(b(b(b(A(x1))))) A(c(c(c(c(x1))))) -> b(C(C(C(x1)))) C(C(C(a(x1)))) -> c(c(c(c(B(x1))))) The set Q consists of the following terms: B(a(a(a(a(x0))))) A(A(A(b(x0)))) C(b(b(b(b(x0))))) B(B(B(c(x0)))) A(c(c(c(c(x0))))) C(C(C(a(x0)))) ---------------------------------------- (5) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: B^1(a(a(a(a(x1))))) -> A^1(A(A(x1))) B^1(a(a(a(a(x1))))) -> A^1(A(x1)) B^1(a(a(a(a(x1))))) -> A^1(x1) A^1(A(A(b(x1)))) -> C^1(x1) C^1(b(b(b(b(x1))))) -> B^1(B(B(x1))) C^1(b(b(b(b(x1))))) -> B^1(B(x1)) C^1(b(b(b(b(x1))))) -> B^1(x1) B^1(B(B(c(x1)))) -> A^1(x1) A^1(c(c(c(c(x1))))) -> C^1(C(C(x1))) A^1(c(c(c(c(x1))))) -> C^1(C(x1)) A^1(c(c(c(c(x1))))) -> C^1(x1) C^1(C(C(a(x1)))) -> B^1(x1) The TRS R consists of the following rules: B(a(a(a(a(x1))))) -> c(A(A(A(x1)))) A(A(A(b(x1)))) -> a(a(a(a(C(x1))))) C(b(b(b(b(x1))))) -> a(B(B(B(x1)))) B(B(B(c(x1)))) -> b(b(b(b(A(x1))))) A(c(c(c(c(x1))))) -> b(C(C(C(x1)))) C(C(C(a(x1)))) -> c(c(c(c(B(x1))))) The set Q consists of the following terms: B(a(a(a(a(x0))))) A(A(A(b(x0)))) C(b(b(b(b(x0))))) B(B(B(c(x0)))) A(c(c(c(c(x0))))) C(C(C(a(x0)))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: B^1(a(a(a(a(x1))))) -> A^1(A(A(x1))) B^1(a(a(a(a(x1))))) -> A^1(A(x1)) B^1(a(a(a(a(x1))))) -> A^1(x1) A^1(A(A(b(x1)))) -> C^1(x1) C^1(b(b(b(b(x1))))) -> B^1(B(B(x1))) C^1(b(b(b(b(x1))))) -> B^1(B(x1)) C^1(b(b(b(b(x1))))) -> B^1(x1) B^1(B(B(c(x1)))) -> A^1(x1) A^1(c(c(c(c(x1))))) -> C^1(C(C(x1))) A^1(c(c(c(c(x1))))) -> C^1(C(x1)) A^1(c(c(c(c(x1))))) -> C^1(x1) C^1(C(C(a(x1)))) -> B^1(x1) Used ordering: Polynomial interpretation [POLO]: POL(A(x_1)) = 3 + x_1 POL(A^1(x_1)) = 2 + x_1 POL(B(x_1)) = 3 + x_1 POL(B^1(x_1)) = 1 + x_1 POL(C(x_1)) = 3 + x_1 POL(C^1(x_1)) = x_1 POL(a(x_1)) = 2 + x_1 POL(b(x_1)) = 2 + x_1 POL(c(x_1)) = 2 + x_1 ---------------------------------------- (8) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: B(a(a(a(a(x1))))) -> c(A(A(A(x1)))) A(A(A(b(x1)))) -> a(a(a(a(C(x1))))) C(b(b(b(b(x1))))) -> a(B(B(B(x1)))) B(B(B(c(x1)))) -> b(b(b(b(A(x1))))) A(c(c(c(c(x1))))) -> b(C(C(C(x1)))) C(C(C(a(x1)))) -> c(c(c(c(B(x1))))) The set Q consists of the following terms: B(a(a(a(a(x0))))) A(A(A(b(x0)))) C(b(b(b(b(x0))))) B(B(B(c(x0)))) A(c(c(c(c(x0))))) C(C(C(a(x0)))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (10) YES