1103.75/291.53	WORST_CASE(Omega(n^2), ?)
1115.56/294.51	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
1115.56/294.51	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
1115.56/294.51	
1115.56/294.51	(0) CpxTRS
1115.56/294.51	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
1115.56/294.51	(2) CpxTRS
1115.56/294.51	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1115.56/294.51	(4) typed CpxTrs
1115.56/294.51	(5) OrderProof [LOWER BOUND(ID), 0 ms]
1115.56/294.51	(6) typed CpxTrs
1115.56/294.51	(7) RewriteLemmaProof [LOWER BOUND(ID), 271 ms]
1115.56/294.51	(8) BEST
1115.56/294.51	    (9) proven lower bound
1115.56/294.51	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
1115.56/294.51	        (11) BOUNDS(n^1, INF)
1115.56/294.51	    (12) typed CpxTrs
1115.56/294.51	        (13) RewriteLemmaProof [LOWER BOUND(ID), 27 ms]
1115.56/294.51	        (14) typed CpxTrs
1115.56/294.51	        (15) RewriteLemmaProof [LOWER BOUND(ID), 59 ms]
1115.56/294.51	        (16) BEST
1115.56/294.51	            (17) proven lower bound
1115.56/294.51	                (18) LowerBoundPropagationProof [FINISHED, 0 ms]
1115.56/294.51	                (19) BOUNDS(n^2, INF)
1115.56/294.51	            (20) typed CpxTrs
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(0)
1115.56/294.51	Obligation:
1115.56/294.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	The TRS R consists of the following rules:
1115.56/294.51	
1115.56/294.51	   -(x, 0) -> x
1115.56/294.51	   -(s(x), s(y)) -> -(x, y)
1115.56/294.51	   +(0, y) -> y
1115.56/294.51	   +(s(x), y) -> s(+(x, y))
1115.56/294.51	   *(x, 0) -> 0
1115.56/294.51	   *(x, s(y)) -> +(x, *(x, y))
1115.56/294.51	   f(s(x), y) -> f(-(*(s(x), s(y)), s(*(s(x), y))), *(y, y))
1115.56/294.51	
1115.56/294.51	S is empty.
1115.56/294.51	Rewrite Strategy: INNERMOST
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(1) RenamingProof (BOTH BOUNDS(ID, ID))
1115.56/294.51	Renamed function symbols to avoid clashes with predefined symbol.
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(2)
1115.56/294.51	Obligation:
1115.56/294.51	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	The TRS R consists of the following rules:
1115.56/294.51	
1115.56/294.51	   -(x, 0') -> x
1115.56/294.51	   -(s(x), s(y)) -> -(x, y)
1115.56/294.51	   +'(0', y) -> y
1115.56/294.51	   +'(s(x), y) -> s(+'(x, y))
1115.56/294.51	   *'(x, 0') -> 0'
1115.56/294.51	   *'(x, s(y)) -> +'(x, *'(x, y))
1115.56/294.51	   f(s(x), y) -> f(-(*'(s(x), s(y)), s(*'(s(x), y))), *'(y, y))
1115.56/294.51	
1115.56/294.51	S is empty.
1115.56/294.51	Rewrite Strategy: INNERMOST
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1115.56/294.51	Infered types.
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(4)
1115.56/294.51	Obligation:
1115.56/294.51	Innermost TRS:
1115.56/294.51	Rules:
1115.56/294.51	-(x, 0') -> x
1115.56/294.51	-(s(x), s(y)) -> -(x, y)
1115.56/294.51	+'(0', y) -> y
1115.56/294.51	+'(s(x), y) -> s(+'(x, y))
1115.56/294.51	*'(x, 0') -> 0'
1115.56/294.51	*'(x, s(y)) -> +'(x, *'(x, y))
1115.56/294.51	f(s(x), y) -> f(-(*'(s(x), s(y)), s(*'(s(x), y))), *'(y, y))
1115.56/294.51	
1115.56/294.51	Types:
1115.56/294.51	- :: 0':s -> 0':s -> 0':s
1115.56/294.51	0' :: 0':s
1115.56/294.51	s :: 0':s -> 0':s
1115.56/294.51	+' :: 0':s -> 0':s -> 0':s
1115.56/294.51	*' :: 0':s -> 0':s -> 0':s
1115.56/294.51	f :: 0':s -> 0':s -> f
1115.56/294.51	hole_0':s1_0 :: 0':s
1115.56/294.51	hole_f2_0 :: f
1115.56/294.51	gen_0':s3_0 :: Nat -> 0':s
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(5) OrderProof (LOWER BOUND(ID))
1115.56/294.51	Heuristically decided to analyse the following defined symbols:
1115.56/294.51	-, +', *', f
1115.56/294.51	
1115.56/294.51	They will be analysed ascendingly in the following order:
1115.56/294.51	- < f
1115.56/294.51	+' < *'
1115.56/294.51	*' < f
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(6)
1115.56/294.51	Obligation:
1115.56/294.51	Innermost TRS:
1115.56/294.51	Rules:
1115.56/294.51	-(x, 0') -> x
1115.56/294.51	-(s(x), s(y)) -> -(x, y)
1115.56/294.51	+'(0', y) -> y
1115.56/294.51	+'(s(x), y) -> s(+'(x, y))
1115.56/294.51	*'(x, 0') -> 0'
1115.56/294.51	*'(x, s(y)) -> +'(x, *'(x, y))
1115.56/294.51	f(s(x), y) -> f(-(*'(s(x), s(y)), s(*'(s(x), y))), *'(y, y))
1115.56/294.51	
1115.56/294.51	Types:
1115.56/294.51	- :: 0':s -> 0':s -> 0':s
1115.56/294.51	0' :: 0':s
1115.56/294.51	s :: 0':s -> 0':s
1115.56/294.51	+' :: 0':s -> 0':s -> 0':s
1115.56/294.51	*' :: 0':s -> 0':s -> 0':s
1115.56/294.51	f :: 0':s -> 0':s -> f
1115.56/294.51	hole_0':s1_0 :: 0':s
1115.56/294.51	hole_f2_0 :: f
1115.56/294.51	gen_0':s3_0 :: Nat -> 0':s
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Generator Equations:
1115.56/294.51	gen_0':s3_0(0) <=> 0'
1115.56/294.51	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	The following defined symbols remain to be analysed:
1115.56/294.51	-, +', *', f
1115.56/294.51	
1115.56/294.51	They will be analysed ascendingly in the following order:
1115.56/294.51	- < f
1115.56/294.51	+' < *'
1115.56/294.51	*' < f
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(7) RewriteLemmaProof (LOWER BOUND(ID))
1115.56/294.51	Proved the following rewrite lemma:
1115.56/294.51	-(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(0), rt in Omega(1 + n5_0)
1115.56/294.51	
1115.56/294.51	Induction Base:
1115.56/294.51	-(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1)
1115.56/294.51	gen_0':s3_0(0)
1115.56/294.51	
1115.56/294.51	Induction Step:
1115.56/294.51	-(gen_0':s3_0(+(n5_0, 1)), gen_0':s3_0(+(n5_0, 1))) ->_R^Omega(1)
1115.56/294.51	-(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) ->_IH
1115.56/294.51	gen_0':s3_0(0)
1115.56/294.51	
1115.56/294.51	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(8)
1115.56/294.51	Complex Obligation (BEST)
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(9)
1115.56/294.51	Obligation:
1115.56/294.51	Proved the lower bound n^1 for the following obligation:
1115.56/294.51	
1115.56/294.51	Innermost TRS:
1115.56/294.51	Rules:
1115.56/294.51	-(x, 0') -> x
1115.56/294.51	-(s(x), s(y)) -> -(x, y)
1115.56/294.51	+'(0', y) -> y
1115.56/294.51	+'(s(x), y) -> s(+'(x, y))
1115.56/294.51	*'(x, 0') -> 0'
1115.56/294.51	*'(x, s(y)) -> +'(x, *'(x, y))
1115.56/294.51	f(s(x), y) -> f(-(*'(s(x), s(y)), s(*'(s(x), y))), *'(y, y))
1115.56/294.51	
1115.56/294.51	Types:
1115.56/294.51	- :: 0':s -> 0':s -> 0':s
1115.56/294.51	0' :: 0':s
1115.56/294.51	s :: 0':s -> 0':s
1115.56/294.51	+' :: 0':s -> 0':s -> 0':s
1115.56/294.51	*' :: 0':s -> 0':s -> 0':s
1115.56/294.51	f :: 0':s -> 0':s -> f
1115.56/294.51	hole_0':s1_0 :: 0':s
1115.56/294.51	hole_f2_0 :: f
1115.56/294.51	gen_0':s3_0 :: Nat -> 0':s
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Generator Equations:
1115.56/294.51	gen_0':s3_0(0) <=> 0'
1115.56/294.51	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	The following defined symbols remain to be analysed:
1115.56/294.51	-, +', *', f
1115.56/294.51	
1115.56/294.51	They will be analysed ascendingly in the following order:
1115.56/294.51	- < f
1115.56/294.51	+' < *'
1115.56/294.51	*' < f
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(10) LowerBoundPropagationProof (FINISHED)
1115.56/294.51	Propagated lower bound.
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(11)
1115.56/294.51	BOUNDS(n^1, INF)
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(12)
1115.56/294.51	Obligation:
1115.56/294.51	Innermost TRS:
1115.56/294.51	Rules:
1115.56/294.51	-(x, 0') -> x
1115.56/294.51	-(s(x), s(y)) -> -(x, y)
1115.56/294.51	+'(0', y) -> y
1115.56/294.51	+'(s(x), y) -> s(+'(x, y))
1115.56/294.51	*'(x, 0') -> 0'
1115.56/294.51	*'(x, s(y)) -> +'(x, *'(x, y))
1115.56/294.51	f(s(x), y) -> f(-(*'(s(x), s(y)), s(*'(s(x), y))), *'(y, y))
1115.56/294.51	
1115.56/294.51	Types:
1115.56/294.51	- :: 0':s -> 0':s -> 0':s
1115.56/294.51	0' :: 0':s
1115.56/294.51	s :: 0':s -> 0':s
1115.56/294.51	+' :: 0':s -> 0':s -> 0':s
1115.56/294.51	*' :: 0':s -> 0':s -> 0':s
1115.56/294.51	f :: 0':s -> 0':s -> f
1115.56/294.51	hole_0':s1_0 :: 0':s
1115.56/294.51	hole_f2_0 :: f
1115.56/294.51	gen_0':s3_0 :: Nat -> 0':s
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Lemmas:
1115.56/294.51	-(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(0), rt in Omega(1 + n5_0)
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Generator Equations:
1115.56/294.51	gen_0':s3_0(0) <=> 0'
1115.56/294.51	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	The following defined symbols remain to be analysed:
1115.56/294.51	+', *', f
1115.56/294.51	
1115.56/294.51	They will be analysed ascendingly in the following order:
1115.56/294.51	+' < *'
1115.56/294.51	*' < f
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(13) RewriteLemmaProof (LOWER BOUND(ID))
1115.56/294.51	Proved the following rewrite lemma:
1115.56/294.51	+'(gen_0':s3_0(n273_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n273_0, b)), rt in Omega(1 + n273_0)
1115.56/294.51	
1115.56/294.51	Induction Base:
1115.56/294.51	+'(gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1)
1115.56/294.51	gen_0':s3_0(b)
1115.56/294.51	
1115.56/294.51	Induction Step:
1115.56/294.51	+'(gen_0':s3_0(+(n273_0, 1)), gen_0':s3_0(b)) ->_R^Omega(1)
1115.56/294.51	s(+'(gen_0':s3_0(n273_0), gen_0':s3_0(b))) ->_IH
1115.56/294.51	s(gen_0':s3_0(+(b, c274_0)))
1115.56/294.51	
1115.56/294.51	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(14)
1115.56/294.51	Obligation:
1115.56/294.51	Innermost TRS:
1115.56/294.51	Rules:
1115.56/294.51	-(x, 0') -> x
1115.56/294.51	-(s(x), s(y)) -> -(x, y)
1115.56/294.51	+'(0', y) -> y
1115.56/294.51	+'(s(x), y) -> s(+'(x, y))
1115.56/294.51	*'(x, 0') -> 0'
1115.56/294.51	*'(x, s(y)) -> +'(x, *'(x, y))
1115.56/294.51	f(s(x), y) -> f(-(*'(s(x), s(y)), s(*'(s(x), y))), *'(y, y))
1115.56/294.51	
1115.56/294.51	Types:
1115.56/294.51	- :: 0':s -> 0':s -> 0':s
1115.56/294.51	0' :: 0':s
1115.56/294.51	s :: 0':s -> 0':s
1115.56/294.51	+' :: 0':s -> 0':s -> 0':s
1115.56/294.51	*' :: 0':s -> 0':s -> 0':s
1115.56/294.51	f :: 0':s -> 0':s -> f
1115.56/294.51	hole_0':s1_0 :: 0':s
1115.56/294.51	hole_f2_0 :: f
1115.56/294.51	gen_0':s3_0 :: Nat -> 0':s
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Lemmas:
1115.56/294.51	-(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(0), rt in Omega(1 + n5_0)
1115.56/294.51	+'(gen_0':s3_0(n273_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n273_0, b)), rt in Omega(1 + n273_0)
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Generator Equations:
1115.56/294.51	gen_0':s3_0(0) <=> 0'
1115.56/294.51	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	The following defined symbols remain to be analysed:
1115.56/294.51	*', f
1115.56/294.51	
1115.56/294.51	They will be analysed ascendingly in the following order:
1115.56/294.51	*' < f
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(15) RewriteLemmaProof (LOWER BOUND(ID))
1115.56/294.51	Proved the following rewrite lemma:
1115.56/294.51	*'(gen_0':s3_0(a), gen_0':s3_0(n792_0)) -> gen_0':s3_0(*(n792_0, a)), rt in Omega(1 + a*n792_0 + n792_0)
1115.56/294.51	
1115.56/294.51	Induction Base:
1115.56/294.51	*'(gen_0':s3_0(a), gen_0':s3_0(0)) ->_R^Omega(1)
1115.56/294.51	0'
1115.56/294.51	
1115.56/294.51	Induction Step:
1115.56/294.51	*'(gen_0':s3_0(a), gen_0':s3_0(+(n792_0, 1))) ->_R^Omega(1)
1115.56/294.51	+'(gen_0':s3_0(a), *'(gen_0':s3_0(a), gen_0':s3_0(n792_0))) ->_IH
1115.56/294.51	+'(gen_0':s3_0(a), gen_0':s3_0(*(c793_0, a))) ->_L^Omega(1 + a)
1115.56/294.51	gen_0':s3_0(+(a, *(n792_0, a)))
1115.56/294.51	
1115.56/294.51	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(16)
1115.56/294.51	Complex Obligation (BEST)
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(17)
1115.56/294.51	Obligation:
1115.56/294.51	Proved the lower bound n^2 for the following obligation:
1115.56/294.51	
1115.56/294.51	Innermost TRS:
1115.56/294.51	Rules:
1115.56/294.51	-(x, 0') -> x
1115.56/294.51	-(s(x), s(y)) -> -(x, y)
1115.56/294.51	+'(0', y) -> y
1115.56/294.51	+'(s(x), y) -> s(+'(x, y))
1115.56/294.51	*'(x, 0') -> 0'
1115.56/294.51	*'(x, s(y)) -> +'(x, *'(x, y))
1115.56/294.51	f(s(x), y) -> f(-(*'(s(x), s(y)), s(*'(s(x), y))), *'(y, y))
1115.56/294.51	
1115.56/294.51	Types:
1115.56/294.51	- :: 0':s -> 0':s -> 0':s
1115.56/294.51	0' :: 0':s
1115.56/294.51	s :: 0':s -> 0':s
1115.56/294.51	+' :: 0':s -> 0':s -> 0':s
1115.56/294.51	*' :: 0':s -> 0':s -> 0':s
1115.56/294.51	f :: 0':s -> 0':s -> f
1115.56/294.51	hole_0':s1_0 :: 0':s
1115.56/294.51	hole_f2_0 :: f
1115.56/294.51	gen_0':s3_0 :: Nat -> 0':s
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Lemmas:
1115.56/294.51	-(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(0), rt in Omega(1 + n5_0)
1115.56/294.51	+'(gen_0':s3_0(n273_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n273_0, b)), rt in Omega(1 + n273_0)
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Generator Equations:
1115.56/294.51	gen_0':s3_0(0) <=> 0'
1115.56/294.51	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	The following defined symbols remain to be analysed:
1115.56/294.51	*', f
1115.56/294.51	
1115.56/294.51	They will be analysed ascendingly in the following order:
1115.56/294.51	*' < f
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(18) LowerBoundPropagationProof (FINISHED)
1115.56/294.51	Propagated lower bound.
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(19)
1115.56/294.51	BOUNDS(n^2, INF)
1115.56/294.51	
1115.56/294.51	----------------------------------------
1115.56/294.51	
1115.56/294.51	(20)
1115.56/294.51	Obligation:
1115.56/294.51	Innermost TRS:
1115.56/294.51	Rules:
1115.56/294.51	-(x, 0') -> x
1115.56/294.51	-(s(x), s(y)) -> -(x, y)
1115.56/294.51	+'(0', y) -> y
1115.56/294.51	+'(s(x), y) -> s(+'(x, y))
1115.56/294.51	*'(x, 0') -> 0'
1115.56/294.51	*'(x, s(y)) -> +'(x, *'(x, y))
1115.56/294.51	f(s(x), y) -> f(-(*'(s(x), s(y)), s(*'(s(x), y))), *'(y, y))
1115.56/294.51	
1115.56/294.51	Types:
1115.56/294.51	- :: 0':s -> 0':s -> 0':s
1115.56/294.51	0' :: 0':s
1115.56/294.51	s :: 0':s -> 0':s
1115.56/294.51	+' :: 0':s -> 0':s -> 0':s
1115.56/294.51	*' :: 0':s -> 0':s -> 0':s
1115.56/294.51	f :: 0':s -> 0':s -> f
1115.56/294.51	hole_0':s1_0 :: 0':s
1115.56/294.51	hole_f2_0 :: f
1115.56/294.51	gen_0':s3_0 :: Nat -> 0':s
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Lemmas:
1115.56/294.51	-(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(0), rt in Omega(1 + n5_0)
1115.56/294.51	+'(gen_0':s3_0(n273_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n273_0, b)), rt in Omega(1 + n273_0)
1115.56/294.51	*'(gen_0':s3_0(a), gen_0':s3_0(n792_0)) -> gen_0':s3_0(*(n792_0, a)), rt in Omega(1 + a*n792_0 + n792_0)
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	Generator Equations:
1115.56/294.51	gen_0':s3_0(0) <=> 0'
1115.56/294.51	gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x))
1115.56/294.51	
1115.56/294.51	
1115.56/294.51	The following defined symbols remain to be analysed:
1115.56/294.51	f
1115.62/294.57	EOF