17.16/5.17 YES 17.16/5.26 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 17.16/5.26 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 17.16/5.26 17.16/5.26 17.16/5.26 Termination w.r.t. Q of the given QTRS could be proven: 17.16/5.26 17.16/5.26 (0) QTRS 17.16/5.26 (1) DependencyPairsProof [EQUIVALENT, 16 ms] 17.16/5.26 (2) QDP 17.16/5.26 (3) DependencyGraphProof [EQUIVALENT, 2 ms] 17.16/5.26 (4) QDP 17.16/5.26 (5) QDPOrderProof [EQUIVALENT, 22 ms] 17.16/5.26 (6) QDP 17.16/5.26 (7) QDPOrderProof [EQUIVALENT, 212 ms] 17.16/5.26 (8) QDP 17.16/5.26 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 17.16/5.26 (10) TRUE 17.16/5.26 17.16/5.26 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (0) 17.16/5.26 Obligation: 17.16/5.26 Q restricted rewrite system: 17.16/5.26 The TRS R consists of the following rules: 17.16/5.26 17.16/5.26 a(a(x1)) -> c(b(a(b(a(x1))))) 17.16/5.26 b(a(b(x1))) -> b(x1) 17.16/5.26 a(a(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(c(x1)) -> a(b(c(b(a(x1))))) 17.16/5.26 a(c(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(a(c(x1))) -> a(a(c(x1))) 17.16/5.26 17.16/5.26 Q is empty. 17.16/5.26 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (1) DependencyPairsProof (EQUIVALENT) 17.16/5.26 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (2) 17.16/5.26 Obligation: 17.16/5.26 Q DP problem: 17.16/5.26 The TRS P consists of the following rules: 17.16/5.26 17.16/5.26 A(a(x1)) -> C(b(a(b(a(x1))))) 17.16/5.26 A(a(x1)) -> B(a(b(a(x1)))) 17.16/5.26 A(a(x1)) -> A(b(a(x1))) 17.16/5.26 A(a(x1)) -> B(a(x1)) 17.16/5.26 A(a(a(x1))) -> C(c(a(x1))) 17.16/5.26 A(a(a(x1))) -> C(a(x1)) 17.16/5.26 C(c(x1)) -> A(b(c(b(a(x1))))) 17.16/5.26 C(c(x1)) -> B(c(b(a(x1)))) 17.16/5.26 C(c(x1)) -> C(b(a(x1))) 17.16/5.26 C(c(x1)) -> B(a(x1)) 17.16/5.26 C(c(x1)) -> A(x1) 17.16/5.26 A(c(a(x1))) -> C(c(a(x1))) 17.16/5.26 C(a(c(x1))) -> A(a(c(x1))) 17.16/5.26 17.16/5.26 The TRS R consists of the following rules: 17.16/5.26 17.16/5.26 a(a(x1)) -> c(b(a(b(a(x1))))) 17.16/5.26 b(a(b(x1))) -> b(x1) 17.16/5.26 a(a(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(c(x1)) -> a(b(c(b(a(x1))))) 17.16/5.26 a(c(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(a(c(x1))) -> a(a(c(x1))) 17.16/5.26 17.16/5.26 Q is empty. 17.16/5.26 We have to consider all minimal (P,Q,R)-chains. 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (3) DependencyGraphProof (EQUIVALENT) 17.16/5.26 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (4) 17.16/5.26 Obligation: 17.16/5.26 Q DP problem: 17.16/5.26 The TRS P consists of the following rules: 17.16/5.26 17.16/5.26 C(c(x1)) -> A(b(c(b(a(x1))))) 17.16/5.26 A(a(x1)) -> C(b(a(b(a(x1))))) 17.16/5.26 C(c(x1)) -> C(b(a(x1))) 17.16/5.26 C(c(x1)) -> A(x1) 17.16/5.26 A(a(x1)) -> A(b(a(x1))) 17.16/5.26 A(a(a(x1))) -> C(c(a(x1))) 17.16/5.26 C(a(c(x1))) -> A(a(c(x1))) 17.16/5.26 A(a(a(x1))) -> C(a(x1)) 17.16/5.26 A(c(a(x1))) -> C(c(a(x1))) 17.16/5.26 17.16/5.26 The TRS R consists of the following rules: 17.16/5.26 17.16/5.26 a(a(x1)) -> c(b(a(b(a(x1))))) 17.16/5.26 b(a(b(x1))) -> b(x1) 17.16/5.26 a(a(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(c(x1)) -> a(b(c(b(a(x1))))) 17.16/5.26 a(c(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(a(c(x1))) -> a(a(c(x1))) 17.16/5.26 17.16/5.26 Q is empty. 17.16/5.26 We have to consider all minimal (P,Q,R)-chains. 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (5) QDPOrderProof (EQUIVALENT) 17.16/5.26 We use the reduction pair processor [LPAR04,JAR06]. 17.16/5.26 17.16/5.26 17.16/5.26 The following pairs can be oriented strictly and are deleted. 17.16/5.26 17.16/5.26 C(c(x1)) -> A(b(c(b(a(x1))))) 17.16/5.26 A(a(x1)) -> C(b(a(b(a(x1))))) 17.16/5.26 C(c(x1)) -> C(b(a(x1))) 17.16/5.26 C(c(x1)) -> A(x1) 17.16/5.26 A(a(x1)) -> A(b(a(x1))) 17.16/5.26 A(a(a(x1))) -> C(a(x1)) 17.16/5.26 The remaining pairs can at least be oriented weakly. 17.16/5.26 Used ordering: Polynomial interpretation [POLO]: 17.16/5.26 17.16/5.26 POL(A(x_1)) = 1 + x_1 17.16/5.26 POL(C(x_1)) = 1 + x_1 17.16/5.26 POL(a(x_1)) = 1 + x_1 17.16/5.26 POL(b(x_1)) = 0 17.16/5.26 POL(c(x_1)) = 1 + x_1 17.16/5.26 17.16/5.26 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 17.16/5.26 17.16/5.26 c(c(x1)) -> a(b(c(b(a(x1))))) 17.16/5.26 a(a(x1)) -> c(b(a(b(a(x1))))) 17.16/5.26 c(a(c(x1))) -> a(a(c(x1))) 17.16/5.26 a(a(a(x1))) -> c(c(a(x1))) 17.16/5.26 a(c(a(x1))) -> c(c(a(x1))) 17.16/5.26 b(a(b(x1))) -> b(x1) 17.16/5.26 17.16/5.26 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (6) 17.16/5.26 Obligation: 17.16/5.26 Q DP problem: 17.16/5.26 The TRS P consists of the following rules: 17.16/5.26 17.16/5.26 A(a(a(x1))) -> C(c(a(x1))) 17.16/5.26 C(a(c(x1))) -> A(a(c(x1))) 17.16/5.26 A(c(a(x1))) -> C(c(a(x1))) 17.16/5.26 17.16/5.26 The TRS R consists of the following rules: 17.16/5.26 17.16/5.26 a(a(x1)) -> c(b(a(b(a(x1))))) 17.16/5.26 b(a(b(x1))) -> b(x1) 17.16/5.26 a(a(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(c(x1)) -> a(b(c(b(a(x1))))) 17.16/5.26 a(c(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(a(c(x1))) -> a(a(c(x1))) 17.16/5.26 17.16/5.26 Q is empty. 17.16/5.26 We have to consider all minimal (P,Q,R)-chains. 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (7) QDPOrderProof (EQUIVALENT) 17.16/5.26 We use the reduction pair processor [LPAR04,JAR06]. 17.16/5.26 17.16/5.26 17.16/5.26 The following pairs can be oriented strictly and are deleted. 17.16/5.26 17.16/5.26 A(a(a(x1))) -> C(c(a(x1))) 17.16/5.26 A(c(a(x1))) -> C(c(a(x1))) 17.16/5.26 The remaining pairs can at least be oriented weakly. 17.16/5.26 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 17.16/5.26 17.16/5.26 <<< 17.16/5.26 POL(A(x_1)) = [[0A]] + [[-I, 1A, -I]] * x_1 17.16/5.26 >>> 17.16/5.26 17.16/5.26 <<< 17.16/5.26 POL(a(x_1)) = [[-I], [-I], [0A]] + [[0A, 1A, 0A], [-I, 0A, 0A], [0A, 1A, 0A]] * x_1 17.16/5.26 >>> 17.16/5.26 17.16/5.26 <<< 17.16/5.26 POL(C(x_1)) = [[0A]] + [[-I, -I, 0A]] * x_1 17.16/5.26 >>> 17.16/5.26 17.16/5.26 <<< 17.16/5.26 POL(c(x_1)) = [[0A], [-I], [-I]] + [[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, -I]] * x_1 17.16/5.26 >>> 17.16/5.26 17.16/5.26 <<< 17.16/5.26 POL(b(x_1)) = [[0A], [-I], [0A]] + [[-I, 0A, -I], [-I, -I, -I], [-I, 0A, -I]] * x_1 17.16/5.26 >>> 17.16/5.26 17.16/5.26 17.16/5.26 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 17.16/5.26 17.16/5.26 c(c(x1)) -> a(b(c(b(a(x1))))) 17.16/5.26 a(a(x1)) -> c(b(a(b(a(x1))))) 17.16/5.26 c(a(c(x1))) -> a(a(c(x1))) 17.16/5.26 a(a(a(x1))) -> c(c(a(x1))) 17.16/5.26 a(c(a(x1))) -> c(c(a(x1))) 17.16/5.26 b(a(b(x1))) -> b(x1) 17.16/5.26 17.16/5.26 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (8) 17.16/5.26 Obligation: 17.16/5.26 Q DP problem: 17.16/5.26 The TRS P consists of the following rules: 17.16/5.26 17.16/5.26 C(a(c(x1))) -> A(a(c(x1))) 17.16/5.26 17.16/5.26 The TRS R consists of the following rules: 17.16/5.26 17.16/5.26 a(a(x1)) -> c(b(a(b(a(x1))))) 17.16/5.26 b(a(b(x1))) -> b(x1) 17.16/5.26 a(a(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(c(x1)) -> a(b(c(b(a(x1))))) 17.16/5.26 a(c(a(x1))) -> c(c(a(x1))) 17.16/5.26 c(a(c(x1))) -> a(a(c(x1))) 17.16/5.26 17.16/5.26 Q is empty. 17.16/5.26 We have to consider all minimal (P,Q,R)-chains. 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (9) DependencyGraphProof (EQUIVALENT) 17.16/5.26 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 17.16/5.26 ---------------------------------------- 17.16/5.26 17.16/5.26 (10) 17.16/5.26 TRUE 17.68/5.35 EOF