/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) Overlay + Local Confluence [EQUIVALENT, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QReductionProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) QDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) QDP (17) QReductionProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) QDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) QDP (24) QReductionProof [EQUIVALENT, 1 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) QDPSizeChangeProof [EQUIVALENT, 0 ms] (34) YES (35) QDP (36) UsableRulesProof [EQUIVALENT, 0 ms] (37) QDP (38) QReductionProof [EQUIVALENT, 4 ms] (39) QDP (40) Induction-Processor [SOUND, 562 ms] (41) AND (42) QDP (43) PisEmptyProof [EQUIVALENT, 0 ms] (44) YES (45) QTRS (46) Overlay + Local Confluence [EQUIVALENT, 10 ms] (47) QTRS (48) DependencyPairsProof [EQUIVALENT, 0 ms] (49) QDP (50) DependencyGraphProof [EQUIVALENT, 0 ms] (51) AND (52) QDP (53) UsableRulesProof [EQUIVALENT, 0 ms] (54) QDP (55) QReductionProof [EQUIVALENT, 0 ms] (56) QDP (57) QDPSizeChangeProof [EQUIVALENT, 0 ms] (58) YES (59) QDP (60) UsableRulesProof [EQUIVALENT, 0 ms] (61) QDP (62) QReductionProof [EQUIVALENT, 0 ms] (63) QDP (64) QDPSizeChangeProof [EQUIVALENT, 0 ms] (65) YES (66) QDP (67) UsableRulesProof [EQUIVALENT, 0 ms] (68) QDP (69) QReductionProof [EQUIVALENT, 0 ms] (70) QDP (71) QDPSizeChangeProof [EQUIVALENT, 0 ms] (72) YES (73) QDP (74) UsableRulesProof [EQUIVALENT, 0 ms] (75) QDP (76) QReductionProof [EQUIVALENT, 0 ms] (77) QDP (78) QDPSizeChangeProof [EQUIVALENT, 0 ms] (79) YES (80) QDP (81) UsableRulesProof [EQUIVALENT, 0 ms] (82) QDP (83) QReductionProof [EQUIVALENT, 0 ms] (84) QDP (85) QDPSizeChangeProof [EQUIVALENT, 0 ms] (86) YES (87) QDP (88) UsableRulesProof [EQUIVALENT, 0 ms] (89) QDP (90) QReductionProof [EQUIVALENT, 0 ms] (91) QDP (92) QDPSizeChangeProof [EQUIVALENT, 0 ms] (93) YES (94) QDP (95) UsableRulesProof [EQUIVALENT, 0 ms] (96) QDP (97) QReductionProof [EQUIVALENT, 0 ms] (98) QDP (99) QDPSizeChangeProof [EQUIVALENT, 0 ms] (100) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) minsort(nil) -> nil minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) del(x, nil) -> nil del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 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: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) minsort(nil) -> nil minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) del(x, nil) -> nil del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) ---------------------------------------- (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: LE(s(x), s(y)) -> LE(x, y) EQ(s(x), s(y)) -> EQ(x, y) IF1(true, x, y, xs) -> MIN(x, xs) IF1(false, x, y, xs) -> MIN(y, xs) IF2(false, x, y, xs) -> DEL(x, xs) MINSORT(cons(x, y)) -> MIN(x, y) MINSORT(cons(x, y)) -> MINSORT(del(min(x, y), cons(x, y))) MINSORT(cons(x, y)) -> DEL(min(x, y), cons(x, y)) MIN(x, cons(y, z)) -> IF1(le(x, y), x, y, z) MIN(x, cons(y, z)) -> LE(x, y) DEL(x, cons(y, z)) -> IF2(eq(x, y), x, y, z) DEL(x, cons(y, z)) -> EQ(x, y) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) minsort(nil) -> nil minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) del(x, nil) -> nil del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) 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: EQ(s(x), s(y)) -> EQ(x, y) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) minsort(nil) -> nil minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) del(x, nil) -> nil del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) 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: EQ(s(x), s(y)) -> EQ(x, y) R is empty. The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) 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]. le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) ---------------------------------------- (11) 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. ---------------------------------------- (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: *EQ(s(x), s(y)) -> EQ(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: DEL(x, cons(y, z)) -> IF2(eq(x, y), x, y, z) IF2(false, x, y, xs) -> DEL(x, xs) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) minsort(nil) -> nil minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) del(x, nil) -> nil del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) 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: DEL(x, cons(y, z)) -> IF2(eq(x, y), x, y, z) IF2(false, x, y, xs) -> DEL(x, 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: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) 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]. le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: DEL(x, cons(y, z)) -> IF2(eq(x, y), x, y, z) IF2(false, x, y, xs) -> DEL(x, 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. ---------------------------------------- (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: *IF2(false, x, y, xs) -> DEL(x, xs) The graph contains the following edges 2 >= 1, 4 >= 2 *DEL(x, cons(y, z)) -> IF2(eq(x, y), x, y, z) The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(x), s(y)) -> LE(x, y) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) minsort(nil) -> nil minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) del(x, nil) -> nil del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) 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: LE(s(x), s(y)) -> LE(x, y) R is empty. The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) 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]. le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(x), s(y)) -> LE(x, y) R is empty. Q is empty. 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: *LE(s(x), s(y)) -> LE(x, y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: MIN(x, cons(y, z)) -> IF1(le(x, y), x, y, z) IF1(true, x, y, xs) -> MIN(x, xs) IF1(false, x, y, xs) -> MIN(y, xs) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) minsort(nil) -> nil minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) del(x, nil) -> nil del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) 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: MIN(x, cons(y, z)) -> IF1(le(x, y), x, y, z) IF1(true, x, y, xs) -> MIN(x, xs) IF1(false, x, y, xs) -> MIN(y, xs) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) 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]. eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: MIN(x, cons(y, z)) -> IF1(le(x, y), x, y, z) IF1(true, x, y, xs) -> MIN(x, xs) IF1(false, x, y, xs) -> MIN(y, xs) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) 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: *MIN(x, cons(y, z)) -> IF1(le(x, y), x, y, z) The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4 *IF1(true, x, y, xs) -> MIN(x, xs) The graph contains the following edges 2 >= 1, 4 >= 2 *IF1(false, x, y, xs) -> MIN(y, xs) The graph contains the following edges 3 >= 1, 4 >= 2 ---------------------------------------- (34) YES ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: MINSORT(cons(x, y)) -> MINSORT(del(min(x, y), cons(x, y))) The TRS R consists of the following rules: le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) eq(0, 0) -> true eq(0, s(y)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) if2(true, x, y, xs) -> xs if2(false, x, y, xs) -> cons(y, del(x, xs)) minsort(nil) -> nil minsort(cons(x, y)) -> cons(min(x, y), minsort(del(min(x, y), cons(x, y)))) min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) del(x, nil) -> nil del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) 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. ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: MINSORT(cons(x, y)) -> MINSORT(del(min(x, y), cons(x, y))) The TRS R consists of the following rules: min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 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 le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) minsort(nil) minsort(cons(x0, x1)) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) 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]. minsort(nil) minsort(cons(x0, x1)) ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: MINSORT(cons(x, y)) -> MINSORT(del(min(x, y), cons(x, y))) The TRS R consists of the following rules: min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 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 le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) Induction-Processor (SOUND) This DP could be deleted by the Induction-Processor: MINSORT(cons(x, y)) -> MINSORT(del(min(x, y), cons(x, y))) This order was computed: Polynomial interpretation [POLO]: POL(0) = 1 POL(MINSORT(x_1)) = x_1 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 POL(del(x_1, x_2)) = x_2 POL(eq(x_1, x_2)) = 1 + x_2 POL(false_renamed) = 1 POL(if1(x_1, x_2, x_3, x_4)) = 1 + x_2 + x_3 + x_4 POL(if2(x_1, x_2, x_3, x_4)) = 1 + x_3 + x_4 POL(le(x_1, x_2)) = 1 + x_1 + x_2 POL(min(x_1, x_2)) = 1 + x_1 + x_2 POL(nil) = 1 POL(s(x_1)) = 1 + x_1 POL(true_renamed) = 1 At least one of these decreasing rules is always used after the deleted DP: if2(true_renamed, x6, y5, xs'') -> xs'' The following formula is valid: x:sort[a0],y:sort[a33].del'(min(x, y), cons(x, y))=true The transformed set: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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, v25, v26, v27, v28, v29, v30, v31, v32, v33, x6, y5, xs'', x7, y6, y2, z', x8, x3, x', x'', y', z, y3, x4, x5, y4, y7, x9, x10, y8, x1, y'', x2, y1] 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> equal_sort[a0](v30, v32) and equal_sort[a33](v31, v33) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> true if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, cons(y2, z')) -> if2'(eq(x7, y2), x7, y2, z') if2'(false_renamed, x7, y6, nil) -> false del'(x8, nil) -> false equal_sort[a44](eq(x3, y2), true_renamed) -> true | del'(x3, cons(y2, z')) -> true equal_sort[a44](eq(x3, y2), true_renamed) -> false | del'(x3, cons(y2, z')) -> del'(x3, z') min(x', nil) -> x' equal_sort[a44](le(x'', y'), true_renamed) -> true | min(x'', cons(y', z)) -> min(x'', z) equal_sort[a44](le(x'', y'), true_renamed) -> false | min(x'', cons(y', z)) -> min(y', z) eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, cons(y2, z')) -> cons(y6, if2(eq(x7, y2), x7, y2, z')) if2(false_renamed, x7, y6, nil) -> cons(y6, nil) del(x8, nil) -> nil equal_sort[a44](eq(x3, y2), true_renamed) -> true | del(x3, cons(y2, z')) -> z' equal_sort[a44](eq(x3, y2), true_renamed) -> false | del(x3, cons(y2, z')) -> cons(y2, del(x3, z')) le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) if1(true_renamed, x1, y'', nil) -> x1 if1(true_renamed, x1, y'', cons(y', z)) -> if1(le(x1, y'), x1, y', z) if1(false_renamed, x2, y1, nil) -> y1 if1(false_renamed, x2, y1, cons(y', z)) -> if1(le(y1, y'), y1, y', z) using the following formula: x:sort[a0],y:sort[a33].del'(min(x, y), cons(x, y))=true could be successfully shown: (0) Formula (1) Conditional Evaluation [EQUIVALENT, 0 ms] (2) AND (3) Formula (4) Symbolic evaluation [EQUIVALENT, 0 ms] (5) YES (6) Formula (7) Hypothesis Lifting [EQUIVALENT, 0 ms] (8) Formula (9) Induction by algorithm [EQUIVALENT, 0 ms] (10) AND (11) Formula (12) Symbolic evaluation [EQUIVALENT, 0 ms] (13) Formula (14) Induction by data structure [EQUIVALENT, 0 ms] (15) AND (16) Formula (17) Symbolic evaluation [EQUIVALENT, 0 ms] (18) YES (19) Formula (20) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms] (21) YES (22) Formula (23) Conditional Evaluation [EQUIVALENT, 0 ms] (24) Formula (25) Conditional Evaluation [EQUIVALENT, 0 ms] (26) Formula (27) Conditional Evaluation [EQUIVALENT, 0 ms] (28) AND (29) Formula (30) Symbolic evaluation [EQUIVALENT, 0 ms] (31) YES (32) Formula (33) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms] (34) YES (35) Formula (36) Conditional Evaluation [EQUIVALENT, 0 ms] (37) Formula (38) Conditional Evaluation [EQUIVALENT, 0 ms] (39) Formula (40) Conditional Evaluation [EQUIVALENT, 0 ms] (41) AND (42) Formula (43) Symbolic evaluation [EQUIVALENT, 0 ms] (44) YES (45) Formula (46) Symbolic evaluation under hypothesis [EQUIVALENT, 0 ms] (47) YES ---------------------------------------- (0) Obligation: Formula: x:sort[a0],y:sort[a33].del'(min(x, y), cons(x, y))=true There are no hypotheses. ---------------------------------------- (1) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: true=true Hypotheses: x:sort[a0],y:sort[a33].equal_sort[a44](eq(min(x, y), x), true_renamed)=true Formula: x:sort[a0],y:sort[a33].del'(min(x, y), y)=true Hypotheses: x:sort[a0],y:sort[a33].equal_sort[a44](eq(min(x, y), x), true_renamed)=false ---------------------------------------- (2) Complex Obligation (AND) ---------------------------------------- (3) Obligation: Formula: true=true Hypotheses: x:sort[a0],y:sort[a33].equal_sort[a44](eq(min(x, y), x), true_renamed)=true ---------------------------------------- (4) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (5) YES ---------------------------------------- (6) Obligation: Formula: x:sort[a0],y:sort[a33].del'(min(x, y), y)=true Hypotheses: x:sort[a0],y:sort[a33].equal_sort[a44](eq(min(x, y), x), true_renamed)=false ---------------------------------------- (7) Hypothesis Lifting (EQUIVALENT) Formula could be generalised by hypothesis lifting to the following new obligation: Formula: x:sort[a0],y:sort[a33].(equal_sort[a44](eq(min(x, y), x), true_renamed)=false->del'(min(x, y), y)=true) There are no hypotheses. ---------------------------------------- (8) Obligation: Formula: x:sort[a0],y:sort[a33].(equal_sort[a44](eq(min(x, y), x), true_renamed)=false->del'(min(x, y), y)=true) There are no hypotheses. ---------------------------------------- (9) Induction by algorithm (EQUIVALENT) Induction by algorithm min(x, y) generates the following cases: 1. Base Case: Formula: x':sort[a0].(equal_sort[a44](eq(min(x', nil), x'), true_renamed)=false->del'(min(x', nil), nil)=true) There are no hypotheses. 1. Step Case: Formula: x'':sort[a0],y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', cons(y', z)), x''), true_renamed)=false->del'(min(x'', cons(y', z)), cons(y', z))=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true 2. Step Case: Formula: x'':sort[a0],y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', cons(y', z)), x''), true_renamed)=false->del'(min(x'', cons(y', z)), cons(y', z))=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false ---------------------------------------- (10) Complex Obligation (AND) ---------------------------------------- (11) Obligation: Formula: x':sort[a0].(equal_sort[a44](eq(min(x', nil), x'), true_renamed)=false->del'(min(x', nil), nil)=true) There are no hypotheses. ---------------------------------------- (12) Symbolic evaluation (EQUIVALENT) Could be shown by simple symbolic evaluation. ---------------------------------------- (13) Obligation: Formula: x':sort[a0].~(equal_sort[a44](eq(x', x'), true_renamed)=false) There are no hypotheses. ---------------------------------------- (14) Induction by data structure (EQUIVALENT) Induction by data structure sort[a0] generates the following cases: 1. Base Case: Formula: ~(equal_sort[a44](eq(0, 0), true_renamed)=false) There are no hypotheses. 1. Step Case: Formula: n:sort[a0].~(equal_sort[a44](eq(s(n), s(n)), true_renamed)=false) Hypotheses: n:sort[a0].~(equal_sort[a44](eq(n, n), true_renamed)=false) ---------------------------------------- (15) Complex Obligation (AND) ---------------------------------------- (16) Obligation: Formula: ~(equal_sort[a44](eq(0, 0), true_renamed)=false) There are no hypotheses. ---------------------------------------- (17) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (18) YES ---------------------------------------- (19) Obligation: Formula: n:sort[a0].~(equal_sort[a44](eq(s(n), s(n)), true_renamed)=false) Hypotheses: n:sort[a0].~(equal_sort[a44](eq(n, n), true_renamed)=false) ---------------------------------------- (20) Symbolic evaluation under hypothesis (EQUIVALENT) Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses: n:sort[a0].~(equal_sort[a44](eq(n, n), true_renamed)=false) ---------------------------------------- (21) YES ---------------------------------------- (22) Obligation: Formula: x'':sort[a0],y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', cons(y', z)), x''), true_renamed)=false->del'(min(x'', cons(y', z)), cons(y', z))=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true ---------------------------------------- (23) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: x'':sort[a0],z:sort[a33],y':sort[a0].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', cons(y', z)), cons(y', z))=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true ---------------------------------------- (24) Obligation: Formula: x'':sort[a0],z:sort[a33],y':sort[a0].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', cons(y', z)), cons(y', z))=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true ---------------------------------------- (25) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: x'':sort[a0],z:sort[a33],y':sort[a0].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), cons(y', z))=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true ---------------------------------------- (26) Obligation: Formula: x'':sort[a0],z:sort[a33],y':sort[a0].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), cons(y', z))=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true ---------------------------------------- (27) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->true=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true x'':sort[a0],z:sort[a33],y':sort[a0].equal_sort[a44](eq(min(x'', z), y'), true_renamed)=true Formula: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true x'':sort[a0],z:sort[a33],y':sort[a0].equal_sort[a44](eq(min(x'', z), y'), true_renamed)=false ---------------------------------------- (28) Complex Obligation (AND) ---------------------------------------- (29) Obligation: Formula: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->true=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true x'':sort[a0],z:sort[a33],y':sort[a0].equal_sort[a44](eq(min(x'', z), y'), true_renamed)=true ---------------------------------------- (30) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (31) YES ---------------------------------------- (32) Obligation: Formula: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) Hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=true x'':sort[a0],z:sort[a33],y':sort[a0].equal_sort[a44](eq(min(x'', z), y'), true_renamed)=false ---------------------------------------- (33) Symbolic evaluation under hypothesis (EQUIVALENT) Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses: x'':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', z), x''), true_renamed)=false->del'(min(x'', z), z)=true) ---------------------------------------- (34) YES ---------------------------------------- (35) Obligation: Formula: x'':sort[a0],y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(x'', cons(y', z)), x''), true_renamed)=false->del'(min(x'', cons(y', z)), cons(y', z))=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false ---------------------------------------- (36) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: y':sort[a0],z:sort[a33],x'':sort[a0].(equal_sort[a44](eq(min(y', z), x''), true_renamed)=false->del'(min(x'', cons(y', z)), cons(y', z))=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false ---------------------------------------- (37) Obligation: Formula: y':sort[a0],z:sort[a33],x'':sort[a0].(equal_sort[a44](eq(min(y', z), x''), true_renamed)=false->del'(min(x'', cons(y', z)), cons(y', z))=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false ---------------------------------------- (38) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: y':sort[a0],z:sort[a33],x'':sort[a0].(equal_sort[a44](eq(min(y', z), x''), true_renamed)=false->del'(min(y', z), cons(y', z))=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false ---------------------------------------- (39) Obligation: Formula: y':sort[a0],z:sort[a33],x'':sort[a0].(equal_sort[a44](eq(min(y', z), x''), true_renamed)=false->del'(min(y', z), cons(y', z))=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false ---------------------------------------- (40) Conditional Evaluation (EQUIVALENT) The formula could be reduced to the following new obligations by conditional evaluation: Formula: y':sort[a0],z:sort[a33],x'':sort[a0].(equal_sort[a44](eq(min(y', z), x''), true_renamed)=false->true=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false y':sort[a0],z:sort[a33].equal_sort[a44](eq(min(y', z), y'), true_renamed)=true Formula: y':sort[a0],z:sort[a33],x'':sort[a0].(equal_sort[a44](eq(min(y', z), x''), true_renamed)=false->del'(min(y', z), z)=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false y':sort[a0],z:sort[a33].equal_sort[a44](eq(min(y', z), y'), true_renamed)=false ---------------------------------------- (41) Complex Obligation (AND) ---------------------------------------- (42) Obligation: Formula: y':sort[a0],z:sort[a33],x'':sort[a0].(equal_sort[a44](eq(min(y', z), x''), true_renamed)=false->true=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false y':sort[a0],z:sort[a33].equal_sort[a44](eq(min(y', z), y'), true_renamed)=true ---------------------------------------- (43) Symbolic evaluation (EQUIVALENT) Could be reduced to the following new obligation by simple symbolic evaluation: True ---------------------------------------- (44) YES ---------------------------------------- (45) Obligation: Formula: y':sort[a0],z:sort[a33],x'':sort[a0].(equal_sort[a44](eq(min(y', z), x''), true_renamed)=false->del'(min(y', z), z)=true) Hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) x'':sort[a0],y':sort[a0].equal_sort[a44](le(x'', y'), true_renamed)=false y':sort[a0],z:sort[a33].equal_sort[a44](eq(min(y', z), y'), true_renamed)=false ---------------------------------------- (46) Symbolic evaluation under hypothesis (EQUIVALENT) Could be shown using symbolic evaluation under hypothesis, by using the following hypotheses: y':sort[a0],z:sort[a33].(equal_sort[a44](eq(min(y', z), y'), true_renamed)=false->del'(min(y', z), z)=true) y':sort[a0],z:sort[a33].equal_sort[a44](eq(min(y', z), y'), true_renamed)=false ---------------------------------------- (47) YES ---------------------------------------- (41) Complex Obligation (AND) ---------------------------------------- (42) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: min(x, nil) -> x min(x, cons(y, z)) -> if1(le(x, y), x, y, z) if1(true, x, y, xs) -> min(x, xs) if1(false, x, y, xs) -> min(y, xs) del(x, cons(y, z)) -> if2(eq(x, y), x, y, z) 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 le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) if1(true, x0, x1, x2) if1(false, x0, x1, x2) if2(true, x0, x1, x2) if2(false, x0, x1, x2) min(x0, nil) min(x0, cons(x1, x2)) del(x0, nil) del(x0, cons(x1, x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (44) YES ---------------------------------------- (45) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> true Q is empty. ---------------------------------------- (46) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (47) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) ---------------------------------------- (48) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: DEL'(x3, cons(y2, z')) -> IF2'(eq(x3, y2), x3, y2, z') DEL'(x3, cons(y2, z')) -> EQ(x3, y2) IF2'(false_renamed, x7, y6, xs1) -> DEL'(x7, xs1) MIN(x'', cons(y', z)) -> IF1(le(x'', y'), x'', y', z) MIN(x'', cons(y', z)) -> LE(x'', y') IF1(true_renamed, x1, y'', xs) -> MIN(x1, xs) IF1(false_renamed, x2, y1, xs') -> MIN(y1, xs') DEL(x3, cons(y2, z')) -> IF2(eq(x3, y2), x3, y2, z') DEL(x3, cons(y2, z')) -> EQ(x3, y2) EQ(s(x5), s(y4)) -> EQ(x5, y4) IF2(false_renamed, x7, y6, xs1) -> DEL(x7, xs1) LE(s(x10), s(y8)) -> LE(x10, y8) EQUAL_SORT[A0](s(v26), s(v27)) -> EQUAL_SORT[A0](v26, v27) EQUAL_SORT[A33](cons(v30, v31), cons(v32, v33)) -> AND(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) EQUAL_SORT[A33](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A0](v30, v32) EQUAL_SORT[A33](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A33](v31, v33) The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 7 SCCs with 5 less nodes. ---------------------------------------- (51) Complex Obligation (AND) ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A0](s(v26), s(v27)) -> EQUAL_SORT[A0](v26, v27) The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) 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. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A0](s(v26), s(v27)) -> EQUAL_SORT[A0](v26, v27) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A0](s(v26), s(v27)) -> EQUAL_SORT[A0](v26, v27) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) 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(v26), s(v27)) -> EQUAL_SORT[A0](v26, v27) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (58) YES ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A33](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A33](v31, v33) The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (60) 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. ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A33](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A33](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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: EQUAL_SORT[A33](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A33](v31, v33) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) 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[A33](cons(v30, v31), cons(v32, v33)) -> EQUAL_SORT[A33](v31, v33) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (65) YES ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(x10), s(y8)) -> LE(x10, y8) The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) 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. ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(x10), s(y8)) -> LE(x10, y8) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(x10), s(y8)) -> LE(x10, y8) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (71) 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: *LE(s(x10), s(y8)) -> LE(x10, y8) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (72) YES ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(x5), s(y4)) -> EQ(x5, y4) The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (74) 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. ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(x5), s(y4)) -> EQ(x5, y4) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (76) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(x5), s(y4)) -> EQ(x5, y4) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (78) 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(y4)) -> EQ(x5, y4) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (79) YES ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(false_renamed, x7, y6, xs1) -> DEL(x7, xs1) DEL(x3, cons(y2, z')) -> IF2(eq(x3, y2), x3, y2, z') The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (81) 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. ---------------------------------------- (82) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(false_renamed, x7, y6, xs1) -> DEL(x7, xs1) DEL(x3, cons(y2, z')) -> IF2(eq(x3, y2), x3, y2, z') The TRS R consists of the following rules: eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (83) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: IF2(false_renamed, x7, y6, xs1) -> DEL(x7, xs1) DEL(x3, cons(y2, z')) -> IF2(eq(x3, y2), x3, y2, z') The TRS R consists of the following rules: eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) 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. ---------------------------------------- (85) 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(y2, z')) -> IF2(eq(x3, y2), x3, y2, z') The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4 *IF2(false_renamed, x7, y6, xs1) -> DEL(x7, xs1) The graph contains the following edges 2 >= 1, 4 >= 2 ---------------------------------------- (86) YES ---------------------------------------- (87) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(true_renamed, x1, y'', xs) -> MIN(x1, xs) MIN(x'', cons(y', z)) -> IF1(le(x'', y'), x'', y', z) IF1(false_renamed, x2, y1, xs') -> MIN(y1, xs') The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (88) 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. ---------------------------------------- (89) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(true_renamed, x1, y'', xs) -> MIN(x1, xs) MIN(x'', cons(y', z)) -> IF1(le(x'', y'), x'', y', z) IF1(false_renamed, x2, y1, xs') -> MIN(y1, xs') The TRS R consists of the following rules: le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (90) 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) min(x0, nil) min(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) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) ---------------------------------------- (91) Obligation: Q DP problem: The TRS P consists of the following rules: IF1(true_renamed, x1, y'', xs) -> MIN(x1, xs) MIN(x'', cons(y', z)) -> IF1(le(x'', y'), x'', y', z) IF1(false_renamed, x2, y1, xs') -> MIN(y1, xs') The TRS R consists of the following rules: le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (92) 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: *MIN(x'', cons(y', z)) -> IF1(le(x'', y'), x'', y', z) The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4 *IF1(true_renamed, x1, y'', xs) -> MIN(x1, xs) The graph contains the following edges 2 >= 1, 4 >= 2 *IF1(false_renamed, x2, y1, xs') -> MIN(y1, xs') The graph contains the following edges 3 >= 1, 4 >= 2 ---------------------------------------- (93) YES ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: IF2'(false_renamed, x7, y6, xs1) -> DEL'(x7, xs1) DEL'(x3, cons(y2, z')) -> IF2'(eq(x3, y2), x3, y2, z') The TRS R consists of the following rules: del'(x3, cons(y2, z')) -> if2'(eq(x3, y2), x3, y2, z') if2'(true_renamed, x6, y5, xs'') -> true if2'(false_renamed, x7, y6, xs1) -> del'(x7, xs1) del'(x8, nil) -> false min(x', nil) -> x' min(x'', cons(y', z)) -> if1(le(x'', y'), x'', y', z) if1(true_renamed, x1, y'', xs) -> min(x1, xs) if1(false_renamed, x2, y1, xs') -> min(y1, xs') del(x3, cons(y2, z')) -> if2(eq(x3, y2), x3, y2, z') eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) if2(true_renamed, x6, y5, xs'') -> xs'' if2(false_renamed, x7, y6, xs1) -> cons(y6, del(x7, xs1)) del(x8, nil) -> nil le(0, y7) -> true_renamed le(s(x9), 0) -> false_renamed le(s(x10), s(y8)) -> le(x10, y8) 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(v25)) -> false equal_sort[a0](s(v26), 0) -> false equal_sort[a0](s(v26), s(v27)) -> equal_sort[a0](v26, v27) equal_sort[a33](nil, nil) -> true equal_sort[a33](nil, cons(v28, v29)) -> false equal_sort[a33](cons(v30, v31), nil) -> false equal_sort[a33](cons(v30, v31), cons(v32, v33)) -> and(equal_sort[a0](v30, v32), equal_sort[a33](v31, v33)) equal_sort[a44](true_renamed, true_renamed) -> true equal_sort[a44](true_renamed, false_renamed) -> false equal_sort[a44](false_renamed, true_renamed) -> false equal_sort[a44](false_renamed, false_renamed) -> true equal_sort[a62](witness_sort[a62], witness_sort[a62]) -> 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) 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. ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: IF2'(false_renamed, x7, y6, xs1) -> DEL'(x7, xs1) DEL'(x3, cons(y2, z')) -> IF2'(eq(x3, y2), x3, y2, z') The TRS R consists of the following rules: eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (97) 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) min(x0, nil) min(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) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) 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[a33](nil, nil) equal_sort[a33](nil, cons(x0, x1)) equal_sort[a33](cons(x0, x1), nil) equal_sort[a33](cons(x0, x1), cons(x2, x3)) equal_sort[a44](true_renamed, true_renamed) equal_sort[a44](true_renamed, false_renamed) equal_sort[a44](false_renamed, true_renamed) equal_sort[a44](false_renamed, false_renamed) equal_sort[a62](witness_sort[a62], witness_sort[a62]) ---------------------------------------- (98) Obligation: Q DP problem: The TRS P consists of the following rules: IF2'(false_renamed, x7, y6, xs1) -> DEL'(x7, xs1) DEL'(x3, cons(y2, z')) -> IF2'(eq(x3, y2), x3, y2, z') The TRS R consists of the following rules: eq(0, 0) -> true_renamed eq(0, s(y3)) -> false_renamed eq(s(x4), 0) -> false_renamed eq(s(x5), s(y4)) -> eq(x5, y4) 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. ---------------------------------------- (99) 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(y2, z')) -> IF2'(eq(x3, y2), x3, y2, z') The graph contains the following edges 1 >= 2, 2 > 3, 2 > 4 *IF2'(false_renamed, x7, y6, xs1) -> DEL'(x7, xs1) The graph contains the following edges 2 >= 1, 4 >= 2 ---------------------------------------- (100) YES