MAYBE We are left with following problem, upon which TcT provides the certificate MAYBE. Strict Trs: { length(nil()) -> 0() , length(cons(x, l)) -> s(length(l)) , lt(x, 0()) -> false() , lt(0(), s(y)) -> true() , lt(s(x), s(y)) -> lt(x, y) , head(nil()) -> undefined() , head(cons(x, l)) -> x , tail(nil()) -> nil() , tail(cons(x, l)) -> l , reverse(l) -> rev(0(), l, nil(), l) , rev(x, l, accu, orig) -> if(lt(x, length(orig)), x, l, accu, orig) , if(false(), x, l, accu, orig) -> accu , if(true(), x, l, accu, orig) -> rev(s(x), tail(l), cons(head(l), accu), orig) } 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: { length^#(nil()) -> c_1() , length^#(cons(x, l)) -> c_2(length^#(l)) , lt^#(x, 0()) -> c_3() , lt^#(0(), s(y)) -> c_4() , lt^#(s(x), s(y)) -> c_5(lt^#(x, y)) , head^#(nil()) -> c_6() , head^#(cons(x, l)) -> c_7(x) , tail^#(nil()) -> c_8() , tail^#(cons(x, l)) -> c_9(l) , reverse^#(l) -> c_10(rev^#(0(), l, nil(), l)) , rev^#(x, l, accu, orig) -> c_11(if^#(lt(x, length(orig)), x, l, accu, orig)) , if^#(false(), x, l, accu, orig) -> c_12(accu) , if^#(true(), x, l, accu, orig) -> c_13(rev^#(s(x), tail(l), cons(head(l), accu), orig)) } and mark the set of starting terms. We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { length^#(nil()) -> c_1() , length^#(cons(x, l)) -> c_2(length^#(l)) , lt^#(x, 0()) -> c_3() , lt^#(0(), s(y)) -> c_4() , lt^#(s(x), s(y)) -> c_5(lt^#(x, y)) , head^#(nil()) -> c_6() , head^#(cons(x, l)) -> c_7(x) , tail^#(nil()) -> c_8() , tail^#(cons(x, l)) -> c_9(l) , reverse^#(l) -> c_10(rev^#(0(), l, nil(), l)) , rev^#(x, l, accu, orig) -> c_11(if^#(lt(x, length(orig)), x, l, accu, orig)) , if^#(false(), x, l, accu, orig) -> c_12(accu) , if^#(true(), x, l, accu, orig) -> c_13(rev^#(s(x), tail(l), cons(head(l), accu), orig)) } Strict Trs: { length(nil()) -> 0() , length(cons(x, l)) -> s(length(l)) , lt(x, 0()) -> false() , lt(0(), s(y)) -> true() , lt(s(x), s(y)) -> lt(x, y) , head(nil()) -> undefined() , head(cons(x, l)) -> x , tail(nil()) -> nil() , tail(cons(x, l)) -> l , reverse(l) -> rev(0(), l, nil(), l) , rev(x, l, accu, orig) -> if(lt(x, length(orig)), x, l, accu, orig) , if(false(), x, l, accu, orig) -> accu , if(true(), x, l, accu, orig) -> rev(s(x), tail(l), cons(head(l), accu), orig) } Obligation: runtime complexity Answer: MAYBE We estimate the number of application of {1,3,4,6,8} by applications of Pre({1,3,4,6,8}) = {2,5,7,9,12}. Here rules are labeled as follows: DPs: { 1: length^#(nil()) -> c_1() , 2: length^#(cons(x, l)) -> c_2(length^#(l)) , 3: lt^#(x, 0()) -> c_3() , 4: lt^#(0(), s(y)) -> c_4() , 5: lt^#(s(x), s(y)) -> c_5(lt^#(x, y)) , 6: head^#(nil()) -> c_6() , 7: head^#(cons(x, l)) -> c_7(x) , 8: tail^#(nil()) -> c_8() , 9: tail^#(cons(x, l)) -> c_9(l) , 10: reverse^#(l) -> c_10(rev^#(0(), l, nil(), l)) , 11: rev^#(x, l, accu, orig) -> c_11(if^#(lt(x, length(orig)), x, l, accu, orig)) , 12: if^#(false(), x, l, accu, orig) -> c_12(accu) , 13: if^#(true(), x, l, accu, orig) -> c_13(rev^#(s(x), tail(l), cons(head(l), accu), orig)) } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { length^#(cons(x, l)) -> c_2(length^#(l)) , lt^#(s(x), s(y)) -> c_5(lt^#(x, y)) , head^#(cons(x, l)) -> c_7(x) , tail^#(cons(x, l)) -> c_9(l) , reverse^#(l) -> c_10(rev^#(0(), l, nil(), l)) , rev^#(x, l, accu, orig) -> c_11(if^#(lt(x, length(orig)), x, l, accu, orig)) , if^#(false(), x, l, accu, orig) -> c_12(accu) , if^#(true(), x, l, accu, orig) -> c_13(rev^#(s(x), tail(l), cons(head(l), accu), orig)) } Strict Trs: { length(nil()) -> 0() , length(cons(x, l)) -> s(length(l)) , lt(x, 0()) -> false() , lt(0(), s(y)) -> true() , lt(s(x), s(y)) -> lt(x, y) , head(nil()) -> undefined() , head(cons(x, l)) -> x , tail(nil()) -> nil() , tail(cons(x, l)) -> l , reverse(l) -> rev(0(), l, nil(), l) , rev(x, l, accu, orig) -> if(lt(x, length(orig)), x, l, accu, orig) , if(false(), x, l, accu, orig) -> accu , if(true(), x, l, accu, orig) -> rev(s(x), tail(l), cons(head(l), accu), orig) } Weak DPs: { length^#(nil()) -> c_1() , lt^#(x, 0()) -> c_3() , lt^#(0(), s(y)) -> c_4() , head^#(nil()) -> c_6() , tail^#(nil()) -> c_8() } Obligation: runtime complexity Answer: MAYBE Empty strict component of the problem is NOT empty. Arrrr..