3.71/1.73 YES 3.71/1.74 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.71/1.74 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.71/1.74 3.71/1.74 3.71/1.74 Quasi decreasingness of the given CTRS could be proven: 3.71/1.74 3.71/1.74 (0) CTRS 3.71/1.74 (1) CTRSToQTRSProof [SOUND, 0 ms] 3.71/1.74 (2) QTRS 3.71/1.74 (3) Overlay + Local Confluence [EQUIVALENT, 0 ms] 3.71/1.74 (4) QTRS 3.71/1.74 (5) DependencyPairsProof [EQUIVALENT, 7 ms] 3.71/1.74 (6) QDP 3.71/1.74 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 3.71/1.74 (8) AND 3.71/1.74 (9) QDP 3.71/1.74 (10) UsableRulesProof [EQUIVALENT, 0 ms] 3.71/1.74 (11) QDP 3.71/1.74 (12) QReductionProof [EQUIVALENT, 0 ms] 3.71/1.74 (13) QDP 3.71/1.74 (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] 3.71/1.74 (15) YES 3.71/1.74 (16) QDP 3.71/1.74 (17) UsableRulesProof [EQUIVALENT, 0 ms] 3.71/1.74 (18) QDP 3.71/1.74 (19) QReductionProof [EQUIVALENT, 0 ms] 3.71/1.74 (20) QDP 3.71/1.74 (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] 3.71/1.74 (22) YES 3.71/1.74 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (0) 3.71/1.74 Obligation: 3.71/1.74 Conditional term rewrite system: 3.71/1.74 The TRS R consists of the following rules: 3.71/1.74 3.71/1.74 fib(0) -> pair(0, s(0)) 3.71/1.74 3.71/1.74 The conditional TRS C consists of the following conditional rules: 3.71/1.74 3.71/1.74 plus(x, y) -> y' <= x -> 0, y -> y' 3.71/1.74 plus(x, y) -> s(plus(x', y')) <= x -> s(x'), y -> y' 3.71/1.74 fib(s(x)) -> pair(z, plus(y, z)) <= fib(x) -> pair(y, z) 3.71/1.74 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (1) CTRSToQTRSProof (SOUND) 3.71/1.74 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (2) 3.71/1.74 Obligation: 3.71/1.74 Q restricted rewrite system: 3.71/1.74 The TRS R consists of the following rules: 3.71/1.74 3.71/1.74 plus(x, y) -> U1(x, y) 3.71/1.74 U1(s(x'), y) -> U3(y, x') 3.71/1.74 U3(y', x') -> s(plus(x', y')) 3.71/1.74 U1(0, y) -> U2(y) 3.71/1.74 U2(y') -> y' 3.71/1.74 fib(s(x)) -> U4(fib(x)) 3.71/1.74 U4(pair(y, z)) -> pair(z, plus(y, z)) 3.71/1.74 fib(0) -> pair(0, s(0)) 3.71/1.74 3.71/1.74 Q is empty. 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (3) Overlay + Local Confluence (EQUIVALENT) 3.71/1.74 The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (4) 3.71/1.74 Obligation: 3.71/1.74 Q restricted rewrite system: 3.71/1.74 The TRS R consists of the following rules: 3.71/1.74 3.71/1.74 plus(x, y) -> U1(x, y) 3.71/1.74 U1(s(x'), y) -> U3(y, x') 3.71/1.74 U3(y', x') -> s(plus(x', y')) 3.71/1.74 U1(0, y) -> U2(y) 3.71/1.74 U2(y') -> y' 3.71/1.74 fib(s(x)) -> U4(fib(x)) 3.71/1.74 U4(pair(y, z)) -> pair(z, plus(y, z)) 3.71/1.74 fib(0) -> pair(0, s(0)) 3.71/1.74 3.71/1.74 The set Q consists of the following terms: 3.71/1.74 3.71/1.74 plus(x0, x1) 3.71/1.74 U1(s(x0), x1) 3.71/1.74 U3(x0, x1) 3.71/1.74 U1(0, x0) 3.71/1.74 U2(x0) 3.71/1.74 fib(s(x0)) 3.71/1.74 U4(pair(x0, x1)) 3.71/1.74 fib(0) 3.71/1.74 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (5) DependencyPairsProof (EQUIVALENT) 3.71/1.74 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (6) 3.71/1.74 Obligation: 3.71/1.74 Q DP problem: 3.71/1.74 The TRS P consists of the following rules: 3.71/1.74 3.71/1.74 PLUS(x, y) -> U1^1(x, y) 3.71/1.74 U1^1(s(x'), y) -> U3^1(y, x') 3.71/1.74 U3^1(y', x') -> PLUS(x', y') 3.71/1.74 U1^1(0, y) -> U2^1(y) 3.71/1.74 FIB(s(x)) -> U4^1(fib(x)) 3.71/1.74 FIB(s(x)) -> FIB(x) 3.71/1.74 U4^1(pair(y, z)) -> PLUS(y, z) 3.71/1.74 3.71/1.74 The TRS R consists of the following rules: 3.71/1.74 3.71/1.74 plus(x, y) -> U1(x, y) 3.71/1.74 U1(s(x'), y) -> U3(y, x') 3.71/1.74 U3(y', x') -> s(plus(x', y')) 3.71/1.74 U1(0, y) -> U2(y) 3.71/1.74 U2(y') -> y' 3.71/1.74 fib(s(x)) -> U4(fib(x)) 3.71/1.74 U4(pair(y, z)) -> pair(z, plus(y, z)) 3.71/1.74 fib(0) -> pair(0, s(0)) 3.71/1.74 3.71/1.74 The set Q consists of the following terms: 3.71/1.74 3.71/1.74 plus(x0, x1) 3.71/1.74 U1(s(x0), x1) 3.71/1.74 U3(x0, x1) 3.71/1.74 U1(0, x0) 3.71/1.74 U2(x0) 3.71/1.74 fib(s(x0)) 3.71/1.74 U4(pair(x0, x1)) 3.71/1.74 fib(0) 3.71/1.74 3.71/1.74 We have to consider all minimal (P,Q,R)-chains. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (7) DependencyGraphProof (EQUIVALENT) 3.71/1.74 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (8) 3.71/1.74 Complex Obligation (AND) 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (9) 3.71/1.74 Obligation: 3.71/1.74 Q DP problem: 3.71/1.74 The TRS P consists of the following rules: 3.71/1.74 3.71/1.74 U1^1(s(x'), y) -> U3^1(y, x') 3.71/1.74 U3^1(y', x') -> PLUS(x', y') 3.71/1.74 PLUS(x, y) -> U1^1(x, y) 3.71/1.74 3.71/1.74 The TRS R consists of the following rules: 3.71/1.74 3.71/1.74 plus(x, y) -> U1(x, y) 3.71/1.74 U1(s(x'), y) -> U3(y, x') 3.71/1.74 U3(y', x') -> s(plus(x', y')) 3.71/1.74 U1(0, y) -> U2(y) 3.71/1.74 U2(y') -> y' 3.71/1.74 fib(s(x)) -> U4(fib(x)) 3.71/1.74 U4(pair(y, z)) -> pair(z, plus(y, z)) 3.71/1.74 fib(0) -> pair(0, s(0)) 3.71/1.74 3.71/1.74 The set Q consists of the following terms: 3.71/1.74 3.71/1.74 plus(x0, x1) 3.71/1.74 U1(s(x0), x1) 3.71/1.74 U3(x0, x1) 3.71/1.74 U1(0, x0) 3.71/1.74 U2(x0) 3.71/1.74 fib(s(x0)) 3.71/1.74 U4(pair(x0, x1)) 3.71/1.74 fib(0) 3.71/1.74 3.71/1.74 We have to consider all minimal (P,Q,R)-chains. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (10) UsableRulesProof (EQUIVALENT) 3.71/1.74 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.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (11) 3.71/1.74 Obligation: 3.71/1.74 Q DP problem: 3.71/1.74 The TRS P consists of the following rules: 3.71/1.74 3.71/1.74 U1^1(s(x'), y) -> U3^1(y, x') 3.71/1.74 U3^1(y', x') -> PLUS(x', y') 3.71/1.74 PLUS(x, y) -> U1^1(x, y) 3.71/1.74 3.71/1.74 R is empty. 3.71/1.74 The set Q consists of the following terms: 3.71/1.74 3.71/1.74 plus(x0, x1) 3.71/1.74 U1(s(x0), x1) 3.71/1.74 U3(x0, x1) 3.71/1.74 U1(0, x0) 3.71/1.74 U2(x0) 3.71/1.74 fib(s(x0)) 3.71/1.74 U4(pair(x0, x1)) 3.71/1.74 fib(0) 3.71/1.74 3.71/1.74 We have to consider all minimal (P,Q,R)-chains. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (12) QReductionProof (EQUIVALENT) 3.71/1.74 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.71/1.74 3.71/1.74 plus(x0, x1) 3.71/1.74 U1(s(x0), x1) 3.71/1.74 U3(x0, x1) 3.71/1.74 U1(0, x0) 3.71/1.74 U2(x0) 3.71/1.74 fib(s(x0)) 3.71/1.74 U4(pair(x0, x1)) 3.71/1.74 fib(0) 3.71/1.74 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (13) 3.71/1.74 Obligation: 3.71/1.74 Q DP problem: 3.71/1.74 The TRS P consists of the following rules: 3.71/1.74 3.71/1.74 U1^1(s(x'), y) -> U3^1(y, x') 3.71/1.74 U3^1(y', x') -> PLUS(x', y') 3.71/1.74 PLUS(x, y) -> U1^1(x, y) 3.71/1.74 3.71/1.74 R is empty. 3.71/1.74 Q is empty. 3.71/1.74 We have to consider all minimal (P,Q,R)-chains. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (14) QDPSizeChangeProof (EQUIVALENT) 3.71/1.74 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.71/1.74 3.71/1.74 From the DPs we obtained the following set of size-change graphs: 3.71/1.74 *U3^1(y', x') -> PLUS(x', y') 3.71/1.74 The graph contains the following edges 2 >= 1, 1 >= 2 3.71/1.74 3.71/1.74 3.71/1.74 *PLUS(x, y) -> U1^1(x, y) 3.71/1.74 The graph contains the following edges 1 >= 1, 2 >= 2 3.71/1.74 3.71/1.74 3.71/1.74 *U1^1(s(x'), y) -> U3^1(y, x') 3.71/1.74 The graph contains the following edges 2 >= 1, 1 > 2 3.71/1.74 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (15) 3.71/1.74 YES 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (16) 3.71/1.74 Obligation: 3.71/1.74 Q DP problem: 3.71/1.74 The TRS P consists of the following rules: 3.71/1.74 3.71/1.74 FIB(s(x)) -> FIB(x) 3.71/1.74 3.71/1.74 The TRS R consists of the following rules: 3.71/1.74 3.71/1.74 plus(x, y) -> U1(x, y) 3.71/1.74 U1(s(x'), y) -> U3(y, x') 3.71/1.74 U3(y', x') -> s(plus(x', y')) 3.71/1.74 U1(0, y) -> U2(y) 3.71/1.74 U2(y') -> y' 3.71/1.74 fib(s(x)) -> U4(fib(x)) 3.71/1.74 U4(pair(y, z)) -> pair(z, plus(y, z)) 3.71/1.74 fib(0) -> pair(0, s(0)) 3.71/1.74 3.71/1.74 The set Q consists of the following terms: 3.71/1.74 3.71/1.74 plus(x0, x1) 3.71/1.74 U1(s(x0), x1) 3.71/1.74 U3(x0, x1) 3.71/1.74 U1(0, x0) 3.71/1.74 U2(x0) 3.71/1.74 fib(s(x0)) 3.71/1.74 U4(pair(x0, x1)) 3.71/1.74 fib(0) 3.71/1.74 3.71/1.74 We have to consider all minimal (P,Q,R)-chains. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (17) UsableRulesProof (EQUIVALENT) 3.71/1.74 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.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (18) 3.71/1.74 Obligation: 3.71/1.74 Q DP problem: 3.71/1.74 The TRS P consists of the following rules: 3.71/1.74 3.71/1.74 FIB(s(x)) -> FIB(x) 3.71/1.74 3.71/1.74 R is empty. 3.71/1.74 The set Q consists of the following terms: 3.71/1.74 3.71/1.74 plus(x0, x1) 3.71/1.74 U1(s(x0), x1) 3.71/1.74 U3(x0, x1) 3.71/1.74 U1(0, x0) 3.71/1.74 U2(x0) 3.71/1.74 fib(s(x0)) 3.71/1.74 U4(pair(x0, x1)) 3.71/1.74 fib(0) 3.71/1.74 3.71/1.74 We have to consider all minimal (P,Q,R)-chains. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (19) QReductionProof (EQUIVALENT) 3.71/1.74 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 3.71/1.74 3.71/1.74 plus(x0, x1) 3.71/1.74 U1(s(x0), x1) 3.71/1.74 U3(x0, x1) 3.71/1.74 U1(0, x0) 3.71/1.74 U2(x0) 3.71/1.74 fib(s(x0)) 3.71/1.74 U4(pair(x0, x1)) 3.71/1.74 fib(0) 3.71/1.74 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (20) 3.71/1.74 Obligation: 3.71/1.74 Q DP problem: 3.71/1.74 The TRS P consists of the following rules: 3.71/1.74 3.71/1.74 FIB(s(x)) -> FIB(x) 3.71/1.74 3.71/1.74 R is empty. 3.71/1.74 Q is empty. 3.71/1.74 We have to consider all minimal (P,Q,R)-chains. 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (21) QDPSizeChangeProof (EQUIVALENT) 3.71/1.74 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.71/1.74 3.71/1.74 From the DPs we obtained the following set of size-change graphs: 3.71/1.74 *FIB(s(x)) -> FIB(x) 3.71/1.74 The graph contains the following edges 1 > 1 3.71/1.74 3.71/1.74 3.71/1.74 ---------------------------------------- 3.71/1.74 3.71/1.74 (22) 3.71/1.74 YES 3.81/1.77 EOF