YES

Problem 1: 

(VAR v_NonEmpty:S k:S m:S n:S psi:S s:S t:S u:S x:S xi:S y:S)
(RULES
Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
Concat(Id,s:S) -> s:S
Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
)

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(s:S,Concat(t:S,u:S))
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(t:S,u:S)
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 SUM_SUB(xi:S,Cons_sum(psi:S,k:S,s:S)) -> SUM_SUB(xi:S,s:S)
 SUM_SUB(xi:S,Cons_usual(y:S,m:S,s:S)) -> SUM_SUB(xi:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> SUM_SUB(xi:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> TERM_SUB(Term_var(x:S),s:S)
 TERM_SUB(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> TERM_SUB(Term_var(x:S),s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)

Problem 1: 

SCC Processor:
-> Pairs:
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(s:S,Concat(t:S,u:S))
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(t:S,u:S)
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 SUM_SUB(xi:S,Cons_sum(psi:S,k:S,s:S)) -> SUM_SUB(xi:S,s:S)
 SUM_SUB(xi:S,Cons_usual(y:S,m:S,s:S)) -> SUM_SUB(xi:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> SUM_SUB(xi:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> TERM_SUB(Term_var(x:S),s:S)
 TERM_SUB(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> TERM_SUB(Term_var(x:S),s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 TERM_SUB(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> TERM_SUB(Term_var(x:S),s:S)
 TERM_SUB(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> TERM_SUB(Term_var(x:S),s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->->Cycle:
->->-> Pairs:
 SUM_SUB(xi:S,Cons_sum(psi:S,k:S,s:S)) -> SUM_SUB(xi:S,s:S)
 SUM_SUB(xi:S,Cons_usual(y:S,m:S,s:S)) -> SUM_SUB(xi:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->->Cycle:
->->-> Pairs:
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(s:S,Concat(t:S,u:S))
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(t:S,u:S)
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)


The problem is decomposed in 3 subproblems.

Problem 1.1: 

Subterm Processor:
-> Pairs:
 TERM_SUB(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> TERM_SUB(Term_var(x:S),s:S)
 TERM_SUB(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> TERM_SUB(Term_var(x:S),s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Projection:
 pi(TERM_SUB) = 2

Problem 1.1: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Subterm Processor:
-> Pairs:
 SUM_SUB(xi:S,Cons_sum(psi:S,k:S,s:S)) -> SUM_SUB(xi:S,s:S)
 SUM_SUB(xi:S,Cons_usual(y:S,m:S,s:S)) -> SUM_SUB(xi:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Projection:
 pi(SUM_SUB) = 2

Problem 1.2: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.3: 

Reduction Pair Processor:
-> Pairs:
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(s:S,Concat(t:S,u:S))
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(t:S,u:S)
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
-> Usable rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->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
[Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1
[Case](X1,X2,X3) = 2.X1 + X3 + 2
[Cons_sum](X1,X2,X3) = 2.X1.X2.X3 + 2.X1.X2 + 2.X2.X3 + 2.X2 + 2.X3 + 2
[Cons_usual](X1,X2,X3) = X1.X2 + X1 + X2 + 2.X3 + 2
[Id] = 2
[Left] = 1
[Right] = 0
[Sum_constant](X) = 2
[Sum_term_var](X) = 2
[Term_app](X1,X2) = 2.X1 + X2 + 2
[Term_inl](X) = 2.X + 1
[Term_inr](X) = 2.X + 2
[Term_pair](X1,X2) = X1 + 2.X2 + 2
[Term_var](X) = 2.X.X + 2.X + 1
[CONCAT](X1,X2) = 2.X1.X2 + 2.X1 + X2
[FROZEN](X1,X2,X3,X4) = 2.X1.X2.X4 + X2.X3.X4 + 2.X1 + 2.X3 + 2.X4 + 2
[TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + X2

Problem 1.3: 

SCC Processor:
-> Pairs:
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(t:S,u:S)
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(t:S,u:S)
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)

Problem 1.3: 

Reduction Pair Processor:
-> Pairs:
 CONCAT(Concat(s:S,t:S),u:S) -> CONCAT(t:S,u:S)
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
-> Usable rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->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) = X2 + 2
[Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2
[Case](X1,X2,X3) = X1 + X3 + 2
[Cons_sum](X1,X2,X3) = X1.X3 + 2.X2.X3 + X1 + 2.X2 + 2.X3 + 2
[Cons_usual](X1,X2,X3) = 2.X1.X3 + 2.X1 + X2 + X3 + 2
[Id] = 2
[Left] = 2
[Right] = 1
[Sum_constant](X) = 2.X + 2
[Sum_term_var](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.X + 2
[CONCAT](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[FROZEN](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X2 + 2.X3 + 2.X4
[TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2

Problem 1.3: 

SCC Processor:
-> Pairs:
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)

Problem 1.3: 

Reduction Pair Processor:
-> Pairs:
 CONCAT(Cons_sum(xi:S,k:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
-> Usable rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->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 + 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.X3 + 2.X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X3 + 2
[Cons_usual](X1,X2,X3) = 2.X1.X2 + X1.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[Id] = 2
[Left] = 1
[Right] = 2
[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) = 2.X1 + X2 + 2
[Term_var](X) = 2.X.X + 2
[CONCAT](X1,X2) = X1.X2 + X1 + 2.X2 + 1
[FROZEN](X1,X2,X3,X4) = X1.X2.X4 + 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X2 + 2.X3 + 2.X4 + 2
[TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2

Problem 1.3: 

SCC Processor:
-> Pairs:
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)

Problem 1.3: 

Reduction Pair Processor:
-> Pairs:
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
-> Usable rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->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.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 + X3 + 2
[Cons_sum](X1,X2,X3) = 2.X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + 2.X3 + 1
[Cons_usual](X1,X2,X3) = X1.X2 + 2.X1.X3 + 2.X1 + X2 + 2.X3 + 2
[Id] = 2
[Left] = 0
[Right] = 2
[Sum_constant](X) = 0
[Sum_term_var](X) = 2.X
[Term_app](X1,X2) = 2.X1 + 2.X2 + 2
[Term_inl](X) = 2.X + 2
[Term_inr](X) = 2.X + 2
[Term_pair](X1,X2) = 2.X1 + 2.X2 + 2
[Term_var](X) = 2.X.X + 2.X + 2
[CONCAT](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2
[FROZEN](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X3 + 2.X4 + 2
[TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 2

Problem 1.3: 

SCC Processor:
-> Pairs:
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)

Problem 1.3: 

Reduction Pair Processor:
-> Pairs:
 CONCAT(Cons_usual(x:S,m:S,s:S),t:S) -> TERM_SUB(m:S,t:S)
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
-> Usable rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->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 + X2 + 2.X3 + 2.X4 + 2
[Sum_sub](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2
[Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + X2
[Case](X1,X2,X3) = X1 + 2.X2 + X3 + 2
[Cons_sum](X1,X2,X3) = 2.X1.X2.X3 + X1.X2 + X1.X3 + 2.X2.X3 + 2.X1 + X2 + 2.X3 + 2
[Cons_usual](X1,X2,X3) = 2.X1.X2 + 2.X1 + 2.X2 + 2.X3 + 2
[Id] = 2
[Left] = 0
[Right] = 0
[Sum_constant](X) = 2.X
[Sum_term_var](X) = 2.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) = 2.X.X + 2.X + 1
[CONCAT](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 1
[FROZEN](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + X2 + 2.X3 + 2.X4 + 1
[TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + X2 + 1

Problem 1.3: 

SCC Processor:
-> Pairs:
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> CONCAT(s:S,t:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)

Problem 1.3: 

Reduction Pair Processor:
-> Pairs:
 FROZEN(m:S,Sum_constant(Left),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
-> Usable rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->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.X2.X4 + 2.X3.X4 + 2.X1 + X2 + 2.X3 + 2.X4 + 2
[Sum_sub](X1,X2) = 2
[Term_sub](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1
[Case](X1,X2,X3) = X1 + X3 + 2
[Cons_sum](X1,X2,X3) = 2.X2.X3 + X1 + 2.X2 + 2.X3 + 2
[Cons_usual](X1,X2,X3) = 2.X1.X2 + 2.X1 + 2.X2 + X3 + 2
[Id] = 2
[Left] = 2
[Right] = 0
[Sum_constant](X) = 0
[Sum_term_var](X) = 2
[Term_app](X1,X2) = X1 + 2.X2 + 2
[Term_inl](X) = X + 2
[Term_inr](X) = 2.X + 2
[Term_pair](X1,X2) = X1 + 2.X2 + 2
[Term_var](X) = 2.X.X + 2.X + 2
[FROZEN](X1,X2,X3,X4) = 2.X1 + X2 + 2.X3 + 2
[TERM_SUB](X1,X2) = 2.X1 + 1

Problem 1.3: 

SCC Processor:
-> Pairs:
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)

Problem 1.3: 

Reduction Pair Processor:
-> Pairs:
 FROZEN(m:S,Sum_constant(Right),n:S,s:S) -> TERM_SUB(n:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
-> Usable rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->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.X2 + 2
[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) = X1.X3 + 2.X2.X3 + 2.X1 + 2.X2 + X3
[Cons_usual](X1,X2,X3) = X1.X2 + 2.X1.X3 + 2.X1 + X2 + 2.X3 + 2
[Id] = 2
[Left] = 2
[Right] = 0
[Sum_constant](X) = 2
[Sum_term_var](X) = 2.X + 2
[Term_app](X1,X2) = X1 + X2 + 2
[Term_inl](X) = X + 1
[Term_inr](X) = 2.X + 2
[Term_pair](X1,X2) = X1 + X2 + 2
[Term_var](X) = 2.X.X + 2
[FROZEN](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X3 + X4 + 2
[TERM_SUB](X1,X2) = 2.X1.X2 + 2.X1 + 1

Problem 1.3: 

SCC Processor:
-> Pairs:
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)

Problem 1.3: 

Reduction Pair Processor:
-> Pairs:
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(m:S,s:S)
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
-> Usable rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[Concat](X1,X2) = X1.X2 + X1 + X2
[Frozen](X1,X2,X3,X4) = 2.X1.X4 + 2.X3.X4 + 2.X1 + 2.X3 + 2.X4 + 2
[Sum_sub](X1,X2) = 2
[Term_sub](X1,X2) = X1.X2 + X1
[Case](X1,X2,X3) = 2.X1 + 2.X3 + 2
[Cons_sum](X1,X2,X3) = 2.X1.X2.X3 + 2.X1.X2 + X1.X3 + 2.X2.X3 + X1 + 2.X2 + 2.X3 + 2
[Cons_usual](X1,X2,X3) = 2.X1.X2 + X1.X3 + 2.X1 + 2.X2 + 2.X3 + 2
[Id] = 2
[Left] = 1
[Right] = 2
[Sum_constant](X) = 1
[Sum_term_var](X) = 0
[Term_app](X1,X2) = 2.X1 + 2.X2
[Term_inl](X) = X + 2
[Term_inr](X) = 2.X
[Term_pair](X1,X2) = 2.X1 + X2 + 1
[Term_var](X) = 2.X.X + 2.X + 2
[FROZEN](X1,X2,X3,X4) = X1.X2 + X2.X3 + 2.X1 + 2.X3 + 2
[TERM_SUB](X1,X2) = 2.X1 + 1

Problem 1.3: 

SCC Processor:
-> Pairs:
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
->->-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)

Problem 1.3: 

Subterm Processor:
-> Pairs:
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_sub(m:S,s:S),t:S) -> TERM_SUB(m:S,Concat(s:S,t:S))
 TERM_SUB(Case(m:S,xi:S,n:S),s:S) -> FROZEN(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_app(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
 TERM_SUB(Term_inl(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_inr(m:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(m:S,s:S)
 TERM_SUB(Term_pair(m:S,n:S),s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Projection:
 pi(FROZEN) = 3
 pi(TERM_SUB) = 1

Problem 1.3: 

SCC Processor:
-> Pairs:
 FROZEN(m:S,Sum_term_var(xi:S),n:S,s:S) -> TERM_SUB(n:S,s:S)
-> Rules:
 Concat(Concat(s:S,t:S),u:S) -> Concat(s:S,Concat(t:S,u:S))
 Concat(Cons_sum(xi:S,k:S,s:S),t:S) -> Cons_sum(xi:S,k:S,Concat(s:S,t:S))
 Concat(Cons_usual(x:S,m:S,s:S),t:S) -> Cons_usual(x:S,Term_sub(m:S,t:S),Concat(s:S,t:S))
 Concat(Id,s:S) -> s:S
 Frozen(m:S,Sum_constant(Left),n:S,s:S) -> Term_sub(m:S,s:S)
 Frozen(m:S,Sum_constant(Right),n:S,s:S) -> Term_sub(n:S,s:S)
 Frozen(m:S,Sum_term_var(xi:S),n:S,s:S) -> Case(Term_sub(m:S,s:S),xi:S,Term_sub(n:S,s:S))
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Cons_sum(psi:S,k:S,s:S)) -> Sum_constant(k:S)
 Sum_sub(xi:S,Cons_usual(y:S,m:S,s:S)) -> Sum_sub(xi:S,s:S)
 Sum_sub(xi:S,Id) -> Sum_term_var(xi:S)
 Term_sub(Term_sub(m:S,s:S),t:S) -> Term_sub(m:S,Concat(s:S,t:S))
 Term_sub(Case(m:S,xi:S,n:S),s:S) -> Frozen(m:S,Sum_sub(xi:S,s:S),n:S,s:S)
 Term_sub(Term_app(m:S,n:S),s:S) -> Term_app(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_inl(m:S),s:S) -> Term_inl(Term_sub(m:S,s:S))
 Term_sub(Term_inr(m:S),s:S) -> Term_inr(Term_sub(m:S,s:S))
 Term_sub(Term_pair(m:S,n:S),s:S) -> Term_pair(Term_sub(m:S,s:S),Term_sub(n:S,s:S))
 Term_sub(Term_var(x:S),Cons_sum(xi:S,k:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> Term_sub(Term_var(x:S),s:S)
 Term_sub(Term_var(x:S),Cons_usual(y:S,m:S,s:S)) -> m:S
 Term_sub(Term_var(x:S),Id) -> Term_var(x:S)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.