/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) Overlay + Local Confluence [EQUIVALENT, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 24 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) QDPOrderProof [EQUIVALENT, 24 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) TRUE (23) QDP (24) UsableRulesProof [EQUIVALENT, 0 ms] (25) QDP (26) QReductionProof [EQUIVALENT, 0 ms] (27) QDP (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] (29) YES (30) QDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) QDP (33) QReductionProof [EQUIVALENT, 0 ms] (34) QDP (35) QDPSizeChangeProof [EQUIVALENT, 0 ms] (36) YES (37) QDP (38) UsableRulesProof [EQUIVALENT, 0 ms] (39) QDP (40) QReductionProof [EQUIVALENT, 0 ms] (41) QDP (42) QDPOrderProof [EQUIVALENT, 161 ms] (43) QDP (44) PisEmptyProof [EQUIVALENT, 0 ms] (45) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) sort(nil) -> nil sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) 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: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) sort(nil) -> nil sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(n), s(m)) -> EQ(n, m) LE(s(n), s(m)) -> LE(n, m) MIN(cons(n, cons(m, x))) -> IF_MIN(le(n, m), cons(n, cons(m, x))) MIN(cons(n, cons(m, x))) -> LE(n, m) IF_MIN(true, cons(n, cons(m, x))) -> MIN(cons(n, x)) IF_MIN(false, cons(n, cons(m, x))) -> MIN(cons(m, x)) REPLACE(n, m, cons(k, x)) -> IF_REPLACE(eq(n, k), n, m, cons(k, x)) REPLACE(n, m, cons(k, x)) -> EQ(n, k) IF_REPLACE(false, n, m, cons(k, x)) -> REPLACE(n, m, x) SORT(cons(n, x)) -> MIN(cons(n, x)) SORT(cons(n, x)) -> SORT(replace(min(cons(n, x)), n, x)) SORT(cons(n, x)) -> REPLACE(min(cons(n, x)), n, x) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) sort(nil) -> nil sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 4 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(n), s(m)) -> LE(n, m) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) sort(nil) -> nil sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(n), s(m)) -> LE(n, m) R is empty. The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(n), s(m)) -> LE(n, m) 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: *LE(s(n), s(m)) -> LE(n, m) 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: MIN(cons(n, cons(m, x))) -> IF_MIN(le(n, m), cons(n, cons(m, x))) IF_MIN(true, cons(n, cons(m, x))) -> MIN(cons(n, x)) IF_MIN(false, cons(n, cons(m, x))) -> MIN(cons(m, x)) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) sort(nil) -> nil sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: MIN(cons(n, cons(m, x))) -> IF_MIN(le(n, m), cons(n, cons(m, x))) IF_MIN(true, cons(n, cons(m, x))) -> MIN(cons(n, x)) IF_MIN(false, cons(n, cons(m, x))) -> MIN(cons(m, x)) The TRS R consists of the following rules: le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MIN(cons(n, cons(m, x))) -> IF_MIN(le(n, m), cons(n, cons(m, x))) IF_MIN(true, cons(n, cons(m, x))) -> MIN(cons(n, x)) IF_MIN(false, cons(n, cons(m, x))) -> MIN(cons(m, x)) The TRS R consists of the following rules: le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) 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. ---------------------------------------- (19) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MIN(cons(n, cons(m, x))) -> IF_MIN(le(n, m), cons(n, cons(m, x))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MIN(x1) = MIN(x1) cons(x1, x2) = cons(x2) IF_MIN(x1, x2) = x2 le(x1, x2) = le(x1, x2) true = true false = false 0 = 0 s(x1) = s Recursive path order with status [RPO]. Quasi-Precedence: [MIN_1, cons_1, true, false, 0, s] > le_2 Status: MIN_1: multiset status cons_1: multiset status le_2: multiset status true: multiset status false: multiset status 0: multiset status s: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: IF_MIN(true, cons(n, cons(m, x))) -> MIN(cons(n, x)) IF_MIN(false, cons(n, cons(m, x))) -> MIN(cons(m, x)) The TRS R consists of the following rules: le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) 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. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (22) TRUE ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(n), s(m)) -> EQ(n, m) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) sort(nil) -> nil sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) 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. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(n), s(m)) -> EQ(n, m) R is empty. The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) 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)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(n), s(m)) -> EQ(n, m) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) 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(n), s(m)) -> EQ(n, m) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (29) YES ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: REPLACE(n, m, cons(k, x)) -> IF_REPLACE(eq(n, k), n, m, cons(k, x)) IF_REPLACE(false, n, m, cons(k, x)) -> REPLACE(n, m, x) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) sort(nil) -> nil sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: REPLACE(n, m, cons(k, x)) -> IF_REPLACE(eq(n, k), n, m, cons(k, x)) IF_REPLACE(false, n, m, cons(k, x)) -> REPLACE(n, m, x) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) 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)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: REPLACE(n, m, cons(k, x)) -> IF_REPLACE(eq(n, k), n, m, cons(k, x)) IF_REPLACE(false, n, m, cons(k, x)) -> REPLACE(n, m, x) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) 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. ---------------------------------------- (35) 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: *IF_REPLACE(false, n, m, cons(k, x)) -> REPLACE(n, m, x) The graph contains the following edges 2 >= 1, 3 >= 2, 4 > 3 *REPLACE(n, m, cons(k, x)) -> IF_REPLACE(eq(n, k), n, m, cons(k, x)) The graph contains the following edges 1 >= 2, 2 >= 3, 3 >= 4 ---------------------------------------- (36) YES ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: SORT(cons(n, x)) -> SORT(replace(min(cons(n, x)), n, x)) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) sort(nil) -> nil sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: SORT(cons(n, x)) -> SORT(replace(min(cons(n, x)), n, x)) The TRS R consists of the following rules: min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) sort(nil) sort(cons(x0, x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. sort(nil) sort(cons(x0, x1)) ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: SORT(cons(n, x)) -> SORT(replace(min(cons(n, x)), n, x)) The TRS R consists of the following rules: min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. SORT(cons(n, x)) -> SORT(replace(min(cons(n, x)), n, x)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. SORT(x1) = SORT(x1) cons(x1, x2) = cons(x2) replace(x1, x2, x3) = x3 min(x1) = min 0 = 0 nil = nil s(x1) = s if_min(x1, x2) = if_min(x1, x2) le(x1, x2) = x1 true = true false = false if_replace(x1, x2, x3, x4) = x4 eq(x1, x2) = eq(x1, x2) Recursive path order with status [RPO]. Quasi-Precedence: if_min_2 > [SORT_1, cons_1, min] [false, eq_2] > [0, true] > [SORT_1, cons_1, min] Status: SORT_1: multiset status cons_1: [1] min: multiset status 0: multiset status nil: multiset status s: [] if_min_2: multiset status true: multiset status false: multiset status eq_2: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) ---------------------------------------- (43) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: min(cons(0, nil)) -> 0 min(cons(s(n), nil)) -> s(n) min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) replace(n, m, nil) -> nil replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) eq(0, 0) -> true eq(0, s(m)) -> false eq(s(n), 0) -> false eq(s(n), s(m)) -> eq(n, m) if_replace(true, n, m, cons(k, x)) -> cons(m, x) if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) le(0, m) -> true le(s(n), 0) -> false le(s(n), s(m)) -> le(n, m) The set Q consists of the following terms: eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) min(cons(0, nil)) min(cons(s(x0), nil)) min(cons(x0, cons(x1, x2))) if_min(true, cons(x0, cons(x1, x2))) if_min(false, cons(x0, cons(x1, x2))) replace(x0, x1, nil) replace(x0, x1, cons(x2, x3)) if_replace(true, x0, x1, cons(x2, x3)) if_replace(false, x0, x1, cons(x2, x3)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (45) YES