details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	291.488368034 seconds
cpu usage	318.117717686
max memory	5.319585792E9

stage attributes

key	value
output-size	20703
starexec-result	WORST_CASE(Omega(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), ?) 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, INF). (0) CpxTRS (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxTRS (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (4) typed CpxTrs (5) OrderProof [LOWER BOUND(ID), 0 ms] (6) typed CpxTrs (7) RewriteLemmaProof [LOWER BOUND(ID), 367 ms] (8) BEST (9) proven lower bound (10) LowerBoundPropagationProof [FINISHED, 0 ms] (11) BOUNDS(n^1, INF) (12) typed CpxTrs (13) RewriteLemmaProof [LOWER BOUND(ID), 5217 ms] (14) typed CpxTrs (15) RewriteLemmaProof [LOWER BOUND(ID), 0 ms] (16) typed CpxTrs (17) RewriteLemmaProof [LOWER BOUND(ID), 29 ms] (18) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: p(s(N)) -> N +(N, 0) -> N +(s(N), s(M)) -> s(s(+(N, M))) *(N, 0) -> 0 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) gt(0, M) -> False gt(NzN, 0) -> u_4(is_NzNat(NzN)) u_4(True) -> True is_NzNat(0) -> False is_NzNat(s(N)) -> True gt(s(N), s(M)) -> gt(N, M) lt(N, M) -> gt(M, N) d(0, N) -> N d(s(N), s(M)) -> d(N, M) quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) quot(NzM, NzM) -> u_01(is_NzNat(NzM)) u_01(True) -> s(0) quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) u_21(True, NzM, N) -> u_2(gt(NzM, N)) u_2(True) -> 0 gcd(0, N) -> 0 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) u_02(True, NzM) -> NzM gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: p(s(N)) -> N +'(N, 0') -> N +'(s(N), s(M)) -> s(s(+'(N, M))) *'(N, 0') -> 0' *'(s(N), s(M)) -> s(+'(N, +'(M, *'(N, M)))) gt(0', M) -> False gt(NzN, 0') -> u_4(is_NzNat(NzN)) u_4(True) -> True is_NzNat(0') -> False is_NzNat(s(N)) -> True gt(s(N), s(M)) -> gt(N, M) lt(N, M) -> gt(M, N) d(0', N) -> N popout

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

job log

popout

actions

all output return to Runti Compl Full Rewri 10127