6.10/2.34	WORST_CASE(NON_POLY, ?)
6.10/2.37	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.10/2.37	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.10/2.37	
6.10/2.37	
6.10/2.37	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF).
6.10/2.37	
6.10/2.37	(0) CpxTRS
6.10/2.37	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
6.10/2.37	(2) TRS for Loop Detection
6.10/2.37	(3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
6.10/2.37	(4) BEST
6.10/2.37	    (5) proven lower bound
6.10/2.37	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
6.10/2.37	        (7) BOUNDS(n^1, INF)
6.10/2.37	    (8) TRS for Loop Detection
6.10/2.37	        (9) DecreasingLoopProof [FINISHED, 462 ms]
6.10/2.37	        (10) BOUNDS(EXP, INF)
6.10/2.37	
6.10/2.37	
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(0)
6.10/2.37	Obligation:
6.10/2.37	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF).
6.10/2.37	
6.10/2.37	
6.10/2.37	The TRS R consists of the following rules:
6.10/2.37	
6.10/2.37	   and(false, false) -> false
6.10/2.37	   and(true, false) -> false
6.10/2.37	   and(false, true) -> false
6.10/2.37	   and(true, true) -> true
6.10/2.37	   eq(nil, nil) -> true
6.10/2.37	   eq(cons(T, L), nil) -> false
6.10/2.37	   eq(nil, cons(T, L)) -> false
6.10/2.37	   eq(cons(T, L), cons(Tp, Lp)) -> and(eq(T, Tp), eq(L, Lp))
6.10/2.37	   eq(var(L), var(Lp)) -> eq(L, Lp)
6.10/2.37	   eq(var(L), apply(T, S)) -> false
6.10/2.37	   eq(var(L), lambda(X, T)) -> false
6.10/2.37	   eq(apply(T, S), var(L)) -> false
6.10/2.37	   eq(apply(T, S), apply(Tp, Sp)) -> and(eq(T, Tp), eq(S, Sp))
6.10/2.37	   eq(apply(T, S), lambda(X, Tp)) -> false
6.10/2.37	   eq(lambda(X, T), var(L)) -> false
6.10/2.37	   eq(lambda(X, T), apply(Tp, Sp)) -> false
6.10/2.37	   eq(lambda(X, T), lambda(Xp, Tp)) -> and(eq(T, Tp), eq(X, Xp))
6.10/2.37	   if(true, var(K), var(L)) -> var(K)
6.10/2.37	   if(false, var(K), var(L)) -> var(L)
6.10/2.37	   ren(var(L), var(K), var(Lp)) -> if(eq(L, Lp), var(K), var(Lp))
6.10/2.37	   ren(X, Y, apply(T, S)) -> apply(ren(X, Y, T), ren(X, Y, S))
6.10/2.37	   ren(X, Y, lambda(Z, T)) -> lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))
6.10/2.37	
6.10/2.37	S is empty.
6.10/2.37	Rewrite Strategy: FULL
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
6.10/2.37	Transformed a relative TRS into a decreasing-loop problem.
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(2)
6.10/2.37	Obligation:
6.10/2.37	Analyzing the following TRS for decreasing loops:
6.10/2.37	
6.10/2.37	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF).
6.10/2.37	
6.10/2.37	
6.10/2.37	The TRS R consists of the following rules:
6.10/2.37	
6.10/2.37	   and(false, false) -> false
6.10/2.37	   and(true, false) -> false
6.10/2.37	   and(false, true) -> false
6.10/2.37	   and(true, true) -> true
6.10/2.37	   eq(nil, nil) -> true
6.10/2.37	   eq(cons(T, L), nil) -> false
6.10/2.37	   eq(nil, cons(T, L)) -> false
6.10/2.37	   eq(cons(T, L), cons(Tp, Lp)) -> and(eq(T, Tp), eq(L, Lp))
6.10/2.37	   eq(var(L), var(Lp)) -> eq(L, Lp)
6.10/2.37	   eq(var(L), apply(T, S)) -> false
6.10/2.37	   eq(var(L), lambda(X, T)) -> false
6.10/2.37	   eq(apply(T, S), var(L)) -> false
6.10/2.37	   eq(apply(T, S), apply(Tp, Sp)) -> and(eq(T, Tp), eq(S, Sp))
6.10/2.37	   eq(apply(T, S), lambda(X, Tp)) -> false
6.10/2.37	   eq(lambda(X, T), var(L)) -> false
6.10/2.37	   eq(lambda(X, T), apply(Tp, Sp)) -> false
6.10/2.37	   eq(lambda(X, T), lambda(Xp, Tp)) -> and(eq(T, Tp), eq(X, Xp))
6.10/2.37	   if(true, var(K), var(L)) -> var(K)
6.10/2.37	   if(false, var(K), var(L)) -> var(L)
6.10/2.37	   ren(var(L), var(K), var(Lp)) -> if(eq(L, Lp), var(K), var(Lp))
6.10/2.37	   ren(X, Y, apply(T, S)) -> apply(ren(X, Y, T), ren(X, Y, S))
6.10/2.37	   ren(X, Y, lambda(Z, T)) -> lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))
6.10/2.37	
6.10/2.37	S is empty.
6.10/2.37	Rewrite Strategy: FULL
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(3) DecreasingLoopProof (LOWER BOUND(ID))
6.10/2.37	The following loop(s) give(s) rise to the lower bound Omega(n^1):
6.10/2.37	
6.10/2.37	The rewrite sequence
6.10/2.37	
6.10/2.37	eq(lambda(X, T), lambda(Xp, Tp)) ->^+ and(eq(T, Tp), eq(X, Xp))
6.10/2.37	
6.10/2.37	gives rise to a decreasing loop by considering the right hand sides subterm at position [0].
6.10/2.37	
6.10/2.37	The pumping substitution is [T / lambda(X, T), Tp / lambda(Xp, Tp)].
6.10/2.37	
6.10/2.37	The result substitution is [ ].
6.10/2.37	
6.10/2.37	
6.10/2.37	
6.10/2.37	
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(4)
6.10/2.37	Complex Obligation (BEST)
6.10/2.37	
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(5)
6.10/2.37	Obligation:
6.10/2.37	Proved the lower bound n^1 for the following obligation:
6.10/2.37	
6.10/2.37	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF).
6.10/2.37	
6.10/2.37	
6.10/2.37	The TRS R consists of the following rules:
6.10/2.37	
6.10/2.37	   and(false, false) -> false
6.10/2.37	   and(true, false) -> false
6.10/2.37	   and(false, true) -> false
6.10/2.37	   and(true, true) -> true
6.10/2.37	   eq(nil, nil) -> true
6.10/2.37	   eq(cons(T, L), nil) -> false
6.10/2.37	   eq(nil, cons(T, L)) -> false
6.10/2.37	   eq(cons(T, L), cons(Tp, Lp)) -> and(eq(T, Tp), eq(L, Lp))
6.10/2.37	   eq(var(L), var(Lp)) -> eq(L, Lp)
6.10/2.37	   eq(var(L), apply(T, S)) -> false
6.10/2.37	   eq(var(L), lambda(X, T)) -> false
6.10/2.37	   eq(apply(T, S), var(L)) -> false
6.10/2.37	   eq(apply(T, S), apply(Tp, Sp)) -> and(eq(T, Tp), eq(S, Sp))
6.10/2.37	   eq(apply(T, S), lambda(X, Tp)) -> false
6.10/2.37	   eq(lambda(X, T), var(L)) -> false
6.10/2.37	   eq(lambda(X, T), apply(Tp, Sp)) -> false
6.10/2.37	   eq(lambda(X, T), lambda(Xp, Tp)) -> and(eq(T, Tp), eq(X, Xp))
6.10/2.37	   if(true, var(K), var(L)) -> var(K)
6.10/2.37	   if(false, var(K), var(L)) -> var(L)
6.10/2.37	   ren(var(L), var(K), var(Lp)) -> if(eq(L, Lp), var(K), var(Lp))
6.10/2.37	   ren(X, Y, apply(T, S)) -> apply(ren(X, Y, T), ren(X, Y, S))
6.10/2.37	   ren(X, Y, lambda(Z, T)) -> lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))
6.10/2.37	
6.10/2.37	S is empty.
6.10/2.37	Rewrite Strategy: FULL
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(6) LowerBoundPropagationProof (FINISHED)
6.10/2.37	Propagated lower bound.
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(7)
6.10/2.37	BOUNDS(n^1, INF)
6.10/2.37	
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(8)
6.10/2.37	Obligation:
6.10/2.37	Analyzing the following TRS for decreasing loops:
6.10/2.37	
6.10/2.37	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(EXP, INF).
6.10/2.37	
6.10/2.37	
6.10/2.37	The TRS R consists of the following rules:
6.10/2.37	
6.10/2.37	   and(false, false) -> false
6.10/2.37	   and(true, false) -> false
6.10/2.37	   and(false, true) -> false
6.10/2.37	   and(true, true) -> true
6.10/2.37	   eq(nil, nil) -> true
6.10/2.37	   eq(cons(T, L), nil) -> false
6.10/2.37	   eq(nil, cons(T, L)) -> false
6.10/2.37	   eq(cons(T, L), cons(Tp, Lp)) -> and(eq(T, Tp), eq(L, Lp))
6.10/2.37	   eq(var(L), var(Lp)) -> eq(L, Lp)
6.10/2.37	   eq(var(L), apply(T, S)) -> false
6.10/2.37	   eq(var(L), lambda(X, T)) -> false
6.10/2.37	   eq(apply(T, S), var(L)) -> false
6.10/2.37	   eq(apply(T, S), apply(Tp, Sp)) -> and(eq(T, Tp), eq(S, Sp))
6.10/2.37	   eq(apply(T, S), lambda(X, Tp)) -> false
6.10/2.37	   eq(lambda(X, T), var(L)) -> false
6.10/2.37	   eq(lambda(X, T), apply(Tp, Sp)) -> false
6.10/2.37	   eq(lambda(X, T), lambda(Xp, Tp)) -> and(eq(T, Tp), eq(X, Xp))
6.10/2.37	   if(true, var(K), var(L)) -> var(K)
6.10/2.37	   if(false, var(K), var(L)) -> var(L)
6.10/2.37	   ren(var(L), var(K), var(Lp)) -> if(eq(L, Lp), var(K), var(Lp))
6.10/2.37	   ren(X, Y, apply(T, S)) -> apply(ren(X, Y, T), ren(X, Y, S))
6.10/2.37	   ren(X, Y, lambda(Z, T)) -> lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))
6.10/2.37	
6.10/2.37	S is empty.
6.10/2.37	Rewrite Strategy: FULL
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(9) DecreasingLoopProof (FINISHED)
6.10/2.37	The following loop(s) give(s) rise to the lower bound EXP:
6.10/2.37	
6.10/2.37	The rewrite sequence
6.10/2.37	
6.10/2.37	ren(X, Y, lambda(Z, lambda(Z3_0, T4_0))) ->^+ lambda(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), lambda(var(cons(X, cons(Y, cons(lambda(var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), ren(Z, var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), ren(Z3_0, var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), T4_0))), nil)))), ren(X, Y, ren(var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), var(cons(X, cons(Y, cons(lambda(var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), ren(Z, var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), ren(Z3_0, var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), T4_0))), nil)))), ren(Z, var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), ren(Z3_0, var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), T4_0))))))
6.10/2.37	
6.10/2.37	gives rise to a decreasing loop by considering the right hand sides subterm at position [1,0,0,1,1,0,1,2].
6.10/2.37	
6.10/2.37	The pumping substitution is [T4_0 / lambda(Z, lambda(Z3_0, T4_0))].
6.10/2.37	
6.10/2.37	The result substitution is [X / Z3_0, Y / var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil))))].
6.10/2.37	
6.10/2.37	
6.10/2.37	
6.10/2.37	The rewrite sequence
6.10/2.37	
6.10/2.37	ren(X, Y, lambda(Z, lambda(Z3_0, T4_0))) ->^+ lambda(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), lambda(var(cons(X, cons(Y, cons(lambda(var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), ren(Z, var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), ren(Z3_0, var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), T4_0))), nil)))), ren(X, Y, ren(var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), var(cons(X, cons(Y, cons(lambda(var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), ren(Z, var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), ren(Z3_0, var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), T4_0))), nil)))), ren(Z, var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), ren(Z3_0, var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil)))), T4_0))))))
6.10/2.37	
6.10/2.37	gives rise to a decreasing loop by considering the right hand sides subterm at position [1,1,2,1,0,1,1,0,1,2].
6.10/2.37	
6.10/2.37	The pumping substitution is [T4_0 / lambda(Z, lambda(Z3_0, T4_0))].
6.10/2.37	
6.10/2.37	The result substitution is [X / Z3_0, Y / var(cons(Z, cons(var(cons(X, cons(Y, cons(lambda(Z, lambda(Z3_0, T4_0)), nil)))), cons(lambda(Z3_0, T4_0), nil))))].
6.10/2.37	
6.10/2.37	
6.10/2.37	
6.10/2.37	
6.10/2.37	----------------------------------------
6.10/2.37	
6.10/2.37	(10)
6.10/2.37	BOUNDS(EXP, INF)
6.39/2.41	EOF