19.55/7.09	WORST_CASE(Omega(n^1), O(n^1))
19.55/7.10	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
19.55/7.10	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
19.55/7.10	
19.55/7.10	
19.55/7.10	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
19.55/7.10	
19.55/7.10	(0) CpxTRS
19.55/7.10	(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	(2) CpxTRS
19.55/7.10	    (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
19.55/7.10	    (4) CdtProblem
19.55/7.10	    (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	    (6) CdtProblem
19.55/7.10	    (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	    (8) CdtProblem
19.55/7.10	    (9) CdtNarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	    (10) CdtProblem
19.55/7.10	    (11) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	    (12) CdtProblem
19.55/7.10	    (13) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	    (14) CdtProblem
19.55/7.10	    (15) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms]
19.55/7.10	    (16) CdtProblem
19.55/7.10	    (17) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	    (18) CdtProblem
19.55/7.10	    (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 0 ms]
19.55/7.10	    (20) CdtProblem
19.55/7.10	    (21) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	    (22) BOUNDS(1, 1)
19.55/7.10	(23) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	(24) CpxTRS
19.55/7.10	    (25) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
19.55/7.10	    (26) typed CpxTrs
19.55/7.10	    (27) OrderProof [LOWER BOUND(ID), 0 ms]
19.55/7.10	    (28) typed CpxTrs
19.55/7.10	    (29) RewriteLemmaProof [LOWER BOUND(ID), 283 ms]
19.55/7.10	    (30) BEST
19.55/7.10	        (31) proven lower bound
19.55/7.10	            (32) LowerBoundPropagationProof [FINISHED, 0 ms]
19.55/7.10	            (33) BOUNDS(n^1, INF)
19.55/7.10	        (34) typed CpxTrs
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(0)
19.55/7.10	Obligation:
19.55/7.10	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
19.55/7.10	
19.55/7.10	
19.55/7.10	The TRS R consists of the following rules:
19.55/7.10	
19.55/7.10	   +(X, 0) -> X
19.55/7.10	   +(X, s(Y)) -> s(+(X, Y))
19.55/7.10	   f(0, s(0), X) -> f(X, +(X, X), X)
19.55/7.10	   g(X, Y) -> X
19.55/7.10	   g(X, Y) -> Y
19.55/7.10	
19.55/7.10	S is empty.
19.55/7.10	Rewrite Strategy: FULL
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
19.55/7.10	Converted rc-obligation to irc-obligation.
19.55/7.10	
19.55/7.10	The duplicating contexts are:
19.55/7.10	f(0, s(0), [])
19.55/7.10	
19.55/7.10	
19.55/7.10	The defined contexts are:
19.55/7.10	f(x0, [], x2)
19.55/7.10	
19.55/7.10	
19.55/7.10	As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(2)
19.55/7.10	Obligation:
19.55/7.10	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
19.55/7.10	
19.55/7.10	
19.55/7.10	The TRS R consists of the following rules:
19.55/7.10	
19.55/7.10	   +(X, 0) -> X
19.55/7.10	   +(X, s(Y)) -> s(+(X, Y))
19.55/7.10	   f(0, s(0), X) -> f(X, +(X, X), X)
19.55/7.10	   g(X, Y) -> X
19.55/7.10	   g(X, Y) -> Y
19.55/7.10	
19.55/7.10	S is empty.
19.55/7.10	Rewrite Strategy: INNERMOST
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(3) CpxTrsToCdtProof (UPPER BOUND(ID))
19.55/7.10	Converted Cpx (relative) TRS to CDT
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(4)
19.55/7.10	Obligation:
19.55/7.10	Complexity Dependency Tuples Problem
19.55/7.10	
19.55/7.10	Rules:
19.55/7.10	   +(z0, 0) -> z0
19.55/7.10	   +(z0, s(z1)) -> s(+(z0, z1))
19.55/7.10	   f(0, s(0), z0) -> f(z0, +(z0, z0), z0)
19.55/7.10	   g(z0, z1) -> z0
19.55/7.10	   g(z0, z1) -> z1
19.55/7.10	Tuples:
19.55/7.10	   +'(z0, 0) -> c
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), z0) -> c2(F(z0, +(z0, z0), z0), +'(z0, z0))
19.55/7.10	   G(z0, z1) -> c3
19.55/7.10	   G(z0, z1) -> c4
19.55/7.10	S tuples:
19.55/7.10	   +'(z0, 0) -> c
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), z0) -> c2(F(z0, +(z0, z0), z0), +'(z0, z0))
19.55/7.10	   G(z0, z1) -> c3
19.55/7.10	   G(z0, z1) -> c4
19.55/7.10	K tuples:none
19.55/7.10	Defined Rule Symbols:   +_2, f_3, g_2
19.55/7.10	
19.55/7.10	Defined Pair Symbols:   +'_2, F_3, G_2
19.55/7.10	
19.55/7.10	Compound Symbols:   c, c1_1, c2_2, c3, c4
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
19.55/7.10	Removed 3 trailing nodes:
19.55/7.10	   G(z0, z1) -> c4
19.55/7.10	   +'(z0, 0) -> c
19.55/7.10	   G(z0, z1) -> c3
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(6)
19.55/7.10	Obligation:
19.55/7.10	Complexity Dependency Tuples Problem
19.55/7.10	
19.55/7.10	Rules:
19.55/7.10	   +(z0, 0) -> z0
19.55/7.10	   +(z0, s(z1)) -> s(+(z0, z1))
19.55/7.10	   f(0, s(0), z0) -> f(z0, +(z0, z0), z0)
19.55/7.10	   g(z0, z1) -> z0
19.55/7.10	   g(z0, z1) -> z1
19.55/7.10	Tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), z0) -> c2(F(z0, +(z0, z0), z0), +'(z0, z0))
19.55/7.10	S tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), z0) -> c2(F(z0, +(z0, z0), z0), +'(z0, z0))
19.55/7.10	K tuples:none
19.55/7.10	Defined Rule Symbols:   +_2, f_3, g_2
19.55/7.10	
19.55/7.10	Defined Pair Symbols:   +'_2, F_3
19.55/7.10	
19.55/7.10	Compound Symbols:   c1_1, c2_2
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
19.55/7.10	The following rules are not usable and were removed:
19.55/7.10	   f(0, s(0), z0) -> f(z0, +(z0, z0), z0)
19.55/7.10	   g(z0, z1) -> z0
19.55/7.10	   g(z0, z1) -> z1
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(8)
19.55/7.10	Obligation:
19.55/7.10	Complexity Dependency Tuples Problem
19.55/7.10	
19.55/7.10	Rules:
19.55/7.10	   +(z0, 0) -> z0
19.55/7.10	   +(z0, s(z1)) -> s(+(z0, z1))
19.55/7.10	Tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), z0) -> c2(F(z0, +(z0, z0), z0), +'(z0, z0))
19.55/7.10	S tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), z0) -> c2(F(z0, +(z0, z0), z0), +'(z0, z0))
19.55/7.10	K tuples:none
19.55/7.10	Defined Rule Symbols:   +_2
19.55/7.10	
19.55/7.10	Defined Pair Symbols:   +'_2, F_3
19.55/7.10	
19.55/7.10	Compound Symbols:   c1_1, c2_2
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(9) CdtNarrowingProof (BOTH BOUNDS(ID, ID))
19.55/7.10	Use narrowing to replace F(0, s(0), z0) -> c2(F(z0, +(z0, z0), z0), +'(z0, z0)) by 
19.55/7.10	   F(0, s(0), 0) -> c2(F(0, 0, 0), +'(0, 0))
19.55/7.10	   F(0, s(0), s(z1)) -> c2(F(s(z1), s(+(s(z1), z1)), s(z1)), +'(s(z1), s(z1)))
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(10)
19.55/7.10	Obligation:
19.55/7.10	Complexity Dependency Tuples Problem
19.55/7.10	
19.55/7.10	Rules:
19.55/7.10	   +(z0, 0) -> z0
19.55/7.10	   +(z0, s(z1)) -> s(+(z0, z1))
19.55/7.10	Tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), 0) -> c2(F(0, 0, 0), +'(0, 0))
19.55/7.10	   F(0, s(0), s(z1)) -> c2(F(s(z1), s(+(s(z1), z1)), s(z1)), +'(s(z1), s(z1)))
19.55/7.10	S tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), 0) -> c2(F(0, 0, 0), +'(0, 0))
19.55/7.10	   F(0, s(0), s(z1)) -> c2(F(s(z1), s(+(s(z1), z1)), s(z1)), +'(s(z1), s(z1)))
19.55/7.10	K tuples:none
19.55/7.10	Defined Rule Symbols:   +_2
19.55/7.10	
19.55/7.10	Defined Pair Symbols:   +'_2, F_3
19.55/7.10	
19.55/7.10	Compound Symbols:   c1_1, c2_2
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(11) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
19.55/7.10	Removed 1 trailing nodes:
19.55/7.10	   F(0, s(0), 0) -> c2(F(0, 0, 0), +'(0, 0))
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(12)
19.55/7.10	Obligation:
19.55/7.10	Complexity Dependency Tuples Problem
19.55/7.10	
19.55/7.10	Rules:
19.55/7.10	   +(z0, 0) -> z0
19.55/7.10	   +(z0, s(z1)) -> s(+(z0, z1))
19.55/7.10	Tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), s(z1)) -> c2(F(s(z1), s(+(s(z1), z1)), s(z1)), +'(s(z1), s(z1)))
19.55/7.10	S tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), s(z1)) -> c2(F(s(z1), s(+(s(z1), z1)), s(z1)), +'(s(z1), s(z1)))
19.55/7.10	K tuples:none
19.55/7.10	Defined Rule Symbols:   +_2
19.55/7.10	
19.55/7.10	Defined Pair Symbols:   +'_2, F_3
19.55/7.10	
19.55/7.10	Compound Symbols:   c1_1, c2_2
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(13) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID))
19.55/7.10	Removed 1 trailing tuple parts
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(14)
19.55/7.10	Obligation:
19.55/7.10	Complexity Dependency Tuples Problem
19.55/7.10	
19.55/7.10	Rules:
19.55/7.10	   +(z0, 0) -> z0
19.55/7.10	   +(z0, s(z1)) -> s(+(z0, z1))
19.55/7.10	Tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), s(z1)) -> c2(+'(s(z1), s(z1)))
19.55/7.10	S tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	   F(0, s(0), s(z1)) -> c2(+'(s(z1), s(z1)))
19.55/7.10	K tuples:none
19.55/7.10	Defined Rule Symbols:   +_2
19.55/7.10	
19.55/7.10	Defined Pair Symbols:   +'_2, F_3
19.55/7.10	
19.55/7.10	Compound Symbols:   c1_1, c2_1
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(15) CdtLeafRemovalProof (ComplexityIfPolyImplication)
19.55/7.10	Removed 1 leading nodes:
19.55/7.10	   F(0, s(0), s(z1)) -> c2(+'(s(z1), s(z1)))
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(16)
19.55/7.10	Obligation:
19.55/7.10	Complexity Dependency Tuples Problem
19.55/7.10	
19.55/7.10	Rules:
19.55/7.10	   +(z0, 0) -> z0
19.55/7.10	   +(z0, s(z1)) -> s(+(z0, z1))
19.55/7.10	Tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	S tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	K tuples:none
19.55/7.10	Defined Rule Symbols:   +_2
19.55/7.10	
19.55/7.10	Defined Pair Symbols:   +'_2
19.55/7.10	
19.55/7.10	Compound Symbols:   c1_1
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(17) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
19.55/7.10	The following rules are not usable and were removed:
19.55/7.10	   +(z0, 0) -> z0
19.55/7.10	   +(z0, s(z1)) -> s(+(z0, z1))
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(18)
19.55/7.10	Obligation:
19.55/7.10	Complexity Dependency Tuples Problem
19.55/7.10	
19.55/7.10	Rules:none
19.55/7.10	Tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	S tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	K tuples:none
19.55/7.10	Defined Rule Symbols:none
19.55/7.10	
19.55/7.10	Defined Pair Symbols:   +'_2
19.55/7.10	
19.55/7.10	Compound Symbols:   c1_1
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
19.55/7.10	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	We considered the (Usable) Rules:none
19.55/7.10	And the Tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	The order we found is given by the following interpretation:
19.55/7.10	
19.55/7.10	Polynomial interpretation :
19.55/7.10	
19.55/7.10	   POL(+'(x_1, x_2)) = x_2
19.55/7.10	   POL(c1(x_1)) = x_1
19.55/7.10	   POL(s(x_1)) = [1] + x_1
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(20)
19.55/7.10	Obligation:
19.55/7.10	Complexity Dependency Tuples Problem
19.55/7.10	
19.55/7.10	Rules:none
19.55/7.10	Tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	S tuples:none
19.55/7.10	K tuples:
19.55/7.10	   +'(z0, s(z1)) -> c1(+'(z0, z1))
19.55/7.10	Defined Rule Symbols:none
19.55/7.10	
19.55/7.10	Defined Pair Symbols:   +'_2
19.55/7.10	
19.55/7.10	Compound Symbols:   c1_1
19.55/7.10	
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(21) SIsEmptyProof (BOTH BOUNDS(ID, ID))
19.55/7.10	The set S is empty
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(22)
19.55/7.10	BOUNDS(1, 1)
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(23) RenamingProof (BOTH BOUNDS(ID, ID))
19.55/7.10	Renamed function symbols to avoid clashes with predefined symbol.
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(24)
19.55/7.10	Obligation:
19.55/7.10	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
19.55/7.10	
19.55/7.10	
19.55/7.10	The TRS R consists of the following rules:
19.55/7.10	
19.55/7.10	   +'(X, 0') -> X
19.55/7.10	   +'(X, s(Y)) -> s(+'(X, Y))
19.55/7.10	   f(0', s(0'), X) -> f(X, +'(X, X), X)
19.55/7.10	   g(X, Y) -> X
19.55/7.10	   g(X, Y) -> Y
19.55/7.10	
19.55/7.10	S is empty.
19.55/7.10	Rewrite Strategy: FULL
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(25) TypeInferenceProof (BOTH BOUNDS(ID, ID))
19.55/7.10	Infered types.
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(26)
19.55/7.10	Obligation:
19.55/7.10	TRS:
19.55/7.10	Rules:
19.55/7.10	+'(X, 0') -> X
19.55/7.10	+'(X, s(Y)) -> s(+'(X, Y))
19.55/7.10	f(0', s(0'), X) -> f(X, +'(X, X), X)
19.55/7.10	g(X, Y) -> X
19.55/7.10	g(X, Y) -> Y
19.55/7.10	
19.55/7.10	Types:
19.55/7.10	+' :: 0':s -> 0':s -> 0':s
19.55/7.10	0' :: 0':s
19.55/7.10	s :: 0':s -> 0':s
19.55/7.10	f :: 0':s -> 0':s -> 0':s -> f
19.55/7.10	g :: g -> g -> g
19.55/7.10	hole_0':s1_0 :: 0':s
19.55/7.10	hole_f2_0 :: f
19.55/7.10	hole_g3_0 :: g
19.55/7.10	gen_0':s4_0 :: Nat -> 0':s
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(27) OrderProof (LOWER BOUND(ID))
19.55/7.10	Heuristically decided to analyse the following defined symbols:
19.55/7.10	+', f
19.55/7.10	
19.55/7.10	They will be analysed ascendingly in the following order:
19.55/7.10	+' < f
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(28)
19.55/7.10	Obligation:
19.55/7.10	TRS:
19.55/7.10	Rules:
19.55/7.10	+'(X, 0') -> X
19.55/7.10	+'(X, s(Y)) -> s(+'(X, Y))
19.55/7.10	f(0', s(0'), X) -> f(X, +'(X, X), X)
19.55/7.10	g(X, Y) -> X
19.55/7.10	g(X, Y) -> Y
19.55/7.10	
19.55/7.10	Types:
19.55/7.10	+' :: 0':s -> 0':s -> 0':s
19.55/7.10	0' :: 0':s
19.55/7.10	s :: 0':s -> 0':s
19.55/7.10	f :: 0':s -> 0':s -> 0':s -> f
19.55/7.10	g :: g -> g -> g
19.55/7.10	hole_0':s1_0 :: 0':s
19.55/7.10	hole_f2_0 :: f
19.55/7.10	hole_g3_0 :: g
19.55/7.10	gen_0':s4_0 :: Nat -> 0':s
19.55/7.10	
19.55/7.10	
19.55/7.10	Generator Equations:
19.55/7.10	gen_0':s4_0(0) <=> 0'
19.55/7.10	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
19.55/7.10	
19.55/7.10	
19.55/7.10	The following defined symbols remain to be analysed:
19.55/7.10	+', f
19.55/7.10	
19.55/7.10	They will be analysed ascendingly in the following order:
19.55/7.10	+' < f
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(29) RewriteLemmaProof (LOWER BOUND(ID))
19.55/7.10	Proved the following rewrite lemma:
19.55/7.10	+'(gen_0':s4_0(a), gen_0':s4_0(n6_0)) -> gen_0':s4_0(+(n6_0, a)), rt in Omega(1 + n6_0)
19.55/7.10	
19.55/7.10	Induction Base:
19.55/7.10	+'(gen_0':s4_0(a), gen_0':s4_0(0)) ->_R^Omega(1)
19.55/7.10	gen_0':s4_0(a)
19.55/7.10	
19.55/7.10	Induction Step:
19.55/7.10	+'(gen_0':s4_0(a), gen_0':s4_0(+(n6_0, 1))) ->_R^Omega(1)
19.55/7.10	s(+'(gen_0':s4_0(a), gen_0':s4_0(n6_0))) ->_IH
19.55/7.10	s(gen_0':s4_0(+(a, c7_0)))
19.55/7.10	
19.55/7.10	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(30)
19.55/7.10	Complex Obligation (BEST)
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(31)
19.55/7.10	Obligation:
19.55/7.10	Proved the lower bound n^1 for the following obligation:
19.55/7.10	
19.55/7.10	TRS:
19.55/7.10	Rules:
19.55/7.10	+'(X, 0') -> X
19.55/7.10	+'(X, s(Y)) -> s(+'(X, Y))
19.55/7.10	f(0', s(0'), X) -> f(X, +'(X, X), X)
19.55/7.10	g(X, Y) -> X
19.55/7.10	g(X, Y) -> Y
19.55/7.10	
19.55/7.10	Types:
19.55/7.10	+' :: 0':s -> 0':s -> 0':s
19.55/7.10	0' :: 0':s
19.55/7.10	s :: 0':s -> 0':s
19.55/7.10	f :: 0':s -> 0':s -> 0':s -> f
19.55/7.10	g :: g -> g -> g
19.55/7.10	hole_0':s1_0 :: 0':s
19.55/7.10	hole_f2_0 :: f
19.55/7.10	hole_g3_0 :: g
19.55/7.10	gen_0':s4_0 :: Nat -> 0':s
19.55/7.10	
19.55/7.10	
19.55/7.10	Generator Equations:
19.55/7.10	gen_0':s4_0(0) <=> 0'
19.55/7.10	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
19.55/7.10	
19.55/7.10	
19.55/7.10	The following defined symbols remain to be analysed:
19.55/7.10	+', f
19.55/7.10	
19.55/7.10	They will be analysed ascendingly in the following order:
19.55/7.10	+' < f
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(32) LowerBoundPropagationProof (FINISHED)
19.55/7.10	Propagated lower bound.
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(33)
19.55/7.10	BOUNDS(n^1, INF)
19.55/7.10	
19.55/7.10	----------------------------------------
19.55/7.10	
19.55/7.10	(34)
19.55/7.10	Obligation:
19.55/7.10	TRS:
19.55/7.10	Rules:
19.55/7.10	+'(X, 0') -> X
19.55/7.10	+'(X, s(Y)) -> s(+'(X, Y))
19.55/7.10	f(0', s(0'), X) -> f(X, +'(X, X), X)
19.55/7.10	g(X, Y) -> X
19.55/7.10	g(X, Y) -> Y
19.55/7.10	
19.55/7.10	Types:
19.55/7.10	+' :: 0':s -> 0':s -> 0':s
19.55/7.10	0' :: 0':s
19.55/7.10	s :: 0':s -> 0':s
19.55/7.10	f :: 0':s -> 0':s -> 0':s -> f
19.55/7.10	g :: g -> g -> g
19.55/7.10	hole_0':s1_0 :: 0':s
19.55/7.10	hole_f2_0 :: f
19.55/7.10	hole_g3_0 :: g
19.55/7.10	gen_0':s4_0 :: Nat -> 0':s
19.55/7.10	
19.55/7.10	
19.55/7.10	Lemmas:
19.55/7.10	+'(gen_0':s4_0(a), gen_0':s4_0(n6_0)) -> gen_0':s4_0(+(n6_0, a)), rt in Omega(1 + n6_0)
19.55/7.10	
19.55/7.10	
19.55/7.10	Generator Equations:
19.55/7.10	gen_0':s4_0(0) <=> 0'
19.55/7.10	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
19.55/7.10	
19.55/7.10	
19.55/7.10	The following defined symbols remain to be analysed:
19.55/7.10	f
19.71/10.44	EOF