16.93/6.50	WORST_CASE(Omega(n^1), O(n^1))
16.93/6.50	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
16.93/6.50	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.93/6.50	
16.93/6.50	
16.93/6.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.93/6.50	
16.93/6.50	(0) CpxTRS
16.93/6.50	(1) DependencyGraphProof [UPPER BOUND(ID), 0 ms]
16.93/6.50	(2) CpxTRS
16.93/6.50	    (3) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
16.93/6.50	    (4) CpxTRS
16.93/6.50	    (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms]
16.93/6.50	    (6) CpxTRS
16.93/6.50	    (7) CpxTrsMatchBoundsTAProof [FINISHED, 18 ms]
16.93/6.50	    (8) BOUNDS(1, n^1)
16.93/6.50	(9) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
16.93/6.50	(10) TRS for Loop Detection
16.93/6.50	    (11) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
16.93/6.50	    (12) BEST
16.93/6.50	        (13) proven lower bound
16.93/6.50	            (14) LowerBoundPropagationProof [FINISHED, 0 ms]
16.93/6.50	            (15) BOUNDS(n^1, INF)
16.93/6.50	        (16) TRS for Loop Detection
16.93/6.50	
16.93/6.50	
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(0)
16.93/6.50	Obligation:
16.93/6.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.93/6.50	
16.93/6.50	
16.93/6.50	The TRS R consists of the following rules:
16.93/6.50	
16.93/6.50	   flatten(nil) -> nil
16.93/6.50	   flatten(unit(x)) -> flatten(x)
16.93/6.50	   flatten(++(x, y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(++(unit(x), y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(flatten(x)) -> flatten(x)
16.93/6.50	   rev(nil) -> nil
16.93/6.50	   rev(unit(x)) -> unit(x)
16.93/6.50	   rev(++(x, y)) -> ++(rev(y), rev(x))
16.93/6.50	   rev(rev(x)) -> x
16.93/6.50	   ++(x, nil) -> x
16.93/6.50	   ++(nil, y) -> y
16.93/6.50	   ++(++(x, y), z) -> ++(x, ++(y, z))
16.93/6.50	
16.93/6.50	S is empty.
16.93/6.50	Rewrite Strategy: FULL
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(1) DependencyGraphProof (UPPER BOUND(ID))
16.93/6.50	The following rules are not reachable from basic terms in the dependency graph and can be removed:
16.93/6.50	
16.93/6.50	rev(++(x, y)) -> ++(rev(y), rev(x))
16.93/6.50	rev(rev(x)) -> x
16.93/6.50	
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(2)
16.93/6.50	Obligation:
16.93/6.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
16.93/6.50	
16.93/6.50	
16.93/6.50	The TRS R consists of the following rules:
16.93/6.50	
16.93/6.50	   flatten(nil) -> nil
16.93/6.50	   flatten(unit(x)) -> flatten(x)
16.93/6.50	   flatten(++(x, y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(++(unit(x), y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(flatten(x)) -> flatten(x)
16.93/6.50	   rev(nil) -> nil
16.93/6.50	   rev(unit(x)) -> unit(x)
16.93/6.50	   ++(x, nil) -> x
16.93/6.50	   ++(nil, y) -> y
16.93/6.50	   ++(++(x, y), z) -> ++(x, ++(y, z))
16.93/6.50	
16.93/6.50	S is empty.
16.93/6.50	Rewrite Strategy: FULL
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(3) NestedDefinedSymbolProof (UPPER BOUND(ID))
16.93/6.50	The TRS does not nest defined symbols.
16.93/6.50	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
16.93/6.50	flatten(++(x, y)) -> ++(flatten(x), flatten(y))
16.93/6.50	flatten(++(unit(x), y)) -> ++(flatten(x), flatten(y))
16.93/6.50	flatten(flatten(x)) -> flatten(x)
16.93/6.50	++(++(x, y), z) -> ++(x, ++(y, z))
16.93/6.50	
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(4)
16.93/6.50	Obligation:
16.93/6.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
16.93/6.50	
16.93/6.50	
16.93/6.50	The TRS R consists of the following rules:
16.93/6.50	
16.93/6.50	   flatten(nil) -> nil
16.93/6.50	   flatten(unit(x)) -> flatten(x)
16.93/6.50	   rev(nil) -> nil
16.93/6.50	   rev(unit(x)) -> unit(x)
16.93/6.50	   ++(x, nil) -> x
16.93/6.50	   ++(nil, y) -> y
16.93/6.50	
16.93/6.50	S is empty.
16.93/6.50	Rewrite Strategy: FULL
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(5) RelTrsToTrsProof (UPPER BOUND(ID))
16.93/6.50	transformed relative TRS to TRS
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(6)
16.93/6.50	Obligation:
16.93/6.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1).
16.93/6.50	
16.93/6.50	
16.93/6.50	The TRS R consists of the following rules:
16.93/6.50	
16.93/6.50	   flatten(nil) -> nil
16.93/6.50	   flatten(unit(x)) -> flatten(x)
16.93/6.50	   rev(nil) -> nil
16.93/6.50	   rev(unit(x)) -> unit(x)
16.93/6.50	   ++(x, nil) -> x
16.93/6.50	   ++(nil, y) -> y
16.93/6.50	
16.93/6.50	S is empty.
16.93/6.50	Rewrite Strategy: FULL
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(7) CpxTrsMatchBoundsTAProof (FINISHED)
16.93/6.50	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. 
16.93/6.50	
16.93/6.50	The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 
16.93/6.50	final states : [1, 2, 3]
16.93/6.50	transitions: 
16.93/6.50	nil0() -> 0
16.93/6.50	unit0(0) -> 0
16.93/6.50	flatten0(0) -> 1
16.93/6.50	rev0(0) -> 2
16.93/6.50	++0(0, 0) -> 3
16.93/6.50	nil1() -> 1
16.93/6.50	flatten1(0) -> 1
16.93/6.50	nil1() -> 2
16.93/6.50	unit1(0) -> 2
16.93/6.50	0 -> 3
16.93/6.50	
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(8)
16.93/6.50	BOUNDS(1, n^1)
16.93/6.50	
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(9) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
16.93/6.50	Transformed a relative TRS into a decreasing-loop problem.
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(10)
16.93/6.50	Obligation:
16.93/6.50	Analyzing the following TRS for decreasing loops:
16.93/6.50	
16.93/6.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.93/6.50	
16.93/6.50	
16.93/6.50	The TRS R consists of the following rules:
16.93/6.50	
16.93/6.50	   flatten(nil) -> nil
16.93/6.50	   flatten(unit(x)) -> flatten(x)
16.93/6.50	   flatten(++(x, y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(++(unit(x), y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(flatten(x)) -> flatten(x)
16.93/6.50	   rev(nil) -> nil
16.93/6.50	   rev(unit(x)) -> unit(x)
16.93/6.50	   rev(++(x, y)) -> ++(rev(y), rev(x))
16.93/6.50	   rev(rev(x)) -> x
16.93/6.50	   ++(x, nil) -> x
16.93/6.50	   ++(nil, y) -> y
16.93/6.50	   ++(++(x, y), z) -> ++(x, ++(y, z))
16.93/6.50	
16.93/6.50	S is empty.
16.93/6.50	Rewrite Strategy: FULL
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(11) DecreasingLoopProof (LOWER BOUND(ID))
16.93/6.50	The following loop(s) give(s) rise to the lower bound Omega(n^1):
16.93/6.50	
16.93/6.50	The rewrite sequence
16.93/6.50	
16.93/6.50	flatten(unit(x)) ->^+ flatten(x)
16.93/6.50	
16.93/6.50	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
16.93/6.50	
16.93/6.50	The pumping substitution is [x / unit(x)].
16.93/6.50	
16.93/6.50	The result substitution is [ ].
16.93/6.50	
16.93/6.50	
16.93/6.50	
16.93/6.50	
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(12)
16.93/6.50	Complex Obligation (BEST)
16.93/6.50	
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(13)
16.93/6.50	Obligation:
16.93/6.50	Proved the lower bound n^1 for the following obligation:
16.93/6.50	
16.93/6.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.93/6.50	
16.93/6.50	
16.93/6.50	The TRS R consists of the following rules:
16.93/6.50	
16.93/6.50	   flatten(nil) -> nil
16.93/6.50	   flatten(unit(x)) -> flatten(x)
16.93/6.50	   flatten(++(x, y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(++(unit(x), y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(flatten(x)) -> flatten(x)
16.93/6.50	   rev(nil) -> nil
16.93/6.50	   rev(unit(x)) -> unit(x)
16.93/6.50	   rev(++(x, y)) -> ++(rev(y), rev(x))
16.93/6.50	   rev(rev(x)) -> x
16.93/6.50	   ++(x, nil) -> x
16.93/6.50	   ++(nil, y) -> y
16.93/6.50	   ++(++(x, y), z) -> ++(x, ++(y, z))
16.93/6.50	
16.93/6.50	S is empty.
16.93/6.50	Rewrite Strategy: FULL
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(14) LowerBoundPropagationProof (FINISHED)
16.93/6.50	Propagated lower bound.
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(15)
16.93/6.50	BOUNDS(n^1, INF)
16.93/6.50	
16.93/6.50	----------------------------------------
16.93/6.50	
16.93/6.50	(16)
16.93/6.50	Obligation:
16.93/6.50	Analyzing the following TRS for decreasing loops:
16.93/6.50	
16.93/6.50	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1).
16.93/6.50	
16.93/6.50	
16.93/6.50	The TRS R consists of the following rules:
16.93/6.50	
16.93/6.50	   flatten(nil) -> nil
16.93/6.50	   flatten(unit(x)) -> flatten(x)
16.93/6.50	   flatten(++(x, y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(++(unit(x), y)) -> ++(flatten(x), flatten(y))
16.93/6.50	   flatten(flatten(x)) -> flatten(x)
16.93/6.50	   rev(nil) -> nil
16.93/6.50	   rev(unit(x)) -> unit(x)
16.93/6.50	   rev(++(x, y)) -> ++(rev(y), rev(x))
16.93/6.50	   rev(rev(x)) -> x
16.93/6.50	   ++(x, nil) -> x
16.93/6.50	   ++(nil, y) -> y
16.93/6.50	   ++(++(x, y), z) -> ++(x, ++(y, z))
16.93/6.50	
16.93/6.50	S is empty.
16.93/6.50	Rewrite Strategy: FULL
17.05/6.54	EOF