1130.37/291.50	WORST_CASE(Omega(n^1), ?)
1130.73/291.54	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
1130.73/291.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1130.73/291.54	
1130.73/291.54	(0) CpxTRS
1130.73/291.54	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
1130.73/291.54	(2) CpxTRS
1130.73/291.54	(3) SlicingProof [LOWER BOUND(ID), 0 ms]
1130.73/291.54	(4) CpxTRS
1130.73/291.54	(5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1130.73/291.54	(6) typed CpxTrs
1130.73/291.54	(7) OrderProof [LOWER BOUND(ID), 0 ms]
1130.73/291.54	(8) typed CpxTrs
1130.73/291.54	(9) RewriteLemmaProof [LOWER BOUND(ID), 354 ms]
1130.73/291.54	(10) BEST
1130.73/291.54	    (11) proven lower bound
1130.73/291.54	        (12) LowerBoundPropagationProof [FINISHED, 0 ms]
1130.73/291.54	        (13) BOUNDS(n^1, INF)
1130.73/291.54	    (14) typed CpxTrs
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(0)
1130.73/291.54	Obligation:
1130.73/291.54	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	The TRS R consists of the following rules:
1130.73/291.54	
1130.73/291.54	   g(A) -> A
1130.73/291.54	   g(B) -> A
1130.73/291.54	   g(B) -> B
1130.73/291.54	   g(C) -> A
1130.73/291.54	   g(C) -> B
1130.73/291.54	   g(C) -> C
1130.73/291.54	   foldf(x, nil) -> x
1130.73/291.54	   foldf(x, cons(y, z)) -> f(foldf(x, z), y)
1130.73/291.54	   f(t, x) -> f'(t, g(x))
1130.73/291.54	   f'(triple(a, b, c), C) -> triple(a, b, cons(C, c))
1130.73/291.54	   f'(triple(a, b, c), B) -> f(triple(a, b, c), A)
1130.73/291.54	   f'(triple(a, b, c), A) -> f''(foldf(triple(cons(A, a), nil, c), b))
1130.73/291.54	   f''(triple(a, b, c)) -> foldf(triple(a, b, nil), c)
1130.73/291.54	
1130.73/291.54	S is empty.
1130.73/291.54	Rewrite Strategy: FULL
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(1) RenamingProof (BOTH BOUNDS(ID, ID))
1130.73/291.54	Renamed function symbols to avoid clashes with predefined symbol.
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(2)
1130.73/291.54	Obligation:
1130.73/291.54	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	The TRS R consists of the following rules:
1130.73/291.54	
1130.73/291.54	   g(A) -> A
1130.73/291.54	   g(B) -> A
1130.73/291.54	   g(B) -> B
1130.73/291.54	   g(C) -> A
1130.73/291.54	   g(C) -> B
1130.73/291.54	   g(C) -> C
1130.73/291.54	   foldf(x, nil) -> x
1130.73/291.54	   foldf(x, cons(y, z)) -> f(foldf(x, z), y)
1130.73/291.54	   f(t, x) -> f'(t, g(x))
1130.73/291.54	   f'(triple(a, b, c), C) -> triple(a, b, cons(C, c))
1130.73/291.54	   f'(triple(a, b, c), B) -> f(triple(a, b, c), A)
1130.73/291.54	   f'(triple(a, b, c), A) -> f''(foldf(triple(cons(A, a), nil, c), b))
1130.73/291.54	   f''(triple(a, b, c)) -> foldf(triple(a, b, nil), c)
1130.73/291.54	
1130.73/291.54	S is empty.
1130.73/291.54	Rewrite Strategy: FULL
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(3) SlicingProof (LOWER BOUND(ID))
1130.73/291.54	Sliced the following arguments:
1130.73/291.54	triple/0
1130.73/291.54	
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(4)
1130.73/291.54	Obligation:
1130.73/291.54	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	The TRS R consists of the following rules:
1130.73/291.54	
1130.73/291.54	   g(A) -> A
1130.73/291.54	   g(B) -> A
1130.73/291.54	   g(B) -> B
1130.73/291.54	   g(C) -> A
1130.73/291.54	   g(C) -> B
1130.73/291.54	   g(C) -> C
1130.73/291.54	   foldf(x, nil) -> x
1130.73/291.54	   foldf(x, cons(y, z)) -> f(foldf(x, z), y)
1130.73/291.54	   f(t, x) -> f'(t, g(x))
1130.73/291.54	   f'(triple(b, c), C) -> triple(b, cons(C, c))
1130.73/291.54	   f'(triple(b, c), B) -> f(triple(b, c), A)
1130.73/291.54	   f'(triple(b, c), A) -> f''(foldf(triple(nil, c), b))
1130.73/291.54	   f''(triple(b, c)) -> foldf(triple(b, nil), c)
1130.73/291.54	
1130.73/291.54	S is empty.
1130.73/291.54	Rewrite Strategy: FULL
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(5) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1130.73/291.54	Infered types.
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(6)
1130.73/291.54	Obligation:
1130.73/291.54	TRS:
1130.73/291.54	Rules:
1130.73/291.54	g(A) -> A
1130.73/291.54	g(B) -> A
1130.73/291.54	g(B) -> B
1130.73/291.54	g(C) -> A
1130.73/291.54	g(C) -> B
1130.73/291.54	g(C) -> C
1130.73/291.54	foldf(x, nil) -> x
1130.73/291.54	foldf(x, cons(y, z)) -> f(foldf(x, z), y)
1130.73/291.54	f(t, x) -> f'(t, g(x))
1130.73/291.54	f'(triple(b, c), C) -> triple(b, cons(C, c))
1130.73/291.54	f'(triple(b, c), B) -> f(triple(b, c), A)
1130.73/291.54	f'(triple(b, c), A) -> f''(foldf(triple(nil, c), b))
1130.73/291.54	f''(triple(b, c)) -> foldf(triple(b, nil), c)
1130.73/291.54	
1130.73/291.54	Types:
1130.73/291.54	g :: A:B:C -> A:B:C
1130.73/291.54	A :: A:B:C
1130.73/291.54	B :: A:B:C
1130.73/291.54	C :: A:B:C
1130.73/291.54	foldf :: triple -> nil:cons -> triple
1130.73/291.54	nil :: nil:cons
1130.73/291.54	cons :: A:B:C -> nil:cons -> nil:cons
1130.73/291.54	f :: triple -> A:B:C -> triple
1130.73/291.54	f' :: triple -> A:B:C -> triple
1130.73/291.54	triple :: nil:cons -> nil:cons -> triple
1130.73/291.54	f'' :: triple -> triple
1130.73/291.54	hole_A:B:C1_0 :: A:B:C
1130.73/291.54	hole_triple2_0 :: triple
1130.73/291.54	hole_nil:cons3_0 :: nil:cons
1130.73/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
1130.73/291.54	
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(7) OrderProof (LOWER BOUND(ID))
1130.73/291.54	Heuristically decided to analyse the following defined symbols:
1130.73/291.54	foldf, f, f', f''
1130.73/291.54	
1130.73/291.54	They will be analysed ascendingly in the following order:
1130.73/291.54	foldf = f
1130.73/291.54	foldf = f'
1130.73/291.54	foldf = f''
1130.73/291.54	f = f'
1130.73/291.54	f = f''
1130.73/291.54	f' = f''
1130.73/291.54	
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(8)
1130.73/291.54	Obligation:
1130.73/291.54	TRS:
1130.73/291.54	Rules:
1130.73/291.54	g(A) -> A
1130.73/291.54	g(B) -> A
1130.73/291.54	g(B) -> B
1130.73/291.54	g(C) -> A
1130.73/291.54	g(C) -> B
1130.73/291.54	g(C) -> C
1130.73/291.54	foldf(x, nil) -> x
1130.73/291.54	foldf(x, cons(y, z)) -> f(foldf(x, z), y)
1130.73/291.54	f(t, x) -> f'(t, g(x))
1130.73/291.54	f'(triple(b, c), C) -> triple(b, cons(C, c))
1130.73/291.54	f'(triple(b, c), B) -> f(triple(b, c), A)
1130.73/291.54	f'(triple(b, c), A) -> f''(foldf(triple(nil, c), b))
1130.73/291.54	f''(triple(b, c)) -> foldf(triple(b, nil), c)
1130.73/291.54	
1130.73/291.54	Types:
1130.73/291.54	g :: A:B:C -> A:B:C
1130.73/291.54	A :: A:B:C
1130.73/291.54	B :: A:B:C
1130.73/291.54	C :: A:B:C
1130.73/291.54	foldf :: triple -> nil:cons -> triple
1130.73/291.54	nil :: nil:cons
1130.73/291.54	cons :: A:B:C -> nil:cons -> nil:cons
1130.73/291.54	f :: triple -> A:B:C -> triple
1130.73/291.54	f' :: triple -> A:B:C -> triple
1130.73/291.54	triple :: nil:cons -> nil:cons -> triple
1130.73/291.54	f'' :: triple -> triple
1130.73/291.54	hole_A:B:C1_0 :: A:B:C
1130.73/291.54	hole_triple2_0 :: triple
1130.73/291.54	hole_nil:cons3_0 :: nil:cons
1130.73/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	Generator Equations:
1130.73/291.54	gen_nil:cons4_0(0) <=> nil
1130.73/291.54	gen_nil:cons4_0(+(x, 1)) <=> cons(A, gen_nil:cons4_0(x))
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	The following defined symbols remain to be analysed:
1130.73/291.54	f, foldf, f', f''
1130.73/291.54	
1130.73/291.54	They will be analysed ascendingly in the following order:
1130.73/291.54	foldf = f
1130.73/291.54	foldf = f'
1130.73/291.54	foldf = f''
1130.73/291.54	f = f'
1130.73/291.54	f = f''
1130.73/291.54	f' = f''
1130.73/291.54	
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(9) RewriteLemmaProof (LOWER BOUND(ID))
1130.73/291.54	Proved the following rewrite lemma:
1130.73/291.54	foldf(triple(nil, nil), gen_nil:cons4_0(n153_0)) -> triple(gen_nil:cons4_0(0), gen_nil:cons4_0(0)), rt in Omega(1 + n153_0)
1130.73/291.54	
1130.73/291.54	Induction Base:
1130.73/291.54	foldf(triple(nil, nil), gen_nil:cons4_0(0)) ->_R^Omega(1)
1130.73/291.54	triple(nil, nil)
1130.73/291.54	
1130.73/291.54	Induction Step:
1130.73/291.54	foldf(triple(nil, nil), gen_nil:cons4_0(+(n153_0, 1))) ->_R^Omega(1)
1130.73/291.54	f(foldf(triple(nil, nil), gen_nil:cons4_0(n153_0)), A) ->_IH
1130.73/291.54	f(triple(gen_nil:cons4_0(0), gen_nil:cons4_0(0)), A) ->_R^Omega(1)
1130.73/291.54	f'(triple(gen_nil:cons4_0(0), gen_nil:cons4_0(0)), g(A)) ->_R^Omega(1)
1130.73/291.54	f'(triple(gen_nil:cons4_0(0), gen_nil:cons4_0(0)), A) ->_R^Omega(1)
1130.73/291.54	f''(foldf(triple(nil, gen_nil:cons4_0(0)), gen_nil:cons4_0(0))) ->_R^Omega(1)
1130.73/291.54	f''(triple(nil, gen_nil:cons4_0(0))) ->_R^Omega(1)
1130.73/291.54	foldf(triple(nil, nil), gen_nil:cons4_0(0)) ->_R^Omega(1)
1130.73/291.54	triple(nil, nil)
1130.73/291.54	
1130.73/291.54	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(10)
1130.73/291.54	Complex Obligation (BEST)
1130.73/291.54	
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(11)
1130.73/291.54	Obligation:
1130.73/291.54	Proved the lower bound n^1 for the following obligation:
1130.73/291.54	
1130.73/291.54	TRS:
1130.73/291.54	Rules:
1130.73/291.54	g(A) -> A
1130.73/291.54	g(B) -> A
1130.73/291.54	g(B) -> B
1130.73/291.54	g(C) -> A
1130.73/291.54	g(C) -> B
1130.73/291.54	g(C) -> C
1130.73/291.54	foldf(x, nil) -> x
1130.73/291.54	foldf(x, cons(y, z)) -> f(foldf(x, z), y)
1130.73/291.54	f(t, x) -> f'(t, g(x))
1130.73/291.54	f'(triple(b, c), C) -> triple(b, cons(C, c))
1130.73/291.54	f'(triple(b, c), B) -> f(triple(b, c), A)
1130.73/291.54	f'(triple(b, c), A) -> f''(foldf(triple(nil, c), b))
1130.73/291.54	f''(triple(b, c)) -> foldf(triple(b, nil), c)
1130.73/291.54	
1130.73/291.54	Types:
1130.73/291.54	g :: A:B:C -> A:B:C
1130.73/291.54	A :: A:B:C
1130.73/291.54	B :: A:B:C
1130.73/291.54	C :: A:B:C
1130.73/291.54	foldf :: triple -> nil:cons -> triple
1130.73/291.54	nil :: nil:cons
1130.73/291.54	cons :: A:B:C -> nil:cons -> nil:cons
1130.73/291.54	f :: triple -> A:B:C -> triple
1130.73/291.54	f' :: triple -> A:B:C -> triple
1130.73/291.54	triple :: nil:cons -> nil:cons -> triple
1130.73/291.54	f'' :: triple -> triple
1130.73/291.54	hole_A:B:C1_0 :: A:B:C
1130.73/291.54	hole_triple2_0 :: triple
1130.73/291.54	hole_nil:cons3_0 :: nil:cons
1130.73/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	Generator Equations:
1130.73/291.54	gen_nil:cons4_0(0) <=> nil
1130.73/291.54	gen_nil:cons4_0(+(x, 1)) <=> cons(A, gen_nil:cons4_0(x))
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	The following defined symbols remain to be analysed:
1130.73/291.54	foldf
1130.73/291.54	
1130.73/291.54	They will be analysed ascendingly in the following order:
1130.73/291.54	foldf = f
1130.73/291.54	foldf = f'
1130.73/291.54	foldf = f''
1130.73/291.54	f = f'
1130.73/291.54	f = f''
1130.73/291.54	f' = f''
1130.73/291.54	
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(12) LowerBoundPropagationProof (FINISHED)
1130.73/291.54	Propagated lower bound.
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(13)
1130.73/291.54	BOUNDS(n^1, INF)
1130.73/291.54	
1130.73/291.54	----------------------------------------
1130.73/291.54	
1130.73/291.54	(14)
1130.73/291.54	Obligation:
1130.73/291.54	TRS:
1130.73/291.54	Rules:
1130.73/291.54	g(A) -> A
1130.73/291.54	g(B) -> A
1130.73/291.54	g(B) -> B
1130.73/291.54	g(C) -> A
1130.73/291.54	g(C) -> B
1130.73/291.54	g(C) -> C
1130.73/291.54	foldf(x, nil) -> x
1130.73/291.54	foldf(x, cons(y, z)) -> f(foldf(x, z), y)
1130.73/291.54	f(t, x) -> f'(t, g(x))
1130.73/291.54	f'(triple(b, c), C) -> triple(b, cons(C, c))
1130.73/291.54	f'(triple(b, c), B) -> f(triple(b, c), A)
1130.73/291.54	f'(triple(b, c), A) -> f''(foldf(triple(nil, c), b))
1130.73/291.54	f''(triple(b, c)) -> foldf(triple(b, nil), c)
1130.73/291.54	
1130.73/291.54	Types:
1130.73/291.54	g :: A:B:C -> A:B:C
1130.73/291.54	A :: A:B:C
1130.73/291.54	B :: A:B:C
1130.73/291.54	C :: A:B:C
1130.73/291.54	foldf :: triple -> nil:cons -> triple
1130.73/291.54	nil :: nil:cons
1130.73/291.54	cons :: A:B:C -> nil:cons -> nil:cons
1130.73/291.54	f :: triple -> A:B:C -> triple
1130.73/291.54	f' :: triple -> A:B:C -> triple
1130.73/291.54	triple :: nil:cons -> nil:cons -> triple
1130.73/291.54	f'' :: triple -> triple
1130.73/291.54	hole_A:B:C1_0 :: A:B:C
1130.73/291.54	hole_triple2_0 :: triple
1130.73/291.54	hole_nil:cons3_0 :: nil:cons
1130.73/291.54	gen_nil:cons4_0 :: Nat -> nil:cons
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	Lemmas:
1130.73/291.54	foldf(triple(nil, nil), gen_nil:cons4_0(n153_0)) -> triple(gen_nil:cons4_0(0), gen_nil:cons4_0(0)), rt in Omega(1 + n153_0)
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	Generator Equations:
1130.73/291.54	gen_nil:cons4_0(0) <=> nil
1130.73/291.54	gen_nil:cons4_0(+(x, 1)) <=> cons(A, gen_nil:cons4_0(x))
1130.73/291.54	
1130.73/291.54	
1130.73/291.54	The following defined symbols remain to be analysed:
1130.73/291.54	f, f', f''
1130.73/291.54	
1130.73/291.54	They will be analysed ascendingly in the following order:
1130.73/291.54	foldf = f
1130.73/291.54	foldf = f'
1130.73/291.54	foldf = f''
1130.73/291.54	f = f'
1130.73/291.54	f = f''
1130.73/291.54	f' = f''
1130.87/291.63	EOF