Derivational Complexity: TRS Innermost pair #487105460

details

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

run statistics

property	value
solver	AProVE
configuration	rcdcRelativeAlsoLower
runtime (wallclock)	292.28 seconds
cpu usage	1147.14
user time	1135.66
system time	11.4831
max virtual memory	1.9924256E7
max residence set size	1.4877568E7

stage attributes

key	value
starexec-result	WORST_CASE(Omega(n^1), ?)

output

WORST_CASE(Omega(n^1), ?)
proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, INF).

(0) DCpxTrs
(1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms]
(2) CpxRelTRS
(3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 603 ms]
(4) CpxRelTRS
(5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
(6) CpxRelTRS
(7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
(8) typed CpxTrs
(9) OrderProof [LOWER BOUND(ID), 0 ms]
(10) typed CpxTrs
(11) RewriteLemmaProof [LOWER BOUND(ID), 2346 ms]
(12) BEST
    (13) proven lower bound
        (14) LowerBoundPropagationProof [FINISHED, 0 ms]
        (15) BOUNDS(n^1, INF)
    (16) typed CpxTrs
        (17) RewriteLemmaProof [LOWER BOUND(ID), 76 ms]
        (18) typed CpxTrs
        (19) RewriteLemmaProof [LOWER BOUND(ID), 81 ms]
        (20) typed CpxTrs
        (21) RewriteLemmaProof [LOWER BOUND(ID), 577 ms]
        (22) typed CpxTrs


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

(0)
Obligation:
The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^1, INF).


The TRS R consists of the following rules:

   O(0) -> 0
   +(0, x) -> x
   +(x, 0) -> x
   +(O(x), O(y)) -> O(+(x, y))
   +(O(x), I(y)) -> I(+(x, y))
   +(I(x), O(y)) -> I(+(x, y))
   +(I(x), I(y)) -> O(+(+(x, y), I(0)))
   +(x, +(y, z)) -> +(+(x, y), z)
   -(x, 0) -> x
   -(0, x) -> 0
   -(O(x), O(y)) -> O(-(x, y))
   -(O(x), I(y)) -> I(-(-(x, y), I(1)))
   -(I(x), O(y)) -> I(-(x, y))
   -(I(x), I(y)) -> O(-(x, y))
   not(true) -> false
   not(false) -> true
   and(x, true) -> x
   and(x, false) -> false
   if(true, x, y) -> x
   if(false, x, y) -> y
   ge(O(x), O(y)) -> ge(x, y)
   ge(O(x), I(y)) -> not(ge(y, x))
   ge(I(x), O(y)) -> ge(x, y)
   ge(I(x), I(y)) -> ge(x, y)
   ge(x, 0) -> true
   ge(0, O(x)) -> ge(0, x)
   ge(0, I(x)) -> false
   Log'(0) -> 0
   Log'(I(x)) -> +(Log'(x), I(0))
   Log'(O(x)) -> if(ge(x, I(0)), +(Log'(x), I(0)), 0)
   Log(x) -> -(Log'(x), I(0))
   Val(L(x)) -> x
   Val(N(x, l, r)) -> x
   Min(L(x)) -> x
   Min(N(x, l, r)) -> Min(l)
   Max(L(x)) -> x
   Max(N(x, l, r)) -> Max(r)
   BS(L(x)) -> true
   BS(N(x, l, r)) -> and(and(ge(x, Max(l)), ge(Min(r), x)), and(BS(l), BS(r)))
   Size(L(x)) -> I(0)
   Size(N(x, l, r)) -> +(+(Size(l), Size(r)), I(1))
   WB(L(x)) -> true
   WB(N(x, l, r)) -> and(if(ge(Size(l), Size(r)), ge(I(0), -(Size(l), Size(r))), ge(I(0), -(Size(r), Size(l)))), and(WB(l), WB(r)))

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

(1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID))
The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem:

   encArg(0) -> 0
   encArg(I(x_1)) -> I(encArg(x_1))
   encArg(1) -> 1
   encArg(true) -> true
   encArg(false) -> false
   encArg(L(x_1)) -> L(encArg(x_1))
   encArg(N(x_1, x_2, x_3)) -> N(encArg(x_1), encArg(x_2), encArg(x_3))
   encArg(l) -> l

popout

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

job log

popout

actions all output return to Derivational Complexity: TRS Innermost