MAYBE 1136.57/297.52 MAYBE 1136.57/297.52 1136.57/297.52 We are left with following problem, upon which TcT provides the 1136.57/297.52 certificate MAYBE. 1136.57/297.52 1136.57/297.52 Strict Trs: 1136.57/297.52 { nonZero(0()) -> false() 1136.57/297.52 , nonZero(s(x)) -> true() 1136.57/297.52 , p(0()) -> 0() 1136.57/297.52 , p(s(x)) -> x 1136.57/297.52 , id_inc(x) -> x 1136.57/297.52 , id_inc(x) -> s(x) 1136.57/297.52 , random(x) -> rand(x, 0()) 1136.57/297.52 , rand(x, y) -> if(nonZero(x), x, y) 1136.57/297.52 , if(false(), x, y) -> y 1136.57/297.52 , if(true(), x, y) -> rand(p(x), id_inc(y)) } 1136.57/297.52 Obligation: 1136.57/297.52 runtime complexity 1136.57/297.52 Answer: 1136.57/297.52 MAYBE 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'With Problem ... (timeout of 297 seconds)' failed due to the 1136.57/297.52 following reason: 1136.57/297.52 1136.57/297.52 Computation stopped due to timeout after 297.0 seconds. 1136.57/297.52 1136.57/297.52 2) 'Best' failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'With Problem ... (timeout of 148 seconds) (timeout of 297 1136.57/297.52 seconds)' failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'empty' failed due to the following reason: 1136.57/297.52 1136.57/297.52 Empty strict component of the problem is NOT empty. 1136.57/297.52 1136.57/297.52 2) 'With Problem ...' failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'empty' failed due to the following reason: 1136.57/297.52 1136.57/297.52 Empty strict component of the problem is NOT empty. 1136.57/297.52 1136.57/297.52 2) 'Fastest' failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'With Problem ...' failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'empty' failed due to the following reason: 1136.57/297.52 1136.57/297.52 Empty strict component of the problem is NOT empty. 1136.57/297.52 1136.57/297.52 2) 'With Problem ...' failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'empty' failed due to the following reason: 1136.57/297.52 1136.57/297.52 Empty strict component of the problem is NOT empty. 1136.57/297.52 1136.57/297.52 2) 'With Problem ...' failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'empty' failed due to the following reason: 1136.57/297.52 1136.57/297.52 Empty strict component of the problem is NOT empty. 1136.57/297.52 1136.57/297.52 2) 'With Problem ...' failed due to the following reason: 1136.57/297.52 1136.57/297.52 Empty strict component of the problem is NOT empty. 1136.57/297.52 1136.57/297.52 1136.57/297.52 1136.57/297.52 1136.57/297.52 2) 'With Problem ...' failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'empty' failed due to the following reason: 1136.57/297.52 1136.57/297.52 Empty strict component of the problem is NOT empty. 1136.57/297.52 1136.57/297.52 2) 'With Problem ...' failed due to the following reason: 1136.57/297.52 1136.57/297.52 Empty strict component of the problem is NOT empty. 1136.57/297.52 1136.57/297.52 1136.57/297.52 1136.57/297.52 1136.57/297.52 1136.57/297.52 2) 'Best' failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'Polynomial Path Order (PS) (timeout of 297 seconds)' failed due 1136.57/297.52 to the following reason: 1136.57/297.52 1136.57/297.52 The processor is inapplicable, reason: 1136.57/297.52 Processor only applicable for innermost runtime complexity analysis 1136.57/297.52 1136.57/297.52 2) 'bsearch-popstar (timeout of 297 seconds)' failed due to the 1136.57/297.52 following reason: 1136.57/297.52 1136.57/297.52 The processor is inapplicable, reason: 1136.57/297.52 Processor only applicable for innermost runtime complexity analysis 1136.57/297.52 1136.57/297.52 1136.57/297.52 3) 'Fastest (timeout of 24 seconds) (timeout of 297 seconds)' 1136.57/297.52 failed due to the following reason: 1136.57/297.52 1136.57/297.52 None of the processors succeeded. 1136.57/297.52 1136.57/297.52 Details of failed attempt(s): 1136.57/297.52 ----------------------------- 1136.57/297.52 1) 'Bounds with minimal-enrichment and initial automaton 'match'' 1136.57/297.52 failed due to the following reason: 1136.57/297.52 1136.57/297.52 match-boundness of the problem could not be verified. 1136.57/297.52 1136.57/297.52 2) 'Bounds with perSymbol-enrichment and initial automaton 'match'' 1136.57/297.52 failed due to the following reason: 1136.57/297.52 1136.57/297.52 match-boundness of the problem could not be verified. 1136.57/297.52 1136.57/297.52 1136.57/297.52 1136.57/297.52 3) 'Weak Dependency Pairs (timeout of 297 seconds)' failed due to 1136.57/297.52 the following reason: 1136.57/297.52 1136.57/297.52 We add the following weak dependency pairs: 1136.57/297.52 1136.57/297.52 Strict DPs: 1136.57/297.52 { nonZero^#(0()) -> c_1() 1136.57/297.52 , nonZero^#(s(x)) -> c_2() 1136.57/297.52 , p^#(0()) -> c_3() 1136.57/297.52 , p^#(s(x)) -> c_4(x) 1136.57/297.52 , id_inc^#(x) -> c_5(x) 1136.57/297.52 , id_inc^#(x) -> c_6(x) 1136.57/297.52 , random^#(x) -> c_7(rand^#(x, 0())) 1136.57/297.52 , rand^#(x, y) -> c_8(if^#(nonZero(x), x, y)) 1136.57/297.52 , if^#(false(), x, y) -> c_9(y) 1136.57/297.52 , if^#(true(), x, y) -> c_10(rand^#(p(x), id_inc(y))) } 1136.57/297.52 1136.57/297.52 and mark the set of starting terms. 1136.57/297.52 1136.57/297.52 We are left with following problem, upon which TcT provides the 1136.57/297.52 certificate MAYBE. 1136.57/297.52 1136.57/297.52 Strict DPs: 1136.57/297.52 { nonZero^#(0()) -> c_1() 1136.57/297.52 , nonZero^#(s(x)) -> c_2() 1136.57/297.52 , p^#(0()) -> c_3() 1136.57/297.52 , p^#(s(x)) -> c_4(x) 1136.57/297.52 , id_inc^#(x) -> c_5(x) 1136.57/297.52 , id_inc^#(x) -> c_6(x) 1136.57/297.52 , random^#(x) -> c_7(rand^#(x, 0())) 1136.57/297.52 , rand^#(x, y) -> c_8(if^#(nonZero(x), x, y)) 1136.57/297.52 , if^#(false(), x, y) -> c_9(y) 1136.57/297.52 , if^#(true(), x, y) -> c_10(rand^#(p(x), id_inc(y))) } 1136.57/297.52 Strict Trs: 1136.57/297.52 { nonZero(0()) -> false() 1136.57/297.52 , nonZero(s(x)) -> true() 1136.57/297.52 , p(0()) -> 0() 1136.57/297.52 , p(s(x)) -> x 1136.57/297.52 , id_inc(x) -> x 1136.57/297.52 , id_inc(x) -> s(x) 1136.57/297.52 , random(x) -> rand(x, 0()) 1136.57/297.52 , rand(x, y) -> if(nonZero(x), x, y) 1136.57/297.52 , if(false(), x, y) -> y 1136.57/297.52 , if(true(), x, y) -> rand(p(x), id_inc(y)) } 1136.57/297.52 Obligation: 1136.57/297.52 runtime complexity 1136.57/297.52 Answer: 1136.57/297.52 MAYBE 1136.57/297.52 1136.57/297.52 We estimate the number of application of {1,2,3} by applications of 1136.57/297.52 Pre({1,2,3}) = {4,5,6,9}. Here rules are labeled as follows: 1136.57/297.52 1136.57/297.52 DPs: 1136.57/297.52 { 1: nonZero^#(0()) -> c_1() 1136.57/297.52 , 2: nonZero^#(s(x)) -> c_2() 1136.57/297.52 , 3: p^#(0()) -> c_3() 1136.57/297.52 , 4: p^#(s(x)) -> c_4(x) 1136.57/297.52 , 5: id_inc^#(x) -> c_5(x) 1136.57/297.52 , 6: id_inc^#(x) -> c_6(x) 1136.57/297.52 , 7: random^#(x) -> c_7(rand^#(x, 0())) 1136.57/297.52 , 8: rand^#(x, y) -> c_8(if^#(nonZero(x), x, y)) 1136.57/297.52 , 9: if^#(false(), x, y) -> c_9(y) 1136.57/297.52 , 10: if^#(true(), x, y) -> c_10(rand^#(p(x), id_inc(y))) } 1136.57/297.52 1136.57/297.52 We are left with following problem, upon which TcT provides the 1136.57/297.52 certificate MAYBE. 1136.57/297.52 1136.57/297.52 Strict DPs: 1136.57/297.52 { p^#(s(x)) -> c_4(x) 1136.57/297.52 , id_inc^#(x) -> c_5(x) 1136.57/297.52 , id_inc^#(x) -> c_6(x) 1136.57/297.52 , random^#(x) -> c_7(rand^#(x, 0())) 1136.57/297.52 , rand^#(x, y) -> c_8(if^#(nonZero(x), x, y)) 1136.57/297.52 , if^#(false(), x, y) -> c_9(y) 1136.57/297.52 , if^#(true(), x, y) -> c_10(rand^#(p(x), id_inc(y))) } 1136.57/297.52 Strict Trs: 1136.57/297.52 { nonZero(0()) -> false() 1136.57/297.52 , nonZero(s(x)) -> true() 1136.57/297.52 , p(0()) -> 0() 1136.57/297.52 , p(s(x)) -> x 1136.57/297.52 , id_inc(x) -> x 1136.57/297.52 , id_inc(x) -> s(x) 1136.57/297.52 , random(x) -> rand(x, 0()) 1136.57/297.52 , rand(x, y) -> if(nonZero(x), x, y) 1136.57/297.52 , if(false(), x, y) -> y 1136.57/297.52 , if(true(), x, y) -> rand(p(x), id_inc(y)) } 1136.57/297.52 Weak DPs: 1136.57/297.52 { nonZero^#(0()) -> c_1() 1136.57/297.52 , nonZero^#(s(x)) -> c_2() 1136.57/297.52 , p^#(0()) -> c_3() } 1136.57/297.52 Obligation: 1136.57/297.52 runtime complexity 1136.57/297.52 Answer: 1136.57/297.52 MAYBE 1136.57/297.52 1136.57/297.52 Empty strict component of the problem is NOT empty. 1136.57/297.52 1136.57/297.52 1136.57/297.52 Arrrr.. 1137.13/298.07 EOF