13.89/4.47	WORST_CASE(Omega(n^1), O(n^1))
13.89/4.48	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
13.89/4.48	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
13.89/4.48	
13.89/4.48	
13.89/4.48	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.89/4.48	
13.89/4.48	(0) CpxTRS
13.89/4.48	(1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
13.89/4.48	(2) CpxTRS
13.89/4.48	    (3) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
13.89/4.48	    (4) CdtProblem
13.89/4.48	    (5) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
13.89/4.48	    (6) CdtProblem
13.89/4.48	    (7) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 64 ms]
13.89/4.48	    (8) CdtProblem
13.89/4.48	    (9) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
13.89/4.48	    (10) BOUNDS(1, 1)
13.89/4.48	(11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
13.89/4.48	(12) CpxTRS
13.89/4.48	    (13) SlicingProof [LOWER BOUND(ID), 0 ms]
13.89/4.48	    (14) CpxTRS
13.89/4.48	    (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
13.89/4.48	    (16) typed CpxTrs
13.89/4.48	    (17) OrderProof [LOWER BOUND(ID), 0 ms]
13.89/4.48	    (18) typed CpxTrs
13.89/4.48	    (19) RewriteLemmaProof [LOWER BOUND(ID), 163 ms]
13.89/4.48	    (20) proven lower bound
13.89/4.48	    (21) LowerBoundPropagationProof [FINISHED, 0 ms]
13.89/4.48	    (22) BOUNDS(n^1, INF)
13.89/4.48	
13.89/4.48	
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(0)
13.89/4.48	Obligation:
13.89/4.48	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
13.89/4.48	
13.89/4.48	
13.89/4.48	The TRS R consists of the following rules:
13.89/4.48	
13.89/4.48	   f(0, y) -> 0
13.89/4.48	   f(s(x), y) -> f(f(x, y), y)
13.89/4.48	
13.89/4.48	S is empty.
13.89/4.48	Rewrite Strategy: FULL
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(1) RcToIrcProof (BOTH BOUNDS(ID, ID))
13.89/4.48	Converted rc-obligation to irc-obligation.
13.89/4.48	
13.89/4.48	The duplicating contexts are:
13.89/4.48	f(s(x), [])
13.89/4.48	
13.89/4.48	
13.89/4.48	The defined contexts are:
13.89/4.48	f([], x1)
13.89/4.48	
13.89/4.48	
13.89/4.48	As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(2)
13.89/4.48	Obligation:
13.89/4.48	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
13.89/4.48	
13.89/4.48	
13.89/4.48	The TRS R consists of the following rules:
13.89/4.48	
13.89/4.48	   f(0, y) -> 0
13.89/4.48	   f(s(x), y) -> f(f(x, y), y)
13.89/4.48	
13.89/4.48	S is empty.
13.89/4.48	Rewrite Strategy: INNERMOST
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(3) CpxTrsToCdtProof (UPPER BOUND(ID))
13.89/4.48	Converted Cpx (relative) TRS to CDT
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(4)
13.89/4.48	Obligation:
13.89/4.48	Complexity Dependency Tuples Problem
13.89/4.48	
13.89/4.48	Rules:
13.89/4.48	   f(0, z0) -> 0
13.89/4.48	   f(s(z0), z1) -> f(f(z0, z1), z1)
13.89/4.48	Tuples:
13.89/4.48	   F(0, z0) -> c
13.89/4.48	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.89/4.48	S tuples:
13.89/4.48	   F(0, z0) -> c
13.89/4.48	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.89/4.48	K tuples:none
13.89/4.48	Defined Rule Symbols:   f_2
13.89/4.48	
13.89/4.48	Defined Pair Symbols:   F_2
13.89/4.48	
13.89/4.48	Compound Symbols:   c, c1_2
13.89/4.48	
13.89/4.48	
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
13.89/4.48	Removed 1 trailing nodes:
13.89/4.48	   F(0, z0) -> c
13.89/4.48	
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(6)
13.89/4.48	Obligation:
13.89/4.48	Complexity Dependency Tuples Problem
13.89/4.48	
13.89/4.48	Rules:
13.89/4.48	   f(0, z0) -> 0
13.89/4.48	   f(s(z0), z1) -> f(f(z0, z1), z1)
13.89/4.48	Tuples:
13.89/4.48	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.89/4.48	S tuples:
13.89/4.48	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.89/4.48	K tuples:none
13.89/4.48	Defined Rule Symbols:   f_2
13.89/4.48	
13.89/4.48	Defined Pair Symbols:   F_2
13.89/4.48	
13.89/4.48	Compound Symbols:   c1_2
13.89/4.48	
13.89/4.48	
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(7) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
13.89/4.48	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
13.89/4.48	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.89/4.48	We considered the (Usable) Rules:
13.89/4.48	   f(0, z0) -> 0
13.89/4.48	   f(s(z0), z1) -> f(f(z0, z1), z1)
13.89/4.48	And the Tuples:
13.89/4.48	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.89/4.48	The order we found is given by the following interpretation:
13.89/4.48	
13.89/4.48	Polynomial interpretation :
13.89/4.48	
13.89/4.48	   POL(0) = 0
13.89/4.48	   POL(F(x_1, x_2)) = x_1
13.89/4.48	   POL(c1(x_1, x_2)) = x_1 + x_2
13.89/4.48	   POL(f(x_1, x_2)) = 0
13.89/4.48	   POL(s(x_1)) = [1] + x_1
13.89/4.48	
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(8)
13.89/4.48	Obligation:
13.89/4.48	Complexity Dependency Tuples Problem
13.89/4.48	
13.89/4.48	Rules:
13.89/4.48	   f(0, z0) -> 0
13.89/4.48	   f(s(z0), z1) -> f(f(z0, z1), z1)
13.89/4.48	Tuples:
13.89/4.48	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.89/4.48	S tuples:none
13.89/4.48	K tuples:
13.89/4.48	   F(s(z0), z1) -> c1(F(f(z0, z1), z1), F(z0, z1))
13.89/4.48	Defined Rule Symbols:   f_2
13.89/4.48	
13.89/4.48	Defined Pair Symbols:   F_2
13.89/4.48	
13.89/4.48	Compound Symbols:   c1_2
13.89/4.48	
13.89/4.48	
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(9) SIsEmptyProof (BOTH BOUNDS(ID, ID))
13.89/4.48	The set S is empty
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(10)
13.89/4.48	BOUNDS(1, 1)
13.89/4.48	
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(11) RenamingProof (BOTH BOUNDS(ID, ID))
13.89/4.48	Renamed function symbols to avoid clashes with predefined symbol.
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(12)
13.89/4.48	Obligation:
13.89/4.48	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
13.89/4.48	
13.89/4.48	
13.89/4.48	The TRS R consists of the following rules:
13.89/4.48	
13.89/4.48	   f(0', y) -> 0'
13.89/4.48	   f(s(x), y) -> f(f(x, y), y)
13.89/4.48	
13.89/4.48	S is empty.
13.89/4.48	Rewrite Strategy: FULL
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(13) SlicingProof (LOWER BOUND(ID))
13.89/4.48	Sliced the following arguments:
13.89/4.48	f/1
13.89/4.48	
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(14)
13.89/4.48	Obligation:
13.89/4.48	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
13.89/4.48	
13.89/4.48	
13.89/4.48	The TRS R consists of the following rules:
13.89/4.48	
13.89/4.48	   f(0') -> 0'
13.89/4.48	   f(s(x)) -> f(f(x))
13.89/4.48	
13.89/4.48	S is empty.
13.89/4.48	Rewrite Strategy: FULL
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(15) TypeInferenceProof (BOTH BOUNDS(ID, ID))
13.89/4.48	Infered types.
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(16)
13.89/4.48	Obligation:
13.89/4.48	TRS:
13.89/4.48	Rules:
13.89/4.48	f(0') -> 0'
13.89/4.48	f(s(x)) -> f(f(x))
13.89/4.48	
13.89/4.48	Types:
13.89/4.48	f :: 0':s -> 0':s
13.89/4.48	0' :: 0':s
13.89/4.48	s :: 0':s -> 0':s
13.89/4.48	hole_0':s1_0 :: 0':s
13.89/4.48	gen_0':s2_0 :: Nat -> 0':s
13.89/4.48	
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(17) OrderProof (LOWER BOUND(ID))
13.89/4.48	Heuristically decided to analyse the following defined symbols:
13.89/4.48	f
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(18)
13.89/4.48	Obligation:
13.89/4.48	TRS:
13.89/4.48	Rules:
13.89/4.48	f(0') -> 0'
13.89/4.48	f(s(x)) -> f(f(x))
13.89/4.48	
13.89/4.48	Types:
13.89/4.48	f :: 0':s -> 0':s
13.89/4.48	0' :: 0':s
13.89/4.48	s :: 0':s -> 0':s
13.89/4.48	hole_0':s1_0 :: 0':s
13.89/4.48	gen_0':s2_0 :: Nat -> 0':s
13.89/4.48	
13.89/4.48	
13.89/4.48	Generator Equations:
13.89/4.48	gen_0':s2_0(0) <=> 0'
13.89/4.48	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
13.89/4.48	
13.89/4.48	
13.89/4.48	The following defined symbols remain to be analysed:
13.89/4.48	f
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(19) RewriteLemmaProof (LOWER BOUND(ID))
13.89/4.48	Proved the following rewrite lemma:
13.89/4.48	f(gen_0':s2_0(n4_0)) -> gen_0':s2_0(0), rt in Omega(1 + n4_0)
13.89/4.48	
13.89/4.48	Induction Base:
13.89/4.48	f(gen_0':s2_0(0)) ->_R^Omega(1)
13.89/4.48	0'
13.89/4.48	
13.89/4.48	Induction Step:
13.89/4.48	f(gen_0':s2_0(+(n4_0, 1))) ->_R^Omega(1)
13.89/4.48	f(f(gen_0':s2_0(n4_0))) ->_IH
13.89/4.48	f(gen_0':s2_0(0)) ->_R^Omega(1)
13.89/4.48	0'
13.89/4.48	
13.89/4.48	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(20)
13.89/4.48	Obligation:
13.89/4.48	Proved the lower bound n^1 for the following obligation:
13.89/4.48	
13.89/4.48	TRS:
13.89/4.48	Rules:
13.89/4.48	f(0') -> 0'
13.89/4.48	f(s(x)) -> f(f(x))
13.89/4.48	
13.89/4.48	Types:
13.89/4.48	f :: 0':s -> 0':s
13.89/4.48	0' :: 0':s
13.89/4.48	s :: 0':s -> 0':s
13.89/4.48	hole_0':s1_0 :: 0':s
13.89/4.48	gen_0':s2_0 :: Nat -> 0':s
13.89/4.48	
13.89/4.48	
13.89/4.48	Generator Equations:
13.89/4.48	gen_0':s2_0(0) <=> 0'
13.89/4.48	gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x))
13.89/4.48	
13.89/4.48	
13.89/4.48	The following defined symbols remain to be analysed:
13.89/4.48	f
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(21) LowerBoundPropagationProof (FINISHED)
13.89/4.48	Propagated lower bound.
13.89/4.48	----------------------------------------
13.89/4.48	
13.89/4.48	(22)
13.89/4.48	BOUNDS(n^1, INF)
14.28/4.74	EOF