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