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