YES proof of /export/starexec/sandbox2/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) QTRS Reverse [EQUIVALENT, 0 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 75 ms] (4) QTRS (5) Overlay + Local Confluence [EQUIVALENT, 2 ms] (6) QTRS (7) DependencyPairsProof [EQUIVALENT, 48 ms] (8) QDP (9) MRRProof [EQUIVALENT, 701 ms] (10) QDP (11) PisEmptyProof [EQUIVALENT, 0 ms] (12) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(a(b(b(x1)))) -> C(C(x1)) b(b(c(c(x1)))) -> A(A(x1)) c(c(a(a(x1)))) -> B(B(x1)) A(A(C(C(x1)))) -> b(b(x1)) C(C(B(B(x1)))) -> a(a(x1)) B(B(A(A(x1)))) -> c(c(x1)) a(a(a(a(a(a(a(a(a(a(x1)))))))))) -> A(A(A(A(A(A(x1)))))) A(A(A(A(A(A(A(A(x1)))))))) -> a(a(a(a(a(a(a(a(x1)))))))) b(b(b(b(b(b(b(b(b(b(x1)))))))))) -> B(B(B(B(B(B(x1)))))) B(B(B(B(B(B(B(B(x1)))))))) -> b(b(b(b(b(b(b(b(x1)))))))) c(c(c(c(c(c(c(c(c(c(x1)))))))))) -> C(C(C(C(C(C(x1)))))) C(C(C(C(C(C(C(C(x1)))))))) -> c(c(c(c(c(c(c(c(x1)))))))) B(B(a(a(a(a(a(a(a(a(x1)))))))))) -> c(c(A(A(A(A(A(A(x1)))))))) A(A(A(A(A(A(b(b(x1)))))))) -> a(a(a(a(a(a(a(a(C(C(x1)))))))))) C(C(b(b(b(b(b(b(b(b(x1)))))))))) -> a(a(B(B(B(B(B(B(x1)))))))) B(B(B(B(B(B(c(c(x1)))))))) -> b(b(b(b(b(b(b(b(A(A(x1)))))))))) A(A(c(c(c(c(c(c(c(c(x1)))))))))) -> b(b(C(C(C(C(C(C(x1)))))))) C(C(C(C(C(C(a(a(x1)))))))) -> c(c(c(c(c(c(c(c(B(B(x1)))))))))) a(a(A(A(x1)))) -> x1 A(A(a(a(x1)))) -> x1 b(b(B(B(x1)))) -> x1 B(B(b(b(x1)))) -> x1 c(c(C(C(x1)))) -> x1 C(C(c(c(x1)))) -> x1 Q is empty. ---------------------------------------- (1) QTRS Reverse (EQUIVALENT) We applied the QTRS Reverse Processor [REVERSE]. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: b(b(a(a(x1)))) -> C(C(x1)) c(c(b(b(x1)))) -> A(A(x1)) a(a(c(c(x1)))) -> B(B(x1)) C(C(A(A(x1)))) -> b(b(x1)) B(B(C(C(x1)))) -> a(a(x1)) A(A(B(B(x1)))) -> c(c(x1)) a(a(a(a(a(a(a(a(a(a(x1)))))))))) -> A(A(A(A(A(A(x1)))))) A(A(A(A(A(A(A(A(x1)))))))) -> a(a(a(a(a(a(a(a(x1)))))))) b(b(b(b(b(b(b(b(b(b(x1)))))))))) -> B(B(B(B(B(B(x1)))))) B(B(B(B(B(B(B(B(x1)))))))) -> b(b(b(b(b(b(b(b(x1)))))))) c(c(c(c(c(c(c(c(c(c(x1)))))))))) -> C(C(C(C(C(C(x1)))))) C(C(C(C(C(C(C(C(x1)))))))) -> c(c(c(c(c(c(c(c(x1)))))))) a(a(a(a(a(a(a(a(B(B(x1)))))))))) -> A(A(A(A(A(A(c(c(x1)))))))) b(b(A(A(A(A(A(A(x1)))))))) -> C(C(a(a(a(a(a(a(a(a(x1)))))))))) b(b(b(b(b(b(b(b(C(C(x1)))))))))) -> B(B(B(B(B(B(a(a(x1)))))))) c(c(B(B(B(B(B(B(x1)))))))) -> A(A(b(b(b(b(b(b(b(b(x1)))))))))) c(c(c(c(c(c(c(c(A(A(x1)))))))))) -> C(C(C(C(C(C(b(b(x1)))))))) a(a(C(C(C(C(C(C(x1)))))))) -> B(B(c(c(c(c(c(c(c(c(x1)))))))))) A(A(a(a(x1)))) -> x1 a(a(A(A(x1)))) -> x1 B(B(b(b(x1)))) -> x1 b(b(B(B(x1)))) -> x1 C(C(c(c(x1)))) -> x1 c(c(C(C(x1)))) -> x1 Q is empty. ---------------------------------------- (3) 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: b(b(a(a(x1)))) -> C(C(x1)) c(c(b(b(x1)))) -> A(A(x1)) a(a(c(c(x1)))) -> B(B(x1)) C(C(A(A(x1)))) -> b(b(x1)) B(B(C(C(x1)))) -> a(a(x1)) A(A(B(B(x1)))) -> c(c(x1)) a(a(a(a(a(a(a(a(a(a(x1)))))))))) -> A(A(A(A(A(A(x1)))))) A(A(A(A(A(A(A(A(x1)))))))) -> a(a(a(a(a(a(a(a(x1)))))))) b(b(b(b(b(b(b(b(b(b(x1)))))))))) -> B(B(B(B(B(B(x1)))))) B(B(B(B(B(B(B(B(x1)))))))) -> b(b(b(b(b(b(b(b(x1)))))))) c(c(c(c(c(c(c(c(c(c(x1)))))))))) -> C(C(C(C(C(C(x1)))))) C(C(C(C(C(C(C(C(x1)))))))) -> c(c(c(c(c(c(c(c(x1)))))))) A(A(a(a(x1)))) -> x1 a(a(A(A(x1)))) -> x1 B(B(b(b(x1)))) -> x1 b(b(B(B(x1)))) -> x1 C(C(c(c(x1)))) -> x1 c(c(C(C(x1)))) -> x1 ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(a(a(a(a(a(a(a(B(B(x1)))))))))) -> A(A(A(A(A(A(c(c(x1)))))))) b(b(A(A(A(A(A(A(x1)))))))) -> C(C(a(a(a(a(a(a(a(a(x1)))))))))) b(b(b(b(b(b(b(b(C(C(x1)))))))))) -> B(B(B(B(B(B(a(a(x1)))))))) c(c(B(B(B(B(B(B(x1)))))))) -> A(A(b(b(b(b(b(b(b(b(x1)))))))))) c(c(c(c(c(c(c(c(A(A(x1)))))))))) -> C(C(C(C(C(C(b(b(x1)))))))) a(a(C(C(C(C(C(C(x1)))))))) -> B(B(c(c(c(c(c(c(c(c(x1)))))))))) Q is empty. ---------------------------------------- (5) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a(a(a(a(a(a(a(a(B(B(x1)))))))))) -> A(A(A(A(A(A(c(c(x1)))))))) b(b(A(A(A(A(A(A(x1)))))))) -> C(C(a(a(a(a(a(a(a(a(x1)))))))))) b(b(b(b(b(b(b(b(C(C(x1)))))))))) -> B(B(B(B(B(B(a(a(x1)))))))) c(c(B(B(B(B(B(B(x1)))))))) -> A(A(b(b(b(b(b(b(b(b(x1)))))))))) c(c(c(c(c(c(c(c(A(A(x1)))))))))) -> C(C(C(C(C(C(b(b(x1)))))))) a(a(C(C(C(C(C(C(x1)))))))) -> B(B(c(c(c(c(c(c(c(c(x1)))))))))) The set Q consists of the following terms: a(a(a(a(a(a(a(a(B(B(x0)))))))))) b(b(A(A(A(A(A(A(x0)))))))) b(b(b(b(b(b(b(b(C(C(x0)))))))))) c(c(B(B(B(B(B(B(x0)))))))) c(c(c(c(c(c(c(c(A(A(x0)))))))))) a(a(C(C(C(C(C(C(x0)))))))) ---------------------------------------- (7) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: A^1(a(a(a(a(a(a(a(B(B(x1)))))))))) -> C^1(c(x1)) A^1(a(a(a(a(a(a(a(B(B(x1)))))))))) -> C^1(x1) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(a(a(a(a(x1)))))))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(a(a(a(x1))))))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(a(a(x1)))))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(a(x1))))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(x1)))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(x1))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(x1)) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(x1) B^1(b(b(b(b(b(b(b(C(C(x1)))))))))) -> A^1(a(x1)) B^1(b(b(b(b(b(b(b(C(C(x1)))))))))) -> A^1(x1) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(b(b(b(b(x1)))))))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(b(b(b(x1))))))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(b(b(x1)))))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(b(x1))))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(x1)))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(x1))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(x1)) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(x1) C^1(c(c(c(c(c(c(c(A(A(x1)))))))))) -> B^1(b(x1)) C^1(c(c(c(c(c(c(c(A(A(x1)))))))))) -> B^1(x1) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(c(c(c(c(x1)))))))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(c(c(c(x1))))))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(c(c(x1)))))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(c(x1))))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(x1)))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(x1))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(x1)) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(x1) The TRS R consists of the following rules: a(a(a(a(a(a(a(a(B(B(x1)))))))))) -> A(A(A(A(A(A(c(c(x1)))))))) b(b(A(A(A(A(A(A(x1)))))))) -> C(C(a(a(a(a(a(a(a(a(x1)))))))))) b(b(b(b(b(b(b(b(C(C(x1)))))))))) -> B(B(B(B(B(B(a(a(x1)))))))) c(c(B(B(B(B(B(B(x1)))))))) -> A(A(b(b(b(b(b(b(b(b(x1)))))))))) c(c(c(c(c(c(c(c(A(A(x1)))))))))) -> C(C(C(C(C(C(b(b(x1)))))))) a(a(C(C(C(C(C(C(x1)))))))) -> B(B(c(c(c(c(c(c(c(c(x1)))))))))) The set Q consists of the following terms: a(a(a(a(a(a(a(a(B(B(x0)))))))))) b(b(A(A(A(A(A(A(x0)))))))) b(b(b(b(b(b(b(b(C(C(x0)))))))))) c(c(B(B(B(B(B(B(x0)))))))) c(c(c(c(c(c(c(c(A(A(x0)))))))))) a(a(C(C(C(C(C(C(x0)))))))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) 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: A^1(a(a(a(a(a(a(a(B(B(x1)))))))))) -> C^1(c(x1)) A^1(a(a(a(a(a(a(a(B(B(x1)))))))))) -> C^1(x1) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(a(a(a(a(x1)))))))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(a(a(a(x1))))))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(a(a(x1)))))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(a(x1))))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(a(x1)))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(a(x1))) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(a(x1)) B^1(b(A(A(A(A(A(A(x1)))))))) -> A^1(x1) B^1(b(b(b(b(b(b(b(C(C(x1)))))))))) -> A^1(a(x1)) B^1(b(b(b(b(b(b(b(C(C(x1)))))))))) -> A^1(x1) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(b(b(b(b(x1)))))))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(b(b(b(x1))))))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(b(b(x1)))))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(b(x1))))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(b(x1)))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(b(x1))) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(b(x1)) C^1(c(B(B(B(B(B(B(x1)))))))) -> B^1(x1) C^1(c(c(c(c(c(c(c(A(A(x1)))))))))) -> B^1(b(x1)) C^1(c(c(c(c(c(c(c(A(A(x1)))))))))) -> B^1(x1) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(c(c(c(c(x1)))))))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(c(c(c(x1))))))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(c(c(x1)))))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(c(x1))))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(c(x1)))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(c(x1))) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(c(x1)) A^1(a(C(C(C(C(C(C(x1)))))))) -> C^1(x1) Used ordering: Polynomial interpretation [POLO]: POL(A(x_1)) = 3 + x_1 POL(A^1(x_1)) = 3 + 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 ---------------------------------------- (10) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: a(a(a(a(a(a(a(a(B(B(x1)))))))))) -> A(A(A(A(A(A(c(c(x1)))))))) b(b(A(A(A(A(A(A(x1)))))))) -> C(C(a(a(a(a(a(a(a(a(x1)))))))))) b(b(b(b(b(b(b(b(C(C(x1)))))))))) -> B(B(B(B(B(B(a(a(x1)))))))) c(c(B(B(B(B(B(B(x1)))))))) -> A(A(b(b(b(b(b(b(b(b(x1)))))))))) c(c(c(c(c(c(c(c(A(A(x1)))))))))) -> C(C(C(C(C(C(b(b(x1)))))))) a(a(C(C(C(C(C(C(x1)))))))) -> B(B(c(c(c(c(c(c(c(c(x1)))))))))) The set Q consists of the following terms: a(a(a(a(a(a(a(a(B(B(x0)))))))))) b(b(A(A(A(A(A(A(x0)))))))) b(b(b(b(b(b(b(b(C(C(x0)))))))))) c(c(B(B(B(B(B(B(x0)))))))) c(c(c(c(c(c(c(c(A(A(x0)))))))))) a(a(C(C(C(C(C(C(x0)))))))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (12) YES