4.26/1.94 YES 4.62/2.02 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 4.62/2.02 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.62/2.02 4.62/2.02 4.62/2.02 Termination w.r.t. Q of the given QTRS could be proven: 4.62/2.02 4.62/2.02 (0) QTRS 4.62/2.02 (1) DependencyPairsProof [EQUIVALENT, 24 ms] 4.62/2.02 (2) QDP 4.62/2.02 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 4.62/2.02 (4) AND 4.62/2.02 (5) QDP 4.62/2.02 (6) UsableRulesProof [EQUIVALENT, 0 ms] 4.62/2.02 (7) QDP 4.62/2.02 (8) QReductionProof [EQUIVALENT, 0 ms] 4.62/2.02 (9) QDP 4.62/2.02 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.62/2.02 (11) YES 4.62/2.02 (12) QDP 4.62/2.02 (13) UsableRulesProof [EQUIVALENT, 0 ms] 4.62/2.02 (14) QDP 4.62/2.02 (15) QReductionProof [EQUIVALENT, 0 ms] 4.62/2.02 (16) QDP 4.62/2.02 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.62/2.02 (18) YES 4.62/2.02 (19) QDP 4.62/2.02 (20) QDPOrderProof [EQUIVALENT, 32 ms] 4.62/2.02 (21) QDP 4.62/2.02 (22) DependencyGraphProof [EQUIVALENT, 0 ms] 4.62/2.02 (23) QDP 4.62/2.02 (24) UsableRulesProof [EQUIVALENT, 0 ms] 4.62/2.02 (25) QDP 4.62/2.02 (26) QReductionProof [EQUIVALENT, 0 ms] 4.62/2.02 (27) QDP 4.62/2.02 (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.62/2.02 (29) YES 4.62/2.02 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (0) 4.62/2.02 Obligation: 4.62/2.02 Q restricted rewrite system: 4.62/2.02 The TRS R consists of the following rules: 4.62/2.02 4.62/2.02 active(f(g(X), Y)) -> mark(f(X, f(g(X), Y))) 4.62/2.02 mark(f(X1, X2)) -> active(f(mark(X1), X2)) 4.62/2.02 mark(g(X)) -> active(g(mark(X))) 4.62/2.02 f(mark(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, mark(X2)) -> f(X1, X2) 4.62/2.02 f(active(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, active(X2)) -> f(X1, X2) 4.62/2.02 g(mark(X)) -> g(X) 4.62/2.02 g(active(X)) -> g(X) 4.62/2.02 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (1) DependencyPairsProof (EQUIVALENT) 4.62/2.02 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (2) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 ACTIVE(f(g(X), Y)) -> MARK(f(X, f(g(X), Y))) 4.62/2.02 ACTIVE(f(g(X), Y)) -> F(X, f(g(X), Y)) 4.62/2.02 MARK(f(X1, X2)) -> ACTIVE(f(mark(X1), X2)) 4.62/2.02 MARK(f(X1, X2)) -> F(mark(X1), X2) 4.62/2.02 MARK(f(X1, X2)) -> MARK(X1) 4.62/2.02 MARK(g(X)) -> ACTIVE(g(mark(X))) 4.62/2.02 MARK(g(X)) -> G(mark(X)) 4.62/2.02 MARK(g(X)) -> MARK(X) 4.62/2.02 F(mark(X1), X2) -> F(X1, X2) 4.62/2.02 F(X1, mark(X2)) -> F(X1, X2) 4.62/2.02 F(active(X1), X2) -> F(X1, X2) 4.62/2.02 F(X1, active(X2)) -> F(X1, X2) 4.62/2.02 G(mark(X)) -> G(X) 4.62/2.02 G(active(X)) -> G(X) 4.62/2.02 4.62/2.02 The TRS R consists of the following rules: 4.62/2.02 4.62/2.02 active(f(g(X), Y)) -> mark(f(X, f(g(X), Y))) 4.62/2.02 mark(f(X1, X2)) -> active(f(mark(X1), X2)) 4.62/2.02 mark(g(X)) -> active(g(mark(X))) 4.62/2.02 f(mark(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, mark(X2)) -> f(X1, X2) 4.62/2.02 f(active(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, active(X2)) -> f(X1, X2) 4.62/2.02 g(mark(X)) -> g(X) 4.62/2.02 g(active(X)) -> g(X) 4.62/2.02 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (3) DependencyGraphProof (EQUIVALENT) 4.62/2.02 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 3 less nodes. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (4) 4.62/2.02 Complex Obligation (AND) 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (5) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 G(active(X)) -> G(X) 4.62/2.02 G(mark(X)) -> G(X) 4.62/2.02 4.62/2.02 The TRS R consists of the following rules: 4.62/2.02 4.62/2.02 active(f(g(X), Y)) -> mark(f(X, f(g(X), Y))) 4.62/2.02 mark(f(X1, X2)) -> active(f(mark(X1), X2)) 4.62/2.02 mark(g(X)) -> active(g(mark(X))) 4.62/2.02 f(mark(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, mark(X2)) -> f(X1, X2) 4.62/2.02 f(active(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, active(X2)) -> f(X1, X2) 4.62/2.02 g(mark(X)) -> g(X) 4.62/2.02 g(active(X)) -> g(X) 4.62/2.02 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (6) UsableRulesProof (EQUIVALENT) 4.62/2.02 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. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (7) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 G(active(X)) -> G(X) 4.62/2.02 G(mark(X)) -> G(X) 4.62/2.02 4.62/2.02 R is empty. 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (8) QReductionProof (EQUIVALENT) 4.62/2.02 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.62/2.02 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (9) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 G(active(X)) -> G(X) 4.62/2.02 G(mark(X)) -> G(X) 4.62/2.02 4.62/2.02 R is empty. 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (10) QDPSizeChangeProof (EQUIVALENT) 4.62/2.02 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. 4.62/2.02 4.62/2.02 From the DPs we obtained the following set of size-change graphs: 4.62/2.02 *G(active(X)) -> G(X) 4.62/2.02 The graph contains the following edges 1 > 1 4.62/2.02 4.62/2.02 4.62/2.02 *G(mark(X)) -> G(X) 4.62/2.02 The graph contains the following edges 1 > 1 4.62/2.02 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (11) 4.62/2.02 YES 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (12) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 F(X1, mark(X2)) -> F(X1, X2) 4.62/2.02 F(mark(X1), X2) -> F(X1, X2) 4.62/2.02 F(active(X1), X2) -> F(X1, X2) 4.62/2.02 F(X1, active(X2)) -> F(X1, X2) 4.62/2.02 4.62/2.02 The TRS R consists of the following rules: 4.62/2.02 4.62/2.02 active(f(g(X), Y)) -> mark(f(X, f(g(X), Y))) 4.62/2.02 mark(f(X1, X2)) -> active(f(mark(X1), X2)) 4.62/2.02 mark(g(X)) -> active(g(mark(X))) 4.62/2.02 f(mark(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, mark(X2)) -> f(X1, X2) 4.62/2.02 f(active(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, active(X2)) -> f(X1, X2) 4.62/2.02 g(mark(X)) -> g(X) 4.62/2.02 g(active(X)) -> g(X) 4.62/2.02 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (13) UsableRulesProof (EQUIVALENT) 4.62/2.02 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. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (14) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 F(X1, mark(X2)) -> F(X1, X2) 4.62/2.02 F(mark(X1), X2) -> F(X1, X2) 4.62/2.02 F(active(X1), X2) -> F(X1, X2) 4.62/2.02 F(X1, active(X2)) -> F(X1, X2) 4.62/2.02 4.62/2.02 R is empty. 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (15) QReductionProof (EQUIVALENT) 4.62/2.02 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.62/2.02 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (16) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 F(X1, mark(X2)) -> F(X1, X2) 4.62/2.02 F(mark(X1), X2) -> F(X1, X2) 4.62/2.02 F(active(X1), X2) -> F(X1, X2) 4.62/2.02 F(X1, active(X2)) -> F(X1, X2) 4.62/2.02 4.62/2.02 R is empty. 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (17) QDPSizeChangeProof (EQUIVALENT) 4.62/2.02 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. 4.62/2.02 4.62/2.02 From the DPs we obtained the following set of size-change graphs: 4.62/2.02 *F(X1, mark(X2)) -> F(X1, X2) 4.62/2.02 The graph contains the following edges 1 >= 1, 2 > 2 4.62/2.02 4.62/2.02 4.62/2.02 *F(mark(X1), X2) -> F(X1, X2) 4.62/2.02 The graph contains the following edges 1 > 1, 2 >= 2 4.62/2.02 4.62/2.02 4.62/2.02 *F(active(X1), X2) -> F(X1, X2) 4.62/2.02 The graph contains the following edges 1 > 1, 2 >= 2 4.62/2.02 4.62/2.02 4.62/2.02 *F(X1, active(X2)) -> F(X1, X2) 4.62/2.02 The graph contains the following edges 1 >= 1, 2 > 2 4.62/2.02 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (18) 4.62/2.02 YES 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (19) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 MARK(f(X1, X2)) -> ACTIVE(f(mark(X1), X2)) 4.62/2.02 ACTIVE(f(g(X), Y)) -> MARK(f(X, f(g(X), Y))) 4.62/2.02 MARK(f(X1, X2)) -> MARK(X1) 4.62/2.02 MARK(g(X)) -> ACTIVE(g(mark(X))) 4.62/2.02 MARK(g(X)) -> MARK(X) 4.62/2.02 4.62/2.02 The TRS R consists of the following rules: 4.62/2.02 4.62/2.02 active(f(g(X), Y)) -> mark(f(X, f(g(X), Y))) 4.62/2.02 mark(f(X1, X2)) -> active(f(mark(X1), X2)) 4.62/2.02 mark(g(X)) -> active(g(mark(X))) 4.62/2.02 f(mark(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, mark(X2)) -> f(X1, X2) 4.62/2.02 f(active(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, active(X2)) -> f(X1, X2) 4.62/2.02 g(mark(X)) -> g(X) 4.62/2.02 g(active(X)) -> g(X) 4.62/2.02 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (20) QDPOrderProof (EQUIVALENT) 4.62/2.02 We use the reduction pair processor [LPAR04,JAR06]. 4.62/2.02 4.62/2.02 4.62/2.02 The following pairs can be oriented strictly and are deleted. 4.62/2.02 4.62/2.02 ACTIVE(f(g(X), Y)) -> MARK(f(X, f(g(X), Y))) 4.62/2.02 MARK(g(X)) -> MARK(X) 4.62/2.02 The remaining pairs can at least be oriented weakly. 4.62/2.02 Used ordering: Combined order from the following AFS and order. 4.62/2.02 MARK(x1) = x1 4.62/2.02 4.62/2.02 f(x1, x2) = x1 4.62/2.02 4.62/2.02 ACTIVE(x1) = x1 4.62/2.02 4.62/2.02 mark(x1) = x1 4.62/2.02 4.62/2.02 g(x1) = g(x1) 4.62/2.02 4.62/2.02 active(x1) = x1 4.62/2.02 4.62/2.02 4.62/2.02 Knuth-Bendix order [KBO] with precedence:trivial 4.62/2.02 4.62/2.02 and weight map: 4.62/2.02 4.62/2.02 dummyConstant=1 4.62/2.02 g_1=1 4.62/2.02 4.62/2.02 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 4.62/2.02 4.62/2.02 mark(f(X1, X2)) -> active(f(mark(X1), X2)) 4.62/2.02 active(f(g(X), Y)) -> mark(f(X, f(g(X), Y))) 4.62/2.02 mark(g(X)) -> active(g(mark(X))) 4.62/2.02 f(X1, mark(X2)) -> f(X1, X2) 4.62/2.02 f(mark(X1), X2) -> f(X1, X2) 4.62/2.02 f(active(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, active(X2)) -> f(X1, X2) 4.62/2.02 g(active(X)) -> g(X) 4.62/2.02 g(mark(X)) -> g(X) 4.62/2.02 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (21) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 MARK(f(X1, X2)) -> ACTIVE(f(mark(X1), X2)) 4.62/2.02 MARK(f(X1, X2)) -> MARK(X1) 4.62/2.02 MARK(g(X)) -> ACTIVE(g(mark(X))) 4.62/2.02 4.62/2.02 The TRS R consists of the following rules: 4.62/2.02 4.62/2.02 active(f(g(X), Y)) -> mark(f(X, f(g(X), Y))) 4.62/2.02 mark(f(X1, X2)) -> active(f(mark(X1), X2)) 4.62/2.02 mark(g(X)) -> active(g(mark(X))) 4.62/2.02 f(mark(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, mark(X2)) -> f(X1, X2) 4.62/2.02 f(active(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, active(X2)) -> f(X1, X2) 4.62/2.02 g(mark(X)) -> g(X) 4.62/2.02 g(active(X)) -> g(X) 4.62/2.02 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (22) DependencyGraphProof (EQUIVALENT) 4.62/2.02 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (23) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 MARK(f(X1, X2)) -> MARK(X1) 4.62/2.02 4.62/2.02 The TRS R consists of the following rules: 4.62/2.02 4.62/2.02 active(f(g(X), Y)) -> mark(f(X, f(g(X), Y))) 4.62/2.02 mark(f(X1, X2)) -> active(f(mark(X1), X2)) 4.62/2.02 mark(g(X)) -> active(g(mark(X))) 4.62/2.02 f(mark(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, mark(X2)) -> f(X1, X2) 4.62/2.02 f(active(X1), X2) -> f(X1, X2) 4.62/2.02 f(X1, active(X2)) -> f(X1, X2) 4.62/2.02 g(mark(X)) -> g(X) 4.62/2.02 g(active(X)) -> g(X) 4.62/2.02 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (24) UsableRulesProof (EQUIVALENT) 4.62/2.02 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. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (25) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 MARK(f(X1, X2)) -> MARK(X1) 4.62/2.02 4.62/2.02 R is empty. 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (26) QReductionProof (EQUIVALENT) 4.62/2.02 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.62/2.02 4.62/2.02 active(f(g(x0), x1)) 4.62/2.02 mark(f(x0, x1)) 4.62/2.02 mark(g(x0)) 4.62/2.02 g(mark(x0)) 4.62/2.02 g(active(x0)) 4.62/2.02 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (27) 4.62/2.02 Obligation: 4.62/2.02 Q DP problem: 4.62/2.02 The TRS P consists of the following rules: 4.62/2.02 4.62/2.02 MARK(f(X1, X2)) -> MARK(X1) 4.62/2.02 4.62/2.02 R is empty. 4.62/2.02 The set Q consists of the following terms: 4.62/2.02 4.62/2.02 f(mark(x0), x1) 4.62/2.02 f(x0, mark(x1)) 4.62/2.02 f(active(x0), x1) 4.62/2.02 f(x0, active(x1)) 4.62/2.02 4.62/2.02 We have to consider all minimal (P,Q,R)-chains. 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (28) QDPSizeChangeProof (EQUIVALENT) 4.62/2.02 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. 4.62/2.02 4.62/2.02 From the DPs we obtained the following set of size-change graphs: 4.62/2.02 *MARK(f(X1, X2)) -> MARK(X1) 4.62/2.02 The graph contains the following edges 1 > 1 4.62/2.02 4.62/2.02 4.62/2.02 ---------------------------------------- 4.62/2.02 4.62/2.02 (29) 4.62/2.02 YES 4.62/2.06 EOF