6.62/2.48	WORST_CASE(Omega(n^1), O(n^1))
6.62/2.49	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.62/2.49	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.62/2.49	
6.62/2.49	
6.62/2.49	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
6.62/2.49	
6.62/2.49	(0) CpxTRS
6.62/2.49	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
6.62/2.49	(2) CpxTRS
6.62/2.49	    (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
6.62/2.49	    (4) CpxTRS
6.62/2.49	    (5) CpxTrsMatchBoundsTAProof [FINISHED, 19 ms]
6.62/2.49	    (6) BOUNDS(1, n^1)
6.62/2.49	(7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
6.62/2.49	(8) CpxTRS
6.62/2.49	    (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
6.62/2.49	    (10) typed CpxTrs
6.62/2.49	    (11) OrderProof [LOWER BOUND(ID), 0 ms]
6.62/2.49	    (12) typed CpxTrs
6.62/2.49	    (13) RewriteLemmaProof [LOWER BOUND(ID), 453 ms]
6.62/2.49	    (14) proven lower bound
6.62/2.49	    (15) LowerBoundPropagationProof [FINISHED, 0 ms]
6.62/2.49	    (16) BOUNDS(n^1, INF)
6.62/2.49	
6.62/2.49	
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(0)
6.62/2.49	Obligation:
6.62/2.49	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
6.62/2.49	
6.62/2.49	
6.62/2.49	The TRS R consists of the following rules:
6.62/2.49	
6.62/2.49	   minus(minus(x)) -> x
6.62/2.49	   minus(h(x)) -> h(minus(x))
6.62/2.49	   minus(f(x, y)) -> f(minus(y), minus(x))
6.62/2.49	
6.62/2.49	S is empty.
6.62/2.49	Rewrite Strategy: FULL
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
6.62/2.49	The TRS does not nest defined symbols.
6.62/2.49	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
6.62/2.49	minus(minus(x)) -> x
6.62/2.49	
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(2)
6.62/2.49	Obligation:
6.62/2.49	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
6.62/2.49	
6.62/2.49	
6.62/2.49	The TRS R consists of the following rules:
6.62/2.49	
6.62/2.49	   minus(h(x)) -> h(minus(x))
6.62/2.49	   minus(f(x, y)) -> f(minus(y), minus(x))
6.62/2.49	
6.62/2.49	S is empty.
6.62/2.49	Rewrite Strategy: FULL
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(3) RelTrsToTrsProof (UPPER BOUND(ID))
6.62/2.49	transformed relative TRS to TRS
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(4)
6.62/2.49	Obligation:
6.62/2.49	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
6.62/2.49	
6.62/2.49	
6.62/2.49	The TRS R consists of the following rules:
6.62/2.49	
6.62/2.49	   minus(h(x)) -> h(minus(x))
6.62/2.49	   minus(f(x, y)) -> f(minus(y), minus(x))
6.62/2.49	
6.62/2.49	S is empty.
6.62/2.49	Rewrite Strategy: FULL
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(5) CpxTrsMatchBoundsTAProof (FINISHED)
6.62/2.49	A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 1. 
6.62/2.49	
6.62/2.49	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
6.62/2.49	final states : [1]
6.62/2.49	transitions: 
6.62/2.49	h0(0) -> 0
6.62/2.49	f0(0, 0) -> 0
6.62/2.49	minus0(0) -> 1
6.62/2.49	minus1(0) -> 2
6.62/2.49	h1(2) -> 1
6.62/2.49	minus1(0) -> 3
6.62/2.49	minus1(0) -> 4
6.62/2.49	f1(3, 4) -> 1
6.62/2.49	h1(2) -> 2
6.62/2.49	h1(2) -> 3
6.62/2.49	h1(2) -> 4
6.62/2.49	f1(3, 4) -> 2
6.62/2.49	f1(3, 4) -> 3
6.62/2.49	f1(3, 4) -> 4
6.62/2.49	
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(6)
6.62/2.49	BOUNDS(1, n^1)
6.62/2.49	
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(7) RenamingProof (BOTH BOUNDS(ID, ID))
6.62/2.49	Renamed function symbols to avoid clashes with predefined symbol.
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(8)
6.62/2.49	Obligation:
6.62/2.49	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
6.62/2.49	
6.62/2.49	
6.62/2.49	The TRS R consists of the following rules:
6.62/2.49	
6.62/2.49	   minus(minus(x)) -> x
6.62/2.49	   minus(h(x)) -> h(minus(x))
6.62/2.49	   minus(f(x, y)) -> f(minus(y), minus(x))
6.62/2.49	
6.62/2.49	S is empty.
6.62/2.49	Rewrite Strategy: FULL
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(9) TypeInferenceProof (BOTH BOUNDS(ID, ID))
6.62/2.49	Infered types.
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(10)
6.62/2.49	Obligation:
6.62/2.49	TRS:
6.62/2.49	Rules:
6.62/2.49	minus(minus(x)) -> x
6.62/2.49	minus(h(x)) -> h(minus(x))
6.62/2.49	minus(f(x, y)) -> f(minus(y), minus(x))
6.62/2.49	
6.62/2.49	Types:
6.62/2.49	minus :: h:f -> h:f
6.62/2.49	h :: h:f -> h:f
6.62/2.49	f :: h:f -> h:f -> h:f
6.62/2.49	hole_h:f1_0 :: h:f
6.62/2.49	gen_h:f2_0 :: Nat -> h:f
6.62/2.49	
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(11) OrderProof (LOWER BOUND(ID))
6.62/2.49	Heuristically decided to analyse the following defined symbols:
6.62/2.49	minus
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(12)
6.62/2.49	Obligation:
6.62/2.49	TRS:
6.62/2.49	Rules:
6.62/2.49	minus(minus(x)) -> x
6.62/2.49	minus(h(x)) -> h(minus(x))
6.62/2.49	minus(f(x, y)) -> f(minus(y), minus(x))
6.62/2.49	
6.62/2.49	Types:
6.62/2.49	minus :: h:f -> h:f
6.62/2.49	h :: h:f -> h:f
6.62/2.49	f :: h:f -> h:f -> h:f
6.62/2.49	hole_h:f1_0 :: h:f
6.62/2.49	gen_h:f2_0 :: Nat -> h:f
6.62/2.49	
6.62/2.49	
6.62/2.49	Generator Equations:
6.62/2.49	gen_h:f2_0(0) <=> hole_h:f1_0
6.62/2.49	gen_h:f2_0(+(x, 1)) <=> h(gen_h:f2_0(x))
6.62/2.49	
6.62/2.49	
6.62/2.49	The following defined symbols remain to be analysed:
6.62/2.49	minus
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(13) RewriteLemmaProof (LOWER BOUND(ID))
6.62/2.49	Proved the following rewrite lemma:
6.62/2.49	minus(gen_h:f2_0(+(1, n4_0))) -> *3_0, rt in Omega(n4_0)
6.62/2.49	
6.62/2.49	Induction Base:
6.62/2.49	minus(gen_h:f2_0(+(1, 0)))
6.62/2.49	
6.62/2.49	Induction Step:
6.62/2.49	minus(gen_h:f2_0(+(1, +(n4_0, 1)))) ->_R^Omega(1)
6.62/2.49	h(minus(gen_h:f2_0(+(1, n4_0)))) ->_IH
6.62/2.49	h(*3_0)
6.62/2.49	
6.62/2.49	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(14)
6.62/2.49	Obligation:
6.62/2.49	Proved the lower bound n^1 for the following obligation:
6.62/2.49	
6.62/2.49	TRS:
6.62/2.49	Rules:
6.62/2.49	minus(minus(x)) -> x
6.62/2.49	minus(h(x)) -> h(minus(x))
6.62/2.49	minus(f(x, y)) -> f(minus(y), minus(x))
6.62/2.49	
6.62/2.49	Types:
6.62/2.49	minus :: h:f -> h:f
6.62/2.49	h :: h:f -> h:f
6.62/2.49	f :: h:f -> h:f -> h:f
6.62/2.49	hole_h:f1_0 :: h:f
6.62/2.49	gen_h:f2_0 :: Nat -> h:f
6.62/2.49	
6.62/2.49	
6.62/2.49	Generator Equations:
6.62/2.49	gen_h:f2_0(0) <=> hole_h:f1_0
6.62/2.49	gen_h:f2_0(+(x, 1)) <=> h(gen_h:f2_0(x))
6.62/2.49	
6.62/2.49	
6.62/2.49	The following defined symbols remain to be analysed:
6.62/2.49	minus
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(15) LowerBoundPropagationProof (FINISHED)
6.62/2.49	Propagated lower bound.
6.62/2.49	----------------------------------------
6.62/2.49	
6.62/2.49	(16)
6.62/2.49	BOUNDS(n^1, INF)
6.85/2.52	EOF