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