Spaces
Explore
Communities
Statistics
Reports
Cluster
Status
Help
Runti Compl Inner Rewri 22807 pair #381904148
details
property
value
status
complete
benchmark
recursion-5.xml
ran by
Akihisa Yamada
cpu timeout
1200 seconds
wallclock timeout
300 seconds
memory limit
137438953472 bytes
execution host
n038.star.cs.uiowa.edu
space
TCT_12
run statistics
property
value
solver
tct 2018-07-13
configuration
tct_rci
runtime (wallclock)
2.48120808601 seconds
cpu usage
10.848376002
max memory
1.38309632E8
stage attributes
key
value
output-size
70693
starexec-result
WORST_CASE(Omega(n^1),O(n^5))
output
/export/starexec/sandbox/solver/bin/starexec_run_tct_rci /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),O(n^5)) * Step 1: Sum WORST_CASE(Omega(n^1),O(n^5)) + Considered Problem: - Strict TRS: f_0(x) -> a() f_1(x) -> g_1(x,x) f_2(x) -> g_2(x,x) f_3(x) -> g_3(x,x) f_4(x) -> g_4(x,x) f_5(x) -> g_5(x,x) g_1(s(x),y) -> b(f_0(y),g_1(x,y)) g_2(s(x),y) -> b(f_1(y),g_2(x,y)) g_3(s(x),y) -> b(f_2(y),g_3(x,y)) g_4(s(x),y) -> b(f_3(y),g_4(x,y)) g_5(s(x),y) -> b(f_4(y),g_5(x,y)) - Signature: {f_0/1,f_1/1,f_2/1,f_3/1,f_4/1,f_5/1,g_1/2,g_2/2,g_3/2,g_4/2,g_5/2} / {a/0,b/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {f_0,f_1,f_2,f_3,f_4,f_5,g_1,g_2,g_3,g_4 ,g_5} and constructors {a,b,s} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: f_0(x) -> a() f_1(x) -> g_1(x,x) f_2(x) -> g_2(x,x) f_3(x) -> g_3(x,x) f_4(x) -> g_4(x,x) f_5(x) -> g_5(x,x) g_1(s(x),y) -> b(f_0(y),g_1(x,y)) g_2(s(x),y) -> b(f_1(y),g_2(x,y)) g_3(s(x),y) -> b(f_2(y),g_3(x,y)) g_4(s(x),y) -> b(f_3(y),g_4(x,y)) g_5(s(x),y) -> b(f_4(y),g_5(x,y)) - Signature: {f_0/1,f_1/1,f_2/1,f_3/1,f_4/1,f_5/1,g_1/2,g_2/2,g_3/2,g_4/2,g_5/2} / {a/0,b/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {f_0,f_1,f_2,f_3,f_4,f_5,g_1,g_2,g_3,g_4 ,g_5} and constructors {a,b,s} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: g_1(x,y){x -> s(x)} = g_1(s(x),y) ->^+ b(f_0(y),g_1(x,y)) = C[g_1(x,y) = g_1(x,y){}] ** Step 1.b:1: DependencyPairs WORST_CASE(?,O(n^5)) + Considered Problem: - Strict TRS: f_0(x) -> a() f_1(x) -> g_1(x,x) f_2(x) -> g_2(x,x) f_3(x) -> g_3(x,x) f_4(x) -> g_4(x,x) f_5(x) -> g_5(x,x) g_1(s(x),y) -> b(f_0(y),g_1(x,y)) g_2(s(x),y) -> b(f_1(y),g_2(x,y)) g_3(s(x),y) -> b(f_2(y),g_3(x,y)) g_4(s(x),y) -> b(f_3(y),g_4(x,y)) g_5(s(x),y) -> b(f_4(y),g_5(x,y)) - Signature: {f_0/1,f_1/1,f_2/1,f_3/1,f_4/1,f_5/1,g_1/2,g_2/2,g_3/2,g_4/2,g_5/2} / {a/0,b/2,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {f_0,f_1,f_2,f_3,f_4,f_5,g_1,g_2,g_3,g_4 ,g_5} and constructors {a,b,s} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs f_0#(x) -> c_1() f_1#(x) -> c_2(g_1#(x,x)) f_2#(x) -> c_3(g_2#(x,x)) f_3#(x) -> c_4(g_3#(x,x)) f_4#(x) -> c_5(g_4#(x,x)) f_5#(x) -> c_6(g_5#(x,x)) g_1#(s(x),y) -> c_7(f_0#(y),g_1#(x,y)) g_2#(s(x),y) -> c_8(f_1#(y),g_2#(x,y)) g_3#(s(x),y) -> c_9(f_2#(y),g_3#(x,y)) g_4#(s(x),y) -> c_10(f_3#(y),g_4#(x,y)) g_5#(s(x),y) -> c_11(f_4#(y),g_5#(x,y)) Weak DPs and mark the set of starting terms. ** Step 1.b:2: PredecessorEstimation WORST_CASE(?,O(n^5)) + Considered Problem: - Strict DPs:
popout
output may be truncated. 'popout' for the full output.
job log
popout
actions
all output
return to Runti Compl Inner Rewri 22807