4.79/2.05 YES 4.79/2.06 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.79/2.06 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.79/2.06 4.79/2.06 4.79/2.06 Termination w.r.t. Q of the given QTRS could be proven: 4.79/2.06 4.79/2.06 (0) QTRS 4.79/2.06 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 4.79/2.06 (2) QDP 4.79/2.06 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 4.79/2.06 (4) AND 4.79/2.06 (5) QDP 4.79/2.06 (6) UsableRulesProof [EQUIVALENT, 0 ms] 4.79/2.06 (7) QDP 4.79/2.06 (8) QReductionProof [EQUIVALENT, 0 ms] 4.79/2.06 (9) QDP 4.79/2.06 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.79/2.06 (11) YES 4.79/2.06 (12) QDP 4.79/2.06 (13) UsableRulesProof [EQUIVALENT, 0 ms] 4.79/2.06 (14) QDP 4.79/2.06 (15) QReductionProof [EQUIVALENT, 0 ms] 4.79/2.06 (16) QDP 4.79/2.06 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.79/2.06 (18) YES 4.79/2.06 (19) QDP 4.79/2.06 (20) UsableRulesProof [EQUIVALENT, 0 ms] 4.79/2.06 (21) QDP 4.79/2.06 (22) QReductionProof [EQUIVALENT, 0 ms] 4.79/2.06 (23) QDP 4.79/2.06 (24) Induction-Processor [SOUND, 5 ms] 4.79/2.06 (25) AND 4.79/2.06 (26) QDP 4.79/2.06 (27) PisEmptyProof [EQUIVALENT, 0 ms] 4.79/2.06 (28) YES 4.79/2.06 (29) QTRS 4.79/2.06 (30) QTRSRRRProof [EQUIVALENT, 2 ms] 4.79/2.06 (31) QTRS 4.79/2.06 (32) RisEmptyProof [EQUIVALENT, 0 ms] 4.79/2.06 (33) YES 4.79/2.06 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (0) 4.79/2.06 Obligation: 4.79/2.06 Q restricted rewrite system: 4.79/2.06 The TRS R consists of the following rules: 4.79/2.06 4.79/2.06 minus(x, 0) -> x 4.79/2.06 minus(s(x), s(y)) -> minus(x, y) 4.79/2.06 le(0, y) -> true 4.79/2.06 le(s(x), 0) -> false 4.79/2.06 le(s(x), s(y)) -> le(x, y) 4.79/2.06 quot(0, s(y)) -> 0 4.79/2.06 quot(s(x), s(y)) -> s(quot(minus(s(x), s(y)), s(y))) 4.79/2.06 4.79/2.06 The set Q consists of the following terms: 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (1) DependencyPairsProof (EQUIVALENT) 4.79/2.06 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (2) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 MINUS(s(x), s(y)) -> MINUS(x, y) 4.79/2.06 LE(s(x), s(y)) -> LE(x, y) 4.79/2.06 QUOT(s(x), s(y)) -> QUOT(minus(s(x), s(y)), s(y)) 4.79/2.06 QUOT(s(x), s(y)) -> MINUS(s(x), s(y)) 4.79/2.06 4.79/2.06 The TRS R consists of the following rules: 4.79/2.06 4.79/2.06 minus(x, 0) -> x 4.79/2.06 minus(s(x), s(y)) -> minus(x, y) 4.79/2.06 le(0, y) -> true 4.79/2.06 le(s(x), 0) -> false 4.79/2.06 le(s(x), s(y)) -> le(x, y) 4.79/2.06 quot(0, s(y)) -> 0 4.79/2.06 quot(s(x), s(y)) -> s(quot(minus(s(x), s(y)), s(y))) 4.79/2.06 4.79/2.06 The set Q consists of the following terms: 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (3) DependencyGraphProof (EQUIVALENT) 4.79/2.06 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 1 less node. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (4) 4.79/2.06 Complex Obligation (AND) 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (5) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 LE(s(x), s(y)) -> LE(x, y) 4.79/2.06 4.79/2.06 The TRS R consists of the following rules: 4.79/2.06 4.79/2.06 minus(x, 0) -> x 4.79/2.06 minus(s(x), s(y)) -> minus(x, y) 4.79/2.06 le(0, y) -> true 4.79/2.06 le(s(x), 0) -> false 4.79/2.06 le(s(x), s(y)) -> le(x, y) 4.79/2.06 quot(0, s(y)) -> 0 4.79/2.06 quot(s(x), s(y)) -> s(quot(minus(s(x), s(y)), s(y))) 4.79/2.06 4.79/2.06 The set Q consists of the following terms: 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (6) UsableRulesProof (EQUIVALENT) 4.79/2.06 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. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (7) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 LE(s(x), s(y)) -> LE(x, y) 4.79/2.06 4.79/2.06 R is empty. 4.79/2.06 The set Q consists of the following terms: 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (8) QReductionProof (EQUIVALENT) 4.79/2.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (9) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 LE(s(x), s(y)) -> LE(x, y) 4.79/2.06 4.79/2.06 R is empty. 4.79/2.06 Q is empty. 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (10) QDPSizeChangeProof (EQUIVALENT) 4.79/2.06 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. 4.79/2.06 4.79/2.06 From the DPs we obtained the following set of size-change graphs: 4.79/2.06 *LE(s(x), s(y)) -> LE(x, y) 4.79/2.06 The graph contains the following edges 1 > 1, 2 > 2 4.79/2.06 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (11) 4.79/2.06 YES 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (12) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 MINUS(s(x), s(y)) -> MINUS(x, y) 4.79/2.06 4.79/2.06 The TRS R consists of the following rules: 4.79/2.06 4.79/2.06 minus(x, 0) -> x 4.79/2.06 minus(s(x), s(y)) -> minus(x, y) 4.79/2.06 le(0, y) -> true 4.79/2.06 le(s(x), 0) -> false 4.79/2.06 le(s(x), s(y)) -> le(x, y) 4.79/2.06 quot(0, s(y)) -> 0 4.79/2.06 quot(s(x), s(y)) -> s(quot(minus(s(x), s(y)), s(y))) 4.79/2.06 4.79/2.06 The set Q consists of the following terms: 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (13) UsableRulesProof (EQUIVALENT) 4.79/2.06 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. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (14) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 MINUS(s(x), s(y)) -> MINUS(x, y) 4.79/2.06 4.79/2.06 R is empty. 4.79/2.06 The set Q consists of the following terms: 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (15) QReductionProof (EQUIVALENT) 4.79/2.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (16) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 MINUS(s(x), s(y)) -> MINUS(x, y) 4.79/2.06 4.79/2.06 R is empty. 4.79/2.06 Q is empty. 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (17) QDPSizeChangeProof (EQUIVALENT) 4.79/2.06 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. 4.79/2.06 4.79/2.06 From the DPs we obtained the following set of size-change graphs: 4.79/2.06 *MINUS(s(x), s(y)) -> MINUS(x, y) 4.79/2.06 The graph contains the following edges 1 > 1, 2 > 2 4.79/2.06 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (18) 4.79/2.06 YES 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (19) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 QUOT(s(x), s(y)) -> QUOT(minus(s(x), s(y)), s(y)) 4.79/2.06 4.79/2.06 The TRS R consists of the following rules: 4.79/2.06 4.79/2.06 minus(x, 0) -> x 4.79/2.06 minus(s(x), s(y)) -> minus(x, y) 4.79/2.06 le(0, y) -> true 4.79/2.06 le(s(x), 0) -> false 4.79/2.06 le(s(x), s(y)) -> le(x, y) 4.79/2.06 quot(0, s(y)) -> 0 4.79/2.06 quot(s(x), s(y)) -> s(quot(minus(s(x), s(y)), s(y))) 4.79/2.06 4.79/2.06 The set Q consists of the following terms: 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (20) UsableRulesProof (EQUIVALENT) 4.79/2.06 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. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (21) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 QUOT(s(x), s(y)) -> QUOT(minus(s(x), s(y)), s(y)) 4.79/2.06 4.79/2.06 The TRS R consists of the following rules: 4.79/2.06 4.79/2.06 minus(s(x), s(y)) -> minus(x, y) 4.79/2.06 minus(x, 0) -> x 4.79/2.06 4.79/2.06 The set Q consists of the following terms: 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (22) QReductionProof (EQUIVALENT) 4.79/2.06 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.79/2.06 4.79/2.06 le(0, x0) 4.79/2.06 le(s(x0), 0) 4.79/2.06 le(s(x0), s(x1)) 4.79/2.06 quot(0, s(x0)) 4.79/2.06 quot(s(x0), s(x1)) 4.79/2.06 4.79/2.06 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (23) 4.79/2.06 Obligation: 4.79/2.06 Q DP problem: 4.79/2.06 The TRS P consists of the following rules: 4.79/2.06 4.79/2.06 QUOT(s(x), s(y)) -> QUOT(minus(s(x), s(y)), s(y)) 4.79/2.06 4.79/2.06 The TRS R consists of the following rules: 4.79/2.06 4.79/2.06 minus(s(x), s(y)) -> minus(x, y) 4.79/2.06 minus(x, 0) -> x 4.79/2.06 4.79/2.06 The set Q consists of the following terms: 4.79/2.06 4.79/2.06 minus(x0, 0) 4.79/2.06 minus(s(x0), s(x1)) 4.79/2.06 4.79/2.06 We have to consider all minimal (P,Q,R)-chains. 4.79/2.06 ---------------------------------------- 4.79/2.06 4.79/2.06 (24) Induction-Processor (SOUND) 4.79/2.06 4.79/2.06 This DP could be deleted by the Induction-Processor: 4.79/2.06 QUOT(s(x), s(y)) -> QUOT(minus(s(x), s(y)), s(y)) 4.79/2.06 4.79/2.06 4.79/2.06 This order was computed: 4.79/2.06 Polynomial interpretation [POLO]: 4.79/2.06 4.79/2.06 POL(0) = 1 4.79/2.06 POL(QUOT(x_1, x_2)) = x_1 4.79/2.06 POL(minus(x_1, x_2)) = x_1 4.79/2.06 POL(s(x_1)) = 1 + x_1 4.79/2.06 4.79/2.06 At least one of these decreasing rules is always used after the deleted DP: 4.79/2.06 minus(s(x'), s(y')) -> minus(x', y') 4.79/2.06 4.79/2.06 4.79/2.06 The following formula is valid: 4.79/2.06 x:sort[a0],y:sort[a0].minus'(s(x), s(y))=true 4.79/2.06 4.79/2.06 4.79/2.06 The transformed set: 4.79/2.06 minus'(s(x'), s(y')) -> true 4.79/2.06 minus'(x'', 0) -> false 4.79/2.06 minus'(0, s(v4)) -> false 4.79/2.06 minus(s(x'), s(y')) -> minus(x', y') 4.79/2.06 minus(x'', 0) -> x'' 4.79/2.06 minus(0, s(v4)) -> 0 4.79/2.06 equal_bool(true, false) -> false 4.79/2.07 equal_bool(false, true) -> false 4.79/2.07 equal_bool(true, true) -> true 4.79/2.07 equal_bool(false, false) -> true 4.79/2.07 and(true, x) -> x 4.79/2.07 and(false, x) -> false 4.79/2.07 or(true, x) -> true 4.79/2.07 or(false, x) -> x 4.79/2.07 not(false) -> true 4.79/2.07 not(true) -> false 4.79/2.07 isa_true(true) -> true 4.79/2.07 isa_true(false) -> false 4.79/2.07 isa_false(true) -> false 4.79/2.07 isa_false(false) -> true 4.79/2.07 equal_sort[a0](s(v5), s(v6)) -> equal_sort[a0](v5, v6) 4.79/2.07 equal_sort[a0](s(v5), 0) -> false 4.79/2.07 equal_sort[a0](0, s(v7)) -> false 4.79/2.07 equal_sort[a0](0, 0) -> true 4.79/2.07 equal_sort[a13](witness_sort[a13], witness_sort[a13]) -> true 4.79/2.07 4.79/2.07 4.79/2.07 The proof given by the theorem prover: 4.79/2.07 The following output was given by the internal theorem prover:proof of internal 4.79/2.07 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.79/2.07 4.79/2.07 4.79/2.07 Partial correctness of the following Program 4.79/2.07 4.79/2.07 [x, v5, v6, v7, x', y', x'', v4] 4.79/2.07 equal_bool(true, false) -> false 4.79/2.07 equal_bool(false, true) -> false 4.79/2.07 equal_bool(true, true) -> true 4.79/2.07 equal_bool(false, false) -> true 4.79/2.07 true and x -> x 4.79/2.07 false and x -> false 4.79/2.07 true or x -> true 4.79/2.07 false or x -> x 4.79/2.07 not(false) -> true 4.79/2.07 not(true) -> false 4.79/2.07 isa_true(true) -> true 4.79/2.07 isa_true(false) -> false 4.79/2.07 isa_false(true) -> false 4.79/2.07 isa_false(false) -> true 4.79/2.07 equal_sort[a0](s(v5), s(v6)) -> equal_sort[a0](v5, v6) 4.79/2.07 equal_sort[a0](s(v5), 0) -> false 4.79/2.07 equal_sort[a0](0, s(v7)) -> false 4.79/2.07 equal_sort[a0](0, 0) -> true 4.79/2.07 equal_sort[a13](witness_sort[a13], witness_sort[a13]) -> true 4.79/2.07 minus'(s(x'), s(y')) -> true 4.79/2.07 minus'(x'', 0) -> false 4.79/2.07 minus'(0, s(v4)) -> false 4.79/2.07 minus(s(x'), s(y')) -> minus(x', y') 4.79/2.07 minus(x'', 0) -> x'' 4.79/2.07 minus(0, s(v4)) -> 0 4.79/2.07 4.79/2.07 using the following formula: 4.79/2.07 x:sort[a0],y:sort[a0].minus'(s(x), s(y))=true 4.79/2.07 4.79/2.07 could be successfully shown: 4.79/2.07 (0) Formula 4.79/2.07 (1) Symbolic evaluation [EQUIVALENT, 0 ms] 4.79/2.07 (2) YES 4.79/2.07 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (0) 4.79/2.07 Obligation: 4.79/2.07 Formula: 4.79/2.07 x:sort[a0],y:sort[a0].minus'(s(x), s(y))=true 4.79/2.07 4.79/2.07 There are no hypotheses. 4.79/2.07 4.79/2.07 4.79/2.07 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (1) Symbolic evaluation (EQUIVALENT) 4.79/2.07 Could be reduced to the following new obligation by simple symbolic evaluation: 4.79/2.07 True 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (2) 4.79/2.07 YES 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (25) 4.79/2.07 Complex Obligation (AND) 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (26) 4.79/2.07 Obligation: 4.79/2.07 Q DP problem: 4.79/2.07 P is empty. 4.79/2.07 The TRS R consists of the following rules: 4.79/2.07 4.79/2.07 minus(s(x), s(y)) -> minus(x, y) 4.79/2.07 minus(x, 0) -> x 4.79/2.07 4.79/2.07 The set Q consists of the following terms: 4.79/2.07 4.79/2.07 minus(x0, 0) 4.79/2.07 minus(s(x0), s(x1)) 4.79/2.07 4.79/2.07 We have to consider all minimal (P,Q,R)-chains. 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (27) PisEmptyProof (EQUIVALENT) 4.79/2.07 The TRS P is empty. Hence, there is no (P,Q,R) chain. 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (28) 4.79/2.07 YES 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (29) 4.79/2.07 Obligation: 4.79/2.07 Q restricted rewrite system: 4.79/2.07 The TRS R consists of the following rules: 4.79/2.07 4.79/2.07 minus'(s(x'), s(y')) -> true 4.79/2.07 minus'(x'', 0) -> false 4.79/2.07 minus'(0, s(v4)) -> false 4.79/2.07 minus(s(x'), s(y')) -> minus(x', y') 4.79/2.07 minus(x'', 0) -> x'' 4.79/2.07 minus(0, s(v4)) -> 0 4.79/2.07 equal_bool(true, false) -> false 4.79/2.07 equal_bool(false, true) -> false 4.79/2.07 equal_bool(true, true) -> true 4.79/2.07 equal_bool(false, false) -> true 4.79/2.07 and(true, x) -> x 4.79/2.07 and(false, x) -> false 4.79/2.07 or(true, x) -> true 4.79/2.07 or(false, x) -> x 4.79/2.07 not(false) -> true 4.79/2.07 not(true) -> false 4.79/2.07 isa_true(true) -> true 4.79/2.07 isa_true(false) -> false 4.79/2.07 isa_false(true) -> false 4.79/2.07 isa_false(false) -> true 4.79/2.07 equal_sort[a0](s(v5), s(v6)) -> equal_sort[a0](v5, v6) 4.79/2.07 equal_sort[a0](s(v5), 0) -> false 4.79/2.07 equal_sort[a0](0, s(v7)) -> false 4.79/2.07 equal_sort[a0](0, 0) -> true 4.79/2.07 equal_sort[a13](witness_sort[a13], witness_sort[a13]) -> true 4.79/2.07 4.79/2.07 Q is empty. 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (30) QTRSRRRProof (EQUIVALENT) 4.79/2.07 Used ordering: 4.79/2.07 Knuth-Bendix order [KBO] with precedence:isa_true_1 > witness_sort[a13] > equal_sort[a13]_2 > minus'_2 > equal_sort[a0]_2 > isa_false_1 > minus_2 > not_1 > or_2 > false > true > equal_bool_2 > and_2 > 0 > s_1 4.79/2.07 4.79/2.07 and weight map: 4.79/2.07 4.79/2.07 true=4 4.79/2.07 0=3 4.79/2.07 false=3 4.79/2.07 witness_sort[a13]=1 4.79/2.07 s_1=1 4.79/2.07 not_1=1 4.79/2.07 isa_true_1=0 4.79/2.07 isa_false_1=2 4.79/2.07 minus'_2=0 4.79/2.07 minus_2=0 4.79/2.07 equal_bool_2=0 4.79/2.07 and_2=0 4.79/2.07 or_2=0 4.79/2.07 equal_sort[a0]_2=0 4.79/2.07 equal_sort[a13]_2=3 4.79/2.07 4.79/2.07 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 4.79/2.07 4.79/2.07 minus'(s(x'), s(y')) -> true 4.79/2.07 minus'(x'', 0) -> false 4.79/2.07 minus'(0, s(v4)) -> false 4.79/2.07 minus(s(x'), s(y')) -> minus(x', y') 4.79/2.07 minus(x'', 0) -> x'' 4.79/2.07 minus(0, s(v4)) -> 0 4.79/2.07 equal_bool(true, false) -> false 4.79/2.07 equal_bool(false, true) -> false 4.79/2.07 equal_bool(true, true) -> true 4.79/2.07 equal_bool(false, false) -> true 4.79/2.07 and(true, x) -> x 4.79/2.07 and(false, x) -> false 4.79/2.07 or(true, x) -> true 4.79/2.07 or(false, x) -> x 4.79/2.07 not(false) -> true 4.79/2.07 not(true) -> false 4.79/2.07 isa_true(true) -> true 4.79/2.07 isa_true(false) -> false 4.79/2.07 isa_false(true) -> false 4.79/2.07 isa_false(false) -> true 4.79/2.07 equal_sort[a0](s(v5), s(v6)) -> equal_sort[a0](v5, v6) 4.79/2.07 equal_sort[a0](s(v5), 0) -> false 4.79/2.07 equal_sort[a0](0, s(v7)) -> false 4.79/2.07 equal_sort[a0](0, 0) -> true 4.79/2.07 equal_sort[a13](witness_sort[a13], witness_sort[a13]) -> true 4.79/2.07 4.79/2.07 4.79/2.07 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (31) 4.79/2.07 Obligation: 4.79/2.07 Q restricted rewrite system: 4.79/2.07 R is empty. 4.79/2.07 Q is empty. 4.79/2.07 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (32) RisEmptyProof (EQUIVALENT) 4.79/2.07 The TRS R is empty. Hence, termination is trivially proven. 4.79/2.07 ---------------------------------------- 4.79/2.07 4.79/2.07 (33) 4.79/2.07 YES 4.79/2.09 EOF