945.25/291.54	WORST_CASE(Omega(n^1), ?)
945.25/291.54	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
945.25/291.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
945.25/291.54	
945.25/291.54	
945.25/291.54	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
945.25/291.54	
945.25/291.54	(0) CpxTRS
945.25/291.54	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
945.25/291.54	(2) CpxTRS
945.25/291.54	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
945.25/291.54	(4) typed CpxTrs
945.25/291.54	(5) OrderProof [LOWER BOUND(ID), 0 ms]
945.25/291.54	(6) typed CpxTrs
945.25/291.54	(7) RewriteLemmaProof [LOWER BOUND(ID), 577 ms]
945.25/291.54	(8) proven lower bound
945.25/291.54	(9) LowerBoundPropagationProof [FINISHED, 0 ms]
945.25/291.54	(10) BOUNDS(n^1, INF)
945.25/291.54	
945.25/291.54	
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(0)
945.25/291.54	Obligation:
945.25/291.54	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
945.25/291.54	
945.25/291.54	
945.25/291.54	The TRS R consists of the following rules:
945.25/291.54	
945.25/291.54	   ack(0, y) -> s(y)
945.25/291.54	   ack(s(x), 0) -> ack(x, s(0))
945.25/291.54	   ack(s(x), s(y)) -> ack(x, ack(s(x), y))
945.25/291.54	
945.25/291.54	S is empty.
945.25/291.54	Rewrite Strategy: INNERMOST
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(1) RenamingProof (BOTH BOUNDS(ID, ID))
945.25/291.54	Renamed function symbols to avoid clashes with predefined symbol.
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(2)
945.25/291.54	Obligation:
945.25/291.54	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
945.25/291.54	
945.25/291.54	
945.25/291.54	The TRS R consists of the following rules:
945.25/291.54	
945.25/291.54	   ack(0', y) -> s(y)
945.25/291.54	   ack(s(x), 0') -> ack(x, s(0'))
945.25/291.54	   ack(s(x), s(y)) -> ack(x, ack(s(x), y))
945.25/291.54	
945.25/291.54	S is empty.
945.25/291.54	Rewrite Strategy: INNERMOST
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
945.25/291.54	Infered types.
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(4)
945.25/291.54	Obligation:
945.25/291.54	Innermost TRS:
945.25/291.54	Rules:
945.25/291.54	ack(0', y) -> s(y)
945.25/291.54	ack(s(x), 0') -> ack(x, s(0'))
945.25/291.54	ack(s(x), s(y)) -> ack(x, ack(s(x), y))
945.25/291.54	
945.25/291.54	Types:
945.25/291.54	ack :: 0':s -> 0':s -> 0':s
945.25/291.54	0' :: 0':s
945.25/291.54	s :: 0':s -> 0':s
945.25/291.54	hole_0':s1_0 :: 0':s
945.25/291.54	gen_0':s2_0 :: Nat -> 0':s
945.25/291.54	
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(5) OrderProof (LOWER BOUND(ID))
945.25/291.54	Heuristically decided to analyse the following defined symbols:
945.25/291.54	ack
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(6)
945.25/291.54	Obligation:
945.25/291.54	Innermost TRS:
945.25/291.54	Rules:
945.25/291.54	ack(0', y) -> s(y)
945.25/291.54	ack(s(x), 0') -> ack(x, s(0'))
945.25/291.54	ack(s(x), s(y)) -> ack(x, ack(s(x), y))
945.25/291.54	
945.25/291.54	Types:
945.25/291.54	ack :: 0':s -> 0':s -> 0':s
945.25/291.54	0' :: 0':s
945.25/291.54	s :: 0':s -> 0':s
945.25/291.54	hole_0':s1_0 :: 0':s
945.25/291.54	gen_0':s2_0 :: Nat -> 0':s
945.25/291.54	
945.25/291.54	
945.25/291.54	Generator Equations:
945.25/291.54	gen_0':s2_0(0) <=> 0'
945.25/291.54	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
945.25/291.54	
945.25/291.54	
945.25/291.54	The following defined symbols remain to be analysed:
945.25/291.54	ack
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(7) RewriteLemmaProof (LOWER BOUND(ID))
945.25/291.54	Proved the following rewrite lemma:
945.25/291.54	ack(gen_0':s2_0(1), gen_0':s2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0)
945.25/291.54	
945.25/291.54	Induction Base:
945.25/291.54	ack(gen_0':s2_0(1), gen_0':s2_0(+(1, 0)))
945.25/291.54	
945.25/291.54	Induction Step:
945.25/291.54	ack(gen_0':s2_0(1), gen_0':s2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1)
945.25/291.54	ack(gen_0':s2_0(0), ack(s(gen_0':s2_0(0)), gen_0':s2_0(+(1, n4_0)))) ->_IH
945.25/291.54	ack(gen_0':s2_0(0), *3_0)
945.25/291.54	
945.25/291.54	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(8)
945.25/291.54	Obligation:
945.25/291.54	Proved the lower bound n^1 for the following obligation:
945.25/291.54	
945.25/291.54	Innermost TRS:
945.25/291.54	Rules:
945.25/291.54	ack(0', y) -> s(y)
945.25/291.54	ack(s(x), 0') -> ack(x, s(0'))
945.25/291.54	ack(s(x), s(y)) -> ack(x, ack(s(x), y))
945.25/291.54	
945.25/291.54	Types:
945.25/291.54	ack :: 0':s -> 0':s -> 0':s
945.25/291.54	0' :: 0':s
945.25/291.54	s :: 0':s -> 0':s
945.25/291.54	hole_0':s1_0 :: 0':s
945.25/291.54	gen_0':s2_0 :: Nat -> 0':s
945.25/291.54	
945.25/291.54	
945.25/291.54	Generator Equations:
945.25/291.54	gen_0':s2_0(0) <=> 0'
945.25/291.54	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
945.25/291.54	
945.25/291.54	
945.25/291.54	The following defined symbols remain to be analysed:
945.25/291.54	ack
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(9) LowerBoundPropagationProof (FINISHED)
945.25/291.54	Propagated lower bound.
945.25/291.54	----------------------------------------
945.25/291.54	
945.25/291.54	(10)
945.25/291.54	BOUNDS(n^1, INF)
945.48/291.58	EOF