/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR k m n psi s t u x xi y) (RULES Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ) Problem 1: Dependency Pairs Processor: -> Pairs: CONCAT(Concat(s,t),u) -> CONCAT(s,Concat(t,u)) CONCAT(Concat(s,t),u) -> CONCAT(t,u) CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) SUM_SUB(xi,Cons_sum(psi,k,s)) -> SUM_SUB(xi,s) SUM_SUB(xi,Cons_usual(y,m,s)) -> SUM_SUB(xi,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Case(m,xi,n),s) -> SUM_SUB(xi,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_var(x),Cons_sum(xi,k,s)) -> TERM_SUB(Term_var(x),s) TERM_SUB(Term_var(x),Cons_usual(y,m,s)) -> TERM_SUB(Term_var(x),s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) Problem 1: SCC Processor: -> Pairs: CONCAT(Concat(s,t),u) -> CONCAT(s,Concat(t,u)) CONCAT(Concat(s,t),u) -> CONCAT(t,u) CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) SUM_SUB(xi,Cons_sum(psi,k,s)) -> SUM_SUB(xi,s) SUM_SUB(xi,Cons_usual(y,m,s)) -> SUM_SUB(xi,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Case(m,xi,n),s) -> SUM_SUB(xi,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_var(x),Cons_sum(xi,k,s)) -> TERM_SUB(Term_var(x),s) TERM_SUB(Term_var(x),Cons_usual(y,m,s)) -> TERM_SUB(Term_var(x),s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: TERM_SUB(Term_var(x),Cons_sum(xi,k,s)) -> TERM_SUB(Term_var(x),s) TERM_SUB(Term_var(x),Cons_usual(y,m,s)) -> TERM_SUB(Term_var(x),s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->->Cycle: ->->-> Pairs: SUM_SUB(xi,Cons_sum(psi,k,s)) -> SUM_SUB(xi,s) SUM_SUB(xi,Cons_usual(y,m,s)) -> SUM_SUB(xi,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->->Cycle: ->->-> Pairs: CONCAT(Concat(s,t),u) -> CONCAT(s,Concat(t,u)) CONCAT(Concat(s,t),u) -> CONCAT(t,u) CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) The problem is decomposed in 3 subproblems. Problem 1.1: Subterm Processor: -> Pairs: TERM_SUB(Term_var(x),Cons_sum(xi,k,s)) -> TERM_SUB(Term_var(x),s) TERM_SUB(Term_var(x),Cons_usual(y,m,s)) -> TERM_SUB(Term_var(x),s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Projection: pi(TERM_SUB) = 2 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: SUM_SUB(xi,Cons_sum(psi,k,s)) -> SUM_SUB(xi,s) SUM_SUB(xi,Cons_usual(y,m,s)) -> SUM_SUB(xi,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Projection: pi(SUM_SUB) = 2 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pair Processor: -> Pairs: CONCAT(Concat(s,t),u) -> CONCAT(s,Concat(t,u)) CONCAT(Concat(s,t),u) -> CONCAT(t,u) CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) -> Usable rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [Concat](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [Frozen](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + X2 + 2.X3 + 2.X4 + 2 [Sum_sub](X1,X2) = X1.X2 + 2.X2 + 2 [Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 1 [Case](X1,X2,X3) = X1 + 2.X2 + X3 + 2 [Cons_sum](X1,X2,X3) = 2.X1.X2.X3 + 2.X1.X2 + X1.X3 + 2.X2.X3 + X1 + 2.X2 + X3 [Cons_usual](X1,X2,X3) = 2.X1.X2 + 2.X1 + 2.X2 + X3 + 2 [Id] = 2 [Left] = 2 [Right] = 2 [Sum_constant](X) = X + 2 [Sum_term_var](X) = 2.X + 2 [Term_app](X1,X2) = 2.X1 + X2 + 2 [Term_inl](X) = 2.X + 2 [Term_inr](X) = 2.X + 1 [Term_pair](X1,X2) = X1 + 2.X2 + 2 [Term_var](X) = 2.X + 2 [CONCAT](X1,X2) = X1.X2 + X1 + 2 [FROZEN](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X3 + 2.X4 + 1 [TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 1 Problem 1.3: SCC Processor: -> Pairs: CONCAT(Concat(s,t),u) -> CONCAT(t,u) CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CONCAT(Concat(s,t),u) -> CONCAT(t,u) CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) Problem 1.3: Reduction Pair Processor: -> Pairs: CONCAT(Concat(s,t),u) -> CONCAT(t,u) CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) -> Usable rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [Concat](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [Frozen](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X2 + 2.X3 + 2.X4 + 2 [Sum_sub](X1,X2) = 2.X1.X2 + 2.X1 + X2 [Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2 [Case](X1,X2,X3) = X1 + 2.X2 + X3 + 2 [Cons_sum](X1,X2,X3) = 2.X1.X2 + X2.X3 + X2 + X3 + 2 [Cons_usual](X1,X2,X3) = X2 + X3 + 2 [Id] = 2 [Left] = 0 [Right] = 0 [Sum_constant](X) = 2 [Sum_term_var](X) = 2.X + 2 [Term_app](X1,X2) = X1 + X2 + 2 [Term_inl](X) = 2.X + 2 [Term_inr](X) = 2.X + 2 [Term_pair](X1,X2) = X1 + X2 + 2 [Term_var](X) = 2 [CONCAT](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [FROZEN](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + X2 + 2.X3 + X4 + 2 [TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + X2 Problem 1.3: SCC Processor: -> Pairs: CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) Problem 1.3: Reduction Pair Processor: -> Pairs: CONCAT(Cons_sum(xi,k,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) -> Usable rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [Concat](X1,X2) = 2.X1.X2 + 2.X1 + X2 [Frozen](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X2 + 2.X3 + 2.X4 + 2 [Sum_sub](X1,X2) = 2.X1 [Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + X2 [Case](X1,X2,X3) = X1 + 2.X2 + X3 + 2 [Cons_sum](X1,X2,X3) = X1.X2 + X1.X3 + 2.X1 + 2.X3 + 2 [Cons_usual](X1,X2,X3) = X1.X2 + 2.X1 + 2.X2 + 2.X3 + 2 [Id] = 0 [Left] = 2 [Right] = 2 [Sum_constant](X) = 0 [Sum_term_var](X) = 2.X [Term_app](X1,X2) = 2.X1 + X2 + 2 [Term_inl](X) = X [Term_inr](X) = 2.X + 1 [Term_pair](X1,X2) = 2.X1 + 2.X2 + 2 [Term_var](X) = 2.X.X + 2.X [CONCAT](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2 [FROZEN](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X2 + 2.X3 + X4 + 2 [TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2 Problem 1.3: SCC Processor: -> Pairs: CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) Problem 1.3: Reduction Pair Processor: -> Pairs: CONCAT(Cons_usual(x,m,s),t) -> CONCAT(s,t) CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) -> Usable rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [Concat](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [Frozen](X1,X2,X3,X4) = X1.X2.X4 + X1.X2 + 2.X1.X4 + 2.X2.X4 + 2.X3.X4 + 2.X1 + 2.X2 + 2.X3 + 2.X4 + 1 [Sum_sub](X1,X2) = 2.X1 + 2 [Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [Case](X1,X2,X3) = X1.X2 + 2.X1 + 2.X2 + X3 + 2 [Cons_sum](X1,X2,X3) = 2.X1.X2 + 2.X2.X3 + 2.X2 + X3 + 2 [Cons_usual](X1,X2,X3) = 2.X1.X2 + 2.X1 + 2.X2 + X3 + 2 [Id] = 2 [Left] = 0 [Right] = 0 [Sum_constant](X) = 2 [Sum_term_var](X) = 2.X + 2 [Term_app](X1,X2) = X1 + 2.X2 + 2 [Term_inl](X) = 2.X + 1 [Term_inr](X) = X + 2 [Term_pair](X1,X2) = 2.X1 + X2 + 2 [Term_var](X) = 2.X.X + 2.X + 2 [CONCAT](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2 [FROZEN](X1,X2,X3,X4) = X1.X2.X4 + 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X2 + 2.X3 + 2.X4 [TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 Problem 1.3: SCC Processor: -> Pairs: CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) Problem 1.3: Reduction Pair Processor: -> Pairs: CONCAT(Cons_usual(x,m,s),t) -> TERM_SUB(m,t) FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) -> Usable rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [Concat](X1,X2) = 2.X1.X2 + 2.X1 [Frozen](X1,X2,X3,X4) = X1.X2.X4 + X2.X3.X4 + X1.X2 + 2.X1.X4 + 2.X2.X3 + 2.X2.X4 + 2.X3.X4 + 2.X1 + X4 + 2 [Sum_sub](X1,X2) = 2 [Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + X2 [Case](X1,X2,X3) = 2.X1 + 2.X3 + 2 [Cons_sum](X1,X2,X3) = 2.X1.X2 + 2.X1.X3 + 2.X2.X3 + X1 + 2.X2 + 2.X3 [Cons_usual](X1,X2,X3) = 2.X1.X2 + 2.X1.X3 + 2.X1 + 2.X2 + 2.X3 + 1 [Id] = 1 [Left] = 0 [Right] = 2 [Sum_constant](X) = 2 [Sum_term_var](X) = 2 [Term_app](X1,X2) = 2.X1 + 2.X2 + 2 [Term_inl](X) = X [Term_inr](X) = 2.X + 1 [Term_pair](X1,X2) = 2.X1 + 2.X2 + 2 [Term_var](X) = 2.X.X + 2.X + 1 [CONCAT](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2 [FROZEN](X1,X2,X3,X4) = X1.X2.X4 + X1.X4 + X2.X4 + 2.X3.X4 + 2.X1 + 2.X2 + 2.X3 + 2.X4 + 2 [TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2 Problem 1.3: SCC Processor: -> Pairs: FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> CONCAT(s,t) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) Problem 1.3: Reduction Pair Processor: -> Pairs: FROZEN(m,Sum_constant(Left),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) -> Usable rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [Concat](X1,X2) = 2.X1.X2 + 2.X1 [Frozen](X1,X2,X3,X4) = X1.X2.X4 + 2.X2.X3.X4 + X2.X3 + 2.X2.X4 + 2.X1 + 2.X3 + 2.X4 + 2 [Sum_sub](X1,X2) = 2 [Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 [Case](X1,X2,X3) = X1 + 2.X3 + 2 [Cons_sum](X1,X2,X3) = 2.X1.X2.X3 + 2.X1.X2 + 2.X1.X3 + X1 + 2.X2 + 2.X3 + 2 [Cons_usual](X1,X2,X3) = 2.X1.X2 + 2.X1 + 2.X2 + 2.X3 + 2 [Id] = 2 [Left] = 2 [Right] = 0 [Sum_constant](X) = 2 [Sum_term_var](X) = 2 [Term_app](X1,X2) = X1 + 2.X2 + 2 [Term_inl](X) = 2.X + 2 [Term_inr](X) = 2.X + 2 [Term_pair](X1,X2) = X1 + 2.X2 + 2 [Term_var](X) = X.X + 2.X + 2 [FROZEN](X1,X2,X3,X4) = X1.X2.X4 + 2.X2.X3.X4 + 2.X2.X3 + X2.X4 + 2.X1 + 2.X4 + 2 [TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 Problem 1.3: SCC Processor: -> Pairs: FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) Problem 1.3: Reduction Pair Processor: -> Pairs: FROZEN(m,Sum_constant(Right),n,s) -> TERM_SUB(n,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) -> Usable rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [Concat](X1,X2) = 2.X1.X2 + 2.X1 [Frozen](X1,X2,X3,X4) = X2.X3.X4 + 2.X1.X4 + 2.X2.X3 + 2.X2.X4 + 2.X3.X4 + 2.X1 + 2.X2 + 2.X4 + 1 [Sum_sub](X1,X2) = 2 [Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 [Case](X1,X2,X3) = X1 + 2.X3 + 2 [Cons_sum](X1,X2,X3) = X1.X2.X3 + 2.X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X3 + 1 [Cons_usual](X1,X2,X3) = X2 + 2.X3 + 2 [Id] = 2 [Left] = 0 [Right] = 0 [Sum_constant](X) = 2 [Sum_term_var](X) = 2 [Term_app](X1,X2) = 2.X1 + X2 + 2 [Term_inl](X) = 2.X + 2 [Term_inr](X) = 2.X + 2 [Term_pair](X1,X2) = X1 + 2.X2 + 2 [Term_var](X) = 2.X.X + X + 2 [FROZEN](X1,X2,X3,X4) = X2.X3.X4 + X1.X4 + X1 + 2.X3 + 2.X4 + 2 [TERM_SUB](X1,X2) = X1.X2 + X1 + X2 + 1 Problem 1.3: SCC Processor: -> Pairs: FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) Problem 1.3: Reduction Pair Processor: -> Pairs: FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(m,s) FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) -> Usable rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [Concat](X1,X2) = 2.X1.X2 [Frozen](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X2 + X4 [Sum_sub](X1,X2) = X1.X2 + X2 [Term_sub](X1,X2) = 2.X1.X2 [Case](X1,X2,X3) = X1 + X2 + X3 + 2 [Cons_sum](X1,X2,X3) = 2.X1.X2.X3 + 2.X1.X3 + X2.X3 + 2.X3 [Cons_usual](X1,X2,X3) = 2.X1.X2 + 2.X2 + 2.X3 [Id] = 2 [Left] = 2 [Right] = 0 [Sum_constant](X) = 0 [Sum_term_var](X) = X + 2 [Term_app](X1,X2) = 2.X1 + 2.X2 [Term_inl](X) = 2.X [Term_inr](X) = 2.X [Term_pair](X1,X2) = 2.X1 + 2.X2 [Term_var](X) = 2.X.X + 2 [FROZEN](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X2 + 2.X4 + 2 [TERM_SUB](X1,X2) = 2.X1.X2 + 2 Problem 1.3: SCC Processor: -> Pairs: FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) ->->-> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) Problem 1.3: Subterm Processor: -> Pairs: FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) TERM_SUB(Term_sub(m,s),t) -> TERM_SUB(m,Concat(s,t)) TERM_SUB(Case(m,xi,n),s) -> FROZEN(m,Sum_sub(xi,s),n,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_app(m,n),s) -> TERM_SUB(n,s) TERM_SUB(Term_inl(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_inr(m),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(m,s) TERM_SUB(Term_pair(m,n),s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Projection: pi(FROZEN) = 3 pi(TERM_SUB) = 1 Problem 1.3: SCC Processor: -> Pairs: FROZEN(m,Sum_term_var(xi),n,s) -> TERM_SUB(n,s) -> Rules: Concat(Concat(s,t),u) -> Concat(s,Concat(t,u)) Concat(Cons_sum(xi,k,s),t) -> Cons_sum(xi,k,Concat(s,t)) Concat(Cons_usual(x,m,s),t) -> Cons_usual(x,Term_sub(m,t),Concat(s,t)) Concat(Id,s) -> s Frozen(m,Sum_constant(Left),n,s) -> Term_sub(m,s) Frozen(m,Sum_constant(Right),n,s) -> Term_sub(n,s) Frozen(m,Sum_term_var(xi),n,s) -> Case(Term_sub(m,s),xi,Term_sub(n,s)) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_sub(xi,s) Sum_sub(xi,Cons_sum(psi,k,s)) -> Sum_constant(k) Sum_sub(xi,Cons_usual(y,m,s)) -> Sum_sub(xi,s) Sum_sub(xi,Id) -> Sum_term_var(xi) Term_sub(Term_sub(m,s),t) -> Term_sub(m,Concat(s,t)) Term_sub(Case(m,xi,n),s) -> Frozen(m,Sum_sub(xi,s),n,s) Term_sub(Term_app(m,n),s) -> Term_app(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_inl(m),s) -> Term_inl(Term_sub(m,s)) Term_sub(Term_inr(m),s) -> Term_inr(Term_sub(m,s)) Term_sub(Term_pair(m,n),s) -> Term_pair(Term_sub(m,s),Term_sub(n,s)) Term_sub(Term_var(x),Cons_sum(xi,k,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> Term_sub(Term_var(x),s) Term_sub(Term_var(x),Cons_usual(y,m,s)) -> m Term_sub(Term_var(x),Id) -> Term_var(x) ->Strongly Connected Components: There is no strongly connected component The problem is finite.