132.03/34.70	WORST_CASE(NON_POLY, ?)
132.03/34.71	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
132.03/34.71	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
132.03/34.71	
132.03/34.71	
132.03/34.71	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
132.03/34.71	
132.03/34.71	(0) CpxRelTRS
132.03/34.71	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 867 ms]
132.03/34.71	(2) CpxRelTRS
132.03/34.71	(3) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
132.03/34.71	(4) TRS for Loop Detection
132.03/34.71	(5) DecreasingLoopProof [LOWER BOUND(ID), 311 ms]
132.03/34.71	(6) BEST
132.03/34.71	    (7) proven lower bound
132.03/34.71	        (8) LowerBoundPropagationProof [FINISHED, 0 ms]
132.03/34.71	        (9) BOUNDS(n^1, INF)
132.03/34.71	    (10) TRS for Loop Detection
132.03/34.71	        (11) DecreasingLoopProof [FINISHED, 20.4 s]
132.03/34.71	        (12) BOUNDS(EXP, INF)
132.03/34.71	
132.03/34.71	
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(0)
132.03/34.71	Obligation:
132.03/34.71	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
132.03/34.71	
132.03/34.71	
132.03/34.71	The TRS R consists of the following rules:
132.03/34.71	
132.03/34.71	   head(Cons(x, xs)) -> x
132.03/34.71	   e(Cons(F, Nil), b) -> False
132.03/34.71	   e(Cons(T, Nil), b) -> False
132.03/34.71	   e(Cons(B, Nil), b) -> False
132.03/34.71	   e(Cons(A, Nil), b) -> e[Match][Cons][Ite][True][Match](A, Nil, b)
132.03/34.71	   e(Cons(F, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(T, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(B, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(A, Cons(x, xs)), b) -> False
132.03/34.71	   equal(F, F) -> True
132.03/34.71	   equal(F, T) -> False
132.03/34.71	   equal(F, B) -> False
132.03/34.71	   equal(F, A) -> False
132.03/34.71	   equal(T, F) -> False
132.03/34.71	   equal(T, T) -> True
132.03/34.71	   equal(T, B) -> False
132.03/34.71	   equal(T, A) -> False
132.03/34.71	   equal(B, F) -> False
132.03/34.71	   equal(B, T) -> False
132.03/34.71	   equal(B, B) -> True
132.03/34.71	   equal(B, A) -> False
132.03/34.71	   equal(A, F) -> False
132.03/34.71	   equal(A, T) -> False
132.03/34.71	   equal(A, B) -> False
132.03/34.71	   equal(A, A) -> True
132.03/34.71	   notEmpty(Cons(x, xs)) -> True
132.03/34.71	   notEmpty(Nil) -> False
132.03/34.71	   e(Nil, b) -> False
132.03/34.71	   t(x, y) -> t[Ite](e(x, y), x, y)
132.03/34.71	   r(x, y) -> r[Ite](e(x, y), x, y)
132.03/34.71	   q(x, y) -> q[Ite](e(x, y), x, y)
132.03/34.71	   p(x, y) -> p[Ite](e(x, y), x, y)
132.03/34.71	   goal(x, y) -> q(x, y)
132.03/34.71	
132.03/34.71	The (relative) TRS S consists of the following rules:
132.03/34.71	
132.03/34.71	   and(False, False) -> False
132.03/34.71	   and(True, False) -> False
132.03/34.71	   and(False, True) -> False
132.03/34.71	   and(True, True) -> True
132.03/34.71	   q[Ite](False, x', Cons(F, Cons(F, xs))) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(F, Cons(F, xs))), q(x', Cons(F, xs))), x', Cons(F, Cons(F, xs)))
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x', Cons(F, Nil)) -> q[Ite][False][Ite](and(True, and(True, and(False, equal(head(Nil), F)))), x', Cons(F, Nil))
132.03/34.71	   q[Ite](False, x', Cons(T, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(T, Nil))
132.03/34.71	   q[Ite](False, x', Cons(B, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(B, Nil))
132.03/34.71	   q[Ite](False, x', Cons(A, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(A, Nil))
132.03/34.71	   r[Ite](False, x', Cons(F, xs)) -> r[Ite][False][Ite][True][Ite](and(q(x', xs), r(x', xs)), x', Cons(F, xs))
132.03/34.71	   r[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   p[Ite](False, x', Cons(F, xs)) -> and(r(x', Cons(F, xs)), p(x', xs))
132.03/34.71	   p[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   q[Ite][False][Ite](True, x', Cons(x, xs)) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(x, xs)), q(x', xs)), x', Cons(x, xs))
132.03/34.71	   t[Ite](False, x, y) -> True
132.03/34.71	   t[Ite](True, x, y) -> True
132.03/34.71	   r[Ite](True, x, y) -> True
132.03/34.71	   q[Ite](True, x, y) -> True
132.03/34.71	   q[Ite][False][Ite](False, x, y) -> False
132.03/34.71	   p[Ite](True, x, y) -> True
132.03/34.71	
132.03/34.71	Rewrite Strategy: INNERMOST
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
132.03/34.71	proved termination of relative rules
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(2)
132.03/34.71	Obligation:
132.03/34.71	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
132.03/34.71	
132.03/34.71	
132.03/34.71	The TRS R consists of the following rules:
132.03/34.71	
132.03/34.71	   head(Cons(x, xs)) -> x
132.03/34.71	   e(Cons(F, Nil), b) -> False
132.03/34.71	   e(Cons(T, Nil), b) -> False
132.03/34.71	   e(Cons(B, Nil), b) -> False
132.03/34.71	   e(Cons(A, Nil), b) -> e[Match][Cons][Ite][True][Match](A, Nil, b)
132.03/34.71	   e(Cons(F, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(T, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(B, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(A, Cons(x, xs)), b) -> False
132.03/34.71	   equal(F, F) -> True
132.03/34.71	   equal(F, T) -> False
132.03/34.71	   equal(F, B) -> False
132.03/34.71	   equal(F, A) -> False
132.03/34.71	   equal(T, F) -> False
132.03/34.71	   equal(T, T) -> True
132.03/34.71	   equal(T, B) -> False
132.03/34.71	   equal(T, A) -> False
132.03/34.71	   equal(B, F) -> False
132.03/34.71	   equal(B, T) -> False
132.03/34.71	   equal(B, B) -> True
132.03/34.71	   equal(B, A) -> False
132.03/34.71	   equal(A, F) -> False
132.03/34.71	   equal(A, T) -> False
132.03/34.71	   equal(A, B) -> False
132.03/34.71	   equal(A, A) -> True
132.03/34.71	   notEmpty(Cons(x, xs)) -> True
132.03/34.71	   notEmpty(Nil) -> False
132.03/34.71	   e(Nil, b) -> False
132.03/34.71	   t(x, y) -> t[Ite](e(x, y), x, y)
132.03/34.71	   r(x, y) -> r[Ite](e(x, y), x, y)
132.03/34.71	   q(x, y) -> q[Ite](e(x, y), x, y)
132.03/34.71	   p(x, y) -> p[Ite](e(x, y), x, y)
132.03/34.71	   goal(x, y) -> q(x, y)
132.03/34.71	
132.03/34.71	The (relative) TRS S consists of the following rules:
132.03/34.71	
132.03/34.71	   and(False, False) -> False
132.03/34.71	   and(True, False) -> False
132.03/34.71	   and(False, True) -> False
132.03/34.71	   and(True, True) -> True
132.03/34.71	   q[Ite](False, x', Cons(F, Cons(F, xs))) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(F, Cons(F, xs))), q(x', Cons(F, xs))), x', Cons(F, Cons(F, xs)))
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x', Cons(F, Nil)) -> q[Ite][False][Ite](and(True, and(True, and(False, equal(head(Nil), F)))), x', Cons(F, Nil))
132.03/34.71	   q[Ite](False, x', Cons(T, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(T, Nil))
132.03/34.71	   q[Ite](False, x', Cons(B, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(B, Nil))
132.03/34.71	   q[Ite](False, x', Cons(A, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(A, Nil))
132.03/34.71	   r[Ite](False, x', Cons(F, xs)) -> r[Ite][False][Ite][True][Ite](and(q(x', xs), r(x', xs)), x', Cons(F, xs))
132.03/34.71	   r[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   p[Ite](False, x', Cons(F, xs)) -> and(r(x', Cons(F, xs)), p(x', xs))
132.03/34.71	   p[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   q[Ite][False][Ite](True, x', Cons(x, xs)) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(x, xs)), q(x', xs)), x', Cons(x, xs))
132.03/34.71	   t[Ite](False, x, y) -> True
132.03/34.71	   t[Ite](True, x, y) -> True
132.03/34.71	   r[Ite](True, x, y) -> True
132.03/34.71	   q[Ite](True, x, y) -> True
132.03/34.71	   q[Ite][False][Ite](False, x, y) -> False
132.03/34.71	   p[Ite](True, x, y) -> True
132.03/34.71	
132.03/34.71	Rewrite Strategy: INNERMOST
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(3) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
132.03/34.71	Transformed a relative TRS into a decreasing-loop problem.
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(4)
132.03/34.71	Obligation:
132.03/34.71	Analyzing the following TRS for decreasing loops:
132.03/34.71	
132.03/34.71	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
132.03/34.71	
132.03/34.71	
132.03/34.71	The TRS R consists of the following rules:
132.03/34.71	
132.03/34.71	   head(Cons(x, xs)) -> x
132.03/34.71	   e(Cons(F, Nil), b) -> False
132.03/34.71	   e(Cons(T, Nil), b) -> False
132.03/34.71	   e(Cons(B, Nil), b) -> False
132.03/34.71	   e(Cons(A, Nil), b) -> e[Match][Cons][Ite][True][Match](A, Nil, b)
132.03/34.71	   e(Cons(F, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(T, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(B, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(A, Cons(x, xs)), b) -> False
132.03/34.71	   equal(F, F) -> True
132.03/34.71	   equal(F, T) -> False
132.03/34.71	   equal(F, B) -> False
132.03/34.71	   equal(F, A) -> False
132.03/34.71	   equal(T, F) -> False
132.03/34.71	   equal(T, T) -> True
132.03/34.71	   equal(T, B) -> False
132.03/34.71	   equal(T, A) -> False
132.03/34.71	   equal(B, F) -> False
132.03/34.71	   equal(B, T) -> False
132.03/34.71	   equal(B, B) -> True
132.03/34.71	   equal(B, A) -> False
132.03/34.71	   equal(A, F) -> False
132.03/34.71	   equal(A, T) -> False
132.03/34.71	   equal(A, B) -> False
132.03/34.71	   equal(A, A) -> True
132.03/34.71	   notEmpty(Cons(x, xs)) -> True
132.03/34.71	   notEmpty(Nil) -> False
132.03/34.71	   e(Nil, b) -> False
132.03/34.71	   t(x, y) -> t[Ite](e(x, y), x, y)
132.03/34.71	   r(x, y) -> r[Ite](e(x, y), x, y)
132.03/34.71	   q(x, y) -> q[Ite](e(x, y), x, y)
132.03/34.71	   p(x, y) -> p[Ite](e(x, y), x, y)
132.03/34.71	   goal(x, y) -> q(x, y)
132.03/34.71	
132.03/34.71	The (relative) TRS S consists of the following rules:
132.03/34.71	
132.03/34.71	   and(False, False) -> False
132.03/34.71	   and(True, False) -> False
132.03/34.71	   and(False, True) -> False
132.03/34.71	   and(True, True) -> True
132.03/34.71	   q[Ite](False, x', Cons(F, Cons(F, xs))) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(F, Cons(F, xs))), q(x', Cons(F, xs))), x', Cons(F, Cons(F, xs)))
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x', Cons(F, Nil)) -> q[Ite][False][Ite](and(True, and(True, and(False, equal(head(Nil), F)))), x', Cons(F, Nil))
132.03/34.71	   q[Ite](False, x', Cons(T, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(T, Nil))
132.03/34.71	   q[Ite](False, x', Cons(B, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(B, Nil))
132.03/34.71	   q[Ite](False, x', Cons(A, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(A, Nil))
132.03/34.71	   r[Ite](False, x', Cons(F, xs)) -> r[Ite][False][Ite][True][Ite](and(q(x', xs), r(x', xs)), x', Cons(F, xs))
132.03/34.71	   r[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   p[Ite](False, x', Cons(F, xs)) -> and(r(x', Cons(F, xs)), p(x', xs))
132.03/34.71	   p[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   q[Ite][False][Ite](True, x', Cons(x, xs)) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(x, xs)), q(x', xs)), x', Cons(x, xs))
132.03/34.71	   t[Ite](False, x, y) -> True
132.03/34.71	   t[Ite](True, x, y) -> True
132.03/34.71	   r[Ite](True, x, y) -> True
132.03/34.71	   q[Ite](True, x, y) -> True
132.03/34.71	   q[Ite][False][Ite](False, x, y) -> False
132.03/34.71	   p[Ite](True, x, y) -> True
132.03/34.71	
132.03/34.71	Rewrite Strategy: INNERMOST
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(5) DecreasingLoopProof (LOWER BOUND(ID))
132.03/34.71	The following loop(s) give(s) rise to the lower bound Omega(n^1):
132.03/34.71	
132.03/34.71	The rewrite sequence
132.03/34.71	
132.03/34.71	r(Cons(B, Cons(x1_0, xs2_0)), Cons(F, xs2_1)) ->^+ r[Ite][False][Ite][True][Ite](and(q(Cons(B, Cons(x1_0, xs2_0)), xs2_1), r(Cons(B, Cons(x1_0, xs2_0)), xs2_1)), Cons(B, Cons(x1_0, xs2_0)), Cons(F, xs2_1))
132.03/34.71	
132.03/34.71	gives rise to a decreasing loop by considering the right hand sides subterm at position [0,1].
132.03/34.71	
132.03/34.71	The pumping substitution is [xs2_1 / Cons(F, xs2_1)].
132.03/34.71	
132.03/34.71	The result substitution is [ ].
132.03/34.71	
132.03/34.71	
132.03/34.71	
132.03/34.71	
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(6)
132.03/34.71	Complex Obligation (BEST)
132.03/34.71	
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(7)
132.03/34.71	Obligation:
132.03/34.71	Proved the lower bound n^1 for the following obligation:
132.03/34.71	
132.03/34.71	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
132.03/34.71	
132.03/34.71	
132.03/34.71	The TRS R consists of the following rules:
132.03/34.71	
132.03/34.71	   head(Cons(x, xs)) -> x
132.03/34.71	   e(Cons(F, Nil), b) -> False
132.03/34.71	   e(Cons(T, Nil), b) -> False
132.03/34.71	   e(Cons(B, Nil), b) -> False
132.03/34.71	   e(Cons(A, Nil), b) -> e[Match][Cons][Ite][True][Match](A, Nil, b)
132.03/34.71	   e(Cons(F, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(T, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(B, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(A, Cons(x, xs)), b) -> False
132.03/34.71	   equal(F, F) -> True
132.03/34.71	   equal(F, T) -> False
132.03/34.71	   equal(F, B) -> False
132.03/34.71	   equal(F, A) -> False
132.03/34.71	   equal(T, F) -> False
132.03/34.71	   equal(T, T) -> True
132.03/34.71	   equal(T, B) -> False
132.03/34.71	   equal(T, A) -> False
132.03/34.71	   equal(B, F) -> False
132.03/34.71	   equal(B, T) -> False
132.03/34.71	   equal(B, B) -> True
132.03/34.71	   equal(B, A) -> False
132.03/34.71	   equal(A, F) -> False
132.03/34.71	   equal(A, T) -> False
132.03/34.71	   equal(A, B) -> False
132.03/34.71	   equal(A, A) -> True
132.03/34.71	   notEmpty(Cons(x, xs)) -> True
132.03/34.71	   notEmpty(Nil) -> False
132.03/34.71	   e(Nil, b) -> False
132.03/34.71	   t(x, y) -> t[Ite](e(x, y), x, y)
132.03/34.71	   r(x, y) -> r[Ite](e(x, y), x, y)
132.03/34.71	   q(x, y) -> q[Ite](e(x, y), x, y)
132.03/34.71	   p(x, y) -> p[Ite](e(x, y), x, y)
132.03/34.71	   goal(x, y) -> q(x, y)
132.03/34.71	
132.03/34.71	The (relative) TRS S consists of the following rules:
132.03/34.71	
132.03/34.71	   and(False, False) -> False
132.03/34.71	   and(True, False) -> False
132.03/34.71	   and(False, True) -> False
132.03/34.71	   and(True, True) -> True
132.03/34.71	   q[Ite](False, x', Cons(F, Cons(F, xs))) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(F, Cons(F, xs))), q(x', Cons(F, xs))), x', Cons(F, Cons(F, xs)))
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x', Cons(F, Nil)) -> q[Ite][False][Ite](and(True, and(True, and(False, equal(head(Nil), F)))), x', Cons(F, Nil))
132.03/34.71	   q[Ite](False, x', Cons(T, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(T, Nil))
132.03/34.71	   q[Ite](False, x', Cons(B, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(B, Nil))
132.03/34.71	   q[Ite](False, x', Cons(A, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(A, Nil))
132.03/34.71	   r[Ite](False, x', Cons(F, xs)) -> r[Ite][False][Ite][True][Ite](and(q(x', xs), r(x', xs)), x', Cons(F, xs))
132.03/34.71	   r[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   p[Ite](False, x', Cons(F, xs)) -> and(r(x', Cons(F, xs)), p(x', xs))
132.03/34.71	   p[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   q[Ite][False][Ite](True, x', Cons(x, xs)) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(x, xs)), q(x', xs)), x', Cons(x, xs))
132.03/34.71	   t[Ite](False, x, y) -> True
132.03/34.71	   t[Ite](True, x, y) -> True
132.03/34.71	   r[Ite](True, x, y) -> True
132.03/34.71	   q[Ite](True, x, y) -> True
132.03/34.71	   q[Ite][False][Ite](False, x, y) -> False
132.03/34.71	   p[Ite](True, x, y) -> True
132.03/34.71	
132.03/34.71	Rewrite Strategy: INNERMOST
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(8) LowerBoundPropagationProof (FINISHED)
132.03/34.71	Propagated lower bound.
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(9)
132.03/34.71	BOUNDS(n^1, INF)
132.03/34.71	
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(10)
132.03/34.71	Obligation:
132.03/34.71	Analyzing the following TRS for decreasing loops:
132.03/34.71	
132.03/34.71	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
132.03/34.71	
132.03/34.71	
132.03/34.71	The TRS R consists of the following rules:
132.03/34.71	
132.03/34.71	   head(Cons(x, xs)) -> x
132.03/34.71	   e(Cons(F, Nil), b) -> False
132.03/34.71	   e(Cons(T, Nil), b) -> False
132.03/34.71	   e(Cons(B, Nil), b) -> False
132.03/34.71	   e(Cons(A, Nil), b) -> e[Match][Cons][Ite][True][Match](A, Nil, b)
132.03/34.71	   e(Cons(F, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(T, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(B, Cons(x, xs)), b) -> False
132.03/34.71	   e(Cons(A, Cons(x, xs)), b) -> False
132.03/34.71	   equal(F, F) -> True
132.03/34.71	   equal(F, T) -> False
132.03/34.71	   equal(F, B) -> False
132.03/34.71	   equal(F, A) -> False
132.03/34.71	   equal(T, F) -> False
132.03/34.71	   equal(T, T) -> True
132.03/34.71	   equal(T, B) -> False
132.03/34.71	   equal(T, A) -> False
132.03/34.71	   equal(B, F) -> False
132.03/34.71	   equal(B, T) -> False
132.03/34.71	   equal(B, B) -> True
132.03/34.71	   equal(B, A) -> False
132.03/34.71	   equal(A, F) -> False
132.03/34.71	   equal(A, T) -> False
132.03/34.71	   equal(A, B) -> False
132.03/34.71	   equal(A, A) -> True
132.03/34.71	   notEmpty(Cons(x, xs)) -> True
132.03/34.71	   notEmpty(Nil) -> False
132.03/34.71	   e(Nil, b) -> False
132.03/34.71	   t(x, y) -> t[Ite](e(x, y), x, y)
132.03/34.71	   r(x, y) -> r[Ite](e(x, y), x, y)
132.03/34.71	   q(x, y) -> q[Ite](e(x, y), x, y)
132.03/34.71	   p(x, y) -> p[Ite](e(x, y), x, y)
132.03/34.71	   goal(x, y) -> q(x, y)
132.03/34.71	
132.03/34.71	The (relative) TRS S consists of the following rules:
132.03/34.71	
132.03/34.71	   and(False, False) -> False
132.03/34.71	   and(True, False) -> False
132.03/34.71	   and(False, True) -> False
132.03/34.71	   and(True, True) -> True
132.03/34.71	   q[Ite](False, x', Cons(F, Cons(F, xs))) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(F, Cons(F, xs))), q(x', Cons(F, xs))), x', Cons(F, Cons(F, xs)))
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(F, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(T, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(B, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(F, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(T, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(B, xs))) -> False
132.03/34.71	   q[Ite](False, x, Cons(A, Cons(A, xs))) -> False
132.03/34.71	   q[Ite](False, x', Cons(F, Nil)) -> q[Ite][False][Ite](and(True, and(True, and(False, equal(head(Nil), F)))), x', Cons(F, Nil))
132.03/34.71	   q[Ite](False, x', Cons(T, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(T, Nil))
132.03/34.71	   q[Ite](False, x', Cons(B, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(B, Nil))
132.03/34.71	   q[Ite](False, x', Cons(A, Nil)) -> q[Ite][False][Ite](and(True, and(False, and(False, equal(head(Nil), F)))), x', Cons(A, Nil))
132.03/34.71	   r[Ite](False, x', Cons(F, xs)) -> r[Ite][False][Ite][True][Ite](and(q(x', xs), r(x', xs)), x', Cons(F, xs))
132.03/34.71	   r[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   r[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   p[Ite](False, x', Cons(F, xs)) -> and(r(x', Cons(F, xs)), p(x', xs))
132.03/34.71	   p[Ite](False, x, Cons(T, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(B, xs)) -> False
132.03/34.71	   p[Ite](False, x, Cons(A, xs)) -> False
132.03/34.71	   q[Ite][False][Ite](True, x', Cons(x, xs)) -> q[Ite][False][Ite][True][Ite](and(p(x', Cons(x, xs)), q(x', xs)), x', Cons(x, xs))
132.03/34.71	   t[Ite](False, x, y) -> True
132.03/34.71	   t[Ite](True, x, y) -> True
132.03/34.71	   r[Ite](True, x, y) -> True
132.03/34.71	   q[Ite](True, x, y) -> True
132.03/34.71	   q[Ite][False][Ite](False, x, y) -> False
132.03/34.71	   p[Ite](True, x, y) -> True
132.03/34.71	
132.03/34.71	Rewrite Strategy: INNERMOST
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(11) DecreasingLoopProof (FINISHED)
132.03/34.71	The following loop(s) give(s) rise to the lower bound EXP:
132.03/34.71	
132.03/34.71	The rewrite sequence
132.03/34.71	
132.03/34.71	r(Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, Cons(F, xs2_2)))) ->^+ r[Ite][False][Ite][True][Ite](and(q[Ite][False][Ite][True][Ite](and(and(r(Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, xs2_2))), p(Cons(B, Cons(x1_0, xs2_0)), Cons(F, xs2_2))), q(Cons(B, Cons(x1_0, xs2_0)), Cons(F, xs2_2))), Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, xs2_2))), r(Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, xs2_2)))), Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, Cons(F, xs2_2))))
132.03/34.71	
132.03/34.71	gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0,0,0,0].
132.03/34.71	
132.03/34.71	The pumping substitution is [xs2_2 / Cons(F, xs2_2)].
132.03/34.71	
132.03/34.71	The result substitution is [ ].
132.03/34.71	
132.03/34.71	
132.03/34.71	
132.03/34.71	The rewrite sequence
132.03/34.71	
132.03/34.71	r(Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, Cons(F, xs2_2)))) ->^+ r[Ite][False][Ite][True][Ite](and(q[Ite][False][Ite][True][Ite](and(and(r(Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, xs2_2))), p(Cons(B, Cons(x1_0, xs2_0)), Cons(F, xs2_2))), q(Cons(B, Cons(x1_0, xs2_0)), Cons(F, xs2_2))), Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, xs2_2))), r(Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, xs2_2)))), Cons(B, Cons(x1_0, xs2_0)), Cons(F, Cons(F, Cons(F, xs2_2))))
132.03/34.71	
132.03/34.71	gives rise to a decreasing loop by considering the right hand sides subterm at position [0,1].
132.03/34.71	
132.03/34.71	The pumping substitution is [xs2_2 / Cons(F, xs2_2)].
132.03/34.71	
132.03/34.71	The result substitution is [ ].
132.03/34.71	
132.03/34.71	
132.03/34.71	
132.03/34.71	
132.03/34.71	----------------------------------------
132.03/34.71	
132.03/34.71	(12)
132.03/34.71	BOUNDS(EXP, INF)
132.03/34.76	EOF