/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 128 ms] (2) QTRS (3) Overlay + Local Confluence [EQUIVALENT, 27 ms] (4) QTRS (5) DependencyPairsProof [EQUIVALENT, 78 ms] (6) QDP (7) MRRProof [EQUIVALENT, 673 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(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) 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(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)))))))) 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 ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: 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)))))))))) 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(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)))))))))) The set Q consists of the following terms: B(B(a(a(a(a(a(a(a(a(x0)))))))))) A(A(A(A(A(A(b(b(x0)))))))) C(C(b(b(b(b(b(b(b(b(x0)))))))))) B(B(B(B(B(B(c(c(x0)))))))) A(A(c(c(c(c(c(c(c(c(x0)))))))))) C(C(C(C(C(C(a(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(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(A(A(x1)))))) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(A(x1))))) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(x1)))) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(x1))) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(x1)) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(x1) A^1(A(A(A(A(A(b(b(x1)))))))) -> C^1(C(x1)) A^1(A(A(A(A(A(b(b(x1)))))))) -> C^1(x1) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(B(B(x1)))))) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(B(x1))))) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(x1)))) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(x1))) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(x1)) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(x1) B^1(B(B(B(B(B(c(c(x1)))))))) -> A^1(A(x1)) B^1(B(B(B(B(B(c(c(x1)))))))) -> A^1(x1) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(C(C(x1)))))) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(C(x1))))) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(x1)))) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(x1))) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(x1)) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(x1) C^1(C(C(C(C(C(a(a(x1)))))))) -> B^1(B(x1)) C^1(C(C(C(C(C(a(a(x1)))))))) -> B^1(x1) The TRS R consists of the following rules: 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)))))))))) The set Q consists of the following terms: B(B(a(a(a(a(a(a(a(a(x0)))))))))) A(A(A(A(A(A(b(b(x0)))))))) C(C(b(b(b(b(b(b(b(b(x0)))))))))) B(B(B(B(B(B(c(c(x0)))))))) A(A(c(c(c(c(c(c(c(c(x0)))))))))) C(C(C(C(C(C(a(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(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(A(A(x1)))))) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(A(x1))))) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(A(x1)))) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(A(x1))) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(A(x1)) B^1(B(a(a(a(a(a(a(a(a(x1)))))))))) -> A^1(x1) A^1(A(A(A(A(A(b(b(x1)))))))) -> C^1(C(x1)) A^1(A(A(A(A(A(b(b(x1)))))))) -> C^1(x1) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(B(B(x1)))))) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(B(x1))))) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(B(x1)))) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(B(x1))) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(B(x1)) C^1(C(b(b(b(b(b(b(b(b(x1)))))))))) -> B^1(x1) B^1(B(B(B(B(B(c(c(x1)))))))) -> A^1(A(x1)) B^1(B(B(B(B(B(c(c(x1)))))))) -> A^1(x1) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(C(C(x1)))))) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(C(x1))))) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(C(x1)))) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(C(x1))) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(C(x1)) A^1(A(c(c(c(c(c(c(c(c(x1)))))))))) -> C^1(x1) C^1(C(C(C(C(C(a(a(x1)))))))) -> B^1(B(x1)) C^1(C(C(C(C(C(a(a(x1)))))))) -> B^1(x1) Used ordering: Polynomial interpretation [POLO]: POL(A(x_1)) = 3 + x_1 POL(A^1(x_1)) = 2 + 2*x_1 POL(B(x_1)) = 3 + x_1 POL(B^1(x_1)) = 2 + 2*x_1 POL(C(x_1)) = 3 + x_1 POL(C^1(x_1)) = 2 + 2*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(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)))))))))) The set Q consists of the following terms: B(B(a(a(a(a(a(a(a(a(x0)))))))))) A(A(A(A(A(A(b(b(x0)))))))) C(C(b(b(b(b(b(b(b(b(x0)))))))))) B(B(B(B(B(B(c(c(x0)))))))) A(A(c(c(c(c(c(c(c(c(x0)))))))))) C(C(C(C(C(C(a(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