Runtime_Complexity_Innermost_Rewriting 2019-04-01 06.40 pair #433313907

details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	291.621 seconds
cpu usage	911.809
user time	902.231
system time	9.57826
max virtual memory	3.8213664E7
max residence set size	7781028.0

stage attributes

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

output

911.48/291.52	WORST_CASE(Omega(n^1), O(n^2))
911.48/291.54	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
911.48/291.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
911.48/291.54	
911.48/291.54	
911.48/291.54	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
911.48/291.54	
911.48/291.54	(0) CpxTRS
911.48/291.54	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
911.48/291.54	(2) CpxWeightedTrs
911.48/291.54	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
911.48/291.54	    (4) CpxTypedWeightedTrs
911.48/291.54	    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
911.48/291.54	    (6) CpxTypedWeightedCompleteTrs
911.48/291.54	    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 3 ms]
911.48/291.54	    (8) CpxRNTS
911.48/291.54	    (9) CompleteCoflocoProof [FINISHED, 38 ms]
911.48/291.54	    (10) BOUNDS(1, n^2)
911.48/291.54	(11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
911.48/291.54	(12) TRS for Loop Detection
911.48/291.54	    (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
911.48/291.54	    (14) BEST
911.48/291.54	        (15) proven lower bound
911.48/291.54	            (16) LowerBoundPropagationProof [FINISHED, 0 ms]
911.48/291.54	            (17) BOUNDS(n^1, INF)
911.48/291.54	        (18) TRS for Loop Detection
911.48/291.54	
911.48/291.54	
911.48/291.54	----------------------------------------
911.48/291.54	
911.48/291.54	(0)
911.48/291.54	Obligation:
911.48/291.54	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
911.48/291.54	
911.48/291.54	
911.48/291.54	The TRS R consists of the following rules:
911.48/291.54	
911.48/291.54	   sub(0, 0) -> 0
911.48/291.54	   sub(s(x), 0) -> s(x)
911.48/291.54	   sub(0, s(x)) -> 0
911.48/291.54	   sub(s(x), s(y)) -> sub(x, y)
911.48/291.54	   zero(nil) -> zero2(0, nil)
911.48/291.54	   zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs))
911.48/291.54	   zero2(0, nil) -> nil
911.48/291.54	   zero2(0, cons(x, xs)) -> cons(sub(x, x), zero(xs))
911.48/291.54	   zero2(s(y), nil) -> zero(nil)
911.48/291.54	   zero2(s(y), cons(x, xs)) -> zero(cons(x, xs))
911.48/291.54	
911.48/291.54	S is empty.
911.48/291.54	Rewrite Strategy: INNERMOST
911.48/291.54	----------------------------------------
911.48/291.54	
911.48/291.54	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
911.48/291.54	Transformed relative TRS to weighted TRS
911.48/291.54	----------------------------------------
911.48/291.54	
911.48/291.54	(2)
911.48/291.54	Obligation:
911.48/291.54	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).
911.48/291.54	
911.48/291.54	
911.48/291.54	The TRS R consists of the following rules:
911.48/291.54	
911.48/291.54	   sub(0, 0) -> 0 [1]
911.48/291.54	   sub(s(x), 0) -> s(x) [1]
911.48/291.54	   sub(0, s(x)) -> 0 [1]
911.48/291.54	   sub(s(x), s(y)) -> sub(x, y) [1]
911.48/291.54	   zero(nil) -> zero2(0, nil) [1]
911.48/291.54	   zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) [1]
911.48/291.54	   zero2(0, nil) -> nil [1]
911.48/291.54	   zero2(0, cons(x, xs)) -> cons(sub(x, x), zero(xs)) [1]
911.48/291.54	   zero2(s(y), nil) -> zero(nil) [1]
911.48/291.54	   zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) [1]
911.48/291.54	
911.48/291.54	Rewrite Strategy: INNERMOST
911.48/291.54	----------------------------------------
911.48/291.54	
911.48/291.54	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
911.48/291.54	Infered types.
911.48/291.54	----------------------------------------
911.48/291.54	
911.48/291.54	(4)
911.48/291.54	Obligation:
911.48/291.54	Runtime Complexity Weighted TRS with Types.
911.48/291.54	The TRS R consists of the following rules:
911.48/291.54	
911.48/291.54	   sub(0, 0) -> 0 [1]
911.48/291.54	   sub(s(x), 0) -> s(x) [1]
911.48/291.54	   sub(0, s(x)) -> 0 [1]
911.48/291.54	   sub(s(x), s(y)) -> sub(x, y) [1]
911.48/291.54	   zero(nil) -> zero2(0, nil) [1]
911.48/291.54	   zero(cons(x, xs)) -> zero2(sub(x, x), cons(x, xs)) [1]
911.48/291.54	   zero2(0, nil) -> nil [1]
911.48/291.54	   zero2(0, cons(x, xs)) -> cons(sub(x, x), zero(xs)) [1]
911.48/291.54	   zero2(s(y), nil) -> zero(nil) [1]
911.48/291.54	   zero2(s(y), cons(x, xs)) -> zero(cons(x, xs)) [1]
911.48/291.54	
911.48/291.54	The TRS has the following type information:
911.48/291.54	sub :: 0:s -> 0:s -> 0:s
911.48/291.54	0 :: 0:s

popout

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

job log

popout

actions all output return to Runtime_Complexity_Innermost_Rewriting 2019-04-01 06.40