Runtime_Complexity_Full_Rewriting 2019-04-01 06.11 pair #433307932

details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	291.69 seconds
cpu usage	883.195
user time	878.743
system time	4.45194
max virtual memory	3.8450128E7
max residence set size	5355892.0

stage attributes

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

output

882.99/291.63	WORST_CASE(Omega(n^1), O(n^2))
882.99/291.64	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
882.99/291.64	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
882.99/291.64	
882.99/291.64	
882.99/291.64	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
882.99/291.64	
882.99/291.64	(0) CpxTRS
882.99/291.64	(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
882.99/291.64	(2) CpxTRS
882.99/291.64	    (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 1 ms]
882.99/291.64	    (4) CpxWeightedTrs
882.99/291.64	    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
882.99/291.64	    (6) CpxTypedWeightedTrs
882.99/291.64	    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
882.99/291.64	    (8) CpxTypedWeightedCompleteTrs
882.99/291.64	    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
882.99/291.64	    (10) CpxRNTS
882.99/291.64	    (11) CompleteCoflocoProof [FINISHED, 218 ms]
882.99/291.64	    (12) BOUNDS(1, n^2)
882.99/291.64	(13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
882.99/291.64	(14) TRS for Loop Detection
882.99/291.64	    (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
882.99/291.64	    (16) BEST
882.99/291.64	        (17) proven lower bound
882.99/291.64	            (18) LowerBoundPropagationProof [FINISHED, 0 ms]
882.99/291.64	            (19) BOUNDS(n^1, INF)
882.99/291.64	        (20) TRS for Loop Detection
882.99/291.64	
882.99/291.64	
882.99/291.64	----------------------------------------
882.99/291.64	
882.99/291.64	(0)
882.99/291.64	Obligation:
882.99/291.64	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
882.99/291.64	
882.99/291.64	
882.99/291.64	The TRS R consists of the following rules:
882.99/291.64	
882.99/291.64	   minus(x, y) -> cond(ge(x, s(y)), x, y)
882.99/291.64	   cond(false, x, y) -> 0
882.99/291.64	   cond(true, x, y) -> s(minus(x, s(y)))
882.99/291.64	   ge(u, 0) -> true
882.99/291.64	   ge(0, s(v)) -> false
882.99/291.64	   ge(s(u), s(v)) -> ge(u, v)
882.99/291.64	
882.99/291.64	S is empty.
882.99/291.64	Rewrite Strategy: FULL
882.99/291.64	----------------------------------------
882.99/291.64	
882.99/291.64	(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
882.99/291.64	Converted rc-obligation to irc-obligation.
882.99/291.64	
882.99/291.64	The duplicating contexts are:
882.99/291.64	minus([], y)
882.99/291.64	minus(x, [])
882.99/291.64	
882.99/291.64	
882.99/291.64	The defined contexts are:
882.99/291.64	cond([], x1, x2)
882.99/291.64	
882.99/291.64	
882.99/291.64	[] just represents basic- or constructor-terms in the following defined contexts:
882.99/291.64	cond([], x1, x2)
882.99/291.64	
882.99/291.64	
882.99/291.64	As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
882.99/291.64	----------------------------------------
882.99/291.64	
882.99/291.64	(2)
882.99/291.64	Obligation:
882.99/291.64	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).
882.99/291.64	
882.99/291.64	
882.99/291.64	The TRS R consists of the following rules:
882.99/291.64	
882.99/291.64	   minus(x, y) -> cond(ge(x, s(y)), x, y)
882.99/291.64	   cond(false, x, y) -> 0
882.99/291.64	   cond(true, x, y) -> s(minus(x, s(y)))
882.99/291.64	   ge(u, 0) -> true
882.99/291.64	   ge(0, s(v)) -> false
882.99/291.64	   ge(s(u), s(v)) -> ge(u, v)
882.99/291.64	
882.99/291.64	S is empty.
882.99/291.64	Rewrite Strategy: INNERMOST
882.99/291.64	----------------------------------------
882.99/291.64	
882.99/291.64	(3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
882.99/291.64	Transformed relative TRS to weighted TRS
882.99/291.64	----------------------------------------
882.99/291.64	
882.99/291.64	(4)
882.99/291.64	Obligation:
882.99/291.64	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).
882.99/291.64	
882.99/291.64	
882.99/291.64	The TRS R consists of the following rules:
882.99/291.64	
882.99/291.64	   minus(x, y) -> cond(ge(x, s(y)), x, y) [1]
882.99/291.64	   cond(false, x, y) -> 0 [1]

popout

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

job log

popout

actions all output return to Runtime_Complexity_Full_Rewriting 2019-04-01 06.11