14.46/4.76	WORST_CASE(Omega(n^1), O(n^1))
14.46/4.77	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
14.46/4.77	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
14.46/4.77	
14.46/4.77	
14.46/4.77	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
14.46/4.77	
14.46/4.77	(0) CpxTRS
14.46/4.77	(1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
14.46/4.77	(2) CdtProblem
14.46/4.77	    (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
14.46/4.77	    (4) CdtProblem
14.46/4.77	    (5) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
14.46/4.77	    (6) CdtProblem
14.46/4.77	    (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 50 ms]
14.46/4.77	    (8) CdtProblem
14.46/4.77	    (9) CdtKnowledgeProof [FINISHED, 0 ms]
14.46/4.77	    (10) BOUNDS(1, 1)
14.46/4.77	(11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
14.46/4.77	(12) CpxTRS
14.46/4.77	    (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
14.46/4.77	    (14) typed CpxTrs
14.46/4.77	    (15) OrderProof [LOWER BOUND(ID), 0 ms]
14.46/4.77	    (16) typed CpxTrs
14.46/4.77	    (17) RewriteLemmaProof [LOWER BOUND(ID), 428 ms]
14.46/4.77	    (18) BEST
14.46/4.77	        (19) proven lower bound
14.46/4.77	            (20) LowerBoundPropagationProof [FINISHED, 0 ms]
14.46/4.77	            (21) BOUNDS(n^1, INF)
14.46/4.77	        (22) typed CpxTrs
14.46/4.77	
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(0)
14.46/4.77	Obligation:
14.46/4.77	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
14.46/4.77	
14.46/4.77	
14.46/4.77	The TRS R consists of the following rules:
14.46/4.77	
14.46/4.77	   div(0, y) -> 0
14.46/4.77	   div(x, y) -> quot(x, y, y)
14.46/4.77	   quot(0, s(y), z) -> 0
14.46/4.77	   quot(s(x), s(y), z) -> quot(x, y, z)
14.46/4.77	   quot(x, 0, s(z)) -> s(div(x, s(z)))
14.46/4.77	
14.46/4.77	S is empty.
14.46/4.77	Rewrite Strategy: INNERMOST
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(1) CpxTrsToCdtProof (UPPER BOUND(ID))
14.46/4.77	Converted Cpx (relative) TRS to CDT
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(2)
14.46/4.77	Obligation:
14.46/4.77	Complexity Dependency Tuples Problem
14.46/4.77	
14.46/4.77	Rules:
14.46/4.77	   div(0, z0) -> 0
14.46/4.77	   div(z0, z1) -> quot(z0, z1, z1)
14.46/4.77	   quot(0, s(z0), z1) -> 0
14.46/4.77	   quot(s(z0), s(z1), z2) -> quot(z0, z1, z2)
14.46/4.77	   quot(z0, 0, s(z1)) -> s(div(z0, s(z1)))
14.46/4.77	Tuples:
14.46/4.77	   DIV(0, z0) -> c
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(0, s(z0), z1) -> c2
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	S tuples:
14.46/4.77	   DIV(0, z0) -> c
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(0, s(z0), z1) -> c2
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	K tuples:none
14.46/4.77	Defined Rule Symbols:   div_2, quot_3
14.46/4.77	
14.46/4.77	Defined Pair Symbols:   DIV_2, QUOT_3
14.46/4.77	
14.46/4.77	Compound Symbols:   c, c1_1, c2, c3_1, c4_1
14.46/4.77	
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
14.46/4.77	Removed 2 trailing nodes:
14.46/4.77	   QUOT(0, s(z0), z1) -> c2
14.46/4.77	   DIV(0, z0) -> c
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(4)
14.46/4.77	Obligation:
14.46/4.77	Complexity Dependency Tuples Problem
14.46/4.77	
14.46/4.77	Rules:
14.46/4.77	   div(0, z0) -> 0
14.46/4.77	   div(z0, z1) -> quot(z0, z1, z1)
14.46/4.77	   quot(0, s(z0), z1) -> 0
14.46/4.77	   quot(s(z0), s(z1), z2) -> quot(z0, z1, z2)
14.46/4.77	   quot(z0, 0, s(z1)) -> s(div(z0, s(z1)))
14.46/4.77	Tuples:
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	S tuples:
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	K tuples:none
14.46/4.77	Defined Rule Symbols:   div_2, quot_3
14.46/4.77	
14.46/4.77	Defined Pair Symbols:   DIV_2, QUOT_3
14.46/4.77	
14.46/4.77	Compound Symbols:   c1_1, c3_1, c4_1
14.46/4.77	
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(5) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
14.46/4.77	The following rules are not usable and were removed:
14.46/4.77	   div(0, z0) -> 0
14.46/4.77	   div(z0, z1) -> quot(z0, z1, z1)
14.46/4.77	   quot(0, s(z0), z1) -> 0
14.46/4.77	   quot(s(z0), s(z1), z2) -> quot(z0, z1, z2)
14.46/4.77	   quot(z0, 0, s(z1)) -> s(div(z0, s(z1)))
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(6)
14.46/4.77	Obligation:
14.46/4.77	Complexity Dependency Tuples Problem
14.46/4.77	
14.46/4.77	Rules:none
14.46/4.77	Tuples:
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	S tuples:
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	K tuples:none
14.46/4.77	Defined Rule Symbols:none
14.46/4.77	
14.46/4.77	Defined Pair Symbols:   DIV_2, QUOT_3
14.46/4.77	
14.46/4.77	Compound Symbols:   c1_1, c3_1, c4_1
14.46/4.77	
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
14.46/4.77	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	We considered the (Usable) Rules:none
14.46/4.77	And the Tuples:
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	The order we found is given by the following interpretation:
14.46/4.77	
14.46/4.77	Polynomial interpretation :
14.46/4.77	
14.46/4.77	   POL(0) = [1]
14.46/4.77	   POL(DIV(x_1, x_2)) = x_1 + x_2
14.46/4.77	   POL(QUOT(x_1, x_2, x_3)) = x_1 + x_3
14.46/4.77	   POL(c1(x_1)) = x_1
14.46/4.77	   POL(c3(x_1)) = x_1
14.46/4.77	   POL(c4(x_1)) = x_1
14.46/4.77	   POL(s(x_1)) = [1] + x_1
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(8)
14.46/4.77	Obligation:
14.46/4.77	Complexity Dependency Tuples Problem
14.46/4.77	
14.46/4.77	Rules:none
14.46/4.77	Tuples:
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	S tuples:
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	K tuples:
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	Defined Rule Symbols:none
14.46/4.77	
14.46/4.77	Defined Pair Symbols:   DIV_2, QUOT_3
14.46/4.77	
14.46/4.77	Compound Symbols:   c1_1, c3_1, c4_1
14.46/4.77	
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(9) CdtKnowledgeProof (FINISHED)
14.46/4.77	The following tuples could be moved from S to K by knowledge propagation:
14.46/4.77	   QUOT(z0, 0, s(z1)) -> c4(DIV(z0, s(z1)))
14.46/4.77	   DIV(z0, z1) -> c1(QUOT(z0, z1, z1))
14.46/4.77	   QUOT(s(z0), s(z1), z2) -> c3(QUOT(z0, z1, z2))
14.46/4.77	Now S is empty
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(10)
14.46/4.77	BOUNDS(1, 1)
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(11) RenamingProof (BOTH BOUNDS(ID, ID))
14.46/4.77	Renamed function symbols to avoid clashes with predefined symbol.
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(12)
14.46/4.77	Obligation:
14.46/4.77	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
14.46/4.77	
14.46/4.77	
14.46/4.77	The TRS R consists of the following rules:
14.46/4.77	
14.46/4.77	   div(0', y) -> 0'
14.46/4.77	   div(x, y) -> quot(x, y, y)
14.46/4.77	   quot(0', s(y), z) -> 0'
14.46/4.77	   quot(s(x), s(y), z) -> quot(x, y, z)
14.46/4.77	   quot(x, 0', s(z)) -> s(div(x, s(z)))
14.46/4.77	
14.46/4.77	S is empty.
14.46/4.77	Rewrite Strategy: INNERMOST
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(13) TypeInferenceProof (BOTH BOUNDS(ID, ID))
14.46/4.77	Infered types.
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(14)
14.46/4.77	Obligation:
14.46/4.77	Innermost TRS:
14.46/4.77	Rules:
14.46/4.77	div(0', y) -> 0'
14.46/4.77	div(x, y) -> quot(x, y, y)
14.46/4.77	quot(0', s(y), z) -> 0'
14.46/4.77	quot(s(x), s(y), z) -> quot(x, y, z)
14.46/4.77	quot(x, 0', s(z)) -> s(div(x, s(z)))
14.46/4.77	
14.46/4.77	Types:
14.46/4.77	div :: 0':s -> 0':s -> 0':s
14.46/4.77	0' :: 0':s
14.46/4.77	quot :: 0':s -> 0':s -> 0':s -> 0':s
14.46/4.77	s :: 0':s -> 0':s
14.46/4.77	hole_0':s1_0 :: 0':s
14.46/4.77	gen_0':s2_0 :: Nat -> 0':s
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(15) OrderProof (LOWER BOUND(ID))
14.46/4.77	Heuristically decided to analyse the following defined symbols:
14.46/4.77	div, quot
14.46/4.77	
14.46/4.77	They will be analysed ascendingly in the following order:
14.46/4.77	div = quot
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(16)
14.46/4.77	Obligation:
14.46/4.77	Innermost TRS:
14.46/4.77	Rules:
14.46/4.77	div(0', y) -> 0'
14.46/4.77	div(x, y) -> quot(x, y, y)
14.46/4.77	quot(0', s(y), z) -> 0'
14.46/4.77	quot(s(x), s(y), z) -> quot(x, y, z)
14.46/4.77	quot(x, 0', s(z)) -> s(div(x, s(z)))
14.46/4.77	
14.46/4.77	Types:
14.46/4.77	div :: 0':s -> 0':s -> 0':s
14.46/4.77	0' :: 0':s
14.46/4.77	quot :: 0':s -> 0':s -> 0':s -> 0':s
14.46/4.77	s :: 0':s -> 0':s
14.46/4.77	hole_0':s1_0 :: 0':s
14.46/4.77	gen_0':s2_0 :: Nat -> 0':s
14.46/4.77	
14.46/4.77	
14.46/4.77	Generator Equations:
14.46/4.77	gen_0':s2_0(0) <=> 0'
14.46/4.77	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
14.46/4.77	
14.46/4.77	
14.46/4.77	The following defined symbols remain to be analysed:
14.46/4.77	quot, div
14.46/4.77	
14.46/4.77	They will be analysed ascendingly in the following order:
14.46/4.77	div = quot
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(17) RewriteLemmaProof (LOWER BOUND(ID))
14.46/4.77	Proved the following rewrite lemma:
14.46/4.77	quot(gen_0':s2_0(n4_0), gen_0':s2_0(+(1, n4_0)), gen_0':s2_0(c)) -> gen_0':s2_0(0), rt in Omega(1 + n4_0)
14.46/4.77	
14.46/4.77	Induction Base:
14.46/4.77	quot(gen_0':s2_0(0), gen_0':s2_0(+(1, 0)), gen_0':s2_0(c)) ->_R^Omega(1)
14.46/4.77	0'
14.46/4.77	
14.46/4.77	Induction Step:
14.46/4.77	quot(gen_0':s2_0(+(n4_0, 1)), gen_0':s2_0(+(1, +(n4_0, 1))), gen_0':s2_0(c)) ->_R^Omega(1)
14.46/4.77	quot(gen_0':s2_0(n4_0), gen_0':s2_0(+(1, n4_0)), gen_0':s2_0(c)) ->_IH
14.46/4.77	gen_0':s2_0(0)
14.46/4.77	
14.46/4.77	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(18)
14.46/4.77	Complex Obligation (BEST)
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(19)
14.46/4.77	Obligation:
14.46/4.77	Proved the lower bound n^1 for the following obligation:
14.46/4.77	
14.46/4.77	Innermost TRS:
14.46/4.77	Rules:
14.46/4.77	div(0', y) -> 0'
14.46/4.77	div(x, y) -> quot(x, y, y)
14.46/4.77	quot(0', s(y), z) -> 0'
14.46/4.77	quot(s(x), s(y), z) -> quot(x, y, z)
14.46/4.77	quot(x, 0', s(z)) -> s(div(x, s(z)))
14.46/4.77	
14.46/4.77	Types:
14.46/4.77	div :: 0':s -> 0':s -> 0':s
14.46/4.77	0' :: 0':s
14.46/4.77	quot :: 0':s -> 0':s -> 0':s -> 0':s
14.46/4.77	s :: 0':s -> 0':s
14.46/4.77	hole_0':s1_0 :: 0':s
14.46/4.77	gen_0':s2_0 :: Nat -> 0':s
14.46/4.77	
14.46/4.77	
14.46/4.77	Generator Equations:
14.46/4.77	gen_0':s2_0(0) <=> 0'
14.46/4.77	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
14.46/4.77	
14.46/4.77	
14.46/4.77	The following defined symbols remain to be analysed:
14.46/4.77	quot, div
14.46/4.77	
14.46/4.77	They will be analysed ascendingly in the following order:
14.46/4.77	div = quot
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(20) LowerBoundPropagationProof (FINISHED)
14.46/4.77	Propagated lower bound.
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(21)
14.46/4.77	BOUNDS(n^1, INF)
14.46/4.77	
14.46/4.77	----------------------------------------
14.46/4.77	
14.46/4.77	(22)
14.46/4.77	Obligation:
14.46/4.77	Innermost TRS:
14.46/4.77	Rules:
14.46/4.77	div(0', y) -> 0'
14.46/4.77	div(x, y) -> quot(x, y, y)
14.46/4.77	quot(0', s(y), z) -> 0'
14.46/4.77	quot(s(x), s(y), z) -> quot(x, y, z)
14.46/4.77	quot(x, 0', s(z)) -> s(div(x, s(z)))
14.46/4.77	
14.46/4.77	Types:
14.46/4.77	div :: 0':s -> 0':s -> 0':s
14.46/4.77	0' :: 0':s
14.46/4.77	quot :: 0':s -> 0':s -> 0':s -> 0':s
14.46/4.77	s :: 0':s -> 0':s
14.46/4.77	hole_0':s1_0 :: 0':s
14.46/4.77	gen_0':s2_0 :: Nat -> 0':s
14.46/4.77	
14.46/4.77	
14.46/4.77	Lemmas:
14.46/4.77	quot(gen_0':s2_0(n4_0), gen_0':s2_0(+(1, n4_0)), gen_0':s2_0(c)) -> gen_0':s2_0(0), rt in Omega(1 + n4_0)
14.46/4.77	
14.46/4.77	
14.46/4.77	Generator Equations:
14.46/4.77	gen_0':s2_0(0) <=> 0'
14.46/4.77	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
14.46/4.77	
14.46/4.77	
14.46/4.77	The following defined symbols remain to be analysed:
14.46/4.77	div
14.46/4.77	
14.46/4.77	They will be analysed ascendingly in the following order:
14.46/4.77	div = quot
14.57/4.82	EOF