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