YES

Problem 1: 

(VAR v_NonEmpty:S x:S y:S z:S)
(RULES
*(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
*(*(x:S,i(y:S)),y:S) -> x:S
*(*(x:S,y:S),i(y:S)) -> x:S
*(i(x:S),x:S) -> 1
*(k(x:S,y:S),k(y:S,x:S)) -> 1
*(1,y:S) -> y:S
*(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
*(x:S,i(x:S)) -> 1
*(x:S,1) -> x:S
i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
i(i(x:S)) -> x:S
i(1) -> 1
k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
k(x:S,1) -> 1
k(x:S,x:S) -> 1
)

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),y:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),z:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> K(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
 I(*(x:S,y:S)) -> *#(i(y:S),i(x:S))
 I(*(x:S,y:S)) -> I(x:S)
 I(*(x:S,y:S)) -> I(y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1

Problem 1: 

SCC Processor:
-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),y:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),z:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> K(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
 I(*(x:S,y:S)) -> *#(i(y:S),i(x:S))
 I(*(x:S,y:S)) -> I(x:S)
 I(*(x:S,y:S)) -> I(y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),y:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),z:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
->->-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->->Cycle:
->->-> Pairs:
 I(*(x:S,y:S)) -> I(x:S)
 I(*(x:S,y:S)) -> I(y:S)
->->-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1


The problem is decomposed in 2 subproblems.

Problem 1.1: 

Reduction Pair Processor:
-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),y:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),z:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
-> Usable rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[*](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1
[i](X) = X
[k](X1,X2) = X1 + 2.X2 + 2
[1] = 1
[*#](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2

Problem 1.1: 

SCC Processor:
-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),z:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),z:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
->->-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1

Problem 1.1: 

Reduction Pair Processor:
-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(*(i(x:S),z:S),x:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
-> Usable rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[*](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1
[i](X) = X
[k](X1,X2) = 2.X1 + X2 + 2
[1] = 1
[*#](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2

Problem 1.1: 

SCC Processor:
-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
->->-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1

Problem 1.1: 

Reduction Pair Processor:
-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),y:S)
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
-> Usable rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Interpretation type:
 Simple mixed
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[*](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1
[i](X) = X
[k](X1,X2) = 2.X1 + X2 + 2
[1] = 1
[*#](X1,X2) = 2.X1.X2 + X1 + 2.X2

Problem 1.1: 

SCC Processor:
-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
->->-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1

Problem 1.1: 

Reduction Pair Processor:
-> Pairs:
 *#(*(i(x:S),k(y:S,z:S)),x:S) -> *#(i(x:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
-> Usable rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[*](X1,X2) = X1 + X2 + 2
[i](X) = 2.X + 2
[k](X1,X2) = X2 + 2
[1] = 0
[*#](X1,X2) = X1 + X2

Problem 1.1: 

SCC Processor:
-> Pairs:
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
->->-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1

Problem 1.1: 

Subterm Processor:
-> Pairs:
 *#(x:S,*(y:S,z:S)) -> *#(*(x:S,y:S),z:S)
 *#(x:S,*(y:S,z:S)) -> *#(x:S,y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Projection:
 pi(*#) = 2

Problem 1.1: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Subterm Processor:
-> Pairs:
 I(*(x:S,y:S)) -> I(x:S)
 I(*(x:S,y:S)) -> I(y:S)
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Projection:
 pi(I) = 1

Problem 1.2: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 *(*(i(x:S),k(y:S,z:S)),x:S) -> k(*(*(i(x:S),y:S),x:S),*(*(i(x:S),z:S),x:S))
 *(*(x:S,i(y:S)),y:S) -> x:S
 *(*(x:S,y:S),i(y:S)) -> x:S
 *(i(x:S),x:S) -> 1
 *(k(x:S,y:S),k(y:S,x:S)) -> 1
 *(1,y:S) -> y:S
 *(x:S,*(y:S,z:S)) -> *(*(x:S,y:S),z:S)
 *(x:S,i(x:S)) -> 1
 *(x:S,1) -> x:S
 i(*(x:S,y:S)) -> *(i(y:S),i(x:S))
 i(i(x:S)) -> x:S
 i(1) -> 1
 k(*(x:S,i(y:S)),*(y:S,i(x:S))) -> 1
 k(x:S,1) -> 1
 k(x:S,x:S) -> 1
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.