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