10.49/3.50 YES 11.23/3.68 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 11.23/3.68 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 11.23/3.68 11.23/3.68 11.23/3.68 Termination w.r.t. Q of the given QTRS could be proven: 11.23/3.68 11.23/3.68 (0) QTRS 11.23/3.68 (1) DependencyPairsProof [EQUIVALENT, 270 ms] 11.23/3.68 (2) QDP 11.23/3.68 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 11.23/3.68 (4) AND 11.23/3.68 (5) QDP 11.23/3.68 (6) QDPSizeChangeProof [EQUIVALENT, 4 ms] 11.23/3.68 (7) YES 11.23/3.68 (8) QDP 11.23/3.68 (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] 11.23/3.68 (10) YES 11.23/3.68 11.23/3.68 11.23/3.68 ---------------------------------------- 11.23/3.68 11.23/3.68 (0) 11.23/3.68 Obligation: 11.23/3.68 Q restricted rewrite system: 11.23/3.68 The TRS R consists of the following rules: 11.23/3.68 11.23/3.68 0(0(1(x1))) -> 0(2(3(0(1(x1))))) 11.23/3.68 0(0(1(x1))) -> 0(4(0(5(4(1(x1)))))) 11.23/3.68 0(0(1(x1))) -> 2(1(0(0(3(4(x1)))))) 11.23/3.68 0(0(1(x1))) -> 4(0(5(4(0(1(x1)))))) 11.23/3.68 0(1(0(x1))) -> 0(0(2(1(2(x1))))) 11.23/3.68 0(1(0(x1))) -> 1(0(0(5(4(x1))))) 11.23/3.68 0(1(0(x1))) -> 0(0(2(5(4(1(x1)))))) 11.23/3.68 0(1(1(x1))) -> 1(0(3(4(1(x1))))) 11.23/3.68 0(1(1(x1))) -> 5(0(3(4(1(1(x1)))))) 11.23/3.68 5(0(1(x1))) -> 0(5(4(1(x1)))) 11.23/3.68 5(0(1(x1))) -> 2(5(4(0(1(x1))))) 11.23/3.68 5(0(1(x1))) -> 5(0(2(1(2(x1))))) 11.23/3.68 5(0(1(x1))) -> 0(1(4(5(4(4(x1)))))) 11.23/3.68 5(0(1(x1))) -> 0(5(4(1(4(4(x1)))))) 11.23/3.68 5(0(1(x1))) -> 5(0(4(3(0(1(x1)))))) 11.23/3.68 5(1(0(x1))) -> 5(0(2(2(1(x1))))) 11.23/3.68 5(1(0(x1))) -> 5(0(5(4(1(x1))))) 11.23/3.68 5(1(0(x1))) -> 0(5(0(2(2(1(x1)))))) 11.23/3.68 5(1(0(x1))) -> 1(4(0(5(2(3(x1)))))) 11.23/3.68 5(1(0(x1))) -> 1(5(0(4(4(2(x1)))))) 11.23/3.68 5(1(0(x1))) -> 4(4(1(0(4(5(x1)))))) 11.23/3.68 5(1(1(x1))) -> 1(1(5(4(x1)))) 11.23/3.68 5(1(1(x1))) -> 5(4(1(1(x1)))) 11.23/3.68 5(1(1(x1))) -> 1(5(3(4(1(x1))))) 11.23/3.68 5(1(1(x1))) -> 1(1(4(5(4(4(x1)))))) 11.23/3.68 5(1(1(x1))) -> 3(5(2(3(1(1(x1)))))) 11.23/3.68 5(1(1(x1))) -> 4(1(2(1(5(4(x1)))))) 11.23/3.68 0(1(3(0(x1)))) -> 0(2(0(2(1(3(x1)))))) 11.23/3.68 0(1(5(0(x1)))) -> 0(0(5(4(1(5(x1)))))) 11.23/3.68 0(1(5(0(x1)))) -> 0(5(4(2(1(0(x1)))))) 11.23/3.68 0(3(0(1(x1)))) -> 0(0(4(1(3(0(x1)))))) 11.23/3.68 0(3(1(0(x1)))) -> 0(0(2(3(1(x1))))) 11.23/3.68 0(3(1(1(x1)))) -> 5(1(1(0(3(4(x1)))))) 11.23/3.68 5(0(1(0(x1)))) -> 5(0(0(4(1(3(x1)))))) 11.23/3.68 5(1(2(0(x1)))) -> 1(4(0(5(4(2(x1)))))) 11.23/3.68 5(1(2(0(x1)))) -> 5(0(4(2(2(1(x1)))))) 11.23/3.68 5(1(4(0(x1)))) -> 1(5(4(0(2(3(x1)))))) 11.23/3.68 5(1(4(0(x1)))) -> 4(5(2(1(3(0(x1)))))) 11.23/3.68 5(1(5(1(x1)))) -> 5(4(1(5(1(x1))))) 11.23/3.68 5(3(0(1(x1)))) -> 0(1(5(2(3(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 1(4(3(5(0(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 1(5(0(4(3(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 5(4(3(1(0(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 1(3(0(4(3(5(x1)))))) 11.23/3.68 5(3(1(1(x1)))) -> 1(1(5(3(3(4(x1)))))) 11.23/3.68 0(1(2(5(0(x1))))) -> 1(5(4(0(2(0(x1)))))) 11.23/3.68 0(1(4(2(0(x1))))) -> 1(0(4(2(3(0(x1)))))) 11.23/3.68 1(4(5(1(0(x1))))) -> 5(4(2(1(1(0(x1)))))) 11.23/3.68 5(0(1(4(0(x1))))) -> 1(4(5(4(0(0(x1)))))) 11.23/3.68 5(5(1(0(0(x1))))) -> 5(5(0(4(1(0(x1)))))) 11.23/3.68 11.23/3.68 Q is empty. 11.23/3.68 11.23/3.68 ---------------------------------------- 11.23/3.68 11.23/3.68 (1) DependencyPairsProof (EQUIVALENT) 11.23/3.68 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 11.23/3.68 ---------------------------------------- 11.23/3.68 11.23/3.68 (2) 11.23/3.68 Obligation: 11.23/3.68 Q DP problem: 11.23/3.68 The TRS P consists of the following rules: 11.23/3.68 11.23/3.68 0^1(0(1(x1))) -> 0^1(2(3(0(1(x1))))) 11.23/3.68 0^1(0(1(x1))) -> 0^1(4(0(5(4(1(x1)))))) 11.23/3.68 0^1(0(1(x1))) -> 0^1(5(4(1(x1)))) 11.23/3.68 0^1(0(1(x1))) -> 5^1(4(1(x1))) 11.23/3.68 0^1(0(1(x1))) -> 1^1(0(0(3(4(x1))))) 11.23/3.68 0^1(0(1(x1))) -> 0^1(0(3(4(x1)))) 11.23/3.68 0^1(0(1(x1))) -> 0^1(3(4(x1))) 11.23/3.68 0^1(0(1(x1))) -> 0^1(5(4(0(1(x1))))) 11.23/3.68 0^1(0(1(x1))) -> 5^1(4(0(1(x1)))) 11.23/3.68 0^1(1(0(x1))) -> 0^1(0(2(1(2(x1))))) 11.23/3.68 0^1(1(0(x1))) -> 0^1(2(1(2(x1)))) 11.23/3.68 0^1(1(0(x1))) -> 1^1(2(x1)) 11.23/3.68 0^1(1(0(x1))) -> 1^1(0(0(5(4(x1))))) 11.23/3.68 0^1(1(0(x1))) -> 0^1(0(5(4(x1)))) 11.23/3.68 0^1(1(0(x1))) -> 0^1(5(4(x1))) 11.23/3.68 0^1(1(0(x1))) -> 5^1(4(x1)) 11.23/3.68 0^1(1(0(x1))) -> 0^1(0(2(5(4(1(x1)))))) 11.23/3.68 0^1(1(0(x1))) -> 0^1(2(5(4(1(x1))))) 11.23/3.68 0^1(1(0(x1))) -> 5^1(4(1(x1))) 11.23/3.68 0^1(1(0(x1))) -> 1^1(x1) 11.23/3.68 0^1(1(1(x1))) -> 1^1(0(3(4(1(x1))))) 11.23/3.68 0^1(1(1(x1))) -> 0^1(3(4(1(x1)))) 11.23/3.68 0^1(1(1(x1))) -> 5^1(0(3(4(1(1(x1)))))) 11.23/3.68 0^1(1(1(x1))) -> 0^1(3(4(1(1(x1))))) 11.23/3.68 5^1(0(1(x1))) -> 0^1(5(4(1(x1)))) 11.23/3.68 5^1(0(1(x1))) -> 5^1(4(1(x1))) 11.23/3.68 5^1(0(1(x1))) -> 5^1(4(0(1(x1)))) 11.23/3.68 5^1(0(1(x1))) -> 5^1(0(2(1(2(x1))))) 11.23/3.68 5^1(0(1(x1))) -> 0^1(2(1(2(x1)))) 11.23/3.68 5^1(0(1(x1))) -> 1^1(2(x1)) 11.23/3.68 5^1(0(1(x1))) -> 0^1(1(4(5(4(4(x1)))))) 11.23/3.68 5^1(0(1(x1))) -> 1^1(4(5(4(4(x1))))) 11.23/3.68 5^1(0(1(x1))) -> 5^1(4(4(x1))) 11.23/3.68 5^1(0(1(x1))) -> 0^1(5(4(1(4(4(x1)))))) 11.23/3.68 5^1(0(1(x1))) -> 5^1(4(1(4(4(x1))))) 11.23/3.68 5^1(0(1(x1))) -> 1^1(4(4(x1))) 11.23/3.68 5^1(0(1(x1))) -> 5^1(0(4(3(0(1(x1)))))) 11.23/3.68 5^1(0(1(x1))) -> 0^1(4(3(0(1(x1))))) 11.23/3.68 5^1(1(0(x1))) -> 5^1(0(2(2(1(x1))))) 11.23/3.68 5^1(1(0(x1))) -> 0^1(2(2(1(x1)))) 11.23/3.68 5^1(1(0(x1))) -> 1^1(x1) 11.23/3.68 5^1(1(0(x1))) -> 5^1(0(5(4(1(x1))))) 11.23/3.68 5^1(1(0(x1))) -> 0^1(5(4(1(x1)))) 11.23/3.68 5^1(1(0(x1))) -> 5^1(4(1(x1))) 11.23/3.68 5^1(1(0(x1))) -> 0^1(5(0(2(2(1(x1)))))) 11.23/3.68 5^1(1(0(x1))) -> 1^1(4(0(5(2(3(x1)))))) 11.23/3.68 5^1(1(0(x1))) -> 0^1(5(2(3(x1)))) 11.23/3.68 5^1(1(0(x1))) -> 5^1(2(3(x1))) 11.23/3.68 5^1(1(0(x1))) -> 1^1(5(0(4(4(2(x1)))))) 11.23/3.68 5^1(1(0(x1))) -> 5^1(0(4(4(2(x1))))) 11.23/3.68 5^1(1(0(x1))) -> 0^1(4(4(2(x1)))) 11.23/3.68 5^1(1(0(x1))) -> 1^1(0(4(5(x1)))) 11.23/3.68 5^1(1(0(x1))) -> 0^1(4(5(x1))) 11.23/3.68 5^1(1(0(x1))) -> 5^1(x1) 11.23/3.68 5^1(1(1(x1))) -> 1^1(1(5(4(x1)))) 11.23/3.68 5^1(1(1(x1))) -> 1^1(5(4(x1))) 11.23/3.68 5^1(1(1(x1))) -> 5^1(4(x1)) 11.23/3.68 5^1(1(1(x1))) -> 5^1(4(1(1(x1)))) 11.23/3.68 5^1(1(1(x1))) -> 1^1(5(3(4(1(x1))))) 11.23/3.68 5^1(1(1(x1))) -> 5^1(3(4(1(x1)))) 11.23/3.68 5^1(1(1(x1))) -> 1^1(1(4(5(4(4(x1)))))) 11.23/3.68 5^1(1(1(x1))) -> 1^1(4(5(4(4(x1))))) 11.23/3.68 5^1(1(1(x1))) -> 5^1(4(4(x1))) 11.23/3.68 5^1(1(1(x1))) -> 5^1(2(3(1(1(x1))))) 11.23/3.68 5^1(1(1(x1))) -> 1^1(2(1(5(4(x1))))) 11.23/3.68 0^1(1(3(0(x1)))) -> 0^1(2(0(2(1(3(x1)))))) 11.23/3.68 0^1(1(3(0(x1)))) -> 0^1(2(1(3(x1)))) 11.23/3.68 0^1(1(3(0(x1)))) -> 1^1(3(x1)) 11.23/3.68 0^1(1(5(0(x1)))) -> 0^1(0(5(4(1(5(x1)))))) 11.23/3.68 0^1(1(5(0(x1)))) -> 0^1(5(4(1(5(x1))))) 11.23/3.68 0^1(1(5(0(x1)))) -> 5^1(4(1(5(x1)))) 11.23/3.68 0^1(1(5(0(x1)))) -> 1^1(5(x1)) 11.23/3.68 0^1(1(5(0(x1)))) -> 5^1(x1) 11.23/3.68 0^1(1(5(0(x1)))) -> 0^1(5(4(2(1(0(x1)))))) 11.23/3.68 0^1(1(5(0(x1)))) -> 5^1(4(2(1(0(x1))))) 11.23/3.68 0^1(1(5(0(x1)))) -> 1^1(0(x1)) 11.23/3.68 0^1(3(0(1(x1)))) -> 0^1(0(4(1(3(0(x1)))))) 11.23/3.68 0^1(3(0(1(x1)))) -> 0^1(4(1(3(0(x1))))) 11.23/3.68 0^1(3(0(1(x1)))) -> 1^1(3(0(x1))) 11.23/3.68 0^1(3(0(1(x1)))) -> 0^1(x1) 11.23/3.68 0^1(3(1(0(x1)))) -> 0^1(0(2(3(1(x1))))) 11.23/3.68 0^1(3(1(0(x1)))) -> 0^1(2(3(1(x1)))) 11.23/3.68 0^1(3(1(0(x1)))) -> 1^1(x1) 11.23/3.68 0^1(3(1(1(x1)))) -> 5^1(1(1(0(3(4(x1)))))) 11.23/3.68 0^1(3(1(1(x1)))) -> 1^1(1(0(3(4(x1))))) 11.23/3.68 0^1(3(1(1(x1)))) -> 1^1(0(3(4(x1)))) 11.23/3.68 0^1(3(1(1(x1)))) -> 0^1(3(4(x1))) 11.23/3.68 5^1(0(1(0(x1)))) -> 5^1(0(0(4(1(3(x1)))))) 11.23/3.68 5^1(0(1(0(x1)))) -> 0^1(0(4(1(3(x1))))) 11.23/3.68 5^1(0(1(0(x1)))) -> 0^1(4(1(3(x1)))) 11.23/3.68 5^1(0(1(0(x1)))) -> 1^1(3(x1)) 11.23/3.68 5^1(1(2(0(x1)))) -> 1^1(4(0(5(4(2(x1)))))) 11.23/3.68 5^1(1(2(0(x1)))) -> 0^1(5(4(2(x1)))) 11.23/3.68 5^1(1(2(0(x1)))) -> 5^1(4(2(x1))) 11.23/3.68 5^1(1(2(0(x1)))) -> 5^1(0(4(2(2(1(x1)))))) 11.23/3.68 5^1(1(2(0(x1)))) -> 0^1(4(2(2(1(x1))))) 11.23/3.68 5^1(1(2(0(x1)))) -> 1^1(x1) 11.23/3.68 5^1(1(4(0(x1)))) -> 1^1(5(4(0(2(3(x1)))))) 11.23/3.68 5^1(1(4(0(x1)))) -> 5^1(4(0(2(3(x1))))) 11.23/3.68 5^1(1(4(0(x1)))) -> 0^1(2(3(x1))) 11.23/3.68 5^1(1(4(0(x1)))) -> 5^1(2(1(3(0(x1))))) 11.23/3.68 5^1(1(4(0(x1)))) -> 1^1(3(0(x1))) 11.23/3.68 5^1(1(5(1(x1)))) -> 5^1(4(1(5(1(x1))))) 11.23/3.68 5^1(3(0(1(x1)))) -> 0^1(1(5(2(3(x1))))) 11.23/3.68 5^1(3(0(1(x1)))) -> 1^1(5(2(3(x1)))) 11.23/3.68 5^1(3(0(1(x1)))) -> 5^1(2(3(x1))) 11.23/3.68 5^1(3(1(0(x1)))) -> 1^1(4(3(5(0(x1))))) 11.23/3.68 5^1(3(1(0(x1)))) -> 5^1(0(x1)) 11.23/3.68 5^1(3(1(0(x1)))) -> 1^1(5(0(4(3(x1))))) 11.23/3.68 5^1(3(1(0(x1)))) -> 5^1(0(4(3(x1)))) 11.23/3.68 5^1(3(1(0(x1)))) -> 0^1(4(3(x1))) 11.23/3.68 5^1(3(1(0(x1)))) -> 5^1(4(3(1(0(x1))))) 11.23/3.68 5^1(3(1(0(x1)))) -> 1^1(3(0(4(3(5(x1)))))) 11.23/3.68 5^1(3(1(0(x1)))) -> 0^1(4(3(5(x1)))) 11.23/3.68 5^1(3(1(0(x1)))) -> 5^1(x1) 11.23/3.68 5^1(3(1(1(x1)))) -> 1^1(1(5(3(3(4(x1)))))) 11.23/3.68 5^1(3(1(1(x1)))) -> 1^1(5(3(3(4(x1))))) 11.23/3.68 5^1(3(1(1(x1)))) -> 5^1(3(3(4(x1)))) 11.23/3.68 0^1(1(2(5(0(x1))))) -> 1^1(5(4(0(2(0(x1)))))) 11.23/3.68 0^1(1(2(5(0(x1))))) -> 5^1(4(0(2(0(x1))))) 11.23/3.68 0^1(1(2(5(0(x1))))) -> 0^1(2(0(x1))) 11.23/3.68 0^1(1(4(2(0(x1))))) -> 1^1(0(4(2(3(0(x1)))))) 11.23/3.68 0^1(1(4(2(0(x1))))) -> 0^1(4(2(3(0(x1))))) 11.23/3.68 1^1(4(5(1(0(x1))))) -> 5^1(4(2(1(1(0(x1)))))) 11.23/3.68 1^1(4(5(1(0(x1))))) -> 1^1(1(0(x1))) 11.23/3.68 5^1(0(1(4(0(x1))))) -> 1^1(4(5(4(0(0(x1)))))) 11.23/3.68 5^1(0(1(4(0(x1))))) -> 5^1(4(0(0(x1)))) 11.23/3.68 5^1(0(1(4(0(x1))))) -> 0^1(0(x1)) 11.23/3.68 5^1(5(1(0(0(x1))))) -> 5^1(5(0(4(1(0(x1)))))) 11.23/3.68 5^1(5(1(0(0(x1))))) -> 5^1(0(4(1(0(x1))))) 11.23/3.68 5^1(5(1(0(0(x1))))) -> 0^1(4(1(0(x1)))) 11.23/3.68 5^1(5(1(0(0(x1))))) -> 1^1(0(x1)) 11.23/3.68 11.23/3.68 The TRS R consists of the following rules: 11.23/3.68 11.23/3.68 0(0(1(x1))) -> 0(2(3(0(1(x1))))) 11.23/3.68 0(0(1(x1))) -> 0(4(0(5(4(1(x1)))))) 11.23/3.68 0(0(1(x1))) -> 2(1(0(0(3(4(x1)))))) 11.23/3.68 0(0(1(x1))) -> 4(0(5(4(0(1(x1)))))) 11.23/3.68 0(1(0(x1))) -> 0(0(2(1(2(x1))))) 11.23/3.68 0(1(0(x1))) -> 1(0(0(5(4(x1))))) 11.23/3.68 0(1(0(x1))) -> 0(0(2(5(4(1(x1)))))) 11.23/3.68 0(1(1(x1))) -> 1(0(3(4(1(x1))))) 11.23/3.68 0(1(1(x1))) -> 5(0(3(4(1(1(x1)))))) 11.23/3.68 5(0(1(x1))) -> 0(5(4(1(x1)))) 11.23/3.68 5(0(1(x1))) -> 2(5(4(0(1(x1))))) 11.23/3.68 5(0(1(x1))) -> 5(0(2(1(2(x1))))) 11.23/3.68 5(0(1(x1))) -> 0(1(4(5(4(4(x1)))))) 11.23/3.68 5(0(1(x1))) -> 0(5(4(1(4(4(x1)))))) 11.23/3.68 5(0(1(x1))) -> 5(0(4(3(0(1(x1)))))) 11.23/3.68 5(1(0(x1))) -> 5(0(2(2(1(x1))))) 11.23/3.68 5(1(0(x1))) -> 5(0(5(4(1(x1))))) 11.23/3.68 5(1(0(x1))) -> 0(5(0(2(2(1(x1)))))) 11.23/3.68 5(1(0(x1))) -> 1(4(0(5(2(3(x1)))))) 11.23/3.68 5(1(0(x1))) -> 1(5(0(4(4(2(x1)))))) 11.23/3.68 5(1(0(x1))) -> 4(4(1(0(4(5(x1)))))) 11.23/3.68 5(1(1(x1))) -> 1(1(5(4(x1)))) 11.23/3.68 5(1(1(x1))) -> 5(4(1(1(x1)))) 11.23/3.68 5(1(1(x1))) -> 1(5(3(4(1(x1))))) 11.23/3.68 5(1(1(x1))) -> 1(1(4(5(4(4(x1)))))) 11.23/3.68 5(1(1(x1))) -> 3(5(2(3(1(1(x1)))))) 11.23/3.68 5(1(1(x1))) -> 4(1(2(1(5(4(x1)))))) 11.23/3.68 0(1(3(0(x1)))) -> 0(2(0(2(1(3(x1)))))) 11.23/3.68 0(1(5(0(x1)))) -> 0(0(5(4(1(5(x1)))))) 11.23/3.68 0(1(5(0(x1)))) -> 0(5(4(2(1(0(x1)))))) 11.23/3.68 0(3(0(1(x1)))) -> 0(0(4(1(3(0(x1)))))) 11.23/3.68 0(3(1(0(x1)))) -> 0(0(2(3(1(x1))))) 11.23/3.68 0(3(1(1(x1)))) -> 5(1(1(0(3(4(x1)))))) 11.23/3.68 5(0(1(0(x1)))) -> 5(0(0(4(1(3(x1)))))) 11.23/3.68 5(1(2(0(x1)))) -> 1(4(0(5(4(2(x1)))))) 11.23/3.68 5(1(2(0(x1)))) -> 5(0(4(2(2(1(x1)))))) 11.23/3.68 5(1(4(0(x1)))) -> 1(5(4(0(2(3(x1)))))) 11.23/3.68 5(1(4(0(x1)))) -> 4(5(2(1(3(0(x1)))))) 11.23/3.68 5(1(5(1(x1)))) -> 5(4(1(5(1(x1))))) 11.23/3.68 5(3(0(1(x1)))) -> 0(1(5(2(3(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 1(4(3(5(0(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 1(5(0(4(3(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 5(4(3(1(0(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 1(3(0(4(3(5(x1)))))) 11.23/3.68 5(3(1(1(x1)))) -> 1(1(5(3(3(4(x1)))))) 11.23/3.68 0(1(2(5(0(x1))))) -> 1(5(4(0(2(0(x1)))))) 11.23/3.68 0(1(4(2(0(x1))))) -> 1(0(4(2(3(0(x1)))))) 11.23/3.68 1(4(5(1(0(x1))))) -> 5(4(2(1(1(0(x1)))))) 11.23/3.68 5(0(1(4(0(x1))))) -> 1(4(5(4(0(0(x1)))))) 11.23/3.68 5(5(1(0(0(x1))))) -> 5(5(0(4(1(0(x1)))))) 11.23/3.68 11.23/3.68 Q is empty. 11.23/3.68 We have to consider all minimal (P,Q,R)-chains. 11.23/3.68 ---------------------------------------- 11.23/3.68 11.23/3.68 (3) DependencyGraphProof (EQUIVALENT) 11.23/3.68 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 125 less nodes. 11.23/3.68 ---------------------------------------- 11.23/3.68 11.23/3.68 (4) 11.23/3.68 Complex Obligation (AND) 11.23/3.68 11.23/3.68 ---------------------------------------- 11.23/3.68 11.23/3.68 (5) 11.23/3.68 Obligation: 11.23/3.68 Q DP problem: 11.23/3.68 The TRS P consists of the following rules: 11.23/3.68 11.23/3.68 1^1(4(5(1(0(x1))))) -> 1^1(1(0(x1))) 11.23/3.68 11.23/3.68 The TRS R consists of the following rules: 11.23/3.68 11.23/3.68 0(0(1(x1))) -> 0(2(3(0(1(x1))))) 11.23/3.68 0(0(1(x1))) -> 0(4(0(5(4(1(x1)))))) 11.23/3.68 0(0(1(x1))) -> 2(1(0(0(3(4(x1)))))) 11.23/3.68 0(0(1(x1))) -> 4(0(5(4(0(1(x1)))))) 11.23/3.68 0(1(0(x1))) -> 0(0(2(1(2(x1))))) 11.23/3.68 0(1(0(x1))) -> 1(0(0(5(4(x1))))) 11.23/3.68 0(1(0(x1))) -> 0(0(2(5(4(1(x1)))))) 11.23/3.68 0(1(1(x1))) -> 1(0(3(4(1(x1))))) 11.23/3.68 0(1(1(x1))) -> 5(0(3(4(1(1(x1)))))) 11.23/3.68 5(0(1(x1))) -> 0(5(4(1(x1)))) 11.23/3.68 5(0(1(x1))) -> 2(5(4(0(1(x1))))) 11.23/3.68 5(0(1(x1))) -> 5(0(2(1(2(x1))))) 11.23/3.68 5(0(1(x1))) -> 0(1(4(5(4(4(x1)))))) 11.23/3.68 5(0(1(x1))) -> 0(5(4(1(4(4(x1)))))) 11.23/3.68 5(0(1(x1))) -> 5(0(4(3(0(1(x1)))))) 11.23/3.68 5(1(0(x1))) -> 5(0(2(2(1(x1))))) 11.23/3.68 5(1(0(x1))) -> 5(0(5(4(1(x1))))) 11.23/3.68 5(1(0(x1))) -> 0(5(0(2(2(1(x1)))))) 11.23/3.68 5(1(0(x1))) -> 1(4(0(5(2(3(x1)))))) 11.23/3.68 5(1(0(x1))) -> 1(5(0(4(4(2(x1)))))) 11.23/3.68 5(1(0(x1))) -> 4(4(1(0(4(5(x1)))))) 11.23/3.68 5(1(1(x1))) -> 1(1(5(4(x1)))) 11.23/3.68 5(1(1(x1))) -> 5(4(1(1(x1)))) 11.23/3.68 5(1(1(x1))) -> 1(5(3(4(1(x1))))) 11.23/3.68 5(1(1(x1))) -> 1(1(4(5(4(4(x1)))))) 11.23/3.68 5(1(1(x1))) -> 3(5(2(3(1(1(x1)))))) 11.23/3.68 5(1(1(x1))) -> 4(1(2(1(5(4(x1)))))) 11.23/3.68 0(1(3(0(x1)))) -> 0(2(0(2(1(3(x1)))))) 11.23/3.68 0(1(5(0(x1)))) -> 0(0(5(4(1(5(x1)))))) 11.23/3.68 0(1(5(0(x1)))) -> 0(5(4(2(1(0(x1)))))) 11.23/3.68 0(3(0(1(x1)))) -> 0(0(4(1(3(0(x1)))))) 11.23/3.68 0(3(1(0(x1)))) -> 0(0(2(3(1(x1))))) 11.23/3.68 0(3(1(1(x1)))) -> 5(1(1(0(3(4(x1)))))) 11.23/3.68 5(0(1(0(x1)))) -> 5(0(0(4(1(3(x1)))))) 11.23/3.68 5(1(2(0(x1)))) -> 1(4(0(5(4(2(x1)))))) 11.23/3.68 5(1(2(0(x1)))) -> 5(0(4(2(2(1(x1)))))) 11.23/3.68 5(1(4(0(x1)))) -> 1(5(4(0(2(3(x1)))))) 11.23/3.68 5(1(4(0(x1)))) -> 4(5(2(1(3(0(x1)))))) 11.23/3.68 5(1(5(1(x1)))) -> 5(4(1(5(1(x1))))) 11.23/3.68 5(3(0(1(x1)))) -> 0(1(5(2(3(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 1(4(3(5(0(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 1(5(0(4(3(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 5(4(3(1(0(x1))))) 11.23/3.68 5(3(1(0(x1)))) -> 1(3(0(4(3(5(x1)))))) 11.23/3.68 5(3(1(1(x1)))) -> 1(1(5(3(3(4(x1)))))) 11.23/3.68 0(1(2(5(0(x1))))) -> 1(5(4(0(2(0(x1)))))) 11.23/3.68 0(1(4(2(0(x1))))) -> 1(0(4(2(3(0(x1)))))) 11.23/3.68 1(4(5(1(0(x1))))) -> 5(4(2(1(1(0(x1)))))) 11.23/3.68 5(0(1(4(0(x1))))) -> 1(4(5(4(0(0(x1)))))) 11.23/3.68 5(5(1(0(0(x1))))) -> 5(5(0(4(1(0(x1)))))) 11.23/3.68 11.23/3.68 Q is empty. 11.23/3.68 We have to consider all minimal (P,Q,R)-chains. 11.23/3.68 ---------------------------------------- 11.23/3.68 11.23/3.68 (6) QDPSizeChangeProof (EQUIVALENT) 11.23/3.68 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 11.23/3.68 11.23/3.68 From the DPs we obtained the following set of size-change graphs: 11.23/3.68 *1^1(4(5(1(0(x1))))) -> 1^1(1(0(x1))) 11.23/3.68 The graph contains the following edges 1 > 1 11.23/3.68 11.23/3.68 11.23/3.68 ---------------------------------------- 11.23/3.68 11.23/3.68 (7) 11.23/3.68 YES 11.23/3.68 11.23/3.68 ---------------------------------------- 11.23/3.68 11.23/3.68 (8) 11.23/3.68 Obligation: 11.23/3.68 Q DP problem: 11.23/3.68 The TRS P consists of the following rules: 11.23/3.68 11.23/3.68 0^1(1(5(0(x1)))) -> 5^1(x1) 11.23/3.68 5^1(1(0(x1))) -> 5^1(x1) 11.23/3.68 5^1(3(1(0(x1)))) -> 5^1(0(x1)) 11.23/3.68 5^1(3(1(0(x1)))) -> 5^1(x1) 11.23/3.69 5^1(0(1(4(0(x1))))) -> 0^1(0(x1)) 11.23/3.69 0^1(3(0(1(x1)))) -> 0^1(x1) 11.23/3.69 11.23/3.69 The TRS R consists of the following rules: 11.23/3.69 11.23/3.69 0(0(1(x1))) -> 0(2(3(0(1(x1))))) 11.23/3.69 0(0(1(x1))) -> 0(4(0(5(4(1(x1)))))) 11.23/3.69 0(0(1(x1))) -> 2(1(0(0(3(4(x1)))))) 11.23/3.69 0(0(1(x1))) -> 4(0(5(4(0(1(x1)))))) 11.23/3.69 0(1(0(x1))) -> 0(0(2(1(2(x1))))) 11.23/3.69 0(1(0(x1))) -> 1(0(0(5(4(x1))))) 11.23/3.69 0(1(0(x1))) -> 0(0(2(5(4(1(x1)))))) 11.23/3.69 0(1(1(x1))) -> 1(0(3(4(1(x1))))) 11.23/3.69 0(1(1(x1))) -> 5(0(3(4(1(1(x1)))))) 11.23/3.69 5(0(1(x1))) -> 0(5(4(1(x1)))) 11.23/3.69 5(0(1(x1))) -> 2(5(4(0(1(x1))))) 11.23/3.69 5(0(1(x1))) -> 5(0(2(1(2(x1))))) 11.23/3.69 5(0(1(x1))) -> 0(1(4(5(4(4(x1)))))) 11.23/3.69 5(0(1(x1))) -> 0(5(4(1(4(4(x1)))))) 11.23/3.69 5(0(1(x1))) -> 5(0(4(3(0(1(x1)))))) 11.23/3.69 5(1(0(x1))) -> 5(0(2(2(1(x1))))) 11.23/3.69 5(1(0(x1))) -> 5(0(5(4(1(x1))))) 11.23/3.69 5(1(0(x1))) -> 0(5(0(2(2(1(x1)))))) 11.23/3.69 5(1(0(x1))) -> 1(4(0(5(2(3(x1)))))) 11.23/3.69 5(1(0(x1))) -> 1(5(0(4(4(2(x1)))))) 11.23/3.69 5(1(0(x1))) -> 4(4(1(0(4(5(x1)))))) 11.23/3.69 5(1(1(x1))) -> 1(1(5(4(x1)))) 11.23/3.69 5(1(1(x1))) -> 5(4(1(1(x1)))) 11.23/3.69 5(1(1(x1))) -> 1(5(3(4(1(x1))))) 11.23/3.69 5(1(1(x1))) -> 1(1(4(5(4(4(x1)))))) 11.23/3.69 5(1(1(x1))) -> 3(5(2(3(1(1(x1)))))) 11.23/3.69 5(1(1(x1))) -> 4(1(2(1(5(4(x1)))))) 11.23/3.69 0(1(3(0(x1)))) -> 0(2(0(2(1(3(x1)))))) 11.23/3.69 0(1(5(0(x1)))) -> 0(0(5(4(1(5(x1)))))) 11.23/3.69 0(1(5(0(x1)))) -> 0(5(4(2(1(0(x1)))))) 11.23/3.69 0(3(0(1(x1)))) -> 0(0(4(1(3(0(x1)))))) 11.23/3.69 0(3(1(0(x1)))) -> 0(0(2(3(1(x1))))) 11.23/3.69 0(3(1(1(x1)))) -> 5(1(1(0(3(4(x1)))))) 11.23/3.69 5(0(1(0(x1)))) -> 5(0(0(4(1(3(x1)))))) 11.23/3.69 5(1(2(0(x1)))) -> 1(4(0(5(4(2(x1)))))) 11.23/3.69 5(1(2(0(x1)))) -> 5(0(4(2(2(1(x1)))))) 11.23/3.69 5(1(4(0(x1)))) -> 1(5(4(0(2(3(x1)))))) 11.23/3.69 5(1(4(0(x1)))) -> 4(5(2(1(3(0(x1)))))) 11.23/3.69 5(1(5(1(x1)))) -> 5(4(1(5(1(x1))))) 11.23/3.69 5(3(0(1(x1)))) -> 0(1(5(2(3(x1))))) 11.23/3.69 5(3(1(0(x1)))) -> 1(4(3(5(0(x1))))) 11.23/3.69 5(3(1(0(x1)))) -> 1(5(0(4(3(x1))))) 11.23/3.69 5(3(1(0(x1)))) -> 5(4(3(1(0(x1))))) 11.23/3.69 5(3(1(0(x1)))) -> 1(3(0(4(3(5(x1)))))) 11.23/3.69 5(3(1(1(x1)))) -> 1(1(5(3(3(4(x1)))))) 11.23/3.69 0(1(2(5(0(x1))))) -> 1(5(4(0(2(0(x1)))))) 11.23/3.69 0(1(4(2(0(x1))))) -> 1(0(4(2(3(0(x1)))))) 11.23/3.69 1(4(5(1(0(x1))))) -> 5(4(2(1(1(0(x1)))))) 11.23/3.69 5(0(1(4(0(x1))))) -> 1(4(5(4(0(0(x1)))))) 11.23/3.69 5(5(1(0(0(x1))))) -> 5(5(0(4(1(0(x1)))))) 11.23/3.69 11.23/3.69 Q is empty. 11.23/3.69 We have to consider all minimal (P,Q,R)-chains. 11.23/3.69 ---------------------------------------- 11.23/3.69 11.23/3.69 (9) QDPSizeChangeProof (EQUIVALENT) 11.23/3.69 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 11.23/3.69 11.23/3.69 From the DPs we obtained the following set of size-change graphs: 11.23/3.69 *5^1(0(1(4(0(x1))))) -> 0^1(0(x1)) 11.23/3.69 The graph contains the following edges 1 > 1 11.23/3.69 11.23/3.69 11.23/3.69 *0^1(3(0(1(x1)))) -> 0^1(x1) 11.23/3.69 The graph contains the following edges 1 > 1 11.23/3.69 11.23/3.69 11.23/3.69 *0^1(1(5(0(x1)))) -> 5^1(x1) 11.23/3.69 The graph contains the following edges 1 > 1 11.23/3.69 11.23/3.69 11.23/3.69 *5^1(1(0(x1))) -> 5^1(x1) 11.23/3.69 The graph contains the following edges 1 > 1 11.23/3.69 11.23/3.69 11.23/3.69 *5^1(3(1(0(x1)))) -> 5^1(0(x1)) 11.23/3.69 The graph contains the following edges 1 > 1 11.23/3.69 11.23/3.69 11.23/3.69 *5^1(3(1(0(x1)))) -> 5^1(x1) 11.23/3.69 The graph contains the following edges 1 > 1 11.23/3.69 11.23/3.69 11.23/3.69 ---------------------------------------- 11.23/3.69 11.23/3.69 (10) 11.23/3.69 YES 11.48/3.77 EOF