25.45/7.31	WORST_CASE(Omega(n^1), O(n^1))
25.52/7.33	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
25.52/7.33	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
25.52/7.33	
25.52/7.33	
25.52/7.33	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
25.52/7.33	
25.52/7.33	(0) CpxTRS
25.52/7.33	(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
25.52/7.33	(2) CpxTRS
25.52/7.33	    (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
25.52/7.33	    (4) CdtProblem
25.52/7.33	    (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
25.52/7.33	    (6) CdtProblem
25.52/7.33	    (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
25.52/7.33	    (8) CdtProblem
25.52/7.33	    (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 21 ms]
25.52/7.33	    (10) CdtProblem
25.52/7.33	    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 0 ms]
25.52/7.33	    (12) CdtProblem
25.52/7.33	    (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
25.52/7.33	    (14) BOUNDS(1, 1)
25.52/7.33	(15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
25.52/7.33	(16) CpxTRS
25.52/7.33	    (17) SlicingProof [LOWER BOUND(ID), 0 ms]
25.52/7.33	    (18) CpxTRS
25.52/7.33	    (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
25.52/7.33	    (20) typed CpxTrs
25.52/7.33	    (21) OrderProof [LOWER BOUND(ID), 0 ms]
25.52/7.33	    (22) typed CpxTrs
25.52/7.33	    (23) RewriteLemmaProof [LOWER BOUND(ID), 1924 ms]
25.52/7.33	    (24) BEST
25.52/7.33	        (25) proven lower bound
25.52/7.33	            (26) LowerBoundPropagationProof [FINISHED, 0 ms]
25.52/7.33	            (27) BOUNDS(n^1, INF)
25.52/7.33	        (28) typed CpxTrs
25.52/7.33	
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(0)
25.52/7.33	Obligation:
25.52/7.33	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
25.52/7.33	
25.52/7.33	
25.52/7.33	The TRS R consists of the following rules:
25.52/7.33	
25.52/7.33	   sum(0) -> 0
25.52/7.33	   sum(s(x)) -> +(sum(x), s(x))
25.52/7.33	   sum1(0) -> 0
25.52/7.33	   sum1(s(x)) -> s(+(sum1(x), +(x, x)))
25.52/7.33	
25.52/7.33	S is empty.
25.52/7.33	Rewrite Strategy: FULL
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
25.52/7.33	Converted rc-obligation to irc-obligation.
25.52/7.33	
25.52/7.33	As the TRS does not nest defined symbols, we have rc = irc.
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(2)
25.52/7.33	Obligation:
25.52/7.33	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
25.52/7.33	
25.52/7.33	
25.52/7.33	The TRS R consists of the following rules:
25.52/7.33	
25.52/7.33	   sum(0) -> 0
25.52/7.33	   sum(s(x)) -> +(sum(x), s(x))
25.52/7.33	   sum1(0) -> 0
25.52/7.33	   sum1(s(x)) -> s(+(sum1(x), +(x, x)))
25.52/7.33	
25.52/7.33	S is empty.
25.52/7.33	Rewrite Strategy: INNERMOST
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(3) CpxTrsToCdtProof (UPPER BOUND(ID))
25.52/7.33	Converted Cpx (relative) TRS to CDT
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(4)
25.52/7.33	Obligation:
25.52/7.33	Complexity Dependency Tuples Problem
25.52/7.33	
25.52/7.33	Rules:
25.52/7.33	   sum(0) -> 0
25.52/7.33	   sum(s(z0)) -> +(sum(z0), s(z0))
25.52/7.33	   sum1(0) -> 0
25.52/7.33	   sum1(s(z0)) -> s(+(sum1(z0), +(z0, z0)))
25.52/7.33	Tuples:
25.52/7.33	   SUM(0) -> c
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(0) -> c2
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	S tuples:
25.52/7.33	   SUM(0) -> c
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(0) -> c2
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	K tuples:none
25.52/7.33	Defined Rule Symbols:   sum_1, sum1_1
25.52/7.33	
25.52/7.33	Defined Pair Symbols:   SUM_1, SUM1_1
25.52/7.33	
25.52/7.33	Compound Symbols:   c, c1_1, c2, c3_1
25.52/7.33	
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
25.52/7.33	Removed 2 trailing nodes:
25.52/7.33	   SUM(0) -> c
25.52/7.33	   SUM1(0) -> c2
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(6)
25.52/7.33	Obligation:
25.52/7.33	Complexity Dependency Tuples Problem
25.52/7.33	
25.52/7.33	Rules:
25.52/7.33	   sum(0) -> 0
25.52/7.33	   sum(s(z0)) -> +(sum(z0), s(z0))
25.52/7.33	   sum1(0) -> 0
25.52/7.33	   sum1(s(z0)) -> s(+(sum1(z0), +(z0, z0)))
25.52/7.33	Tuples:
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	S tuples:
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	K tuples:none
25.52/7.33	Defined Rule Symbols:   sum_1, sum1_1
25.52/7.33	
25.52/7.33	Defined Pair Symbols:   SUM_1, SUM1_1
25.52/7.33	
25.52/7.33	Compound Symbols:   c1_1, c3_1
25.52/7.33	
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
25.52/7.33	The following rules are not usable and were removed:
25.52/7.33	   sum(0) -> 0
25.52/7.33	   sum(s(z0)) -> +(sum(z0), s(z0))
25.52/7.33	   sum1(0) -> 0
25.52/7.33	   sum1(s(z0)) -> s(+(sum1(z0), +(z0, z0)))
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(8)
25.52/7.33	Obligation:
25.52/7.33	Complexity Dependency Tuples Problem
25.52/7.33	
25.52/7.33	Rules:none
25.52/7.33	Tuples:
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	S tuples:
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	K tuples:none
25.52/7.33	Defined Rule Symbols:none
25.52/7.33	
25.52/7.33	Defined Pair Symbols:   SUM_1, SUM1_1
25.52/7.33	
25.52/7.33	Compound Symbols:   c1_1, c3_1
25.52/7.33	
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
25.52/7.33	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	We considered the (Usable) Rules:none
25.52/7.33	And the Tuples:
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	The order we found is given by the following interpretation:
25.52/7.33	
25.52/7.33	Polynomial interpretation :
25.52/7.33	
25.52/7.33	   POL(SUM(x_1)) = 0
25.52/7.33	   POL(SUM1(x_1)) = x_1
25.52/7.33	   POL(c1(x_1)) = x_1
25.52/7.33	   POL(c3(x_1)) = x_1
25.52/7.33	   POL(s(x_1)) = [1] + x_1
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(10)
25.52/7.33	Obligation:
25.52/7.33	Complexity Dependency Tuples Problem
25.52/7.33	
25.52/7.33	Rules:none
25.52/7.33	Tuples:
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	S tuples:
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	K tuples:
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	Defined Rule Symbols:none
25.52/7.33	
25.52/7.33	Defined Pair Symbols:   SUM_1, SUM1_1
25.52/7.33	
25.52/7.33	Compound Symbols:   c1_1, c3_1
25.52/7.33	
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
25.52/7.33	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	We considered the (Usable) Rules:none
25.52/7.33	And the Tuples:
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	The order we found is given by the following interpretation:
25.52/7.33	
25.52/7.33	Polynomial interpretation :
25.52/7.33	
25.52/7.33	   POL(SUM(x_1)) = x_1
25.52/7.33	   POL(SUM1(x_1)) = 0
25.52/7.33	   POL(c1(x_1)) = x_1
25.52/7.33	   POL(c3(x_1)) = x_1
25.52/7.33	   POL(s(x_1)) = [1] + x_1
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(12)
25.52/7.33	Obligation:
25.52/7.33	Complexity Dependency Tuples Problem
25.52/7.33	
25.52/7.33	Rules:none
25.52/7.33	Tuples:
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	S tuples:none
25.52/7.33	K tuples:
25.52/7.33	   SUM1(s(z0)) -> c3(SUM1(z0))
25.52/7.33	   SUM(s(z0)) -> c1(SUM(z0))
25.52/7.33	Defined Rule Symbols:none
25.52/7.33	
25.52/7.33	Defined Pair Symbols:   SUM_1, SUM1_1
25.52/7.33	
25.52/7.33	Compound Symbols:   c1_1, c3_1
25.52/7.33	
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(13) SIsEmptyProof (BOTH BOUNDS(ID, ID))
25.52/7.33	The set S is empty
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(14)
25.52/7.33	BOUNDS(1, 1)
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(15) RenamingProof (BOTH BOUNDS(ID, ID))
25.52/7.33	Renamed function symbols to avoid clashes with predefined symbol.
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(16)
25.52/7.33	Obligation:
25.52/7.33	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
25.52/7.33	
25.52/7.33	
25.52/7.33	The TRS R consists of the following rules:
25.52/7.33	
25.52/7.33	   sum(0') -> 0'
25.52/7.33	   sum(s(x)) -> +'(sum(x), s(x))
25.52/7.33	   sum1(0') -> 0'
25.52/7.33	   sum1(s(x)) -> s(+'(sum1(x), +'(x, x)))
25.52/7.33	
25.52/7.33	S is empty.
25.52/7.33	Rewrite Strategy: FULL
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(17) SlicingProof (LOWER BOUND(ID))
25.52/7.33	Sliced the following arguments:
25.52/7.33	+'/1
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(18)
25.52/7.33	Obligation:
25.52/7.33	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
25.52/7.33	
25.52/7.33	
25.52/7.33	The TRS R consists of the following rules:
25.52/7.33	
25.52/7.33	   sum(0') -> 0'
25.52/7.33	   sum(s(x)) -> +'(sum(x))
25.52/7.33	   sum1(0') -> 0'
25.52/7.33	   sum1(s(x)) -> s(+'(sum1(x)))
25.52/7.33	
25.52/7.33	S is empty.
25.52/7.33	Rewrite Strategy: FULL
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(19) TypeInferenceProof (BOTH BOUNDS(ID, ID))
25.52/7.33	Infered types.
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(20)
25.52/7.33	Obligation:
25.52/7.33	TRS:
25.52/7.33	Rules:
25.52/7.33	sum(0') -> 0'
25.52/7.33	sum(s(x)) -> +'(sum(x))
25.52/7.33	sum1(0') -> 0'
25.52/7.33	sum1(s(x)) -> s(+'(sum1(x)))
25.52/7.33	
25.52/7.33	Types:
25.52/7.33	sum :: 0':s:+' -> 0':s:+'
25.52/7.33	0' :: 0':s:+'
25.52/7.33	s :: 0':s:+' -> 0':s:+'
25.52/7.33	+' :: 0':s:+' -> 0':s:+'
25.52/7.33	sum1 :: 0':s:+' -> 0':s:+'
25.52/7.33	hole_0':s:+'1_0 :: 0':s:+'
25.52/7.33	gen_0':s:+'2_0 :: Nat -> 0':s:+'
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(21) OrderProof (LOWER BOUND(ID))
25.52/7.33	Heuristically decided to analyse the following defined symbols:
25.52/7.33	sum, sum1
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(22)
25.52/7.33	Obligation:
25.52/7.33	TRS:
25.52/7.33	Rules:
25.52/7.33	sum(0') -> 0'
25.52/7.33	sum(s(x)) -> +'(sum(x))
25.52/7.33	sum1(0') -> 0'
25.52/7.33	sum1(s(x)) -> s(+'(sum1(x)))
25.52/7.33	
25.52/7.33	Types:
25.52/7.33	sum :: 0':s:+' -> 0':s:+'
25.52/7.33	0' :: 0':s:+'
25.52/7.33	s :: 0':s:+' -> 0':s:+'
25.52/7.33	+' :: 0':s:+' -> 0':s:+'
25.52/7.33	sum1 :: 0':s:+' -> 0':s:+'
25.52/7.33	hole_0':s:+'1_0 :: 0':s:+'
25.52/7.33	gen_0':s:+'2_0 :: Nat -> 0':s:+'
25.52/7.33	
25.52/7.33	
25.52/7.33	Generator Equations:
25.52/7.33	gen_0':s:+'2_0(0) <=> 0'
25.52/7.33	gen_0':s:+'2_0(+(x, 1)) <=> s(gen_0':s:+'2_0(x))
25.52/7.33	
25.52/7.33	
25.52/7.33	The following defined symbols remain to be analysed:
25.52/7.33	sum, sum1
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(23) RewriteLemmaProof (LOWER BOUND(ID))
25.52/7.33	Proved the following rewrite lemma:
25.52/7.33	sum(gen_0':s:+'2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0)
25.52/7.33	
25.52/7.33	Induction Base:
25.52/7.33	sum(gen_0':s:+'2_0(+(1, 0)))
25.52/7.33	
25.52/7.33	Induction Step:
25.52/7.33	sum(gen_0':s:+'2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1)
25.52/7.33	+'(sum(gen_0':s:+'2_0(+(1, n4_0)))) ->_IH
25.52/7.33	+'(*3_0)
25.52/7.33	
25.52/7.33	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(24)
25.52/7.33	Complex Obligation (BEST)
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(25)
25.52/7.33	Obligation:
25.52/7.33	Proved the lower bound n^1 for the following obligation:
25.52/7.33	
25.52/7.33	TRS:
25.52/7.33	Rules:
25.52/7.33	sum(0') -> 0'
25.52/7.33	sum(s(x)) -> +'(sum(x))
25.52/7.33	sum1(0') -> 0'
25.52/7.33	sum1(s(x)) -> s(+'(sum1(x)))
25.52/7.33	
25.52/7.33	Types:
25.52/7.33	sum :: 0':s:+' -> 0':s:+'
25.52/7.33	0' :: 0':s:+'
25.52/7.33	s :: 0':s:+' -> 0':s:+'
25.52/7.33	+' :: 0':s:+' -> 0':s:+'
25.52/7.33	sum1 :: 0':s:+' -> 0':s:+'
25.52/7.33	hole_0':s:+'1_0 :: 0':s:+'
25.52/7.33	gen_0':s:+'2_0 :: Nat -> 0':s:+'
25.52/7.33	
25.52/7.33	
25.52/7.33	Generator Equations:
25.52/7.33	gen_0':s:+'2_0(0) <=> 0'
25.52/7.33	gen_0':s:+'2_0(+(x, 1)) <=> s(gen_0':s:+'2_0(x))
25.52/7.33	
25.52/7.33	
25.52/7.33	The following defined symbols remain to be analysed:
25.52/7.33	sum, sum1
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(26) LowerBoundPropagationProof (FINISHED)
25.52/7.33	Propagated lower bound.
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(27)
25.52/7.33	BOUNDS(n^1, INF)
25.52/7.33	
25.52/7.33	----------------------------------------
25.52/7.33	
25.52/7.33	(28)
25.52/7.33	Obligation:
25.52/7.33	TRS:
25.52/7.33	Rules:
25.52/7.33	sum(0') -> 0'
25.52/7.33	sum(s(x)) -> +'(sum(x))
25.52/7.33	sum1(0') -> 0'
25.52/7.33	sum1(s(x)) -> s(+'(sum1(x)))
25.52/7.33	
25.52/7.33	Types:
25.52/7.33	sum :: 0':s:+' -> 0':s:+'
25.52/7.33	0' :: 0':s:+'
25.52/7.33	s :: 0':s:+' -> 0':s:+'
25.52/7.33	+' :: 0':s:+' -> 0':s:+'
25.52/7.33	sum1 :: 0':s:+' -> 0':s:+'
25.52/7.33	hole_0':s:+'1_0 :: 0':s:+'
25.52/7.33	gen_0':s:+'2_0 :: Nat -> 0':s:+'
25.52/7.33	
25.52/7.33	
25.52/7.33	Lemmas:
25.52/7.33	sum(gen_0':s:+'2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0)
25.52/7.33	
25.52/7.33	
25.52/7.33	Generator Equations:
25.52/7.33	gen_0':s:+'2_0(0) <=> 0'
25.52/7.33	gen_0':s:+'2_0(+(x, 1)) <=> s(gen_0':s:+'2_0(x))
25.52/7.33	
25.52/7.33	
25.52/7.33	The following defined symbols remain to be analysed:
25.52/7.33	sum1
26.18/7.94	EOF