Runti Compl Full Rewri 10127 pair #381903563

details

property	value
status	complete
benchmark	Ex1_2_AEL03_C.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	Transformed_CSR_04

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	12.0370631218 seconds
cpu usage	39.798924912
max memory	4.3273216E9

stage attributes

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

output

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


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


WORST_CASE(Omega(n^1), O(n^1))
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).

(0) CpxTRS
(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
(2) CpxTRS
    (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
    (4) CpxTRS
    (5) CpxTrsMatchBoundsTAProof [FINISHED, 254 ms]
    (6) BOUNDS(1, n^1)
(7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(8) CpxTRS
    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (10) typed CpxTrs
    (11) OrderProof [LOWER BOUND(ID), 0 ms]
    (12) typed CpxTrs
    (13) RewriteLemmaProof [LOWER BOUND(ID), 457 ms]
    (14) BEST
        (15) proven lower bound
            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
            (17) BOUNDS(n^1, INF)
        (18) typed CpxTrs
            (19) RewriteLemmaProof [LOWER BOUND(ID), 131 ms]
            (20) typed CpxTrs
            (21) RewriteLemmaProof [LOWER BOUND(ID), 113 ms]
            (22) typed CpxTrs
            (23) RewriteLemmaProof [LOWER BOUND(ID), 143 ms]
            (24) typed CpxTrs
            (25) RewriteLemmaProof [LOWER BOUND(ID), 117 ms]
            (26) typed CpxTrs
            (27) RewriteLemmaProof [LOWER BOUND(ID), 98 ms]
            (28) typed CpxTrs
            (29) RewriteLemmaProof [LOWER BOUND(ID), 57 ms]
            (30) typed CpxTrs
            (31) RewriteLemmaProof [LOWER BOUND(ID), 98 ms]
            (32) typed CpxTrs
            (33) RewriteLemmaProof [LOWER BOUND(ID), 100 ms]
            (34) typed CpxTrs
            (35) RewriteLemmaProof [LOWER BOUND(ID), 113 ms]
            (36) typed CpxTrs
            (37) RewriteLemmaProof [LOWER BOUND(ID), 54 ms]
            (38) typed CpxTrs
            (39) RewriteLemmaProof [LOWER BOUND(ID), 127 ms]
            (40) typed CpxTrs


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

(0)
Obligation:
The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).


The TRS R consists of the following rules:

   active(from(X)) -> mark(cons(X, from(s(X))))
   active(2ndspos(0, Z)) -> mark(rnil)
   active(2ndspos(s(N), cons(X, cons(Y, Z)))) -> mark(rcons(posrecip(Y), 2ndsneg(N, Z)))
   active(2ndsneg(0, Z)) -> mark(rnil)
   active(2ndsneg(s(N), cons(X, cons(Y, Z)))) -> mark(rcons(negrecip(Y), 2ndspos(N, Z)))
   active(pi(X)) -> mark(2ndspos(X, from(0)))
   active(plus(0, Y)) -> mark(Y)
   active(plus(s(X), Y)) -> mark(s(plus(X, Y)))
   active(times(0, Y)) -> mark(0)
   active(times(s(X), Y)) -> mark(plus(Y, times(X, Y)))
   active(square(X)) -> mark(times(X, X))
   active(s(X)) -> s(active(X))
   active(posrecip(X)) -> posrecip(active(X))
   active(negrecip(X)) -> negrecip(active(X))
   active(cons(X1, X2)) -> cons(active(X1), X2)
   active(rcons(X1, X2)) -> rcons(active(X1), X2)
   active(rcons(X1, X2)) -> rcons(X1, active(X2))
   active(from(X)) -> from(active(X))
   active(2ndspos(X1, X2)) -> 2ndspos(active(X1), X2)
   active(2ndspos(X1, X2)) -> 2ndspos(X1, active(X2))
   active(2ndsneg(X1, X2)) -> 2ndsneg(active(X1), X2)
   active(2ndsneg(X1, X2)) -> 2ndsneg(X1, active(X2))
   active(pi(X)) -> pi(active(X))
   active(plus(X1, X2)) -> plus(active(X1), X2)
   active(plus(X1, X2)) -> plus(X1, active(X2))
   active(times(X1, X2)) -> times(active(X1), X2)
   active(times(X1, X2)) -> times(X1, active(X2))
   active(square(X)) -> square(active(X))
   s(mark(X)) -> mark(s(X))
   posrecip(mark(X)) -> mark(posrecip(X))
   negrecip(mark(X)) -> mark(negrecip(X))
   cons(mark(X1), X2) -> mark(cons(X1, X2))
   rcons(mark(X1), X2) -> mark(rcons(X1, X2))
   rcons(X1, mark(X2)) -> mark(rcons(X1, X2))
   from(mark(X)) -> mark(from(X))

popout

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

job log

popout

actions all output return to Runti Compl Full Rewri 10127