details

property	value
status	complete
benchmark	division.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	Rubio_04

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	291.471271038 seconds
cpu usage	316.365555145
max memory	5.318127616E9

stage attributes

key	value
output-size	16583
starexec-result	WORST_CASE(Omega(n^1), 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^1), 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^1, n^3). (0) CpxTRS (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (2) CdtProblem (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CdtProblem (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CdtProblem (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 99 ms] (8) CdtProblem (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 184 ms] (10) CdtProblem (11) CdtKnowledgeProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CdtProblem (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^3)), 1237 ms] (14) CdtProblem (15) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] (16) BOUNDS(1, 1) (17) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (18) TRS for Loop Detection (19) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (20) BEST (21) proven lower bound (22) LowerBoundPropagationProof [FINISHED, 0 ms] (23) BOUNDS(n^1, INF) (24) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^3). The TRS R consists of the following rules: le(0, Y) -> true le(s(X), 0) -> false le(s(X), s(Y)) -> le(X, Y) minus(0, Y) -> 0 minus(s(X), Y) -> ifMinus(le(s(X), Y), s(X), Y) ifMinus(true, s(X), Y) -> 0 ifMinus(false, s(X), Y) -> s(minus(X, Y)) quot(0, s(Y)) -> 0 quot(s(X), s(Y)) -> s(quot(minus(X, Y), s(Y))) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (2) Obligation: Complexity Dependency Tuples Problem Rules: le(0, z0) -> true le(s(z0), 0) -> false le(s(z0), s(z1)) -> le(z0, z1) minus(0, z0) -> 0 minus(s(z0), z1) -> ifMinus(le(s(z0), z1), s(z0), z1) ifMinus(true, s(z0), z1) -> 0 ifMinus(false, s(z0), z1) -> s(minus(z0, z1)) quot(0, s(z0)) -> 0 quot(s(z0), s(z1)) -> s(quot(minus(z0, z1), s(z1))) Tuples: LE(0, z0) -> c LE(s(z0), 0) -> c1 LE(s(z0), s(z1)) -> c2(LE(z0, z1)) MINUS(0, z0) -> c3 MINUS(s(z0), z1) -> c4(IFMINUS(le(s(z0), z1), s(z0), z1), LE(s(z0), z1)) IFMINUS(true, s(z0), z1) -> c5 IFMINUS(false, s(z0), z1) -> c6(MINUS(z0, z1)) QUOT(0, s(z0)) -> c7 QUOT(s(z0), s(z1)) -> c8(QUOT(minus(z0, z1), s(z1)), MINUS(z0, z1)) S tuples: LE(0, z0) -> c LE(s(z0), 0) -> c1 LE(s(z0), s(z1)) -> c2(LE(z0, z1)) MINUS(0, z0) -> c3 MINUS(s(z0), z1) -> c4(IFMINUS(le(s(z0), z1), s(z0), z1), LE(s(z0), z1)) IFMINUS(true, s(z0), z1) -> c5 IFMINUS(false, s(z0), z1) -> c6(MINUS(z0, z1)) QUOT(0, s(z0)) -> c7 popout

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

job log

popout

actions

all output return to Runti Compl Inner Rewri 22807