/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/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) QDPOrderProof [EQUIVALENT, 0 ms] (34) QDP (35) PisEmptyProof [EQUIVALENT, 0 ms] (36) YES (37) QDP (38) UsableRulesProof [EQUIVALENT, 0 ms] (39) QDP (40) QReductionProof [EQUIVALENT, 0 ms] (41) QDP (42) Induction-Processor [SOUND, 80 ms] (43) AND (44) QDP (45) PisEmptyProof [EQUIVALENT, 0 ms] (46) YES (47) QTRS (48) Overlay + Local Confluence [EQUIVALENT, 0 ms] (49) QTRS (50) DependencyPairsProof [EQUIVALENT, 4 ms] (51) QDP (52) DependencyGraphProof [EQUIVALENT, 0 ms] (53) AND (54) QDP (55) UsableRulesProof [EQUIVALENT, 0 ms] (56) QDP (57) QReductionProof [EQUIVALENT, 0 ms] (58) QDP (59) QDPSizeChangeProof [EQUIVALENT, 0 ms] (60) YES (61) QDP (62) UsableRulesProof [EQUIVALENT, 0 ms] (63) QDP (64) QReductionProof [EQUIVALENT, 0 ms] (65) QDP (66) QDPSizeChangeProof [EQUIVALENT, 0 ms] (67) YES (68) QDP (69) UsableRulesProof [EQUIVALENT, 0 ms] (70) QDP (71) QReductionProof [EQUIVALENT, 0 ms] (72) QDP (73) QDPSizeChangeProof [EQUIVALENT, 0 ms] (74) YES (75) QDP (76) UsableRulesProof [EQUIVALENT, 0 ms] (77) QDP (78) QReductionProof [EQUIVALENT, 0 ms] (79) QDP (80) QDPSizeChangeProof [EQUIVALENT, 0 ms] (81) YES (82) QDP (83) UsableRulesProof [EQUIVALENT, 0 ms] (84) QDP (85) QReductionProof [EQUIVALENT, 0 ms] (86) QDP (87) QDPSizeChangeProof [EQUIVALENT, 0 ms] (88) YES (89) QDP (90) UsableRulesProof [EQUIVALENT, 0 ms] (91) QDP (92) QReductionProof [EQUIVALENT, 0 ms] (93) QDP (94) QDPOrderProof [EQUIVALENT, 0 ms] (95) QDP (96) PisEmptyProof [EQUIVALENT, 0 ms] (97) YES (98) QDP (99) UsableRulesProof [EQUIVALENT, 0 ms] (100) QDP (101) QReductionProof [EQUIVALENT, 0 ms] (102) QDP (103) QDPSizeChangeProof [EQUIVALENT, 0 ms] (104) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: max(nil) -> 0 max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, nil) -> nil del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) sort(nil) -> nil sort(cons(x, xs)) -> cons(max(cons(x, xs)), sort(del(max(cons(x, xs)), cons(x, xs)))) ge(0, 0) -> true ge(s(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: max(nil) -> 0 max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, nil) -> nil del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) sort(nil) -> nil sort(cons(x, xs)) -> cons(max(cons(x, xs)), sort(del(max(cons(x, xs)), cons(x, xs)))) ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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: MAX(cons(x, cons(y, xs))) -> IF1(ge(x, y), x, y, xs) MAX(cons(x, cons(y, xs))) -> GE(x, y) IF1(true, x, y, xs) -> MAX(cons(x, xs)) IF1(false, x, y, xs) -> MAX(cons(y, xs)) DEL(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs) DEL(x, cons(y, xs)) -> EQ(x, y) IF2(false, x, y, xs) -> DEL(x, xs) EQ(s(x), s(y)) -> EQ(x, y) SORT(cons(x, xs)) -> MAX(cons(x, xs)) SORT(cons(x, xs)) -> SORT(del(max(cons(x, xs)), cons(x, xs))) SORT(cons(x, xs)) -> DEL(max(cons(x, xs)), cons(x, xs)) GE(s(x), s(y)) -> GE(x, y) The TRS R consists of the following rules: max(nil) -> 0 max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, nil) -> nil del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) sort(nil) -> nil sort(cons(x, xs)) -> cons(max(cons(x, xs)), sort(del(max(cons(x, xs)), cons(x, xs)))) ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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 5 SCCs with 4 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: max(nil) -> 0 max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, nil) -> nil del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) sort(nil) -> nil sort(cons(x, xs)) -> cons(max(cons(x, xs)), sort(del(max(cons(x, xs)), cons(x, xs)))) ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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]. max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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: EQ(s(x), s(y)) -> EQ(x, y) The TRS R consists of the following rules: max(nil) -> 0 max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, nil) -> nil del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) sort(nil) -> nil sort(cons(x, xs)) -> cons(max(cons(x, xs)), sort(del(max(cons(x, xs)), cons(x, xs)))) ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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: EQ(s(x), s(y)) -> EQ(x, y) R is empty. The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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]. max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(x), s(y)) -> EQ(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: *EQ(s(x), s(y)) -> EQ(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: IF2(false, x, y, xs) -> DEL(x, xs) DEL(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs) The TRS R consists of the following rules: max(nil) -> 0 max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, nil) -> nil del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) sort(nil) -> nil sort(cons(x, xs)) -> cons(max(cons(x, xs)), sort(del(max(cons(x, xs)), cons(x, xs)))) ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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: IF2(false, x, y, xs) -> DEL(x, xs) DEL(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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]. max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(false, x, y, xs) -> DEL(x, xs) DEL(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(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: *DEL(x, cons(y, xs)) -> IF2(eq(x, y), x, y, xs) The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4 *IF2(false, x, y, xs) -> DEL(x, xs) The graph contains the following edges 2 >= 1, 4 >= 2 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(true, x, y, xs) -> MAX(cons(x, xs)) MAX(cons(x, cons(y, xs))) -> IF1(ge(x, y), x, y, xs) IF1(false, x, y, xs) -> MAX(cons(y, xs)) The TRS R consists of the following rules: max(nil) -> 0 max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, nil) -> nil del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) sort(nil) -> nil sort(cons(x, xs)) -> cons(max(cons(x, xs)), sort(del(max(cons(x, xs)), cons(x, xs)))) ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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: IF1(true, x, y, xs) -> MAX(cons(x, xs)) MAX(cons(x, cons(y, xs))) -> IF1(ge(x, y), x, y, xs) IF1(false, x, y, xs) -> MAX(cons(y, xs)) The TRS R consists of the following rules: ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(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]. max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(true, x, y, xs) -> MAX(cons(x, xs)) MAX(cons(x, cons(y, xs))) -> IF1(ge(x, y), x, y, xs) IF1(false, x, y, xs) -> MAX(cons(y, xs)) The TRS R consists of the following rules: ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. IF1(true, x, y, xs) -> MAX(cons(x, xs)) MAX(cons(x, cons(y, xs))) -> IF1(ge(x, y), x, y, xs) IF1(false, x, y, xs) -> MAX(cons(y, xs)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. IF1(x1, x2, x3, x4) = IF1(x4) MAX(x1) = x1 cons(x1, x2) = cons(x2) Knuth-Bendix order [KBO] with precedence:trivial and weight map: dummyConstant=1 IF1_1=3 cons_1=2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (34) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (36) YES ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: SORT(cons(x, xs)) -> SORT(del(max(cons(x, xs)), cons(x, xs))) The TRS R consists of the following rules: max(nil) -> 0 max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, nil) -> nil del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) sort(nil) -> nil sort(cons(x, xs)) -> cons(max(cons(x, xs)), sort(del(max(cons(x, xs)), cons(x, xs)))) ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) 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. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: SORT(cons(x, xs)) -> SORT(del(max(cons(x, xs)), cons(x, xs))) The TRS R consists of the following rules: max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) del(x, nil) -> nil ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) sort(nil) sort(cons(x0, x1)) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) 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]. sort(nil) sort(cons(x0, x1)) ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: SORT(cons(x, xs)) -> SORT(del(max(cons(x, xs)), cons(x, xs))) The TRS R consists of the following rules: max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) del(x, nil) -> nil ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) Induction-Processor (SOUND) This DP could be deleted by the Induction-Processor: SORT(cons(x, xs)) -> SORT(del(max(cons(x, xs)), cons(x, xs))) This order was computed: Polynomial interpretation [POLO]: POL(0) = 0 POL(SORT(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(del(x_1, x_2)) = x_2 POL(eq(x_1, x_2)) = 0 POL(false_renamed) = 0 POL(ge(x_1, x_2)) = 1 POL(if1(x_1, x_2, x_3, x_4)) = 1 + 2*x_1 + x_2 + 2*x_3 + 2*x_4 POL(if2(x_1, x_2, x_3, x_4)) = 1 + x_3 + 2*x_4 POL(max(x_1)) = x_1 POL(nil) = 0 POL(s(x_1)) = 3*x_1 POL(true_renamed) = 0 At least one of these decreasing rules is always used after the deleted DP: if2(true_renamed, x6, y4, xs3) -> xs3 The following formula is valid: z0:sort[a35].(~(z0=nil)->del'(max(z0), z0)=true) The transformed set: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> 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, v27, v28, v29, v30, v31, v32, v33, v34, v35, x6, y4, xs3, x7, y5, y1, xs2, x8, x3, x', x'', y, xs', y2, x4, x5, y3, x9, x10, x11, y6, x1, y', x2, y'', xs'', xs1] 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> equal_sort[a0](v30, v32) and equal_sort[a35](v31, v33) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, cons(y1, xs2)) -> if2'(eq(x7, y1), x7, y1, xs2) if2'(false_renamed, x7, y5, nil) -> false del'(x8, nil) -> false equal_sort[a43](eq(x3, y1), true_renamed) -> true | del'(x3, cons(y1, xs2)) -> true equal_sort[a43](eq(x3, y1), true_renamed) -> false | del'(x3, cons(y1, xs2)) -> del'(x3, xs2) max(cons(x', nil)) -> x' max(nil) -> 0 equal_sort[a43](ge(x'', y), true_renamed) -> true | max(cons(x'', cons(y, xs'))) -> max(cons(x'', xs')) equal_sort[a43](ge(x'', y), true_renamed) -> false | max(cons(x'', cons(y, xs'))) -> max(cons(y, xs')) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, cons(y1, xs2)) -> cons(y5, if2(eq(x7, y1), x7, y1, xs2)) if2(false_renamed, x7, y5, nil) -> cons(y5, nil) del(x8, nil) -> nil equal_sort[a43](eq(x3, y1), true_renamed) -> true | del(x3, cons(y1, xs2)) -> xs2 equal_sort[a43](eq(x3, y1), true_renamed) -> false | del(x3, cons(y1, xs2)) -> cons(y1, del(x3, xs2)) ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) if1(true_renamed, x1, y', nil) -> x1 if1(true_renamed, x1, y', cons(y, xs')) -> if1(ge(x1, y), x1, y, xs') if1(false_renamed, x2, y'', nil) -> y'' if1(false_renamed, x2, y'', cons(y, xs')) -> if1(ge(y'', y), y'', y, xs') if1(true_renamed, x1, y', xs'') -> 0 if1(false_renamed, x2, y'', xs1) -> 0 using the following formula: z0:sort[a35].(~(z0=nil)->del'(max(z0), 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 [EQUIVALENT, 0 ms] (10) YES (11) Formula (12) Conditional Evaluation [EQUIVALENT, 0 ms] (13) AND (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) Symbolic evaluation under hypothesis [SOUND, 0 ms] (23) Formula (24) Hypothesis Lifting [EQUIVALENT, 0 ms] (25) Formula (26) Hypothesis Lifting [EQUIVALENT, 0 ms] (27) Formula (28) Conditional Evaluation [EQUIVALENT, 0 ms] (29) AND (30) Formula (31) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms] (32) YES (33) Formula (34) Symbolic evaluation [EQUIVALENT, 0 ms] (35) YES (36) Formula (37) Symbolic evaluation [EQUIVALENT, 0 ms] (38) YES (39) Formula (40) Symbolic evaluation [EQUIVALENT, 0 ms] (41) Formula (42) Conditional Evaluation [EQUIVALENT, 0 ms] (43) Formula (44) Conditional Evaluation [EQUIVALENT, 0 ms] (45) AND (46) Formula (47) Symbolic evaluation [EQUIVALENT, 0 ms] (48) YES (49) Formula (50) Conditional Evaluation [EQUIVALENT, 0 ms] (51) AND (52) Formula (53) Symbolic evaluation [EQUIVALENT, 0 ms] (54) YES (55) Formula (56) Hypothesis Lifting [EQUIVALENT, 0 ms] (57) Formula (58) Conditional Evaluation [EQUIVALENT, 0 ms] (59) Formula (60) Symbolic evaluation [EQUIVALENT, 0 ms] (61) YES (62) Formula (63) Symbolic evaluation [EQUIVALENT, 0 ms] (64) Formula (65) Conditional Evaluation [EQUIVALENT, 0 ms] (66) Formula (67) Conditional Evaluation [EQUIVALENT, 0 ms] (68) AND (69) Formula (70) Symbolic evaluation [EQUIVALENT, 0 ms] (71) YES (72) Formula (73) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms] (74) YES ---------------------------------------- (0) Obligation: Formula: z0:sort[a35].(~(z0=nil)->del'(max(z0), z0)=true) There are no hypotheses. ---------------------------------------- (1) Induction by algorithm (EQUIVALENT) Induction by algorithm max(z0) generates the following cases: 1. Base Case: Formula: x':sort[a0].(~(cons(x', nil)=nil)->del'(max(cons(x', nil)), cons(x', nil))=true) There are no hypotheses. 2. Base Case: Formula: (~(nil=nil)->del'(max(nil), nil)=true) There are no hypotheses. 1. Step Case: Formula: x'':sort[a0],y:sort[a0],xs':sort[a35].(~(cons(x'', cons(y, xs'))=nil)->del'(max(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true) Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true 2. Step Case: Formula: x'':sort[a0],y:sort[a0],xs':sort[a35].(~(cons(x'', cons(y, xs'))=nil)->del'(max(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true) Hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=false ---------------------------------------- (2) Complex Obligation (AND) ---------------------------------------- (3) Obligation: Formula: x':sort[a0].(~(cons(x', nil)=nil)->del'(max(cons(x', nil)), cons(x', nil))=true) There are no hypotheses. ---------------------------------------- (4) Symbolic evaluation (EQUIVALENT) Could be shown by simple symbolic evaluation. ---------------------------------------- (5) Obligation: Formula: x':sort[a0].del'(x', cons(x', nil))=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: del'(0, cons(0, nil))=true There are no hypotheses. 1. Step Case: Formula: n:sort[a0].del'(s(n), cons(s(n), nil))=true Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true ---------------------------------------- (7) Complex Obligation (AND) ---------------------------------------- (8) Obligation: Formula: del'(0, cons(0, nil))=true There are no hypotheses. ---------------------------------------- (9) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (10) YES ---------------------------------------- (11) Obligation: Formula: n:sort[a0].del'(s(n), cons(s(n), nil))=true Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true ---------------------------------------- (12) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: true=true Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=true Formula: n:sort[a0].del'(s(n), nil)=true Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false ---------------------------------------- (13) Complex Obligation (AND) ---------------------------------------- (14) Obligation: Formula: true=true Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=true ---------------------------------------- (15) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (16) YES ---------------------------------------- (17) Obligation: Formula: n:sort[a0].del'(s(n), nil)=true Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false ---------------------------------------- (18) Symbolic evaluation (EQUIVALENT) Could be shown by simple symbolic evaluation. ---------------------------------------- (19) Obligation: Formula: False Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false ---------------------------------------- (20) Hypothesis Lifting (EQUIVALENT) Formula could be generalised by hypothesis lifting to the following new obligation: Formula: n:sort[a0].((del'(n, cons(n, nil))=true/\equal_sort[a43](eq(s(n), s(n)), true_renamed)=false)->False) Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false ---------------------------------------- (21) Obligation: Formula: n:sort[a0].((del'(n, cons(n, nil))=true/\equal_sort[a43](eq(s(n), s(n)), true_renamed)=false)->False) Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false ---------------------------------------- (22) Symbolic evaluation under hypothesis (SOUND) Could be reduced by symbolic evaluation under hypothesis to: n:sort[a0].~(equal_sort[a43](eq(n, n), true_renamed)=false) By using the following hypotheses: n:sort[a0].del'(n, cons(n, nil))=true ---------------------------------------- (23) Obligation: Formula: n:sort[a0].~(equal_sort[a43](eq(n, n), true_renamed)=false) Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true n:sort[a0].equal_sort[a43](eq(s(n), s(n)), true_renamed)=false ---------------------------------------- (24) Hypothesis Lifting (EQUIVALENT) Formula could be generalised by hypothesis lifting to the following new obligation: Formula: n:sort[a0].(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false)) Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true ---------------------------------------- (25) Obligation: Formula: n:sort[a0].(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false)) Hypotheses: n:sort[a0].del'(n, cons(n, nil))=true ---------------------------------------- (26) Hypothesis Lifting (EQUIVALENT) Formula could be generalised by hypothesis lifting to the following new obligation: Formula: n:sort[a0].(del'(n, cons(n, nil))=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false))) There are no hypotheses. ---------------------------------------- (27) Obligation: Formula: n:sort[a0].(del'(n, cons(n, nil))=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false))) There are no hypotheses. ---------------------------------------- (28) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: n:sort[a0].(true=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false))) Hypotheses: n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=true Formula: n:sort[a0].(del'(n, nil)=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false))) Hypotheses: n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=false ---------------------------------------- (29) Complex Obligation (AND) ---------------------------------------- (30) Obligation: Formula: n:sort[a0].(true=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false))) Hypotheses: n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=true ---------------------------------------- (31) Symbolic evaluation under hypothesis (EQUIVALENT) Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses: n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=true ---------------------------------------- (32) YES ---------------------------------------- (33) Obligation: Formula: n:sort[a0].(del'(n, nil)=true->(equal_sort[a43](eq(n, n), true_renamed)=false->~(equal_sort[a43](eq(n, n), true_renamed)=false))) Hypotheses: n:sort[a0].equal_sort[a43](eq(n, n), true_renamed)=false ---------------------------------------- (34) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (35) YES ---------------------------------------- (36) Obligation: Formula: (~(nil=nil)->del'(max(nil), nil)=true) There are no hypotheses. ---------------------------------------- (37) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (38) YES ---------------------------------------- (39) Obligation: Formula: x'':sort[a0],y:sort[a0],xs':sort[a35].(~(cons(x'', cons(y, xs'))=nil)->del'(max(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true) Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true ---------------------------------------- (40) Symbolic evaluation (EQUIVALENT) Could be shown by simple symbolic evaluation. ---------------------------------------- (41) Obligation: Formula: x'':sort[a0],y:sort[a0],xs':sort[a35].del'(max(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true ---------------------------------------- (42) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: x'':sort[a0],xs':sort[a35],y:sort[a0].del'(max(cons(x'', xs')), cons(x'', cons(y, xs')))=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true ---------------------------------------- (43) Obligation: Formula: x'':sort[a0],xs':sort[a35],y:sort[a0].del'(max(cons(x'', xs')), cons(x'', cons(y, xs')))=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true ---------------------------------------- (44) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: true=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=true Formula: x'':sort[a0],xs':sort[a35],y:sort[a0].del'(max(cons(x'', xs')), cons(y, xs'))=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false ---------------------------------------- (45) Complex Obligation (AND) ---------------------------------------- (46) Obligation: Formula: true=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=true ---------------------------------------- (47) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (48) YES ---------------------------------------- (49) Obligation: Formula: x'':sort[a0],xs':sort[a35],y:sort[a0].del'(max(cons(x'', xs')), cons(y, xs'))=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false ---------------------------------------- (50) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: true=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(max(cons(x'', xs')), y), true_renamed)=true Formula: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), xs')=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(max(cons(x'', xs')), y), true_renamed)=false ---------------------------------------- (51) Complex Obligation (AND) ---------------------------------------- (52) Obligation: Formula: true=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(max(cons(x'', xs')), y), true_renamed)=true ---------------------------------------- (53) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (54) YES ---------------------------------------- (55) Obligation: Formula: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), xs')=true Hypotheses: x'':sort[a0],xs':sort[a35].del'(max(cons(x'', xs')), cons(x'', xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(max(cons(x'', xs')), y), true_renamed)=false ---------------------------------------- (56) Hypothesis Lifting (EQUIVALENT) Formula could be generalised by hypothesis lifting to the following new obligation: Formula: x'':sort[a0],xs':sort[a35].(del'(max(cons(x'', xs')), cons(x'', xs'))=true->del'(max(cons(x'', xs')), xs')=true) Hypotheses: x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(max(cons(x'', xs')), y), true_renamed)=false ---------------------------------------- (57) Obligation: Formula: x'':sort[a0],xs':sort[a35].(del'(max(cons(x'', xs')), cons(x'', xs'))=true->del'(max(cons(x'', xs')), xs')=true) Hypotheses: x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(max(cons(x'', xs')), y), true_renamed)=false ---------------------------------------- (58) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: x'':sort[a0],xs':sort[a35].(del'(max(cons(x'', xs')), xs')=true->del'(max(cons(x'', xs')), xs')=true) Hypotheses: x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(max(cons(x'', xs')), y), true_renamed)=false ---------------------------------------- (59) Obligation: Formula: x'':sort[a0],xs':sort[a35].(del'(max(cons(x'', xs')), xs')=true->del'(max(cons(x'', xs')), xs')=true) Hypotheses: x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=true x'':sort[a0],xs':sort[a35].equal_sort[a43](eq(max(cons(x'', xs')), x''), true_renamed)=false x'':sort[a0],xs':sort[a35],y:sort[a0].equal_sort[a43](eq(max(cons(x'', xs')), y), true_renamed)=false ---------------------------------------- (60) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (61) YES ---------------------------------------- (62) Obligation: Formula: x'':sort[a0],y:sort[a0],xs':sort[a35].(~(cons(x'', cons(y, xs'))=nil)->del'(max(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true) Hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=false ---------------------------------------- (63) Symbolic evaluation (EQUIVALENT) Could be shown by simple symbolic evaluation. ---------------------------------------- (64) Obligation: Formula: x'':sort[a0],y:sort[a0],xs':sort[a35].del'(max(cons(x'', cons(y, xs'))), cons(x'', cons(y, xs')))=true Hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=false ---------------------------------------- (65) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: y:sort[a0],xs':sort[a35],x'':sort[a0].del'(max(cons(y, xs')), cons(x'', cons(y, xs')))=true Hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=false ---------------------------------------- (66) Obligation: Formula: y:sort[a0],xs':sort[a35],x'':sort[a0].del'(max(cons(y, xs')), cons(x'', cons(y, xs')))=true Hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=false ---------------------------------------- (67) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: true=true Hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=false y:sort[a0],xs':sort[a35],x'':sort[a0].equal_sort[a43](eq(max(cons(y, xs')), x''), true_renamed)=true Formula: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true Hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=false y:sort[a0],xs':sort[a35],x'':sort[a0].equal_sort[a43](eq(max(cons(y, xs')), x''), true_renamed)=false ---------------------------------------- (68) Complex Obligation (AND) ---------------------------------------- (69) Obligation: Formula: true=true Hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=false y:sort[a0],xs':sort[a35],x'':sort[a0].equal_sort[a43](eq(max(cons(y, xs')), x''), true_renamed)=true ---------------------------------------- (70) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (71) YES ---------------------------------------- (72) Obligation: Formula: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true Hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true x'':sort[a0],y:sort[a0].equal_sort[a43](ge(x'', y), true_renamed)=false y:sort[a0],xs':sort[a35],x'':sort[a0].equal_sort[a43](eq(max(cons(y, xs')), x''), true_renamed)=false ---------------------------------------- (73) Symbolic evaluation under hypothesis (EQUIVALENT) Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses: y:sort[a0],xs':sort[a35].del'(max(cons(y, xs')), cons(y, xs'))=true ---------------------------------------- (74) YES ---------------------------------------- (43) Complex Obligation (AND) ---------------------------------------- (44) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: max(cons(x, nil)) -> x max(cons(x, cons(y, xs))) -> if1(ge(x, y), x, y, xs) if1(true, x, y, xs) -> max(cons(x, xs)) if1(false, x, y, xs) -> max(cons(y, xs)) del(x, cons(y, xs)) -> if2(eq(x, y), x, y, xs) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) del(x, nil) -> nil ge(0, 0) -> true ge(s(x), 0) -> true ge(0, s(x)) -> false ge(s(x), s(y)) -> ge(x, y) The set Q consists of the following terms: max(nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true, x0, x1, x2) if1(false, x0, x1, x2) del(x0, nil) del(x0, cons(x1, x2)) if2(true, x0, x1, x2) if2(false, x0, x1, x2) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (46) YES ---------------------------------------- (47) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true Q is empty. ---------------------------------------- (48) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (49) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) ---------------------------------------- (50) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: DEL'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2) DEL'(x3, cons(y1, xs2)) -> EQ(x3, y1) IF2'(false_renamed, x7, y5, xs4) -> DEL'(x7, xs4) MAX(cons(x'', cons(y, xs'))) -> IF1(ge(x'', y), x'', y, xs') MAX(cons(x'', cons(y, xs'))) -> GE(x'', y) IF1(true_renamed, x1, y', xs'') -> MAX(cons(x1, xs'')) IF1(false_renamed, x2, y'', xs1) -> MAX(cons(y'', xs1)) DEL(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2) DEL(x3, cons(y1, xs2)) -> EQ(x3, y1) EQ(s(x5), s(y3)) -> EQ(x5, y3) IF2(false_renamed, x7, y5, xs4) -> DEL(x7, xs4) GE(s(x11), s(y6)) -> GE(x11, y6) EQUAL_SORT[A0](s(v28), s(v29)) -> EQUAL_SORT[A0](v28, v29) EQUAL_SORT[A35](cons(v30, v31), cons(v32, v33)) -> AND(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) EQUAL_SORT[A35](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A0](v30, v32) EQUAL_SORT[A35](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A35](v31, v33) The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 7 SCCs with 5 less nodes. ---------------------------------------- (53) Complex Obligation (AND) ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A0](s(v28), s(v29)) -> EQUAL_SORT[A0](v28, v29) The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) 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. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A0](s(v28), s(v29)) -> EQUAL_SORT[A0](v28, v29) R is empty. The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) 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]. del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A0](s(v28), s(v29)) -> EQUAL_SORT[A0](v28, v29) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) 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: *EQUAL_SORT[A0](s(v28), s(v29)) -> EQUAL_SORT[A0](v28, v29) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (60) YES ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A35](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A35](v31, v33) The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) 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. ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A35](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A35](v31, v33) R is empty. The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) 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]. del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A35](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A35](v31, v33) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) 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: *EQUAL_SORT[A35](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A35](v31, v33) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (67) YES ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: GE(s(x11), s(y6)) -> GE(x11, y6) The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) 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. ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: GE(s(x11), s(y6)) -> GE(x11, y6) R is empty. The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (71) 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]. del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: GE(s(x11), s(y6)) -> GE(x11, y6) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) 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(x11), s(y6)) -> GE(x11, y6) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (74) YES ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(x5), s(y3)) -> EQ(x5, y3) The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (76) 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. ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(x5), s(y3)) -> EQ(x5, y3) R is empty. The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (78) 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]. del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(x5), s(y3)) -> EQ(x5, y3) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (80) 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: *EQ(s(x5), s(y3)) -> EQ(x5, y3) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (81) YES ---------------------------------------- (82) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(false_renamed, x7, y5, xs4) -> DEL(x7, xs4) DEL(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2) The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (83) 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. ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(false_renamed, x7, y5, xs4) -> DEL(x7, xs4) DEL(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2) The TRS R consists of the following rules: eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (85) 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]. del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(false_renamed, x7, y5, xs4) -> DEL(x7, xs4) DEL(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2) The TRS R consists of the following rules: eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (87) 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: *DEL(x3, cons(y1, xs2)) -> IF2(eq(x3, y1), x3, y1, xs2) The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4 *IF2(false_renamed, x7, y5, xs4) -> DEL(x7, xs4) The graph contains the following edges 2 >= 1, 4 >= 2 ---------------------------------------- (88) YES ---------------------------------------- (89) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(true_renamed, x1, y', xs'') -> MAX(cons(x1, xs'')) MAX(cons(x'', cons(y, xs'))) -> IF1(ge(x'', y), x'', y, xs') IF1(false_renamed, x2, y'', xs1) -> MAX(cons(y'', xs1)) The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (90) 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. ---------------------------------------- (91) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(true_renamed, x1, y', xs'') -> MAX(cons(x1, xs'')) MAX(cons(x'', cons(y, xs'))) -> IF1(ge(x'', y), x'', y, xs') IF1(false_renamed, x2, y'', xs1) -> MAX(cons(y'', xs1)) The TRS R consists of the following rules: ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (92) 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]. del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) ---------------------------------------- (93) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(true_renamed, x1, y', xs'') -> MAX(cons(x1, xs'')) MAX(cons(x'', cons(y, xs'))) -> IF1(ge(x'', y), x'', y, xs') IF1(false_renamed, x2, y'', xs1) -> MAX(cons(y'', xs1)) The TRS R consists of the following rules: ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) The set Q consists of the following terms: ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (94) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. IF1(true_renamed, x1, y', xs'') -> MAX(cons(x1, xs'')) MAX(cons(x'', cons(y, xs'))) -> IF1(ge(x'', y), x'', y, xs') IF1(false_renamed, x2, y'', xs1) -> MAX(cons(y'', xs1)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. IF1(x1, x2, x3, x4) = IF1(x4) MAX(x1) = x1 cons(x1, x2) = cons(x2) Knuth-Bendix order [KBO] with precedence:trivial and weight map: dummyConstant=1 IF1_1=3 cons_1=2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (95) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) The set Q consists of the following terms: ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (96) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (97) YES ---------------------------------------- (98) Obligation: Q DP problem: The TRS P consists of the following rules: IF2'(false_renamed, x7, y5, xs4) -> DEL'(x7, xs4) DEL'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2) The TRS R consists of the following rules: del'(x3, cons(y1, xs2)) -> if2'(eq(x3, y1), x3, y1, xs2) if2'(true_renamed, x6, y4, xs3) -> true if2'(false_renamed, x7, y5, xs4) -> del'(x7, xs4) del'(x8, nil) -> false max(cons(x', nil)) -> x' max(cons(x'', cons(y, xs'))) -> if1(ge(x'', y), x'', y, xs') if1(true_renamed, x1, y', xs'') -> max(cons(x1, xs'')) if1(false_renamed, x2, y'', xs1) -> max(cons(y'', xs1)) del(x3, cons(y1, xs2)) -> if2(eq(x3, y1), x3, y1, xs2) eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) if2(true_renamed, x6, y4, xs3) -> xs3 if2(false_renamed, x7, y5, xs4) -> cons(y5, del(x7, xs4)) del(x8, nil) -> nil ge(0, 0) -> true_renamed ge(s(x9), 0) -> true_renamed ge(0, s(x10)) -> false_renamed ge(s(x11), s(y6)) -> ge(x11, y6) max(nil) -> 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](0, 0) -> true equal_sort[a0](0, s(v27)) -> false equal_sort[a0](s(v28), 0) -> false equal_sort[a0](s(v28), s(v29)) -> equal_sort[a0](v28, v29) equal_sort[a35](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a35](v31, v33)) equal_sort[a35](cons(v30, v31), nil) -> false equal_sort[a35](nil, cons(v34, v35)) -> false equal_sort[a35](nil, nil) -> true equal_sort[a43](true_renamed, true_renamed) -> true equal_sort[a43](true_renamed, false_renamed) -> false equal_sort[a43](false_renamed, true_renamed) -> false equal_sort[a43](false_renamed, false_renamed) -> true equal_sort[a61](witness_sort[a61], witness_sort[a61]) -> true The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (99) 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. ---------------------------------------- (100) Obligation: Q DP problem: The TRS P consists of the following rules: IF2'(false_renamed, x7, y5, xs4) -> DEL'(x7, xs4) DEL'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2) The TRS R consists of the following rules: eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) The set Q consists of the following terms: del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (101) 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]. del'(x0, cons(x1, x2)) if2'(true_renamed, x0, x1, x2) if2'(false_renamed, x0, x1, x2) del'(x0, nil) max(cons(x0, nil)) max(cons(x0, cons(x1, x2))) if1(true_renamed, x0, x1, x2) if1(false_renamed, x0, x1, x2) del(x0, cons(x1, x2)) if2(true_renamed, x0, x1, x2) if2(false_renamed, x0, x1, x2) del(x0, nil) ge(0, 0) ge(s(x0), 0) ge(0, s(x0)) ge(s(x0), s(x1)) max(nil) equal_bool(true, false) equal_bool(false, true) equal_bool(true, true) equal_bool(false, false) and(true, x0) and(false, x0) or(true, x0) or(false, x0) not(false) not(true) isa_true(true) isa_true(false) isa_false(true) isa_false(false) equal_sort[a0](0, 0) equal_sort[a0](0, s(x0)) equal_sort[a0](s(x0), 0) equal_sort[a0](s(x0), s(x1)) equal_sort[a35](cons(x0, x1), cons(x2, x3)) equal_sort[a35](cons(x0, x1), nil) equal_sort[a35](nil, cons(x0, x1)) equal_sort[a35](nil, nil) equal_sort[a43](true_renamed, true_renamed) equal_sort[a43](true_renamed, false_renamed) equal_sort[a43](false_renamed, true_renamed) equal_sort[a43](false_renamed, false_renamed) equal_sort[a61](witness_sort[a61], witness_sort[a61]) ---------------------------------------- (102) Obligation: Q DP problem: The TRS P consists of the following rules: IF2'(false_renamed, x7, y5, xs4) -> DEL'(x7, xs4) DEL'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2) The TRS R consists of the following rules: eq(0, 0) -> true_renamed eq(0, s(y2)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y3)) -> eq(x5, y3) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (103) 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: *DEL'(x3, cons(y1, xs2)) -> IF2'(eq(x3, y1), x3, y1, xs2) The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4 *IF2'(false_renamed, x7, y5, xs4) -> DEL'(x7, xs4) The graph contains the following edges 2 >= 1, 4 >= 2 ---------------------------------------- (104) YES