YES

Problem 1: 

(VAR v_NonEmpty:S X:S X1:S X2:S)
(RULES
a__a -> a
a__a -> b
a__f(X:S,X:S) -> a__h(a__a)
a__f(X1:S,X2:S) -> f(X1:S,X2:S)
a__g(a,X:S) -> a__f(b,X:S)
a__g(X1:S,X2:S) -> g(X1:S,X2:S)
a__h(X:S) -> a__g(mark(X:S),X:S)
a__h(X:S) -> h(X:S)
mark(a) -> a__a
mark(b) -> b
mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
mark(h(X:S)) -> a__h(mark(X:S))
) 
(STRATEGY INNERMOST)

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__A
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(X:S) -> A__G(mark(X:S),X:S)
 A__H(X:S) -> MARK(X:S)
 MARK(a) -> A__A
 MARK(f(X1:S,X2:S)) -> A__F(mark(X1:S),X2:S)
 MARK(f(X1:S,X2:S)) -> MARK(X1:S)
 MARK(g(X1:S,X2:S)) -> A__G(mark(X1:S),X2:S)
 MARK(g(X1:S,X2:S)) -> MARK(X1:S)
 MARK(h(X:S)) -> A__H(mark(X:S))
 MARK(h(X:S)) -> MARK(X:S)
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))

Problem 1: 

SCC Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__A
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(X:S) -> A__G(mark(X:S),X:S)
 A__H(X:S) -> MARK(X:S)
 MARK(a) -> A__A
 MARK(f(X1:S,X2:S)) -> A__F(mark(X1:S),X2:S)
 MARK(f(X1:S,X2:S)) -> MARK(X1:S)
 MARK(g(X1:S,X2:S)) -> A__G(mark(X1:S),X2:S)
 MARK(g(X1:S,X2:S)) -> MARK(X1:S)
 MARK(h(X:S)) -> A__H(mark(X:S))
 MARK(h(X:S)) -> MARK(X:S)
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(X:S) -> A__G(mark(X:S),X:S)
 A__H(X:S) -> MARK(X:S)
 MARK(f(X1:S,X2:S)) -> A__F(mark(X1:S),X2:S)
 MARK(f(X1:S,X2:S)) -> MARK(X1:S)
 MARK(g(X1:S,X2:S)) -> A__G(mark(X1:S),X2:S)
 MARK(g(X1:S,X2:S)) -> MARK(X1:S)
 MARK(h(X:S)) -> A__H(mark(X:S))
 MARK(h(X:S)) -> MARK(X:S)
->->-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))

Problem 1: 

Reduction Pairs Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(X:S) -> A__G(mark(X:S),X:S)
 A__H(X:S) -> MARK(X:S)
 MARK(f(X1:S,X2:S)) -> A__F(mark(X1:S),X2:S)
 MARK(f(X1:S,X2:S)) -> MARK(X1:S)
 MARK(g(X1:S,X2:S)) -> A__G(mark(X1:S),X2:S)
 MARK(g(X1:S,X2:S)) -> MARK(X1:S)
 MARK(h(X:S)) -> A__H(mark(X:S))
 MARK(h(X:S)) -> MARK(X:S)
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
-> Usable rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__a] = 0
[a__f](X1,X2) = 2.X1 + 2
[a__g](X1,X2) = X1 + 2
[a__h](X) = 2.X + 2
[mark](X) = 2.X
[a] = 0
[b] = 0
[f](X1,X2) = 2.X1 + 2
[fSNonEmpty] = 0
[g](X1,X2) = X1 + 1
[h](X) = 2.X + 2
[A__A] = 0
[A__F](X1,X2) = 1
[A__G](X1,X2) = 1
[A__H](X) = 2.X + 1
[MARK](X) = 2.X

Problem 1: 

SCC Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(X:S) -> A__G(mark(X:S),X:S)
 MARK(f(X1:S,X2:S)) -> A__F(mark(X1:S),X2:S)
 MARK(f(X1:S,X2:S)) -> MARK(X1:S)
 MARK(g(X1:S,X2:S)) -> A__G(mark(X1:S),X2:S)
 MARK(g(X1:S,X2:S)) -> MARK(X1:S)
 MARK(h(X:S)) -> A__H(mark(X:S))
 MARK(h(X:S)) -> MARK(X:S)
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(X:S) -> A__G(mark(X:S),X:S)
->->-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->->Cycle:
->->-> Pairs:
 MARK(f(X1:S,X2:S)) -> MARK(X1:S)
 MARK(g(X1:S,X2:S)) -> MARK(X1:S)
 MARK(h(X:S)) -> MARK(X:S)
->->-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))


The problem is decomposed in 2 subproblems.

Problem 1.1: 

Narrowing Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(X:S) -> A__G(mark(X:S),X:S)
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Narrowed Pairs:
->->Original Pair:
 A__H(X:S) -> A__G(mark(X:S),X:S)
->-> Narrowed pairs:
 A__H(a) -> A__G(a__a,a)
 A__H(b) -> A__G(b,b)
 A__H(f(X1:S,X2:S)) -> A__G(a__f(mark(X1:S),X2:S),f(X1:S,X2:S))
 A__H(g(X1:S,X2:S)) -> A__G(a__g(mark(X1:S),X2:S),g(X1:S,X2:S))
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))

Problem 1.1: 

SCC Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
 A__H(b) -> A__G(b,b)
 A__H(f(X1:S,X2:S)) -> A__G(a__f(mark(X1:S),X2:S),f(X1:S,X2:S))
 A__H(g(X1:S,X2:S)) -> A__G(a__g(mark(X1:S),X2:S),g(X1:S,X2:S))
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
 A__H(f(X1:S,X2:S)) -> A__G(a__f(mark(X1:S),X2:S),f(X1:S,X2:S))
 A__H(g(X1:S,X2:S)) -> A__G(a__g(mark(X1:S),X2:S),g(X1:S,X2:S))
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))
->->-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))

Problem 1.1: 

Reduction Pairs Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
 A__H(f(X1:S,X2:S)) -> A__G(a__f(mark(X1:S),X2:S),f(X1:S,X2:S))
 A__H(g(X1:S,X2:S)) -> A__G(a__g(mark(X1:S),X2:S),g(X1:S,X2:S))
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
-> Usable rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__a] = 1
[a__f](X1,X2) = 2.X1 + 2
[a__g](X1,X2) = 2
[a__h](X) = 2
[mark](X) = 2.X + 2
[a] = 1
[b] = 0
[f](X1,X2) = 2.X1 + 2
[fSNonEmpty] = 0
[g](X1,X2) = 2
[h](X) = 2
[A__A] = 0
[A__F](X1,X2) = 2.X1 + 2
[A__G](X1,X2) = 2
[A__H](X) = 2.X
[MARK](X) = 0

Problem 1.1: 

SCC Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
 A__H(g(X1:S,X2:S)) -> A__G(a__g(mark(X1:S),X2:S),g(X1:S,X2:S))
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
 A__H(g(X1:S,X2:S)) -> A__G(a__g(mark(X1:S),X2:S),g(X1:S,X2:S))
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))
->->-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))

Problem 1.1: 

Reduction Pairs Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
 A__H(g(X1:S,X2:S)) -> A__G(a__g(mark(X1:S),X2:S),g(X1:S,X2:S))
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
-> Usable rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__a] = 2
[a__f](X1,X2) = X1 + 1
[a__g](X1,X2) = 1
[a__h](X) = 1
[mark](X) = 2.X + 2
[a] = 2
[b] = 0
[f](X1,X2) = X1 + 1
[fSNonEmpty] = 0
[g](X1,X2) = 0
[h](X) = 1
[A__A] = 0
[A__F](X1,X2) = 2
[A__G](X1,X2) = X1
[A__H](X) = 2
[MARK](X) = 0

Problem 1.1: 

SCC Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))
->->-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))

Problem 1.1: 

Reduction Pairs Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
 A__H(h(X:S)) -> A__G(a__h(mark(X:S)),h(X:S))
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
-> Usable rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Interpretation type:
 Linear
->Coefficients:
 Natural Numbers
->Dimension:
 1
->Bound:
 2
->Interpretation:
 
[a__a] = 0
[a__f](X1,X2) = 2
[a__g](X1,X2) = 2
[a__h](X) = 2.X + 2
[mark](X) = 2.X + 2
[a] = 0
[b] = 0
[f](X1,X2) = 1
[fSNonEmpty] = 0
[g](X1,X2) = 1
[h](X) = 2.X + 2
[A__A] = 0
[A__F](X1,X2) = X2 + 2
[A__G](X1,X2) = X2 + 2
[A__H](X) = 2.X + 2
[MARK](X) = 0

Problem 1.1: 

SCC Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Strongly Connected Components:
->->Cycle:
->->-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
->->-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))

Problem 1.1: 

Reduction Pair Processor:
-> Pairs:
 A__F(X:S,X:S) -> A__H(a__a)
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
-> Usable rules:
 a__a -> a
 a__a -> b
->Mace4 Output:
 ============================== Mace4 =================================
Mace4 (64) version 2009-11A, November 2009.
Process 26059 was started by sandbox2 on n141.star.cs.uiowa.edu,
Mon Jun 22 00:36:13 2020
The command was "./mace4 -c -f /tmp/mace41562402336298625210.in".
============================== end of head ===========================

============================== INPUT =================================

% Reading from file /tmp/mace41562402336298625210.in

assign(max_seconds,20).

formulas(assumptions).
gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility).
succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility).
gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility).
arrow_s0(x1,y) -> arrow_s0(f3(x1,x2),f3(y,x2)) # label(congruence).
arrow_s0(x2,y) -> arrow_s0(f3(x1,x2),f3(x1,y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f4(x1,x2),f4(y,x2)) # label(congruence).
arrow_s0(x2,y) -> arrow_s0(f4(x1,x2),f4(x1,y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f5(x1),f5(y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f6(x1),f6(y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f9(x1,x2),f9(y,x2)) # label(congruence).
arrow_s0(x2,y) -> arrow_s0(f9(x1,x2),f9(x1,y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f11(x1,x2),f11(y,x2)) # label(congruence).
arrow_s0(x2,y) -> arrow_s0(f11(x1,x2),f11(x1,y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f12(x1),f12(y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f15(x1,x2),f15(y,x2)) # label(congruence).
arrow_s0(x2,y) -> arrow_s0(f15(x1,x2),f15(x1,y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f16(x1,x2),f16(y,x2)) # label(congruence).
arrow_s0(x2,y) -> arrow_s0(f16(x1,x2),f16(x1,y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f17(x1),f17(y)) # label(congruence).
arrow_s0(x1,y) -> arrow_s0(f18(x1),f18(y)) # label(congruence).
arrow_s0(f2,f7) # label(replacement).
arrow_s0(f2,f8) # label(replacement).
arrow_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion).
sqsupset_s0(f15(x1,x1),f17(f2)) # label(replacement).
succeq_s0(f16(f7,x1),f15(f8,x1)) # label(replacement).
succeq_s0(f17(f7),f16(f2,f7)) # label(replacement).
sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion).
sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility).
end_of_list.

formulas(goals).
(exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness).
end_of_list.

============================== end of input ==========================

============================== PROCESS NON-CLAUSAL FORMULAS ==========

% Formulas that are not ordinary clauses:
1 gtrsim_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause).  [assumption].
2 succeq_s0(x,y) & sqsupset_s0(y,z) -> sqsupset_s0(x,z) # label(compatibility) # label(non_clause).  [assumption].
3 gtrsim_s0(x,y) & succeq_s0(y,z) -> gtrsim_s0(x,z) # label(compatibility) # label(non_clause).  [assumption].
4 arrow_s0(x1,y) -> arrow_s0(f3(x1,x2),f3(y,x2)) # label(congruence) # label(non_clause).  [assumption].
5 arrow_s0(x2,y) -> arrow_s0(f3(x1,x2),f3(x1,y)) # label(congruence) # label(non_clause).  [assumption].
6 arrow_s0(x1,y) -> arrow_s0(f4(x1,x2),f4(y,x2)) # label(congruence) # label(non_clause).  [assumption].
7 arrow_s0(x2,y) -> arrow_s0(f4(x1,x2),f4(x1,y)) # label(congruence) # label(non_clause).  [assumption].
8 arrow_s0(x1,y) -> arrow_s0(f5(x1),f5(y)) # label(congruence) # label(non_clause).  [assumption].
9 arrow_s0(x1,y) -> arrow_s0(f6(x1),f6(y)) # label(congruence) # label(non_clause).  [assumption].
10 arrow_s0(x1,y) -> arrow_s0(f9(x1,x2),f9(y,x2)) # label(congruence) # label(non_clause).  [assumption].
11 arrow_s0(x2,y) -> arrow_s0(f9(x1,x2),f9(x1,y)) # label(congruence) # label(non_clause).  [assumption].
12 arrow_s0(x1,y) -> arrow_s0(f11(x1,x2),f11(y,x2)) # label(congruence) # label(non_clause).  [assumption].
13 arrow_s0(x2,y) -> arrow_s0(f11(x1,x2),f11(x1,y)) # label(congruence) # label(non_clause).  [assumption].
14 arrow_s0(x1,y) -> arrow_s0(f12(x1),f12(y)) # label(congruence) # label(non_clause).  [assumption].
15 arrow_s0(x1,y) -> arrow_s0(f15(x1,x2),f15(y,x2)) # label(congruence) # label(non_clause).  [assumption].
16 arrow_s0(x2,y) -> arrow_s0(f15(x1,x2),f15(x1,y)) # label(congruence) # label(non_clause).  [assumption].
17 arrow_s0(x1,y) -> arrow_s0(f16(x1,x2),f16(y,x2)) # label(congruence) # label(non_clause).  [assumption].
18 arrow_s0(x2,y) -> arrow_s0(f16(x1,x2),f16(x1,y)) # label(congruence) # label(non_clause).  [assumption].
19 arrow_s0(x1,y) -> arrow_s0(f17(x1),f17(y)) # label(congruence) # label(non_clause).  [assumption].
20 arrow_s0(x1,y) -> arrow_s0(f18(x1),f18(y)) # label(congruence) # label(non_clause).  [assumption].
21 arrow_s0(x,y) -> gtrsim_s0(x,y) # label(inclusion) # label(non_clause).  [assumption].
22 sqsupset_s0(x,y) -> sqsupsetStar_s0(x,y) # label(inclusion) # label(non_clause).  [assumption].
23 sqsupset_s0(x,y) & sqsupsetStar_s0(y,z) -> sqsupsetStar_s0(x,z) # label(compatibility) # label(non_clause).  [assumption].
24 (exists x sqsupsetStar_s0(x,x)) # label(wellfoundedness) # label(non_clause) # label(goal).  [goal].

============================== end of process non-clausal formulas ===

============================== CLAUSES FOR SEARCH ====================

formulas(mace4_clauses).
-gtrsim_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility).
-succeq_s0(x,y) | -sqsupset_s0(y,z) | sqsupset_s0(x,z) # label(compatibility).
-gtrsim_s0(x,y) | -succeq_s0(y,z) | gtrsim_s0(x,z) # label(compatibility).
-arrow_s0(x,y) | arrow_s0(f3(x,z),f3(y,z)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f3(z,x),f3(z,y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f4(x,z),f4(y,z)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f4(z,x),f4(z,y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f5(x),f5(y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f6(x),f6(y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f9(x,z),f9(y,z)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f9(z,x),f9(z,y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f11(x,z),f11(y,z)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f11(z,x),f11(z,y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f12(x),f12(y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f15(x,z),f15(y,z)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f15(z,x),f15(z,y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f16(x,z),f16(y,z)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f16(z,x),f16(z,y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f17(x),f17(y)) # label(congruence).
-arrow_s0(x,y) | arrow_s0(f18(x),f18(y)) # label(congruence).
arrow_s0(f2,f7) # label(replacement).
arrow_s0(f2,f8) # label(replacement).
-arrow_s0(x,y) | gtrsim_s0(x,y) # label(inclusion).
sqsupset_s0(f15(x,x),f17(f2)) # label(replacement).
succeq_s0(f16(f7,x),f15(f8,x)) # label(replacement).
succeq_s0(f17(f7),f16(f2,f7)) # label(replacement).
-sqsupset_s0(x,y) | sqsupsetStar_s0(x,y) # label(inclusion).
-sqsupset_s0(x,y) | -sqsupsetStar_s0(y,z) | sqsupsetStar_s0(x,z) # label(compatibility).
-sqsupsetStar_s0(x,x) # label(wellfoundedness).
end_of_list.

============================== end of clauses for search =============

% There are no natural numbers in the input.

============================== DOMAIN SIZE 2 =========================

============================== STATISTICS ============================

For domain size 2.

Current CPU time: 0.00 seconds (total CPU time: 0.00 seconds).
Ground clauses: seen=165, kept=165.
Selections=16, assignments=31, propagations=161, current_models=0.
Rewrite_terms=441, rewrite_bools=1073, indexes=66.
Rules_from_neg_clauses=57, cross_offs=57.

============================== end of statistics =====================

============================== DOMAIN SIZE 3 =========================

============================== MODEL =================================

interpretation( 3, [number=1, seconds=0], [

        function(f2, [ 0 ]),

        function(f7, [ 1 ]),

        function(f8, [ 2 ]),

        function(f12(_), [ 0, 0, 0 ]),

        function(f17(_), [ 1, 1, 1 ]),

        function(f18(_), [ 0, 0, 0 ]),

        function(f5(_), [ 0, 0, 0 ]),

        function(f6(_), [ 0, 0, 0 ]),

        function(f11(_,_), [
			   0, 0, 0,
			   0, 0, 0,
			   0, 0, 0 ]),

        function(f15(_,_), [
			   0, 0, 0,
			   0, 0, 0,
			   0, 1, 0 ]),

        function(f16(_,_), [
			   0, 1, 0,
			   0, 1, 0,
			   0, 1, 0 ]),

        function(f3(_,_), [
			   0, 0, 0,
			   0, 0, 0,
			   0, 0, 0 ]),

        function(f4(_,_), [
			   0, 0, 0,
			   0, 0, 0,
			   0, 0, 0 ]),

        function(f9(_,_), [
			   0, 0, 0,
			   0, 0, 0,
			   0, 0, 0 ]),

        relation(arrow_s0(_,_), [
			   1, 1, 1,
			   0, 1, 0,
			   0, 0, 0 ]),

        relation(gtrsim_s0(_,_), [
			   1, 1, 1,
			   0, 1, 0,
			   0, 0, 0 ]),

        relation(sqsupsetStar_s0(_,_), [
			   0, 1, 0,
			   0, 0, 0,
			   0, 0, 0 ]),

        relation(sqsupset_s0(_,_), [
			   0, 1, 0,
			   0, 0, 0,
			   0, 0, 0 ]),

        relation(succeq_s0(_,_), [
			   1, 0, 0,
			   0, 1, 0,
			   0, 0, 0 ])
]).

============================== end of model ==========================

============================== STATISTICS ============================

For domain size 3.

Current CPU time: 0.00 seconds (total CPU time: 0.01 seconds).
Ground clauses: seen=507, kept=507.
Selections=246, assignments=581, propagations=2751, current_models=1.
Rewrite_terms=11510, rewrite_bools=28632, indexes=1025.
Rules_from_neg_clauses=669, cross_offs=1628.

============================== end of statistics =====================

User_CPU=0.01, System_CPU=0.00, Wall_clock=0.

Exiting with 1 model.

Process 26059 exit (max_models) Mon Jun 22 00:36:13 2020
The process finished Mon Jun 22 00:36:13 2020


Mace4 cooked interpretation:

% number = 1
% seconds = 0

% Interpretation of size 3

f2 = 0.

f7 = 1.

f8 = 2.

f12(0) = 0.
f12(1) = 0.
f12(2) = 0.

f17(0) = 1.
f17(1) = 1.
f17(2) = 1.

f18(0) = 0.
f18(1) = 0.
f18(2) = 0.

f5(0) = 0.
f5(1) = 0.
f5(2) = 0.

f6(0) = 0.
f6(1) = 0.
f6(2) = 0.

f11(0,0) = 0.
f11(0,1) = 0.
f11(0,2) = 0.
f11(1,0) = 0.
f11(1,1) = 0.
f11(1,2) = 0.
f11(2,0) = 0.
f11(2,1) = 0.
f11(2,2) = 0.

f15(0,0) = 0.
f15(0,1) = 0.
f15(0,2) = 0.
f15(1,0) = 0.
f15(1,1) = 0.
f15(1,2) = 0.
f15(2,0) = 0.
f15(2,1) = 1.
f15(2,2) = 0.

f16(0,0) = 0.
f16(0,1) = 1.
f16(0,2) = 0.
f16(1,0) = 0.
f16(1,1) = 1.
f16(1,2) = 0.
f16(2,0) = 0.
f16(2,1) = 1.
f16(2,2) = 0.

f3(0,0) = 0.
f3(0,1) = 0.
f3(0,2) = 0.
f3(1,0) = 0.
f3(1,1) = 0.
f3(1,2) = 0.
f3(2,0) = 0.
f3(2,1) = 0.
f3(2,2) = 0.

f4(0,0) = 0.
f4(0,1) = 0.
f4(0,2) = 0.
f4(1,0) = 0.
f4(1,1) = 0.
f4(1,2) = 0.
f4(2,0) = 0.
f4(2,1) = 0.
f4(2,2) = 0.

f9(0,0) = 0.
f9(0,1) = 0.
f9(0,2) = 0.
f9(1,0) = 0.
f9(1,1) = 0.
f9(1,2) = 0.
f9(2,0) = 0.
f9(2,1) = 0.
f9(2,2) = 0.

  arrow_s0(0,0).
  arrow_s0(0,1).
  arrow_s0(0,2).
- arrow_s0(1,0).
  arrow_s0(1,1).
- arrow_s0(1,2).
- arrow_s0(2,0).
- arrow_s0(2,1).
- arrow_s0(2,2).

  gtrsim_s0(0,0).
  gtrsim_s0(0,1).
  gtrsim_s0(0,2).
- gtrsim_s0(1,0).
  gtrsim_s0(1,1).
- gtrsim_s0(1,2).
- gtrsim_s0(2,0).
- gtrsim_s0(2,1).
- gtrsim_s0(2,2).

- sqsupsetStar_s0(0,0).
  sqsupsetStar_s0(0,1).
- sqsupsetStar_s0(0,2).
- sqsupsetStar_s0(1,0).
- sqsupsetStar_s0(1,1).
- sqsupsetStar_s0(1,2).
- sqsupsetStar_s0(2,0).
- sqsupsetStar_s0(2,1).
- sqsupsetStar_s0(2,2).

- sqsupset_s0(0,0).
  sqsupset_s0(0,1).
- sqsupset_s0(0,2).
- sqsupset_s0(1,0).
- sqsupset_s0(1,1).
- sqsupset_s0(1,2).
- sqsupset_s0(2,0).
- sqsupset_s0(2,1).
- sqsupset_s0(2,2).

  succeq_s0(0,0).
- succeq_s0(0,1).
- succeq_s0(0,2).
- succeq_s0(1,0).
  succeq_s0(1,1).
- succeq_s0(1,2).
- succeq_s0(2,0).
- succeq_s0(2,1).
- succeq_s0(2,2).


Problem 1.1: 

SCC Processor:
-> Pairs:
 A__G(a,X:S) -> A__F(b,X:S)
 A__H(a) -> A__G(a__a,a)
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.

Problem 1.2: 

Subterm Processor:
-> Pairs:
 MARK(f(X1:S,X2:S)) -> MARK(X1:S)
 MARK(g(X1:S,X2:S)) -> MARK(X1:S)
 MARK(h(X:S)) -> MARK(X:S)
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Projection:
 pi(MARK) = 1

Problem 1.2: 

SCC Processor:
-> Pairs:
 Empty
-> Rules:
 a__a -> a
 a__a -> b
 a__f(X:S,X:S) -> a__h(a__a)
 a__f(X1:S,X2:S) -> f(X1:S,X2:S)
 a__g(a,X:S) -> a__f(b,X:S)
 a__g(X1:S,X2:S) -> g(X1:S,X2:S)
 a__h(X:S) -> a__g(mark(X:S),X:S)
 a__h(X:S) -> h(X:S)
 mark(a) -> a__a
 mark(b) -> b
 mark(f(X1:S,X2:S)) -> a__f(mark(X1:S),X2:S)
 mark(g(X1:S,X2:S)) -> a__g(mark(X1:S),X2:S)
 mark(h(X:S)) -> a__h(mark(X:S))
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.