891.35/291.62 WORST_CASE(Omega(n^1), ?) 896.04/292.83 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 896.04/292.83 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 896.04/292.83 896.04/292.83 896.04/292.83 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 896.04/292.83 896.04/292.83 (0) CpxRelTRS 896.04/292.83 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 1008 ms] 896.04/292.83 (2) CpxRelTRS 896.04/292.83 (3) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 896.04/292.83 (4) TRS for Loop Detection 896.04/292.83 (5) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 896.04/292.83 (6) BEST 896.04/292.83 (7) proven lower bound 896.04/292.83 (8) LowerBoundPropagationProof [FINISHED, 0 ms] 896.04/292.83 (9) BOUNDS(n^1, INF) 896.04/292.83 (10) TRS for Loop Detection 896.04/292.83 896.04/292.83 896.04/292.83 ---------------------------------------- 896.04/292.83 896.04/292.83 (0) 896.04/292.83 Obligation: 896.04/292.83 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 896.04/292.83 896.04/292.83 896.04/292.83 The TRS R consists of the following rules: 896.04/292.83 896.04/292.83 eeval(Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.83 eeval(Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.83 eeval(Error(e11, e12), ns, vs, p) -> eeval[False][Ite](False, Error(e11, e12), ns, vs, p) 896.04/292.83 eeval(F, ns, vs, p) -> F 896.04/292.83 eeval(T, ns, vs, p) -> T 896.04/292.83 eeval(ITE(i, t, e), ns, vs, p) -> eeval[Ite](checkConstrExp(eeval(i, ns, vs, p), T), ITE(i, t, e), ns, vs, p) 896.04/292.83 eeval(Bsf(op, t1, t2), ns, vs, p) -> eeval[Let](Bsf(op, t1, t2), ns, vs, p, eeval(t1, ns, vs, p)) 896.04/292.83 eeval(Var(int), ns, vs, p) -> lookvar(int, ns, vs) 896.04/292.83 run(Cons(Fun(f0, e), xs), input) -> run[Let][Let](Cons(Fun(f0, e), xs), input, f0, lookbody(f0, Cons(Fun(f0, e), xs))) 896.04/292.83 eqExp(Error(e11, e12), Error(e21, e22)) -> and(eqExp(e11, e21), eqExp(e12, e22)) 896.04/292.83 eqExp(Error(e11, e12), F) -> False 896.04/292.83 eqExp(Error(e11, e12), T) -> False 896.04/292.83 eqExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Error(e11, e12), Var(v2)) -> False 896.04/292.83 eqExp(F, Error(e21, e22)) -> False 896.04/292.83 eqExp(F, F) -> True 896.04/292.83 eqExp(F, T) -> False 896.04/292.83 eqExp(F, Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(F, Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(F, ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(F, Var(v2)) -> False 896.04/292.83 eqExp(T, Error(e21, e22)) -> False 896.04/292.83 eqExp(T, F) -> False 896.04/292.83 eqExp(T, T) -> True 896.04/292.83 eqExp(T, Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(T, Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(T, ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(T, Var(v2)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), F) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), T) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> and(!EQ(fn1, fn2), eqExp(fe1, fe2)) 896.04/292.83 eqExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), F) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), T) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> and(eqExp(eq11, eq21), eqExp(eq12, eq22)) 896.04/292.83 eqExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), F) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), T) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> and(eqExp(i1, i2), and(eqExp(t1, t2), eqExp(e1, e2))) 896.04/292.83 eqExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), F) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), T) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Bsf(o1, b11, b12), Bsf(o2, b21, b22)) -> and(True, and(eqExp(b11, b21), eqExp(b12, b22))) 896.04/292.83 eqExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.83 eqExp(Var(v1), Error(e21, e22)) -> False 896.04/292.83 eqExp(Var(v1), F) -> False 896.04/292.83 eqExp(Var(v1), T) -> False 896.04/292.83 eqExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Var(v1), Var(v2)) -> !EQ(v1, v2) 896.04/292.83 checkConstrExp(Error(e11, e12), Error(e21, e22)) -> True 896.04/292.83 checkConstrExp(Error(e11, e12), F) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), T) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Var(v2)) -> False 896.04/292.83 checkConstrExp(F, Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(F, F) -> True 896.04/292.83 checkConstrExp(F, T) -> False 896.04/292.83 checkConstrExp(F, Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(F, Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(F, ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(F, Var(v2)) -> False 896.04/292.83 checkConstrExp(T, Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(T, F) -> False 896.04/292.83 checkConstrExp(T, T) -> True 896.04/292.83 checkConstrExp(T, Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(T, Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(T, ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(T, Var(v2)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), F) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), T) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> True 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), F) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), T) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> True 896.04/292.83 checkConstrExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), F) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), T) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> True 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), F) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), T) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Bsf(op2, b21, b22)) -> True 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.83 checkConstrExp(Var(v1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Var(v1), F) -> False 896.04/292.83 checkConstrExp(Var(v1), T) -> False 896.04/292.83 checkConstrExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Var(v1), Var(v2)) -> True 896.04/292.83 lookname(f, Cons(Fun(n, e), xs)) -> lookname[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.83 lookbody(f, Cons(Fun(n, e), xs)) -> lookbody[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.83 getVar(Var(int)) -> int 896.04/292.83 getIfTrue(ITE(i, t, e)) -> t 896.04/292.83 getIfGuard(ITE(i, t, e)) -> i 896.04/292.83 getIfFalse(ITE(i, t, e)) -> e 896.04/292.83 getFuncName(Fun(n, e)) -> n 896.04/292.83 getFuncExp(Fun(n, e)) -> e 896.04/292.83 getEqSecond(Eq(f, s)) -> s 896.04/292.83 getEqFirst(Eq(f, s)) -> f 896.04/292.83 getConst(Cst(int)) -> int 896.04/292.83 getBsfSecondTerm(Bsf(op, t1, t2)) -> t2 896.04/292.83 getBsfOp(Bsf(op, t1, t2)) -> op 896.04/292.83 getBsfFirstTerm(Bsf(op, t1, t2)) -> t1 896.04/292.83 apply(op, v1, v2) -> apply[Ite](eqExp(v1, v2), op, v1, v2) 896.04/292.83 lookvar(x', Cons(x, xs), vs) -> lookvar[Ite](!EQ(x', x), x', Cons(x, xs), vs) 896.04/292.83 eqOps(o1, o2) -> True 896.04/292.83 896.04/292.83 The (relative) TRS S consists of the following rules: 896.04/292.83 896.04/292.83 !EQ(S(x), S(y)) -> !EQ(x, y) 896.04/292.83 !EQ(0, S(y)) -> False 896.04/292.83 !EQ(S(x), 0) -> False 896.04/292.83 !EQ(0, 0) -> True 896.04/292.83 and(False, False) -> False 896.04/292.83 and(True, False) -> False 896.04/292.83 and(False, True) -> False 896.04/292.83 and(True, True) -> True 896.04/292.83 eeval[False][Ite](True, Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.83 lookvar[Ite](False, x', Cons(x'', xs'), Cons(x, xs)) -> lookvar(x', xs', xs) 896.04/292.83 lookname[Ite](True, f, Cons(Fun(n, e), xs)) -> n 896.04/292.83 lookbody[Ite](True, f, Cons(Fun(n, e), xs)) -> e 896.04/292.83 eeval[False][Ite](False, Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.83 eeval[Ite](False, ITE(i, t, e), ns, vs, p) -> eeval(e, ns, vs, p) 896.04/292.83 eeval[Ite](True, ITE(i, t, e), ns, vs, p) -> eeval(t, ns, vs, p) 896.04/292.83 eeval[False][Let](Fun(n, e), ns, vs, p, ef) -> eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, lookname(n, p)) 896.04/292.83 eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, nf) -> eeval[Let][Let][Let](Fun(n, e), ns, vs, p, ef, nf, eeval(e, ns, vs, p)) 896.04/292.83 eeval[Let](Bsf(op, t1, t2), ns, vs, p, v1) -> eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, eeval(t2, ns, vs, p)) 896.04/292.83 eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, v2) -> apply(op, v1, v2) 896.04/292.83 lookvar[Ite](True, x', ns, Cons(x, xs)) -> x 896.04/292.83 lookname[Ite](False, f, Cons(x, xs)) -> lookname(f, xs) 896.04/292.83 lookbody[Ite](False, f, Cons(x, xs)) -> lookbody(f, xs) 896.04/292.83 eeval[True][Ite](False, e, ns, vs, p) -> F 896.04/292.83 eeval[True][Ite](True, e, ns, vs, p) -> T 896.04/292.83 apply[Ite](False, op, v1, v2) -> F 896.04/292.83 apply[Ite](True, op, v1, v2) -> T 896.04/292.83 run[Let][Let](p, input, f0, ef) -> run[Let](p, input, f0, ef, lookname(f0, p)) 896.04/292.83 run[Let](p, input, f0, ef, nf) -> eeval(ef, Cons(nf, Nil), Cons(input, Nil), p) 896.04/292.83 eeval[Let][Let][Let](e, ns, vs, p, ef, nf, v) -> eeval(ef, Cons(nf, Nil), Cons(v, Nil), p) 896.04/292.83 896.04/292.83 Rewrite Strategy: INNERMOST 896.04/292.83 ---------------------------------------- 896.04/292.83 896.04/292.83 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 896.04/292.83 proved termination of relative rules 896.04/292.83 ---------------------------------------- 896.04/292.83 896.04/292.83 (2) 896.04/292.83 Obligation: 896.04/292.83 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 896.04/292.83 896.04/292.83 896.04/292.83 The TRS R consists of the following rules: 896.04/292.83 896.04/292.83 eeval(Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.83 eeval(Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.83 eeval(Error(e11, e12), ns, vs, p) -> eeval[False][Ite](False, Error(e11, e12), ns, vs, p) 896.04/292.83 eeval(F, ns, vs, p) -> F 896.04/292.83 eeval(T, ns, vs, p) -> T 896.04/292.83 eeval(ITE(i, t, e), ns, vs, p) -> eeval[Ite](checkConstrExp(eeval(i, ns, vs, p), T), ITE(i, t, e), ns, vs, p) 896.04/292.83 eeval(Bsf(op, t1, t2), ns, vs, p) -> eeval[Let](Bsf(op, t1, t2), ns, vs, p, eeval(t1, ns, vs, p)) 896.04/292.83 eeval(Var(int), ns, vs, p) -> lookvar(int, ns, vs) 896.04/292.83 run(Cons(Fun(f0, e), xs), input) -> run[Let][Let](Cons(Fun(f0, e), xs), input, f0, lookbody(f0, Cons(Fun(f0, e), xs))) 896.04/292.83 eqExp(Error(e11, e12), Error(e21, e22)) -> and(eqExp(e11, e21), eqExp(e12, e22)) 896.04/292.83 eqExp(Error(e11, e12), F) -> False 896.04/292.83 eqExp(Error(e11, e12), T) -> False 896.04/292.83 eqExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Error(e11, e12), Var(v2)) -> False 896.04/292.83 eqExp(F, Error(e21, e22)) -> False 896.04/292.83 eqExp(F, F) -> True 896.04/292.83 eqExp(F, T) -> False 896.04/292.83 eqExp(F, Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(F, Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(F, ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(F, Var(v2)) -> False 896.04/292.83 eqExp(T, Error(e21, e22)) -> False 896.04/292.83 eqExp(T, F) -> False 896.04/292.83 eqExp(T, T) -> True 896.04/292.83 eqExp(T, Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(T, Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(T, ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(T, Var(v2)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), F) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), T) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> and(!EQ(fn1, fn2), eqExp(fe1, fe2)) 896.04/292.83 eqExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), F) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), T) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> and(eqExp(eq11, eq21), eqExp(eq12, eq22)) 896.04/292.83 eqExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), F) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), T) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> and(eqExp(i1, i2), and(eqExp(t1, t2), eqExp(e1, e2))) 896.04/292.83 eqExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), F) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), T) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Bsf(o1, b11, b12), Bsf(o2, b21, b22)) -> and(True, and(eqExp(b11, b21), eqExp(b12, b22))) 896.04/292.83 eqExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.83 eqExp(Var(v1), Error(e21, e22)) -> False 896.04/292.83 eqExp(Var(v1), F) -> False 896.04/292.83 eqExp(Var(v1), T) -> False 896.04/292.83 eqExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Var(v1), Var(v2)) -> !EQ(v1, v2) 896.04/292.83 checkConstrExp(Error(e11, e12), Error(e21, e22)) -> True 896.04/292.83 checkConstrExp(Error(e11, e12), F) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), T) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Var(v2)) -> False 896.04/292.83 checkConstrExp(F, Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(F, F) -> True 896.04/292.83 checkConstrExp(F, T) -> False 896.04/292.83 checkConstrExp(F, Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(F, Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(F, ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(F, Var(v2)) -> False 896.04/292.83 checkConstrExp(T, Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(T, F) -> False 896.04/292.83 checkConstrExp(T, T) -> True 896.04/292.83 checkConstrExp(T, Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(T, Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(T, ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(T, Var(v2)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), F) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), T) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> True 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), F) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), T) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> True 896.04/292.83 checkConstrExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), F) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), T) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> True 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), F) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), T) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Bsf(op2, b21, b22)) -> True 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.83 checkConstrExp(Var(v1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Var(v1), F) -> False 896.04/292.83 checkConstrExp(Var(v1), T) -> False 896.04/292.83 checkConstrExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Var(v1), Var(v2)) -> True 896.04/292.83 lookname(f, Cons(Fun(n, e), xs)) -> lookname[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.83 lookbody(f, Cons(Fun(n, e), xs)) -> lookbody[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.83 getVar(Var(int)) -> int 896.04/292.83 getIfTrue(ITE(i, t, e)) -> t 896.04/292.83 getIfGuard(ITE(i, t, e)) -> i 896.04/292.83 getIfFalse(ITE(i, t, e)) -> e 896.04/292.83 getFuncName(Fun(n, e)) -> n 896.04/292.83 getFuncExp(Fun(n, e)) -> e 896.04/292.83 getEqSecond(Eq(f, s)) -> s 896.04/292.83 getEqFirst(Eq(f, s)) -> f 896.04/292.83 getConst(Cst(int)) -> int 896.04/292.83 getBsfSecondTerm(Bsf(op, t1, t2)) -> t2 896.04/292.83 getBsfOp(Bsf(op, t1, t2)) -> op 896.04/292.83 getBsfFirstTerm(Bsf(op, t1, t2)) -> t1 896.04/292.83 apply(op, v1, v2) -> apply[Ite](eqExp(v1, v2), op, v1, v2) 896.04/292.83 lookvar(x', Cons(x, xs), vs) -> lookvar[Ite](!EQ(x', x), x', Cons(x, xs), vs) 896.04/292.83 eqOps(o1, o2) -> True 896.04/292.83 896.04/292.83 The (relative) TRS S consists of the following rules: 896.04/292.83 896.04/292.83 !EQ(S(x), S(y)) -> !EQ(x, y) 896.04/292.83 !EQ(0, S(y)) -> False 896.04/292.83 !EQ(S(x), 0) -> False 896.04/292.83 !EQ(0, 0) -> True 896.04/292.83 and(False, False) -> False 896.04/292.83 and(True, False) -> False 896.04/292.83 and(False, True) -> False 896.04/292.83 and(True, True) -> True 896.04/292.83 eeval[False][Ite](True, Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.83 lookvar[Ite](False, x', Cons(x'', xs'), Cons(x, xs)) -> lookvar(x', xs', xs) 896.04/292.83 lookname[Ite](True, f, Cons(Fun(n, e), xs)) -> n 896.04/292.83 lookbody[Ite](True, f, Cons(Fun(n, e), xs)) -> e 896.04/292.83 eeval[False][Ite](False, Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.83 eeval[Ite](False, ITE(i, t, e), ns, vs, p) -> eeval(e, ns, vs, p) 896.04/292.83 eeval[Ite](True, ITE(i, t, e), ns, vs, p) -> eeval(t, ns, vs, p) 896.04/292.83 eeval[False][Let](Fun(n, e), ns, vs, p, ef) -> eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, lookname(n, p)) 896.04/292.83 eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, nf) -> eeval[Let][Let][Let](Fun(n, e), ns, vs, p, ef, nf, eeval(e, ns, vs, p)) 896.04/292.83 eeval[Let](Bsf(op, t1, t2), ns, vs, p, v1) -> eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, eeval(t2, ns, vs, p)) 896.04/292.83 eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, v2) -> apply(op, v1, v2) 896.04/292.83 lookvar[Ite](True, x', ns, Cons(x, xs)) -> x 896.04/292.83 lookname[Ite](False, f, Cons(x, xs)) -> lookname(f, xs) 896.04/292.83 lookbody[Ite](False, f, Cons(x, xs)) -> lookbody(f, xs) 896.04/292.83 eeval[True][Ite](False, e, ns, vs, p) -> F 896.04/292.83 eeval[True][Ite](True, e, ns, vs, p) -> T 896.04/292.83 apply[Ite](False, op, v1, v2) -> F 896.04/292.83 apply[Ite](True, op, v1, v2) -> T 896.04/292.83 run[Let][Let](p, input, f0, ef) -> run[Let](p, input, f0, ef, lookname(f0, p)) 896.04/292.83 run[Let](p, input, f0, ef, nf) -> eeval(ef, Cons(nf, Nil), Cons(input, Nil), p) 896.04/292.83 eeval[Let][Let][Let](e, ns, vs, p, ef, nf, v) -> eeval(ef, Cons(nf, Nil), Cons(v, Nil), p) 896.04/292.83 896.04/292.83 Rewrite Strategy: INNERMOST 896.04/292.83 ---------------------------------------- 896.04/292.83 896.04/292.83 (3) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 896.04/292.83 Transformed a relative TRS into a decreasing-loop problem. 896.04/292.83 ---------------------------------------- 896.04/292.83 896.04/292.83 (4) 896.04/292.83 Obligation: 896.04/292.83 Analyzing the following TRS for decreasing loops: 896.04/292.83 896.04/292.83 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 896.04/292.83 896.04/292.83 896.04/292.83 The TRS R consists of the following rules: 896.04/292.83 896.04/292.83 eeval(Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.83 eeval(Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.83 eeval(Error(e11, e12), ns, vs, p) -> eeval[False][Ite](False, Error(e11, e12), ns, vs, p) 896.04/292.83 eeval(F, ns, vs, p) -> F 896.04/292.83 eeval(T, ns, vs, p) -> T 896.04/292.83 eeval(ITE(i, t, e), ns, vs, p) -> eeval[Ite](checkConstrExp(eeval(i, ns, vs, p), T), ITE(i, t, e), ns, vs, p) 896.04/292.83 eeval(Bsf(op, t1, t2), ns, vs, p) -> eeval[Let](Bsf(op, t1, t2), ns, vs, p, eeval(t1, ns, vs, p)) 896.04/292.83 eeval(Var(int), ns, vs, p) -> lookvar(int, ns, vs) 896.04/292.83 run(Cons(Fun(f0, e), xs), input) -> run[Let][Let](Cons(Fun(f0, e), xs), input, f0, lookbody(f0, Cons(Fun(f0, e), xs))) 896.04/292.83 eqExp(Error(e11, e12), Error(e21, e22)) -> and(eqExp(e11, e21), eqExp(e12, e22)) 896.04/292.83 eqExp(Error(e11, e12), F) -> False 896.04/292.83 eqExp(Error(e11, e12), T) -> False 896.04/292.83 eqExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Error(e11, e12), Var(v2)) -> False 896.04/292.83 eqExp(F, Error(e21, e22)) -> False 896.04/292.83 eqExp(F, F) -> True 896.04/292.83 eqExp(F, T) -> False 896.04/292.83 eqExp(F, Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(F, Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(F, ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(F, Var(v2)) -> False 896.04/292.83 eqExp(T, Error(e21, e22)) -> False 896.04/292.83 eqExp(T, F) -> False 896.04/292.83 eqExp(T, T) -> True 896.04/292.83 eqExp(T, Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(T, Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(T, ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(T, Var(v2)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), F) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), T) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> and(!EQ(fn1, fn2), eqExp(fe1, fe2)) 896.04/292.83 eqExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), F) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), T) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> and(eqExp(eq11, eq21), eqExp(eq12, eq22)) 896.04/292.83 eqExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), F) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), T) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> and(eqExp(i1, i2), and(eqExp(t1, t2), eqExp(e1, e2))) 896.04/292.83 eqExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), F) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), T) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Bsf(o1, b11, b12), Bsf(o2, b21, b22)) -> and(True, and(eqExp(b11, b21), eqExp(b12, b22))) 896.04/292.83 eqExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.83 eqExp(Var(v1), Error(e21, e22)) -> False 896.04/292.83 eqExp(Var(v1), F) -> False 896.04/292.83 eqExp(Var(v1), T) -> False 896.04/292.83 eqExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Var(v1), Var(v2)) -> !EQ(v1, v2) 896.04/292.83 checkConstrExp(Error(e11, e12), Error(e21, e22)) -> True 896.04/292.83 checkConstrExp(Error(e11, e12), F) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), T) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Var(v2)) -> False 896.04/292.83 checkConstrExp(F, Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(F, F) -> True 896.04/292.83 checkConstrExp(F, T) -> False 896.04/292.83 checkConstrExp(F, Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(F, Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(F, ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(F, Var(v2)) -> False 896.04/292.83 checkConstrExp(T, Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(T, F) -> False 896.04/292.83 checkConstrExp(T, T) -> True 896.04/292.83 checkConstrExp(T, Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(T, Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(T, ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(T, Var(v2)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), F) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), T) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> True 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), F) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), T) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> True 896.04/292.83 checkConstrExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), F) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), T) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> True 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), F) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), T) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Bsf(op2, b21, b22)) -> True 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.83 checkConstrExp(Var(v1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Var(v1), F) -> False 896.04/292.83 checkConstrExp(Var(v1), T) -> False 896.04/292.83 checkConstrExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Var(v1), Var(v2)) -> True 896.04/292.83 lookname(f, Cons(Fun(n, e), xs)) -> lookname[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.83 lookbody(f, Cons(Fun(n, e), xs)) -> lookbody[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.83 getVar(Var(int)) -> int 896.04/292.83 getIfTrue(ITE(i, t, e)) -> t 896.04/292.83 getIfGuard(ITE(i, t, e)) -> i 896.04/292.83 getIfFalse(ITE(i, t, e)) -> e 896.04/292.83 getFuncName(Fun(n, e)) -> n 896.04/292.83 getFuncExp(Fun(n, e)) -> e 896.04/292.83 getEqSecond(Eq(f, s)) -> s 896.04/292.83 getEqFirst(Eq(f, s)) -> f 896.04/292.83 getConst(Cst(int)) -> int 896.04/292.83 getBsfSecondTerm(Bsf(op, t1, t2)) -> t2 896.04/292.83 getBsfOp(Bsf(op, t1, t2)) -> op 896.04/292.83 getBsfFirstTerm(Bsf(op, t1, t2)) -> t1 896.04/292.83 apply(op, v1, v2) -> apply[Ite](eqExp(v1, v2), op, v1, v2) 896.04/292.83 lookvar(x', Cons(x, xs), vs) -> lookvar[Ite](!EQ(x', x), x', Cons(x, xs), vs) 896.04/292.83 eqOps(o1, o2) -> True 896.04/292.83 896.04/292.83 The (relative) TRS S consists of the following rules: 896.04/292.83 896.04/292.83 !EQ(S(x), S(y)) -> !EQ(x, y) 896.04/292.83 !EQ(0, S(y)) -> False 896.04/292.83 !EQ(S(x), 0) -> False 896.04/292.83 !EQ(0, 0) -> True 896.04/292.83 and(False, False) -> False 896.04/292.83 and(True, False) -> False 896.04/292.83 and(False, True) -> False 896.04/292.83 and(True, True) -> True 896.04/292.83 eeval[False][Ite](True, Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.83 lookvar[Ite](False, x', Cons(x'', xs'), Cons(x, xs)) -> lookvar(x', xs', xs) 896.04/292.83 lookname[Ite](True, f, Cons(Fun(n, e), xs)) -> n 896.04/292.83 lookbody[Ite](True, f, Cons(Fun(n, e), xs)) -> e 896.04/292.83 eeval[False][Ite](False, Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.83 eeval[Ite](False, ITE(i, t, e), ns, vs, p) -> eeval(e, ns, vs, p) 896.04/292.83 eeval[Ite](True, ITE(i, t, e), ns, vs, p) -> eeval(t, ns, vs, p) 896.04/292.83 eeval[False][Let](Fun(n, e), ns, vs, p, ef) -> eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, lookname(n, p)) 896.04/292.83 eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, nf) -> eeval[Let][Let][Let](Fun(n, e), ns, vs, p, ef, nf, eeval(e, ns, vs, p)) 896.04/292.83 eeval[Let](Bsf(op, t1, t2), ns, vs, p, v1) -> eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, eeval(t2, ns, vs, p)) 896.04/292.83 eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, v2) -> apply(op, v1, v2) 896.04/292.83 lookvar[Ite](True, x', ns, Cons(x, xs)) -> x 896.04/292.83 lookname[Ite](False, f, Cons(x, xs)) -> lookname(f, xs) 896.04/292.83 lookbody[Ite](False, f, Cons(x, xs)) -> lookbody(f, xs) 896.04/292.83 eeval[True][Ite](False, e, ns, vs, p) -> F 896.04/292.83 eeval[True][Ite](True, e, ns, vs, p) -> T 896.04/292.83 apply[Ite](False, op, v1, v2) -> F 896.04/292.83 apply[Ite](True, op, v1, v2) -> T 896.04/292.83 run[Let][Let](p, input, f0, ef) -> run[Let](p, input, f0, ef, lookname(f0, p)) 896.04/292.83 run[Let](p, input, f0, ef, nf) -> eeval(ef, Cons(nf, Nil), Cons(input, Nil), p) 896.04/292.83 eeval[Let][Let][Let](e, ns, vs, p, ef, nf, v) -> eeval(ef, Cons(nf, Nil), Cons(v, Nil), p) 896.04/292.83 896.04/292.83 Rewrite Strategy: INNERMOST 896.04/292.83 ---------------------------------------- 896.04/292.83 896.04/292.83 (5) DecreasingLoopProof (LOWER BOUND(ID)) 896.04/292.83 The following loop(s) give(s) rise to the lower bound Omega(n^1): 896.04/292.83 896.04/292.83 The rewrite sequence 896.04/292.83 896.04/292.83 eeval(Bsf(op, t1, t2), ns, vs, p) ->^+ eeval[Let](Bsf(op, t1, t2), ns, vs, p, eeval(t1, ns, vs, p)) 896.04/292.83 896.04/292.83 gives rise to a decreasing loop by considering the right hand sides subterm at position [4]. 896.04/292.83 896.04/292.83 The pumping substitution is [t1 / Bsf(op, t1, t2)]. 896.04/292.83 896.04/292.83 The result substitution is [ ]. 896.04/292.83 896.04/292.83 896.04/292.83 896.04/292.83 896.04/292.83 ---------------------------------------- 896.04/292.83 896.04/292.83 (6) 896.04/292.83 Complex Obligation (BEST) 896.04/292.83 896.04/292.83 ---------------------------------------- 896.04/292.83 896.04/292.83 (7) 896.04/292.83 Obligation: 896.04/292.83 Proved the lower bound n^1 for the following obligation: 896.04/292.83 896.04/292.83 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 896.04/292.83 896.04/292.83 896.04/292.83 The TRS R consists of the following rules: 896.04/292.83 896.04/292.83 eeval(Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.83 eeval(Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.83 eeval(Error(e11, e12), ns, vs, p) -> eeval[False][Ite](False, Error(e11, e12), ns, vs, p) 896.04/292.83 eeval(F, ns, vs, p) -> F 896.04/292.83 eeval(T, ns, vs, p) -> T 896.04/292.83 eeval(ITE(i, t, e), ns, vs, p) -> eeval[Ite](checkConstrExp(eeval(i, ns, vs, p), T), ITE(i, t, e), ns, vs, p) 896.04/292.83 eeval(Bsf(op, t1, t2), ns, vs, p) -> eeval[Let](Bsf(op, t1, t2), ns, vs, p, eeval(t1, ns, vs, p)) 896.04/292.83 eeval(Var(int), ns, vs, p) -> lookvar(int, ns, vs) 896.04/292.83 run(Cons(Fun(f0, e), xs), input) -> run[Let][Let](Cons(Fun(f0, e), xs), input, f0, lookbody(f0, Cons(Fun(f0, e), xs))) 896.04/292.83 eqExp(Error(e11, e12), Error(e21, e22)) -> and(eqExp(e11, e21), eqExp(e12, e22)) 896.04/292.83 eqExp(Error(e11, e12), F) -> False 896.04/292.83 eqExp(Error(e11, e12), T) -> False 896.04/292.83 eqExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Error(e11, e12), Var(v2)) -> False 896.04/292.83 eqExp(F, Error(e21, e22)) -> False 896.04/292.83 eqExp(F, F) -> True 896.04/292.83 eqExp(F, T) -> False 896.04/292.83 eqExp(F, Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(F, Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(F, ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(F, Var(v2)) -> False 896.04/292.83 eqExp(T, Error(e21, e22)) -> False 896.04/292.83 eqExp(T, F) -> False 896.04/292.83 eqExp(T, T) -> True 896.04/292.83 eqExp(T, Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(T, Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(T, ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(T, Var(v2)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), F) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), T) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> and(!EQ(fn1, fn2), eqExp(fe1, fe2)) 896.04/292.83 eqExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), F) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), T) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> and(eqExp(eq11, eq21), eqExp(eq12, eq22)) 896.04/292.83 eqExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), F) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), T) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> and(eqExp(i1, i2), and(eqExp(t1, t2), eqExp(e1, e2))) 896.04/292.83 eqExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), F) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), T) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Bsf(o1, b11, b12), Bsf(o2, b21, b22)) -> and(True, and(eqExp(b11, b21), eqExp(b12, b22))) 896.04/292.83 eqExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.83 eqExp(Var(v1), Error(e21, e22)) -> False 896.04/292.83 eqExp(Var(v1), F) -> False 896.04/292.83 eqExp(Var(v1), T) -> False 896.04/292.83 eqExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.83 eqExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.83 eqExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.83 eqExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.83 eqExp(Var(v1), Var(v2)) -> !EQ(v1, v2) 896.04/292.83 checkConstrExp(Error(e11, e12), Error(e21, e22)) -> True 896.04/292.83 checkConstrExp(Error(e11, e12), F) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), T) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Error(e11, e12), Var(v2)) -> False 896.04/292.83 checkConstrExp(F, Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(F, F) -> True 896.04/292.83 checkConstrExp(F, T) -> False 896.04/292.83 checkConstrExp(F, Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(F, Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(F, ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(F, Var(v2)) -> False 896.04/292.83 checkConstrExp(T, Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(T, F) -> False 896.04/292.83 checkConstrExp(T, T) -> True 896.04/292.83 checkConstrExp(T, Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(T, Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(T, ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(T, Var(v2)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), F) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), T) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> True 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), F) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), T) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> True 896.04/292.83 checkConstrExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), F) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), T) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> True 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.83 checkConstrExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), F) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), T) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.83 checkConstrExp(Bsf(op1, b11, b12), Bsf(op2, b21, b22)) -> True 896.04/292.84 checkConstrExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.84 checkConstrExp(Var(v1), Error(e21, e22)) -> False 896.04/292.84 checkConstrExp(Var(v1), F) -> False 896.04/292.84 checkConstrExp(Var(v1), T) -> False 896.04/292.84 checkConstrExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.84 checkConstrExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.84 checkConstrExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.84 checkConstrExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.84 checkConstrExp(Var(v1), Var(v2)) -> True 896.04/292.84 lookname(f, Cons(Fun(n, e), xs)) -> lookname[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.84 lookbody(f, Cons(Fun(n, e), xs)) -> lookbody[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.84 getVar(Var(int)) -> int 896.04/292.84 getIfTrue(ITE(i, t, e)) -> t 896.04/292.84 getIfGuard(ITE(i, t, e)) -> i 896.04/292.84 getIfFalse(ITE(i, t, e)) -> e 896.04/292.84 getFuncName(Fun(n, e)) -> n 896.04/292.84 getFuncExp(Fun(n, e)) -> e 896.04/292.84 getEqSecond(Eq(f, s)) -> s 896.04/292.84 getEqFirst(Eq(f, s)) -> f 896.04/292.84 getConst(Cst(int)) -> int 896.04/292.84 getBsfSecondTerm(Bsf(op, t1, t2)) -> t2 896.04/292.84 getBsfOp(Bsf(op, t1, t2)) -> op 896.04/292.84 getBsfFirstTerm(Bsf(op, t1, t2)) -> t1 896.04/292.84 apply(op, v1, v2) -> apply[Ite](eqExp(v1, v2), op, v1, v2) 896.04/292.84 lookvar(x', Cons(x, xs), vs) -> lookvar[Ite](!EQ(x', x), x', Cons(x, xs), vs) 896.04/292.84 eqOps(o1, o2) -> True 896.04/292.84 896.04/292.84 The (relative) TRS S consists of the following rules: 896.04/292.84 896.04/292.84 !EQ(S(x), S(y)) -> !EQ(x, y) 896.04/292.84 !EQ(0, S(y)) -> False 896.04/292.84 !EQ(S(x), 0) -> False 896.04/292.84 !EQ(0, 0) -> True 896.04/292.84 and(False, False) -> False 896.04/292.84 and(True, False) -> False 896.04/292.84 and(False, True) -> False 896.04/292.84 and(True, True) -> True 896.04/292.84 eeval[False][Ite](True, Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.84 lookvar[Ite](False, x', Cons(x'', xs'), Cons(x, xs)) -> lookvar(x', xs', xs) 896.04/292.84 lookname[Ite](True, f, Cons(Fun(n, e), xs)) -> n 896.04/292.84 lookbody[Ite](True, f, Cons(Fun(n, e), xs)) -> e 896.04/292.84 eeval[False][Ite](False, Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.84 eeval[Ite](False, ITE(i, t, e), ns, vs, p) -> eeval(e, ns, vs, p) 896.04/292.84 eeval[Ite](True, ITE(i, t, e), ns, vs, p) -> eeval(t, ns, vs, p) 896.04/292.84 eeval[False][Let](Fun(n, e), ns, vs, p, ef) -> eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, lookname(n, p)) 896.04/292.84 eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, nf) -> eeval[Let][Let][Let](Fun(n, e), ns, vs, p, ef, nf, eeval(e, ns, vs, p)) 896.04/292.84 eeval[Let](Bsf(op, t1, t2), ns, vs, p, v1) -> eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, eeval(t2, ns, vs, p)) 896.04/292.84 eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, v2) -> apply(op, v1, v2) 896.04/292.84 lookvar[Ite](True, x', ns, Cons(x, xs)) -> x 896.04/292.84 lookname[Ite](False, f, Cons(x, xs)) -> lookname(f, xs) 896.04/292.84 lookbody[Ite](False, f, Cons(x, xs)) -> lookbody(f, xs) 896.04/292.84 eeval[True][Ite](False, e, ns, vs, p) -> F 896.04/292.84 eeval[True][Ite](True, e, ns, vs, p) -> T 896.04/292.84 apply[Ite](False, op, v1, v2) -> F 896.04/292.84 apply[Ite](True, op, v1, v2) -> T 896.04/292.84 run[Let][Let](p, input, f0, ef) -> run[Let](p, input, f0, ef, lookname(f0, p)) 896.04/292.84 run[Let](p, input, f0, ef, nf) -> eeval(ef, Cons(nf, Nil), Cons(input, Nil), p) 896.04/292.84 eeval[Let][Let][Let](e, ns, vs, p, ef, nf, v) -> eeval(ef, Cons(nf, Nil), Cons(v, Nil), p) 896.04/292.84 896.04/292.84 Rewrite Strategy: INNERMOST 896.04/292.84 ---------------------------------------- 896.04/292.84 896.04/292.84 (8) LowerBoundPropagationProof (FINISHED) 896.04/292.84 Propagated lower bound. 896.04/292.84 ---------------------------------------- 896.04/292.84 896.04/292.84 (9) 896.04/292.84 BOUNDS(n^1, INF) 896.04/292.84 896.04/292.84 ---------------------------------------- 896.04/292.84 896.04/292.84 (10) 896.04/292.84 Obligation: 896.04/292.84 Analyzing the following TRS for decreasing loops: 896.04/292.84 896.04/292.84 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 896.04/292.84 896.04/292.84 896.04/292.84 The TRS R consists of the following rules: 896.04/292.84 896.04/292.84 eeval(Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.84 eeval(Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.84 eeval(Error(e11, e12), ns, vs, p) -> eeval[False][Ite](False, Error(e11, e12), ns, vs, p) 896.04/292.84 eeval(F, ns, vs, p) -> F 896.04/292.84 eeval(T, ns, vs, p) -> T 896.04/292.84 eeval(ITE(i, t, e), ns, vs, p) -> eeval[Ite](checkConstrExp(eeval(i, ns, vs, p), T), ITE(i, t, e), ns, vs, p) 896.04/292.84 eeval(Bsf(op, t1, t2), ns, vs, p) -> eeval[Let](Bsf(op, t1, t2), ns, vs, p, eeval(t1, ns, vs, p)) 896.04/292.84 eeval(Var(int), ns, vs, p) -> lookvar(int, ns, vs) 896.04/292.84 run(Cons(Fun(f0, e), xs), input) -> run[Let][Let](Cons(Fun(f0, e), xs), input, f0, lookbody(f0, Cons(Fun(f0, e), xs))) 896.04/292.84 eqExp(Error(e11, e12), Error(e21, e22)) -> and(eqExp(e11, e21), eqExp(e12, e22)) 896.04/292.84 eqExp(Error(e11, e12), F) -> False 896.04/292.84 eqExp(Error(e11, e12), T) -> False 896.04/292.84 eqExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.84 eqExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.84 eqExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.84 eqExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.84 eqExp(Error(e11, e12), Var(v2)) -> False 896.04/292.84 eqExp(F, Error(e21, e22)) -> False 896.04/292.84 eqExp(F, F) -> True 896.04/292.84 eqExp(F, T) -> False 896.04/292.84 eqExp(F, Fun(fn2, fe2)) -> False 896.04/292.84 eqExp(F, Eq(eq21, eq22)) -> False 896.04/292.84 eqExp(F, ITE(i2, t2, e2)) -> False 896.04/292.84 eqExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.84 eqExp(F, Var(v2)) -> False 896.04/292.84 eqExp(T, Error(e21, e22)) -> False 896.04/292.84 eqExp(T, F) -> False 896.04/292.84 eqExp(T, T) -> True 896.04/292.84 eqExp(T, Fun(fn2, fe2)) -> False 896.04/292.84 eqExp(T, Eq(eq21, eq22)) -> False 896.04/292.84 eqExp(T, ITE(i2, t2, e2)) -> False 896.04/292.84 eqExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.84 eqExp(T, Var(v2)) -> False 896.04/292.84 eqExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.84 eqExp(Fun(fn1, fe1), F) -> False 896.04/292.84 eqExp(Fun(fn1, fe1), T) -> False 896.04/292.84 eqExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> and(!EQ(fn1, fn2), eqExp(fe1, fe2)) 896.04/292.84 eqExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.84 eqExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.84 eqExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.84 eqExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.84 eqExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.84 eqExp(Eq(eq11, eq12), F) -> False 896.04/292.84 eqExp(Eq(eq11, eq12), T) -> False 896.04/292.84 eqExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.84 eqExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> and(eqExp(eq11, eq21), eqExp(eq12, eq22)) 896.04/292.84 eqExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.84 eqExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.84 eqExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.84 eqExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.84 eqExp(ITE(i1, t1, e1), F) -> False 896.04/292.84 eqExp(ITE(i1, t1, e1), T) -> False 896.04/292.84 eqExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.84 eqExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.84 eqExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> and(eqExp(i1, i2), and(eqExp(t1, t2), eqExp(e1, e2))) 896.04/292.84 eqExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.84 eqExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.84 eqExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.84 eqExp(Bsf(op1, b11, b12), F) -> False 896.04/292.84 eqExp(Bsf(op1, b11, b12), T) -> False 896.04/292.84 eqExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.84 eqExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.84 eqExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.84 eqExp(Bsf(o1, b11, b12), Bsf(o2, b21, b22)) -> and(True, and(eqExp(b11, b21), eqExp(b12, b22))) 896.04/292.84 eqExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.84 eqExp(Var(v1), Error(e21, e22)) -> False 896.04/292.84 eqExp(Var(v1), F) -> False 896.04/292.84 eqExp(Var(v1), T) -> False 896.04/292.84 eqExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.84 eqExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.84 eqExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.84 eqExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.84 eqExp(Var(v1), Var(v2)) -> !EQ(v1, v2) 896.04/292.84 checkConstrExp(Error(e11, e12), Error(e21, e22)) -> True 896.04/292.84 checkConstrExp(Error(e11, e12), F) -> False 896.04/292.84 checkConstrExp(Error(e11, e12), T) -> False 896.04/292.84 checkConstrExp(Error(e11, e12), Fun(fn2, fe2)) -> False 896.04/292.84 checkConstrExp(Error(e11, e12), Eq(eq21, eq22)) -> False 896.04/292.84 checkConstrExp(Error(e11, e12), ITE(i2, t2, e2)) -> False 896.04/292.84 checkConstrExp(Error(e11, e12), Bsf(op2, b21, b22)) -> False 896.04/292.84 checkConstrExp(Error(e11, e12), Var(v2)) -> False 896.04/292.84 checkConstrExp(F, Error(e21, e22)) -> False 896.04/292.84 checkConstrExp(F, F) -> True 896.04/292.84 checkConstrExp(F, T) -> False 896.04/292.84 checkConstrExp(F, Fun(fn2, fe2)) -> False 896.04/292.84 checkConstrExp(F, Eq(eq21, eq22)) -> False 896.04/292.84 checkConstrExp(F, ITE(i2, t2, e2)) -> False 896.04/292.84 checkConstrExp(F, Bsf(op2, b21, b22)) -> False 896.04/292.84 checkConstrExp(F, Var(v2)) -> False 896.04/292.84 checkConstrExp(T, Error(e21, e22)) -> False 896.04/292.84 checkConstrExp(T, F) -> False 896.04/292.84 checkConstrExp(T, T) -> True 896.04/292.84 checkConstrExp(T, Fun(fn2, fe2)) -> False 896.04/292.84 checkConstrExp(T, Eq(eq21, eq22)) -> False 896.04/292.84 checkConstrExp(T, ITE(i2, t2, e2)) -> False 896.04/292.84 checkConstrExp(T, Bsf(op2, b21, b22)) -> False 896.04/292.84 checkConstrExp(T, Var(v2)) -> False 896.04/292.84 checkConstrExp(Fun(fn1, fe1), Error(e21, e22)) -> False 896.04/292.84 checkConstrExp(Fun(fn1, fe1), F) -> False 896.04/292.84 checkConstrExp(Fun(fn1, fe1), T) -> False 896.04/292.84 checkConstrExp(Fun(fn1, fe1), Fun(fn2, fe2)) -> True 896.04/292.84 checkConstrExp(Fun(fn1, fe1), Eq(eq21, eq22)) -> False 896.04/292.84 checkConstrExp(Fun(fn1, fe1), ITE(i2, t2, e2)) -> False 896.04/292.84 checkConstrExp(Fun(fn1, fe1), Bsf(op2, b21, b22)) -> False 896.04/292.84 checkConstrExp(Fun(fn1, fe1), Var(v2)) -> False 896.04/292.84 checkConstrExp(Eq(eq11, eq12), Error(e21, e22)) -> False 896.04/292.84 checkConstrExp(Eq(eq11, eq12), F) -> False 896.04/292.84 checkConstrExp(Eq(eq11, eq12), T) -> False 896.04/292.84 checkConstrExp(Eq(eq11, eq12), Fun(fn2, fe2)) -> False 896.04/292.84 checkConstrExp(Eq(eq11, eq12), Eq(eq21, eq22)) -> True 896.04/292.84 checkConstrExp(Eq(eq11, eq12), ITE(i2, t2, e2)) -> False 896.04/292.84 checkConstrExp(Eq(eq11, eq12), Bsf(op2, b21, b22)) -> False 896.04/292.84 checkConstrExp(Eq(eq11, eq12), Var(v2)) -> False 896.04/292.84 checkConstrExp(ITE(i1, t1, e1), Error(e21, e22)) -> False 896.04/292.84 checkConstrExp(ITE(i1, t1, e1), F) -> False 896.04/292.84 checkConstrExp(ITE(i1, t1, e1), T) -> False 896.04/292.84 checkConstrExp(ITE(i1, t1, e1), Fun(fn2, fe2)) -> False 896.04/292.84 checkConstrExp(ITE(i1, t1, e1), Eq(eq21, eq22)) -> False 896.04/292.84 checkConstrExp(ITE(i1, t1, e1), ITE(i2, t2, e2)) -> True 896.04/292.84 checkConstrExp(ITE(i1, t1, e1), Bsf(op2, b21, b22)) -> False 896.04/292.84 checkConstrExp(ITE(i1, t1, e1), Var(v2)) -> False 896.04/292.84 checkConstrExp(Bsf(op1, b11, b12), Error(e21, e22)) -> False 896.04/292.84 checkConstrExp(Bsf(op1, b11, b12), F) -> False 896.04/292.84 checkConstrExp(Bsf(op1, b11, b12), T) -> False 896.04/292.84 checkConstrExp(Bsf(op1, b11, b12), Fun(fn2, fe2)) -> False 896.04/292.84 checkConstrExp(Bsf(op1, b11, b12), Eq(eq21, eq22)) -> False 896.04/292.84 checkConstrExp(Bsf(op1, b11, b12), ITE(i2, t2, e2)) -> False 896.04/292.84 checkConstrExp(Bsf(op1, b11, b12), Bsf(op2, b21, b22)) -> True 896.04/292.84 checkConstrExp(Bsf(op1, b11, b12), Var(v2)) -> False 896.04/292.84 checkConstrExp(Var(v1), Error(e21, e22)) -> False 896.04/292.84 checkConstrExp(Var(v1), F) -> False 896.04/292.84 checkConstrExp(Var(v1), T) -> False 896.04/292.84 checkConstrExp(Var(v1), Fun(fn2, fe2)) -> False 896.04/292.84 checkConstrExp(Var(v1), Eq(eq21, eq22)) -> False 896.04/292.84 checkConstrExp(Var(v1), ITE(i2, t2, e2)) -> False 896.04/292.84 checkConstrExp(Var(v1), Bsf(op2, b21, b22)) -> False 896.04/292.84 checkConstrExp(Var(v1), Var(v2)) -> True 896.04/292.84 lookname(f, Cons(Fun(n, e), xs)) -> lookname[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.84 lookbody(f, Cons(Fun(n, e), xs)) -> lookbody[Ite](!EQ(f, n), f, Cons(Fun(n, e), xs)) 896.04/292.84 getVar(Var(int)) -> int 896.04/292.84 getIfTrue(ITE(i, t, e)) -> t 896.04/292.84 getIfGuard(ITE(i, t, e)) -> i 896.04/292.84 getIfFalse(ITE(i, t, e)) -> e 896.04/292.84 getFuncName(Fun(n, e)) -> n 896.04/292.84 getFuncExp(Fun(n, e)) -> e 896.04/292.84 getEqSecond(Eq(f, s)) -> s 896.04/292.84 getEqFirst(Eq(f, s)) -> f 896.04/292.84 getConst(Cst(int)) -> int 896.04/292.84 getBsfSecondTerm(Bsf(op, t1, t2)) -> t2 896.04/292.84 getBsfOp(Bsf(op, t1, t2)) -> op 896.04/292.84 getBsfFirstTerm(Bsf(op, t1, t2)) -> t1 896.04/292.84 apply(op, v1, v2) -> apply[Ite](eqExp(v1, v2), op, v1, v2) 896.04/292.84 lookvar(x', Cons(x, xs), vs) -> lookvar[Ite](!EQ(x', x), x', Cons(x, xs), vs) 896.04/292.84 eqOps(o1, o2) -> True 896.04/292.84 896.04/292.84 The (relative) TRS S consists of the following rules: 896.04/292.84 896.04/292.84 !EQ(S(x), S(y)) -> !EQ(x, y) 896.04/292.84 !EQ(0, S(y)) -> False 896.04/292.84 !EQ(S(x), 0) -> False 896.04/292.84 !EQ(0, 0) -> True 896.04/292.84 and(False, False) -> False 896.04/292.84 and(True, False) -> False 896.04/292.84 and(False, True) -> False 896.04/292.84 and(True, True) -> True 896.04/292.84 eeval[False][Ite](True, Eq(f, s), ns, vs, p) -> eeval[True][Ite](eqExp(eeval(f, ns, vs, p), eeval(s, ns, vs, p)), Eq(f, s), ns, vs, p) 896.04/292.84 lookvar[Ite](False, x', Cons(x'', xs'), Cons(x, xs)) -> lookvar(x', xs', xs) 896.04/292.84 lookname[Ite](True, f, Cons(Fun(n, e), xs)) -> n 896.04/292.84 lookbody[Ite](True, f, Cons(Fun(n, e), xs)) -> e 896.04/292.84 eeval[False][Ite](False, Fun(n, e), ns, vs, p) -> eeval[False][Let](Fun(n, e), ns, vs, p, lookbody(n, p)) 896.04/292.84 eeval[Ite](False, ITE(i, t, e), ns, vs, p) -> eeval(e, ns, vs, p) 896.04/292.84 eeval[Ite](True, ITE(i, t, e), ns, vs, p) -> eeval(t, ns, vs, p) 896.04/292.84 eeval[False][Let](Fun(n, e), ns, vs, p, ef) -> eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, lookname(n, p)) 896.04/292.84 eeval[False][Let][Let](Fun(n, e), ns, vs, p, ef, nf) -> eeval[Let][Let][Let](Fun(n, e), ns, vs, p, ef, nf, eeval(e, ns, vs, p)) 896.04/292.84 eeval[Let](Bsf(op, t1, t2), ns, vs, p, v1) -> eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, eeval(t2, ns, vs, p)) 896.04/292.84 eeval[Let][Let](Bsf(op, t1, t2), ns, vs, p, v1, v2) -> apply(op, v1, v2) 896.04/292.84 lookvar[Ite](True, x', ns, Cons(x, xs)) -> x 896.04/292.84 lookname[Ite](False, f, Cons(x, xs)) -> lookname(f, xs) 896.04/292.84 lookbody[Ite](False, f, Cons(x, xs)) -> lookbody(f, xs) 896.04/292.84 eeval[True][Ite](False, e, ns, vs, p) -> F 896.04/292.84 eeval[True][Ite](True, e, ns, vs, p) -> T 896.04/292.84 apply[Ite](False, op, v1, v2) -> F 896.04/292.84 apply[Ite](True, op, v1, v2) -> T 896.04/292.84 run[Let][Let](p, input, f0, ef) -> run[Let](p, input, f0, ef, lookname(f0, p)) 896.04/292.84 run[Let](p, input, f0, ef, nf) -> eeval(ef, Cons(nf, Nil), Cons(input, Nil), p) 896.04/292.84 eeval[Let][Let][Let](e, ns, vs, p, ef, nf, v) -> eeval(ef, Cons(nf, Nil), Cons(v, Nil), p) 896.04/292.84 896.04/292.84 Rewrite Strategy: INNERMOST 896.23/292.91 EOF