27.32/7.95 YES 27.96/7.99 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 27.96/7.99 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 27.96/7.99 27.96/7.99 27.96/7.99 Termination w.r.t. Q of the given QTRS could be proven: 27.96/7.99 27.96/7.99 (0) QTRS 27.96/7.99 (1) QTRS Reverse [EQUIVALENT, 0 ms] 27.96/7.99 (2) QTRS 27.96/7.99 (3) Overlay + Local Confluence [EQUIVALENT, 11 ms] 27.96/7.99 (4) QTRS 27.96/7.99 (5) DependencyPairsProof [EQUIVALENT, 23 ms] 27.96/7.99 (6) QDP 27.96/7.99 (7) DependencyGraphProof [EQUIVALENT, 3 ms] 27.96/7.99 (8) AND 27.96/7.99 (9) QDP 27.96/7.99 (10) UsableRulesProof [EQUIVALENT, 0 ms] 27.96/7.99 (11) QDP 27.96/7.99 (12) QReductionProof [EQUIVALENT, 0 ms] 27.96/7.99 (13) QDP 27.96/7.99 (14) QDPOrderProof [EQUIVALENT, 59 ms] 27.96/7.99 (15) QDP 27.96/7.99 (16) QDPOrderProof [EQUIVALENT, 33 ms] 27.96/7.99 (17) QDP 27.96/7.99 (18) DependencyGraphProof [EQUIVALENT, 0 ms] 27.96/7.99 (19) QDP 27.96/7.99 (20) UsableRulesProof [EQUIVALENT, 0 ms] 27.96/7.99 (21) QDP 27.96/7.99 (22) QReductionProof [EQUIVALENT, 0 ms] 27.96/7.99 (23) QDP 27.96/7.99 (24) QDPOrderProof [EQUIVALENT, 0 ms] 27.96/7.99 (25) QDP 27.96/7.99 (26) DependencyGraphProof [EQUIVALENT, 0 ms] 27.96/7.99 (27) TRUE 27.96/7.99 (28) QDP 27.96/7.99 (29) UsableRulesProof [EQUIVALENT, 0 ms] 27.96/7.99 (30) QDP 27.96/7.99 (31) QReductionProof [EQUIVALENT, 0 ms] 27.96/7.99 (32) QDP 27.96/7.99 (33) QDPOrderProof [EQUIVALENT, 76 ms] 27.96/7.99 (34) QDP 27.96/7.99 (35) UsableRulesProof [EQUIVALENT, 0 ms] 27.96/7.99 (36) QDP 27.96/7.99 (37) QReductionProof [EQUIVALENT, 0 ms] 27.96/7.99 (38) QDP 27.96/7.99 (39) QDPSizeChangeProof [EQUIVALENT, 0 ms] 27.96/7.99 (40) YES 27.96/7.99 27.96/7.99 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (0) 27.96/7.99 Obligation: 27.96/7.99 Q restricted rewrite system: 27.96/7.99 The TRS R consists of the following rules: 27.96/7.99 27.96/7.99 p(0(x1)) -> s(s(0(s(s(p(x1)))))) 27.96/7.99 p(s(0(x1))) -> 0(x1) 27.96/7.99 p(s(s(x1))) -> s(p(s(x1))) 27.96/7.99 f(s(x1)) -> g(q(i(x1))) 27.96/7.99 g(x1) -> f(p(p(x1))) 27.96/7.99 q(i(x1)) -> q(s(x1)) 27.96/7.99 q(s(x1)) -> s(s(x1)) 27.96/7.99 i(x1) -> s(x1) 27.96/7.99 27.96/7.99 Q is empty. 27.96/7.99 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (1) QTRS Reverse (EQUIVALENT) 27.96/7.99 We applied the QTRS Reverse Processor [REVERSE]. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (2) 27.96/7.99 Obligation: 27.96/7.99 Q restricted rewrite system: 27.96/7.99 The TRS R consists of the following rules: 27.96/7.99 27.96/7.99 0(p(x1)) -> p(s(s(0(s(s(x1)))))) 27.96/7.99 0(s(p(x1))) -> 0(x1) 27.96/7.99 s(s(p(x1))) -> s(p(s(x1))) 27.96/7.99 s(f(x1)) -> i(q(g(x1))) 27.96/7.99 g(x1) -> p(p(f(x1))) 27.96/7.99 i(q(x1)) -> s(q(x1)) 27.96/7.99 s(q(x1)) -> s(s(x1)) 27.96/7.99 i(x1) -> s(x1) 27.96/7.99 27.96/7.99 Q is empty. 27.96/7.99 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (3) Overlay + Local Confluence (EQUIVALENT) 27.96/7.99 The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (4) 27.96/7.99 Obligation: 27.96/7.99 Q restricted rewrite system: 27.96/7.99 The TRS R consists of the following rules: 27.96/7.99 27.96/7.99 0(p(x1)) -> p(s(s(0(s(s(x1)))))) 27.96/7.99 0(s(p(x1))) -> 0(x1) 27.96/7.99 s(s(p(x1))) -> s(p(s(x1))) 27.96/7.99 s(f(x1)) -> i(q(g(x1))) 27.96/7.99 g(x1) -> p(p(f(x1))) 27.96/7.99 i(q(x1)) -> s(q(x1)) 27.96/7.99 s(q(x1)) -> s(s(x1)) 27.96/7.99 i(x1) -> s(x1) 27.96/7.99 27.96/7.99 The set Q consists of the following terms: 27.96/7.99 27.96/7.99 0(p(x0)) 27.96/7.99 0(s(p(x0))) 27.96/7.99 s(s(p(x0))) 27.96/7.99 s(f(x0)) 27.96/7.99 g(x0) 27.96/7.99 s(q(x0)) 27.96/7.99 i(x0) 27.96/7.99 27.96/7.99 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (5) DependencyPairsProof (EQUIVALENT) 27.96/7.99 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (6) 27.96/7.99 Obligation: 27.96/7.99 Q DP problem: 27.96/7.99 The TRS P consists of the following rules: 27.96/7.99 27.96/7.99 0^1(p(x1)) -> S(s(0(s(s(x1))))) 27.96/7.99 0^1(p(x1)) -> S(0(s(s(x1)))) 27.96/7.99 0^1(p(x1)) -> 0^1(s(s(x1))) 27.96/7.99 0^1(p(x1)) -> S(s(x1)) 27.96/7.99 0^1(p(x1)) -> S(x1) 27.96/7.99 0^1(s(p(x1))) -> 0^1(x1) 27.96/7.99 S(s(p(x1))) -> S(p(s(x1))) 27.96/7.99 S(s(p(x1))) -> S(x1) 27.96/7.99 S(f(x1)) -> I(q(g(x1))) 27.96/7.99 S(f(x1)) -> G(x1) 27.96/7.99 I(q(x1)) -> S(q(x1)) 27.96/7.99 S(q(x1)) -> S(s(x1)) 27.96/7.99 S(q(x1)) -> S(x1) 27.96/7.99 I(x1) -> S(x1) 27.96/7.99 27.96/7.99 The TRS R consists of the following rules: 27.96/7.99 27.96/7.99 0(p(x1)) -> p(s(s(0(s(s(x1)))))) 27.96/7.99 0(s(p(x1))) -> 0(x1) 27.96/7.99 s(s(p(x1))) -> s(p(s(x1))) 27.96/7.99 s(f(x1)) -> i(q(g(x1))) 27.96/7.99 g(x1) -> p(p(f(x1))) 27.96/7.99 i(q(x1)) -> s(q(x1)) 27.96/7.99 s(q(x1)) -> s(s(x1)) 27.96/7.99 i(x1) -> s(x1) 27.96/7.99 27.96/7.99 The set Q consists of the following terms: 27.96/7.99 27.96/7.99 0(p(x0)) 27.96/7.99 0(s(p(x0))) 27.96/7.99 s(s(p(x0))) 27.96/7.99 s(f(x0)) 27.96/7.99 g(x0) 27.96/7.99 s(q(x0)) 27.96/7.99 i(x0) 27.96/7.99 27.96/7.99 We have to consider all minimal (P,Q,R)-chains. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (7) DependencyGraphProof (EQUIVALENT) 27.96/7.99 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 6 less nodes. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (8) 27.96/7.99 Complex Obligation (AND) 27.96/7.99 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (9) 27.96/7.99 Obligation: 27.96/7.99 Q DP problem: 27.96/7.99 The TRS P consists of the following rules: 27.96/7.99 27.96/7.99 S(f(x1)) -> I(q(g(x1))) 27.96/7.99 I(q(x1)) -> S(q(x1)) 27.96/7.99 S(q(x1)) -> S(s(x1)) 27.96/7.99 S(s(p(x1))) -> S(x1) 27.96/7.99 S(q(x1)) -> S(x1) 27.96/7.99 I(x1) -> S(x1) 27.96/7.99 27.96/7.99 The TRS R consists of the following rules: 27.96/7.99 27.96/7.99 0(p(x1)) -> p(s(s(0(s(s(x1)))))) 27.96/7.99 0(s(p(x1))) -> 0(x1) 27.96/7.99 s(s(p(x1))) -> s(p(s(x1))) 27.96/7.99 s(f(x1)) -> i(q(g(x1))) 27.96/7.99 g(x1) -> p(p(f(x1))) 27.96/7.99 i(q(x1)) -> s(q(x1)) 27.96/7.99 s(q(x1)) -> s(s(x1)) 27.96/7.99 i(x1) -> s(x1) 27.96/7.99 27.96/7.99 The set Q consists of the following terms: 27.96/7.99 27.96/7.99 0(p(x0)) 27.96/7.99 0(s(p(x0))) 27.96/7.99 s(s(p(x0))) 27.96/7.99 s(f(x0)) 27.96/7.99 g(x0) 27.96/7.99 s(q(x0)) 27.96/7.99 i(x0) 27.96/7.99 27.96/7.99 We have to consider all minimal (P,Q,R)-chains. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (10) UsableRulesProof (EQUIVALENT) 27.96/7.99 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. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (11) 27.96/7.99 Obligation: 27.96/7.99 Q DP problem: 27.96/7.99 The TRS P consists of the following rules: 27.96/7.99 27.96/7.99 S(f(x1)) -> I(q(g(x1))) 27.96/7.99 I(q(x1)) -> S(q(x1)) 27.96/7.99 S(q(x1)) -> S(s(x1)) 27.96/7.99 S(s(p(x1))) -> S(x1) 27.96/7.99 S(q(x1)) -> S(x1) 27.96/7.99 I(x1) -> S(x1) 27.96/7.99 27.96/7.99 The TRS R consists of the following rules: 27.96/7.99 27.96/7.99 s(s(p(x1))) -> s(p(s(x1))) 27.96/7.99 s(f(x1)) -> i(q(g(x1))) 27.96/7.99 i(q(x1)) -> s(q(x1)) 27.96/7.99 s(q(x1)) -> s(s(x1)) 27.96/7.99 i(x1) -> s(x1) 27.96/7.99 g(x1) -> p(p(f(x1))) 27.96/7.99 27.96/7.99 The set Q consists of the following terms: 27.96/7.99 27.96/7.99 0(p(x0)) 27.96/7.99 0(s(p(x0))) 27.96/7.99 s(s(p(x0))) 27.96/7.99 s(f(x0)) 27.96/7.99 g(x0) 27.96/7.99 s(q(x0)) 27.96/7.99 i(x0) 27.96/7.99 27.96/7.99 We have to consider all minimal (P,Q,R)-chains. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (12) QReductionProof (EQUIVALENT) 27.96/7.99 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 27.96/7.99 27.96/7.99 0(p(x0)) 27.96/7.99 0(s(p(x0))) 27.96/7.99 27.96/7.99 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (13) 27.96/7.99 Obligation: 27.96/7.99 Q DP problem: 27.96/7.99 The TRS P consists of the following rules: 27.96/7.99 27.96/7.99 S(f(x1)) -> I(q(g(x1))) 27.96/7.99 I(q(x1)) -> S(q(x1)) 27.96/7.99 S(q(x1)) -> S(s(x1)) 27.96/7.99 S(s(p(x1))) -> S(x1) 27.96/7.99 S(q(x1)) -> S(x1) 27.96/7.99 I(x1) -> S(x1) 27.96/7.99 27.96/7.99 The TRS R consists of the following rules: 27.96/7.99 27.96/7.99 s(s(p(x1))) -> s(p(s(x1))) 27.96/7.99 s(f(x1)) -> i(q(g(x1))) 27.96/7.99 i(q(x1)) -> s(q(x1)) 27.96/7.99 s(q(x1)) -> s(s(x1)) 27.96/7.99 i(x1) -> s(x1) 27.96/7.99 g(x1) -> p(p(f(x1))) 27.96/7.99 27.96/7.99 The set Q consists of the following terms: 27.96/7.99 27.96/7.99 s(s(p(x0))) 27.96/7.99 s(f(x0)) 27.96/7.99 g(x0) 27.96/7.99 s(q(x0)) 27.96/7.99 i(x0) 27.96/7.99 27.96/7.99 We have to consider all minimal (P,Q,R)-chains. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (14) QDPOrderProof (EQUIVALENT) 27.96/7.99 We use the reduction pair processor [LPAR04,JAR06]. 27.96/7.99 27.96/7.99 27.96/7.99 The following pairs can be oriented strictly and are deleted. 27.96/7.99 27.96/7.99 S(q(x1)) -> S(x1) 27.96/7.99 The remaining pairs can at least be oriented weakly. 27.96/7.99 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 27.96/7.99 27.96/7.99 POL( I_1(x_1) ) = 2x_1 + 2 27.96/7.99 POL( q_1(x_1) ) = x_1 + 2 27.96/7.99 POL( S_1(x_1) ) = 2x_1 + 2 27.96/7.99 POL( i_1(x_1) ) = x_1 + 2 27.96/7.99 POL( g_1(x_1) ) = 0 27.96/7.99 POL( p_1(x_1) ) = max{0, x_1 - 2} 27.96/7.99 POL( f_1(x_1) ) = 2 27.96/7.99 POL( s_1(x_1) ) = x_1 + 2 27.96/7.99 27.96/7.99 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 27.96/7.99 27.96/7.99 g(x1) -> p(p(f(x1))) 27.96/7.99 s(s(p(x1))) -> s(p(s(x1))) 27.96/7.99 s(f(x1)) -> i(q(g(x1))) 27.96/7.99 i(q(x1)) -> s(q(x1)) 27.96/7.99 s(q(x1)) -> s(s(x1)) 27.96/7.99 i(x1) -> s(x1) 27.96/7.99 27.96/7.99 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (15) 27.96/7.99 Obligation: 27.96/7.99 Q DP problem: 27.96/7.99 The TRS P consists of the following rules: 27.96/7.99 27.96/7.99 S(f(x1)) -> I(q(g(x1))) 27.96/7.99 I(q(x1)) -> S(q(x1)) 27.96/7.99 S(q(x1)) -> S(s(x1)) 27.96/7.99 S(s(p(x1))) -> S(x1) 27.96/7.99 I(x1) -> S(x1) 27.96/7.99 27.96/7.99 The TRS R consists of the following rules: 27.96/7.99 27.96/7.99 s(s(p(x1))) -> s(p(s(x1))) 27.96/7.99 s(f(x1)) -> i(q(g(x1))) 27.96/7.99 i(q(x1)) -> s(q(x1)) 27.96/7.99 s(q(x1)) -> s(s(x1)) 27.96/7.99 i(x1) -> s(x1) 27.96/7.99 g(x1) -> p(p(f(x1))) 27.96/7.99 27.96/7.99 The set Q consists of the following terms: 27.96/7.99 27.96/7.99 s(s(p(x0))) 27.96/7.99 s(f(x0)) 27.96/7.99 g(x0) 27.96/7.99 s(q(x0)) 27.96/7.99 i(x0) 27.96/7.99 27.96/7.99 We have to consider all minimal (P,Q,R)-chains. 27.96/7.99 ---------------------------------------- 27.96/7.99 27.96/7.99 (16) QDPOrderProof (EQUIVALENT) 27.96/7.99 We use the reduction pair processor [LPAR04,JAR06]. 27.96/7.99 27.96/7.99 27.96/7.99 The following pairs can be oriented strictly and are deleted. 27.96/7.99 27.96/8.01 S(s(p(x1))) -> S(x1) 27.96/8.01 The remaining pairs can at least be oriented weakly. 27.96/8.01 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 27.96/8.01 27.96/8.01 POL( I_1(x_1) ) = 2x_1 27.96/8.01 POL( q_1(x_1) ) = 2x_1 + 2 27.96/8.01 POL( S_1(x_1) ) = 2x_1 27.96/8.01 POL( i_1(x_1) ) = x_1 + 2 27.96/8.01 POL( g_1(x_1) ) = 0 27.96/8.01 POL( p_1(x_1) ) = max{0, x_1 - 1} 27.96/8.01 POL( f_1(x_1) ) = 2 27.96/8.01 POL( s_1(x_1) ) = x_1 + 2 27.96/8.01 27.96/8.01 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 27.96/8.01 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 s(s(p(x1))) -> s(p(s(x1))) 27.96/8.01 s(f(x1)) -> i(q(g(x1))) 27.96/8.01 i(q(x1)) -> s(q(x1)) 27.96/8.01 s(q(x1)) -> s(s(x1)) 27.96/8.01 i(x1) -> s(x1) 27.96/8.01 27.96/8.01 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (17) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 S(f(x1)) -> I(q(g(x1))) 27.96/8.01 I(q(x1)) -> S(q(x1)) 27.96/8.01 S(q(x1)) -> S(s(x1)) 27.96/8.01 I(x1) -> S(x1) 27.96/8.01 27.96/8.01 The TRS R consists of the following rules: 27.96/8.01 27.96/8.01 s(s(p(x1))) -> s(p(s(x1))) 27.96/8.01 s(f(x1)) -> i(q(g(x1))) 27.96/8.01 i(q(x1)) -> s(q(x1)) 27.96/8.01 s(q(x1)) -> s(s(x1)) 27.96/8.01 i(x1) -> s(x1) 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 g(x0) 27.96/8.01 s(q(x0)) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (18) DependencyGraphProof (EQUIVALENT) 27.96/8.01 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (19) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 I(x1) -> S(x1) 27.96/8.01 S(f(x1)) -> I(q(g(x1))) 27.96/8.01 27.96/8.01 The TRS R consists of the following rules: 27.96/8.01 27.96/8.01 s(s(p(x1))) -> s(p(s(x1))) 27.96/8.01 s(f(x1)) -> i(q(g(x1))) 27.96/8.01 i(q(x1)) -> s(q(x1)) 27.96/8.01 s(q(x1)) -> s(s(x1)) 27.96/8.01 i(x1) -> s(x1) 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 g(x0) 27.96/8.01 s(q(x0)) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (20) UsableRulesProof (EQUIVALENT) 27.96/8.01 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. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (21) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 I(x1) -> S(x1) 27.96/8.01 S(f(x1)) -> I(q(g(x1))) 27.96/8.01 27.96/8.01 The TRS R consists of the following rules: 27.96/8.01 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 g(x0) 27.96/8.01 s(q(x0)) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (22) QReductionProof (EQUIVALENT) 27.96/8.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 27.96/8.01 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 s(q(x0)) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (23) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 I(x1) -> S(x1) 27.96/8.01 S(f(x1)) -> I(q(g(x1))) 27.96/8.01 27.96/8.01 The TRS R consists of the following rules: 27.96/8.01 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 g(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (24) QDPOrderProof (EQUIVALENT) 27.96/8.01 We use the reduction pair processor [LPAR04,JAR06]. 27.96/8.01 27.96/8.01 27.96/8.01 The following pairs can be oriented strictly and are deleted. 27.96/8.01 27.96/8.01 S(f(x1)) -> I(q(g(x1))) 27.96/8.01 The remaining pairs can at least be oriented weakly. 27.96/8.01 Used ordering: Polynomial interpretation [POLO]: 27.96/8.01 27.96/8.01 POL(I(x_1)) = 1 + x_1 27.96/8.01 POL(S(x_1)) = 1 + x_1 27.96/8.01 POL(f(x_1)) = 1 + x_1 27.96/8.01 POL(g(x_1)) = 1 + x_1 27.96/8.01 POL(p(x_1)) = 1 27.96/8.01 POL(q(x_1)) = 0 27.96/8.01 27.96/8.01 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 27.96/8.01 none 27.96/8.01 27.96/8.01 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (25) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 I(x1) -> S(x1) 27.96/8.01 27.96/8.01 The TRS R consists of the following rules: 27.96/8.01 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 g(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (26) DependencyGraphProof (EQUIVALENT) 27.96/8.01 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (27) 27.96/8.01 TRUE 27.96/8.01 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (28) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 0^1(s(p(x1))) -> 0^1(x1) 27.96/8.01 0^1(p(x1)) -> 0^1(s(s(x1))) 27.96/8.01 27.96/8.01 The TRS R consists of the following rules: 27.96/8.01 27.96/8.01 0(p(x1)) -> p(s(s(0(s(s(x1)))))) 27.96/8.01 0(s(p(x1))) -> 0(x1) 27.96/8.01 s(s(p(x1))) -> s(p(s(x1))) 27.96/8.01 s(f(x1)) -> i(q(g(x1))) 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 i(q(x1)) -> s(q(x1)) 27.96/8.01 s(q(x1)) -> s(s(x1)) 27.96/8.01 i(x1) -> s(x1) 27.96/8.01 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 0(p(x0)) 27.96/8.01 0(s(p(x0))) 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 g(x0) 27.96/8.01 s(q(x0)) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (29) UsableRulesProof (EQUIVALENT) 27.96/8.01 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. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (30) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 0^1(s(p(x1))) -> 0^1(x1) 27.96/8.01 0^1(p(x1)) -> 0^1(s(s(x1))) 27.96/8.01 27.96/8.01 The TRS R consists of the following rules: 27.96/8.01 27.96/8.01 s(s(p(x1))) -> s(p(s(x1))) 27.96/8.01 s(f(x1)) -> i(q(g(x1))) 27.96/8.01 i(q(x1)) -> s(q(x1)) 27.96/8.01 s(q(x1)) -> s(s(x1)) 27.96/8.01 i(x1) -> s(x1) 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 0(p(x0)) 27.96/8.01 0(s(p(x0))) 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 g(x0) 27.96/8.01 s(q(x0)) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (31) QReductionProof (EQUIVALENT) 27.96/8.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 27.96/8.01 27.96/8.01 0(p(x0)) 27.96/8.01 0(s(p(x0))) 27.96/8.01 27.96/8.01 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (32) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 0^1(s(p(x1))) -> 0^1(x1) 27.96/8.01 0^1(p(x1)) -> 0^1(s(s(x1))) 27.96/8.01 27.96/8.01 The TRS R consists of the following rules: 27.96/8.01 27.96/8.01 s(s(p(x1))) -> s(p(s(x1))) 27.96/8.01 s(f(x1)) -> i(q(g(x1))) 27.96/8.01 i(q(x1)) -> s(q(x1)) 27.96/8.01 s(q(x1)) -> s(s(x1)) 27.96/8.01 i(x1) -> s(x1) 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 g(x0) 27.96/8.01 s(q(x0)) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (33) QDPOrderProof (EQUIVALENT) 27.96/8.01 We use the reduction pair processor [LPAR04,JAR06]. 27.96/8.01 27.96/8.01 27.96/8.01 The following pairs can be oriented strictly and are deleted. 27.96/8.01 27.96/8.01 0^1(p(x1)) -> 0^1(s(s(x1))) 27.96/8.01 The remaining pairs can at least be oriented weakly. 27.96/8.01 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 27.96/8.01 27.96/8.01 <<< 27.96/8.01 POL(0^1(x_1)) = [[0A]] + [[0A, 0A, 0A]] * x_1 27.96/8.01 >>> 27.96/8.01 27.96/8.01 <<< 27.96/8.01 POL(s(x_1)) = [[0A], [0A], [0A]] + [[-I, 0A, -I], [-I, 0A, -I], [0A, 0A, -I]] * x_1 27.96/8.01 >>> 27.96/8.01 27.96/8.01 <<< 27.96/8.01 POL(p(x_1)) = [[0A], [0A], [1A]] + [[0A, 0A, 0A], [0A, 0A, -I], [0A, 1A, 0A]] * x_1 27.96/8.01 >>> 27.96/8.01 27.96/8.01 <<< 27.96/8.01 POL(f(x_1)) = [[0A], [0A], [0A]] + [[0A, -I, -I], [0A, -I, -I], [0A, -I, -I]] * x_1 27.96/8.01 >>> 27.96/8.01 27.96/8.01 <<< 27.96/8.01 POL(i(x_1)) = [[0A], [0A], [0A]] + [[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, 0A]] * x_1 27.96/8.01 >>> 27.96/8.01 27.96/8.01 <<< 27.96/8.01 POL(q(x_1)) = [[0A], [0A], [-I]] + [[-I, -I, -I], [-I, 0A, -I], [-I, -I, -I]] * x_1 27.96/8.01 >>> 27.96/8.01 27.96/8.01 <<< 27.96/8.01 POL(g(x_1)) = [[1A], [0A], [1A]] + [[1A, 0A, 0A], [0A, -I, -I], [1A, 0A, 0A]] * x_1 27.96/8.01 >>> 27.96/8.01 27.96/8.01 27.96/8.01 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 27.96/8.01 27.96/8.01 s(s(p(x1))) -> s(p(s(x1))) 27.96/8.01 s(f(x1)) -> i(q(g(x1))) 27.96/8.01 i(q(x1)) -> s(q(x1)) 27.96/8.01 s(q(x1)) -> s(s(x1)) 27.96/8.01 i(x1) -> s(x1) 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 27.96/8.01 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (34) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 0^1(s(p(x1))) -> 0^1(x1) 27.96/8.01 27.96/8.01 The TRS R consists of the following rules: 27.96/8.01 27.96/8.01 s(s(p(x1))) -> s(p(s(x1))) 27.96/8.01 s(f(x1)) -> i(q(g(x1))) 27.96/8.01 i(q(x1)) -> s(q(x1)) 27.96/8.01 s(q(x1)) -> s(s(x1)) 27.96/8.01 i(x1) -> s(x1) 27.96/8.01 g(x1) -> p(p(f(x1))) 27.96/8.01 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 g(x0) 27.96/8.01 s(q(x0)) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (35) UsableRulesProof (EQUIVALENT) 27.96/8.01 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. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (36) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 0^1(s(p(x1))) -> 0^1(x1) 27.96/8.01 27.96/8.01 R is empty. 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 g(x0) 27.96/8.01 s(q(x0)) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (37) QReductionProof (EQUIVALENT) 27.96/8.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 27.96/8.01 27.96/8.01 g(x0) 27.96/8.01 i(x0) 27.96/8.01 27.96/8.01 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (38) 27.96/8.01 Obligation: 27.96/8.01 Q DP problem: 27.96/8.01 The TRS P consists of the following rules: 27.96/8.01 27.96/8.01 0^1(s(p(x1))) -> 0^1(x1) 27.96/8.01 27.96/8.01 R is empty. 27.96/8.01 The set Q consists of the following terms: 27.96/8.01 27.96/8.01 s(s(p(x0))) 27.96/8.01 s(f(x0)) 27.96/8.01 s(q(x0)) 27.96/8.01 27.96/8.01 We have to consider all minimal (P,Q,R)-chains. 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (39) QDPSizeChangeProof (EQUIVALENT) 27.96/8.01 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. 27.96/8.01 27.96/8.01 From the DPs we obtained the following set of size-change graphs: 27.96/8.01 *0^1(s(p(x1))) -> 0^1(x1) 27.96/8.01 The graph contains the following edges 1 > 1 27.96/8.01 27.96/8.01 27.96/8.01 ---------------------------------------- 27.96/8.01 27.96/8.01 (40) 27.96/8.01 YES 28.22/8.09 EOF