/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) Overlay + Local Confluence [EQUIVALENT, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QReductionProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) QDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) QDP (17) QReductionProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) QDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) QDP (24) QReductionProof [EQUIVALENT, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [EQUIVALENT, 0 ms] (36) QDP (37) DependencyGraphProof [EQUIVALENT, 0 ms] (38) QDP (39) TransformationProof [EQUIVALENT, 0 ms] (40) QDP (41) DependencyGraphProof [EQUIVALENT, 0 ms] (42) QDP (43) TransformationProof [EQUIVALENT, 0 ms] (44) QDP (45) TransformationProof [EQUIVALENT, 0 ms] (46) QDP (47) TransformationProof [EQUIVALENT, 0 ms] (48) QDP (49) TransformationProof [EQUIVALENT, 0 ms] (50) QDP (51) TransformationProof [EQUIVALENT, 0 ms] (52) QDP (53) TransformationProof [EQUIVALENT, 0 ms] (54) QDP (55) TransformationProof [EQUIVALENT, 0 ms] (56) QDP (57) TransformationProof [EQUIVALENT, 0 ms] (58) QDP (59) Induction-Processor [SOUND, 25 ms] (60) AND (61) QDP (62) DependencyGraphProof [EQUIVALENT, 0 ms] (63) QDP (64) Induction-Processor [SOUND, 23 ms] (65) AND (66) QDP (67) DependencyGraphProof [EQUIVALENT, 0 ms] (68) TRUE (69) QTRS (70) QTRSRRRProof [EQUIVALENT, 45 ms] (71) QTRS (72) RisEmptyProof [EQUIVALENT, 0 ms] (73) YES (74) QTRS (75) QTRSRRRProof [EQUIVALENT, 36 ms] (76) QTRS (77) QTRSRRRProof [EQUIVALENT, 0 ms] (78) QTRS (79) RisEmptyProof [EQUIVALENT, 0 ms] (80) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gcd(x, y) -> if1(ge(x, y), x, y) if1(true, x, y) -> if2(gt(y, 0), x, y) if1(false, x, y) -> if3(gt(x, 0), x, y) if2(true, x, y) -> gcd(minus(x, y), y) if2(false, x, y) -> x if3(true, x, y) -> gcd(x, minus(y, x)) if3(false, x, y) -> y gt(0, y) -> false gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) Q is empty. ---------------------------------------- (1) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gcd(x, y) -> if1(ge(x, y), x, y) if1(true, x, y) -> if2(gt(y, 0), x, y) if1(false, x, y) -> if3(gt(x, 0), x, y) if2(true, x, y) -> gcd(minus(x, y), y) if2(false, x, y) -> x if3(true, x, y) -> gcd(x, minus(y, x)) if3(false, x, y) -> y gt(0, y) -> false gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(s(x), y) -> IF(gt(s(x), y), x, y) MINUS(s(x), y) -> GT(s(x), y) IF(true, x, y) -> MINUS(x, y) GCD(x, y) -> IF1(ge(x, y), x, y) GCD(x, y) -> GE(x, y) IF1(true, x, y) -> IF2(gt(y, 0), x, y) IF1(true, x, y) -> GT(y, 0) IF1(false, x, y) -> IF3(gt(x, 0), x, y) IF1(false, x, y) -> GT(x, 0) IF2(true, x, y) -> GCD(minus(x, y), y) IF2(true, x, y) -> MINUS(x, y) IF3(true, x, y) -> GCD(x, minus(y, x)) IF3(true, x, y) -> MINUS(y, x) GT(s(x), s(y)) -> GT(x, y) GE(s(x), s(y)) -> GE(x, y) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gcd(x, y) -> if1(ge(x, y), x, y) if1(true, x, y) -> if2(gt(y, 0), x, y) if1(false, x, y) -> if3(gt(x, 0), x, y) if2(true, x, y) -> gcd(minus(x, y), y) if2(false, x, y) -> x if3(true, x, y) -> gcd(x, minus(y, x)) if3(false, x, y) -> y gt(0, y) -> false gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 6 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: GE(s(x), s(y)) -> GE(x, y) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gcd(x, y) -> if1(ge(x, y), x, y) if1(true, x, y) -> if2(gt(y, 0), x, y) if1(false, x, y) -> if3(gt(x, 0), x, y) if2(true, x, y) -> gcd(minus(x, y), y) if2(false, x, y) -> x if3(true, x, y) -> gcd(x, minus(y, x)) if3(false, x, y) -> y gt(0, y) -> false gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: GE(s(x), s(y)) -> GE(x, y) R is empty. The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: GE(s(x), s(y)) -> GE(x, y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *GE(s(x), s(y)) -> GE(x, y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: GT(s(x), s(y)) -> GT(x, y) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gcd(x, y) -> if1(ge(x, y), x, y) if1(true, x, y) -> if2(gt(y, 0), x, y) if1(false, x, y) -> if3(gt(x, 0), x, y) if2(true, x, y) -> gcd(minus(x, y), y) if2(false, x, y) -> x if3(true, x, y) -> gcd(x, minus(y, x)) if3(false, x, y) -> y gt(0, y) -> false gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: GT(s(x), s(y)) -> GT(x, y) R is empty. The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: GT(s(x), s(y)) -> GT(x, y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *GT(s(x), s(y)) -> GT(x, y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: IF(true, x, y) -> MINUS(x, y) MINUS(s(x), y) -> IF(gt(s(x), y), x, y) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gcd(x, y) -> if1(ge(x, y), x, y) if1(true, x, y) -> if2(gt(y, 0), x, y) if1(false, x, y) -> if3(gt(x, 0), x, y) if2(true, x, y) -> gcd(minus(x, y), y) if2(false, x, y) -> x if3(true, x, y) -> gcd(x, minus(y, x)) if3(false, x, y) -> y gt(0, y) -> false gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: IF(true, x, y) -> MINUS(x, y) MINUS(s(x), y) -> IF(gt(s(x), y), x, y) The TRS R consists of the following rules: gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) gt(0, y) -> false The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: IF(true, x, y) -> MINUS(x, y) MINUS(s(x), y) -> IF(gt(s(x), y), x, y) The TRS R consists of the following rules: gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) gt(0, y) -> false The set Q consists of the following terms: gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *MINUS(s(x), y) -> IF(gt(s(x), y), x, y) The graph contains the following edges 1 > 2, 2 >= 3 *IF(true, x, y) -> MINUS(x, y) The graph contains the following edges 2 >= 1, 3 >= 2 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(true, x, y) -> GCD(minus(x, y), y) GCD(x, y) -> IF1(ge(x, y), x, y) IF1(true, x, y) -> IF2(gt(y, 0), x, y) IF1(false, x, y) -> IF3(gt(x, 0), x, y) IF3(true, x, y) -> GCD(x, minus(y, x)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gcd(x, y) -> if1(ge(x, y), x, y) if1(true, x, y) -> if2(gt(y, 0), x, y) if1(false, x, y) -> if3(gt(x, 0), x, y) if2(true, x, y) -> gcd(minus(x, y), y) if2(false, x, y) -> x if3(true, x, y) -> gcd(x, minus(y, x)) if3(false, x, y) -> y gt(0, y) -> false gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(true, x, y) -> GCD(minus(x, y), y) GCD(x, y) -> IF1(ge(x, y), x, y) IF1(true, x, y) -> IF2(gt(y, 0), x, y) IF1(false, x, y) -> IF3(gt(x, 0), x, y) IF3(true, x, y) -> GCD(x, minus(y, x)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. gcd(x0, x1) if1(true, x0, x1) if1(false, x0, x1) if2(true, x0, x1) if2(false, x0, x1) if3(true, x0, x1) if3(false, x0, x1) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(true, x, y) -> GCD(minus(x, y), y) GCD(x, y) -> IF1(ge(x, y), x, y) IF1(true, x, y) -> IF2(gt(y, 0), x, y) IF1(false, x, y) -> IF3(gt(x, 0), x, y) IF3(true, x, y) -> GCD(x, minus(y, x)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule GCD(x, y) -> IF1(ge(x, y), x, y) at position [0] we obtained the following new rules [LPAR04]: (GCD(x0, 0) -> IF1(true, x0, 0),GCD(x0, 0) -> IF1(true, x0, 0)) (GCD(0, s(x0)) -> IF1(false, 0, s(x0)),GCD(0, s(x0)) -> IF1(false, 0, s(x0))) (GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)),GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(true, x, y) -> GCD(minus(x, y), y) IF1(true, x, y) -> IF2(gt(y, 0), x, y) IF1(false, x, y) -> IF3(gt(x, 0), x, y) IF3(true, x, y) -> GCD(x, minus(y, x)) GCD(x0, 0) -> IF1(true, x0, 0) GCD(0, s(x0)) -> IF1(false, 0, s(x0)) GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule IF1(true, x, y) -> IF2(gt(y, 0), x, y) at position [0] we obtained the following new rules [LPAR04]: (IF1(true, y0, s(x0)) -> IF2(true, y0, s(x0)),IF1(true, y0, s(x0)) -> IF2(true, y0, s(x0))) (IF1(true, y0, 0) -> IF2(false, y0, 0),IF1(true, y0, 0) -> IF2(false, y0, 0)) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(true, x, y) -> GCD(minus(x, y), y) IF1(false, x, y) -> IF3(gt(x, 0), x, y) IF3(true, x, y) -> GCD(x, minus(y, x)) GCD(x0, 0) -> IF1(true, x0, 0) GCD(0, s(x0)) -> IF1(false, 0, s(x0)) GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(true, y0, s(x0)) -> IF2(true, y0, s(x0)) IF1(true, y0, 0) -> IF2(false, y0, 0) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(0, s(x0)) -> IF1(false, 0, s(x0)) IF1(false, x, y) -> IF3(gt(x, 0), x, y) IF3(true, x, y) -> GCD(x, minus(y, x)) GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(true, y0, s(x0)) -> IF2(true, y0, s(x0)) IF2(true, x, y) -> GCD(minus(x, y), y) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule IF1(false, x, y) -> IF3(gt(x, 0), x, y) at position [0] we obtained the following new rules [LPAR04]: (IF1(false, s(x0), y1) -> IF3(true, s(x0), y1),IF1(false, s(x0), y1) -> IF3(true, s(x0), y1)) (IF1(false, 0, y1) -> IF3(false, 0, y1),IF1(false, 0, y1) -> IF3(false, 0, y1)) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(0, s(x0)) -> IF1(false, 0, s(x0)) IF3(true, x, y) -> GCD(x, minus(y, x)) GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(true, y0, s(x0)) -> IF2(true, y0, s(x0)) IF2(true, x, y) -> GCD(minus(x, y), y) IF1(false, s(x0), y1) -> IF3(true, s(x0), y1) IF1(false, 0, y1) -> IF3(false, 0, y1) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(true, y0, s(x0)) -> IF2(true, y0, s(x0)) IF2(true, x, y) -> GCD(minus(x, y), y) IF1(false, s(x0), y1) -> IF3(true, s(x0), y1) IF3(true, x, y) -> GCD(x, minus(y, x)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule IF2(true, x, y) -> GCD(minus(x, y), y) at position [0] we obtained the following new rules [LPAR04]: (IF2(true, s(x0), x1) -> GCD(if(gt(s(x0), x1), x0, x1), x1),IF2(true, s(x0), x1) -> GCD(if(gt(s(x0), x1), x0, x1), x1)) ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(true, y0, s(x0)) -> IF2(true, y0, s(x0)) IF1(false, s(x0), y1) -> IF3(true, s(x0), y1) IF3(true, x, y) -> GCD(x, minus(y, x)) IF2(true, s(x0), x1) -> GCD(if(gt(s(x0), x1), x0, x1), x1) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule IF3(true, x, y) -> GCD(x, minus(y, x)) at position [1] we obtained the following new rules [LPAR04]: (IF3(true, x1, s(x0)) -> GCD(x1, if(gt(s(x0), x1), x0, x1)),IF3(true, x1, s(x0)) -> GCD(x1, if(gt(s(x0), x1), x0, x1))) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(true, y0, s(x0)) -> IF2(true, y0, s(x0)) IF1(false, s(x0), y1) -> IF3(true, s(x0), y1) IF2(true, s(x0), x1) -> GCD(if(gt(s(x0), x1), x0, x1), x1) IF3(true, x1, s(x0)) -> GCD(x1, if(gt(s(x0), x1), x0, x1)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule IF1(true, y0, s(x0)) -> IF2(true, y0, s(x0)) we obtained the following new rules [LPAR04]: (IF1(true, s(z0), s(z1)) -> IF2(true, s(z0), s(z1)),IF1(true, s(z0), s(z1)) -> IF2(true, s(z0), s(z1))) ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(false, s(x0), y1) -> IF3(true, s(x0), y1) IF2(true, s(x0), x1) -> GCD(if(gt(s(x0), x1), x0, x1), x1) IF3(true, x1, s(x0)) -> GCD(x1, if(gt(s(x0), x1), x0, x1)) IF1(true, s(z0), s(z1)) -> IF2(true, s(z0), s(z1)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule IF1(false, s(x0), y1) -> IF3(true, s(x0), y1) we obtained the following new rules [LPAR04]: (IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1)),IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1))) ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF2(true, s(x0), x1) -> GCD(if(gt(s(x0), x1), x0, x1), x1) IF3(true, x1, s(x0)) -> GCD(x1, if(gt(s(x0), x1), x0, x1)) IF1(true, s(z0), s(z1)) -> IF2(true, s(z0), s(z1)) IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule IF2(true, s(x0), x1) -> GCD(if(gt(s(x0), x1), x0, x1), x1) we obtained the following new rules [LPAR04]: (IF2(true, s(z0), s(z1)) -> GCD(if(gt(s(z0), s(z1)), z0, s(z1)), s(z1)),IF2(true, s(z0), s(z1)) -> GCD(if(gt(s(z0), s(z1)), z0, s(z1)), s(z1))) ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF3(true, x1, s(x0)) -> GCD(x1, if(gt(s(x0), x1), x0, x1)) IF1(true, s(z0), s(z1)) -> IF2(true, s(z0), s(z1)) IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1)) IF2(true, s(z0), s(z1)) -> GCD(if(gt(s(z0), s(z1)), z0, s(z1)), s(z1)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule IF2(true, s(z0), s(z1)) -> GCD(if(gt(s(z0), s(z1)), z0, s(z1)), s(z1)) at position [0,0] we obtained the following new rules [LPAR04]: (IF2(true, s(z0), s(z1)) -> GCD(if(gt(z0, z1), z0, s(z1)), s(z1)),IF2(true, s(z0), s(z1)) -> GCD(if(gt(z0, z1), z0, s(z1)), s(z1))) ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF3(true, x1, s(x0)) -> GCD(x1, if(gt(s(x0), x1), x0, x1)) IF1(true, s(z0), s(z1)) -> IF2(true, s(z0), s(z1)) IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1)) IF2(true, s(z0), s(z1)) -> GCD(if(gt(z0, z1), z0, s(z1)), s(z1)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule IF3(true, x1, s(x0)) -> GCD(x1, if(gt(s(x0), x1), x0, x1)) we obtained the following new rules [LPAR04]: (IF3(true, s(z0), s(z1)) -> GCD(s(z0), if(gt(s(z1), s(z0)), z1, s(z0))),IF3(true, s(z0), s(z1)) -> GCD(s(z0), if(gt(s(z1), s(z0)), z1, s(z0)))) ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(true, s(z0), s(z1)) -> IF2(true, s(z0), s(z1)) IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1)) IF2(true, s(z0), s(z1)) -> GCD(if(gt(z0, z1), z0, s(z1)), s(z1)) IF3(true, s(z0), s(z1)) -> GCD(s(z0), if(gt(s(z1), s(z0)), z1, s(z0))) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule IF3(true, s(z0), s(z1)) -> GCD(s(z0), if(gt(s(z1), s(z0)), z1, s(z0))) at position [1,0] we obtained the following new rules [LPAR04]: (IF3(true, s(z0), s(z1)) -> GCD(s(z0), if(gt(z1, z0), z1, s(z0))),IF3(true, s(z0), s(z1)) -> GCD(s(z0), if(gt(z1, z0), z1, s(z0)))) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(true, s(z0), s(z1)) -> IF2(true, s(z0), s(z1)) IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1)) IF2(true, s(z0), s(z1)) -> GCD(if(gt(z0, z1), z0, s(z1)), s(z1)) IF3(true, s(z0), s(z1)) -> GCD(s(z0), if(gt(z1, z0), z1, s(z0))) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) Induction-Processor (SOUND) This DP could be deleted by the Induction-Processor: IF2(true_renamed, s(z0''), s(z1'')) -> GCD(if(gt(z0'', z1''), z0'', s(z1'')), s(z1'')) This order was computed: Polynomial interpretation [POLO]: POL(0) = 0 POL(GCD(x_1, x_2)) = x_1 POL(IF1(x_1, x_2, x_3)) = x_2 POL(IF2(x_1, x_2, x_3)) = x_1 + x_2 POL(IF3(x_1, x_2, x_3)) = x_1 + x_2 POL(false_renamed) = 0 POL(ge(x_1, x_2)) = x_1 POL(gt(x_1, x_2)) = x_1 + x_2 POL(if(x_1, x_2, x_3)) = 1 + x_2 POL(minus(x_1, x_2)) = x_1 POL(s(x_1)) = 1 + x_1 POL(true_renamed) = 0 At least one of these decreasing rules is always used after the deleted DP: if(false_renamed, x2, y'') -> 0 The following formula is valid: z0'':sort[a0],z1'':sort[a0].if'(gt(z0'', z1''), z0'', s(z1''))=true The transformed set: if'(true_renamed, x'', y') -> minus'(x'', y') if'(false_renamed, x2, y'') -> true minus'(s(x6), y3) -> if'(gt(s(x6), y3), x6, y3) minus'(0, v58) -> false gt(s(x), 0) -> true_renamed gt(s(x'), s(y)) -> gt(x', y) if(true_renamed, x'', y') -> s(minus(x'', y')) if(false_renamed, x2, y'') -> 0 gt(0, y1) -> false_renamed ge(x3, 0) -> true_renamed ge(0, s(x4)) -> false_renamed ge(s(x5), s(y2)) -> ge(x5, y2) minus(s(x6), y3) -> if(gt(s(x6), y3), x6, y3) minus(0, v58) -> 0 equal_bool(true, false) -> false equal_bool(false, true) -> false equal_bool(true, true) -> true equal_bool(false, false) -> true and(true, x) -> x and(false, x) -> false or(true, x) -> true or(false, x) -> x not(false) -> true not(true) -> false isa_true(true) -> true isa_true(false) -> false isa_false(true) -> false isa_false(false) -> true equal_sort[a0](s(v60), s(v61)) -> equal_sort[a0](v60, v61) equal_sort[a0](s(v60), 0) -> false equal_sort[a0](0, s(v62)) -> false equal_sort[a0](0, 0) -> true equal_sort[a26](true_renamed, true_renamed) -> true equal_sort[a26](true_renamed, false_renamed) -> false equal_sort[a26](false_renamed, true_renamed) -> false equal_sort[a26](false_renamed, false_renamed) -> true equal_sort[a44](witness_sort[a44], witness_sort[a44]) -> true The proof given by the theorem prover: The following output was given by the internal theorem prover:proof of internal # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Partial correctness of the following Program [x, v60, v61, v62, x2, y'', x6, y', v58, y3, x', y, y1, x3, x4, x5, y2] equal_bool(true, false) -> false equal_bool(false, true) -> false equal_bool(true, true) -> true equal_bool(false, false) -> true true and x -> x false and x -> false true or x -> true false or x -> x not(false) -> true not(true) -> false isa_true(true) -> true isa_true(false) -> false isa_false(true) -> false isa_false(false) -> true equal_sort[a0](s(v60), s(v61)) -> equal_sort[a0](v60, v61) equal_sort[a0](s(v60), 0) -> false equal_sort[a0](0, s(v62)) -> false equal_sort[a0](0, 0) -> true equal_sort[a26](true_renamed, true_renamed) -> true equal_sort[a26](true_renamed, false_renamed) -> false equal_sort[a26](false_renamed, true_renamed) -> false equal_sort[a26](false_renamed, false_renamed) -> true equal_sort[a44](witness_sort[a44], witness_sort[a44]) -> true if'(false_renamed, x2, y'') -> true if'(true_renamed, s(x6), y') -> if'(gt(s(x6), y'), x6, y') if'(true_renamed, 0, y') -> false minus'(0, v58) -> false equal_sort[a26](gt(s(x6), y3), true_renamed) -> true | minus'(s(x6), y3) -> minus'(x6, y3) equal_sort[a26](gt(s(x6), y3), true_renamed) -> false | minus'(s(x6), y3) -> true gt(s(x), 0) -> true_renamed gt(s(x'), s(y)) -> gt(x', y) gt(0, y1) -> false_renamed if(false_renamed, x2, y'') -> 0 if(true_renamed, s(x6), y') -> s(if(gt(s(x6), y'), x6, y')) if(true_renamed, 0, y') -> s(0) ge(x3, 0) -> true_renamed ge(0, s(x4)) -> false_renamed ge(s(x5), s(y2)) -> ge(x5, y2) minus(0, v58) -> 0 equal_sort[a26](gt(s(x6), y3), true_renamed) -> true | minus(s(x6), y3) -> s(minus(x6, y3)) equal_sort[a26](gt(s(x6), y3), true_renamed) -> false | minus(s(x6), y3) -> 0 using the following formula: z0'':sort[a0],z1'':sort[a0].if'(gt(z0'', z1''), z0'', s(z1''))=true could be successfully shown: (0) Formula (1) Induction by algorithm [EQUIVALENT, 0 ms] (2) AND (3) Formula (4) Symbolic evaluation [EQUIVALENT, 0 ms] (5) Formula (6) Induction by data structure [EQUIVALENT, 0 ms] (7) AND (8) Formula (9) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms] (10) YES (11) Formula (12) Symbolic evaluation [EQUIVALENT, 0 ms] (13) YES (14) Formula (15) Symbolic evaluation [EQUIVALENT, 0 ms] (16) YES (17) Formula (18) Symbolic evaluation [EQUIVALENT, 0 ms] (19) Formula (20) Hypothesis Lifting [EQUIVALENT, 0 ms] (21) Formula (22) Inverse Substitution [SOUND, 0 ms] (23) Formula (24) Inverse Substitution [SOUND, 0 ms] (25) Formula (26) Induction by algorithm [EQUIVALENT, 0 ms] (27) AND (28) Formula (29) Symbolic evaluation [EQUIVALENT, 0 ms] (30) YES (31) Formula (32) Symbolic evaluation [EQUIVALENT, 0 ms] (33) YES (34) Formula (35) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms] (36) YES ---------------------------------------- (0) Obligation: Formula: z0'':sort[a0],z1'':sort[a0].if'(gt(z0'', z1''), z0'', s(z1''))=true There are no hypotheses. ---------------------------------------- (1) Induction by algorithm (EQUIVALENT) Induction by algorithm gt(z0'', z1'') generates the following cases: 1. Base Case: Formula: x:sort[a0].if'(gt(s(x), 0), s(x), s(0))=true There are no hypotheses. 2. Base Case: Formula: y1:sort[a0].if'(gt(0, y1), 0, s(y1))=true There are no hypotheses. 1. Step Case: Formula: x':sort[a0],y:sort[a0].if'(gt(s(x'), s(y)), s(x'), s(s(y)))=true Hypotheses: x':sort[a0],y:sort[a0].if'(gt(x', y), x', s(y))=true ---------------------------------------- (2) Complex Obligation (AND) ---------------------------------------- (3) Obligation: Formula: x:sort[a0].if'(gt(s(x), 0), s(x), s(0))=true There are no hypotheses. ---------------------------------------- (4) Symbolic evaluation (EQUIVALENT) Could be shown by simple symbolic evaluation. ---------------------------------------- (5) Obligation: Formula: x:sort[a0].if'(gt(x, 0), x, s(0))=true There are no hypotheses. ---------------------------------------- (6) Induction by data structure (EQUIVALENT) Induction by data structure sort[a0] generates the following cases: 1. Base Case: Formula: if'(gt(0, 0), 0, s(0))=true There are no hypotheses. 1. Step Case: Formula: n:sort[a0].if'(gt(s(n), 0), s(n), s(0))=true Hypotheses: n:sort[a0].if'(gt(n, 0), n, s(0))=true ---------------------------------------- (7) Complex Obligation (AND) ---------------------------------------- (8) Obligation: Formula: n:sort[a0].if'(gt(s(n), 0), s(n), s(0))=true Hypotheses: n:sort[a0].if'(gt(n, 0), n, s(0))=true ---------------------------------------- (9) Symbolic evaluation under hypothesis (EQUIVALENT) Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses: n:sort[a0].if'(gt(n, 0), n, s(0))=true ---------------------------------------- (10) YES ---------------------------------------- (11) Obligation: Formula: if'(gt(0, 0), 0, s(0))=true There are no hypotheses. ---------------------------------------- (12) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Formula: y1:sort[a0].if'(gt(0, y1), 0, s(y1))=true There are no hypotheses. ---------------------------------------- (15) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (16) YES ---------------------------------------- (17) Obligation: Formula: x':sort[a0],y:sort[a0].if'(gt(s(x'), s(y)), s(x'), s(s(y)))=true Hypotheses: x':sort[a0],y:sort[a0].if'(gt(x', y), x', s(y))=true ---------------------------------------- (18) Symbolic evaluation (EQUIVALENT) Could be shown by simple symbolic evaluation. ---------------------------------------- (19) Obligation: Formula: x':sort[a0],y:sort[a0].if'(gt(x', y), s(x'), s(s(y)))=true Hypotheses: x':sort[a0],y:sort[a0].if'(gt(x', y), x', s(y))=true ---------------------------------------- (20) Hypothesis Lifting (EQUIVALENT) Formula could be generalised by hypothesis lifting to the following new obligation: Formula: x':sort[a0],y:sort[a0].(if'(gt(x', y), x', s(y))=true->if'(gt(x', y), s(x'), s(s(y)))=true) There are no hypotheses. ---------------------------------------- (21) Obligation: Formula: x':sort[a0],y:sort[a0].(if'(gt(x', y), x', s(y))=true->if'(gt(x', y), s(x'), s(s(y)))=true) There are no hypotheses. ---------------------------------------- (22) Inverse Substitution (SOUND) The formula could be generalised by inverse substitution to: n:sort[a26],x':sort[a0],y:sort[a0].(if'(n, x', s(y))=true->if'(n, s(x'), s(s(y)))=true) Inverse substitution used: [gt(x', y)/n] ---------------------------------------- (23) Obligation: Formula: n:sort[a26],x':sort[a0],y:sort[a0].(if'(n, x', s(y))=true->if'(n, s(x'), s(s(y)))=true) There are no hypotheses. ---------------------------------------- (24) Inverse Substitution (SOUND) The formula could be generalised by inverse substitution to: n:sort[a26],x':sort[a0],n':sort[a0].(if'(n, x', n')=true->if'(n, s(x'), s(n'))=true) Inverse substitution used: [s(y)/n'] ---------------------------------------- (25) Obligation: Formula: n:sort[a26],x':sort[a0],n':sort[a0].(if'(n, x', n')=true->if'(n, s(x'), s(n'))=true) There are no hypotheses. ---------------------------------------- (26) Induction by algorithm (EQUIVALENT) Induction by algorithm if'(n, x', n') generates the following cases: 1. Base Case: Formula: x2:sort[a0],y'':sort[a0].(if'(false_renamed, x2, y'')=true->if'(false_renamed, s(x2), s(y''))=true) There are no hypotheses. 2. Base Case: Formula: y':sort[a0].(if'(true_renamed, 0, y')=true->if'(true_renamed, s(0), s(y'))=true) There are no hypotheses. 1. Step Case: Formula: x6:sort[a0],y':sort[a0].(if'(true_renamed, s(x6), y')=true->if'(true_renamed, s(s(x6)), s(y'))=true) Hypotheses: x6:sort[a0],y':sort[a0].(if'(gt(s(x6), y'), x6, y')=true->if'(gt(s(x6), y'), s(x6), s(y'))=true) ---------------------------------------- (27) Complex Obligation (AND) ---------------------------------------- (28) Obligation: Formula: x2:sort[a0],y'':sort[a0].(if'(false_renamed, x2, y'')=true->if'(false_renamed, s(x2), s(y''))=true) There are no hypotheses. ---------------------------------------- (29) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (30) YES ---------------------------------------- (31) Obligation: Formula: y':sort[a0].(if'(true_renamed, 0, y')=true->if'(true_renamed, s(0), s(y'))=true) There are no hypotheses. ---------------------------------------- (32) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (33) YES ---------------------------------------- (34) Obligation: Formula: x6:sort[a0],y':sort[a0].(if'(true_renamed, s(x6), y')=true->if'(true_renamed, s(s(x6)), s(y'))=true) Hypotheses: x6:sort[a0],y':sort[a0].(if'(gt(s(x6), y'), x6, y')=true->if'(gt(s(x6), y'), s(x6), s(y'))=true) ---------------------------------------- (35) Symbolic evaluation under hypothesis (EQUIVALENT) Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses: x6:sort[a0],y':sort[a0].(if'(gt(s(x6), y'), x6, y')=true->if'(gt(s(x6), y'), s(x6), s(y'))=true) ---------------------------------------- (36) YES ---------------------------------------- (60) Complex Obligation (AND) ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) IF1(true, s(z0), s(z1)) -> IF2(true, s(z0), s(z1)) IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1)) IF3(true, s(z0), s(z1)) -> GCD(s(z0), if(gt(z1, z0), z1, s(z0))) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1)) IF3(true, s(z0), s(z1)) -> GCD(s(z0), if(gt(z1, z0), z1, s(z0))) GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) Induction-Processor (SOUND) This DP could be deleted by the Induction-Processor: IF3(true_renamed, s(z0'), s(z1')) -> GCD(s(z0'), if(gt(z1', z0'), z1', s(z0'))) This order was computed: Polynomial interpretation [POLO]: POL(0) = 0 POL(GCD(x_1, x_2)) = x_2 POL(IF1(x_1, x_2, x_3)) = x_3 POL(IF3(x_1, x_2, x_3)) = x_1 + x_3 POL(false_renamed) = 0 POL(ge(x_1, x_2)) = x_1 + x_2 POL(gt(x_1, x_2)) = x_1 + x_2 POL(if(x_1, x_2, x_3)) = 1 + x_2 POL(minus(x_1, x_2)) = x_1 POL(s(x_1)) = 1 + x_1 POL(true_renamed) = 0 At least one of these decreasing rules is always used after the deleted DP: if(false_renamed, x2, y'') -> 0 The following formula is valid: z1':sort[a0],z0':sort[a0].if'(gt(z1', z0'), z1', s(z0'))=true The transformed set: if'(true_renamed, x'', y') -> minus'(x'', y') if'(false_renamed, x2, y'') -> true minus'(s(x6), y3) -> if'(gt(s(x6), y3), x6, y3) minus'(0, v28) -> false gt(s(x), 0) -> true_renamed gt(s(x'), s(y)) -> gt(x', y) if(true_renamed, x'', y') -> s(minus(x'', y')) if(false_renamed, x2, y'') -> 0 gt(0, y1) -> false_renamed ge(x3, 0) -> true_renamed ge(0, s(x4)) -> false_renamed ge(s(x5), s(y2)) -> ge(x5, y2) minus(s(x6), y3) -> if(gt(s(x6), y3), x6, y3) minus(0, v28) -> 0 equal_bool(true, false) -> false equal_bool(false, true) -> false equal_bool(true, true) -> true equal_bool(false, false) -> true and(true, x) -> x and(false, x) -> false or(true, x) -> true or(false, x) -> x not(false) -> true not(true) -> false isa_true(true) -> true isa_true(false) -> false isa_false(true) -> false isa_false(false) -> true equal_sort[a0](s(v30), s(v31)) -> equal_sort[a0](v30, v31) equal_sort[a0](s(v30), 0) -> false equal_sort[a0](0, s(v32)) -> false equal_sort[a0](0, 0) -> true equal_sort[a22](true_renamed, true_renamed) -> true equal_sort[a22](true_renamed, false_renamed) -> false equal_sort[a22](false_renamed, true_renamed) -> false equal_sort[a22](false_renamed, false_renamed) -> true equal_sort[a41](witness_sort[a41], witness_sort[a41]) -> true The proof given by the theorem prover: The following output was given by the internal theorem prover:proof of internal # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Partial correctness of the following Program [x, v30, v31, v32, x2, y'', x6, y', v28, y3, x', y, y1, x3, x4, x5, y2] equal_bool(true, false) -> false equal_bool(false, true) -> false equal_bool(true, true) -> true equal_bool(false, false) -> true true and x -> x false and x -> false true or x -> true false or x -> x not(false) -> true not(true) -> false isa_true(true) -> true isa_true(false) -> false isa_false(true) -> false isa_false(false) -> true equal_sort[a0](s(v30), s(v31)) -> equal_sort[a0](v30, v31) equal_sort[a0](s(v30), 0) -> false equal_sort[a0](0, s(v32)) -> false equal_sort[a0](0, 0) -> true equal_sort[a22](true_renamed, true_renamed) -> true equal_sort[a22](true_renamed, false_renamed) -> false equal_sort[a22](false_renamed, true_renamed) -> false equal_sort[a22](false_renamed, false_renamed) -> true equal_sort[a41](witness_sort[a41], witness_sort[a41]) -> true if'(false_renamed, x2, y'') -> true if'(true_renamed, s(x6), y') -> if'(gt(s(x6), y'), x6, y') if'(true_renamed, 0, y') -> false minus'(0, v28) -> false equal_sort[a22](gt(s(x6), y3), true_renamed) -> true | minus'(s(x6), y3) -> minus'(x6, y3) equal_sort[a22](gt(s(x6), y3), true_renamed) -> false | minus'(s(x6), y3) -> true gt(s(x), 0) -> true_renamed gt(s(x'), s(y)) -> gt(x', y) gt(0, y1) -> false_renamed if(false_renamed, x2, y'') -> 0 if(true_renamed, s(x6), y') -> s(if(gt(s(x6), y'), x6, y')) if(true_renamed, 0, y') -> s(0) ge(x3, 0) -> true_renamed ge(0, s(x4)) -> false_renamed ge(s(x5), s(y2)) -> ge(x5, y2) minus(0, v28) -> 0 equal_sort[a22](gt(s(x6), y3), true_renamed) -> true | minus(s(x6), y3) -> s(minus(x6, y3)) equal_sort[a22](gt(s(x6), y3), true_renamed) -> false | minus(s(x6), y3) -> 0 using the following formula: z1':sort[a0],z0':sort[a0].if'(gt(z1', z0'), z1', s(z0'))=true could be successfully shown: (0) Formula (1) Induction by algorithm [EQUIVALENT, 0 ms] (2) AND (3) Formula (4) Symbolic evaluation [EQUIVALENT, 0 ms] (5) Formula (6) Induction by data structure [EQUIVALENT, 0 ms] (7) AND (8) Formula (9) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms] (10) YES (11) Formula (12) Symbolic evaluation [EQUIVALENT, 0 ms] (13) YES (14) Formula (15) Symbolic evaluation [EQUIVALENT, 0 ms] (16) YES (17) Formula (18) Symbolic evaluation [EQUIVALENT, 0 ms] (19) Formula (20) Hypothesis Lifting [EQUIVALENT, 0 ms] (21) Formula (22) Inverse Substitution [SOUND, 0 ms] (23) Formula (24) Inverse Substitution [SOUND, 0 ms] (25) Formula (26) Induction by algorithm [EQUIVALENT, 0 ms] (27) AND (28) Formula (29) Symbolic evaluation [EQUIVALENT, 0 ms] (30) YES (31) Formula (32) Symbolic evaluation [EQUIVALENT, 0 ms] (33) YES (34) Formula (35) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms] (36) YES ---------------------------------------- (0) Obligation: Formula: z1':sort[a0],z0':sort[a0].if'(gt(z1', z0'), z1', s(z0'))=true There are no hypotheses. ---------------------------------------- (1) Induction by algorithm (EQUIVALENT) Induction by algorithm gt(z1', z0') generates the following cases: 1. Base Case: Formula: x:sort[a0].if'(gt(s(x), 0), s(x), s(0))=true There are no hypotheses. 2. Base Case: Formula: y1:sort[a0].if'(gt(0, y1), 0, s(y1))=true There are no hypotheses. 1. Step Case: Formula: x':sort[a0],y:sort[a0].if'(gt(s(x'), s(y)), s(x'), s(s(y)))=true Hypotheses: x':sort[a0],y:sort[a0].if'(gt(x', y), x', s(y))=true ---------------------------------------- (2) Complex Obligation (AND) ---------------------------------------- (3) Obligation: Formula: x:sort[a0].if'(gt(s(x), 0), s(x), s(0))=true There are no hypotheses. ---------------------------------------- (4) Symbolic evaluation (EQUIVALENT) Could be shown by simple symbolic evaluation. ---------------------------------------- (5) Obligation: Formula: x:sort[a0].if'(gt(x, 0), x, s(0))=true There are no hypotheses. ---------------------------------------- (6) Induction by data structure (EQUIVALENT) Induction by data structure sort[a0] generates the following cases: 1. Base Case: Formula: if'(gt(0, 0), 0, s(0))=true There are no hypotheses. 1. Step Case: Formula: n:sort[a0].if'(gt(s(n), 0), s(n), s(0))=true Hypotheses: n:sort[a0].if'(gt(n, 0), n, s(0))=true ---------------------------------------- (7) Complex Obligation (AND) ---------------------------------------- (8) Obligation: Formula: n:sort[a0].if'(gt(s(n), 0), s(n), s(0))=true Hypotheses: n:sort[a0].if'(gt(n, 0), n, s(0))=true ---------------------------------------- (9) Symbolic evaluation under hypothesis (EQUIVALENT) Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses: n:sort[a0].if'(gt(n, 0), n, s(0))=true ---------------------------------------- (10) YES ---------------------------------------- (11) Obligation: Formula: if'(gt(0, 0), 0, s(0))=true There are no hypotheses. ---------------------------------------- (12) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Formula: y1:sort[a0].if'(gt(0, y1), 0, s(y1))=true There are no hypotheses. ---------------------------------------- (15) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (16) YES ---------------------------------------- (17) Obligation: Formula: x':sort[a0],y:sort[a0].if'(gt(s(x'), s(y)), s(x'), s(s(y)))=true Hypotheses: x':sort[a0],y:sort[a0].if'(gt(x', y), x', s(y))=true ---------------------------------------- (18) Symbolic evaluation (EQUIVALENT) Could be shown by simple symbolic evaluation. ---------------------------------------- (19) Obligation: Formula: x':sort[a0],y:sort[a0].if'(gt(x', y), s(x'), s(s(y)))=true Hypotheses: x':sort[a0],y:sort[a0].if'(gt(x', y), x', s(y))=true ---------------------------------------- (20) Hypothesis Lifting (EQUIVALENT) Formula could be generalised by hypothesis lifting to the following new obligation: Formula: x':sort[a0],y:sort[a0].(if'(gt(x', y), x', s(y))=true->if'(gt(x', y), s(x'), s(s(y)))=true) There are no hypotheses. ---------------------------------------- (21) Obligation: Formula: x':sort[a0],y:sort[a0].(if'(gt(x', y), x', s(y))=true->if'(gt(x', y), s(x'), s(s(y)))=true) There are no hypotheses. ---------------------------------------- (22) Inverse Substitution (SOUND) The formula could be generalised by inverse substitution to: n:sort[a22],x':sort[a0],y:sort[a0].(if'(n, x', s(y))=true->if'(n, s(x'), s(s(y)))=true) Inverse substitution used: [gt(x', y)/n] ---------------------------------------- (23) Obligation: Formula: n:sort[a22],x':sort[a0],y:sort[a0].(if'(n, x', s(y))=true->if'(n, s(x'), s(s(y)))=true) There are no hypotheses. ---------------------------------------- (24) Inverse Substitution (SOUND) The formula could be generalised by inverse substitution to: n:sort[a22],x':sort[a0],n':sort[a0].(if'(n, x', n')=true->if'(n, s(x'), s(n'))=true) Inverse substitution used: [s(y)/n'] ---------------------------------------- (25) Obligation: Formula: n:sort[a22],x':sort[a0],n':sort[a0].(if'(n, x', n')=true->if'(n, s(x'), s(n'))=true) There are no hypotheses. ---------------------------------------- (26) Induction by algorithm (EQUIVALENT) Induction by algorithm if'(n, x', n') generates the following cases: 1. Base Case: Formula: x2:sort[a0],y'':sort[a0].(if'(false_renamed, x2, y'')=true->if'(false_renamed, s(x2), s(y''))=true) There are no hypotheses. 2. Base Case: Formula: y':sort[a0].(if'(true_renamed, 0, y')=true->if'(true_renamed, s(0), s(y'))=true) There are no hypotheses. 1. Step Case: Formula: x6:sort[a0],y':sort[a0].(if'(true_renamed, s(x6), y')=true->if'(true_renamed, s(s(x6)), s(y'))=true) Hypotheses: x6:sort[a0],y':sort[a0].(if'(gt(s(x6), y'), x6, y')=true->if'(gt(s(x6), y'), s(x6), s(y'))=true) ---------------------------------------- (27) Complex Obligation (AND) ---------------------------------------- (28) Obligation: Formula: x2:sort[a0],y'':sort[a0].(if'(false_renamed, x2, y'')=true->if'(false_renamed, s(x2), s(y''))=true) There are no hypotheses. ---------------------------------------- (29) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (30) YES ---------------------------------------- (31) Obligation: Formula: y':sort[a0].(if'(true_renamed, 0, y')=true->if'(true_renamed, s(0), s(y'))=true) There are no hypotheses. ---------------------------------------- (32) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (33) YES ---------------------------------------- (34) Obligation: Formula: x6:sort[a0],y':sort[a0].(if'(true_renamed, s(x6), y')=true->if'(true_renamed, s(s(x6)), s(y'))=true) Hypotheses: x6:sort[a0],y':sort[a0].(if'(gt(s(x6), y'), x6, y')=true->if'(gt(s(x6), y'), s(x6), s(y'))=true) ---------------------------------------- (35) Symbolic evaluation under hypothesis (EQUIVALENT) Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses: x6:sort[a0],y':sort[a0].(if'(gt(s(x6), y'), x6, y')=true->if'(gt(s(x6), y'), s(x6), s(y'))=true) ---------------------------------------- (36) YES ---------------------------------------- (65) Complex Obligation (AND) ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(false, s(z0), s(z1)) -> IF3(true, s(z0), s(z1)) GCD(s(x0), s(x1)) -> IF1(ge(x0, x1), s(x0), s(x1)) The TRS R consists of the following rules: minus(s(x), y) -> if(gt(s(x), y), x, y) gt(s(x), 0) -> true gt(s(x), s(y)) -> gt(x, y) if(true, x, y) -> s(minus(x, y)) if(false, x, y) -> 0 gt(0, y) -> false ge(x, 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: minus(s(x0), x1) if(true, x0, x1) if(false, x0, x1) gt(0, x0) gt(s(x0), 0) gt(s(x0), s(x1)) ge(x0, 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (68) TRUE ---------------------------------------- (69) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: if'(true_renamed, x'', y') -> minus'(x'', y') if'(false_renamed, x2, y'') -> true minus'(s(x6), y3) -> if'(gt(s(x6), y3), x6, y3) minus'(0, v28) -> false gt(s(x), 0) -> true_renamed gt(s(x'), s(y)) -> gt(x', y) if(true_renamed, x'', y') -> s(minus(x'', y')) if(false_renamed, x2, y'') -> 0 gt(0, y1) -> false_renamed ge(x3, 0) -> true_renamed ge(0, s(x4)) -> false_renamed ge(s(x5), s(y2)) -> ge(x5, y2) minus(s(x6), y3) -> if(gt(s(x6), y3), x6, y3) minus(0, v28) -> 0 equal_bool(true, false) -> false equal_bool(false, true) -> false equal_bool(true, true) -> true equal_bool(false, false) -> true and(true, x) -> x and(false, x) -> false or(true, x) -> true or(false, x) -> x not(false) -> true not(true) -> false isa_true(true) -> true isa_true(false) -> false isa_false(true) -> false isa_false(false) -> true equal_sort[a0](s(v30), s(v31)) -> equal_sort[a0](v30, v31) equal_sort[a0](s(v30), 0) -> false equal_sort[a0](0, s(v32)) -> false equal_sort[a0](0, 0) -> true equal_sort[a22](true_renamed, true_renamed) -> true equal_sort[a22](true_renamed, false_renamed) -> false equal_sort[a22](false_renamed, true_renamed) -> false equal_sort[a22](false_renamed, false_renamed) -> true equal_sort[a41](witness_sort[a41], witness_sort[a41]) -> true Q is empty. ---------------------------------------- (70) QTRSRRRProof (EQUIVALENT) Used ordering: Quasi precedence: [if'_3, minus'_2] > [false_renamed, gt_2] > 0 [if'_3, minus'_2] > [false_renamed, gt_2] > [false, equal_bool_2, equal_sort[a0]_2, equal_sort[a22]_2] > [true_renamed, true, equal_sort[a41]_2] > s_1 [if_3, minus_2] > [false_renamed, gt_2] > 0 [if_3, minus_2] > [false_renamed, gt_2] > [false, equal_bool_2, equal_sort[a0]_2, equal_sort[a22]_2] > [true_renamed, true, equal_sort[a41]_2] > s_1 ge_2 > [false_renamed, gt_2] > 0 ge_2 > [false_renamed, gt_2] > [false, equal_bool_2, equal_sort[a0]_2, equal_sort[a22]_2] > [true_renamed, true, equal_sort[a41]_2] > s_1 not_1 > [false, equal_bool_2, equal_sort[a0]_2, equal_sort[a22]_2] > [true_renamed, true, equal_sort[a41]_2] > s_1 isa_false_1 > [false, equal_bool_2, equal_sort[a0]_2, equal_sort[a22]_2] > [true_renamed, true, equal_sort[a41]_2] > s_1 witness_sort[a41] > [true_renamed, true, equal_sort[a41]_2] > s_1 Status: if'_3: [2,3,1] true_renamed: multiset status minus'_2: [1,2] false_renamed: multiset status true: multiset status s_1: [1] gt_2: [1,2] 0: multiset status false: multiset status if_3: [3,2,1] minus_2: [2,1] ge_2: [1,2] equal_bool_2: multiset status and_2: [2,1] or_2: [2,1] not_1: multiset status isa_true_1: multiset status isa_false_1: multiset status equal_sort[a0]_2: [2,1] equal_sort[a22]_2: [2,1] equal_sort[a41]_2: multiset status witness_sort[a41]: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: if'(true_renamed, x'', y') -> minus'(x'', y') if'(false_renamed, x2, y'') -> true minus'(s(x6), y3) -> if'(gt(s(x6), y3), x6, y3) minus'(0, v28) -> false gt(s(x), 0) -> true_renamed gt(s(x'), s(y)) -> gt(x', y) if(true_renamed, x'', y') -> s(minus(x'', y')) if(false_renamed, x2, y'') -> 0 gt(0, y1) -> false_renamed ge(x3, 0) -> true_renamed ge(0, s(x4)) -> false_renamed ge(s(x5), s(y2)) -> ge(x5, y2) minus(s(x6), y3) -> if(gt(s(x6), y3), x6, y3) minus(0, v28) -> 0 equal_bool(true, false) -> false equal_bool(false, true) -> false equal_bool(true, true) -> true equal_bool(false, false) -> true and(true, x) -> x and(false, x) -> false or(true, x) -> true or(false, x) -> x not(false) -> true not(true) -> false isa_true(true) -> true isa_true(false) -> false isa_false(true) -> false isa_false(false) -> true equal_sort[a0](s(v30), s(v31)) -> equal_sort[a0](v30, v31) equal_sort[a0](s(v30), 0) -> false equal_sort[a0](0, s(v32)) -> false equal_sort[a0](0, 0) -> true equal_sort[a22](true_renamed, true_renamed) -> true equal_sort[a22](true_renamed, false_renamed) -> false equal_sort[a22](false_renamed, true_renamed) -> false equal_sort[a22](false_renamed, false_renamed) -> true equal_sort[a41](witness_sort[a41], witness_sort[a41]) -> true ---------------------------------------- (71) Obligation: Q restricted rewrite system: R is empty. Q is empty. ---------------------------------------- (72) RisEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (73) YES ---------------------------------------- (74) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: if'(true_renamed, x'', y') -> minus'(x'', y') if'(false_renamed, x2, y'') -> true minus'(s(x6), y3) -> if'(gt(s(x6), y3), x6, y3) minus'(0, v58) -> false gt(s(x), 0) -> true_renamed gt(s(x'), s(y)) -> gt(x', y) if(true_renamed, x'', y') -> s(minus(x'', y')) if(false_renamed, x2, y'') -> 0 gt(0, y1) -> false_renamed ge(x3, 0) -> true_renamed ge(0, s(x4)) -> false_renamed ge(s(x5), s(y2)) -> ge(x5, y2) minus(s(x6), y3) -> if(gt(s(x6), y3), x6, y3) minus(0, v58) -> 0 equal_bool(true, false) -> false equal_bool(false, true) -> false equal_bool(true, true) -> true equal_bool(false, false) -> true and(true, x) -> x and(false, x) -> false or(true, x) -> true or(false, x) -> x not(false) -> true not(true) -> false isa_true(true) -> true isa_true(false) -> false isa_false(true) -> false isa_false(false) -> true equal_sort[a0](s(v60), s(v61)) -> equal_sort[a0](v60, v61) equal_sort[a0](s(v60), 0) -> false equal_sort[a0](0, s(v62)) -> false equal_sort[a0](0, 0) -> true equal_sort[a26](true_renamed, true_renamed) -> true equal_sort[a26](true_renamed, false_renamed) -> false equal_sort[a26](false_renamed, true_renamed) -> false equal_sort[a26](false_renamed, false_renamed) -> true equal_sort[a44](witness_sort[a44], witness_sort[a44]) -> true Q is empty. ---------------------------------------- (75) QTRSRRRProof (EQUIVALENT) Used ordering: if'/3(YES,YES,YES) true_renamed/0) minus'/2(YES,YES) false_renamed/0) true/0) s/1(YES) gt/2(YES,YES) 0/0) false/0) if/3(YES,YES,YES) minus/2(YES,YES) ge/2(YES,YES) equal_bool/2(YES,YES) and/2(YES,YES) or/2(YES,YES) not/1(YES) isa_true/1)YES( isa_false/1(YES) equal_sort[a0]/2(YES,YES) equal_sort[a26]/2(YES,YES) equal_sort[a44]/2(YES,YES) witness_sort[a44]/0) Quasi precedence: ge_2 > [true_renamed, true, witness_sort[a44]] > [if'_3, minus'_2] > gt_2 > s_1 ge_2 > [true_renamed, true, witness_sort[a44]] > [if_3, minus_2] > gt_2 > s_1 equal_bool_2 > s_1 and_2 > s_1 or_2 > s_1 isa_false_1 > [false_renamed, 0, false, not_1] > [true_renamed, true, witness_sort[a44]] > [if'_3, minus'_2] > gt_2 > s_1 isa_false_1 > [false_renamed, 0, false, not_1] > [true_renamed, true, witness_sort[a44]] > [if_3, minus_2] > gt_2 > s_1 equal_sort[a0]_2 > [true_renamed, true, witness_sort[a44]] > [if'_3, minus'_2] > gt_2 > s_1 equal_sort[a0]_2 > [true_renamed, true, witness_sort[a44]] > [if_3, minus_2] > gt_2 > s_1 equal_sort[a26]_2 > s_1 equal_sort[a44]_2 > s_1 Status: if'_3: [2,3,1] true_renamed: multiset status minus'_2: [1,2] false_renamed: multiset status true: multiset status s_1: multiset status gt_2: multiset status 0: multiset status false: multiset status if_3: [2,3,1] minus_2: [1,2] ge_2: [2,1] equal_bool_2: [2,1] and_2: [2,1] or_2: [2,1] not_1: [1] isa_false_1: multiset status equal_sort[a0]_2: [1,2] equal_sort[a26]_2: multiset status equal_sort[a44]_2: [2,1] witness_sort[a44]: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: if'(true_renamed, x'', y') -> minus'(x'', y') if'(false_renamed, x2, y'') -> true minus'(s(x6), y3) -> if'(gt(s(x6), y3), x6, y3) minus'(0, v58) -> false gt(s(x), 0) -> true_renamed gt(s(x'), s(y)) -> gt(x', y) if(true_renamed, x'', y') -> s(minus(x'', y')) if(false_renamed, x2, y'') -> 0 gt(0, y1) -> false_renamed ge(x3, 0) -> true_renamed ge(0, s(x4)) -> false_renamed ge(s(x5), s(y2)) -> ge(x5, y2) minus(s(x6), y3) -> if(gt(s(x6), y3), x6, y3) minus(0, v58) -> 0 equal_bool(true, false) -> false equal_bool(false, true) -> false equal_bool(true, true) -> true equal_bool(false, false) -> true and(true, x) -> x and(false, x) -> false or(true, x) -> true or(false, x) -> x not(false) -> true not(true) -> false isa_false(true) -> false isa_false(false) -> true equal_sort[a0](s(v60), s(v61)) -> equal_sort[a0](v60, v61) equal_sort[a0](s(v60), 0) -> false equal_sort[a0](0, s(v62)) -> false equal_sort[a0](0, 0) -> true equal_sort[a26](true_renamed, true_renamed) -> true equal_sort[a26](true_renamed, false_renamed) -> false equal_sort[a26](false_renamed, true_renamed) -> false equal_sort[a26](false_renamed, false_renamed) -> true equal_sort[a44](witness_sort[a44], witness_sort[a44]) -> true ---------------------------------------- (76) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: isa_true(true) -> true isa_true(false) -> false Q is empty. ---------------------------------------- (77) QTRSRRRProof (EQUIVALENT) Used ordering: Knuth-Bendix order [KBO] with precedence:isa_true_1 > false > true and weight map: true=1 false=1 isa_true_1=0 The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: isa_true(true) -> true isa_true(false) -> false ---------------------------------------- (78) Obligation: Q restricted rewrite system: R is empty. Q is empty. ---------------------------------------- (79) RisEmptyProof (EQUIVALENT) The TRS R is empty. Hence, termination is trivially proven. ---------------------------------------- (80) YES