details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	10.6172719002 seconds
cpu usage	36.426526053
max memory	4.342484992E9

stage attributes

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

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^1)) proof of /export/starexec/sandbox2/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, 376 ms] (6) BOUNDS(1, n^1) (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (8) TRS for Loop Detection (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (10) BEST (11) proven lower bound (12) LowerBoundPropagationProof [FINISHED, 0 ms] (13) BOUNDS(n^1, INF) (14) TRS for Loop Detection ---------------------------------------- (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(sel(s(X), cons(Y, Z))) -> mark(sel(X, Z)) active(sel(0, cons(X, Z))) -> mark(X) active(first(0, Z)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) active(sel1(s(X), cons(Y, Z))) -> mark(sel1(X, Z)) active(sel1(0, cons(X, Z))) -> mark(quote(X)) active(first1(0, Z)) -> mark(nil1) active(first1(s(X), cons(Y, Z))) -> mark(cons1(quote(Y), first1(X, Z))) active(quote(0)) -> mark(01) active(quote1(cons(X, Z))) -> mark(cons1(quote(X), quote1(Z))) active(quote1(nil)) -> mark(nil1) active(quote(s(X))) -> mark(s1(quote(X))) active(quote(sel(X, Z))) -> mark(sel1(X, Z)) active(quote1(first(X, Z))) -> mark(first1(X, Z)) active(unquote(01)) -> mark(0) active(unquote(s1(X))) -> mark(s(unquote(X))) active(unquote1(nil1)) -> mark(nil) active(unquote1(cons1(X, Z))) -> mark(fcons(unquote(X), unquote1(Z))) active(fcons(X, Z)) -> mark(cons(X, Z)) active(sel(X1, X2)) -> sel(active(X1), X2) active(sel(X1, X2)) -> sel(X1, active(X2)) active(s(X)) -> s(active(X)) active(cons(X1, X2)) -> cons(active(X1), X2) active(first(X1, X2)) -> first(active(X1), X2) active(first(X1, X2)) -> first(X1, active(X2)) active(from(X)) -> from(active(X)) active(sel1(X1, X2)) -> sel1(active(X1), X2) active(sel1(X1, X2)) -> sel1(X1, active(X2)) active(first1(X1, X2)) -> first1(active(X1), X2) active(first1(X1, X2)) -> first1(X1, active(X2)) active(cons1(X1, X2)) -> cons1(active(X1), X2) active(cons1(X1, X2)) -> cons1(X1, active(X2)) active(s1(X)) -> s1(active(X)) active(unquote(X)) -> unquote(active(X)) active(unquote1(X)) -> unquote1(active(X)) active(fcons(X1, X2)) -> fcons(active(X1), X2) active(fcons(X1, X2)) -> fcons(X1, active(X2)) sel(mark(X1), X2) -> mark(sel(X1, X2)) sel(X1, mark(X2)) -> mark(sel(X1, X2)) s(mark(X)) -> mark(s(X)) cons(mark(X1), X2) -> mark(cons(X1, X2)) first(mark(X1), X2) -> mark(first(X1, X2)) first(X1, mark(X2)) -> mark(first(X1, X2)) from(mark(X)) -> mark(from(X)) sel1(mark(X1), X2) -> mark(sel1(X1, X2)) sel1(X1, mark(X2)) -> mark(sel1(X1, X2)) first1(mark(X1), X2) -> mark(first1(X1, X2)) first1(X1, mark(X2)) -> mark(first1(X1, X2)) cons1(mark(X1), X2) -> mark(cons1(X1, X2)) cons1(X1, mark(X2)) -> mark(cons1(X1, X2)) s1(mark(X)) -> mark(s1(X)) unquote(mark(X)) -> mark(unquote(X)) unquote1(mark(X)) -> mark(unquote1(X)) fcons(mark(X1), X2) -> mark(fcons(X1, X2)) fcons(X1, mark(X2)) -> mark(fcons(X1, X2)) proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) proper(s(X)) -> s(proper(X)) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(0) -> ok(0) proper(first(X1, X2)) -> first(proper(X1), proper(X2)) popout

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

job log

popout

actions

all output return to Runti Compl Full Rewri 10127