Runtime_Complexity_Innermost_Rewriting 2019-04-01 06.40 pair #433313287

details

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

run statistics

property	value
solver	AProVE
configuration	complexity
runtime (wallclock)	291.556 seconds
cpu usage	353.521
user time	349.866
system time	3.65517
max virtual memory	3.8075584E7
max residence set size	5444352.0

stage attributes

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

output

353.42/291.49	WORST_CASE(Omega(n^1), O(n^2))
353.42/291.51	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
353.42/291.51	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
353.42/291.51	
353.42/291.51	
353.42/291.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
353.42/291.51	
353.42/291.51	(0) CpxTRS
353.42/291.51	(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
353.42/291.51	(2) CdtProblem
353.42/291.51	    (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
353.42/291.51	    (4) CdtProblem
353.42/291.51	    (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
353.42/291.51	    (6) CdtProblem
353.42/291.51	    (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 120 ms]
353.42/291.51	    (8) CdtProblem
353.42/291.51	    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 1040 ms]
353.42/291.51	    (10) CdtProblem
353.42/291.51	    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 649 ms]
353.42/291.51	    (12) CdtProblem
353.42/291.51	    (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 693 ms]
353.42/291.51	    (14) CdtProblem
353.42/291.51	    (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^2)), 554 ms]
353.42/291.51	    (16) CdtProblem
353.42/291.51	    (17) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
353.42/291.51	    (18) BOUNDS(1, 1)
353.42/291.51	(19) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
353.42/291.51	(20) TRS for Loop Detection
353.42/291.51	    (21) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
353.42/291.51	    (22) BEST
353.42/291.51	        (23) proven lower bound
353.42/291.51	            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
353.42/291.51	            (25) BOUNDS(n^1, INF)
353.42/291.51	        (26) TRS for Loop Detection
353.42/291.51	
353.42/291.51	
353.42/291.51	----------------------------------------
353.42/291.51	
353.42/291.51	(0)
353.42/291.51	Obligation:
353.42/291.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
353.42/291.51	
353.42/291.51	
353.42/291.51	The TRS R consists of the following rules:
353.42/291.51	
353.42/291.51	   lt(0, s(X)) -> true
353.42/291.51	   lt(s(X), 0) -> false
353.42/291.51	   lt(s(X), s(Y)) -> lt(X, Y)
353.42/291.51	   append(nil, Y) -> Y
353.42/291.51	   append(add(N, X), Y) -> add(N, append(X, Y))
353.42/291.51	   split(N, nil) -> pair(nil, nil)
353.42/291.51	   split(N, add(M, Y)) -> f_1(split(N, Y), N, M, Y)
353.42/291.51	   f_1(pair(X, Z), N, M, Y) -> f_2(lt(N, M), N, M, Y, X, Z)
353.42/291.51	   f_2(true, N, M, Y, X, Z) -> pair(X, add(M, Z))
353.42/291.51	   f_2(false, N, M, Y, X, Z) -> pair(add(M, X), Z)
353.42/291.51	   qsort(nil) -> nil
353.42/291.51	   qsort(add(N, X)) -> f_3(split(N, X), N, X)
353.42/291.51	   f_3(pair(Y, Z), N, X) -> append(qsort(Y), add(X, qsort(Z)))
353.42/291.51	
353.42/291.51	S is empty.
353.42/291.51	Rewrite Strategy: INNERMOST
353.42/291.51	----------------------------------------
353.42/291.51	
353.42/291.51	(1) CpxTrsToCdtProof (UPPER BOUND(ID))
353.42/291.51	Converted Cpx (relative) TRS to CDT
353.42/291.51	----------------------------------------
353.42/291.51	
353.42/291.51	(2)
353.42/291.51	Obligation:
353.42/291.51	Complexity Dependency Tuples Problem
353.42/291.51	
353.42/291.51	Rules:
353.42/291.51	   lt(0, s(z0)) -> true
353.42/291.51	   lt(s(z0), 0) -> false
353.42/291.51	   lt(s(z0), s(z1)) -> lt(z0, z1)
353.42/291.51	   append(nil, z0) -> z0
353.42/291.51	   append(add(z0, z1), z2) -> add(z0, append(z1, z2))
353.42/291.51	   split(z0, nil) -> pair(nil, nil)
353.42/291.51	   split(z0, add(z1, z2)) -> f_1(split(z0, z2), z0, z1, z2)
353.42/291.51	   f_1(pair(z0, z1), z2, z3, z4) -> f_2(lt(z2, z3), z2, z3, z4, z0, z1)
353.42/291.51	   f_2(true, z0, z1, z2, z3, z4) -> pair(z3, add(z1, z4))
353.42/291.51	   f_2(false, z0, z1, z2, z3, z4) -> pair(add(z1, z3), z4)
353.42/291.51	   qsort(nil) -> nil
353.42/291.51	   qsort(add(z0, z1)) -> f_3(split(z0, z1), z0, z1)
353.42/291.51	   f_3(pair(z0, z1), z2, z3) -> append(qsort(z0), add(z3, qsort(z1)))
353.42/291.51	Tuples:
353.42/291.51	   LT(0, s(z0)) -> c
353.42/291.51	   LT(s(z0), 0) -> c1
353.42/291.51	   LT(s(z0), s(z1)) -> c2(LT(z0, z1))
353.42/291.51	   APPEND(nil, z0) -> c3
353.42/291.51	   APPEND(add(z0, z1), z2) -> c4(APPEND(z1, z2))
353.42/291.51	   SPLIT(z0, nil) -> c5
353.42/291.51	   SPLIT(z0, add(z1, z2)) -> c6(F_1(split(z0, z2), z0, z1, z2), SPLIT(z0, z2))
353.42/291.51	   F_1(pair(z0, z1), z2, z3, z4) -> c7(F_2(lt(z2, z3), z2, z3, z4, z0, z1), LT(z2, z3))
353.42/291.51	   F_2(true, z0, z1, z2, z3, z4) -> c8
353.42/291.51	   F_2(false, z0, z1, z2, z3, z4) -> c9
353.42/291.51	   QSORT(nil) -> c10
353.42/291.51	   QSORT(add(z0, z1)) -> c11(F_3(split(z0, z1), z0, z1), SPLIT(z0, z1))
353.42/291.51	   F_3(pair(z0, z1), z2, z3) -> c12(APPEND(qsort(z0), add(z3, qsort(z1))), QSORT(z0), QSORT(z1))
353.42/291.51	S tuples:

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