Runti Compl Inner Rewri 22807 pair #381904598

details

property	value
status	complete
benchmark	mul_better.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	Frederiksen_Glenstrup

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	4.81116890907 seconds
cpu usage	15.442604862
max memory	3.73499904E9

stage attributes

key	value
output-size	15196
starexec-result	WORST_CASE(Omega(n^3), O(n^3))

output

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


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


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


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

(0) CpxTRS
(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
(2) CdtProblem
    (3) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
    (4) CdtProblem
    (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
    (6) CdtProblem
    (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 58 ms]
    (8) CdtProblem
    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 174 ms]
    (10) CdtProblem
    (11) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
    (12) BOUNDS(1, 1)
(13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(14) CpxTRS
    (15) SlicingProof [LOWER BOUND(ID), 0 ms]
    (16) CpxTRS
    (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
    (18) typed CpxTrs
    (19) OrderProof [LOWER BOUND(ID), 0 ms]
    (20) typed CpxTrs
    (21) RewriteLemmaProof [LOWER BOUND(ID), 287 ms]
    (22) BEST
        (23) proven lower bound
            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
            (25) BOUNDS(n^1, INF)
        (26) typed CpxTrs
            (27) RewriteLemmaProof [LOWER BOUND(ID), 78 ms]
            (28) proven lower bound
            (29) LowerBoundPropagationProof [FINISHED, 0 ms]
            (30) BOUNDS(n^3, INF)


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

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


The TRS R consists of the following rules:

   mul0(C(x, y), y') -> add0(mul0(y, y'), y')
   mul0(Z, y) -> Z
   add0(C(x, y), y') -> add0(y, C(S, y'))
   add0(Z, y) -> y
   second(C(x, y)) -> y
   isZero(C(x, y)) -> False
   isZero(Z) -> True
   goal(xs, ys) -> mul0(xs, ys)

S is empty.
Rewrite Strategy: INNERMOST
----------------------------------------

(1) CpxTrsToCdtProof (UPPER BOUND(ID))
Converted Cpx (relative) TRS to CDT
----------------------------------------

(2)
Obligation:
Complexity Dependency Tuples Problem

Rules:
   mul0(C(z0, z1), z2) -> add0(mul0(z1, z2), z2)
   mul0(Z, z0) -> Z
   add0(C(z0, z1), z2) -> add0(z1, C(S, z2))
   add0(Z, z0) -> z0
   second(C(z0, z1)) -> z1
   isZero(C(z0, z1)) -> False
   isZero(Z) -> True
   goal(z0, z1) -> mul0(z0, z1)
Tuples:
   MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2))
   MUL0(Z, z0) -> c1
   ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2)))
   ADD0(Z, z0) -> c3
   SECOND(C(z0, z1)) -> c4
   ISZERO(C(z0, z1)) -> c5
   ISZERO(Z) -> c6
   GOAL(z0, z1) -> c7(MUL0(z0, z1))
S tuples:
   MUL0(C(z0, z1), z2) -> c(ADD0(mul0(z1, z2), z2), MUL0(z1, z2))
   MUL0(Z, z0) -> c1
   ADD0(C(z0, z1), z2) -> c2(ADD0(z1, C(S, z2)))
   ADD0(Z, z0) -> c3
   SECOND(C(z0, z1)) -> c4

popout

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

job log

popout

actions all output return to Runti Compl Inner Rewri 22807