5.67/2.30	WORST_CASE(Omega(n^1), O(n^1))
6.04/2.31	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.04/2.31	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.04/2.31	
6.04/2.31	
6.04/2.31	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
6.04/2.31	
6.04/2.31	(0) CpxTRS
6.04/2.31	(1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
6.04/2.31	(2) CpxTRS
6.04/2.31	    (3) CpxTrsMatchBoundsTAProof [FINISHED, 0 ms]
6.04/2.31	    (4) BOUNDS(1, n^1)
6.04/2.31	(5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
6.04/2.31	(6) CpxTRS
6.04/2.31	    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
6.04/2.31	    (8) typed CpxTrs
6.04/2.31	    (9) OrderProof [LOWER BOUND(ID), 0 ms]
6.04/2.31	    (10) typed CpxTrs
6.04/2.31	    (11) RewriteLemmaProof [LOWER BOUND(ID), 291 ms]
6.04/2.31	    (12) proven lower bound
6.04/2.31	    (13) LowerBoundPropagationProof [FINISHED, 0 ms]
6.04/2.31	    (14) BOUNDS(n^1, INF)
6.04/2.31	
6.04/2.31	
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(0)
6.04/2.31	Obligation:
6.04/2.31	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
6.04/2.31	
6.04/2.31	
6.04/2.31	The TRS R consists of the following rules:
6.04/2.31	
6.04/2.31	   f(x, a) -> x
6.04/2.31	   f(x, g(y)) -> f(g(x), y)
6.04/2.31	
6.04/2.31	S is empty.
6.04/2.31	Rewrite Strategy: INNERMOST
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(1) RelTrsToTrsProof (UPPER BOUND(ID))
6.04/2.31	transformed relative TRS to TRS
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(2)
6.04/2.31	Obligation:
6.04/2.31	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
6.04/2.31	
6.04/2.31	
6.04/2.31	The TRS R consists of the following rules:
6.04/2.31	
6.04/2.31	   f(x, a) -> x
6.04/2.31	   f(x, g(y)) -> f(g(x), y)
6.04/2.31	
6.04/2.31	S is empty.
6.04/2.31	Rewrite Strategy: INNERMOST
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(3) CpxTrsMatchBoundsTAProof (FINISHED)
6.04/2.31	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 1. 
6.04/2.31	
6.04/2.31	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
6.04/2.31	final states : [1]
6.04/2.31	transitions: 
6.04/2.31	a0() -> 0
6.04/2.31	g0(0) -> 0
6.04/2.31	f0(0, 0) -> 1
6.04/2.31	g1(0) -> 2
6.04/2.31	f1(2, 0) -> 1
6.04/2.31	g1(2) -> 2
6.04/2.31	0 -> 1
6.04/2.31	2 -> 1
6.04/2.31	
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(4)
6.04/2.31	BOUNDS(1, n^1)
6.04/2.31	
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(5) RenamingProof (BOTH BOUNDS(ID, ID))
6.04/2.31	Renamed function symbols to avoid clashes with predefined symbol.
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(6)
6.04/2.31	Obligation:
6.04/2.31	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
6.04/2.31	
6.04/2.31	
6.04/2.31	The TRS R consists of the following rules:
6.04/2.31	
6.04/2.31	   f(x, a) -> x
6.04/2.31	   f(x, g(y)) -> f(g(x), y)
6.04/2.31	
6.04/2.31	S is empty.
6.04/2.31	Rewrite Strategy: INNERMOST
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(7) TypeInferenceProof (BOTH BOUNDS(ID, ID))
6.04/2.31	Infered types.
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(8)
6.04/2.31	Obligation:
6.04/2.31	Innermost TRS:
6.04/2.31	Rules:
6.04/2.31	f(x, a) -> x
6.04/2.31	f(x, g(y)) -> f(g(x), y)
6.04/2.31	
6.04/2.31	Types:
6.04/2.31	f :: a:g -> a:g -> a:g
6.04/2.31	a :: a:g
6.04/2.31	g :: a:g -> a:g
6.04/2.31	hole_a:g1_0 :: a:g
6.04/2.31	gen_a:g2_0 :: Nat -> a:g
6.04/2.31	
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(9) OrderProof (LOWER BOUND(ID))
6.04/2.31	Heuristically decided to analyse the following defined symbols:
6.04/2.31	f
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(10)
6.04/2.31	Obligation:
6.04/2.31	Innermost TRS:
6.04/2.31	Rules:
6.04/2.31	f(x, a) -> x
6.04/2.31	f(x, g(y)) -> f(g(x), y)
6.04/2.31	
6.04/2.31	Types:
6.04/2.31	f :: a:g -> a:g -> a:g
6.04/2.31	a :: a:g
6.04/2.31	g :: a:g -> a:g
6.04/2.31	hole_a:g1_0 :: a:g
6.04/2.31	gen_a:g2_0 :: Nat -> a:g
6.04/2.31	
6.04/2.31	
6.04/2.31	Generator Equations:
6.04/2.31	gen_a:g2_0(0) <=> a
6.04/2.31	gen_a:g2_0(+(x, 1)) <=> g(gen_a:g2_0(x))
6.04/2.31	
6.04/2.31	
6.04/2.31	The following defined symbols remain to be analysed:
6.04/2.31	f
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(11) RewriteLemmaProof (LOWER BOUND(ID))
6.04/2.31	Proved the following rewrite lemma:
6.04/2.31	f(gen_a:g2_0(a), gen_a:g2_0(n4_0)) -> gen_a:g2_0(+(n4_0, a)), rt in Omega(1 + n4_0)
6.04/2.31	
6.04/2.31	Induction Base:
6.04/2.31	f(gen_a:g2_0(a), gen_a:g2_0(0)) ->_R^Omega(1)
6.04/2.31	gen_a:g2_0(a)
6.04/2.31	
6.04/2.31	Induction Step:
6.04/2.31	f(gen_a:g2_0(a), gen_a:g2_0(+(n4_0, 1))) ->_R^Omega(1)
6.04/2.31	f(g(gen_a:g2_0(a)), gen_a:g2_0(n4_0)) ->_IH
6.04/2.31	gen_a:g2_0(+(+(a, 1), c5_0))
6.04/2.31	
6.04/2.31	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(12)
6.04/2.31	Obligation:
6.04/2.31	Proved the lower bound n^1 for the following obligation:
6.04/2.31	
6.04/2.31	Innermost TRS:
6.04/2.31	Rules:
6.04/2.31	f(x, a) -> x
6.04/2.31	f(x, g(y)) -> f(g(x), y)
6.04/2.31	
6.04/2.31	Types:
6.04/2.31	f :: a:g -> a:g -> a:g
6.04/2.31	a :: a:g
6.04/2.31	g :: a:g -> a:g
6.04/2.31	hole_a:g1_0 :: a:g
6.04/2.31	gen_a:g2_0 :: Nat -> a:g
6.04/2.31	
6.04/2.31	
6.04/2.31	Generator Equations:
6.04/2.31	gen_a:g2_0(0) <=> a
6.04/2.31	gen_a:g2_0(+(x, 1)) <=> g(gen_a:g2_0(x))
6.04/2.31	
6.04/2.31	
6.04/2.31	The following defined symbols remain to be analysed:
6.04/2.31	f
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(13) LowerBoundPropagationProof (FINISHED)
6.04/2.31	Propagated lower bound.
6.04/2.31	----------------------------------------
6.04/2.31	
6.04/2.31	(14)
6.04/2.31	BOUNDS(n^1, INF)
6.04/2.35	EOF