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