details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	1.70640015602 seconds
cpu usage	3.747939064
max memory	2.00880128E8

stage attributes

key	value
output-size	3074
starexec-result	WORST_CASE(?, O(1))

output

/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(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(1, 1). (0) CpxTRS (1) DependencyGraphProof [UPPER BOUND(ID), 0 ms] (2) CpxTRS (3) NestedDefinedSymbolProof [UPPER BOUND(ID), 1 ms] (4) CpxTRS (5) NarrowingOnBasicTermsTerminatesProof [FINISHED, 0 ms] (6) BOUNDS(1, 1) ---------------------------------------- (0) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, 1). The TRS R consists of the following rules: i(x, x) -> i(a, b) g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) DependencyGraphProof (UPPER BOUND(ID)) The following rules are not reachable from basic terms in the dependency graph and can be removed: g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y)))))) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, 1). The TRS R consists of the following rules: i(x, x) -> i(a, b) g(x, x) -> g(a, b) h(s(f(x))) -> h(f(x)) f(s(x)) -> s(s(f(h(s(x))))) f(g(s(x), y)) -> f(g(x, s(y))) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) S is empty. Rewrite Strategy: FULL ---------------------------------------- (3) NestedDefinedSymbolProof (UPPER BOUND(ID)) The following defined symbols can occur below the 0th argument of f: h The following defined symbols can occur below the 0th argument of h: h Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: h(s(f(x))) -> h(f(x)) f(g(s(x), y)) -> f(g(x, s(y))) h(g(x, s(y))) -> h(g(s(x), y)) h(i(x, y)) -> i(i(c, h(h(y))), x) ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, 1). The TRS R consists of the following rules: i(x, x) -> i(a, b) g(x, x) -> g(a, b) f(s(x)) -> s(s(f(h(s(x))))) S is empty. Rewrite Strategy: FULL ---------------------------------------- (5) NarrowingOnBasicTermsTerminatesProof (FINISHED) Constant runtime complexity proven by termination of constructor-based narrowing. popout

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

job log

popout

actions

all output return to Runti Compl Full Rewri 10127