Runtime_Complexity_Innermost_Rewriting 2019-04-01 06.40 pair #433313795

details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	4.59639 seconds
cpu usage	14.3124
user time	13.1186
system time	1.19386
max virtual memory	1.917572E7
max residence set size	3461652.0

stage attributes

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

output

14.14/4.55	WORST_CASE(Omega(n^1), O(n^1))
14.14/4.56	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
14.14/4.56	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
14.14/4.56	
14.14/4.56	
14.14/4.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
14.14/4.56	
14.14/4.56	(0) CpxRelTRS
14.14/4.56	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 140 ms]
14.14/4.56	(2) CpxRelTRS
14.14/4.56	(3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
14.14/4.56	(4) CdtProblem
14.14/4.56	    (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (6) CdtProblem
14.14/4.56	    (7) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (8) CdtProblem
14.14/4.56	    (9) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (10) CdtProblem
14.14/4.56	    (11) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
14.14/4.56	    (12) CdtProblem
14.14/4.56	    (13) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (14) CdtProblem
14.14/4.56	    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 16 ms]
14.14/4.56	    (16) CdtProblem
14.14/4.56	    (17) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (18) BOUNDS(1, 1)
14.14/4.56	(19) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	(20) CpxRelTRS
14.14/4.56	    (21) SlicingProof [LOWER BOUND(ID), 0 ms]
14.14/4.56	    (22) CpxRelTRS
14.14/4.56	    (23) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
14.14/4.56	    (24) typed CpxTrs
14.14/4.56	    (25) OrderProof [LOWER BOUND(ID), 0 ms]
14.14/4.56	    (26) typed CpxTrs
14.14/4.56	    (27) RewriteLemmaProof [LOWER BOUND(ID), 299 ms]
14.14/4.56	    (28) BEST
14.14/4.56	        (29) proven lower bound
14.14/4.56	            (30) LowerBoundPropagationProof [FINISHED, 0 ms]
14.14/4.56	            (31) BOUNDS(n^1, INF)
14.14/4.56	        (32) typed CpxTrs
14.14/4.56	            (33) RewriteLemmaProof [LOWER BOUND(ID), 49 ms]
14.14/4.56	            (34) BOUNDS(1, INF)
14.14/4.56	
14.14/4.56	
14.14/4.56	----------------------------------------
14.14/4.56	
14.14/4.56	(0)
14.14/4.56	Obligation:
14.14/4.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
14.14/4.56	
14.14/4.56	
14.14/4.56	The TRS R consists of the following rules:
14.14/4.56	
14.14/4.56	   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
14.14/4.56	   lte(Cons(x, xs), Nil) -> False
14.14/4.56	   even(Cons(x, Nil)) -> False
14.14/4.56	   even(Cons(x', Cons(x, xs))) -> even(xs)
14.14/4.56	   notEmpty(Cons(x, xs)) -> True
14.14/4.56	   notEmpty(Nil) -> False
14.14/4.56	   lte(Nil, y) -> True
14.14/4.56	   even(Nil) -> True
14.14/4.56	   goal(x, y) -> and(lte(x, y), even(x))
14.14/4.56	
14.14/4.56	The (relative) TRS S consists of the following rules:
14.14/4.56	
14.14/4.56	   and(False, False) -> False
14.14/4.56	   and(True, False) -> False
14.14/4.56	   and(False, True) -> False
14.14/4.56	   and(True, True) -> True
14.14/4.56	
14.14/4.56	Rewrite Strategy: INNERMOST
14.14/4.56	----------------------------------------
14.14/4.56	
14.14/4.56	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
14.14/4.56	proved termination of relative rules
14.14/4.56	----------------------------------------
14.14/4.56	
14.14/4.56	(2)
14.14/4.56	Obligation:
14.14/4.56	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1).
14.14/4.56	
14.14/4.56	
14.14/4.56	The TRS R consists of the following rules:
14.14/4.56	
14.14/4.56	   lte(Cons(x', xs'), Cons(x, xs)) -> lte(xs', xs)
14.14/4.56	   lte(Cons(x, xs), Nil) -> False
14.14/4.56	   even(Cons(x, Nil)) -> False
14.14/4.56	   even(Cons(x', Cons(x, xs))) -> even(xs)
14.14/4.56	   notEmpty(Cons(x, xs)) -> True
14.14/4.56	   notEmpty(Nil) -> False
14.14/4.56	   lte(Nil, y) -> True
14.14/4.56	   even(Nil) -> True
14.14/4.56	   goal(x, y) -> and(lte(x, y), even(x))
14.14/4.56	
14.14/4.56	The (relative) TRS S consists of the following rules:
14.14/4.56	
14.14/4.56	   and(False, False) -> False
14.14/4.56	   and(True, False) -> False
14.14/4.56	   and(False, True) -> False
14.14/4.56	   and(True, True) -> True

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