3.94/1.89 YES 3.94/1.90 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.94/1.90 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.94/1.90 3.94/1.90 3.94/1.90 Termination w.r.t. Q of the given QTRS could be proven: 3.94/1.90 3.94/1.90 (0) QTRS 3.94/1.90 (1) DependencyPairsProof [EQUIVALENT, 36 ms] 3.94/1.90 (2) QDP 3.94/1.90 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 3.94/1.90 (4) QDP 3.94/1.90 (5) MRRProof [EQUIVALENT, 0 ms] 3.94/1.90 (6) QDP 3.94/1.90 (7) TransformationProof [EQUIVALENT, 0 ms] 3.94/1.90 (8) QDP 3.94/1.90 (9) TransformationProof [EQUIVALENT, 0 ms] 3.94/1.90 (10) QDP 3.94/1.90 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 3.94/1.90 (12) QDP 3.94/1.90 (13) UsableRulesProof [EQUIVALENT, 0 ms] 3.94/1.90 (14) QDP 3.94/1.90 (15) QReductionProof [EQUIVALENT, 0 ms] 3.94/1.90 (16) QDP 3.94/1.90 (17) TransformationProof [EQUIVALENT, 0 ms] 3.94/1.90 (18) QDP 3.94/1.90 (19) DependencyGraphProof [EQUIVALENT, 0 ms] 3.94/1.90 (20) QDP 3.94/1.90 (21) UsableRulesProof [EQUIVALENT, 0 ms] 3.94/1.90 (22) QDP 3.94/1.90 (23) QReductionProof [EQUIVALENT, 0 ms] 3.94/1.90 (24) QDP 3.94/1.90 (25) TransformationProof [EQUIVALENT, 0 ms] 3.94/1.90 (26) QDP 3.94/1.90 (27) DependencyGraphProof [EQUIVALENT, 0 ms] 3.94/1.90 (28) TRUE 3.94/1.90 3.94/1.90 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (0) 3.94/1.90 Obligation: 3.94/1.90 Q restricted rewrite system: 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__h(X) -> a__g(mark(X), X) 3.94/1.90 a__g(a, X) -> a__f(b, X) 3.94/1.90 a__f(X, X) -> a__h(a__a) 3.94/1.90 a__a -> b 3.94/1.90 mark(h(X)) -> a__h(mark(X)) 3.94/1.90 mark(g(X1, X2)) -> a__g(mark(X1), X2) 3.94/1.90 mark(a) -> a__a 3.94/1.90 mark(f(X1, X2)) -> a__f(mark(X1), X2) 3.94/1.90 mark(b) -> b 3.94/1.90 a__h(X) -> h(X) 3.94/1.90 a__g(X1, X2) -> g(X1, X2) 3.94/1.90 a__a -> a 3.94/1.90 a__f(X1, X2) -> f(X1, X2) 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__h(x0) 3.94/1.90 a__a 3.94/1.90 mark(h(x0)) 3.94/1.90 mark(g(x0, x1)) 3.94/1.90 mark(a) 3.94/1.90 mark(f(x0, x1)) 3.94/1.90 mark(b) 3.94/1.90 a__g(x0, x1) 3.94/1.90 a__f(x0, x1) 3.94/1.90 3.94/1.90 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (1) DependencyPairsProof (EQUIVALENT) 3.94/1.90 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (2) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__H(X) -> A__G(mark(X), X) 3.94/1.90 A__H(X) -> MARK(X) 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 A__F(X, X) -> A__H(a__a) 3.94/1.90 A__F(X, X) -> A__A 3.94/1.90 MARK(h(X)) -> A__H(mark(X)) 3.94/1.90 MARK(h(X)) -> MARK(X) 3.94/1.90 MARK(g(X1, X2)) -> A__G(mark(X1), X2) 3.94/1.90 MARK(g(X1, X2)) -> MARK(X1) 3.94/1.90 MARK(a) -> A__A 3.94/1.90 MARK(f(X1, X2)) -> A__F(mark(X1), X2) 3.94/1.90 MARK(f(X1, X2)) -> MARK(X1) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__h(X) -> a__g(mark(X), X) 3.94/1.90 a__g(a, X) -> a__f(b, X) 3.94/1.90 a__f(X, X) -> a__h(a__a) 3.94/1.90 a__a -> b 3.94/1.90 mark(h(X)) -> a__h(mark(X)) 3.94/1.90 mark(g(X1, X2)) -> a__g(mark(X1), X2) 3.94/1.90 mark(a) -> a__a 3.94/1.90 mark(f(X1, X2)) -> a__f(mark(X1), X2) 3.94/1.90 mark(b) -> b 3.94/1.90 a__h(X) -> h(X) 3.94/1.90 a__g(X1, X2) -> g(X1, X2) 3.94/1.90 a__a -> a 3.94/1.90 a__f(X1, X2) -> f(X1, X2) 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__h(x0) 3.94/1.90 a__a 3.94/1.90 mark(h(x0)) 3.94/1.90 mark(g(x0, x1)) 3.94/1.90 mark(a) 3.94/1.90 mark(f(x0, x1)) 3.94/1.90 mark(b) 3.94/1.90 a__g(x0, x1) 3.94/1.90 a__f(x0, x1) 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (3) DependencyGraphProof (EQUIVALENT) 3.94/1.90 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (4) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 A__F(X, X) -> A__H(a__a) 3.94/1.90 A__H(X) -> A__G(mark(X), X) 3.94/1.90 A__H(X) -> MARK(X) 3.94/1.90 MARK(h(X)) -> A__H(mark(X)) 3.94/1.90 MARK(h(X)) -> MARK(X) 3.94/1.90 MARK(g(X1, X2)) -> A__G(mark(X1), X2) 3.94/1.90 MARK(g(X1, X2)) -> MARK(X1) 3.94/1.90 MARK(f(X1, X2)) -> A__F(mark(X1), X2) 3.94/1.90 MARK(f(X1, X2)) -> MARK(X1) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__h(X) -> a__g(mark(X), X) 3.94/1.90 a__g(a, X) -> a__f(b, X) 3.94/1.90 a__f(X, X) -> a__h(a__a) 3.94/1.90 a__a -> b 3.94/1.90 mark(h(X)) -> a__h(mark(X)) 3.94/1.90 mark(g(X1, X2)) -> a__g(mark(X1), X2) 3.94/1.90 mark(a) -> a__a 3.94/1.90 mark(f(X1, X2)) -> a__f(mark(X1), X2) 3.94/1.90 mark(b) -> b 3.94/1.90 a__h(X) -> h(X) 3.94/1.90 a__g(X1, X2) -> g(X1, X2) 3.94/1.90 a__a -> a 3.94/1.90 a__f(X1, X2) -> f(X1, X2) 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__h(x0) 3.94/1.90 a__a 3.94/1.90 mark(h(x0)) 3.94/1.90 mark(g(x0, x1)) 3.94/1.90 mark(a) 3.94/1.90 mark(f(x0, x1)) 3.94/1.90 mark(b) 3.94/1.90 a__g(x0, x1) 3.94/1.90 a__f(x0, x1) 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (5) MRRProof (EQUIVALENT) 3.94/1.90 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 3.94/1.90 3.94/1.90 Strictly oriented dependency pairs: 3.94/1.90 3.94/1.90 A__H(X) -> MARK(X) 3.94/1.90 MARK(h(X)) -> A__H(mark(X)) 3.94/1.90 MARK(h(X)) -> MARK(X) 3.94/1.90 MARK(g(X1, X2)) -> A__G(mark(X1), X2) 3.94/1.90 MARK(g(X1, X2)) -> MARK(X1) 3.94/1.90 MARK(f(X1, X2)) -> A__F(mark(X1), X2) 3.94/1.90 MARK(f(X1, X2)) -> MARK(X1) 3.94/1.90 3.94/1.90 3.94/1.90 Used ordering: Polynomial interpretation [POLO]: 3.94/1.90 3.94/1.90 POL(A__F(x_1, x_2)) = 2 + 2*x_1 + x_2 3.94/1.90 POL(A__G(x_1, x_2)) = 2 + x_1 + x_2 3.94/1.90 POL(A__H(x_1)) = 2 + 2*x_1 3.94/1.90 POL(MARK(x_1)) = 1 + 2*x_1 3.94/1.90 POL(a) = 0 3.94/1.90 POL(a__a) = 0 3.94/1.90 POL(a__f(x_1, x_2)) = 2 + 2*x_1 + x_2 3.94/1.90 POL(a__g(x_1, x_2)) = 2 + x_1 + x_2 3.94/1.90 POL(a__h(x_1)) = 2 + 2*x_1 3.94/1.90 POL(b) = 0 3.94/1.90 POL(f(x_1, x_2)) = 2 + 2*x_1 + x_2 3.94/1.90 POL(g(x_1, x_2)) = 2 + x_1 + x_2 3.94/1.90 POL(h(x_1)) = 2 + 2*x_1 3.94/1.90 POL(mark(x_1)) = x_1 3.94/1.90 3.94/1.90 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (6) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 A__F(X, X) -> A__H(a__a) 3.94/1.90 A__H(X) -> A__G(mark(X), X) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__h(X) -> a__g(mark(X), X) 3.94/1.90 a__g(a, X) -> a__f(b, X) 3.94/1.90 a__f(X, X) -> a__h(a__a) 3.94/1.90 a__a -> b 3.94/1.90 mark(h(X)) -> a__h(mark(X)) 3.94/1.90 mark(g(X1, X2)) -> a__g(mark(X1), X2) 3.94/1.90 mark(a) -> a__a 3.94/1.90 mark(f(X1, X2)) -> a__f(mark(X1), X2) 3.94/1.90 mark(b) -> b 3.94/1.90 a__h(X) -> h(X) 3.94/1.90 a__g(X1, X2) -> g(X1, X2) 3.94/1.90 a__a -> a 3.94/1.90 a__f(X1, X2) -> f(X1, X2) 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__h(x0) 3.94/1.90 a__a 3.94/1.90 mark(h(x0)) 3.94/1.90 mark(g(x0, x1)) 3.94/1.90 mark(a) 3.94/1.90 mark(f(x0, x1)) 3.94/1.90 mark(b) 3.94/1.90 a__g(x0, x1) 3.94/1.90 a__f(x0, x1) 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (7) TransformationProof (EQUIVALENT) 3.94/1.90 By narrowing [LPAR04] the rule A__F(X, X) -> A__H(a__a) at position [0] we obtained the following new rules [LPAR04]: 3.94/1.90 3.94/1.90 (A__F(y0, y0) -> A__H(b),A__F(y0, y0) -> A__H(b)) 3.94/1.90 (A__F(y0, y0) -> A__H(a),A__F(y0, y0) -> A__H(a)) 3.94/1.90 3.94/1.90 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (8) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 A__H(X) -> A__G(mark(X), X) 3.94/1.90 A__F(y0, y0) -> A__H(b) 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__h(X) -> a__g(mark(X), X) 3.94/1.90 a__g(a, X) -> a__f(b, X) 3.94/1.90 a__f(X, X) -> a__h(a__a) 3.94/1.90 a__a -> b 3.94/1.90 mark(h(X)) -> a__h(mark(X)) 3.94/1.90 mark(g(X1, X2)) -> a__g(mark(X1), X2) 3.94/1.90 mark(a) -> a__a 3.94/1.90 mark(f(X1, X2)) -> a__f(mark(X1), X2) 3.94/1.90 mark(b) -> b 3.94/1.90 a__h(X) -> h(X) 3.94/1.90 a__g(X1, X2) -> g(X1, X2) 3.94/1.90 a__a -> a 3.94/1.90 a__f(X1, X2) -> f(X1, X2) 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__h(x0) 3.94/1.90 a__a 3.94/1.90 mark(h(x0)) 3.94/1.90 mark(g(x0, x1)) 3.94/1.90 mark(a) 3.94/1.90 mark(f(x0, x1)) 3.94/1.90 mark(b) 3.94/1.90 a__g(x0, x1) 3.94/1.90 a__f(x0, x1) 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (9) TransformationProof (EQUIVALENT) 3.94/1.90 By narrowing [LPAR04] the rule A__H(X) -> A__G(mark(X), X) at position [0] we obtained the following new rules [LPAR04]: 3.94/1.90 3.94/1.90 (A__H(h(x0)) -> A__G(a__h(mark(x0)), h(x0)),A__H(h(x0)) -> A__G(a__h(mark(x0)), h(x0))) 3.94/1.90 (A__H(g(x0, x1)) -> A__G(a__g(mark(x0), x1), g(x0, x1)),A__H(g(x0, x1)) -> A__G(a__g(mark(x0), x1), g(x0, x1))) 3.94/1.90 (A__H(a) -> A__G(a__a, a),A__H(a) -> A__G(a__a, a)) 3.94/1.90 (A__H(f(x0, x1)) -> A__G(a__f(mark(x0), x1), f(x0, x1)),A__H(f(x0, x1)) -> A__G(a__f(mark(x0), x1), f(x0, x1))) 3.94/1.90 (A__H(b) -> A__G(b, b),A__H(b) -> A__G(b, b)) 3.94/1.90 3.94/1.90 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (10) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 A__F(y0, y0) -> A__H(b) 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 A__H(h(x0)) -> A__G(a__h(mark(x0)), h(x0)) 3.94/1.90 A__H(g(x0, x1)) -> A__G(a__g(mark(x0), x1), g(x0, x1)) 3.94/1.90 A__H(a) -> A__G(a__a, a) 3.94/1.90 A__H(f(x0, x1)) -> A__G(a__f(mark(x0), x1), f(x0, x1)) 3.94/1.90 A__H(b) -> A__G(b, b) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__h(X) -> a__g(mark(X), X) 3.94/1.90 a__g(a, X) -> a__f(b, X) 3.94/1.90 a__f(X, X) -> a__h(a__a) 3.94/1.90 a__a -> b 3.94/1.90 mark(h(X)) -> a__h(mark(X)) 3.94/1.90 mark(g(X1, X2)) -> a__g(mark(X1), X2) 3.94/1.90 mark(a) -> a__a 3.94/1.90 mark(f(X1, X2)) -> a__f(mark(X1), X2) 3.94/1.90 mark(b) -> b 3.94/1.90 a__h(X) -> h(X) 3.94/1.90 a__g(X1, X2) -> g(X1, X2) 3.94/1.90 a__a -> a 3.94/1.90 a__f(X1, X2) -> f(X1, X2) 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__h(x0) 3.94/1.90 a__a 3.94/1.90 mark(h(x0)) 3.94/1.90 mark(g(x0, x1)) 3.94/1.90 mark(a) 3.94/1.90 mark(f(x0, x1)) 3.94/1.90 mark(b) 3.94/1.90 a__g(x0, x1) 3.94/1.90 a__f(x0, x1) 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (11) DependencyGraphProof (EQUIVALENT) 3.94/1.90 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (12) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 A__H(a) -> A__G(a__a, a) 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__h(X) -> a__g(mark(X), X) 3.94/1.90 a__g(a, X) -> a__f(b, X) 3.94/1.90 a__f(X, X) -> a__h(a__a) 3.94/1.90 a__a -> b 3.94/1.90 mark(h(X)) -> a__h(mark(X)) 3.94/1.90 mark(g(X1, X2)) -> a__g(mark(X1), X2) 3.94/1.90 mark(a) -> a__a 3.94/1.90 mark(f(X1, X2)) -> a__f(mark(X1), X2) 3.94/1.90 mark(b) -> b 3.94/1.90 a__h(X) -> h(X) 3.94/1.90 a__g(X1, X2) -> g(X1, X2) 3.94/1.90 a__a -> a 3.94/1.90 a__f(X1, X2) -> f(X1, X2) 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__h(x0) 3.94/1.90 a__a 3.94/1.90 mark(h(x0)) 3.94/1.90 mark(g(x0, x1)) 3.94/1.90 mark(a) 3.94/1.90 mark(f(x0, x1)) 3.94/1.90 mark(b) 3.94/1.90 a__g(x0, x1) 3.94/1.90 a__f(x0, x1) 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (13) UsableRulesProof (EQUIVALENT) 3.94/1.90 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (14) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 A__H(a) -> A__G(a__a, a) 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__a -> b 3.94/1.90 a__a -> a 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__h(x0) 3.94/1.90 a__a 3.94/1.90 mark(h(x0)) 3.94/1.90 mark(g(x0, x1)) 3.94/1.90 mark(a) 3.94/1.90 mark(f(x0, x1)) 3.94/1.90 mark(b) 3.94/1.90 a__g(x0, x1) 3.94/1.90 a__f(x0, x1) 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (15) QReductionProof (EQUIVALENT) 3.94/1.90 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.94/1.90 3.94/1.90 a__h(x0) 3.94/1.90 mark(h(x0)) 3.94/1.90 mark(g(x0, x1)) 3.94/1.90 mark(a) 3.94/1.90 mark(f(x0, x1)) 3.94/1.90 mark(b) 3.94/1.90 a__g(x0, x1) 3.94/1.90 a__f(x0, x1) 3.94/1.90 3.94/1.90 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (16) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 A__H(a) -> A__G(a__a, a) 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__a -> b 3.94/1.90 a__a -> a 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__a 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (17) TransformationProof (EQUIVALENT) 3.94/1.90 By narrowing [LPAR04] the rule A__H(a) -> A__G(a__a, a) at position [0] we obtained the following new rules [LPAR04]: 3.94/1.90 3.94/1.90 (A__H(a) -> A__G(b, a),A__H(a) -> A__G(b, a)) 3.94/1.90 (A__H(a) -> A__G(a, a),A__H(a) -> A__G(a, a)) 3.94/1.90 3.94/1.90 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (18) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 A__H(a) -> A__G(b, a) 3.94/1.90 A__H(a) -> A__G(a, a) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__a -> b 3.94/1.90 a__a -> a 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__a 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (19) DependencyGraphProof (EQUIVALENT) 3.94/1.90 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (20) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__H(a) -> A__G(a, a) 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 3.94/1.90 The TRS R consists of the following rules: 3.94/1.90 3.94/1.90 a__a -> b 3.94/1.90 a__a -> a 3.94/1.90 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__a 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (21) UsableRulesProof (EQUIVALENT) 3.94/1.90 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (22) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__H(a) -> A__G(a, a) 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 3.94/1.90 R is empty. 3.94/1.90 The set Q consists of the following terms: 3.94/1.90 3.94/1.90 a__a 3.94/1.90 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (23) QReductionProof (EQUIVALENT) 3.94/1.90 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.94/1.90 3.94/1.90 a__a 3.94/1.90 3.94/1.90 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (24) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__H(a) -> A__G(a, a) 3.94/1.90 A__G(a, X) -> A__F(b, X) 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 3.94/1.90 R is empty. 3.94/1.90 Q is empty. 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (25) TransformationProof (EQUIVALENT) 3.94/1.90 By instantiating [LPAR04] the rule A__G(a, X) -> A__F(b, X) we obtained the following new rules [LPAR04]: 3.94/1.90 3.94/1.90 (A__G(a, a) -> A__F(b, a),A__G(a, a) -> A__F(b, a)) 3.94/1.90 3.94/1.90 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (26) 3.94/1.90 Obligation: 3.94/1.90 Q DP problem: 3.94/1.90 The TRS P consists of the following rules: 3.94/1.90 3.94/1.90 A__H(a) -> A__G(a, a) 3.94/1.90 A__F(y0, y0) -> A__H(a) 3.94/1.90 A__G(a, a) -> A__F(b, a) 3.94/1.90 3.94/1.90 R is empty. 3.94/1.90 Q is empty. 3.94/1.90 We have to consider all minimal (P,Q,R)-chains. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (27) DependencyGraphProof (EQUIVALENT) 3.94/1.90 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes. 3.94/1.90 ---------------------------------------- 3.94/1.90 3.94/1.90 (28) 3.94/1.90 TRUE 3.94/1.92 EOF