Deriv Compl Full Rewri 33144 pair #381922133

details

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

run statistics

property	value
solver	tct 2018-07-13
configuration	tct_dc
runtime (wallclock)	30.0318439007 seconds
cpu usage	96.49960694
max memory	5.6393728E7

stage attributes

key	value
output-size	8290
starexec-result	WORST_CASE(?,O(n^1))

output

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


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


WORST_CASE(?,O(n^1))
* Step 1: WeightGap WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            f(1()) -> f(g(1()))
            f(f(x)) -> f(x)
            g(0()) -> g(f(0()))
            g(g(x)) -> g(x)
        - Signature:
            {f/1,g/1} / {0/0,1/0}
        - Obligation:
             derivational complexity wrt. signature {0,1,f,g}
    + Applied Processor:
        WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = NoUArgs, wgOn = WgOnAny}
    + Details:
        The weightgap principle applies using the following nonconstant growth matrix-interpretation:
          We apply a matrix interpretation of kind triangular matrix interpretation:
          
          Following symbols are considered usable:
            all
          TcT has computed the following interpretation:
            p(0) = [9]         
            p(1) = [8]         
            p(f) = [1] x1 + [0]
            p(g) = [1] x1 + [4]
          
          Following rules are strictly oriented:
          g(g(x)) = [1] x + [8]
                  > [1] x + [4]
                  = g(x)       
          
          
          Following rules are (at-least) weakly oriented:
           f(1()) =  [8]        
                  >= [12]       
                  =  f(g(1()))  
          
          f(f(x)) =  [1] x + [0]
                  >= [1] x + [0]
                  =  f(x)       
          
           g(0()) =  [13]       
                  >= [13]       
                  =  g(f(0()))  
          
        Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 2: WeightGap WORST_CASE(?,O(n^1))
    + Considered Problem:
        - Strict TRS:
            f(1()) -> f(g(1()))
            f(f(x)) -> f(x)
            g(0()) -> g(f(0()))
        - Weak TRS:
            g(g(x)) -> g(x)
        - Signature:
            {f/1,g/1} / {0/0,1/0}
        - Obligation:
             derivational complexity wrt. signature {0,1,f,g}
    + Applied Processor:
        WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = NoUArgs, wgOn = WgOnAny}
    + Details:
        The weightgap principle applies using the following nonconstant growth matrix-interpretation:
          We apply a matrix interpretation of kind triangular matrix interpretation:
          
          Following symbols are considered usable:
            all
          TcT has computed the following interpretation:
            p(0) = [1]         
            p(1) = [5]         
            p(f) = [1] x1 + [2]
            p(g) = [1] x1 + [0]
          
          Following rules are strictly oriented:
          f(f(x)) = [1] x + [4]
                  > [1] x + [2]
                  = f(x)       
          
          
          Following rules are (at-least) weakly oriented:
           f(1()) =  [7]        
                  >= [7]        
                  =  f(g(1()))  
          
           g(0()) =  [1]        
                  >= [3]        
                  =  g(f(0()))  
          
          g(g(x)) =  [1] x + [0]
                  >= [1] x + [0]
                  =  g(x)       
          
        Further, it can be verified that all rules not oriented are covered by the weightgap condition.
* Step 3: NaturalMI WORST_CASE(?,O(n^1))
    + Considered Problem:

popout

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

job log

popout

actions all output return to Deriv Compl Full Rewri 33144