YES

Problem 1: 

(VAR v_NonEmpty:S x:S y:S)
(RULES
f(g(x:S),g(y:S)) -> f(p(f(g(x:S),s(y:S))),g(s(p(x:S))))
g(s(p(x:S))) -> p(x:S)
p(0) -> g(0)
) 
(STRATEGY INNERMOST)

Problem 1: 

Dependency Pairs Processor:
-> Pairs:
 F(g(x:S),g(y:S)) -> F(g(x:S),s(y:S))
 F(g(x:S),g(y:S)) -> F(p(f(g(x:S),s(y:S))),g(s(p(x:S))))
 F(g(x:S),g(y:S)) -> G(s(p(x:S)))
 F(g(x:S),g(y:S)) -> P(f(g(x:S),s(y:S)))
 F(g(x:S),g(y:S)) -> P(x:S)
-> Rules:
 f(g(x:S),g(y:S)) -> f(p(f(g(x:S),s(y:S))),g(s(p(x:S))))
 g(s(p(x:S))) -> p(x:S)
 p(0) -> g(0)

Problem 1: 

SCC Processor:
-> Pairs:
 F(g(x:S),g(y:S)) -> F(g(x:S),s(y:S))
 F(g(x:S),g(y:S)) -> F(p(f(g(x:S),s(y:S))),g(s(p(x:S))))
 F(g(x:S),g(y:S)) -> G(s(p(x:S)))
 F(g(x:S),g(y:S)) -> P(f(g(x:S),s(y:S)))
 F(g(x:S),g(y:S)) -> P(x:S)
-> Rules:
 f(g(x:S),g(y:S)) -> f(p(f(g(x:S),s(y:S))),g(s(p(x:S))))
 g(s(p(x:S))) -> p(x:S)
 p(0) -> g(0)
->Strongly Connected Components:
 There is no strongly connected component

The problem is finite.