(0) Obligation:

Clauses:

d(X, X, 1).
d(T, X1, 0) :- isnumber(T).
d(times(U, V), X, +(times(B, U), times(A, V))) :- ','(d(U, X, A), d(V, X, B)).
d(div(U, V), X, W) :- d(times(U, power(V, p(0))), X, W).
d(power(U, V), X, times(V, times(W, power(U, p(V))))) :- ','(isnumber(V), d(U, X, W)).
isnumber(0).
isnumber(s(X)) :- isnumber(X).
isnumber(p(X)) :- isnumber(X).

Queries:

d(g,g,a).

(1) PrologToPiTRSProof (SOUND transformation)

We use the technique of [LOPSTR]. With regard to the inferred argument filtering the predicates were used in the following modes:
d_in: (b,b,f)
isnumber_in: (b)
Transforming Prolog into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog

(2) Obligation:

Pi-finite rewrite system:
The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)

(3) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

D_IN_GGA(T, X1, 0) → U1_GGA(T, X1, isnumber_in_g(T))
D_IN_GGA(T, X1, 0) → ISNUMBER_IN_G(T)
ISNUMBER_IN_G(s(X)) → U7_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(p(X)) → U8_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → U2_GGA(U, V, X, B, A, d_in_gga(U, X, A))
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → D_IN_GGA(U, X, A)
D_IN_GGA(div(U, V), X, W) → U4_GGA(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
D_IN_GGA(div(U, V), X, W) → D_IN_GGA(times(U, power(V, p(0))), X, W)
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_GGA(U, V, X, W, isnumber_in_g(V))
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → ISNUMBER_IN_G(V)
U5_GGA(U, V, X, W, isnumber_out_g(V)) → U6_GGA(U, V, X, W, d_in_gga(U, X, W))
U5_GGA(U, V, X, W, isnumber_out_g(V)) → D_IN_GGA(U, X, W)
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → U3_GGA(U, V, X, B, A, d_in_gga(V, X, B))
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → D_IN_GGA(V, X, B)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)
D_IN_GGA(x1, x2, x3)  =  D_IN_GGA(x1, x2)
U1_GGA(x1, x2, x3)  =  U1_GGA(x3)
ISNUMBER_IN_G(x1)  =  ISNUMBER_IN_G(x1)
U7_G(x1, x2)  =  U7_G(x2)
U8_G(x1, x2)  =  U8_G(x2)
U2_GGA(x1, x2, x3, x4, x5, x6)  =  U2_GGA(x1, x2, x3, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x5)
U5_GGA(x1, x2, x3, x4, x5)  =  U5_GGA(x1, x2, x3, x5)
U6_GGA(x1, x2, x3, x4, x5)  =  U6_GGA(x1, x2, x5)
U3_GGA(x1, x2, x3, x4, x5, x6)  =  U3_GGA(x1, x2, x5, x6)

We have to consider all (P,R,Pi)-chains

(4) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

D_IN_GGA(T, X1, 0) → U1_GGA(T, X1, isnumber_in_g(T))
D_IN_GGA(T, X1, 0) → ISNUMBER_IN_G(T)
ISNUMBER_IN_G(s(X)) → U7_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(p(X)) → U8_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → U2_GGA(U, V, X, B, A, d_in_gga(U, X, A))
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → D_IN_GGA(U, X, A)
D_IN_GGA(div(U, V), X, W) → U4_GGA(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
D_IN_GGA(div(U, V), X, W) → D_IN_GGA(times(U, power(V, p(0))), X, W)
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_GGA(U, V, X, W, isnumber_in_g(V))
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → ISNUMBER_IN_G(V)
U5_GGA(U, V, X, W, isnumber_out_g(V)) → U6_GGA(U, V, X, W, d_in_gga(U, X, W))
U5_GGA(U, V, X, W, isnumber_out_g(V)) → D_IN_GGA(U, X, W)
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → U3_GGA(U, V, X, B, A, d_in_gga(V, X, B))
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → D_IN_GGA(V, X, B)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)
D_IN_GGA(x1, x2, x3)  =  D_IN_GGA(x1, x2)
U1_GGA(x1, x2, x3)  =  U1_GGA(x3)
ISNUMBER_IN_G(x1)  =  ISNUMBER_IN_G(x1)
U7_G(x1, x2)  =  U7_G(x2)
U8_G(x1, x2)  =  U8_G(x2)
U2_GGA(x1, x2, x3, x4, x5, x6)  =  U2_GGA(x1, x2, x3, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x5)
U5_GGA(x1, x2, x3, x4, x5)  =  U5_GGA(x1, x2, x3, x5)
U6_GGA(x1, x2, x3, x4, x5)  =  U6_GGA(x1, x2, x5)
U3_GGA(x1, x2, x3, x4, x5, x6)  =  U3_GGA(x1, x2, x5, x6)

We have to consider all (P,R,Pi)-chains

(5) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 8 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)
ISNUMBER_IN_G(x1)  =  ISNUMBER_IN_G(x1)

We have to consider all (P,R,Pi)-chains

(8) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(9) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)

R is empty.
Pi is empty.
We have to consider all (P,R,Pi)-chains

(10) PiDPToQDPProof (EQUIVALENT transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(11) Obligation:

Q DP problem:
The TRS P consists of the following rules:

ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(12) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
    The graph contains the following edges 1 > 1

  • ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
    The graph contains the following edges 1 > 1

(13) TRUE

(14) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → U2_GGA(U, V, X, B, A, d_in_gga(U, X, A))
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → D_IN_GGA(V, X, B)
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → D_IN_GGA(U, X, A)
D_IN_GGA(div(U, V), X, W) → D_IN_GGA(times(U, power(V, p(0))), X, W)
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_GGA(U, V, X, W, isnumber_in_g(V))
U5_GGA(U, V, X, W, isnumber_out_g(V)) → D_IN_GGA(U, X, W)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)
D_IN_GGA(x1, x2, x3)  =  D_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4, x5, x6)  =  U2_GGA(x1, x2, x3, x6)
U5_GGA(x1, x2, x3, x4, x5)  =  U5_GGA(x1, x2, x3, x5)

We have to consider all (P,R,Pi)-chains

(15) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(16) Obligation:

Q DP problem:
The TRS P consists of the following rules:

D_IN_GGA(times(U, V), X) → U2_GGA(U, V, X, d_in_gga(U, X))
U2_GGA(U, V, X, d_out_gga(A)) → D_IN_GGA(V, X)
D_IN_GGA(times(U, V), X) → D_IN_GGA(U, X)
D_IN_GGA(div(U, V), X) → D_IN_GGA(times(U, power(V, p(0))), X)
D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U5_GGA(U, V, X, isnumber_out_g) → D_IN_GGA(U, X)

The TRS R consists of the following rules:

d_in_gga(X, X) → d_out_gga(1)
d_in_gga(T, X1) → U1_gga(isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g
isnumber_in_g(s(X)) → U7_g(isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(isnumber_in_g(X))
U8_g(isnumber_out_g) → isnumber_out_g
U7_g(isnumber_out_g) → isnumber_out_g
U1_gga(isnumber_out_g) → d_out_gga(0)
d_in_gga(times(U, V), X) → U2_gga(U, V, X, d_in_gga(U, X))
d_in_gga(div(U, V), X) → U4_gga(d_in_gga(times(U, power(V, p(0))), X))
d_in_gga(power(U, V), X) → U5_gga(U, V, X, isnumber_in_g(V))
U5_gga(U, V, X, isnumber_out_g) → U6_gga(U, V, d_in_gga(U, X))
U6_gga(U, V, d_out_gga(W)) → d_out_gga(times(V, times(W, power(U, p(V)))))
U4_gga(d_out_gga(W)) → d_out_gga(W)
U2_gga(U, V, X, d_out_gga(A)) → U3_gga(U, V, A, d_in_gga(V, X))
U3_gga(U, V, A, d_out_gga(B)) → d_out_gga(+(times(B, U), times(A, V)))

The set Q consists of the following terms:

d_in_gga(x0, x1)
isnumber_in_g(x0)
U8_g(x0)
U7_g(x0)
U1_gga(x0)
U5_gga(x0, x1, x2, x3)
U6_gga(x0, x1, x2)
U4_gga(x0)
U2_gga(x0, x1, x2, x3)
U3_gga(x0, x1, x2, x3)

We have to consider all (P,Q,R)-chains.

(17) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


D_IN_GGA(div(U, V), X) → D_IN_GGA(times(U, power(V, p(0))), X)
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:

POL(+(x1, x2)) = 0   
POL(0) = 0   
POL(1) = 0   
POL(D_IN_GGA(x1, x2)) = x1   
POL(U1_gga(x1)) = 0   
POL(U2_GGA(x1, x2, x3, x4)) = x1 + x2   
POL(U2_gga(x1, x2, x3, x4)) = 0   
POL(U3_gga(x1, x2, x3, x4)) = 0   
POL(U4_gga(x1)) = 0   
POL(U5_GGA(x1, x2, x3, x4)) = x1   
POL(U5_gga(x1, x2, x3, x4)) = 0   
POL(U6_gga(x1, x2, x3)) = 0   
POL(U7_g(x1)) = 0   
POL(U8_g(x1)) = 0   
POL(d_in_gga(x1, x2)) = 0   
POL(d_out_gga(x1)) = 0   
POL(div(x1, x2)) = 1 + x1 + x2   
POL(isnumber_in_g(x1)) = 0   
POL(isnumber_out_g) = 0   
POL(p(x1)) = 0   
POL(power(x1, x2)) = x1   
POL(s(x1)) = 0   
POL(times(x1, x2)) = x1 + x2   

The following usable rules [FROCOS05] were oriented: none

(18) Obligation:

Q DP problem:
The TRS P consists of the following rules:

D_IN_GGA(times(U, V), X) → U2_GGA(U, V, X, d_in_gga(U, X))
U2_GGA(U, V, X, d_out_gga(A)) → D_IN_GGA(V, X)
D_IN_GGA(times(U, V), X) → D_IN_GGA(U, X)
D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U5_GGA(U, V, X, isnumber_out_g) → D_IN_GGA(U, X)

The TRS R consists of the following rules:

d_in_gga(X, X) → d_out_gga(1)
d_in_gga(T, X1) → U1_gga(isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g
isnumber_in_g(s(X)) → U7_g(isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(isnumber_in_g(X))
U8_g(isnumber_out_g) → isnumber_out_g
U7_g(isnumber_out_g) → isnumber_out_g
U1_gga(isnumber_out_g) → d_out_gga(0)
d_in_gga(times(U, V), X) → U2_gga(U, V, X, d_in_gga(U, X))
d_in_gga(div(U, V), X) → U4_gga(d_in_gga(times(U, power(V, p(0))), X))
d_in_gga(power(U, V), X) → U5_gga(U, V, X, isnumber_in_g(V))
U5_gga(U, V, X, isnumber_out_g) → U6_gga(U, V, d_in_gga(U, X))
U6_gga(U, V, d_out_gga(W)) → d_out_gga(times(V, times(W, power(U, p(V)))))
U4_gga(d_out_gga(W)) → d_out_gga(W)
U2_gga(U, V, X, d_out_gga(A)) → U3_gga(U, V, A, d_in_gga(V, X))
U3_gga(U, V, A, d_out_gga(B)) → d_out_gga(+(times(B, U), times(A, V)))

The set Q consists of the following terms:

d_in_gga(x0, x1)
isnumber_in_g(x0)
U8_g(x0)
U7_g(x0)
U1_gga(x0)
U5_gga(x0, x1, x2, x3)
U6_gga(x0, x1, x2)
U4_gga(x0)
U2_gga(x0, x1, x2, x3)
U3_gga(x0, x1, x2, x3)

We have to consider all (P,Q,R)-chains.

(19) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • U2_GGA(U, V, X, d_out_gga(A)) → D_IN_GGA(V, X)
    The graph contains the following edges 2 >= 1, 3 >= 2

  • D_IN_GGA(times(U, V), X) → D_IN_GGA(U, X)
    The graph contains the following edges 1 > 1, 2 >= 2

  • U5_GGA(U, V, X, isnumber_out_g) → D_IN_GGA(U, X)
    The graph contains the following edges 1 >= 1, 3 >= 2

  • D_IN_GGA(times(U, V), X) → U2_GGA(U, V, X, d_in_gga(U, X))
    The graph contains the following edges 1 > 1, 1 > 2, 2 >= 3

  • D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
    The graph contains the following edges 1 > 1, 1 > 2, 2 >= 3

(20) TRUE

(21) PrologToPiTRSProof (SOUND transformation)

We use the technique of [LOPSTR]. With regard to the inferred argument filtering the predicates were used in the following modes:
d_in: (b,b,f)
isnumber_in: (b)
Transforming Prolog into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x1, x2, x3)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x2, x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g(x1)
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x1, x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x1, x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x1, x2, x3, x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x3, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x3, x5, x6)
+(x1, x2)  =  +(x1, x2)

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog

(22) Obligation:

Pi-finite rewrite system:
The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x1, x2, x3)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x2, x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g(x1)
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x1, x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x1, x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x1, x2, x3, x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x3, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x3, x5, x6)
+(x1, x2)  =  +(x1, x2)

(23) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

D_IN_GGA(T, X1, 0) → U1_GGA(T, X1, isnumber_in_g(T))
D_IN_GGA(T, X1, 0) → ISNUMBER_IN_G(T)
ISNUMBER_IN_G(s(X)) → U7_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(p(X)) → U8_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → U2_GGA(U, V, X, B, A, d_in_gga(U, X, A))
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → D_IN_GGA(U, X, A)
D_IN_GGA(div(U, V), X, W) → U4_GGA(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
D_IN_GGA(div(U, V), X, W) → D_IN_GGA(times(U, power(V, p(0))), X, W)
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_GGA(U, V, X, W, isnumber_in_g(V))
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → ISNUMBER_IN_G(V)
U5_GGA(U, V, X, W, isnumber_out_g(V)) → U6_GGA(U, V, X, W, d_in_gga(U, X, W))
U5_GGA(U, V, X, W, isnumber_out_g(V)) → D_IN_GGA(U, X, W)
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → U3_GGA(U, V, X, B, A, d_in_gga(V, X, B))
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → D_IN_GGA(V, X, B)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x1, x2, x3)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x2, x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g(x1)
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x1, x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x1, x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x1, x2, x3, x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x3, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x3, x5, x6)
+(x1, x2)  =  +(x1, x2)
D_IN_GGA(x1, x2, x3)  =  D_IN_GGA(x1, x2)
U1_GGA(x1, x2, x3)  =  U1_GGA(x1, x2, x3)
ISNUMBER_IN_G(x1)  =  ISNUMBER_IN_G(x1)
U7_G(x1, x2)  =  U7_G(x1, x2)
U8_G(x1, x2)  =  U8_G(x1, x2)
U2_GGA(x1, x2, x3, x4, x5, x6)  =  U2_GGA(x1, x2, x3, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x1, x2, x3, x5)
U5_GGA(x1, x2, x3, x4, x5)  =  U5_GGA(x1, x2, x3, x5)
U6_GGA(x1, x2, x3, x4, x5)  =  U6_GGA(x1, x2, x3, x5)
U3_GGA(x1, x2, x3, x4, x5, x6)  =  U3_GGA(x1, x2, x3, x5, x6)

We have to consider all (P,R,Pi)-chains

(24) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

D_IN_GGA(T, X1, 0) → U1_GGA(T, X1, isnumber_in_g(T))
D_IN_GGA(T, X1, 0) → ISNUMBER_IN_G(T)
ISNUMBER_IN_G(s(X)) → U7_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(p(X)) → U8_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → U2_GGA(U, V, X, B, A, d_in_gga(U, X, A))
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → D_IN_GGA(U, X, A)
D_IN_GGA(div(U, V), X, W) → U4_GGA(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
D_IN_GGA(div(U, V), X, W) → D_IN_GGA(times(U, power(V, p(0))), X, W)
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_GGA(U, V, X, W, isnumber_in_g(V))
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → ISNUMBER_IN_G(V)
U5_GGA(U, V, X, W, isnumber_out_g(V)) → U6_GGA(U, V, X, W, d_in_gga(U, X, W))
U5_GGA(U, V, X, W, isnumber_out_g(V)) → D_IN_GGA(U, X, W)
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → U3_GGA(U, V, X, B, A, d_in_gga(V, X, B))
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → D_IN_GGA(V, X, B)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x1, x2, x3)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x2, x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g(x1)
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x1, x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x1, x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x1, x2, x3, x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x3, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x3, x5, x6)
+(x1, x2)  =  +(x1, x2)
D_IN_GGA(x1, x2, x3)  =  D_IN_GGA(x1, x2)
U1_GGA(x1, x2, x3)  =  U1_GGA(x1, x2, x3)
ISNUMBER_IN_G(x1)  =  ISNUMBER_IN_G(x1)
U7_G(x1, x2)  =  U7_G(x1, x2)
U8_G(x1, x2)  =  U8_G(x1, x2)
U2_GGA(x1, x2, x3, x4, x5, x6)  =  U2_GGA(x1, x2, x3, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x1, x2, x3, x5)
U5_GGA(x1, x2, x3, x4, x5)  =  U5_GGA(x1, x2, x3, x5)
U6_GGA(x1, x2, x3, x4, x5)  =  U6_GGA(x1, x2, x3, x5)
U3_GGA(x1, x2, x3, x4, x5, x6)  =  U3_GGA(x1, x2, x3, x5, x6)

We have to consider all (P,R,Pi)-chains

(25) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 8 less nodes.

(26) Complex Obligation (AND)

(27) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x1, x2, x3)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x2, x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g(x1)
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x1, x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x1, x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x1, x2, x3, x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x3, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x3, x5, x6)
+(x1, x2)  =  +(x1, x2)
ISNUMBER_IN_G(x1)  =  ISNUMBER_IN_G(x1)

We have to consider all (P,R,Pi)-chains

(28) UsableRulesProof (EQUIVALENT transformation)

For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.

(29) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)

R is empty.
Pi is empty.
We have to consider all (P,R,Pi)-chains

(30) PiDPToQDPProof (EQUIVALENT transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(31) Obligation:

Q DP problem:
The TRS P consists of the following rules:

ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.

(32) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
    The graph contains the following edges 1 > 1

  • ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
    The graph contains the following edges 1 > 1

(33) TRUE

(34) Obligation:

Pi DP problem:
The TRS P consists of the following rules:

D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → U2_GGA(U, V, X, B, A, d_in_gga(U, X, A))
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → D_IN_GGA(V, X, B)
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → D_IN_GGA(U, X, A)
D_IN_GGA(div(U, V), X, W) → D_IN_GGA(times(U, power(V, p(0))), X, W)
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_GGA(U, V, X, W, isnumber_in_g(V))
U5_GGA(U, V, X, W, isnumber_out_g(V)) → D_IN_GGA(U, X, W)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X1, 0) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x1, x2, x3)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x2, x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g(x1)
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x1, x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x1, x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x1, x2, x3, x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x3, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x3, x5, x6)
+(x1, x2)  =  +(x1, x2)
D_IN_GGA(x1, x2, x3)  =  D_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4, x5, x6)  =  U2_GGA(x1, x2, x3, x6)
U5_GGA(x1, x2, x3, x4, x5)  =  U5_GGA(x1, x2, x3, x5)

We have to consider all (P,R,Pi)-chains

(35) PiDPToQDPProof (SOUND transformation)

Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.

(36) Obligation:

Q DP problem:
The TRS P consists of the following rules:

D_IN_GGA(times(U, V), X) → U2_GGA(U, V, X, d_in_gga(U, X))
U2_GGA(U, V, X, d_out_gga(U, X, A)) → D_IN_GGA(V, X)
D_IN_GGA(times(U, V), X) → D_IN_GGA(U, X)
D_IN_GGA(div(U, V), X) → D_IN_GGA(times(U, power(V, p(0))), X)
D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U5_GGA(U, V, X, isnumber_out_g(V)) → D_IN_GGA(U, X)

The TRS R consists of the following rules:

d_in_gga(X, X) → d_out_gga(X, X, 1)
d_in_gga(T, X1) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X) → U2_gga(U, V, X, d_in_gga(U, X))
d_in_gga(div(U, V), X) → U4_gga(U, V, X, d_in_gga(times(U, power(V, p(0))), X))
d_in_gga(power(U, V), X) → U5_gga(U, V, X, isnumber_in_g(V))
U5_gga(U, V, X, isnumber_out_g(V)) → U6_gga(U, V, X, d_in_gga(U, X))
U6_gga(U, V, X, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, d_out_gga(U, X, A)) → U3_gga(U, V, X, A, d_in_gga(V, X))
U3_gga(U, V, X, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The set Q consists of the following terms:

d_in_gga(x0, x1)
isnumber_in_g(x0)
U8_g(x0, x1)
U7_g(x0, x1)
U1_gga(x0, x1, x2)
U5_gga(x0, x1, x2, x3)
U6_gga(x0, x1, x2, x3)
U4_gga(x0, x1, x2, x3)
U2_gga(x0, x1, x2, x3)
U3_gga(x0, x1, x2, x3, x4)

We have to consider all (P,Q,R)-chains.

(37) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


D_IN_GGA(times(U, V), X) → U2_GGA(U, V, X, d_in_gga(U, X))
D_IN_GGA(times(U, V), X) → D_IN_GGA(U, X)
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:

POL(+(x1, x2)) = 0   
POL(0) = 0   
POL(1) = 0   
POL(D_IN_GGA(x1, x2)) = x1   
POL(U1_gga(x1, x2, x3)) = 0   
POL(U2_GGA(x1, x2, x3, x4)) = x2   
POL(U2_gga(x1, x2, x3, x4)) = 0   
POL(U3_gga(x1, x2, x3, x4, x5)) = 0   
POL(U4_gga(x1, x2, x3, x4)) = 0   
POL(U5_GGA(x1, x2, x3, x4)) = x1   
POL(U5_gga(x1, x2, x3, x4)) = 0   
POL(U6_gga(x1, x2, x3, x4)) = 0   
POL(U7_g(x1, x2)) = 0   
POL(U8_g(x1, x2)) = 0   
POL(d_in_gga(x1, x2)) = 0   
POL(d_out_gga(x1, x2, x3)) = 0   
POL(div(x1, x2)) = 1 + x1 + x2   
POL(isnumber_in_g(x1)) = 0   
POL(isnumber_out_g(x1)) = 0   
POL(p(x1)) = 0   
POL(power(x1, x2)) = x1   
POL(s(x1)) = 0   
POL(times(x1, x2)) = 1 + x1 + x2   

The following usable rules [FROCOS05] were oriented: none

(38) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U2_GGA(U, V, X, d_out_gga(U, X, A)) → D_IN_GGA(V, X)
D_IN_GGA(div(U, V), X) → D_IN_GGA(times(U, power(V, p(0))), X)
D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U5_GGA(U, V, X, isnumber_out_g(V)) → D_IN_GGA(U, X)

The TRS R consists of the following rules:

d_in_gga(X, X) → d_out_gga(X, X, 1)
d_in_gga(T, X1) → U1_gga(T, X1, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X1, isnumber_out_g(T)) → d_out_gga(T, X1, 0)
d_in_gga(times(U, V), X) → U2_gga(U, V, X, d_in_gga(U, X))
d_in_gga(div(U, V), X) → U4_gga(U, V, X, d_in_gga(times(U, power(V, p(0))), X))
d_in_gga(power(U, V), X) → U5_gga(U, V, X, isnumber_in_g(V))
U5_gga(U, V, X, isnumber_out_g(V)) → U6_gga(U, V, X, d_in_gga(U, X))
U6_gga(U, V, X, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, d_out_gga(U, X, A)) → U3_gga(U, V, X, A, d_in_gga(V, X))
U3_gga(U, V, X, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The set Q consists of the following terms:

d_in_gga(x0, x1)
isnumber_in_g(x0)
U8_g(x0, x1)
U7_g(x0, x1)
U1_gga(x0, x1, x2)
U5_gga(x0, x1, x2, x3)
U6_gga(x0, x1, x2, x3)
U4_gga(x0, x1, x2, x3)
U2_gga(x0, x1, x2, x3)
U3_gga(x0, x1, x2, x3, x4)

We have to consider all (P,Q,R)-chains.