Runti Compl Full Rewri 10127 pair #381902723

details

property	value
status	complete
benchmark	perfect.xml
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n039.star.cs.uiowa.edu
space	Mixed_TRS

run statistics

property	value
solver	tct 2018-07-13
configuration	tct_rc
runtime (wallclock)	1.01504182816 seconds
cpu usage	3.967048575
max memory	5.933056E7

stage attributes

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

output

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


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


WORST_CASE(Omega(n^1),O(n^1))
* Step 1: Sum WORST_CASE(Omega(n^1),O(n^1))
    + Considered Problem:
        - Strict TRS:
            f(0(),y,0(),u) -> true()
            f(0(),y,s(z),u) -> false()
            f(s(x),0(),z,u) -> f(x,u,minus(z,s(x)),u)
            f(s(x),s(y),z,u) -> if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
            perfectp(0()) -> false()
            perfectp(s(x)) -> f(x,s(0()),s(x),s(x))
        - Signature:
            {f/4,perfectp/1} / {0/0,false/0,if/3,le/2,minus/2,s/1,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {f,perfectp} and constructors {0,false,if,le,minus,s,true}
    + Applied Processor:
        Sum {left = someStrategy, right = someStrategy}
    + Details:
        ()
** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?)
    + Considered Problem:
        - Strict TRS:
            f(0(),y,0(),u) -> true()
            f(0(),y,s(z),u) -> false()
            f(s(x),0(),z,u) -> f(x,u,minus(z,s(x)),u)
            f(s(x),s(y),z,u) -> if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
            perfectp(0()) -> false()
            perfectp(s(x)) -> f(x,s(0()),s(x),s(x))
        - Signature:
            {f/4,perfectp/1} / {0/0,false/0,if/3,le/2,minus/2,s/1,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {f,perfectp} and constructors {0,false,if,le,minus,s,true}
    + Applied Processor:
        DecreasingLoops {bound = AnyLoop, narrow = 10}
    + Details:
        The system has following decreasing Loops:
          f(x,0(),u,0()){x -> s(s(x))} =
            f(s(s(x)),0(),u,0()) ->^+ f(x,0(),minus(minus(u,s(s(x))),s(x)),0())
              = C[f(x,0(),minus(minus(u,s(s(x))),s(x)),0()) = f(x,0(),u,0()){u -> minus(minus(u,s(s(x))),s(x))}]

** Step 1.b:1: DependencyPairs WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            f(0(),y,0(),u) -> true()
            f(0(),y,s(z),u) -> false()
            f(s(x),0(),z,u) -> f(x,u,minus(z,s(x)),u)
            f(s(x),s(y),z,u) -> if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
            perfectp(0()) -> false()
            perfectp(s(x)) -> f(x,s(0()),s(x),s(x))
        - Signature:
            {f/4,perfectp/1} / {0/0,false/0,if/3,le/2,minus/2,s/1,true/0}
        - Obligation:
             runtime complexity wrt. defined symbols {f,perfectp} and constructors {0,false,if,le,minus,s,true}
    + Applied Processor:
        DependencyPairs {dpKind_ = WIDP}
    + Details:
        We add the following weak dependency pairs:
        
        Strict DPs
          f#(0(),y,0(),u) -> c_1()
          f#(0(),y,s(z),u) -> c_2()
          f#(s(x),0(),z,u) -> c_3(f#(x,u,minus(z,s(x)),u))
          f#(s(x),s(y),z,u) -> c_4(x,y,f#(s(x),minus(y,x),z,u),f#(x,u,z,u))
          perfectp#(0()) -> c_5()
          perfectp#(s(x)) -> c_6(f#(x,s(0()),s(x),s(x)))
        Weak DPs
          
        
        and mark the set of starting terms.
** Step 1.b:2: UsableRules WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict DPs:
            f#(0(),y,0(),u) -> c_1()
            f#(0(),y,s(z),u) -> c_2()
            f#(s(x),0(),z,u) -> c_3(f#(x,u,minus(z,s(x)),u))
            f#(s(x),s(y),z,u) -> c_4(x,y,f#(s(x),minus(y,x),z,u),f#(x,u,z,u))
            perfectp#(0()) -> c_5()
            perfectp#(s(x)) -> c_6(f#(x,s(0()),s(x),s(x)))
        - Strict TRS:
            f(0(),y,0(),u) -> true()
            f(0(),y,s(z),u) -> false()
            f(s(x),0(),z,u) -> f(x,u,minus(z,s(x)),u)
            f(s(x),s(y),z,u) -> if(le(x,y),f(s(x),minus(y,x),z,u),f(x,u,z,u))
            perfectp(0()) -> false()
            perfectp(s(x)) -> f(x,s(0()),s(x),s(x))
        - Signature:
            {f/4,perfectp/1,f#/4,perfectp#/1} / {0/0,false/0,if/3,le/2,minus/2,s/1,true/0,c_1/0,c_2/0,c_3/1,c_4/4,c_5/0
            ,c_6/1}
        - Obligation:
             runtime complexity wrt. defined symbols {f#,perfectp#} and constructors {0,false,if,le,minus,s,true}
    + Applied Processor:
        UsableRules
    + Details:
        We replace rewrite rules by usable rules:
          f#(0(),y,0(),u) -> c_1()

popout

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

job log

popout

actions all output return to Runti Compl Full Rewri 10127