22.28/6.55	WORST_CASE(Omega(n^1), O(n^1))
22.28/6.56	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
22.28/6.56	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
22.28/6.56	
22.28/6.56	
22.28/6.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
22.28/6.56	
22.28/6.56	(0) CpxTRS
22.28/6.56	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
22.28/6.56	(2) CpxTRS
22.28/6.56	    (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
22.28/6.56	    (4) CpxTRS
22.28/6.56	    (5) CpxTrsMatchBoundsProof [FINISHED, 0 ms]
22.28/6.56	    (6) BOUNDS(1, n^1)
22.28/6.56	(7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
22.28/6.56	(8) TRS for Loop Detection
22.28/6.56	    (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
22.28/6.56	    (10) BEST
22.28/6.56	        (11) proven lower bound
22.28/6.56	            (12) LowerBoundPropagationProof [FINISHED, 0 ms]
22.28/6.56	            (13) BOUNDS(n^1, INF)
22.28/6.56	        (14) TRS for Loop Detection
22.28/6.56	
22.28/6.56	
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(0)
22.28/6.56	Obligation:
22.28/6.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
22.28/6.56	
22.28/6.56	
22.28/6.56	The TRS R consists of the following rules:
22.28/6.56	
22.28/6.56	   active(f(f(a))) -> mark(f(g(f(a))))
22.28/6.56	   active(g(X)) -> g(active(X))
22.28/6.56	   g(mark(X)) -> mark(g(X))
22.28/6.56	   proper(f(X)) -> f(proper(X))
22.28/6.56	   proper(a) -> ok(a)
22.28/6.56	   proper(g(X)) -> g(proper(X))
22.28/6.56	   f(ok(X)) -> ok(f(X))
22.28/6.56	   g(ok(X)) -> ok(g(X))
22.28/6.56	   top(mark(X)) -> top(proper(X))
22.28/6.56	   top(ok(X)) -> top(active(X))
22.28/6.56	
22.28/6.56	S is empty.
22.28/6.56	Rewrite Strategy: FULL
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
22.28/6.56	The following defined symbols can occur below the 0th argument of top: proper, active
22.28/6.56	The following defined symbols can occur below the 0th argument of proper: proper, active
22.28/6.56	The following defined symbols can occur below the 0th argument of active: proper, active
22.28/6.56	
22.28/6.56	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
22.28/6.56	active(f(f(a))) -> mark(f(g(f(a))))
22.28/6.56	active(g(X)) -> g(active(X))
22.28/6.56	proper(f(X)) -> f(proper(X))
22.28/6.56	proper(g(X)) -> g(proper(X))
22.28/6.56	
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(2)
22.28/6.56	Obligation:
22.28/6.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
22.28/6.56	
22.28/6.56	
22.28/6.56	The TRS R consists of the following rules:
22.28/6.56	
22.28/6.56	   g(mark(X)) -> mark(g(X))
22.28/6.56	   proper(a) -> ok(a)
22.28/6.56	   f(ok(X)) -> ok(f(X))
22.28/6.56	   g(ok(X)) -> ok(g(X))
22.28/6.56	   top(mark(X)) -> top(proper(X))
22.28/6.56	   top(ok(X)) -> top(active(X))
22.28/6.56	
22.28/6.56	S is empty.
22.28/6.56	Rewrite Strategy: FULL
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(3) RelTrsToTrsProof (UPPER BOUND(ID))
22.28/6.56	transformed relative TRS to TRS
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(4)
22.28/6.56	Obligation:
22.28/6.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
22.28/6.56	
22.28/6.56	
22.28/6.56	The TRS R consists of the following rules:
22.28/6.56	
22.28/6.56	   g(mark(X)) -> mark(g(X))
22.28/6.56	   proper(a) -> ok(a)
22.28/6.56	   f(ok(X)) -> ok(f(X))
22.28/6.56	   g(ok(X)) -> ok(g(X))
22.28/6.56	   top(mark(X)) -> top(proper(X))
22.28/6.56	   top(ok(X)) -> top(active(X))
22.28/6.56	
22.28/6.56	S is empty.
22.28/6.56	Rewrite Strategy: FULL
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(5) CpxTrsMatchBoundsProof (FINISHED)
22.28/6.56	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 2. 
22.28/6.56	The certificate found is represented by the following graph.
22.28/6.56	
22.28/6.56	"[20, 21, 22, 23, 24, 25, 26, 27, 28]
22.28/6.56	{(20,21,[g_1|0, proper_1|0, f_1|0, top_1|0]), (20,22,[mark_1|1]), (20,23,[ok_1|1]), (20,24,[ok_1|1]), (20,25,[ok_1|1]), (20,26,[top_1|1]), (20,27,[top_1|1]), (20,28,[top_1|2]), (21,21,[mark_1|0, a|0, ok_1|0, active_1|0]), (22,21,[g_1|1]), (22,22,[mark_1|1]), (22,23,[ok_1|1]), (23,21,[g_1|1]), (23,22,[mark_1|1]), (23,23,[ok_1|1]), (24,21,[a|1]), (25,21,[f_1|1]), (25,25,[ok_1|1]), (26,21,[proper_1|1]), (26,24,[ok_1|1]), (27,21,[active_1|1]), (28,24,[active_1|2])}"
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(6)
22.28/6.56	BOUNDS(1, n^1)
22.28/6.56	
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
22.28/6.56	Transformed a relative TRS into a decreasing-loop problem.
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(8)
22.28/6.56	Obligation:
22.28/6.56	Analyzing the following TRS for decreasing loops:
22.28/6.56	
22.28/6.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
22.28/6.56	
22.28/6.56	
22.28/6.56	The TRS R consists of the following rules:
22.28/6.56	
22.28/6.56	   active(f(f(a))) -> mark(f(g(f(a))))
22.28/6.56	   active(g(X)) -> g(active(X))
22.28/6.56	   g(mark(X)) -> mark(g(X))
22.28/6.56	   proper(f(X)) -> f(proper(X))
22.28/6.56	   proper(a) -> ok(a)
22.28/6.56	   proper(g(X)) -> g(proper(X))
22.28/6.56	   f(ok(X)) -> ok(f(X))
22.28/6.56	   g(ok(X)) -> ok(g(X))
22.28/6.56	   top(mark(X)) -> top(proper(X))
22.28/6.56	   top(ok(X)) -> top(active(X))
22.28/6.56	
22.28/6.56	S is empty.
22.28/6.56	Rewrite Strategy: FULL
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(9) DecreasingLoopProof (LOWER BOUND(ID))
22.28/6.56	The following loop(s) give(s) rise to the lower bound Omega(n^1):
22.28/6.56	
22.28/6.56	The rewrite sequence
22.28/6.56	
22.28/6.56	g(ok(X)) ->^+ ok(g(X))
22.28/6.56	
22.28/6.56	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
22.28/6.56	
22.28/6.56	The pumping substitution is [X / ok(X)].
22.28/6.56	
22.28/6.56	The result substitution is [ ].
22.28/6.56	
22.28/6.56	
22.28/6.56	
22.28/6.56	
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(10)
22.28/6.56	Complex Obligation (BEST)
22.28/6.56	
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(11)
22.28/6.56	Obligation:
22.28/6.56	Proved the lower bound n^1 for the following obligation:
22.28/6.56	
22.28/6.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
22.28/6.56	
22.28/6.56	
22.28/6.56	The TRS R consists of the following rules:
22.28/6.56	
22.28/6.56	   active(f(f(a))) -> mark(f(g(f(a))))
22.28/6.56	   active(g(X)) -> g(active(X))
22.28/6.56	   g(mark(X)) -> mark(g(X))
22.28/6.56	   proper(f(X)) -> f(proper(X))
22.28/6.56	   proper(a) -> ok(a)
22.28/6.56	   proper(g(X)) -> g(proper(X))
22.28/6.56	   f(ok(X)) -> ok(f(X))
22.28/6.56	   g(ok(X)) -> ok(g(X))
22.28/6.56	   top(mark(X)) -> top(proper(X))
22.28/6.56	   top(ok(X)) -> top(active(X))
22.28/6.56	
22.28/6.56	S is empty.
22.28/6.56	Rewrite Strategy: FULL
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(12) LowerBoundPropagationProof (FINISHED)
22.28/6.56	Propagated lower bound.
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(13)
22.28/6.56	BOUNDS(n^1, INF)
22.28/6.56	
22.28/6.56	----------------------------------------
22.28/6.56	
22.28/6.56	(14)
22.28/6.56	Obligation:
22.28/6.56	Analyzing the following TRS for decreasing loops:
22.28/6.56	
22.28/6.56	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
22.28/6.56	
22.28/6.56	
22.28/6.56	The TRS R consists of the following rules:
22.28/6.56	
22.28/6.56	   active(f(f(a))) -> mark(f(g(f(a))))
22.28/6.56	   active(g(X)) -> g(active(X))
22.28/6.56	   g(mark(X)) -> mark(g(X))
22.28/6.56	   proper(f(X)) -> f(proper(X))
22.28/6.56	   proper(a) -> ok(a)
22.28/6.56	   proper(g(X)) -> g(proper(X))
22.28/6.56	   f(ok(X)) -> ok(f(X))
22.28/6.56	   g(ok(X)) -> ok(g(X))
22.28/6.56	   top(mark(X)) -> top(proper(X))
22.28/6.56	   top(ok(X)) -> top(active(X))
22.28/6.56	
22.28/6.56	S is empty.
22.28/6.56	Rewrite Strategy: FULL
22.62/6.68	EOF