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