(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) PrologToPrologProblemTransformerProof (SOUND transformation)

Built Prolog problem from termination graph ICLP10.

(2) Obligation:

Clauses:

minusA(T162, 0, T162).
minusA(s(T167), s(T168), X274) :- minusA(T167, T168, X274).
minusB(s(T154), s(T155), X255) :- minusA(T154, T155, X255).
divC(0, T72, 0, 0).
divC(T121, T135, s(T104), T105) :- minusB(T121, T135, X177).
divC(T121, T135, s(T104), T105) :- ','(minusB(T121, T135, T144), divC(T144, T135, T104, T105)).
divC(T189, T195, T183, T189).
divC(T207, T213, T201, T207).

Query: divC(g,g,a,a)

(3) PrologToPiTRSProof (SOUND transformation)

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

divC_in_ggaa(0, T72, 0, 0) → divC_out_ggaa(0, T72, 0, 0)
divC_in_ggaa(T121, T135, s(T104), T105) → U3_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, X177))
minusB_in_gga(s(T154), s(T155), X255) → U2_gga(T154, T155, X255, minusA_in_gga(T154, T155, X255))
minusA_in_gga(T162, 0, T162) → minusA_out_gga(T162, 0, T162)
minusA_in_gga(s(T167), s(T168), X274) → U1_gga(T167, T168, X274, minusA_in_gga(T167, T168, X274))
U1_gga(T167, T168, X274, minusA_out_gga(T167, T168, X274)) → minusA_out_gga(s(T167), s(T168), X274)
U2_gga(T154, T155, X255, minusA_out_gga(T154, T155, X255)) → minusB_out_gga(s(T154), s(T155), X255)
U3_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, X177)) → divC_out_ggaa(T121, T135, s(T104), T105)
divC_in_ggaa(T121, T135, s(T104), T105) → U4_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → U5_ggaa(T121, T135, T104, T105, divC_in_ggaa(T144, T135, T104, T105))
divC_in_ggaa(T189, T195, T183, T189) → divC_out_ggaa(T189, T195, T183, T189)
U5_ggaa(T121, T135, T104, T105, divC_out_ggaa(T144, T135, T104, T105)) → divC_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divC_in_ggaa(x1, x2, x3, x4)  =  divC_in_ggaa(x1, x2)
0  =  0
divC_out_ggaa(x1, x2, x3, x4)  =  divC_out_ggaa
U3_ggaa(x1, x2, x3, x4, x5)  =  U3_ggaa(x5)
minusB_in_gga(x1, x2, x3)  =  minusB_in_gga(x1, x2)
s(x1)  =  s(x1)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
minusA_in_gga(x1, x2, x3)  =  minusA_in_gga(x1, x2)
minusA_out_gga(x1, x2, x3)  =  minusA_out_gga(x3)
U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
minusB_out_gga(x1, x2, x3)  =  minusB_out_gga(x3)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x2, x5)
U5_ggaa(x1, x2, x3, x4, x5)  =  U5_ggaa(x5)

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog

(4) Obligation:

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

divC_in_ggaa(0, T72, 0, 0) → divC_out_ggaa(0, T72, 0, 0)
divC_in_ggaa(T121, T135, s(T104), T105) → U3_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, X177))
minusB_in_gga(s(T154), s(T155), X255) → U2_gga(T154, T155, X255, minusA_in_gga(T154, T155, X255))
minusA_in_gga(T162, 0, T162) → minusA_out_gga(T162, 0, T162)
minusA_in_gga(s(T167), s(T168), X274) → U1_gga(T167, T168, X274, minusA_in_gga(T167, T168, X274))
U1_gga(T167, T168, X274, minusA_out_gga(T167, T168, X274)) → minusA_out_gga(s(T167), s(T168), X274)
U2_gga(T154, T155, X255, minusA_out_gga(T154, T155, X255)) → minusB_out_gga(s(T154), s(T155), X255)
U3_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, X177)) → divC_out_ggaa(T121, T135, s(T104), T105)
divC_in_ggaa(T121, T135, s(T104), T105) → U4_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → U5_ggaa(T121, T135, T104, T105, divC_in_ggaa(T144, T135, T104, T105))
divC_in_ggaa(T189, T195, T183, T189) → divC_out_ggaa(T189, T195, T183, T189)
U5_ggaa(T121, T135, T104, T105, divC_out_ggaa(T144, T135, T104, T105)) → divC_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divC_in_ggaa(x1, x2, x3, x4)  =  divC_in_ggaa(x1, x2)
0  =  0
divC_out_ggaa(x1, x2, x3, x4)  =  divC_out_ggaa
U3_ggaa(x1, x2, x3, x4, x5)  =  U3_ggaa(x5)
minusB_in_gga(x1, x2, x3)  =  minusB_in_gga(x1, x2)
s(x1)  =  s(x1)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
minusA_in_gga(x1, x2, x3)  =  minusA_in_gga(x1, x2)
minusA_out_gga(x1, x2, x3)  =  minusA_out_gga(x3)
U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
minusB_out_gga(x1, x2, x3)  =  minusB_out_gga(x3)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x2, x5)
U5_ggaa(x1, x2, x3, x4, x5)  =  U5_ggaa(x5)

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

DIVC_IN_GGAA(T121, T135, s(T104), T105) → U3_GGAA(T121, T135, T104, T105, minusB_in_gga(T121, T135, X177))
DIVC_IN_GGAA(T121, T135, s(T104), T105) → MINUSB_IN_GGA(T121, T135, X177)
MINUSB_IN_GGA(s(T154), s(T155), X255) → U2_GGA(T154, T155, X255, minusA_in_gga(T154, T155, X255))
MINUSB_IN_GGA(s(T154), s(T155), X255) → MINUSA_IN_GGA(T154, T155, X255)
MINUSA_IN_GGA(s(T167), s(T168), X274) → U1_GGA(T167, T168, X274, minusA_in_gga(T167, T168, X274))
MINUSA_IN_GGA(s(T167), s(T168), X274) → MINUSA_IN_GGA(T167, T168, X274)
DIVC_IN_GGAA(T121, T135, s(T104), T105) → U4_GGAA(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_GGAA(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → U5_GGAA(T121, T135, T104, T105, divC_in_ggaa(T144, T135, T104, T105))
U4_GGAA(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → DIVC_IN_GGAA(T144, T135, T104, T105)

The TRS R consists of the following rules:

divC_in_ggaa(0, T72, 0, 0) → divC_out_ggaa(0, T72, 0, 0)
divC_in_ggaa(T121, T135, s(T104), T105) → U3_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, X177))
minusB_in_gga(s(T154), s(T155), X255) → U2_gga(T154, T155, X255, minusA_in_gga(T154, T155, X255))
minusA_in_gga(T162, 0, T162) → minusA_out_gga(T162, 0, T162)
minusA_in_gga(s(T167), s(T168), X274) → U1_gga(T167, T168, X274, minusA_in_gga(T167, T168, X274))
U1_gga(T167, T168, X274, minusA_out_gga(T167, T168, X274)) → minusA_out_gga(s(T167), s(T168), X274)
U2_gga(T154, T155, X255, minusA_out_gga(T154, T155, X255)) → minusB_out_gga(s(T154), s(T155), X255)
U3_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, X177)) → divC_out_ggaa(T121, T135, s(T104), T105)
divC_in_ggaa(T121, T135, s(T104), T105) → U4_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → U5_ggaa(T121, T135, T104, T105, divC_in_ggaa(T144, T135, T104, T105))
divC_in_ggaa(T189, T195, T183, T189) → divC_out_ggaa(T189, T195, T183, T189)
U5_ggaa(T121, T135, T104, T105, divC_out_ggaa(T144, T135, T104, T105)) → divC_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divC_in_ggaa(x1, x2, x3, x4)  =  divC_in_ggaa(x1, x2)
0  =  0
divC_out_ggaa(x1, x2, x3, x4)  =  divC_out_ggaa
U3_ggaa(x1, x2, x3, x4, x5)  =  U3_ggaa(x5)
minusB_in_gga(x1, x2, x3)  =  minusB_in_gga(x1, x2)
s(x1)  =  s(x1)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
minusA_in_gga(x1, x2, x3)  =  minusA_in_gga(x1, x2)
minusA_out_gga(x1, x2, x3)  =  minusA_out_gga(x3)
U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
minusB_out_gga(x1, x2, x3)  =  minusB_out_gga(x3)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x2, x5)
U5_ggaa(x1, x2, x3, x4, x5)  =  U5_ggaa(x5)
DIVC_IN_GGAA(x1, x2, x3, x4)  =  DIVC_IN_GGAA(x1, x2)
U3_GGAA(x1, x2, x3, x4, x5)  =  U3_GGAA(x5)
MINUSB_IN_GGA(x1, x2, x3)  =  MINUSB_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4)  =  U2_GGA(x4)
MINUSA_IN_GGA(x1, x2, x3)  =  MINUSA_IN_GGA(x1, x2)
U1_GGA(x1, x2, x3, x4)  =  U1_GGA(x4)
U4_GGAA(x1, x2, x3, x4, x5)  =  U4_GGAA(x2, x5)
U5_GGAA(x1, x2, x3, x4, x5)  =  U5_GGAA(x5)

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

(6) Obligation:

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

DIVC_IN_GGAA(T121, T135, s(T104), T105) → U3_GGAA(T121, T135, T104, T105, minusB_in_gga(T121, T135, X177))
DIVC_IN_GGAA(T121, T135, s(T104), T105) → MINUSB_IN_GGA(T121, T135, X177)
MINUSB_IN_GGA(s(T154), s(T155), X255) → U2_GGA(T154, T155, X255, minusA_in_gga(T154, T155, X255))
MINUSB_IN_GGA(s(T154), s(T155), X255) → MINUSA_IN_GGA(T154, T155, X255)
MINUSA_IN_GGA(s(T167), s(T168), X274) → U1_GGA(T167, T168, X274, minusA_in_gga(T167, T168, X274))
MINUSA_IN_GGA(s(T167), s(T168), X274) → MINUSA_IN_GGA(T167, T168, X274)
DIVC_IN_GGAA(T121, T135, s(T104), T105) → U4_GGAA(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_GGAA(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → U5_GGAA(T121, T135, T104, T105, divC_in_ggaa(T144, T135, T104, T105))
U4_GGAA(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → DIVC_IN_GGAA(T144, T135, T104, T105)

The TRS R consists of the following rules:

divC_in_ggaa(0, T72, 0, 0) → divC_out_ggaa(0, T72, 0, 0)
divC_in_ggaa(T121, T135, s(T104), T105) → U3_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, X177))
minusB_in_gga(s(T154), s(T155), X255) → U2_gga(T154, T155, X255, minusA_in_gga(T154, T155, X255))
minusA_in_gga(T162, 0, T162) → minusA_out_gga(T162, 0, T162)
minusA_in_gga(s(T167), s(T168), X274) → U1_gga(T167, T168, X274, minusA_in_gga(T167, T168, X274))
U1_gga(T167, T168, X274, minusA_out_gga(T167, T168, X274)) → minusA_out_gga(s(T167), s(T168), X274)
U2_gga(T154, T155, X255, minusA_out_gga(T154, T155, X255)) → minusB_out_gga(s(T154), s(T155), X255)
U3_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, X177)) → divC_out_ggaa(T121, T135, s(T104), T105)
divC_in_ggaa(T121, T135, s(T104), T105) → U4_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → U5_ggaa(T121, T135, T104, T105, divC_in_ggaa(T144, T135, T104, T105))
divC_in_ggaa(T189, T195, T183, T189) → divC_out_ggaa(T189, T195, T183, T189)
U5_ggaa(T121, T135, T104, T105, divC_out_ggaa(T144, T135, T104, T105)) → divC_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divC_in_ggaa(x1, x2, x3, x4)  =  divC_in_ggaa(x1, x2)
0  =  0
divC_out_ggaa(x1, x2, x3, x4)  =  divC_out_ggaa
U3_ggaa(x1, x2, x3, x4, x5)  =  U3_ggaa(x5)
minusB_in_gga(x1, x2, x3)  =  minusB_in_gga(x1, x2)
s(x1)  =  s(x1)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
minusA_in_gga(x1, x2, x3)  =  minusA_in_gga(x1, x2)
minusA_out_gga(x1, x2, x3)  =  minusA_out_gga(x3)
U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
minusB_out_gga(x1, x2, x3)  =  minusB_out_gga(x3)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x2, x5)
U5_ggaa(x1, x2, x3, x4, x5)  =  U5_ggaa(x5)
DIVC_IN_GGAA(x1, x2, x3, x4)  =  DIVC_IN_GGAA(x1, x2)
U3_GGAA(x1, x2, x3, x4, x5)  =  U3_GGAA(x5)
MINUSB_IN_GGA(x1, x2, x3)  =  MINUSB_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4)  =  U2_GGA(x4)
MINUSA_IN_GGA(x1, x2, x3)  =  MINUSA_IN_GGA(x1, x2)
U1_GGA(x1, x2, x3, x4)  =  U1_GGA(x4)
U4_GGAA(x1, x2, x3, x4, x5)  =  U4_GGAA(x2, x5)
U5_GGAA(x1, x2, x3, x4, x5)  =  U5_GGAA(x5)

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

(7) DependencyGraphProof (EQUIVALENT transformation)

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

(8) Complex Obligation (AND)

(9) Obligation:

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

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

The TRS R consists of the following rules:

divC_in_ggaa(0, T72, 0, 0) → divC_out_ggaa(0, T72, 0, 0)
divC_in_ggaa(T121, T135, s(T104), T105) → U3_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, X177))
minusB_in_gga(s(T154), s(T155), X255) → U2_gga(T154, T155, X255, minusA_in_gga(T154, T155, X255))
minusA_in_gga(T162, 0, T162) → minusA_out_gga(T162, 0, T162)
minusA_in_gga(s(T167), s(T168), X274) → U1_gga(T167, T168, X274, minusA_in_gga(T167, T168, X274))
U1_gga(T167, T168, X274, minusA_out_gga(T167, T168, X274)) → minusA_out_gga(s(T167), s(T168), X274)
U2_gga(T154, T155, X255, minusA_out_gga(T154, T155, X255)) → minusB_out_gga(s(T154), s(T155), X255)
U3_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, X177)) → divC_out_ggaa(T121, T135, s(T104), T105)
divC_in_ggaa(T121, T135, s(T104), T105) → U4_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → U5_ggaa(T121, T135, T104, T105, divC_in_ggaa(T144, T135, T104, T105))
divC_in_ggaa(T189, T195, T183, T189) → divC_out_ggaa(T189, T195, T183, T189)
U5_ggaa(T121, T135, T104, T105, divC_out_ggaa(T144, T135, T104, T105)) → divC_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divC_in_ggaa(x1, x2, x3, x4)  =  divC_in_ggaa(x1, x2)
0  =  0
divC_out_ggaa(x1, x2, x3, x4)  =  divC_out_ggaa
U3_ggaa(x1, x2, x3, x4, x5)  =  U3_ggaa(x5)
minusB_in_gga(x1, x2, x3)  =  minusB_in_gga(x1, x2)
s(x1)  =  s(x1)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
minusA_in_gga(x1, x2, x3)  =  minusA_in_gga(x1, x2)
minusA_out_gga(x1, x2, x3)  =  minusA_out_gga(x3)
U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
minusB_out_gga(x1, x2, x3)  =  minusB_out_gga(x3)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x2, x5)
U5_ggaa(x1, x2, x3, x4, x5)  =  U5_ggaa(x5)
MINUSA_IN_GGA(x1, x2, x3)  =  MINUSA_IN_GGA(x1, x2)

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

(10) UsableRulesProof (EQUIVALENT transformation)

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

(11) Obligation:

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

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

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

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

(12) PiDPToQDPProof (SOUND transformation)

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

(13) Obligation:

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

MINUSA_IN_GGA(s(T167), s(T168)) → MINUSA_IN_GGA(T167, T168)

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

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

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

(15) YES

(16) Obligation:

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

DIVC_IN_GGAA(T121, T135, s(T104), T105) → U4_GGAA(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_GGAA(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → DIVC_IN_GGAA(T144, T135, T104, T105)

The TRS R consists of the following rules:

divC_in_ggaa(0, T72, 0, 0) → divC_out_ggaa(0, T72, 0, 0)
divC_in_ggaa(T121, T135, s(T104), T105) → U3_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, X177))
minusB_in_gga(s(T154), s(T155), X255) → U2_gga(T154, T155, X255, minusA_in_gga(T154, T155, X255))
minusA_in_gga(T162, 0, T162) → minusA_out_gga(T162, 0, T162)
minusA_in_gga(s(T167), s(T168), X274) → U1_gga(T167, T168, X274, minusA_in_gga(T167, T168, X274))
U1_gga(T167, T168, X274, minusA_out_gga(T167, T168, X274)) → minusA_out_gga(s(T167), s(T168), X274)
U2_gga(T154, T155, X255, minusA_out_gga(T154, T155, X255)) → minusB_out_gga(s(T154), s(T155), X255)
U3_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, X177)) → divC_out_ggaa(T121, T135, s(T104), T105)
divC_in_ggaa(T121, T135, s(T104), T105) → U4_ggaa(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_ggaa(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → U5_ggaa(T121, T135, T104, T105, divC_in_ggaa(T144, T135, T104, T105))
divC_in_ggaa(T189, T195, T183, T189) → divC_out_ggaa(T189, T195, T183, T189)
U5_ggaa(T121, T135, T104, T105, divC_out_ggaa(T144, T135, T104, T105)) → divC_out_ggaa(T121, T135, s(T104), T105)

The argument filtering Pi contains the following mapping:
divC_in_ggaa(x1, x2, x3, x4)  =  divC_in_ggaa(x1, x2)
0  =  0
divC_out_ggaa(x1, x2, x3, x4)  =  divC_out_ggaa
U3_ggaa(x1, x2, x3, x4, x5)  =  U3_ggaa(x5)
minusB_in_gga(x1, x2, x3)  =  minusB_in_gga(x1, x2)
s(x1)  =  s(x1)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
minusA_in_gga(x1, x2, x3)  =  minusA_in_gga(x1, x2)
minusA_out_gga(x1, x2, x3)  =  minusA_out_gga(x3)
U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
minusB_out_gga(x1, x2, x3)  =  minusB_out_gga(x3)
U4_ggaa(x1, x2, x3, x4, x5)  =  U4_ggaa(x2, x5)
U5_ggaa(x1, x2, x3, x4, x5)  =  U5_ggaa(x5)
DIVC_IN_GGAA(x1, x2, x3, x4)  =  DIVC_IN_GGAA(x1, x2)
U4_GGAA(x1, x2, x3, x4, x5)  =  U4_GGAA(x2, x5)

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

(17) UsableRulesProof (EQUIVALENT transformation)

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

(18) Obligation:

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

DIVC_IN_GGAA(T121, T135, s(T104), T105) → U4_GGAA(T121, T135, T104, T105, minusB_in_gga(T121, T135, T144))
U4_GGAA(T121, T135, T104, T105, minusB_out_gga(T121, T135, T144)) → DIVC_IN_GGAA(T144, T135, T104, T105)

The TRS R consists of the following rules:

minusB_in_gga(s(T154), s(T155), X255) → U2_gga(T154, T155, X255, minusA_in_gga(T154, T155, X255))
U2_gga(T154, T155, X255, minusA_out_gga(T154, T155, X255)) → minusB_out_gga(s(T154), s(T155), X255)
minusA_in_gga(T162, 0, T162) → minusA_out_gga(T162, 0, T162)
minusA_in_gga(s(T167), s(T168), X274) → U1_gga(T167, T168, X274, minusA_in_gga(T167, T168, X274))
U1_gga(T167, T168, X274, minusA_out_gga(T167, T168, X274)) → minusA_out_gga(s(T167), s(T168), X274)

The argument filtering Pi contains the following mapping:
0  =  0
minusB_in_gga(x1, x2, x3)  =  minusB_in_gga(x1, x2)
s(x1)  =  s(x1)
U2_gga(x1, x2, x3, x4)  =  U2_gga(x4)
minusA_in_gga(x1, x2, x3)  =  minusA_in_gga(x1, x2)
minusA_out_gga(x1, x2, x3)  =  minusA_out_gga(x3)
U1_gga(x1, x2, x3, x4)  =  U1_gga(x4)
minusB_out_gga(x1, x2, x3)  =  minusB_out_gga(x3)
DIVC_IN_GGAA(x1, x2, x3, x4)  =  DIVC_IN_GGAA(x1, x2)
U4_GGAA(x1, x2, x3, x4, x5)  =  U4_GGAA(x2, x5)

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

(19) PiDPToQDPProof (SOUND transformation)

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

(20) Obligation:

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

DIVC_IN_GGAA(T121, T135) → U4_GGAA(T135, minusB_in_gga(T121, T135))
U4_GGAA(T135, minusB_out_gga(T144)) → DIVC_IN_GGAA(T144, T135)

The TRS R consists of the following rules:

minusB_in_gga(s(T154), s(T155)) → U2_gga(minusA_in_gga(T154, T155))
U2_gga(minusA_out_gga(X255)) → minusB_out_gga(X255)
minusA_in_gga(T162, 0) → minusA_out_gga(T162)
minusA_in_gga(s(T167), s(T168)) → U1_gga(minusA_in_gga(T167, T168))
U1_gga(minusA_out_gga(X274)) → minusA_out_gga(X274)

The set Q consists of the following terms:

minusB_in_gga(x0, x1)
U2_gga(x0)
minusA_in_gga(x0, x1)
U1_gga(x0)

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

(21) QDPOrderProof (EQUIVALENT transformation)

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


The following pairs can be oriented strictly and are deleted.


U4_GGAA(T135, minusB_out_gga(T144)) → DIVC_IN_GGAA(T144, T135)
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( U4_GGAA(x1, x2) ) = 2x2 + 2


POL( minusB_in_gga(x1, x2) ) = x1


POL( s(x1) ) = x1 + 2


POL( U2_gga(x1) ) = x1


POL( minusA_in_gga(x1, x2) ) = x1 + 2


POL( 0 ) = 2


POL( minusA_out_gga(x1) ) = x1 + 2


POL( U1_gga(x1) ) = x1 + 1


POL( minusB_out_gga(x1) ) = x1 + 2


POL( DIVC_IN_GGAA(x1, x2) ) = 2x1 + 2



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

minusB_in_gga(s(T154), s(T155)) → U2_gga(minusA_in_gga(T154, T155))
minusA_in_gga(T162, 0) → minusA_out_gga(T162)
minusA_in_gga(s(T167), s(T168)) → U1_gga(minusA_in_gga(T167, T168))
U2_gga(minusA_out_gga(X255)) → minusB_out_gga(X255)
U1_gga(minusA_out_gga(X274)) → minusA_out_gga(X274)

(22) Obligation:

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

DIVC_IN_GGAA(T121, T135) → U4_GGAA(T135, minusB_in_gga(T121, T135))

The TRS R consists of the following rules:

minusB_in_gga(s(T154), s(T155)) → U2_gga(minusA_in_gga(T154, T155))
U2_gga(minusA_out_gga(X255)) → minusB_out_gga(X255)
minusA_in_gga(T162, 0) → minusA_out_gga(T162)
minusA_in_gga(s(T167), s(T168)) → U1_gga(minusA_in_gga(T167, T168))
U1_gga(minusA_out_gga(X274)) → minusA_out_gga(X274)

The set Q consists of the following terms:

minusB_in_gga(x0, x1)
U2_gga(x0)
minusA_in_gga(x0, x1)
U1_gga(x0)

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

(23) DependencyGraphProof (EQUIVALENT transformation)

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

(24) TRUE