3.29/1.61 YES 3.29/1.61 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.29/1.61 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.29/1.61 3.29/1.61 3.29/1.61 Termination w.r.t. Q of the given QTRS could be proven: 3.29/1.61 3.29/1.61 (0) QTRS 3.29/1.61 (1) DependencyPairsProof [EQUIVALENT, 8 ms] 3.29/1.61 (2) QDP 3.29/1.61 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 3.29/1.61 (4) QDP 3.29/1.61 (5) UsableRulesProof [EQUIVALENT, 0 ms] 3.29/1.61 (6) QDP 3.29/1.61 (7) QReductionProof [EQUIVALENT, 0 ms] 3.29/1.61 (8) QDP 3.29/1.61 (9) TransformationProof [EQUIVALENT, 0 ms] 3.29/1.61 (10) QDP 3.29/1.61 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 3.29/1.61 (12) TRUE 3.29/1.61 3.29/1.61 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (0) 3.29/1.61 Obligation: 3.29/1.61 Q restricted rewrite system: 3.29/1.61 The TRS R consists of the following rules: 3.29/1.61 3.29/1.61 f(x, x) -> f(g(x), x) 3.29/1.61 g(x) -> s(x) 3.29/1.61 3.29/1.61 The set Q consists of the following terms: 3.29/1.61 3.29/1.61 f(x0, x0) 3.29/1.61 g(x0) 3.29/1.61 3.29/1.61 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (1) DependencyPairsProof (EQUIVALENT) 3.29/1.61 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (2) 3.29/1.61 Obligation: 3.29/1.61 Q DP problem: 3.29/1.61 The TRS P consists of the following rules: 3.29/1.61 3.29/1.61 F(x, x) -> F(g(x), x) 3.29/1.61 F(x, x) -> G(x) 3.29/1.61 3.29/1.61 The TRS R consists of the following rules: 3.29/1.61 3.29/1.61 f(x, x) -> f(g(x), x) 3.29/1.61 g(x) -> s(x) 3.29/1.61 3.29/1.61 The set Q consists of the following terms: 3.29/1.61 3.29/1.61 f(x0, x0) 3.29/1.61 g(x0) 3.29/1.61 3.29/1.61 We have to consider all minimal (P,Q,R)-chains. 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (3) DependencyGraphProof (EQUIVALENT) 3.29/1.61 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (4) 3.29/1.61 Obligation: 3.29/1.61 Q DP problem: 3.29/1.61 The TRS P consists of the following rules: 3.29/1.61 3.29/1.61 F(x, x) -> F(g(x), x) 3.29/1.61 3.29/1.61 The TRS R consists of the following rules: 3.29/1.61 3.29/1.61 f(x, x) -> f(g(x), x) 3.29/1.61 g(x) -> s(x) 3.29/1.61 3.29/1.61 The set Q consists of the following terms: 3.29/1.61 3.29/1.61 f(x0, x0) 3.29/1.61 g(x0) 3.29/1.61 3.29/1.61 We have to consider all minimal (P,Q,R)-chains. 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (5) UsableRulesProof (EQUIVALENT) 3.29/1.61 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.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (6) 3.29/1.61 Obligation: 3.29/1.61 Q DP problem: 3.29/1.61 The TRS P consists of the following rules: 3.29/1.61 3.29/1.61 F(x, x) -> F(g(x), x) 3.29/1.61 3.29/1.61 The TRS R consists of the following rules: 3.29/1.61 3.29/1.61 g(x) -> s(x) 3.29/1.61 3.29/1.61 The set Q consists of the following terms: 3.29/1.61 3.29/1.61 f(x0, x0) 3.29/1.61 g(x0) 3.29/1.61 3.29/1.61 We have to consider all minimal (P,Q,R)-chains. 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (7) QReductionProof (EQUIVALENT) 3.29/1.61 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.29/1.61 3.29/1.61 f(x0, x0) 3.29/1.61 3.29/1.61 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (8) 3.29/1.61 Obligation: 3.29/1.61 Q DP problem: 3.29/1.61 The TRS P consists of the following rules: 3.29/1.61 3.29/1.61 F(x, x) -> F(g(x), x) 3.29/1.61 3.29/1.61 The TRS R consists of the following rules: 3.29/1.61 3.29/1.61 g(x) -> s(x) 3.29/1.61 3.29/1.61 The set Q consists of the following terms: 3.29/1.61 3.29/1.61 g(x0) 3.29/1.61 3.29/1.61 We have to consider all minimal (P,Q,R)-chains. 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (9) TransformationProof (EQUIVALENT) 3.29/1.61 By rewriting [LPAR04] the rule F(x, x) -> F(g(x), x) at position [0] we obtained the following new rules [LPAR04]: 3.29/1.61 3.29/1.61 (F(x, x) -> F(s(x), x),F(x, x) -> F(s(x), x)) 3.29/1.61 3.29/1.61 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (10) 3.29/1.61 Obligation: 3.29/1.61 Q DP problem: 3.29/1.61 The TRS P consists of the following rules: 3.29/1.61 3.29/1.61 F(x, x) -> F(s(x), x) 3.29/1.61 3.29/1.61 The TRS R consists of the following rules: 3.29/1.61 3.29/1.61 g(x) -> s(x) 3.29/1.61 3.29/1.61 The set Q consists of the following terms: 3.29/1.61 3.29/1.61 g(x0) 3.29/1.61 3.29/1.61 We have to consider all minimal (P,Q,R)-chains. 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (11) DependencyGraphProof (EQUIVALENT) 3.29/1.61 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 3.29/1.61 ---------------------------------------- 3.29/1.61 3.29/1.61 (12) 3.29/1.61 TRUE 3.42/1.63 EOF