Runti Compl Full Rewri 10127 pair #381902103

details

property	value
status	complete
benchmark	recursion-10.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n050.star.cs.uiowa.edu
space	TCT_12

run statistics

property	value
solver	tct 2018-07-13
configuration	tct_rc
runtime (wallclock)	38.9434790611 seconds
cpu usage	110.469044741
max memory	1.96001792E8

stage attributes

key	value
output-size	245107
starexec-result	WORST_CASE(Omega(n^1),O(n^10))

output

/export/starexec/sandbox2/solver/bin/starexec_run_tct_rc /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(Omega(n^1),O(n^10))
* Step 1: Sum WORST_CASE(Omega(n^1),O(n^10))
    + Considered Problem:
        - Strict TRS:
            f_0(x) -> a()
            f_1(x) -> g_1(x,x)
            f_10(x) -> g_10(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)
            f_6(x) -> g_6(x,x)
            f_7(x) -> g_7(x,x)
            f_8(x) -> g_8(x,x)
            f_9(x) -> g_9(x,x)
            g_1(s(x),y) -> b(f_0(y),g_1(x,y))
            g_10(s(x),y) -> b(f_9(y),g_10(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))
            g_6(s(x),y) -> b(f_5(y),g_6(x,y))
            g_7(s(x),y) -> b(f_6(y),g_7(x,y))
            g_8(s(x),y) -> b(f_7(y),g_8(x,y))
            g_9(s(x),y) -> b(f_8(y),g_9(x,y))
        - Signature:
            {f_0/1,f_1/1,f_10/1,f_2/1,f_3/1,f_4/1,f_5/1,f_6/1,f_7/1,f_8/1,f_9/1,g_1/2,g_10/2,g_2/2,g_3/2,g_4/2,g_5/2
            ,g_6/2,g_7/2,g_8/2,g_9/2} / {a/0,b/2,s/1}
        - Obligation:
             runtime complexity wrt. defined symbols {f_0,f_1,f_10,f_2,f_3,f_4,f_5,f_6,f_7,f_8,f_9,g_1,g_10,g_2,g_3,g_4
            ,g_5,g_6,g_7,g_8,g_9} 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_10(x) -> g_10(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)
            f_6(x) -> g_6(x,x)
            f_7(x) -> g_7(x,x)
            f_8(x) -> g_8(x,x)
            f_9(x) -> g_9(x,x)
            g_1(s(x),y) -> b(f_0(y),g_1(x,y))
            g_10(s(x),y) -> b(f_9(y),g_10(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))
            g_6(s(x),y) -> b(f_5(y),g_6(x,y))
            g_7(s(x),y) -> b(f_6(y),g_7(x,y))
            g_8(s(x),y) -> b(f_7(y),g_8(x,y))
            g_9(s(x),y) -> b(f_8(y),g_9(x,y))
        - Signature:
            {f_0/1,f_1/1,f_10/1,f_2/1,f_3/1,f_4/1,f_5/1,f_6/1,f_7/1,f_8/1,f_9/1,g_1/2,g_10/2,g_2/2,g_3/2,g_4/2,g_5/2
            ,g_6/2,g_7/2,g_8/2,g_9/2} / {a/0,b/2,s/1}
        - Obligation:
             runtime complexity wrt. defined symbols {f_0,f_1,f_10,f_2,f_3,f_4,f_5,f_6,f_7,f_8,f_9,g_1,g_10,g_2,g_3,g_4
            ,g_5,g_6,g_7,g_8,g_9} 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^10))
    + Considered Problem:
        - Strict TRS:
            f_0(x) -> a()
            f_1(x) -> g_1(x,x)
            f_10(x) -> g_10(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)
            f_6(x) -> g_6(x,x)
            f_7(x) -> g_7(x,x)
            f_8(x) -> g_8(x,x)
            f_9(x) -> g_9(x,x)
            g_1(s(x),y) -> b(f_0(y),g_1(x,y))
            g_10(s(x),y) -> b(f_9(y),g_10(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))
            g_6(s(x),y) -> b(f_5(y),g_6(x,y))

popout

output may be truncated. 'popout' for the full output.

job log

popout

actions all output return to Runti Compl Full Rewri 10127