1012.14/258.06 YES 1012.95/258.22 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1012.95/258.22 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1012.95/258.22 1012.95/258.22 1012.95/258.22 Termination w.r.t. Q of the given QTRS could be proven: 1012.95/258.22 1012.95/258.22 (0) QTRS 1012.95/258.22 (1) FlatCCProof [EQUIVALENT, 0 ms] 1012.95/258.22 (2) QTRS 1012.95/258.22 (3) RootLabelingProof [EQUIVALENT, 0 ms] 1012.95/258.22 (4) QTRS 1012.95/258.22 (5) DependencyPairsProof [EQUIVALENT, 32 ms] 1012.95/258.22 (6) QDP 1012.95/258.22 (7) QDPOrderProof [EQUIVALENT, 161 ms] 1012.95/258.22 (8) QDP 1012.95/258.22 (9) DependencyGraphProof [EQUIVALENT, 0 ms] 1012.95/258.22 (10) AND 1012.95/258.22 (11) QDP 1012.95/258.22 (12) QDPOrderProof [EQUIVALENT, 9000 ms] 1012.95/258.22 (13) QDP 1012.95/258.22 (14) QDPOrderProof [EQUIVALENT, 549 ms] 1012.95/258.22 (15) QDP 1012.95/258.22 (16) DependencyGraphProof [EQUIVALENT, 0 ms] 1012.95/258.22 (17) QDP 1012.95/258.22 (18) QDPOrderProof [EQUIVALENT, 2790 ms] 1012.95/258.22 (19) QDP 1012.95/258.22 (20) QDPOrderProof [EQUIVALENT, 24.1 s] 1012.95/258.22 (21) QDP 1012.95/258.22 (22) PisEmptyProof [EQUIVALENT, 0 ms] 1012.95/258.22 (23) YES 1012.95/258.22 (24) QDP 1012.95/258.22 (25) QDPOrderProof [EQUIVALENT, 3257 ms] 1012.95/258.22 (26) QDP 1012.95/258.22 (27) QDPOrderProof [EQUIVALENT, 9160 ms] 1012.95/258.22 (28) QDP 1012.95/258.22 (29) DependencyGraphProof [EQUIVALENT, 0 ms] 1012.95/258.22 (30) TRUE 1012.95/258.22 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (0) 1012.95/258.22 Obligation: 1012.95/258.22 Q restricted rewrite system: 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b(a(a(b(x1)))) -> a(b(a(b(x1)))) 1012.95/258.22 a(a(a(a(x1)))) -> b(b(b(b(x1)))) 1012.95/258.22 b(b(a(b(x1)))) -> b(b(a(a(x1)))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (1) FlatCCProof (EQUIVALENT) 1012.95/258.22 We used flat context closure [ROOTLAB] 1012.95/258.22 As Q is empty the flat context closure was sound AND complete. 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (2) 1012.95/258.22 Obligation: 1012.95/258.22 Q restricted rewrite system: 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b(b(a(b(x1)))) -> b(b(a(a(x1)))) 1012.95/258.22 b(b(a(a(b(x1))))) -> b(a(b(a(b(x1))))) 1012.95/258.22 a(b(a(a(b(x1))))) -> a(a(b(a(b(x1))))) 1012.95/258.22 b(a(a(a(a(x1))))) -> b(b(b(b(b(x1))))) 1012.95/258.22 a(a(a(a(a(x1))))) -> a(b(b(b(b(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (3) RootLabelingProof (EQUIVALENT) 1012.95/258.22 We used plain root labeling [ROOTLAB] with the following heuristic: 1012.95/258.22 LabelAll: All function symbols get labeled 1012.95/258.22 1012.95/258.22 As Q is empty the root labeling was sound AND complete. 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (4) 1012.95/258.22 Obligation: 1012.95/258.22 Q restricted rewrite system: 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (5) DependencyPairsProof (EQUIVALENT) 1012.95/258.22 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (6) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> A_{A_1}(a_{b_1}(x1)) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(a_{a_1}(x1)) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> A_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{b_1}(x1))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> A_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(x1))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> A_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{b_1}(x1))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> A_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(x1))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(x1))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(x1)) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(x1) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{a_1}(x1))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{a_1}(x1)) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{A_1}(x1) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(x1))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(x1)) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(x1) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{a_1}(x1))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{a_1}(x1)) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{A_1}(x1) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (7) QDPOrderProof (EQUIVALENT) 1012.95/258.22 We use the reduction pair processor [LPAR04,JAR06]. 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following pairs can be oriented strictly and are deleted. 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{b_1}(x1))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> A_{A_1}(a_{b_1}(x1)) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> A_{B_1}(x1) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{A_1}(a_{a_1}(a_{a_1}(x1))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(a_{a_1}(x1)) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> A_{A_1}(x1) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> A_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{b_1}(x1))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> A_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(x1))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> A_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{b_1}(x1))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> A_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(x1))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(x1))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(x1)) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(x1) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{a_1}(x1))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{a_1}(x1)) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{A_1}(x1) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(x1))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(x1)) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(x1) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{a_1}(x1))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{a_1}(x1)) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{A_1}(x1) 1012.95/258.22 The remaining pairs can at least be oriented weakly. 1012.95/258.22 Used ordering: Polynomial interpretation [POLO]: 1012.95/258.22 1012.95/258.22 POL(A_{A_1}(x_1)) = x_1 1012.95/258.22 POL(A_{B_1}(x_1)) = x_1 1012.95/258.22 POL(B_{A_1}(x_1)) = 1 + x_1 1012.95/258.22 POL(B_{B_1}(x_1)) = 1 + x_1 1012.95/258.22 POL(a_{a_1}(x_1)) = 1 + x_1 1012.95/258.22 POL(a_{b_1}(x_1)) = 1 + x_1 1012.95/258.22 POL(b_{a_1}(x_1)) = 1 + x_1 1012.95/258.22 POL(b_{b_1}(x_1)) = 1 + x_1 1012.95/258.22 1012.95/258.22 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 1012.95/258.22 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (8) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1)))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1)))) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (9) DependencyGraphProof (EQUIVALENT) 1012.95/258.22 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (10) 1012.95/258.22 Complex Obligation (AND) 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (11) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (12) QDPOrderProof (EQUIVALENT) 1012.95/258.22 We use the reduction pair processor [LPAR04,JAR06]. 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following pairs can be oriented strictly and are deleted. 1012.95/258.22 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 The remaining pairs can at least be oriented weakly. 1012.95/258.22 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(B_{B_1}(x_1)) = [[0A]] + [[0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{a_1}(x_1)) = [[0A], [-I], [-I]] + [[-I, 0A, 0A], [0A, -I, 0A], [-I, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{b_1}(x_1)) = [[-I], [-I], [-I]] + [[1A, 0A, 0A], [0A, -I, 0A], [0A, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{a_1}(x_1)) = [[0A], [-I], [0A]] + [[-I, 0A, 0A], [0A, 0A, 1A], [-I, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{b_1}(x_1)) = [[0A], [0A], [0A]] + [[0A, 0A, 0A], [0A, 0A, -I], [0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(B_{A_1}(x_1)) = [[1A]] + [[-I, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 1012.95/258.22 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (13) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (14) QDPOrderProof (EQUIVALENT) 1012.95/258.22 We use the reduction pair processor [LPAR04,JAR06]. 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following pairs can be oriented strictly and are deleted. 1012.95/258.22 1012.95/258.22 B_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> B_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 The remaining pairs can at least be oriented weakly. 1012.95/258.22 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(B_{B_1}(x_1)) = [[0A]] + [[-I, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{a_1}(x_1)) = [[0A], [0A], [0A]] + [[0A, -I, 0A], [0A, -I, -I], [0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{b_1}(x_1)) = [[0A], [-I], [0A]] + [[-I, -I, 0A], [1A, 0A, 0A], [0A, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{a_1}(x_1)) = [[0A], [0A], [0A]] + [[0A, -I, 0A], [1A, 0A, 0A], [0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{b_1}(x_1)) = [[0A], [0A], [0A]] + [[0A, 0A, 0A], [0A, 0A, 0A], [0A, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(B_{A_1}(x_1)) = [[0A]] + [[0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 1012.95/258.22 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (15) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> B_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (16) DependencyGraphProof (EQUIVALENT) 1012.95/258.22 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (17) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (18) QDPOrderProof (EQUIVALENT) 1012.95/258.22 We use the reduction pair processor [LPAR04,JAR06]. 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following pairs can be oriented strictly and are deleted. 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 The remaining pairs can at least be oriented weakly. 1012.95/258.22 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(B_{B_1}(x_1)) = [[0A]] + [[-I, 0A, -I]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{a_1}(x_1)) = [[0A], [0A], [-I]] + [[-I, 0A, 0A], [-I, 0A, -I], [0A, -I, -I]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{b_1}(x_1)) = [[0A], [0A], [1A]] + [[-I, -I, 0A], [0A, 0A, 1A], [0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{b_1}(x_1)) = [[0A], [0A], [0A]] + [[0A, -I, -I], [1A, -I, 0A], [1A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{a_1}(x_1)) = [[0A], [0A], [1A]] + [[1A, -I, 0A], [0A, -I, -I], [0A, 0A, -I]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 1012.95/258.22 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (19) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (20) QDPOrderProof (EQUIVALENT) 1012.95/258.22 We use the reduction pair processor [LPAR04,JAR06]. 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following pairs can be oriented strictly and are deleted. 1012.95/258.22 1012.95/258.22 B_{B_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> B_{B_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 The remaining pairs can at least be oriented weakly. 1012.95/258.22 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(B_{B_1}(x_1)) = [[-I]] + [[0A, -I, 0A, -I, -I]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{a_1}(x_1)) = [[-I], [-I], [0A], [0A], [0A]] + [[0A, -I, -I, 0A, -I], [0A, 0A, 0A, -I, 0A], [-I, 0A, -I, -I, -I], [0A, 0A, 0A, -I, 0A], [0A, 0A, 0A, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{b_1}(x_1)) = [[0A], [-I], [-I], [1A], [-I]] + [[-I, 0A, 0A, 0A, 0A], [-I, 0A, 0A, 0A, -I], [-I, 0A, 0A, 0A, 0A], [0A, 1A, 0A, 0A, 0A], [-I, 0A, -I, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{a_1}(x_1)) = [[0A], [0A], [0A], [0A], [-I]] + [[0A, 0A, -I, -I, -I], [-I, -I, -I, -I, 0A], [0A, 1A, 0A, 0A, 0A], [-I, -I, -I, -I, 0A], [-I, 0A, 0A, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{b_1}(x_1)) = [[0A], [0A], [0A], [0A], [0A]] + [[0A, 0A, 1A, 0A, 0A], [-I, -I, 0A, -I, -I], [-I, -I, 0A, -I, -I], [0A, 0A, 1A, 0A, 0A], [0A, 0A, 1A, 0A, -I]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 1012.95/258.22 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (21) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 P is empty. 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (22) PisEmptyProof (EQUIVALENT) 1012.95/258.22 The TRS P is empty. Hence, there is no (P,Q,R) chain. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (23) 1012.95/258.22 YES 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (24) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (25) QDPOrderProof (EQUIVALENT) 1012.95/258.22 We use the reduction pair processor [LPAR04,JAR06]. 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following pairs can be oriented strictly and are deleted. 1012.95/258.22 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 The remaining pairs can at least be oriented weakly. 1012.95/258.22 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(A_{A_1}(x_1)) = [[0A]] + [[0A, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{a_1}(x_1)) = [[-I], [0A], [0A]] + [[0A, -I, 0A], [1A, 0A, 0A], [0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{b_1}(x_1)) = [[-I], [0A], [-I]] + [[0A, 0A, 0A], [0A, 1A, -I], [0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(A_{B_1}(x_1)) = [[0A]] + [[0A, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{b_1}(x_1)) = [[-I], [-I], [0A]] + [[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{a_1}(x_1)) = [[-I], [-I], [-I]] + [[0A, -I, 0A], [0A, -I, 0A], [0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (26) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (27) QDPOrderProof (EQUIVALENT) 1012.95/258.22 We use the reduction pair processor [LPAR04,JAR06]. 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following pairs can be oriented strictly and are deleted. 1012.95/258.22 1012.95/258.22 A_{A_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> A_{B_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 The remaining pairs can at least be oriented weakly. 1012.95/258.22 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(A_{A_1}(x_1)) = [[0A]] + [[0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{a_1}(x_1)) = [[0A], [0A], [-I]] + [[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, 1A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(a_{b_1}(x_1)) = [[0A], [-I], [-I]] + [[0A, 1A, 0A], [-I, -I, 0A], [-I, -I, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(A_{B_1}(x_1)) = [[1A]] + [[0A, 0A, 0A]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{b_1}(x_1)) = [[-I], [0A], [0A]] + [[0A, -I, -I], [1A, 0A, 0A], [1A, 0A, -I]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 <<< 1012.95/258.22 POL(b_{a_1}(x_1)) = [[0A], [-I], [-I]] + [[0A, 0A, -I], [-I, 0A, 0A], [-I, 0A, -I]] * x_1 1012.95/258.22 >>> 1012.95/258.22 1012.95/258.22 1012.95/258.22 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (28) 1012.95/258.22 Obligation: 1012.95/258.22 Q DP problem: 1012.95/258.22 The TRS P consists of the following rules: 1012.95/258.22 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 A_{B_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> A_{A_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 The TRS R consists of the following rules: 1012.95/258.22 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1)))) -> b_{b_1}(b_{a_1}(a_{a_1}(a_{a_1}(x1)))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> b_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{b_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{b_1}(b_{a_1}(a_{a_1}(a_{b_1}(b_{a_1}(x1))))) -> a_{a_1}(a_{b_1}(b_{a_1}(a_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 b_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{b_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(x1))))) 1012.95/258.22 a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(a_{a_1}(x1))))) -> a_{b_1}(b_{b_1}(b_{b_1}(b_{b_1}(b_{a_1}(x1))))) 1012.95/258.22 1012.95/258.22 Q is empty. 1012.95/258.22 We have to consider all minimal (P,Q,R)-chains. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (29) DependencyGraphProof (EQUIVALENT) 1012.95/258.22 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 1012.95/258.22 ---------------------------------------- 1012.95/258.22 1012.95/258.22 (30) 1012.95/258.22 TRUE 1013.13/258.30 EOF