(0) Obligation:

Clauses:

div(X1, 0, X2, X3) :- failure(a).
div(0, Y, 0, 0) :- no(zero(Y)).
div(X, Y, s(Z), R) :- ','(no(zero(X)), ','(no(zero(Y)), ','(minus(X, Y, U), ','(!, div(U, Y, Z, R))))).
div(X, Y, X4, X) :- ','(no(zero(X)), no(zero(Y))).
minus(X, 0, X).
minus(s(X), s(Y), Z) :- minus(X, Y, Z).
failure(b).
zero(0).
no(X) :- ','(X, ','(!, failure(a))).
no(X5).

Query: div(g,g,a,a)

(1) PrologToPiTRSViaGraphTransformerProof (SOUND transformation)

Transformed Prolog program to (Pi-)TRS.

(2) Obligation:

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

divA_in_ggaa(0, T72, 0, 0) → divA_out_ggaa(0, T72, 0, 0)
divA_in_ggaa(T121, T135, s(T104), T105) → U1_ggaa(T121, T135, T104, T105, pB_in_ggaaa(T121, T135, X177, T104, T105))
pB_in_ggaaa(T121, T135, T144, T104, T105) → U5_ggaaa(T121, T135, T144, T104, T105, minusD_in_gga(T121, T135, T144))
minusD_in_gga(s(T154), s(T155), X255) → U3_gga(T154, T155, X255, minusC_in_gga(T154, T155, X255))
minusC_in_gga(T162, 0, T162) → minusC_out_gga(T162, 0, T162)
minusC_in_gga(s(T167), s(T168), X274) → U2_gga(T167, T168, X274, minusC_in_gga(T167, T168, X274))
U2_gga(T167, T168, X274, minusC_out_gga(T167, T168, X274)) → minusC_out_gga(s(T167), s(T168), X274)
U3_gga(T154, T155, X255, minusC_out_gga(T154, T155, X255)) → minusD_out_gga(s(T154), s(T155), X255)
U5_ggaaa(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → U6_ggaaa(T121, T135, T144, T104, T105, pE_in_ggaa(T144, T135, T104, T105))
pE_in_ggaa(T144, T135, T104, T105) → U4_ggaa(T144, T135, T104, T105, divA_in_ggaa(T144, T135, T104, T105))
divA_in_ggaa(T189, T195, T183, T189) → divA_out_ggaa(T189, T195, T183, T189)
U4_ggaa(T144, T135, T104, T105, divA_out_ggaa(T144, T135, T104, T105)) → pE_out_ggaa(T144, T135, T104, T105)
U6_ggaaa(T121, T135, T144, T104, T105, pE_out_ggaa(T144, T135, T104, T105)) → pB_out_ggaaa(T121, T135, T144, T104, T105)
U1_ggaa(T121, T135, T104, T105, pB_out_ggaaa(T121, T135, X177, T104, T105)) → divA_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divA_in_ggaa(x1, x2, x3, x4)  =  divA_in_ggaa(x1, x2)
0  =  0
divA_out_ggaa(x1, x2, x3, x4)  =  divA_out_ggaa(x1, x2, x4)
U1_ggaa(x1, x2, x3, x4, x5)  =  U1_ggaa(x1, x2, x5)
pB_in_ggaaa(x1, x2, x3, x4, x5)  =  pB_in_ggaaa(x1, x2)
U5_ggaaa(x1, x2, x3, x4, x5, x6)  =  U5_ggaaa(x1, x2, x6)
minusD_in_gga(x1, x2, x3)  =  minusD_in_gga(x1, x2)
s(x1)  =  s(x1)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
minusC_in_gga(x1, x2, x3)  =  minusC_in_gga(x1, x2)
minusC_out_gga(x1, x2, x3)  =  minusC_out_gga(x1, x2, x3)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x1, x2, x4)
minusD_out_gga(x1, x2, x3)  =  minusD_out_gga(x1, x2, x3)
U6_ggaaa(x1, x2, x3, x4, x5, x6)  =  U6_ggaaa(x1, x2, x3, x6)
pE_in_ggaa(x1, x2, x3, x4)  =  pE_in_ggaa(x1, x2)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x1, x2, x5)
pE_out_ggaa(x1, x2, x3, x4)  =  pE_out_ggaa(x1, x2, x4)
pB_out_ggaaa(x1, x2, x3, x4, x5)  =  pB_out_ggaaa(x1, x2, x3, x5)

(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:

DIVA_IN_GGAA(T121, T135, s(T104), T105) → U1_GGAA(T121, T135, T104, T105, pB_in_ggaaa(T121, T135, X177, T104, T105))
DIVA_IN_GGAA(T121, T135, s(T104), T105) → PB_IN_GGAAA(T121, T135, X177, T104, T105)
PB_IN_GGAAA(T121, T135, T144, T104, T105) → U5_GGAAA(T121, T135, T144, T104, T105, minusD_in_gga(T121, T135, T144))
PB_IN_GGAAA(T121, T135, T144, T104, T105) → MINUSD_IN_GGA(T121, T135, T144)
MINUSD_IN_GGA(s(T154), s(T155), X255) → U3_GGA(T154, T155, X255, minusC_in_gga(T154, T155, X255))
MINUSD_IN_GGA(s(T154), s(T155), X255) → MINUSC_IN_GGA(T154, T155, X255)
MINUSC_IN_GGA(s(T167), s(T168), X274) → U2_GGA(T167, T168, X274, minusC_in_gga(T167, T168, X274))
MINUSC_IN_GGA(s(T167), s(T168), X274) → MINUSC_IN_GGA(T167, T168, X274)
U5_GGAAA(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → U6_GGAAA(T121, T135, T144, T104, T105, pE_in_ggaa(T144, T135, T104, T105))
U5_GGAAA(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → PE_IN_GGAA(T144, T135, T104, T105)
PE_IN_GGAA(T144, T135, T104, T105) → U4_GGAA(T144, T135, T104, T105, divA_in_ggaa(T144, T135, T104, T105))
PE_IN_GGAA(T144, T135, T104, T105) → DIVA_IN_GGAA(T144, T135, T104, T105)

The TRS R consists of the following rules:

divA_in_ggaa(0, T72, 0, 0) → divA_out_ggaa(0, T72, 0, 0)
divA_in_ggaa(T121, T135, s(T104), T105) → U1_ggaa(T121, T135, T104, T105, pB_in_ggaaa(T121, T135, X177, T104, T105))
pB_in_ggaaa(T121, T135, T144, T104, T105) → U5_ggaaa(T121, T135, T144, T104, T105, minusD_in_gga(T121, T135, T144))
minusD_in_gga(s(T154), s(T155), X255) → U3_gga(T154, T155, X255, minusC_in_gga(T154, T155, X255))
minusC_in_gga(T162, 0, T162) → minusC_out_gga(T162, 0, T162)
minusC_in_gga(s(T167), s(T168), X274) → U2_gga(T167, T168, X274, minusC_in_gga(T167, T168, X274))
U2_gga(T167, T168, X274, minusC_out_gga(T167, T168, X274)) → minusC_out_gga(s(T167), s(T168), X274)
U3_gga(T154, T155, X255, minusC_out_gga(T154, T155, X255)) → minusD_out_gga(s(T154), s(T155), X255)
U5_ggaaa(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → U6_ggaaa(T121, T135, T144, T104, T105, pE_in_ggaa(T144, T135, T104, T105))
pE_in_ggaa(T144, T135, T104, T105) → U4_ggaa(T144, T135, T104, T105, divA_in_ggaa(T144, T135, T104, T105))
divA_in_ggaa(T189, T195, T183, T189) → divA_out_ggaa(T189, T195, T183, T189)
U4_ggaa(T144, T135, T104, T105, divA_out_ggaa(T144, T135, T104, T105)) → pE_out_ggaa(T144, T135, T104, T105)
U6_ggaaa(T121, T135, T144, T104, T105, pE_out_ggaa(T144, T135, T104, T105)) → pB_out_ggaaa(T121, T135, T144, T104, T105)
U1_ggaa(T121, T135, T104, T105, pB_out_ggaaa(T121, T135, X177, T104, T105)) → divA_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divA_in_ggaa(x1, x2, x3, x4)  =  divA_in_ggaa(x1, x2)
0  =  0
divA_out_ggaa(x1, x2, x3, x4)  =  divA_out_ggaa(x1, x2, x4)
U1_ggaa(x1, x2, x3, x4, x5)  =  U1_ggaa(x1, x2, x5)
pB_in_ggaaa(x1, x2, x3, x4, x5)  =  pB_in_ggaaa(x1, x2)
U5_ggaaa(x1, x2, x3, x4, x5, x6)  =  U5_ggaaa(x1, x2, x6)
minusD_in_gga(x1, x2, x3)  =  minusD_in_gga(x1, x2)
s(x1)  =  s(x1)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
minusC_in_gga(x1, x2, x3)  =  minusC_in_gga(x1, x2)
minusC_out_gga(x1, x2, x3)  =  minusC_out_gga(x1, x2, x3)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x1, x2, x4)
minusD_out_gga(x1, x2, x3)  =  minusD_out_gga(x1, x2, x3)
U6_ggaaa(x1, x2, x3, x4, x5, x6)  =  U6_ggaaa(x1, x2, x3, x6)
pE_in_ggaa(x1, x2, x3, x4)  =  pE_in_ggaa(x1, x2)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x1, x2, x5)
pE_out_ggaa(x1, x2, x3, x4)  =  pE_out_ggaa(x1, x2, x4)
pB_out_ggaaa(x1, x2, x3, x4, x5)  =  pB_out_ggaaa(x1, x2, x3, x5)
DIVA_IN_GGAA(x1, x2, x3, x4)  =  DIVA_IN_GGAA(x1, x2)
U1_GGAA(x1, x2, x3, x4, x5)  =  U1_GGAA(x1, x2, x5)
PB_IN_GGAAA(x1, x2, x3, x4, x5)  =  PB_IN_GGAAA(x1, x2)
U5_GGAAA(x1, x2, x3, x4, x5, x6)  =  U5_GGAAA(x1, x2, x6)
MINUSD_IN_GGA(x1, x2, x3)  =  MINUSD_IN_GGA(x1, x2)
U3_GGA(x1, x2, x3, x4)  =  U3_GGA(x1, x2, x4)
MINUSC_IN_GGA(x1, x2, x3)  =  MINUSC_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4)  =  U2_GGA(x1, x2, x4)
U6_GGAAA(x1, x2, x3, x4, x5, x6)  =  U6_GGAAA(x1, x2, x3, x6)
PE_IN_GGAA(x1, x2, x3, x4)  =  PE_IN_GGAA(x1, x2)
U4_GGAA(x1, x2, x3, x4, x5)  =  U4_GGAA(x1, x2, x5)

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

(4) Obligation:

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

DIVA_IN_GGAA(T121, T135, s(T104), T105) → U1_GGAA(T121, T135, T104, T105, pB_in_ggaaa(T121, T135, X177, T104, T105))
DIVA_IN_GGAA(T121, T135, s(T104), T105) → PB_IN_GGAAA(T121, T135, X177, T104, T105)
PB_IN_GGAAA(T121, T135, T144, T104, T105) → U5_GGAAA(T121, T135, T144, T104, T105, minusD_in_gga(T121, T135, T144))
PB_IN_GGAAA(T121, T135, T144, T104, T105) → MINUSD_IN_GGA(T121, T135, T144)
MINUSD_IN_GGA(s(T154), s(T155), X255) → U3_GGA(T154, T155, X255, minusC_in_gga(T154, T155, X255))
MINUSD_IN_GGA(s(T154), s(T155), X255) → MINUSC_IN_GGA(T154, T155, X255)
MINUSC_IN_GGA(s(T167), s(T168), X274) → U2_GGA(T167, T168, X274, minusC_in_gga(T167, T168, X274))
MINUSC_IN_GGA(s(T167), s(T168), X274) → MINUSC_IN_GGA(T167, T168, X274)
U5_GGAAA(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → U6_GGAAA(T121, T135, T144, T104, T105, pE_in_ggaa(T144, T135, T104, T105))
U5_GGAAA(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → PE_IN_GGAA(T144, T135, T104, T105)
PE_IN_GGAA(T144, T135, T104, T105) → U4_GGAA(T144, T135, T104, T105, divA_in_ggaa(T144, T135, T104, T105))
PE_IN_GGAA(T144, T135, T104, T105) → DIVA_IN_GGAA(T144, T135, T104, T105)

The TRS R consists of the following rules:

divA_in_ggaa(0, T72, 0, 0) → divA_out_ggaa(0, T72, 0, 0)
divA_in_ggaa(T121, T135, s(T104), T105) → U1_ggaa(T121, T135, T104, T105, pB_in_ggaaa(T121, T135, X177, T104, T105))
pB_in_ggaaa(T121, T135, T144, T104, T105) → U5_ggaaa(T121, T135, T144, T104, T105, minusD_in_gga(T121, T135, T144))
minusD_in_gga(s(T154), s(T155), X255) → U3_gga(T154, T155, X255, minusC_in_gga(T154, T155, X255))
minusC_in_gga(T162, 0, T162) → minusC_out_gga(T162, 0, T162)
minusC_in_gga(s(T167), s(T168), X274) → U2_gga(T167, T168, X274, minusC_in_gga(T167, T168, X274))
U2_gga(T167, T168, X274, minusC_out_gga(T167, T168, X274)) → minusC_out_gga(s(T167), s(T168), X274)
U3_gga(T154, T155, X255, minusC_out_gga(T154, T155, X255)) → minusD_out_gga(s(T154), s(T155), X255)
U5_ggaaa(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → U6_ggaaa(T121, T135, T144, T104, T105, pE_in_ggaa(T144, T135, T104, T105))
pE_in_ggaa(T144, T135, T104, T105) → U4_ggaa(T144, T135, T104, T105, divA_in_ggaa(T144, T135, T104, T105))
divA_in_ggaa(T189, T195, T183, T189) → divA_out_ggaa(T189, T195, T183, T189)
U4_ggaa(T144, T135, T104, T105, divA_out_ggaa(T144, T135, T104, T105)) → pE_out_ggaa(T144, T135, T104, T105)
U6_ggaaa(T121, T135, T144, T104, T105, pE_out_ggaa(T144, T135, T104, T105)) → pB_out_ggaaa(T121, T135, T144, T104, T105)
U1_ggaa(T121, T135, T104, T105, pB_out_ggaaa(T121, T135, X177, T104, T105)) → divA_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divA_in_ggaa(x1, x2, x3, x4)  =  divA_in_ggaa(x1, x2)
0  =  0
divA_out_ggaa(x1, x2, x3, x4)  =  divA_out_ggaa(x1, x2, x4)
U1_ggaa(x1, x2, x3, x4, x5)  =  U1_ggaa(x1, x2, x5)
pB_in_ggaaa(x1, x2, x3, x4, x5)  =  pB_in_ggaaa(x1, x2)
U5_ggaaa(x1, x2, x3, x4, x5, x6)  =  U5_ggaaa(x1, x2, x6)
minusD_in_gga(x1, x2, x3)  =  minusD_in_gga(x1, x2)
s(x1)  =  s(x1)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
minusC_in_gga(x1, x2, x3)  =  minusC_in_gga(x1, x2)
minusC_out_gga(x1, x2, x3)  =  minusC_out_gga(x1, x2, x3)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x1, x2, x4)
minusD_out_gga(x1, x2, x3)  =  minusD_out_gga(x1, x2, x3)
U6_ggaaa(x1, x2, x3, x4, x5, x6)  =  U6_ggaaa(x1, x2, x3, x6)
pE_in_ggaa(x1, x2, x3, x4)  =  pE_in_ggaa(x1, x2)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x1, x2, x5)
pE_out_ggaa(x1, x2, x3, x4)  =  pE_out_ggaa(x1, x2, x4)
pB_out_ggaaa(x1, x2, x3, x4, x5)  =  pB_out_ggaaa(x1, x2, x3, x5)
DIVA_IN_GGAA(x1, x2, x3, x4)  =  DIVA_IN_GGAA(x1, x2)
U1_GGAA(x1, x2, x3, x4, x5)  =  U1_GGAA(x1, x2, x5)
PB_IN_GGAAA(x1, x2, x3, x4, x5)  =  PB_IN_GGAAA(x1, x2)
U5_GGAAA(x1, x2, x3, x4, x5, x6)  =  U5_GGAAA(x1, x2, x6)
MINUSD_IN_GGA(x1, x2, x3)  =  MINUSD_IN_GGA(x1, x2)
U3_GGA(x1, x2, x3, x4)  =  U3_GGA(x1, x2, x4)
MINUSC_IN_GGA(x1, x2, x3)  =  MINUSC_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4)  =  U2_GGA(x1, x2, x4)
U6_GGAAA(x1, x2, x3, x4, x5, x6)  =  U6_GGAAA(x1, x2, x3, x6)
PE_IN_GGAA(x1, x2, x3, x4)  =  PE_IN_GGAA(x1, x2)
U4_GGAA(x1, x2, x3, x4, x5)  =  U4_GGAA(x1, x2, x5)

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

(5) DependencyGraphProof (EQUIVALENT transformation)

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

(6) Complex Obligation (AND)

(7) Obligation:

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

MINUSC_IN_GGA(s(T167), s(T168), X274) → MINUSC_IN_GGA(T167, T168, X274)

The TRS R consists of the following rules:

divA_in_ggaa(0, T72, 0, 0) → divA_out_ggaa(0, T72, 0, 0)
divA_in_ggaa(T121, T135, s(T104), T105) → U1_ggaa(T121, T135, T104, T105, pB_in_ggaaa(T121, T135, X177, T104, T105))
pB_in_ggaaa(T121, T135, T144, T104, T105) → U5_ggaaa(T121, T135, T144, T104, T105, minusD_in_gga(T121, T135, T144))
minusD_in_gga(s(T154), s(T155), X255) → U3_gga(T154, T155, X255, minusC_in_gga(T154, T155, X255))
minusC_in_gga(T162, 0, T162) → minusC_out_gga(T162, 0, T162)
minusC_in_gga(s(T167), s(T168), X274) → U2_gga(T167, T168, X274, minusC_in_gga(T167, T168, X274))
U2_gga(T167, T168, X274, minusC_out_gga(T167, T168, X274)) → minusC_out_gga(s(T167), s(T168), X274)
U3_gga(T154, T155, X255, minusC_out_gga(T154, T155, X255)) → minusD_out_gga(s(T154), s(T155), X255)
U5_ggaaa(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → U6_ggaaa(T121, T135, T144, T104, T105, pE_in_ggaa(T144, T135, T104, T105))
pE_in_ggaa(T144, T135, T104, T105) → U4_ggaa(T144, T135, T104, T105, divA_in_ggaa(T144, T135, T104, T105))
divA_in_ggaa(T189, T195, T183, T189) → divA_out_ggaa(T189, T195, T183, T189)
U4_ggaa(T144, T135, T104, T105, divA_out_ggaa(T144, T135, T104, T105)) → pE_out_ggaa(T144, T135, T104, T105)
U6_ggaaa(T121, T135, T144, T104, T105, pE_out_ggaa(T144, T135, T104, T105)) → pB_out_ggaaa(T121, T135, T144, T104, T105)
U1_ggaa(T121, T135, T104, T105, pB_out_ggaaa(T121, T135, X177, T104, T105)) → divA_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divA_in_ggaa(x1, x2, x3, x4)  =  divA_in_ggaa(x1, x2)
0  =  0
divA_out_ggaa(x1, x2, x3, x4)  =  divA_out_ggaa(x1, x2, x4)
U1_ggaa(x1, x2, x3, x4, x5)  =  U1_ggaa(x1, x2, x5)
pB_in_ggaaa(x1, x2, x3, x4, x5)  =  pB_in_ggaaa(x1, x2)
U5_ggaaa(x1, x2, x3, x4, x5, x6)  =  U5_ggaaa(x1, x2, x6)
minusD_in_gga(x1, x2, x3)  =  minusD_in_gga(x1, x2)
s(x1)  =  s(x1)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
minusC_in_gga(x1, x2, x3)  =  minusC_in_gga(x1, x2)
minusC_out_gga(x1, x2, x3)  =  minusC_out_gga(x1, x2, x3)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x1, x2, x4)
minusD_out_gga(x1, x2, x3)  =  minusD_out_gga(x1, x2, x3)
U6_ggaaa(x1, x2, x3, x4, x5, x6)  =  U6_ggaaa(x1, x2, x3, x6)
pE_in_ggaa(x1, x2, x3, x4)  =  pE_in_ggaa(x1, x2)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x1, x2, x5)
pE_out_ggaa(x1, x2, x3, x4)  =  pE_out_ggaa(x1, x2, x4)
pB_out_ggaaa(x1, x2, x3, x4, x5)  =  pB_out_ggaaa(x1, x2, x3, x5)
MINUSC_IN_GGA(x1, x2, x3)  =  MINUSC_IN_GGA(x1, x2)

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:

MINUSC_IN_GGA(s(T167), s(T168), X274) → MINUSC_IN_GGA(T167, T168, X274)

R is empty.
The argument filtering Pi contains the following mapping:
s(x1)  =  s(x1)
MINUSC_IN_GGA(x1, x2, x3)  =  MINUSC_IN_GGA(x1, x2)

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

(10) PiDPToQDPProof (SOUND 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:

MINUSC_IN_GGA(s(T167), s(T168)) → MINUSC_IN_GGA(T167, T168)

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:

  • MINUSC_IN_GGA(s(T167), s(T168)) → MINUSC_IN_GGA(T167, T168)
    The graph contains the following edges 1 > 1, 2 > 2

(13) YES

(14) Obligation:

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

DIVA_IN_GGAA(T121, T135, s(T104), T105) → PB_IN_GGAAA(T121, T135, X177, T104, T105)
PB_IN_GGAAA(T121, T135, T144, T104, T105) → U5_GGAAA(T121, T135, T144, T104, T105, minusD_in_gga(T121, T135, T144))
U5_GGAAA(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → PE_IN_GGAA(T144, T135, T104, T105)
PE_IN_GGAA(T144, T135, T104, T105) → DIVA_IN_GGAA(T144, T135, T104, T105)

The TRS R consists of the following rules:

divA_in_ggaa(0, T72, 0, 0) → divA_out_ggaa(0, T72, 0, 0)
divA_in_ggaa(T121, T135, s(T104), T105) → U1_ggaa(T121, T135, T104, T105, pB_in_ggaaa(T121, T135, X177, T104, T105))
pB_in_ggaaa(T121, T135, T144, T104, T105) → U5_ggaaa(T121, T135, T144, T104, T105, minusD_in_gga(T121, T135, T144))
minusD_in_gga(s(T154), s(T155), X255) → U3_gga(T154, T155, X255, minusC_in_gga(T154, T155, X255))
minusC_in_gga(T162, 0, T162) → minusC_out_gga(T162, 0, T162)
minusC_in_gga(s(T167), s(T168), X274) → U2_gga(T167, T168, X274, minusC_in_gga(T167, T168, X274))
U2_gga(T167, T168, X274, minusC_out_gga(T167, T168, X274)) → minusC_out_gga(s(T167), s(T168), X274)
U3_gga(T154, T155, X255, minusC_out_gga(T154, T155, X255)) → minusD_out_gga(s(T154), s(T155), X255)
U5_ggaaa(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → U6_ggaaa(T121, T135, T144, T104, T105, pE_in_ggaa(T144, T135, T104, T105))
pE_in_ggaa(T144, T135, T104, T105) → U4_ggaa(T144, T135, T104, T105, divA_in_ggaa(T144, T135, T104, T105))
divA_in_ggaa(T189, T195, T183, T189) → divA_out_ggaa(T189, T195, T183, T189)
U4_ggaa(T144, T135, T104, T105, divA_out_ggaa(T144, T135, T104, T105)) → pE_out_ggaa(T144, T135, T104, T105)
U6_ggaaa(T121, T135, T144, T104, T105, pE_out_ggaa(T144, T135, T104, T105)) → pB_out_ggaaa(T121, T135, T144, T104, T105)
U1_ggaa(T121, T135, T104, T105, pB_out_ggaaa(T121, T135, X177, T104, T105)) → divA_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divA_in_ggaa(x1, x2, x3, x4)  =  divA_in_ggaa(x1, x2)
0  =  0
divA_out_ggaa(x1, x2, x3, x4)  =  divA_out_ggaa(x1, x2, x4)
U1_ggaa(x1, x2, x3, x4, x5)  =  U1_ggaa(x1, x2, x5)
pB_in_ggaaa(x1, x2, x3, x4, x5)  =  pB_in_ggaaa(x1, x2)
U5_ggaaa(x1, x2, x3, x4, x5, x6)  =  U5_ggaaa(x1, x2, x6)
minusD_in_gga(x1, x2, x3)  =  minusD_in_gga(x1, x2)
s(x1)  =  s(x1)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
minusC_in_gga(x1, x2, x3)  =  minusC_in_gga(x1, x2)
minusC_out_gga(x1, x2, x3)  =  minusC_out_gga(x1, x2, x3)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x1, x2, x4)
minusD_out_gga(x1, x2, x3)  =  minusD_out_gga(x1, x2, x3)
U6_ggaaa(x1, x2, x3, x4, x5, x6)  =  U6_ggaaa(x1, x2, x3, x6)
pE_in_ggaa(x1, x2, x3, x4)  =  pE_in_ggaa(x1, x2)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x1, x2, x5)
pE_out_ggaa(x1, x2, x3, x4)  =  pE_out_ggaa(x1, x2, x4)
pB_out_ggaaa(x1, x2, x3, x4, x5)  =  pB_out_ggaaa(x1, x2, x3, x5)
DIVA_IN_GGAA(x1, x2, x3, x4)  =  DIVA_IN_GGAA(x1, x2)
PB_IN_GGAAA(x1, x2, x3, x4, x5)  =  PB_IN_GGAAA(x1, x2)
U5_GGAAA(x1, x2, x3, x4, x5, x6)  =  U5_GGAAA(x1, x2, x6)
PE_IN_GGAA(x1, x2, x3, x4)  =  PE_IN_GGAA(x1, x2)

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

(15) UsableRulesProof (EQUIVALENT transformation)

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

(16) Obligation:

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

DIVA_IN_GGAA(T121, T135, s(T104), T105) → PB_IN_GGAAA(T121, T135, X177, T104, T105)
PB_IN_GGAAA(T121, T135, T144, T104, T105) → U5_GGAAA(T121, T135, T144, T104, T105, minusD_in_gga(T121, T135, T144))
U5_GGAAA(T121, T135, T144, T104, T105, minusD_out_gga(T121, T135, T144)) → PE_IN_GGAA(T144, T135, T104, T105)
PE_IN_GGAA(T144, T135, T104, T105) → DIVA_IN_GGAA(T144, T135, T104, T105)

The TRS R consists of the following rules:

minusD_in_gga(s(T154), s(T155), X255) → U3_gga(T154, T155, X255, minusC_in_gga(T154, T155, X255))
U3_gga(T154, T155, X255, minusC_out_gga(T154, T155, X255)) → minusD_out_gga(s(T154), s(T155), X255)
minusC_in_gga(T162, 0, T162) → minusC_out_gga(T162, 0, T162)
minusC_in_gga(s(T167), s(T168), X274) → U2_gga(T167, T168, X274, minusC_in_gga(T167, T168, X274))
U2_gga(T167, T168, X274, minusC_out_gga(T167, T168, X274)) → minusC_out_gga(s(T167), s(T168), X274)

The argument filtering Pi contains the following mapping:
0  =  0
minusD_in_gga(x1, x2, x3)  =  minusD_in_gga(x1, x2)
s(x1)  =  s(x1)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
minusC_in_gga(x1, x2, x3)  =  minusC_in_gga(x1, x2)
minusC_out_gga(x1, x2, x3)  =  minusC_out_gga(x1, x2, x3)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x1, x2, x4)
minusD_out_gga(x1, x2, x3)  =  minusD_out_gga(x1, x2, x3)
DIVA_IN_GGAA(x1, x2, x3, x4)  =  DIVA_IN_GGAA(x1, x2)
PB_IN_GGAAA(x1, x2, x3, x4, x5)  =  PB_IN_GGAAA(x1, x2)
U5_GGAAA(x1, x2, x3, x4, x5, x6)  =  U5_GGAAA(x1, x2, x6)
PE_IN_GGAA(x1, x2, x3, x4)  =  PE_IN_GGAA(x1, x2)

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

(17) PiDPToQDPProof (SOUND transformation)

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

(18) Obligation:

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

DIVA_IN_GGAA(T121, T135) → PB_IN_GGAAA(T121, T135)
PB_IN_GGAAA(T121, T135) → U5_GGAAA(T121, T135, minusD_in_gga(T121, T135))
U5_GGAAA(T121, T135, minusD_out_gga(T121, T135, T144)) → PE_IN_GGAA(T144, T135)
PE_IN_GGAA(T144, T135) → DIVA_IN_GGAA(T144, T135)

The TRS R consists of the following rules:

minusD_in_gga(s(T154), s(T155)) → U3_gga(T154, T155, minusC_in_gga(T154, T155))
U3_gga(T154, T155, minusC_out_gga(T154, T155, X255)) → minusD_out_gga(s(T154), s(T155), X255)
minusC_in_gga(T162, 0) → minusC_out_gga(T162, 0, T162)
minusC_in_gga(s(T167), s(T168)) → U2_gga(T167, T168, minusC_in_gga(T167, T168))
U2_gga(T167, T168, minusC_out_gga(T167, T168, X274)) → minusC_out_gga(s(T167), s(T168), X274)

The set Q consists of the following terms:

minusD_in_gga(x0, x1)
U3_gga(x0, x1, x2)
minusC_in_gga(x0, x1)
U2_gga(x0, x1, x2)

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

(19) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.


PB_IN_GGAAA(T121, T135) → U5_GGAAA(T121, T135, minusD_in_gga(T121, T135))
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:

POL(0) = 0   
POL(DIVA_IN_GGAA(x1, x2)) = 1 + x1   
POL(PB_IN_GGAAA(x1, x2)) = 1 + x1   
POL(PE_IN_GGAA(x1, x2)) = 1 + x1   
POL(U2_gga(x1, x2, x3)) = x3   
POL(U3_gga(x1, x2, x3)) = 1 + x3   
POL(U5_GGAAA(x1, x2, x3)) = x3   
POL(minusC_in_gga(x1, x2)) = x1   
POL(minusC_out_gga(x1, x2, x3)) = x3   
POL(minusD_in_gga(x1, x2)) = x1   
POL(minusD_out_gga(x1, x2, x3)) = 1 + x3   
POL(s(x1)) = 1 + x1   

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

minusD_in_gga(s(T154), s(T155)) → U3_gga(T154, T155, minusC_in_gga(T154, T155))
minusC_in_gga(T162, 0) → minusC_out_gga(T162, 0, T162)
minusC_in_gga(s(T167), s(T168)) → U2_gga(T167, T168, minusC_in_gga(T167, T168))
U3_gga(T154, T155, minusC_out_gga(T154, T155, X255)) → minusD_out_gga(s(T154), s(T155), X255)
U2_gga(T167, T168, minusC_out_gga(T167, T168, X274)) → minusC_out_gga(s(T167), s(T168), X274)

(20) Obligation:

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

DIVA_IN_GGAA(T121, T135) → PB_IN_GGAAA(T121, T135)
U5_GGAAA(T121, T135, minusD_out_gga(T121, T135, T144)) → PE_IN_GGAA(T144, T135)
PE_IN_GGAA(T144, T135) → DIVA_IN_GGAA(T144, T135)

The TRS R consists of the following rules:

minusD_in_gga(s(T154), s(T155)) → U3_gga(T154, T155, minusC_in_gga(T154, T155))
U3_gga(T154, T155, minusC_out_gga(T154, T155, X255)) → minusD_out_gga(s(T154), s(T155), X255)
minusC_in_gga(T162, 0) → minusC_out_gga(T162, 0, T162)
minusC_in_gga(s(T167), s(T168)) → U2_gga(T167, T168, minusC_in_gga(T167, T168))
U2_gga(T167, T168, minusC_out_gga(T167, T168, X274)) → minusC_out_gga(s(T167), s(T168), X274)

The set Q consists of the following terms:

minusD_in_gga(x0, x1)
U3_gga(x0, x1, x2)
minusC_in_gga(x0, x1)
U2_gga(x0, x1, x2)

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

(21) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes.

(22) TRUE