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