and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
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)))
Renamed function symbols to avoid clashes with predefined symbol.
Runtime Complexity TRS:
The TRS R consists of the following rules:
and'(false', false') → false'
and'(true', false') → false'
and'(false', true') → false'
and'(true', true') → true'
eq'(nil', nil') → true'
eq'(cons'(T, L), nil') → false'
eq'(nil', cons'(T, L)) → false'
eq'(cons'(T, L), cons'(Tp, Lp)) → and'(eq'(T, Tp), eq'(L, Lp))
eq'(var'(L), var'(Lp)) → eq'(L, Lp)
eq'(var'(L), apply'(T, S)) → false'
eq'(var'(L), lambda'(X, T)) → false'
eq'(apply'(T, S), var'(L)) → false'
eq'(apply'(T, S), apply'(Tp, Sp)) → and'(eq'(T, Tp), eq'(S, Sp))
eq'(apply'(T, S), lambda'(X, Tp)) → false'
eq'(lambda'(X, T), var'(L)) → false'
eq'(lambda'(X, T), apply'(Tp, Sp)) → false'
eq'(lambda'(X, T), lambda'(Xp, Tp)) → and'(eq'(T, Tp), eq'(X, Xp))
if'(true', var'(K), var'(L)) → var'(K)
if'(false', var'(K), var'(L)) → var'(L)
ren'(var'(L), var'(K), var'(Lp)) → if'(eq'(L, Lp), var'(K), var'(Lp))
ren'(X, Y, apply'(T, S)) → apply'(ren'(X, Y, T), ren'(X, Y, S))
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)))
Infered types.
Rules:
and'(false', false') → false'
and'(true', false') → false'
and'(false', true') → false'
and'(true', true') → true'
eq'(nil', nil') → true'
eq'(cons'(T, L), nil') → false'
eq'(nil', cons'(T, L)) → false'
eq'(cons'(T, L), cons'(Tp, Lp)) → and'(eq'(T, Tp), eq'(L, Lp))
eq'(var'(L), var'(Lp)) → eq'(L, Lp)
eq'(var'(L), apply'(T, S)) → false'
eq'(var'(L), lambda'(X, T)) → false'
eq'(apply'(T, S), var'(L)) → false'
eq'(apply'(T, S), apply'(Tp, Sp)) → and'(eq'(T, Tp), eq'(S, Sp))
eq'(apply'(T, S), lambda'(X, Tp)) → false'
eq'(lambda'(X, T), var'(L)) → false'
eq'(lambda'(X, T), apply'(Tp, Sp)) → false'
eq'(lambda'(X, T), lambda'(Xp, Tp)) → and'(eq'(T, Tp), eq'(X, Xp))
if'(true', var'(K), var'(L)) → var'(K)
if'(false', var'(K), var'(L)) → var'(L)
ren'(var'(L), var'(K), var'(Lp)) → if'(eq'(L, Lp), var'(K), var'(Lp))
ren'(X, Y, apply'(T, S)) → apply'(ren'(X, Y, T), ren'(X, Y, S))
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)))
Types:
and' :: false':true' → false':true' → false':true'
false' :: false':true'
true' :: false':true'
eq' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → false':true'
nil' :: nil':cons':var':apply':lambda'
cons' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
var' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
apply' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
lambda' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
if' :: false':true' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
ren' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
_hole_false':true'1 :: false':true'
_hole_nil':cons':var':apply':lambda'2 :: nil':cons':var':apply':lambda'
_gen_nil':cons':var':apply':lambda'3 :: Nat → nil':cons':var':apply':lambda'
Heuristically decided to analyse the following defined symbols:
eq', ren'
They will be analysed ascendingly in the following order:
eq' < ren'
Rules:
and'(false', false') → false'
and'(true', false') → false'
and'(false', true') → false'
and'(true', true') → true'
eq'(nil', nil') → true'
eq'(cons'(T, L), nil') → false'
eq'(nil', cons'(T, L)) → false'
eq'(cons'(T, L), cons'(Tp, Lp)) → and'(eq'(T, Tp), eq'(L, Lp))
eq'(var'(L), var'(Lp)) → eq'(L, Lp)
eq'(var'(L), apply'(T, S)) → false'
eq'(var'(L), lambda'(X, T)) → false'
eq'(apply'(T, S), var'(L)) → false'
eq'(apply'(T, S), apply'(Tp, Sp)) → and'(eq'(T, Tp), eq'(S, Sp))
eq'(apply'(T, S), lambda'(X, Tp)) → false'
eq'(lambda'(X, T), var'(L)) → false'
eq'(lambda'(X, T), apply'(Tp, Sp)) → false'
eq'(lambda'(X, T), lambda'(Xp, Tp)) → and'(eq'(T, Tp), eq'(X, Xp))
if'(true', var'(K), var'(L)) → var'(K)
if'(false', var'(K), var'(L)) → var'(L)
ren'(var'(L), var'(K), var'(Lp)) → if'(eq'(L, Lp), var'(K), var'(Lp))
ren'(X, Y, apply'(T, S)) → apply'(ren'(X, Y, T), ren'(X, Y, S))
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)))
Types:
and' :: false':true' → false':true' → false':true'
false' :: false':true'
true' :: false':true'
eq' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → false':true'
nil' :: nil':cons':var':apply':lambda'
cons' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
var' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
apply' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
lambda' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
if' :: false':true' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
ren' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
_hole_false':true'1 :: false':true'
_hole_nil':cons':var':apply':lambda'2 :: nil':cons':var':apply':lambda'
_gen_nil':cons':var':apply':lambda'3 :: Nat → nil':cons':var':apply':lambda'
Generator Equations:
_gen_nil':cons':var':apply':lambda'3(0) ⇔ nil'
_gen_nil':cons':var':apply':lambda'3(+(x, 1)) ⇔ cons'(nil', _gen_nil':cons':var':apply':lambda'3(x))
The following defined symbols remain to be analysed:
eq', ren'
They will be analysed ascendingly in the following order:
eq' < ren'
Proved the following rewrite lemma:
eq'(_gen_nil':cons':var':apply':lambda'3(_n5), _gen_nil':cons':var':apply':lambda'3(_n5)) → true', rt ∈ Ω(1 + n5)
Induction Base:
eq'(_gen_nil':cons':var':apply':lambda'3(0), _gen_nil':cons':var':apply':lambda'3(0)) →RΩ(1)
true'
Induction Step:
eq'(_gen_nil':cons':var':apply':lambda'3(+(_$n6, 1)), _gen_nil':cons':var':apply':lambda'3(+(_$n6, 1))) →RΩ(1)
and'(eq'(nil', nil'), eq'(_gen_nil':cons':var':apply':lambda'3(_$n6), _gen_nil':cons':var':apply':lambda'3(_$n6))) →RΩ(1)
and'(true', eq'(_gen_nil':cons':var':apply':lambda'3(_$n6), _gen_nil':cons':var':apply':lambda'3(_$n6))) →IH
and'(true', true') →RΩ(1)
true'
We have rt ∈ Ω(n) and sz ∈ O(n). Thus, we have ircR ∈ Ω(n).
Rules:
and'(false', false') → false'
and'(true', false') → false'
and'(false', true') → false'
and'(true', true') → true'
eq'(nil', nil') → true'
eq'(cons'(T, L), nil') → false'
eq'(nil', cons'(T, L)) → false'
eq'(cons'(T, L), cons'(Tp, Lp)) → and'(eq'(T, Tp), eq'(L, Lp))
eq'(var'(L), var'(Lp)) → eq'(L, Lp)
eq'(var'(L), apply'(T, S)) → false'
eq'(var'(L), lambda'(X, T)) → false'
eq'(apply'(T, S), var'(L)) → false'
eq'(apply'(T, S), apply'(Tp, Sp)) → and'(eq'(T, Tp), eq'(S, Sp))
eq'(apply'(T, S), lambda'(X, Tp)) → false'
eq'(lambda'(X, T), var'(L)) → false'
eq'(lambda'(X, T), apply'(Tp, Sp)) → false'
eq'(lambda'(X, T), lambda'(Xp, Tp)) → and'(eq'(T, Tp), eq'(X, Xp))
if'(true', var'(K), var'(L)) → var'(K)
if'(false', var'(K), var'(L)) → var'(L)
ren'(var'(L), var'(K), var'(Lp)) → if'(eq'(L, Lp), var'(K), var'(Lp))
ren'(X, Y, apply'(T, S)) → apply'(ren'(X, Y, T), ren'(X, Y, S))
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)))
Types:
and' :: false':true' → false':true' → false':true'
false' :: false':true'
true' :: false':true'
eq' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → false':true'
nil' :: nil':cons':var':apply':lambda'
cons' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
var' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
apply' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
lambda' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
if' :: false':true' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
ren' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
_hole_false':true'1 :: false':true'
_hole_nil':cons':var':apply':lambda'2 :: nil':cons':var':apply':lambda'
_gen_nil':cons':var':apply':lambda'3 :: Nat → nil':cons':var':apply':lambda'
Lemmas:
eq'(_gen_nil':cons':var':apply':lambda'3(_n5), _gen_nil':cons':var':apply':lambda'3(_n5)) → true', rt ∈ Ω(1 + n5)
Generator Equations:
_gen_nil':cons':var':apply':lambda'3(0) ⇔ nil'
_gen_nil':cons':var':apply':lambda'3(+(x, 1)) ⇔ cons'(nil', _gen_nil':cons':var':apply':lambda'3(x))
The following defined symbols remain to be analysed:
ren'
Could not prove a rewrite lemma for the defined symbol ren'.
Rules:
and'(false', false') → false'
and'(true', false') → false'
and'(false', true') → false'
and'(true', true') → true'
eq'(nil', nil') → true'
eq'(cons'(T, L), nil') → false'
eq'(nil', cons'(T, L)) → false'
eq'(cons'(T, L), cons'(Tp, Lp)) → and'(eq'(T, Tp), eq'(L, Lp))
eq'(var'(L), var'(Lp)) → eq'(L, Lp)
eq'(var'(L), apply'(T, S)) → false'
eq'(var'(L), lambda'(X, T)) → false'
eq'(apply'(T, S), var'(L)) → false'
eq'(apply'(T, S), apply'(Tp, Sp)) → and'(eq'(T, Tp), eq'(S, Sp))
eq'(apply'(T, S), lambda'(X, Tp)) → false'
eq'(lambda'(X, T), var'(L)) → false'
eq'(lambda'(X, T), apply'(Tp, Sp)) → false'
eq'(lambda'(X, T), lambda'(Xp, Tp)) → and'(eq'(T, Tp), eq'(X, Xp))
if'(true', var'(K), var'(L)) → var'(K)
if'(false', var'(K), var'(L)) → var'(L)
ren'(var'(L), var'(K), var'(Lp)) → if'(eq'(L, Lp), var'(K), var'(Lp))
ren'(X, Y, apply'(T, S)) → apply'(ren'(X, Y, T), ren'(X, Y, S))
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)))
Types:
and' :: false':true' → false':true' → false':true'
false' :: false':true'
true' :: false':true'
eq' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → false':true'
nil' :: nil':cons':var':apply':lambda'
cons' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
var' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
apply' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
lambda' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
if' :: false':true' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
ren' :: nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda' → nil':cons':var':apply':lambda'
_hole_false':true'1 :: false':true'
_hole_nil':cons':var':apply':lambda'2 :: nil':cons':var':apply':lambda'
_gen_nil':cons':var':apply':lambda'3 :: Nat → nil':cons':var':apply':lambda'
Lemmas:
eq'(_gen_nil':cons':var':apply':lambda'3(_n5), _gen_nil':cons':var':apply':lambda'3(_n5)) → true', rt ∈ Ω(1 + n5)
Generator Equations:
_gen_nil':cons':var':apply':lambda'3(0) ⇔ nil'
_gen_nil':cons':var':apply':lambda'3(+(x, 1)) ⇔ cons'(nil', _gen_nil':cons':var':apply':lambda'3(x))
No more defined symbols left to analyse.
The lowerbound Ω(n) was proven with the following lemma:
eq'(_gen_nil':cons':var':apply':lambda'3(_n5), _gen_nil':cons':var':apply':lambda'3(_n5)) → true', rt ∈ Ω(1 + n5)