YES Time: 0.023140 TRS: { qsort nil() -> nil(), qsort .(x, y) -> ++(qsort lowers(x, y), .(x, qsort greaters(x, y))), lowers(x, nil()) -> nil(), lowers(x, .(y, z)) -> if(<=(y, x), .(y, lowers(x, z)), lowers(x, z)), greaters(x, nil()) -> nil(), greaters(x, .(y, z)) -> if(<=(y, x), greaters(x, z), .(y, greaters(x, z)))} DP: DP: { qsort# .(x, y) -> qsort# lowers(x, y), qsort# .(x, y) -> qsort# greaters(x, y), qsort# .(x, y) -> lowers#(x, y), qsort# .(x, y) -> greaters#(x, y), lowers#(x, .(y, z)) -> lowers#(x, z), greaters#(x, .(y, z)) -> greaters#(x, z)} TRS: { qsort nil() -> nil(), qsort .(x, y) -> ++(qsort lowers(x, y), .(x, qsort greaters(x, y))), lowers(x, nil()) -> nil(), lowers(x, .(y, z)) -> if(<=(y, x), .(y, lowers(x, z)), lowers(x, z)), greaters(x, nil()) -> nil(), greaters(x, .(y, z)) -> if(<=(y, x), greaters(x, z), .(y, greaters(x, z)))} EDG: {(greaters#(x, .(y, z)) -> greaters#(x, z), greaters#(x, .(y, z)) -> greaters#(x, z)) (qsort# .(x, y) -> greaters#(x, y), greaters#(x, .(y, z)) -> greaters#(x, z)) (qsort# .(x, y) -> qsort# greaters(x, y), qsort# .(x, y) -> greaters#(x, y)) (qsort# .(x, y) -> qsort# greaters(x, y), qsort# .(x, y) -> lowers#(x, y)) (qsort# .(x, y) -> qsort# greaters(x, y), qsort# .(x, y) -> qsort# greaters(x, y)) (qsort# .(x, y) -> qsort# greaters(x, y), qsort# .(x, y) -> qsort# lowers(x, y)) (qsort# .(x, y) -> qsort# lowers(x, y), qsort# .(x, y) -> qsort# lowers(x, y)) (qsort# .(x, y) -> qsort# lowers(x, y), qsort# .(x, y) -> qsort# greaters(x, y)) (qsort# .(x, y) -> qsort# lowers(x, y), qsort# .(x, y) -> lowers#(x, y)) (qsort# .(x, y) -> qsort# lowers(x, y), qsort# .(x, y) -> greaters#(x, y)) (qsort# .(x, y) -> lowers#(x, y), lowers#(x, .(y, z)) -> lowers#(x, z)) (lowers#(x, .(y, z)) -> lowers#(x, z), lowers#(x, .(y, z)) -> lowers#(x, z))} EDG: {(greaters#(x, .(y, z)) -> greaters#(x, z), greaters#(x, .(y, z)) -> greaters#(x, z)) (qsort# .(x, y) -> greaters#(x, y), greaters#(x, .(y, z)) -> greaters#(x, z)) (qsort# .(x, y) -> lowers#(x, y), lowers#(x, .(y, z)) -> lowers#(x, z)) (lowers#(x, .(y, z)) -> lowers#(x, z), lowers#(x, .(y, z)) -> lowers#(x, z))} EDG: {(greaters#(x, .(y, z)) -> greaters#(x, z), greaters#(x, .(y, z)) -> greaters#(x, z)) (qsort# .(x, y) -> greaters#(x, y), greaters#(x, .(y, z)) -> greaters#(x, z)) (qsort# .(x, y) -> lowers#(x, y), lowers#(x, .(y, z)) -> lowers#(x, z)) (lowers#(x, .(y, z)) -> lowers#(x, z), lowers#(x, .(y, z)) -> lowers#(x, z))} EDG: {(greaters#(x, .(y, z)) -> greaters#(x, z), greaters#(x, .(y, z)) -> greaters#(x, z)) (qsort# .(x, y) -> greaters#(x, y), greaters#(x, .(y, z)) -> greaters#(x, z)) (qsort# .(x, y) -> lowers#(x, y), lowers#(x, .(y, z)) -> lowers#(x, z)) (lowers#(x, .(y, z)) -> lowers#(x, z), lowers#(x, .(y, z)) -> lowers#(x, z))} STATUS: arrows: 0.888889 SCCS (2): Scc: {greaters#(x, .(y, z)) -> greaters#(x, z)} Scc: {lowers#(x, .(y, z)) -> lowers#(x, z)} SCC (1): Strict: {greaters#(x, .(y, z)) -> greaters#(x, z)} Weak: { qsort nil() -> nil(), qsort .(x, y) -> ++(qsort lowers(x, y), .(x, qsort greaters(x, y))), lowers(x, nil()) -> nil(), lowers(x, .(y, z)) -> if(<=(y, x), .(y, lowers(x, z)), lowers(x, z)), greaters(x, nil()) -> nil(), greaters(x, .(y, z)) -> if(<=(y, x), greaters(x, z), .(y, greaters(x, z)))} POLY: Mode: weak, max_in=1, output_bits=-1, dnum=1, ur=true Interpretation: [if](x0, x1, x2) = x0 + x1 + x2, [++](x0, x1) = x0 + 1, [lowers](x0, x1) = 1, [.](x0, x1) = x0 + x1 + 1, [greaters](x0, x1) = 1, [<=](x0, x1) = x0, [qsort](x0) = x0 + 1, [nil] = 1, [greaters#](x0, x1) = x0 Strict: greaters#(x, .(y, z)) -> greaters#(x, z) 1 + 0x + 1y + 1z >= 0 + 0x + 1z Weak: greaters(x, .(y, z)) -> if(<=(y, x), greaters(x, z), .(y, greaters(x, z))) 1 + 0x + 0y + 0z >= 3 + 0x + 2y + 0z greaters(x, nil()) -> nil() 1 + 0x >= 1 lowers(x, .(y, z)) -> if(<=(y, x), .(y, lowers(x, z)), lowers(x, z)) 1 + 0x + 0y + 0z >= 3 + 0x + 2y + 0z lowers(x, nil()) -> nil() 1 + 0x >= 1 qsort .(x, y) -> ++(qsort lowers(x, y), .(x, qsort greaters(x, y))) 2 + 1x + 1y >= 4 + 1x + 0y qsort nil() -> nil() 2 >= 1 Qed SCC (1): Strict: {lowers#(x, .(y, z)) -> lowers#(x, z)} Weak: { qsort nil() -> nil(), qsort .(x, y) -> ++(qsort lowers(x, y), .(x, qsort greaters(x, y))), lowers(x, nil()) -> nil(), lowers(x, .(y, z)) -> if(<=(y, x), .(y, lowers(x, z)), lowers(x, z)), greaters(x, nil()) -> nil(), greaters(x, .(y, z)) -> if(<=(y, x), greaters(x, z), .(y, greaters(x, z)))} POLY: Mode: weak, max_in=1, output_bits=-1, dnum=1, ur=true Interpretation: [if](x0, x1, x2) = x0 + x1 + x2, [++](x0, x1) = x0 + 1, [lowers](x0, x1) = 1, [.](x0, x1) = x0 + x1 + 1, [greaters](x0, x1) = 1, [<=](x0, x1) = x0, [qsort](x0) = x0 + 1, [nil] = 1, [lowers#](x0, x1) = x0 Strict: lowers#(x, .(y, z)) -> lowers#(x, z) 1 + 0x + 1y + 1z >= 0 + 0x + 1z Weak: greaters(x, .(y, z)) -> if(<=(y, x), greaters(x, z), .(y, greaters(x, z))) 1 + 0x + 0y + 0z >= 3 + 0x + 2y + 0z greaters(x, nil()) -> nil() 1 + 0x >= 1 lowers(x, .(y, z)) -> if(<=(y, x), .(y, lowers(x, z)), lowers(x, z)) 1 + 0x + 0y + 0z >= 3 + 0x + 2y + 0z lowers(x, nil()) -> nil() 1 + 0x >= 1 qsort .(x, y) -> ++(qsort lowers(x, y), .(x, qsort greaters(x, y))) 2 + 1x + 1y >= 4 + 1x + 0y qsort nil() -> nil() 2 >= 1 Qed