3.43/1.56	WORST_CASE(?, O(1))
3.43/1.57	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
3.43/1.57	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.43/1.57	
3.43/1.57	
3.43/1.57	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, 1).
3.43/1.57	
3.43/1.57	(0) CpxTRS
3.43/1.57	(1) DependencyGraphProof [UPPER BOUND(ID), 0 ms]
3.43/1.57	(2) CpxTRS
3.43/1.57	(3) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
3.43/1.57	(4) CpxTRS
3.43/1.57	(5) NarrowingOnBasicTermsTerminatesProof [FINISHED, 0 ms]
3.43/1.57	(6) BOUNDS(1, 1)
3.43/1.57	
3.43/1.57	
3.43/1.57	----------------------------------------
3.43/1.57	
3.43/1.57	(0)
3.43/1.57	Obligation:
3.43/1.57	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, 1).
3.43/1.57	
3.43/1.57	
3.43/1.57	The TRS R consists of the following rules:
3.43/1.57	
3.43/1.57	   i(x, x) -> i(a, b)
3.43/1.57	   g(x, x) -> g(a, b)
3.43/1.57	   h(s(f(x))) -> h(f(x))
3.43/1.57	   f(s(x)) -> s(s(f(h(s(x)))))
3.43/1.57	   f(g(s(x), y)) -> f(g(x, s(y)))
3.43/1.57	   h(g(x, s(y))) -> h(g(s(x), y))
3.43/1.57	   h(i(x, y)) -> i(i(c, h(h(y))), x)
3.43/1.57	   g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y))))))
3.43/1.57	
3.43/1.57	S is empty.
3.43/1.57	Rewrite Strategy: FULL
3.43/1.57	----------------------------------------
3.43/1.57	
3.43/1.57	(1) DependencyGraphProof (UPPER BOUND(ID))
3.43/1.57	The following rules are not reachable from basic terms in the dependency graph and can be removed:
3.43/1.57	
3.43/1.57	g(a, g(x, g(b, g(a, g(x, y))))) -> g(a, g(a, g(a, g(x, g(b, g(b, y))))))
3.43/1.57	
3.43/1.57	----------------------------------------
3.43/1.57	
3.43/1.57	(2)
3.43/1.57	Obligation:
3.43/1.57	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, 1).
3.43/1.57	
3.43/1.57	
3.43/1.57	The TRS R consists of the following rules:
3.43/1.57	
3.43/1.57	   i(x, x) -> i(a, b)
3.43/1.57	   g(x, x) -> g(a, b)
3.43/1.57	   h(s(f(x))) -> h(f(x))
3.43/1.57	   f(s(x)) -> s(s(f(h(s(x)))))
3.43/1.57	   f(g(s(x), y)) -> f(g(x, s(y)))
3.43/1.57	   h(g(x, s(y))) -> h(g(s(x), y))
3.43/1.57	   h(i(x, y)) -> i(i(c, h(h(y))), x)
3.43/1.57	
3.43/1.57	S is empty.
3.43/1.57	Rewrite Strategy: FULL
3.43/1.57	----------------------------------------
3.43/1.57	
3.43/1.57	(3) NestedDefinedSymbolProof (UPPER BOUND(ID))
3.43/1.57	The following defined symbols can occur below the 0th argument of f: h
3.43/1.57	The following defined symbols can occur below the 0th argument of h: h
3.43/1.57	
3.43/1.57	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
3.43/1.57	h(s(f(x))) -> h(f(x))
3.43/1.57	f(g(s(x), y)) -> f(g(x, s(y)))
3.43/1.57	h(g(x, s(y))) -> h(g(s(x), y))
3.43/1.57	h(i(x, y)) -> i(i(c, h(h(y))), x)
3.43/1.57	
3.43/1.57	----------------------------------------
3.43/1.57	
3.43/1.57	(4)
3.43/1.57	Obligation:
3.43/1.57	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, 1).
3.43/1.57	
3.43/1.57	
3.43/1.57	The TRS R consists of the following rules:
3.43/1.57	
3.43/1.57	   i(x, x) -> i(a, b)
3.43/1.57	   g(x, x) -> g(a, b)
3.43/1.57	   f(s(x)) -> s(s(f(h(s(x)))))
3.43/1.57	
3.43/1.57	S is empty.
3.43/1.57	Rewrite Strategy: FULL
3.43/1.57	----------------------------------------
3.43/1.57	
3.43/1.57	(5) NarrowingOnBasicTermsTerminatesProof (FINISHED)
3.43/1.57	Constant runtime complexity proven by termination of constructor-based narrowing.
3.43/1.57	
3.43/1.57	The maximal most general narrowing sequences give rise to the following rewrite sequences:
3.43/1.57	
3.43/1.57	g(x0, x0) ->^* g(a, b)
3.43/1.57	
3.43/1.57	i(x0, x0) ->^* i(a, b)
3.43/1.57	
3.43/1.57	f(s(x0)) ->^* s(s(f(h(s(x0)))))
3.43/1.57	
3.43/1.57	
3.43/1.57	
3.43/1.57	
3.43/1.57	----------------------------------------
3.43/1.57	
3.43/1.57	(6)
3.43/1.57	BOUNDS(1, 1)
3.43/1.59	EOF