30.17/10.54	WORST_CASE(Omega(n^1), O(n^1))
30.30/10.55	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
30.30/10.55	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
30.30/10.55	
30.30/10.55	
30.30/10.55	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
30.30/10.55	
30.30/10.55	(0) CpxTRS
30.30/10.55	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
30.30/10.55	(2) CpxTRS
30.30/10.55	    (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 6 ms]
30.30/10.55	    (4) CpxTRS
30.30/10.55	    (5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms]
30.30/10.55	    (6) CdtProblem
30.30/10.55	    (7) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms]
30.30/10.55	    (8) CdtProblem
30.30/10.55	    (9) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms]
30.30/10.55	    (10) CdtProblem
30.30/10.55	    (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 18 ms]
30.30/10.55	    (12) CdtProblem
30.30/10.55	    (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms]
30.30/10.55	    (14) BOUNDS(1, 1)
30.30/10.55	(15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
30.30/10.55	(16) CpxTRS
30.30/10.55	    (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
30.30/10.55	    (18) typed CpxTrs
30.30/10.55	    (19) OrderProof [LOWER BOUND(ID), 0 ms]
30.30/10.55	    (20) typed CpxTrs
30.30/10.55	    (21) RewriteLemmaProof [LOWER BOUND(ID), 516 ms]
30.30/10.55	    (22) BEST
30.30/10.55	        (23) proven lower bound
30.30/10.55	            (24) LowerBoundPropagationProof [FINISHED, 0 ms]
30.30/10.55	            (25) BOUNDS(n^1, INF)
30.30/10.55	        (26) typed CpxTrs
30.30/10.55	
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(0)
30.30/10.55	Obligation:
30.30/10.55	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
30.30/10.55	
30.30/10.55	
30.30/10.55	The TRS R consists of the following rules:
30.30/10.55	
30.30/10.55	   h(e(x), y) -> h(d(x, y), s(y))
30.30/10.55	   d(g(g(0, x), y), s(z)) -> g(e(x), d(g(g(0, x), y), z))
30.30/10.55	   d(g(g(0, x), y), 0) -> e(y)
30.30/10.55	   d(g(0, x), y) -> e(x)
30.30/10.55	   d(g(x, y), z) -> g(d(x, z), e(y))
30.30/10.55	   g(e(x), e(y)) -> e(g(x, y))
30.30/10.55	
30.30/10.55	S is empty.
30.30/10.55	Rewrite Strategy: FULL
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
30.30/10.55	The following defined symbols can occur below the 0th argument of h: d
30.30/10.55	The following defined symbols can occur below the 0th argument of d: d
30.30/10.55	
30.30/10.55	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
30.30/10.55	d(g(g(0, x), y), s(z)) -> g(e(x), d(g(g(0, x), y), z))
30.30/10.55	d(g(g(0, x), y), 0) -> e(y)
30.30/10.55	d(g(0, x), y) -> e(x)
30.30/10.55	d(g(x, y), z) -> g(d(x, z), e(y))
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(2)
30.30/10.55	Obligation:
30.30/10.55	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
30.30/10.55	
30.30/10.55	
30.30/10.55	The TRS R consists of the following rules:
30.30/10.55	
30.30/10.55	   h(e(x), y) -> h(d(x, y), s(y))
30.30/10.55	   g(e(x), e(y)) -> e(g(x, y))
30.30/10.55	
30.30/10.55	S is empty.
30.30/10.55	Rewrite Strategy: FULL
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(3) RcToIrcProof (BOTH BOUNDS(ID, ID))
30.30/10.55	Converted rc-obligation to irc-obligation.
30.30/10.55	
30.30/10.55	As the TRS does not nest defined symbols, we have rc = irc.
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(4)
30.30/10.55	Obligation:
30.30/10.55	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
30.30/10.55	
30.30/10.55	
30.30/10.55	The TRS R consists of the following rules:
30.30/10.55	
30.30/10.55	   h(e(x), y) -> h(d(x, y), s(y))
30.30/10.55	   g(e(x), e(y)) -> e(g(x, y))
30.30/10.55	
30.30/10.55	S is empty.
30.30/10.55	Rewrite Strategy: INNERMOST
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(5) CpxTrsToCdtProof (UPPER BOUND(ID))
30.30/10.55	Converted Cpx (relative) TRS to CDT
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(6)
30.30/10.55	Obligation:
30.30/10.55	Complexity Dependency Tuples Problem
30.30/10.55	
30.30/10.55	Rules:
30.30/10.55	   h(e(z0), z1) -> h(d(z0, z1), s(z1))
30.30/10.55	   g(e(z0), e(z1)) -> e(g(z0, z1))
30.30/10.55	Tuples:
30.30/10.55	   H(e(z0), z1) -> c(H(d(z0, z1), s(z1)))
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	S tuples:
30.30/10.55	   H(e(z0), z1) -> c(H(d(z0, z1), s(z1)))
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	K tuples:none
30.30/10.55	Defined Rule Symbols:   h_2, g_2
30.30/10.55	
30.30/10.55	Defined Pair Symbols:   H_2, G_2
30.30/10.55	
30.30/10.55	Compound Symbols:   c_1, c1_1
30.30/10.55	
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID))
30.30/10.55	Removed 1 trailing nodes:
30.30/10.55	   H(e(z0), z1) -> c(H(d(z0, z1), s(z1)))
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(8)
30.30/10.55	Obligation:
30.30/10.55	Complexity Dependency Tuples Problem
30.30/10.55	
30.30/10.55	Rules:
30.30/10.55	   h(e(z0), z1) -> h(d(z0, z1), s(z1))
30.30/10.55	   g(e(z0), e(z1)) -> e(g(z0, z1))
30.30/10.55	Tuples:
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	S tuples:
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	K tuples:none
30.30/10.55	Defined Rule Symbols:   h_2, g_2
30.30/10.55	
30.30/10.55	Defined Pair Symbols:   G_2
30.30/10.55	
30.30/10.55	Compound Symbols:   c1_1
30.30/10.55	
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(9) CdtUsableRulesProof (BOTH BOUNDS(ID, ID))
30.30/10.55	The following rules are not usable and were removed:
30.30/10.55	   h(e(z0), z1) -> h(d(z0, z1), s(z1))
30.30/10.55	   g(e(z0), e(z1)) -> e(g(z0, z1))
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(10)
30.30/10.55	Obligation:
30.30/10.55	Complexity Dependency Tuples Problem
30.30/10.55	
30.30/10.55	Rules:none
30.30/10.55	Tuples:
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	S tuples:
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	K tuples:none
30.30/10.55	Defined Rule Symbols:none
30.30/10.55	
30.30/10.55	Defined Pair Symbols:   G_2
30.30/10.55	
30.30/10.55	Compound Symbols:   c1_1
30.30/10.55	
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)))
30.30/10.55	Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	We considered the (Usable) Rules:none
30.30/10.55	And the Tuples:
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	The order we found is given by the following interpretation:
30.30/10.55	
30.30/10.55	Polynomial interpretation :
30.30/10.55	
30.30/10.55	   POL(G(x_1, x_2)) = x_2
30.30/10.55	   POL(c1(x_1)) = x_1
30.30/10.55	   POL(e(x_1)) = [1] + x_1
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(12)
30.30/10.55	Obligation:
30.30/10.55	Complexity Dependency Tuples Problem
30.30/10.55	
30.30/10.55	Rules:none
30.30/10.55	Tuples:
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	S tuples:none
30.30/10.55	K tuples:
30.30/10.55	   G(e(z0), e(z1)) -> c1(G(z0, z1))
30.30/10.55	Defined Rule Symbols:none
30.30/10.55	
30.30/10.55	Defined Pair Symbols:   G_2
30.30/10.55	
30.30/10.55	Compound Symbols:   c1_1
30.30/10.55	
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(13) SIsEmptyProof (BOTH BOUNDS(ID, ID))
30.30/10.55	The set S is empty
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(14)
30.30/10.55	BOUNDS(1, 1)
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(15) RenamingProof (BOTH BOUNDS(ID, ID))
30.30/10.55	Renamed function symbols to avoid clashes with predefined symbol.
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(16)
30.30/10.55	Obligation:
30.30/10.55	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
30.30/10.55	
30.30/10.55	
30.30/10.55	The TRS R consists of the following rules:
30.30/10.55	
30.30/10.55	   h(e(x), y) -> h(d(x, y), s(y))
30.30/10.55	   d(g(g(0', x), y), s(z)) -> g(e(x), d(g(g(0', x), y), z))
30.30/10.55	   d(g(g(0', x), y), 0') -> e(y)
30.30/10.55	   d(g(0', x), y) -> e(x)
30.30/10.55	   d(g(x, y), z) -> g(d(x, z), e(y))
30.30/10.55	   g(e(x), e(y)) -> e(g(x, y))
30.30/10.55	
30.30/10.55	S is empty.
30.30/10.55	Rewrite Strategy: FULL
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(17) TypeInferenceProof (BOTH BOUNDS(ID, ID))
30.30/10.55	Infered types.
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(18)
30.30/10.55	Obligation:
30.30/10.55	TRS:
30.30/10.55	Rules:
30.30/10.55	h(e(x), y) -> h(d(x, y), s(y))
30.30/10.55	d(g(g(0', x), y), s(z)) -> g(e(x), d(g(g(0', x), y), z))
30.30/10.55	d(g(g(0', x), y), 0') -> e(y)
30.30/10.55	d(g(0', x), y) -> e(x)
30.30/10.55	d(g(x, y), z) -> g(d(x, z), e(y))
30.30/10.55	g(e(x), e(y)) -> e(g(x, y))
30.30/10.55	
30.30/10.55	Types:
30.30/10.55	h :: e:s:0' -> e:s:0' -> h
30.30/10.55	e :: e:s:0' -> e:s:0'
30.30/10.55	d :: e:s:0' -> e:s:0' -> e:s:0'
30.30/10.55	s :: e:s:0' -> e:s:0'
30.30/10.55	g :: e:s:0' -> e:s:0' -> e:s:0'
30.30/10.55	0' :: e:s:0'
30.30/10.55	hole_h1_0 :: h
30.30/10.55	hole_e:s:0'2_0 :: e:s:0'
30.30/10.55	gen_e:s:0'3_0 :: Nat -> e:s:0'
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(19) OrderProof (LOWER BOUND(ID))
30.30/10.55	Heuristically decided to analyse the following defined symbols:
30.30/10.55	h, d, g
30.30/10.55	
30.30/10.55	They will be analysed ascendingly in the following order:
30.30/10.55	d < h
30.30/10.55	g < d
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(20)
30.30/10.55	Obligation:
30.30/10.55	TRS:
30.30/10.55	Rules:
30.30/10.55	h(e(x), y) -> h(d(x, y), s(y))
30.30/10.55	d(g(g(0', x), y), s(z)) -> g(e(x), d(g(g(0', x), y), z))
30.30/10.55	d(g(g(0', x), y), 0') -> e(y)
30.30/10.55	d(g(0', x), y) -> e(x)
30.30/10.55	d(g(x, y), z) -> g(d(x, z), e(y))
30.30/10.55	g(e(x), e(y)) -> e(g(x, y))
30.30/10.55	
30.30/10.55	Types:
30.30/10.55	h :: e:s:0' -> e:s:0' -> h
30.30/10.55	e :: e:s:0' -> e:s:0'
30.30/10.55	d :: e:s:0' -> e:s:0' -> e:s:0'
30.30/10.55	s :: e:s:0' -> e:s:0'
30.30/10.55	g :: e:s:0' -> e:s:0' -> e:s:0'
30.30/10.55	0' :: e:s:0'
30.30/10.55	hole_h1_0 :: h
30.30/10.55	hole_e:s:0'2_0 :: e:s:0'
30.30/10.55	gen_e:s:0'3_0 :: Nat -> e:s:0'
30.30/10.55	
30.30/10.55	
30.30/10.55	Generator Equations:
30.30/10.55	gen_e:s:0'3_0(0) <=> 0'
30.30/10.55	gen_e:s:0'3_0(+(x, 1)) <=> e(gen_e:s:0'3_0(x))
30.30/10.55	
30.30/10.55	
30.30/10.55	The following defined symbols remain to be analysed:
30.30/10.55	g, h, d
30.30/10.55	
30.30/10.55	They will be analysed ascendingly in the following order:
30.30/10.55	d < h
30.30/10.55	g < d
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(21) RewriteLemmaProof (LOWER BOUND(ID))
30.30/10.55	Proved the following rewrite lemma:
30.30/10.55	g(gen_e:s:0'3_0(+(1, n5_0)), gen_e:s:0'3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
30.30/10.55	
30.30/10.55	Induction Base:
30.30/10.55	g(gen_e:s:0'3_0(+(1, 0)), gen_e:s:0'3_0(+(1, 0)))
30.30/10.55	
30.30/10.55	Induction Step:
30.30/10.55	g(gen_e:s:0'3_0(+(1, +(n5_0, 1))), gen_e:s:0'3_0(+(1, +(n5_0, 1)))) ->_R^Omega(1)
30.30/10.55	e(g(gen_e:s:0'3_0(+(1, n5_0)), gen_e:s:0'3_0(+(1, n5_0)))) ->_IH
30.30/10.55	e(*4_0)
30.30/10.55	
30.30/10.55	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(22)
30.30/10.55	Complex Obligation (BEST)
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(23)
30.30/10.55	Obligation:
30.30/10.55	Proved the lower bound n^1 for the following obligation:
30.30/10.55	
30.30/10.55	TRS:
30.30/10.55	Rules:
30.30/10.55	h(e(x), y) -> h(d(x, y), s(y))
30.30/10.55	d(g(g(0', x), y), s(z)) -> g(e(x), d(g(g(0', x), y), z))
30.30/10.55	d(g(g(0', x), y), 0') -> e(y)
30.30/10.55	d(g(0', x), y) -> e(x)
30.30/10.55	d(g(x, y), z) -> g(d(x, z), e(y))
30.30/10.55	g(e(x), e(y)) -> e(g(x, y))
30.30/10.55	
30.30/10.55	Types:
30.30/10.55	h :: e:s:0' -> e:s:0' -> h
30.30/10.55	e :: e:s:0' -> e:s:0'
30.30/10.55	d :: e:s:0' -> e:s:0' -> e:s:0'
30.30/10.55	s :: e:s:0' -> e:s:0'
30.30/10.55	g :: e:s:0' -> e:s:0' -> e:s:0'
30.30/10.55	0' :: e:s:0'
30.30/10.55	hole_h1_0 :: h
30.30/10.55	hole_e:s:0'2_0 :: e:s:0'
30.30/10.55	gen_e:s:0'3_0 :: Nat -> e:s:0'
30.30/10.55	
30.30/10.55	
30.30/10.55	Generator Equations:
30.30/10.55	gen_e:s:0'3_0(0) <=> 0'
30.30/10.55	gen_e:s:0'3_0(+(x, 1)) <=> e(gen_e:s:0'3_0(x))
30.30/10.55	
30.30/10.55	
30.30/10.55	The following defined symbols remain to be analysed:
30.30/10.55	g, h, d
30.30/10.55	
30.30/10.55	They will be analysed ascendingly in the following order:
30.30/10.55	d < h
30.30/10.55	g < d
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(24) LowerBoundPropagationProof (FINISHED)
30.30/10.55	Propagated lower bound.
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(25)
30.30/10.55	BOUNDS(n^1, INF)
30.30/10.55	
30.30/10.55	----------------------------------------
30.30/10.55	
30.30/10.55	(26)
30.30/10.55	Obligation:
30.30/10.55	TRS:
30.30/10.56	Rules:
30.30/10.56	h(e(x), y) -> h(d(x, y), s(y))
30.30/10.56	d(g(g(0', x), y), s(z)) -> g(e(x), d(g(g(0', x), y), z))
30.30/10.56	d(g(g(0', x), y), 0') -> e(y)
30.30/10.56	d(g(0', x), y) -> e(x)
30.30/10.56	d(g(x, y), z) -> g(d(x, z), e(y))
30.30/10.56	g(e(x), e(y)) -> e(g(x, y))
30.30/10.56	
30.30/10.56	Types:
30.30/10.56	h :: e:s:0' -> e:s:0' -> h
30.30/10.56	e :: e:s:0' -> e:s:0'
30.30/10.56	d :: e:s:0' -> e:s:0' -> e:s:0'
30.30/10.56	s :: e:s:0' -> e:s:0'
30.30/10.56	g :: e:s:0' -> e:s:0' -> e:s:0'
30.30/10.56	0' :: e:s:0'
30.30/10.56	hole_h1_0 :: h
30.30/10.56	hole_e:s:0'2_0 :: e:s:0'
30.30/10.56	gen_e:s:0'3_0 :: Nat -> e:s:0'
30.30/10.56	
30.30/10.56	
30.30/10.56	Lemmas:
30.30/10.56	g(gen_e:s:0'3_0(+(1, n5_0)), gen_e:s:0'3_0(+(1, n5_0))) -> *4_0, rt in Omega(n5_0)
30.30/10.56	
30.30/10.56	
30.30/10.56	Generator Equations:
30.30/10.56	gen_e:s:0'3_0(0) <=> 0'
30.30/10.56	gen_e:s:0'3_0(+(x, 1)) <=> e(gen_e:s:0'3_0(x))
30.30/10.56	
30.30/10.56	
30.30/10.56	The following defined symbols remain to be analysed:
30.30/10.56	d, h
30.30/10.56	
30.30/10.56	They will be analysed ascendingly in the following order:
30.30/10.56	d < h
30.33/10.60	EOF