4.25/1.86	WORST_CASE(NON_POLY, ?)
4.25/1.87	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.25/1.87	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.25/1.87	
4.25/1.87	
4.25/1.87	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
4.25/1.87	
4.25/1.87	(0) CpxRelTRS
4.25/1.87	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 132 ms]
4.25/1.87	(2) CpxRelTRS
4.25/1.87	(3) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
4.25/1.87	(4) TRS for Loop Detection
4.25/1.87	(5) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
4.25/1.87	(6) BEST
4.25/1.87	    (7) proven lower bound
4.25/1.87	        (8) LowerBoundPropagationProof [FINISHED, 0 ms]
4.25/1.87	        (9) BOUNDS(n^1, INF)
4.25/1.87	    (10) TRS for Loop Detection
4.25/1.87	        (11) DecreasingLoopProof [FINISHED, 79 ms]
4.25/1.87	        (12) BOUNDS(EXP, INF)
4.25/1.87	
4.25/1.87	
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(0)
4.25/1.87	Obligation:
4.25/1.87	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
4.25/1.87	
4.25/1.87	
4.25/1.87	The TRS R consists of the following rules:
4.25/1.87	
4.25/1.87	   disj(T) -> True
4.25/1.87	   disj(F) -> True
4.25/1.87	   conj(Or(o1, o2)) -> False
4.25/1.87	   conj(T) -> True
4.25/1.87	   conj(F) -> True
4.25/1.87	   disj(And(a1, a2)) -> conj(And(a1, a2))
4.25/1.87	   disj(Or(t1, t2)) -> and(conj(t1), disj(t1))
4.25/1.87	   conj(And(t1, t2)) -> and(disj(t1), conj(t1))
4.25/1.87	   bool(T) -> True
4.25/1.87	   bool(F) -> True
4.25/1.87	   bool(And(a1, a2)) -> False
4.25/1.87	   bool(Or(o1, o2)) -> False
4.25/1.87	   isConsTerm(T, T) -> True
4.25/1.87	   isConsTerm(T, F) -> False
4.25/1.87	   isConsTerm(T, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(T, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(F, T) -> False
4.25/1.87	   isConsTerm(F, F) -> True
4.25/1.87	   isConsTerm(F, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(F, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(And(a1, a2), T) -> False
4.25/1.87	   isConsTerm(And(a1, a2), F) -> False
4.25/1.87	   isConsTerm(And(a1, a2), And(y1, y2)) -> True
4.25/1.87	   isConsTerm(And(a1, a2), Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), T) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), F) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), And(y1, y2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), Or(x1, x2)) -> True
4.25/1.87	   isOp(T) -> False
4.25/1.87	   isOp(F) -> False
4.25/1.87	   isOp(And(t1, t2)) -> True
4.25/1.87	   isOp(Or(t1, t2)) -> True
4.25/1.87	   isAnd(T) -> False
4.25/1.87	   isAnd(F) -> False
4.25/1.87	   isAnd(And(t1, t2)) -> True
4.25/1.87	   isAnd(Or(t1, t2)) -> False
4.25/1.87	   getSecond(And(t1, t2)) -> t1
4.25/1.87	   getSecond(Or(t1, t2)) -> t1
4.25/1.87	   getFirst(And(t1, t2)) -> t1
4.25/1.87	   getFirst(Or(t1, t2)) -> t1
4.25/1.87	   disjconj(p) -> disj(p)
4.25/1.87	
4.25/1.87	The (relative) TRS S consists of the following rules:
4.25/1.87	
4.25/1.87	   and(False, False) -> False
4.25/1.87	   and(True, False) -> False
4.25/1.87	   and(False, True) -> False
4.25/1.87	   and(True, True) -> True
4.25/1.87	
4.25/1.87	Rewrite Strategy: INNERMOST
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
4.25/1.87	proved termination of relative rules
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(2)
4.25/1.87	Obligation:
4.25/1.87	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
4.25/1.87	
4.25/1.87	
4.25/1.87	The TRS R consists of the following rules:
4.25/1.87	
4.25/1.87	   disj(T) -> True
4.25/1.87	   disj(F) -> True
4.25/1.87	   conj(Or(o1, o2)) -> False
4.25/1.87	   conj(T) -> True
4.25/1.87	   conj(F) -> True
4.25/1.87	   disj(And(a1, a2)) -> conj(And(a1, a2))
4.25/1.87	   disj(Or(t1, t2)) -> and(conj(t1), disj(t1))
4.25/1.87	   conj(And(t1, t2)) -> and(disj(t1), conj(t1))
4.25/1.87	   bool(T) -> True
4.25/1.87	   bool(F) -> True
4.25/1.87	   bool(And(a1, a2)) -> False
4.25/1.87	   bool(Or(o1, o2)) -> False
4.25/1.87	   isConsTerm(T, T) -> True
4.25/1.87	   isConsTerm(T, F) -> False
4.25/1.87	   isConsTerm(T, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(T, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(F, T) -> False
4.25/1.87	   isConsTerm(F, F) -> True
4.25/1.87	   isConsTerm(F, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(F, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(And(a1, a2), T) -> False
4.25/1.87	   isConsTerm(And(a1, a2), F) -> False
4.25/1.87	   isConsTerm(And(a1, a2), And(y1, y2)) -> True
4.25/1.87	   isConsTerm(And(a1, a2), Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), T) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), F) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), And(y1, y2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), Or(x1, x2)) -> True
4.25/1.87	   isOp(T) -> False
4.25/1.87	   isOp(F) -> False
4.25/1.87	   isOp(And(t1, t2)) -> True
4.25/1.87	   isOp(Or(t1, t2)) -> True
4.25/1.87	   isAnd(T) -> False
4.25/1.87	   isAnd(F) -> False
4.25/1.87	   isAnd(And(t1, t2)) -> True
4.25/1.87	   isAnd(Or(t1, t2)) -> False
4.25/1.87	   getSecond(And(t1, t2)) -> t1
4.25/1.87	   getSecond(Or(t1, t2)) -> t1
4.25/1.87	   getFirst(And(t1, t2)) -> t1
4.25/1.87	   getFirst(Or(t1, t2)) -> t1
4.25/1.87	   disjconj(p) -> disj(p)
4.25/1.87	
4.25/1.87	The (relative) TRS S consists of the following rules:
4.25/1.87	
4.25/1.87	   and(False, False) -> False
4.25/1.87	   and(True, False) -> False
4.25/1.87	   and(False, True) -> False
4.25/1.87	   and(True, True) -> True
4.25/1.87	
4.25/1.87	Rewrite Strategy: INNERMOST
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(3) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
4.25/1.87	Transformed a relative TRS into a decreasing-loop problem.
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(4)
4.25/1.87	Obligation:
4.25/1.87	Analyzing the following TRS for decreasing loops:
4.25/1.87	
4.25/1.87	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
4.25/1.87	
4.25/1.87	
4.25/1.87	The TRS R consists of the following rules:
4.25/1.87	
4.25/1.87	   disj(T) -> True
4.25/1.87	   disj(F) -> True
4.25/1.87	   conj(Or(o1, o2)) -> False
4.25/1.87	   conj(T) -> True
4.25/1.87	   conj(F) -> True
4.25/1.87	   disj(And(a1, a2)) -> conj(And(a1, a2))
4.25/1.87	   disj(Or(t1, t2)) -> and(conj(t1), disj(t1))
4.25/1.87	   conj(And(t1, t2)) -> and(disj(t1), conj(t1))
4.25/1.87	   bool(T) -> True
4.25/1.87	   bool(F) -> True
4.25/1.87	   bool(And(a1, a2)) -> False
4.25/1.87	   bool(Or(o1, o2)) -> False
4.25/1.87	   isConsTerm(T, T) -> True
4.25/1.87	   isConsTerm(T, F) -> False
4.25/1.87	   isConsTerm(T, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(T, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(F, T) -> False
4.25/1.87	   isConsTerm(F, F) -> True
4.25/1.87	   isConsTerm(F, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(F, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(And(a1, a2), T) -> False
4.25/1.87	   isConsTerm(And(a1, a2), F) -> False
4.25/1.87	   isConsTerm(And(a1, a2), And(y1, y2)) -> True
4.25/1.87	   isConsTerm(And(a1, a2), Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), T) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), F) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), And(y1, y2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), Or(x1, x2)) -> True
4.25/1.87	   isOp(T) -> False
4.25/1.87	   isOp(F) -> False
4.25/1.87	   isOp(And(t1, t2)) -> True
4.25/1.87	   isOp(Or(t1, t2)) -> True
4.25/1.87	   isAnd(T) -> False
4.25/1.87	   isAnd(F) -> False
4.25/1.87	   isAnd(And(t1, t2)) -> True
4.25/1.87	   isAnd(Or(t1, t2)) -> False
4.25/1.87	   getSecond(And(t1, t2)) -> t1
4.25/1.87	   getSecond(Or(t1, t2)) -> t1
4.25/1.87	   getFirst(And(t1, t2)) -> t1
4.25/1.87	   getFirst(Or(t1, t2)) -> t1
4.25/1.87	   disjconj(p) -> disj(p)
4.25/1.87	
4.25/1.87	The (relative) TRS S consists of the following rules:
4.25/1.87	
4.25/1.87	   and(False, False) -> False
4.25/1.87	   and(True, False) -> False
4.25/1.87	   and(False, True) -> False
4.25/1.87	   and(True, True) -> True
4.25/1.87	
4.25/1.87	Rewrite Strategy: INNERMOST
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(5) DecreasingLoopProof (LOWER BOUND(ID))
4.25/1.87	The following loop(s) give(s) rise to the lower bound Omega(n^1):
4.25/1.87	
4.25/1.87	The rewrite sequence
4.25/1.87	
4.25/1.87	conj(And(t1, t2)) ->^+ and(disj(t1), conj(t1))
4.25/1.87	
4.25/1.87	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
4.25/1.87	
4.25/1.87	The pumping substitution is [t1 / And(t1, t2)].
4.25/1.87	
4.25/1.87	The result substitution is [ ].
4.25/1.87	
4.25/1.87	
4.25/1.87	
4.25/1.87	
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(6)
4.25/1.87	Complex Obligation (BEST)
4.25/1.87	
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(7)
4.25/1.87	Obligation:
4.25/1.87	Proved the lower bound n^1 for the following obligation:
4.25/1.87	
4.25/1.87	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
4.25/1.87	
4.25/1.87	
4.25/1.87	The TRS R consists of the following rules:
4.25/1.87	
4.25/1.87	   disj(T) -> True
4.25/1.87	   disj(F) -> True
4.25/1.87	   conj(Or(o1, o2)) -> False
4.25/1.87	   conj(T) -> True
4.25/1.87	   conj(F) -> True
4.25/1.87	   disj(And(a1, a2)) -> conj(And(a1, a2))
4.25/1.87	   disj(Or(t1, t2)) -> and(conj(t1), disj(t1))
4.25/1.87	   conj(And(t1, t2)) -> and(disj(t1), conj(t1))
4.25/1.87	   bool(T) -> True
4.25/1.87	   bool(F) -> True
4.25/1.87	   bool(And(a1, a2)) -> False
4.25/1.87	   bool(Or(o1, o2)) -> False
4.25/1.87	   isConsTerm(T, T) -> True
4.25/1.87	   isConsTerm(T, F) -> False
4.25/1.87	   isConsTerm(T, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(T, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(F, T) -> False
4.25/1.87	   isConsTerm(F, F) -> True
4.25/1.87	   isConsTerm(F, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(F, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(And(a1, a2), T) -> False
4.25/1.87	   isConsTerm(And(a1, a2), F) -> False
4.25/1.87	   isConsTerm(And(a1, a2), And(y1, y2)) -> True
4.25/1.87	   isConsTerm(And(a1, a2), Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), T) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), F) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), And(y1, y2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), Or(x1, x2)) -> True
4.25/1.87	   isOp(T) -> False
4.25/1.87	   isOp(F) -> False
4.25/1.87	   isOp(And(t1, t2)) -> True
4.25/1.87	   isOp(Or(t1, t2)) -> True
4.25/1.87	   isAnd(T) -> False
4.25/1.87	   isAnd(F) -> False
4.25/1.87	   isAnd(And(t1, t2)) -> True
4.25/1.87	   isAnd(Or(t1, t2)) -> False
4.25/1.87	   getSecond(And(t1, t2)) -> t1
4.25/1.87	   getSecond(Or(t1, t2)) -> t1
4.25/1.87	   getFirst(And(t1, t2)) -> t1
4.25/1.87	   getFirst(Or(t1, t2)) -> t1
4.25/1.87	   disjconj(p) -> disj(p)
4.25/1.87	
4.25/1.87	The (relative) TRS S consists of the following rules:
4.25/1.87	
4.25/1.87	   and(False, False) -> False
4.25/1.87	   and(True, False) -> False
4.25/1.87	   and(False, True) -> False
4.25/1.87	   and(True, True) -> True
4.25/1.87	
4.25/1.87	Rewrite Strategy: INNERMOST
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(8) LowerBoundPropagationProof (FINISHED)
4.25/1.87	Propagated lower bound.
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(9)
4.25/1.87	BOUNDS(n^1, INF)
4.25/1.87	
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(10)
4.25/1.87	Obligation:
4.25/1.87	Analyzing the following TRS for decreasing loops:
4.25/1.87	
4.25/1.87	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(EXP, INF).
4.25/1.87	
4.25/1.87	
4.25/1.87	The TRS R consists of the following rules:
4.25/1.87	
4.25/1.87	   disj(T) -> True
4.25/1.87	   disj(F) -> True
4.25/1.87	   conj(Or(o1, o2)) -> False
4.25/1.87	   conj(T) -> True
4.25/1.87	   conj(F) -> True
4.25/1.87	   disj(And(a1, a2)) -> conj(And(a1, a2))
4.25/1.87	   disj(Or(t1, t2)) -> and(conj(t1), disj(t1))
4.25/1.87	   conj(And(t1, t2)) -> and(disj(t1), conj(t1))
4.25/1.87	   bool(T) -> True
4.25/1.87	   bool(F) -> True
4.25/1.87	   bool(And(a1, a2)) -> False
4.25/1.87	   bool(Or(o1, o2)) -> False
4.25/1.87	   isConsTerm(T, T) -> True
4.25/1.87	   isConsTerm(T, F) -> False
4.25/1.87	   isConsTerm(T, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(T, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(F, T) -> False
4.25/1.87	   isConsTerm(F, F) -> True
4.25/1.87	   isConsTerm(F, And(y1, y2)) -> False
4.25/1.87	   isConsTerm(F, Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(And(a1, a2), T) -> False
4.25/1.87	   isConsTerm(And(a1, a2), F) -> False
4.25/1.87	   isConsTerm(And(a1, a2), And(y1, y2)) -> True
4.25/1.87	   isConsTerm(And(a1, a2), Or(x1, x2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), T) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), F) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), And(y1, y2)) -> False
4.25/1.87	   isConsTerm(Or(o1, o2), Or(x1, x2)) -> True
4.25/1.87	   isOp(T) -> False
4.25/1.87	   isOp(F) -> False
4.25/1.87	   isOp(And(t1, t2)) -> True
4.25/1.87	   isOp(Or(t1, t2)) -> True
4.25/1.87	   isAnd(T) -> False
4.25/1.87	   isAnd(F) -> False
4.25/1.87	   isAnd(And(t1, t2)) -> True
4.25/1.87	   isAnd(Or(t1, t2)) -> False
4.25/1.87	   getSecond(And(t1, t2)) -> t1
4.25/1.87	   getSecond(Or(t1, t2)) -> t1
4.25/1.87	   getFirst(And(t1, t2)) -> t1
4.25/1.87	   getFirst(Or(t1, t2)) -> t1
4.25/1.87	   disjconj(p) -> disj(p)
4.25/1.87	
4.25/1.87	The (relative) TRS S consists of the following rules:
4.25/1.87	
4.25/1.87	   and(False, False) -> False
4.25/1.87	   and(True, False) -> False
4.25/1.87	   and(False, True) -> False
4.25/1.87	   and(True, True) -> True
4.25/1.87	
4.25/1.87	Rewrite Strategy: INNERMOST
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(11) DecreasingLoopProof (FINISHED)
4.25/1.87	The following loop(s) give(s) rise to the lower bound EXP:
4.25/1.87	
4.25/1.87	The rewrite sequence
4.25/1.87	
4.25/1.87	conj(And(And(a11_0, a22_0), t2)) ->^+ and(conj(And(a11_0, a22_0)), conj(And(a11_0, a22_0)))
4.25/1.87	
4.25/1.87	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
4.25/1.87	
4.25/1.87	The pumping substitution is [a11_0 / And(a11_0, a22_0)].
4.25/1.87	
4.25/1.87	The result substitution is [t2 / a22_0].
4.25/1.87	
4.25/1.87	
4.25/1.87	
4.25/1.87	The rewrite sequence
4.25/1.87	
4.25/1.87	conj(And(And(a11_0, a22_0), t2)) ->^+ and(conj(And(a11_0, a22_0)), conj(And(a11_0, a22_0)))
4.25/1.87	
4.25/1.87	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
4.25/1.87	
4.25/1.87	The pumping substitution is [a11_0 / And(a11_0, a22_0)].
4.25/1.87	
4.25/1.87	The result substitution is [t2 / a22_0].
4.25/1.87	
4.25/1.87	
4.25/1.87	
4.25/1.87	
4.25/1.87	----------------------------------------
4.25/1.87	
4.25/1.87	(12)
4.25/1.87	BOUNDS(EXP, INF)
4.32/2.78	EOF