16.57/5.30	WORST_CASE(Omega(n^1), O(n^1))
16.87/5.35	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
16.87/5.35	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.87/5.35	
16.87/5.35	
16.87/5.35	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.87/5.35	
16.87/5.35	(0) CpxTRS
16.87/5.35	(1) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
16.87/5.35	(2) CpxTRS
16.87/5.35	    (3) CpxTrsMatchBoundsTAProof [FINISHED, 0 ms]
16.87/5.35	    (4) BOUNDS(1, n^1)
16.87/5.35	(5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
16.87/5.35	(6) CpxTRS
16.87/5.35	    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
16.87/5.35	    (8) typed CpxTrs
16.87/5.35	    (9) OrderProof [LOWER BOUND(ID), 0 ms]
16.87/5.35	    (10) typed CpxTrs
16.87/5.35	    (11) RewriteLemmaProof [LOWER BOUND(ID), 460 ms]
16.87/5.35	    (12) BEST
16.87/5.35	        (13) proven lower bound
16.87/5.35	            (14) LowerBoundPropagationProof [FINISHED, 0 ms]
16.87/5.35	            (15) BOUNDS(n^1, INF)
16.87/5.35	        (16) typed CpxTrs
16.87/5.35	
16.87/5.35	
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(0)
16.87/5.35	Obligation:
16.87/5.35	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.87/5.35	
16.87/5.35	
16.87/5.35	The TRS R consists of the following rules:
16.87/5.35	
16.87/5.35	   f(s(X)) -> f(X)
16.87/5.35	   g(cons(0, Y)) -> g(Y)
16.87/5.35	   g(cons(s(X), Y)) -> s(X)
16.87/5.35	   h(cons(X, Y)) -> h(g(cons(X, Y)))
16.87/5.35	
16.87/5.35	S is empty.
16.87/5.35	Rewrite Strategy: INNERMOST
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(1) RelTrsToTrsProof (UPPER BOUND(ID))
16.87/5.35	transformed relative TRS to TRS
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(2)
16.87/5.35	Obligation:
16.87/5.35	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
16.87/5.35	
16.87/5.35	
16.87/5.35	The TRS R consists of the following rules:
16.87/5.35	
16.87/5.35	   f(s(X)) -> f(X)
16.87/5.35	   g(cons(0, Y)) -> g(Y)
16.87/5.35	   g(cons(s(X), Y)) -> s(X)
16.87/5.35	   h(cons(X, Y)) -> h(g(cons(X, Y)))
16.87/5.35	
16.87/5.35	S is empty.
16.87/5.35	Rewrite Strategy: INNERMOST
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(3) CpxTrsMatchBoundsTAProof (FINISHED)
16.87/5.35	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. 
16.87/5.35	
16.87/5.35	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
16.87/5.35	final states : [1, 2, 3]
16.87/5.35	transitions: 
16.87/5.35	s0(0) -> 0
16.87/5.35	cons0(0, 0) -> 0
16.87/5.35	00() -> 0
16.87/5.35	f0(0) -> 1
16.87/5.35	g0(0) -> 2
16.87/5.35	h0(0) -> 3
16.87/5.35	f1(0) -> 1
16.87/5.35	g1(0) -> 2
16.87/5.35	s1(0) -> 2
16.87/5.35	cons1(0, 0) -> 5
16.87/5.35	g1(5) -> 4
16.87/5.35	h1(4) -> 3
16.87/5.35	g1(0) -> 4
16.87/5.35	s1(0) -> 4
16.87/5.35	
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(4)
16.87/5.35	BOUNDS(1, n^1)
16.87/5.35	
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(5) RenamingProof (BOTH BOUNDS(ID, ID))
16.87/5.35	Renamed function symbols to avoid clashes with predefined symbol.
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(6)
16.87/5.35	Obligation:
16.87/5.35	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
16.87/5.35	
16.87/5.35	
16.87/5.35	The TRS R consists of the following rules:
16.87/5.35	
16.87/5.35	   f(s(X)) -> f(X)
16.87/5.35	   g(cons(0', Y)) -> g(Y)
16.87/5.35	   g(cons(s(X), Y)) -> s(X)
16.87/5.35	   h(cons(X, Y)) -> h(g(cons(X, Y)))
16.87/5.35	
16.87/5.35	S is empty.
16.87/5.35	Rewrite Strategy: INNERMOST
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(7) TypeInferenceProof (BOTH BOUNDS(ID, ID))
16.87/5.35	Infered types.
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(8)
16.87/5.35	Obligation:
16.87/5.35	Innermost TRS:
16.87/5.35	Rules:
16.87/5.35	f(s(X)) -> f(X)
16.87/5.35	g(cons(0', Y)) -> g(Y)
16.87/5.35	g(cons(s(X), Y)) -> s(X)
16.87/5.35	h(cons(X, Y)) -> h(g(cons(X, Y)))
16.87/5.35	
16.87/5.35	Types:
16.87/5.35	f :: s:0':cons -> f
16.87/5.35	s :: s:0':cons -> s:0':cons
16.87/5.35	g :: s:0':cons -> s:0':cons
16.87/5.35	cons :: s:0':cons -> s:0':cons -> s:0':cons
16.87/5.35	0' :: s:0':cons
16.87/5.35	h :: s:0':cons -> h
16.87/5.35	hole_f1_0 :: f
16.87/5.35	hole_s:0':cons2_0 :: s:0':cons
16.87/5.35	hole_h3_0 :: h
16.87/5.35	gen_s:0':cons4_0 :: Nat -> s:0':cons
16.87/5.35	
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(9) OrderProof (LOWER BOUND(ID))
16.87/5.35	Heuristically decided to analyse the following defined symbols:
16.87/5.35	f, g, h
16.87/5.35	
16.87/5.35	They will be analysed ascendingly in the following order:
16.87/5.35	g < h
16.87/5.35	
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(10)
16.87/5.35	Obligation:
16.87/5.35	Innermost TRS:
16.87/5.35	Rules:
16.87/5.35	f(s(X)) -> f(X)
16.87/5.35	g(cons(0', Y)) -> g(Y)
16.87/5.35	g(cons(s(X), Y)) -> s(X)
16.87/5.35	h(cons(X, Y)) -> h(g(cons(X, Y)))
16.87/5.35	
16.87/5.35	Types:
16.87/5.35	f :: s:0':cons -> f
16.87/5.35	s :: s:0':cons -> s:0':cons
16.87/5.35	g :: s:0':cons -> s:0':cons
16.87/5.35	cons :: s:0':cons -> s:0':cons -> s:0':cons
16.87/5.35	0' :: s:0':cons
16.87/5.35	h :: s:0':cons -> h
16.87/5.35	hole_f1_0 :: f
16.87/5.35	hole_s:0':cons2_0 :: s:0':cons
16.87/5.35	hole_h3_0 :: h
16.87/5.35	gen_s:0':cons4_0 :: Nat -> s:0':cons
16.87/5.35	
16.87/5.35	
16.87/5.35	Generator Equations:
16.87/5.35	gen_s:0':cons4_0(0) <=> 0'
16.87/5.35	gen_s:0':cons4_0(+(x, 1)) <=> s(gen_s:0':cons4_0(x))
16.87/5.35	
16.87/5.35	
16.87/5.35	The following defined symbols remain to be analysed:
16.87/5.35	f, g, h
16.87/5.35	
16.87/5.35	They will be analysed ascendingly in the following order:
16.87/5.35	g < h
16.87/5.35	
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(11) RewriteLemmaProof (LOWER BOUND(ID))
16.87/5.35	Proved the following rewrite lemma:
16.87/5.35	f(gen_s:0':cons4_0(+(1, n6_0))) -> *5_0, rt in Omega(n6_0)
16.87/5.35	
16.87/5.35	Induction Base:
16.87/5.35	f(gen_s:0':cons4_0(+(1, 0)))
16.87/5.35	
16.87/5.35	Induction Step:
16.87/5.35	f(gen_s:0':cons4_0(+(1, +(n6_0, 1)))) ->_R^Omega(1)
16.87/5.35	f(gen_s:0':cons4_0(+(1, n6_0))) ->_IH
16.87/5.35	*5_0
16.87/5.35	
16.87/5.35	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(12)
16.87/5.35	Complex Obligation (BEST)
16.87/5.35	
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(13)
16.87/5.35	Obligation:
16.87/5.35	Proved the lower bound n^1 for the following obligation:
16.87/5.35	
16.87/5.35	Innermost TRS:
16.87/5.35	Rules:
16.87/5.35	f(s(X)) -> f(X)
16.87/5.35	g(cons(0', Y)) -> g(Y)
16.87/5.35	g(cons(s(X), Y)) -> s(X)
16.87/5.35	h(cons(X, Y)) -> h(g(cons(X, Y)))
16.87/5.35	
16.87/5.35	Types:
16.87/5.35	f :: s:0':cons -> f
16.87/5.35	s :: s:0':cons -> s:0':cons
16.87/5.35	g :: s:0':cons -> s:0':cons
16.87/5.35	cons :: s:0':cons -> s:0':cons -> s:0':cons
16.87/5.35	0' :: s:0':cons
16.87/5.35	h :: s:0':cons -> h
16.87/5.35	hole_f1_0 :: f
16.87/5.35	hole_s:0':cons2_0 :: s:0':cons
16.87/5.35	hole_h3_0 :: h
16.87/5.35	gen_s:0':cons4_0 :: Nat -> s:0':cons
16.87/5.35	
16.87/5.35	
16.87/5.35	Generator Equations:
16.87/5.35	gen_s:0':cons4_0(0) <=> 0'
16.87/5.35	gen_s:0':cons4_0(+(x, 1)) <=> s(gen_s:0':cons4_0(x))
16.87/5.35	
16.87/5.35	
16.87/5.35	The following defined symbols remain to be analysed:
16.87/5.35	f, g, h
16.87/5.35	
16.87/5.35	They will be analysed ascendingly in the following order:
16.87/5.35	g < h
16.87/5.35	
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(14) LowerBoundPropagationProof (FINISHED)
16.87/5.35	Propagated lower bound.
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(15)
16.87/5.35	BOUNDS(n^1, INF)
16.87/5.35	
16.87/5.35	----------------------------------------
16.87/5.35	
16.87/5.35	(16)
16.87/5.35	Obligation:
16.87/5.35	Innermost TRS:
16.87/5.35	Rules:
16.87/5.35	f(s(X)) -> f(X)
16.87/5.35	g(cons(0', Y)) -> g(Y)
16.87/5.35	g(cons(s(X), Y)) -> s(X)
16.87/5.35	h(cons(X, Y)) -> h(g(cons(X, Y)))
16.87/5.35	
16.87/5.35	Types:
16.87/5.35	f :: s:0':cons -> f
16.87/5.35	s :: s:0':cons -> s:0':cons
16.87/5.35	g :: s:0':cons -> s:0':cons
16.87/5.35	cons :: s:0':cons -> s:0':cons -> s:0':cons
16.87/5.35	0' :: s:0':cons
16.87/5.35	h :: s:0':cons -> h
16.87/5.35	hole_f1_0 :: f
16.87/5.35	hole_s:0':cons2_0 :: s:0':cons
16.87/5.35	hole_h3_0 :: h
16.87/5.35	gen_s:0':cons4_0 :: Nat -> s:0':cons
16.87/5.35	
16.87/5.35	
16.87/5.35	Lemmas:
16.87/5.35	f(gen_s:0':cons4_0(+(1, n6_0))) -> *5_0, rt in Omega(n6_0)
16.87/5.35	
16.87/5.35	
16.87/5.35	Generator Equations:
16.87/5.35	gen_s:0':cons4_0(0) <=> 0'
16.87/5.35	gen_s:0':cons4_0(+(x, 1)) <=> s(gen_s:0':cons4_0(x))
16.87/5.35	
16.87/5.35	
16.87/5.35	The following defined symbols remain to be analysed:
16.87/5.35	g, h
16.87/5.35	
16.87/5.35	They will be analysed ascendingly in the following order:
16.87/5.35	g < h
16.98/5.42	EOF