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