1132.03/295.20	WORST_CASE(Omega(n^1), ?)
1132.38/295.32	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
1132.38/295.32	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1132.38/295.32	
1132.38/295.32	
1132.38/295.32	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1132.38/295.32	
1132.38/295.32	(0) CpxTRS
1132.38/295.32	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
1132.38/295.32	(2) TRS for Loop Detection
1132.38/295.32	(3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
1132.38/295.32	(4) BEST
1132.38/295.32	    (5) proven lower bound
1132.38/295.32	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
1132.38/295.32	        (7) BOUNDS(n^1, INF)
1132.38/295.32	    (8) TRS for Loop Detection
1132.38/295.32	
1132.38/295.32	
1132.38/295.32	----------------------------------------
1132.38/295.32	
1132.38/295.32	(0)
1132.38/295.32	Obligation:
1132.38/295.32	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1132.38/295.32	
1132.38/295.32	
1132.38/295.32	The TRS R consists of the following rules:
1132.38/295.32	
1132.38/295.32	   0(#) -> #
1132.38/295.32	   +(#, x) -> x
1132.38/295.32	   +(x, #) -> x
1132.38/295.32	   +(0(x), 0(y)) -> 0(+(x, y))
1132.38/295.32	   +(0(x), 1(y)) -> 1(+(x, y))
1132.38/295.32	   +(1(x), 0(y)) -> 1(+(x, y))
1132.38/295.32	   +(0(x), j(y)) -> j(+(x, y))
1132.38/295.32	   +(j(x), 0(y)) -> j(+(x, y))
1132.38/295.32	   +(1(x), 1(y)) -> j(+(+(x, y), 1(#)))
1132.38/295.32	   +(j(x), j(y)) -> 1(+(+(x, y), j(#)))
1132.38/295.32	   +(1(x), j(y)) -> 0(+(x, y))
1132.38/295.32	   +(j(x), 1(y)) -> 0(+(x, y))
1132.38/295.32	   +(+(x, y), z) -> +(x, +(y, z))
1132.38/295.32	   opp(#) -> #
1132.38/295.32	   opp(0(x)) -> 0(opp(x))
1132.38/295.32	   opp(1(x)) -> j(opp(x))
1132.38/295.32	   opp(j(x)) -> 1(opp(x))
1132.38/295.32	   -(x, y) -> +(x, opp(y))
1132.38/295.32	   *(#, x) -> #
1132.38/295.32	   *(0(x), y) -> 0(*(x, y))
1132.38/295.32	   *(1(x), y) -> +(0(*(x, y)), y)
1132.38/295.32	   *(j(x), y) -> -(0(*(x, y)), y)
1132.38/295.32	   *(*(x, y), z) -> *(x, *(y, z))
1132.38/295.32	   *(+(x, y), z) -> +(*(x, z), *(y, z))
1132.38/295.32	   *(x, +(y, z)) -> +(*(x, y), *(x, z))
1132.38/295.32	
1132.38/295.32	S is empty.
1132.38/295.32	Rewrite Strategy: FULL
1132.38/295.32	----------------------------------------
1132.38/295.32	
1132.38/295.32	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
1132.38/295.32	Transformed a relative TRS into a decreasing-loop problem.
1132.38/295.32	----------------------------------------
1132.38/295.32	
1132.38/295.32	(2)
1132.38/295.32	Obligation:
1132.38/295.32	Analyzing the following TRS for decreasing loops:
1132.38/295.32	
1132.38/295.32	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1132.38/295.32	
1132.38/295.32	
1132.38/295.32	The TRS R consists of the following rules:
1132.38/295.32	
1132.38/295.32	   0(#) -> #
1132.38/295.32	   +(#, x) -> x
1132.38/295.32	   +(x, #) -> x
1132.38/295.32	   +(0(x), 0(y)) -> 0(+(x, y))
1132.38/295.32	   +(0(x), 1(y)) -> 1(+(x, y))
1132.38/295.32	   +(1(x), 0(y)) -> 1(+(x, y))
1132.38/295.32	   +(0(x), j(y)) -> j(+(x, y))
1132.38/295.32	   +(j(x), 0(y)) -> j(+(x, y))
1132.38/295.32	   +(1(x), 1(y)) -> j(+(+(x, y), 1(#)))
1132.38/295.32	   +(j(x), j(y)) -> 1(+(+(x, y), j(#)))
1132.38/295.32	   +(1(x), j(y)) -> 0(+(x, y))
1132.38/295.32	   +(j(x), 1(y)) -> 0(+(x, y))
1132.38/295.32	   +(+(x, y), z) -> +(x, +(y, z))
1132.38/295.32	   opp(#) -> #
1132.38/295.32	   opp(0(x)) -> 0(opp(x))
1132.38/295.32	   opp(1(x)) -> j(opp(x))
1132.38/295.32	   opp(j(x)) -> 1(opp(x))
1132.38/295.32	   -(x, y) -> +(x, opp(y))
1132.38/295.32	   *(#, x) -> #
1132.38/295.32	   *(0(x), y) -> 0(*(x, y))
1132.38/295.32	   *(1(x), y) -> +(0(*(x, y)), y)
1132.38/295.32	   *(j(x), y) -> -(0(*(x, y)), y)
1132.38/295.32	   *(*(x, y), z) -> *(x, *(y, z))
1132.38/295.32	   *(+(x, y), z) -> +(*(x, z), *(y, z))
1132.38/295.32	   *(x, +(y, z)) -> +(*(x, y), *(x, z))
1132.38/295.32	
1132.38/295.32	S is empty.
1132.38/295.32	Rewrite Strategy: FULL
1132.38/295.32	----------------------------------------
1132.38/295.32	
1132.38/295.32	(3) DecreasingLoopProof (LOWER BOUND(ID))
1132.38/295.32	The following loop(s) give(s) rise to the lower bound Omega(n^1):
1132.38/295.32	
1132.38/295.32	The rewrite sequence
1132.38/295.32	
1132.38/295.32	+(j(x), j(y)) ->^+ 1(+(+(x, y), j(#)))
1132.38/295.32	
1132.38/295.32	gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0].
1132.38/295.32	
1132.38/295.32	The pumping substitution is [x / j(x), y / j(y)].
1132.38/295.32	
1132.38/295.32	The result substitution is [ ].
1132.38/295.32	
1132.38/295.32	
1132.38/295.32	
1132.38/295.32	
1132.38/295.32	----------------------------------------
1132.38/295.32	
1132.38/295.32	(4)
1132.38/295.32	Complex Obligation (BEST)
1132.38/295.32	
1132.38/295.32	----------------------------------------
1132.38/295.32	
1132.38/295.32	(5)
1132.38/295.32	Obligation:
1132.38/295.32	Proved the lower bound n^1 for the following obligation:
1132.38/295.32	
1132.38/295.32	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1132.38/295.32	
1132.38/295.32	
1132.38/295.32	The TRS R consists of the following rules:
1132.38/295.32	
1132.38/295.32	   0(#) -> #
1132.38/295.32	   +(#, x) -> x
1132.38/295.32	   +(x, #) -> x
1132.38/295.32	   +(0(x), 0(y)) -> 0(+(x, y))
1132.38/295.32	   +(0(x), 1(y)) -> 1(+(x, y))
1132.38/295.32	   +(1(x), 0(y)) -> 1(+(x, y))
1132.38/295.32	   +(0(x), j(y)) -> j(+(x, y))
1132.38/295.32	   +(j(x), 0(y)) -> j(+(x, y))
1132.38/295.32	   +(1(x), 1(y)) -> j(+(+(x, y), 1(#)))
1132.38/295.32	   +(j(x), j(y)) -> 1(+(+(x, y), j(#)))
1132.38/295.32	   +(1(x), j(y)) -> 0(+(x, y))
1132.38/295.32	   +(j(x), 1(y)) -> 0(+(x, y))
1132.38/295.32	   +(+(x, y), z) -> +(x, +(y, z))
1132.38/295.32	   opp(#) -> #
1132.38/295.32	   opp(0(x)) -> 0(opp(x))
1132.38/295.32	   opp(1(x)) -> j(opp(x))
1132.38/295.32	   opp(j(x)) -> 1(opp(x))
1132.38/295.32	   -(x, y) -> +(x, opp(y))
1132.38/295.32	   *(#, x) -> #
1132.38/295.32	   *(0(x), y) -> 0(*(x, y))
1132.38/295.32	   *(1(x), y) -> +(0(*(x, y)), y)
1132.38/295.32	   *(j(x), y) -> -(0(*(x, y)), y)
1132.38/295.32	   *(*(x, y), z) -> *(x, *(y, z))
1132.38/295.32	   *(+(x, y), z) -> +(*(x, z), *(y, z))
1132.38/295.32	   *(x, +(y, z)) -> +(*(x, y), *(x, z))
1132.38/295.32	
1132.38/295.32	S is empty.
1132.38/295.32	Rewrite Strategy: FULL
1132.38/295.32	----------------------------------------
1132.38/295.32	
1132.38/295.32	(6) LowerBoundPropagationProof (FINISHED)
1132.38/295.32	Propagated lower bound.
1132.38/295.32	----------------------------------------
1132.38/295.32	
1132.38/295.32	(7)
1132.38/295.32	BOUNDS(n^1, INF)
1132.38/295.32	
1132.38/295.32	----------------------------------------
1132.38/295.32	
1132.38/295.32	(8)
1132.38/295.32	Obligation:
1132.38/295.32	Analyzing the following TRS for decreasing loops:
1132.38/295.32	
1132.38/295.32	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1132.38/295.32	
1132.38/295.32	
1132.38/295.32	The TRS R consists of the following rules:
1132.38/295.32	
1132.38/295.32	   0(#) -> #
1132.38/295.32	   +(#, x) -> x
1132.38/295.32	   +(x, #) -> x
1132.38/295.32	   +(0(x), 0(y)) -> 0(+(x, y))
1132.38/295.32	   +(0(x), 1(y)) -> 1(+(x, y))
1132.38/295.32	   +(1(x), 0(y)) -> 1(+(x, y))
1132.38/295.32	   +(0(x), j(y)) -> j(+(x, y))
1132.38/295.32	   +(j(x), 0(y)) -> j(+(x, y))
1132.38/295.32	   +(1(x), 1(y)) -> j(+(+(x, y), 1(#)))
1132.38/295.32	   +(j(x), j(y)) -> 1(+(+(x, y), j(#)))
1132.38/295.32	   +(1(x), j(y)) -> 0(+(x, y))
1132.38/295.32	   +(j(x), 1(y)) -> 0(+(x, y))
1132.38/295.32	   +(+(x, y), z) -> +(x, +(y, z))
1132.38/295.32	   opp(#) -> #
1132.38/295.32	   opp(0(x)) -> 0(opp(x))
1132.38/295.32	   opp(1(x)) -> j(opp(x))
1132.38/295.32	   opp(j(x)) -> 1(opp(x))
1132.38/295.32	   -(x, y) -> +(x, opp(y))
1132.38/295.32	   *(#, x) -> #
1132.38/295.32	   *(0(x), y) -> 0(*(x, y))
1132.38/295.32	   *(1(x), y) -> +(0(*(x, y)), y)
1132.38/295.32	   *(j(x), y) -> -(0(*(x, y)), y)
1132.38/295.32	   *(*(x, y), z) -> *(x, *(y, z))
1132.38/295.32	   *(+(x, y), z) -> +(*(x, z), *(y, z))
1132.38/295.32	   *(x, +(y, z)) -> +(*(x, y), *(x, z))
1132.38/295.32	
1132.38/295.32	S is empty.
1132.38/295.32	Rewrite Strategy: FULL
1132.67/295.39	EOF