MAYBE We are left with following problem, upon which TcT provides the certificate MAYBE. Strict Trs: { average(x, y) -> if(ge(x, y), x, y) , if(true(), x, y) -> averIter(y, x, y) , if(false(), x, y) -> averIter(x, y, x) , ge(x, 0()) -> true() , ge(s(x), s(y)) -> ge(x, y) , ge(0(), s(y)) -> false() , averIter(x, y, z) -> ifIter(ge(x, y), x, y, z) , ifIter(true(), x, y, z) -> z , ifIter(false(), x, y, z) -> averIter(plus(x, s(s(s(0())))), plus(y, s(0())), plus(z, s(0()))) , plus(s(x), y) -> s(plus(x, y)) , plus(0(), y) -> y , append(nil(), y) -> y , append(cons(n, x), y) -> cons(n, app(x, y)) , low(n, nil()) -> nil() , low(n, cons(m, x)) -> if_low(ge(m, n), n, cons(m, x)) , if_low(true(), n, cons(m, x)) -> low(n, x) , if_low(false(), n, cons(m, x)) -> cons(m, low(n, x)) , high(n, nil()) -> nil() , high(n, cons(m, x)) -> if_high(ge(m, n), n, cons(m, x)) , if_high(true(), n, cons(m, x)) -> cons(average(m, m), high(n, x)) , if_high(false(), n, cons(m, x)) -> high(n, x) , quicksort(x) -> ifquick(isempty(x), x) , ifquick(true(), x) -> nil() , ifquick(false(), x) -> append(quicksort(low(head(x), tail(x))), cons(tail(x), quicksort(high(head(x), tail(x))))) , isempty(nil()) -> true() , isempty(cons(n, x)) -> false() , head(nil()) -> error() , head(cons(n, x)) -> n , tail(nil()) -> nil() , tail(cons(n, x)) -> x , a() -> b() , a() -> c() } Obligation: runtime complexity Answer: MAYBE None of the processors succeeded. Details of failed attempt(s): ----------------------------- 1) 'WithProblem (timeout of 60 seconds)' failed due to the following reason: Computation stopped due to timeout after 60.0 seconds. 2) 'Best' failed due to the following reason: None of the processors succeeded. Details of failed attempt(s): ----------------------------- 1) 'WithProblem (timeout of 30 seconds) (timeout of 60 seconds)' failed due to the following reason: Computation stopped due to timeout after 30.0 seconds. 2) 'Best' failed due to the following reason: None of the processors succeeded. Details of failed attempt(s): ----------------------------- 1) 'bsearch-popstar (timeout of 60 seconds)' failed due to the following reason: The processor is inapplicable, reason: Processor only applicable for innermost runtime complexity analysis 2) 'Polynomial Path Order (PS) (timeout of 60 seconds)' failed due to the following reason: The processor is inapplicable, reason: Processor only applicable for innermost runtime complexity analysis 3) 'Fastest (timeout of 5 seconds) (timeout of 60 seconds)' failed due to the following reason: None of the processors succeeded. Details of failed attempt(s): ----------------------------- 1) 'Bounds with perSymbol-enrichment and initial automaton 'match'' failed due to the following reason: match-boundness of the problem could not be verified. 2) 'Bounds with minimal-enrichment and initial automaton 'match'' failed due to the following reason: match-boundness of the problem could not be verified. 3) 'Innermost Weak Dependency Pairs (timeout of 60 seconds)' failed due to the following reason: We add the following weak dependency pairs: Strict DPs: { average^#(x, y) -> c_1(if^#(ge(x, y), x, y)) , if^#(true(), x, y) -> c_2(averIter^#(y, x, y)) , if^#(false(), x, y) -> c_3(averIter^#(x, y, x)) , averIter^#(x, y, z) -> c_7(ifIter^#(ge(x, y), x, y, z)) , ge^#(x, 0()) -> c_4() , ge^#(s(x), s(y)) -> c_5(ge^#(x, y)) , ge^#(0(), s(y)) -> c_6() , ifIter^#(true(), x, y, z) -> c_8(z) , ifIter^#(false(), x, y, z) -> c_9(averIter^#(plus(x, s(s(s(0())))), plus(y, s(0())), plus(z, s(0())))) , plus^#(s(x), y) -> c_10(plus^#(x, y)) , plus^#(0(), y) -> c_11(y) , append^#(nil(), y) -> c_12(y) , append^#(cons(n, x), y) -> c_13(n, x, y) , low^#(n, nil()) -> c_14() , low^#(n, cons(m, x)) -> c_15(if_low^#(ge(m, n), n, cons(m, x))) , if_low^#(true(), n, cons(m, x)) -> c_16(low^#(n, x)) , if_low^#(false(), n, cons(m, x)) -> c_17(m, low^#(n, x)) , high^#(n, nil()) -> c_18() , high^#(n, cons(m, x)) -> c_19(if_high^#(ge(m, n), n, cons(m, x))) , if_high^#(true(), n, cons(m, x)) -> c_20(average^#(m, m), high^#(n, x)) , if_high^#(false(), n, cons(m, x)) -> c_21(high^#(n, x)) , quicksort^#(x) -> c_22(ifquick^#(isempty(x), x)) , ifquick^#(true(), x) -> c_23() , ifquick^#(false(), x) -> c_24(append^#(quicksort(low(head(x), tail(x))), cons(tail(x), quicksort(high(head(x), tail(x)))))) , isempty^#(nil()) -> c_25() , isempty^#(cons(n, x)) -> c_26() , head^#(nil()) -> c_27() , head^#(cons(n, x)) -> c_28(n) , tail^#(nil()) -> c_29() , tail^#(cons(n, x)) -> c_30(x) , a^#() -> c_31() , a^#() -> c_32() } and mark the set of starting terms. We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { average^#(x, y) -> c_1(if^#(ge(x, y), x, y)) , if^#(true(), x, y) -> c_2(averIter^#(y, x, y)) , if^#(false(), x, y) -> c_3(averIter^#(x, y, x)) , averIter^#(x, y, z) -> c_7(ifIter^#(ge(x, y), x, y, z)) , ge^#(x, 0()) -> c_4() , ge^#(s(x), s(y)) -> c_5(ge^#(x, y)) , ge^#(0(), s(y)) -> c_6() , ifIter^#(true(), x, y, z) -> c_8(z) , ifIter^#(false(), x, y, z) -> c_9(averIter^#(plus(x, s(s(s(0())))), plus(y, s(0())), plus(z, s(0())))) , plus^#(s(x), y) -> c_10(plus^#(x, y)) , plus^#(0(), y) -> c_11(y) , append^#(nil(), y) -> c_12(y) , append^#(cons(n, x), y) -> c_13(n, x, y) , low^#(n, nil()) -> c_14() , low^#(n, cons(m, x)) -> c_15(if_low^#(ge(m, n), n, cons(m, x))) , if_low^#(true(), n, cons(m, x)) -> c_16(low^#(n, x)) , if_low^#(false(), n, cons(m, x)) -> c_17(m, low^#(n, x)) , high^#(n, nil()) -> c_18() , high^#(n, cons(m, x)) -> c_19(if_high^#(ge(m, n), n, cons(m, x))) , if_high^#(true(), n, cons(m, x)) -> c_20(average^#(m, m), high^#(n, x)) , if_high^#(false(), n, cons(m, x)) -> c_21(high^#(n, x)) , quicksort^#(x) -> c_22(ifquick^#(isempty(x), x)) , ifquick^#(true(), x) -> c_23() , ifquick^#(false(), x) -> c_24(append^#(quicksort(low(head(x), tail(x))), cons(tail(x), quicksort(high(head(x), tail(x)))))) , isempty^#(nil()) -> c_25() , isempty^#(cons(n, x)) -> c_26() , head^#(nil()) -> c_27() , head^#(cons(n, x)) -> c_28(n) , tail^#(nil()) -> c_29() , tail^#(cons(n, x)) -> c_30(x) , a^#() -> c_31() , a^#() -> c_32() } Strict Trs: { average(x, y) -> if(ge(x, y), x, y) , if(true(), x, y) -> averIter(y, x, y) , if(false(), x, y) -> averIter(x, y, x) , ge(x, 0()) -> true() , ge(s(x), s(y)) -> ge(x, y) , ge(0(), s(y)) -> false() , averIter(x, y, z) -> ifIter(ge(x, y), x, y, z) , ifIter(true(), x, y, z) -> z , ifIter(false(), x, y, z) -> averIter(plus(x, s(s(s(0())))), plus(y, s(0())), plus(z, s(0()))) , plus(s(x), y) -> s(plus(x, y)) , plus(0(), y) -> y , append(nil(), y) -> y , append(cons(n, x), y) -> cons(n, app(x, y)) , low(n, nil()) -> nil() , low(n, cons(m, x)) -> if_low(ge(m, n), n, cons(m, x)) , if_low(true(), n, cons(m, x)) -> low(n, x) , if_low(false(), n, cons(m, x)) -> cons(m, low(n, x)) , high(n, nil()) -> nil() , high(n, cons(m, x)) -> if_high(ge(m, n), n, cons(m, x)) , if_high(true(), n, cons(m, x)) -> cons(average(m, m), high(n, x)) , if_high(false(), n, cons(m, x)) -> high(n, x) , quicksort(x) -> ifquick(isempty(x), x) , ifquick(true(), x) -> nil() , ifquick(false(), x) -> append(quicksort(low(head(x), tail(x))), cons(tail(x), quicksort(high(head(x), tail(x))))) , isempty(nil()) -> true() , isempty(cons(n, x)) -> false() , head(nil()) -> error() , head(cons(n, x)) -> n , tail(nil()) -> nil() , tail(cons(n, x)) -> x , a() -> b() , a() -> c() } Obligation: runtime complexity Answer: MAYBE We estimate the number of application of {5,7,14,18,23,25,26,27,29,31,32} by applications of Pre({5,7,14,18,23,25,26,27,29,31,32}) = {6,8,11,12,13,16,17,20,21,22,28,30}. Here rules are labeled as follows: DPs: { 1: average^#(x, y) -> c_1(if^#(ge(x, y), x, y)) , 2: if^#(true(), x, y) -> c_2(averIter^#(y, x, y)) , 3: if^#(false(), x, y) -> c_3(averIter^#(x, y, x)) , 4: averIter^#(x, y, z) -> c_7(ifIter^#(ge(x, y), x, y, z)) , 5: ge^#(x, 0()) -> c_4() , 6: ge^#(s(x), s(y)) -> c_5(ge^#(x, y)) , 7: ge^#(0(), s(y)) -> c_6() , 8: ifIter^#(true(), x, y, z) -> c_8(z) , 9: ifIter^#(false(), x, y, z) -> c_9(averIter^#(plus(x, s(s(s(0())))), plus(y, s(0())), plus(z, s(0())))) , 10: plus^#(s(x), y) -> c_10(plus^#(x, y)) , 11: plus^#(0(), y) -> c_11(y) , 12: append^#(nil(), y) -> c_12(y) , 13: append^#(cons(n, x), y) -> c_13(n, x, y) , 14: low^#(n, nil()) -> c_14() , 15: low^#(n, cons(m, x)) -> c_15(if_low^#(ge(m, n), n, cons(m, x))) , 16: if_low^#(true(), n, cons(m, x)) -> c_16(low^#(n, x)) , 17: if_low^#(false(), n, cons(m, x)) -> c_17(m, low^#(n, x)) , 18: high^#(n, nil()) -> c_18() , 19: high^#(n, cons(m, x)) -> c_19(if_high^#(ge(m, n), n, cons(m, x))) , 20: if_high^#(true(), n, cons(m, x)) -> c_20(average^#(m, m), high^#(n, x)) , 21: if_high^#(false(), n, cons(m, x)) -> c_21(high^#(n, x)) , 22: quicksort^#(x) -> c_22(ifquick^#(isempty(x), x)) , 23: ifquick^#(true(), x) -> c_23() , 24: ifquick^#(false(), x) -> c_24(append^#(quicksort(low(head(x), tail(x))), cons(tail(x), quicksort(high(head(x), tail(x)))))) , 25: isempty^#(nil()) -> c_25() , 26: isempty^#(cons(n, x)) -> c_26() , 27: head^#(nil()) -> c_27() , 28: head^#(cons(n, x)) -> c_28(n) , 29: tail^#(nil()) -> c_29() , 30: tail^#(cons(n, x)) -> c_30(x) , 31: a^#() -> c_31() , 32: a^#() -> c_32() } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { average^#(x, y) -> c_1(if^#(ge(x, y), x, y)) , if^#(true(), x, y) -> c_2(averIter^#(y, x, y)) , if^#(false(), x, y) -> c_3(averIter^#(x, y, x)) , averIter^#(x, y, z) -> c_7(ifIter^#(ge(x, y), x, y, z)) , ge^#(s(x), s(y)) -> c_5(ge^#(x, y)) , ifIter^#(true(), x, y, z) -> c_8(z) , ifIter^#(false(), x, y, z) -> c_9(averIter^#(plus(x, s(s(s(0())))), plus(y, s(0())), plus(z, s(0())))) , plus^#(s(x), y) -> c_10(plus^#(x, y)) , plus^#(0(), y) -> c_11(y) , append^#(nil(), y) -> c_12(y) , append^#(cons(n, x), y) -> c_13(n, x, y) , low^#(n, cons(m, x)) -> c_15(if_low^#(ge(m, n), n, cons(m, x))) , if_low^#(true(), n, cons(m, x)) -> c_16(low^#(n, x)) , if_low^#(false(), n, cons(m, x)) -> c_17(m, low^#(n, x)) , high^#(n, cons(m, x)) -> c_19(if_high^#(ge(m, n), n, cons(m, x))) , if_high^#(true(), n, cons(m, x)) -> c_20(average^#(m, m), high^#(n, x)) , if_high^#(false(), n, cons(m, x)) -> c_21(high^#(n, x)) , quicksort^#(x) -> c_22(ifquick^#(isempty(x), x)) , ifquick^#(false(), x) -> c_24(append^#(quicksort(low(head(x), tail(x))), cons(tail(x), quicksort(high(head(x), tail(x)))))) , head^#(cons(n, x)) -> c_28(n) , tail^#(cons(n, x)) -> c_30(x) } Strict Trs: { average(x, y) -> if(ge(x, y), x, y) , if(true(), x, y) -> averIter(y, x, y) , if(false(), x, y) -> averIter(x, y, x) , ge(x, 0()) -> true() , ge(s(x), s(y)) -> ge(x, y) , ge(0(), s(y)) -> false() , averIter(x, y, z) -> ifIter(ge(x, y), x, y, z) , ifIter(true(), x, y, z) -> z , ifIter(false(), x, y, z) -> averIter(plus(x, s(s(s(0())))), plus(y, s(0())), plus(z, s(0()))) , plus(s(x), y) -> s(plus(x, y)) , plus(0(), y) -> y , append(nil(), y) -> y , append(cons(n, x), y) -> cons(n, app(x, y)) , low(n, nil()) -> nil() , low(n, cons(m, x)) -> if_low(ge(m, n), n, cons(m, x)) , if_low(true(), n, cons(m, x)) -> low(n, x) , if_low(false(), n, cons(m, x)) -> cons(m, low(n, x)) , high(n, nil()) -> nil() , high(n, cons(m, x)) -> if_high(ge(m, n), n, cons(m, x)) , if_high(true(), n, cons(m, x)) -> cons(average(m, m), high(n, x)) , if_high(false(), n, cons(m, x)) -> high(n, x) , quicksort(x) -> ifquick(isempty(x), x) , ifquick(true(), x) -> nil() , ifquick(false(), x) -> append(quicksort(low(head(x), tail(x))), cons(tail(x), quicksort(high(head(x), tail(x))))) , isempty(nil()) -> true() , isempty(cons(n, x)) -> false() , head(nil()) -> error() , head(cons(n, x)) -> n , tail(nil()) -> nil() , tail(cons(n, x)) -> x , a() -> b() , a() -> c() } Weak DPs: { ge^#(x, 0()) -> c_4() , ge^#(0(), s(y)) -> c_6() , low^#(n, nil()) -> c_14() , high^#(n, nil()) -> c_18() , ifquick^#(true(), x) -> c_23() , isempty^#(nil()) -> c_25() , isempty^#(cons(n, x)) -> c_26() , head^#(nil()) -> c_27() , tail^#(nil()) -> c_29() , a^#() -> c_31() , a^#() -> c_32() } Obligation: runtime complexity Answer: MAYBE Empty strict component of the problem is NOT empty. Arrrr..