3.35/1.70 YES 3.35/1.70 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.35/1.70 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.35/1.70 3.35/1.70 3.35/1.70 Termination w.r.t. Q of the given QTRS could be proven: 3.35/1.70 3.35/1.70 (0) QTRS 3.35/1.70 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 3.35/1.70 (2) QDP 3.35/1.70 (3) UsableRulesProof [EQUIVALENT, 0 ms] 3.35/1.70 (4) QDP 3.35/1.70 (5) QReductionProof [EQUIVALENT, 0 ms] 3.35/1.70 (6) QDP 3.35/1.70 (7) QDPSizeChangeProof [EQUIVALENT, 0 ms] 3.35/1.70 (8) YES 3.35/1.70 3.35/1.70 3.35/1.70 ---------------------------------------- 3.35/1.70 3.35/1.70 (0) 3.35/1.70 Obligation: 3.35/1.70 Q restricted rewrite system: 3.35/1.70 The TRS R consists of the following rules: 3.35/1.70 3.35/1.70 quot(0, s(y), s(z)) -> 0 3.35/1.70 quot(s(x), s(y), z) -> quot(x, y, z) 3.35/1.70 quot(x, 0, s(z)) -> s(quot(x, s(z), s(z))) 3.35/1.70 3.35/1.70 The set Q consists of the following terms: 3.35/1.70 3.35/1.70 quot(0, s(x0), s(x1)) 3.35/1.70 quot(s(x0), s(x1), x2) 3.35/1.70 quot(x0, 0, s(x1)) 3.35/1.70 3.35/1.70 3.35/1.70 ---------------------------------------- 3.35/1.70 3.35/1.70 (1) DependencyPairsProof (EQUIVALENT) 3.35/1.70 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 3.35/1.70 ---------------------------------------- 3.35/1.70 3.35/1.70 (2) 3.35/1.70 Obligation: 3.35/1.70 Q DP problem: 3.35/1.70 The TRS P consists of the following rules: 3.35/1.70 3.35/1.70 QUOT(s(x), s(y), z) -> QUOT(x, y, z) 3.35/1.70 QUOT(x, 0, s(z)) -> QUOT(x, s(z), s(z)) 3.35/1.70 3.35/1.70 The TRS R consists of the following rules: 3.35/1.70 3.35/1.70 quot(0, s(y), s(z)) -> 0 3.35/1.70 quot(s(x), s(y), z) -> quot(x, y, z) 3.35/1.70 quot(x, 0, s(z)) -> s(quot(x, s(z), s(z))) 3.35/1.70 3.35/1.70 The set Q consists of the following terms: 3.35/1.70 3.35/1.70 quot(0, s(x0), s(x1)) 3.35/1.70 quot(s(x0), s(x1), x2) 3.35/1.70 quot(x0, 0, s(x1)) 3.35/1.70 3.35/1.70 We have to consider all minimal (P,Q,R)-chains. 3.35/1.70 ---------------------------------------- 3.35/1.70 3.35/1.70 (3) UsableRulesProof (EQUIVALENT) 3.35/1.70 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.35/1.70 ---------------------------------------- 3.35/1.70 3.35/1.70 (4) 3.35/1.70 Obligation: 3.35/1.70 Q DP problem: 3.35/1.70 The TRS P consists of the following rules: 3.35/1.70 3.35/1.70 QUOT(s(x), s(y), z) -> QUOT(x, y, z) 3.35/1.70 QUOT(x, 0, s(z)) -> QUOT(x, s(z), s(z)) 3.35/1.70 3.35/1.70 R is empty. 3.35/1.70 The set Q consists of the following terms: 3.35/1.70 3.35/1.70 quot(0, s(x0), s(x1)) 3.35/1.70 quot(s(x0), s(x1), x2) 3.35/1.70 quot(x0, 0, s(x1)) 3.35/1.71 3.35/1.71 We have to consider all minimal (P,Q,R)-chains. 3.35/1.71 ---------------------------------------- 3.35/1.71 3.35/1.71 (5) QReductionProof (EQUIVALENT) 3.35/1.71 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.35/1.71 3.35/1.71 quot(0, s(x0), s(x1)) 3.35/1.71 quot(s(x0), s(x1), x2) 3.35/1.71 quot(x0, 0, s(x1)) 3.35/1.71 3.35/1.71 3.35/1.71 ---------------------------------------- 3.35/1.71 3.35/1.71 (6) 3.35/1.71 Obligation: 3.35/1.71 Q DP problem: 3.35/1.71 The TRS P consists of the following rules: 3.35/1.71 3.35/1.71 QUOT(s(x), s(y), z) -> QUOT(x, y, z) 3.35/1.71 QUOT(x, 0, s(z)) -> QUOT(x, s(z), s(z)) 3.35/1.71 3.35/1.71 R is empty. 3.35/1.71 Q is empty. 3.35/1.71 We have to consider all minimal (P,Q,R)-chains. 3.35/1.71 ---------------------------------------- 3.35/1.71 3.35/1.71 (7) QDPSizeChangeProof (EQUIVALENT) 3.35/1.71 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.35/1.71 3.35/1.71 From the DPs we obtained the following set of size-change graphs: 3.35/1.71 *QUOT(s(x), s(y), z) -> QUOT(x, y, z) 3.35/1.71 The graph contains the following edges 1 > 1, 2 > 2, 3 >= 3 3.35/1.71 3.35/1.71 3.35/1.71 *QUOT(x, 0, s(z)) -> QUOT(x, s(z), s(z)) 3.35/1.71 The graph contains the following edges 1 >= 1, 3 >= 2, 3 >= 3 3.35/1.71 3.35/1.71 3.35/1.71 ---------------------------------------- 3.35/1.71 3.35/1.71 (8) 3.35/1.71 YES 3.58/1.74 EOF