6.28/2.46	WORST_CASE(Omega(n^1), O(n^1))
6.28/2.47	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
6.28/2.47	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.28/2.47	
6.28/2.47	
6.28/2.47	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
6.28/2.47	
6.28/2.47	(0) CpxTRS
6.28/2.47	(1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
6.28/2.47	(2) CpxTRS
6.28/2.47	    (3) CpxTrsMatchBoundsProof [FINISHED, 0 ms]
6.28/2.47	    (4) BOUNDS(1, n^1)
6.28/2.47	(5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
6.28/2.47	(6) CpxTRS
6.28/2.47	    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
6.28/2.47	    (8) typed CpxTrs
6.28/2.47	    (9) OrderProof [LOWER BOUND(ID), 0 ms]
6.28/2.47	    (10) typed CpxTrs
6.28/2.47	    (11) RewriteLemmaProof [LOWER BOUND(ID), 464 ms]
6.28/2.47	    (12) proven lower bound
6.28/2.47	    (13) LowerBoundPropagationProof [FINISHED, 0 ms]
6.28/2.47	    (14) BOUNDS(n^1, INF)
6.28/2.47	
6.28/2.47	
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(0)
6.28/2.47	Obligation:
6.28/2.47	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
6.28/2.47	
6.28/2.47	
6.28/2.47	The TRS R consists of the following rules:
6.28/2.47	
6.28/2.47	   a(b(x)) -> b(a(x))
6.28/2.47	   a(c(x)) -> x
6.28/2.47	
6.28/2.47	S is empty.
6.28/2.47	Rewrite Strategy: INNERMOST
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(1) RelTrsToTrsProof (UPPER BOUND(ID))
6.28/2.47	transformed relative TRS to TRS
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(2)
6.28/2.47	Obligation:
6.28/2.47	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
6.28/2.47	
6.28/2.47	
6.28/2.47	The TRS R consists of the following rules:
6.28/2.47	
6.28/2.47	   a(b(x)) -> b(a(x))
6.28/2.47	   a(c(x)) -> x
6.28/2.47	
6.28/2.47	S is empty.
6.28/2.47	Rewrite Strategy: INNERMOST
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(3) CpxTrsMatchBoundsProof (FINISHED)
6.28/2.47	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 1. 
6.28/2.47	The certificate found is represented by the following graph.
6.28/2.47	
6.28/2.47	"[1, 2, 4]
6.28/2.47	{(1,2,[a_1|0, b_1|1, c_1|1]), (1,4,[b_1|1]), (2,2,[b_1|0, c_1|0]), (4,2,[a_1|1, b_1|1, c_1|1]), (4,4,[b_1|1])}"
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(4)
6.28/2.47	BOUNDS(1, n^1)
6.28/2.47	
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(5) RenamingProof (BOTH BOUNDS(ID, ID))
6.28/2.47	Renamed function symbols to avoid clashes with predefined symbol.
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(6)
6.28/2.47	Obligation:
6.28/2.47	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
6.28/2.47	
6.28/2.47	
6.28/2.47	The TRS R consists of the following rules:
6.28/2.47	
6.28/2.47	   a(b(x)) -> b(a(x))
6.28/2.47	   a(c(x)) -> x
6.28/2.47	
6.28/2.47	S is empty.
6.28/2.47	Rewrite Strategy: INNERMOST
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(7) TypeInferenceProof (BOTH BOUNDS(ID, ID))
6.28/2.47	Infered types.
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(8)
6.28/2.47	Obligation:
6.28/2.47	Innermost TRS:
6.28/2.47	Rules:
6.28/2.47	a(b(x)) -> b(a(x))
6.28/2.47	a(c(x)) -> x
6.28/2.47	
6.28/2.47	Types:
6.28/2.47	a :: b:c -> b:c
6.28/2.47	b :: b:c -> b:c
6.28/2.47	c :: b:c -> b:c
6.28/2.47	hole_b:c1_0 :: b:c
6.28/2.47	gen_b:c2_0 :: Nat -> b:c
6.28/2.47	
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(9) OrderProof (LOWER BOUND(ID))
6.28/2.47	Heuristically decided to analyse the following defined symbols:
6.28/2.47	a
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(10)
6.28/2.47	Obligation:
6.28/2.47	Innermost TRS:
6.28/2.47	Rules:
6.28/2.47	a(b(x)) -> b(a(x))
6.28/2.47	a(c(x)) -> x
6.28/2.47	
6.28/2.47	Types:
6.28/2.47	a :: b:c -> b:c
6.28/2.47	b :: b:c -> b:c
6.28/2.47	c :: b:c -> b:c
6.28/2.47	hole_b:c1_0 :: b:c
6.28/2.47	gen_b:c2_0 :: Nat -> b:c
6.28/2.47	
6.28/2.47	
6.28/2.47	Generator Equations:
6.28/2.47	gen_b:c2_0(0) <=> hole_b:c1_0
6.28/2.47	gen_b:c2_0(+(x, 1)) <=> b(gen_b:c2_0(x))
6.28/2.47	
6.28/2.47	
6.28/2.47	The following defined symbols remain to be analysed:
6.28/2.47	a
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(11) RewriteLemmaProof (LOWER BOUND(ID))
6.28/2.47	Proved the following rewrite lemma:
6.28/2.47	a(gen_b:c2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0)
6.28/2.47	
6.28/2.47	Induction Base:
6.28/2.47	a(gen_b:c2_0(+(1, 0)))
6.28/2.47	
6.28/2.47	Induction Step:
6.28/2.47	a(gen_b:c2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1)
6.28/2.47	b(a(gen_b:c2_0(+(1, n4_0)))) ->_IH
6.28/2.47	b(*3_0)
6.28/2.47	
6.28/2.47	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(12)
6.28/2.47	Obligation:
6.28/2.47	Proved the lower bound n^1 for the following obligation:
6.28/2.47	
6.28/2.47	Innermost TRS:
6.28/2.47	Rules:
6.28/2.47	a(b(x)) -> b(a(x))
6.28/2.47	a(c(x)) -> x
6.28/2.47	
6.28/2.47	Types:
6.28/2.47	a :: b:c -> b:c
6.28/2.47	b :: b:c -> b:c
6.28/2.47	c :: b:c -> b:c
6.28/2.47	hole_b:c1_0 :: b:c
6.28/2.47	gen_b:c2_0 :: Nat -> b:c
6.28/2.47	
6.28/2.47	
6.28/2.47	Generator Equations:
6.28/2.47	gen_b:c2_0(0) <=> hole_b:c1_0
6.28/2.47	gen_b:c2_0(+(x, 1)) <=> b(gen_b:c2_0(x))
6.28/2.47	
6.28/2.47	
6.28/2.47	The following defined symbols remain to be analysed:
6.28/2.47	a
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(13) LowerBoundPropagationProof (FINISHED)
6.28/2.47	Propagated lower bound.
6.28/2.47	----------------------------------------
6.28/2.47	
6.28/2.47	(14)
6.28/2.47	BOUNDS(n^1, INF)
6.59/2.55	EOF