(0) Obligation:

Clauses:

ackermann(0, N, s(N)).
ackermann(s(M), 0, Res) :- ackermann(M, s(0), Res).
ackermann(s(M), s(N), Res) :- ','(ackermann(s(M), N, Res1), ackermann(M, Res1, Res)).

Query: ackermann(g,g,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:

ackermannA_in_gga(0, T5, s(T5)) → ackermannA_out_gga(0, T5, s(T5))
ackermannA_in_gga(s(0), 0, s(s(0))) → ackermannA_out_gga(s(0), 0, s(s(0)))
ackermannA_in_gga(s(s(T20)), 0, T22) → U1_gga(T20, T22, pB_in_gaa(T20, X36, T22))
pB_in_gaa(T20, T23, T22) → U8_gaa(T20, T23, T22, ackermannE_in_ga(T20, T23))
ackermannE_in_ga(T28, X60) → U4_ga(T28, X60, ackermannF_in_ga(T28, X60))
ackermannF_in_ga(0, s(s(0))) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32), X83) → U5_ga(T32, X83, pG_in_gaa(T32, X82, X83))
pG_in_gaa(T32, T33, X83) → U10_gaa(T32, T33, X83, ackermannE_in_ga(T32, T33))
U10_gaa(T32, T33, X83, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, X83, ackermannH_in_gga(T32, T33, X83))
ackermannH_in_gga(0, T40, s(T40)) → ackermannH_out_gga(0, T40, s(T40))
ackermannH_in_gga(s(T45), 0, X109) → U6_gga(T45, X109, ackermannF_in_ga(T45, X109))
U6_gga(T45, X109, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
ackermannH_in_gga(s(T50), s(T51), X125) → U7_gga(T50, T51, X125, pI_in_ggaa(T50, T51, X124, X125))
pI_in_ggaa(T50, T51, T52, X125) → U12_ggaa(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
U12_ggaa(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, X125, ackermannH_in_gga(T50, T52, X125))
U13_ggaa(T50, T51, T52, X125, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U7_gga(T50, T51, X125, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
U11_gaa(T32, T33, X83, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)
U5_ga(T32, X83, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U4_ga(T28, X60, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U8_gaa(T20, T23, T22, ackermannE_out_ga(T20, T23)) → U9_gaa(T20, T23, T22, ackermannA_in_gga(T20, T23, T22))
ackermannA_in_gga(s(T70), s(0), T65) → U2_gga(T70, T65, pC_in_gaa(T70, X162, T65))
pC_in_gaa(T70, T71, T65) → U14_gaa(T70, T71, T65, ackermannF_in_ga(T70, T71))
U14_gaa(T70, T71, T65, ackermannF_out_ga(T70, T71)) → U15_gaa(T70, T71, T65, ackermannA_in_gga(T70, T71, T65))
ackermannA_in_gga(s(T78), s(s(T79)), T65) → U3_gga(T78, T79, T65, pD_in_ggaaa(T78, T79, X181, X182, T65))
pD_in_ggaaa(T78, T79, T80, X182, T65) → U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_in_gga(s(T78), T79, T80))
U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → U17_ggaaa(T78, T79, T80, X182, T65, pJ_in_ggaa(T78, T80, X182, T65))
pJ_in_ggaa(T78, T80, T83, T65) → U18_ggaa(T78, T80, T83, T65, ackermannH_in_gga(T78, T80, T83))
U18_ggaa(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → U19_ggaa(T78, T80, T83, T65, ackermannA_in_gga(T78, T83, T65))
U19_ggaa(T78, T80, T83, T65, ackermannA_out_gga(T78, T83, T65)) → pJ_out_ggaa(T78, T80, T83, T65)
U17_ggaaa(T78, T79, T80, X182, T65, pJ_out_ggaa(T78, T80, X182, T65)) → pD_out_ggaaa(T78, T79, T80, X182, T65)
U3_gga(T78, T79, T65, pD_out_ggaaa(T78, T79, X181, X182, T65)) → ackermannA_out_gga(s(T78), s(s(T79)), T65)
U15_gaa(T70, T71, T65, ackermannA_out_gga(T70, T71, T65)) → pC_out_gaa(T70, T71, T65)
U2_gga(T70, T65, pC_out_gaa(T70, X162, T65)) → ackermannA_out_gga(s(T70), s(0), T65)
U9_gaa(T20, T23, T22, ackermannA_out_gga(T20, T23, T22)) → pB_out_gaa(T20, T23, T22)
U1_gga(T20, T22, pB_out_gaa(T20, X36, T22)) → ackermannA_out_gga(s(s(T20)), 0, T22)

The argument filtering Pi contains the following mapping:
ackermannA_in_gga(x1, x2, x3)  =  ackermannA_in_gga(x1, x2)
0  =  0
ackermannA_out_gga(x1, x2, x3)  =  ackermannA_out_gga(x1, x2, x3)
s(x1)  =  s(x1)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x3)
pB_in_gaa(x1, x2, x3)  =  pB_in_gaa(x1)
U8_gaa(x1, x2, x3, x4)  =  U8_gaa(x1, x4)
ackermannE_in_ga(x1, x2)  =  ackermannE_in_ga(x1)
U4_ga(x1, x2, x3)  =  U4_ga(x1, x3)
ackermannF_in_ga(x1, x2)  =  ackermannF_in_ga(x1)
ackermannF_out_ga(x1, x2)  =  ackermannF_out_ga(x1, x2)
U5_ga(x1, x2, x3)  =  U5_ga(x1, x3)
pG_in_gaa(x1, x2, x3)  =  pG_in_gaa(x1)
U10_gaa(x1, x2, x3, x4)  =  U10_gaa(x1, x4)
ackermannE_out_ga(x1, x2)  =  ackermannE_out_ga(x1, x2)
U11_gaa(x1, x2, x3, x4)  =  U11_gaa(x1, x2, x4)
ackermannH_in_gga(x1, x2, x3)  =  ackermannH_in_gga(x1, x2)
ackermannH_out_gga(x1, x2, x3)  =  ackermannH_out_gga(x1, x2, x3)
U6_gga(x1, x2, x3)  =  U6_gga(x1, x3)
U7_gga(x1, x2, x3, x4)  =  U7_gga(x1, x2, x4)
pI_in_ggaa(x1, x2, x3, x4)  =  pI_in_ggaa(x1, x2)
U12_ggaa(x1, x2, x3, x4, x5)  =  U12_ggaa(x1, x2, x5)
U13_ggaa(x1, x2, x3, x4, x5)  =  U13_ggaa(x1, x2, x3, x5)
pI_out_ggaa(x1, x2, x3, x4)  =  pI_out_ggaa(x1, x2, x3, x4)
pG_out_gaa(x1, x2, x3)  =  pG_out_gaa(x1, x2, x3)
U9_gaa(x1, x2, x3, x4)  =  U9_gaa(x1, x2, x4)
U2_gga(x1, x2, x3)  =  U2_gga(x1, x3)
pC_in_gaa(x1, x2, x3)  =  pC_in_gaa(x1)
U14_gaa(x1, x2, x3, x4)  =  U14_gaa(x1, x4)
U15_gaa(x1, x2, x3, x4)  =  U15_gaa(x1, x2, x4)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
pD_in_ggaaa(x1, x2, x3, x4, x5)  =  pD_in_ggaaa(x1, x2)
U16_ggaaa(x1, x2, x3, x4, x5, x6)  =  U16_ggaaa(x1, x2, x6)
U17_ggaaa(x1, x2, x3, x4, x5, x6)  =  U17_ggaaa(x1, x2, x3, x6)
pJ_in_ggaa(x1, x2, x3, x4)  =  pJ_in_ggaa(x1, x2)
U18_ggaa(x1, x2, x3, x4, x5)  =  U18_ggaa(x1, x2, x5)
U19_ggaa(x1, x2, x3, x4, x5)  =  U19_ggaa(x1, x2, x3, x5)
pJ_out_ggaa(x1, x2, x3, x4)  =  pJ_out_ggaa(x1, x2, x3, x4)
pD_out_ggaaa(x1, x2, x3, x4, x5)  =  pD_out_ggaaa(x1, x2, x3, x4, x5)
pC_out_gaa(x1, x2, x3)  =  pC_out_gaa(x1, x2, x3)
pB_out_gaa(x1, x2, x3)  =  pB_out_gaa(x1, x2, x3)

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

ACKERMANNA_IN_GGA(s(s(T20)), 0, T22) → U1_GGA(T20, T22, pB_in_gaa(T20, X36, T22))
ACKERMANNA_IN_GGA(s(s(T20)), 0, T22) → PB_IN_GAA(T20, X36, T22)
PB_IN_GAA(T20, T23, T22) → U8_GAA(T20, T23, T22, ackermannE_in_ga(T20, T23))
PB_IN_GAA(T20, T23, T22) → ACKERMANNE_IN_GA(T20, T23)
ACKERMANNE_IN_GA(T28, X60) → U4_GA(T28, X60, ackermannF_in_ga(T28, X60))
ACKERMANNE_IN_GA(T28, X60) → ACKERMANNF_IN_GA(T28, X60)
ACKERMANNF_IN_GA(s(T32), X83) → U5_GA(T32, X83, pG_in_gaa(T32, X82, X83))
ACKERMANNF_IN_GA(s(T32), X83) → PG_IN_GAA(T32, X82, X83)
PG_IN_GAA(T32, T33, X83) → U10_GAA(T32, T33, X83, ackermannE_in_ga(T32, T33))
PG_IN_GAA(T32, T33, X83) → ACKERMANNE_IN_GA(T32, T33)
U10_GAA(T32, T33, X83, ackermannE_out_ga(T32, T33)) → U11_GAA(T32, T33, X83, ackermannH_in_gga(T32, T33, X83))
U10_GAA(T32, T33, X83, ackermannE_out_ga(T32, T33)) → ACKERMANNH_IN_GGA(T32, T33, X83)
ACKERMANNH_IN_GGA(s(T45), 0, X109) → U6_GGA(T45, X109, ackermannF_in_ga(T45, X109))
ACKERMANNH_IN_GGA(s(T45), 0, X109) → ACKERMANNF_IN_GA(T45, X109)
ACKERMANNH_IN_GGA(s(T50), s(T51), X125) → U7_GGA(T50, T51, X125, pI_in_ggaa(T50, T51, X124, X125))
ACKERMANNH_IN_GGA(s(T50), s(T51), X125) → PI_IN_GGAA(T50, T51, X124, X125)
PI_IN_GGAA(T50, T51, T52, X125) → U12_GGAA(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
PI_IN_GGAA(T50, T51, T52, X125) → ACKERMANNH_IN_GGA(s(T50), T51, T52)
U12_GGAA(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → U13_GGAA(T50, T51, T52, X125, ackermannH_in_gga(T50, T52, X125))
U12_GGAA(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → ACKERMANNH_IN_GGA(T50, T52, X125)
U8_GAA(T20, T23, T22, ackermannE_out_ga(T20, T23)) → U9_GAA(T20, T23, T22, ackermannA_in_gga(T20, T23, T22))
U8_GAA(T20, T23, T22, ackermannE_out_ga(T20, T23)) → ACKERMANNA_IN_GGA(T20, T23, T22)
ACKERMANNA_IN_GGA(s(T70), s(0), T65) → U2_GGA(T70, T65, pC_in_gaa(T70, X162, T65))
ACKERMANNA_IN_GGA(s(T70), s(0), T65) → PC_IN_GAA(T70, X162, T65)
PC_IN_GAA(T70, T71, T65) → U14_GAA(T70, T71, T65, ackermannF_in_ga(T70, T71))
PC_IN_GAA(T70, T71, T65) → ACKERMANNF_IN_GA(T70, T71)
U14_GAA(T70, T71, T65, ackermannF_out_ga(T70, T71)) → U15_GAA(T70, T71, T65, ackermannA_in_gga(T70, T71, T65))
U14_GAA(T70, T71, T65, ackermannF_out_ga(T70, T71)) → ACKERMANNA_IN_GGA(T70, T71, T65)
ACKERMANNA_IN_GGA(s(T78), s(s(T79)), T65) → U3_GGA(T78, T79, T65, pD_in_ggaaa(T78, T79, X181, X182, T65))
ACKERMANNA_IN_GGA(s(T78), s(s(T79)), T65) → PD_IN_GGAAA(T78, T79, X181, X182, T65)
PD_IN_GGAAA(T78, T79, T80, X182, T65) → U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_in_gga(s(T78), T79, T80))
PD_IN_GGAAA(T78, T79, T80, X182, T65) → ACKERMANNH_IN_GGA(s(T78), T79, T80)
U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → U17_GGAAA(T78, T79, T80, X182, T65, pJ_in_ggaa(T78, T80, X182, T65))
U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → PJ_IN_GGAA(T78, T80, X182, T65)
PJ_IN_GGAA(T78, T80, T83, T65) → U18_GGAA(T78, T80, T83, T65, ackermannH_in_gga(T78, T80, T83))
PJ_IN_GGAA(T78, T80, T83, T65) → ACKERMANNH_IN_GGA(T78, T80, T83)
U18_GGAA(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → U19_GGAA(T78, T80, T83, T65, ackermannA_in_gga(T78, T83, T65))
U18_GGAA(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → ACKERMANNA_IN_GGA(T78, T83, T65)

The TRS R consists of the following rules:

ackermannA_in_gga(0, T5, s(T5)) → ackermannA_out_gga(0, T5, s(T5))
ackermannA_in_gga(s(0), 0, s(s(0))) → ackermannA_out_gga(s(0), 0, s(s(0)))
ackermannA_in_gga(s(s(T20)), 0, T22) → U1_gga(T20, T22, pB_in_gaa(T20, X36, T22))
pB_in_gaa(T20, T23, T22) → U8_gaa(T20, T23, T22, ackermannE_in_ga(T20, T23))
ackermannE_in_ga(T28, X60) → U4_ga(T28, X60, ackermannF_in_ga(T28, X60))
ackermannF_in_ga(0, s(s(0))) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32), X83) → U5_ga(T32, X83, pG_in_gaa(T32, X82, X83))
pG_in_gaa(T32, T33, X83) → U10_gaa(T32, T33, X83, ackermannE_in_ga(T32, T33))
U10_gaa(T32, T33, X83, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, X83, ackermannH_in_gga(T32, T33, X83))
ackermannH_in_gga(0, T40, s(T40)) → ackermannH_out_gga(0, T40, s(T40))
ackermannH_in_gga(s(T45), 0, X109) → U6_gga(T45, X109, ackermannF_in_ga(T45, X109))
U6_gga(T45, X109, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
ackermannH_in_gga(s(T50), s(T51), X125) → U7_gga(T50, T51, X125, pI_in_ggaa(T50, T51, X124, X125))
pI_in_ggaa(T50, T51, T52, X125) → U12_ggaa(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
U12_ggaa(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, X125, ackermannH_in_gga(T50, T52, X125))
U13_ggaa(T50, T51, T52, X125, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U7_gga(T50, T51, X125, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
U11_gaa(T32, T33, X83, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)
U5_ga(T32, X83, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U4_ga(T28, X60, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U8_gaa(T20, T23, T22, ackermannE_out_ga(T20, T23)) → U9_gaa(T20, T23, T22, ackermannA_in_gga(T20, T23, T22))
ackermannA_in_gga(s(T70), s(0), T65) → U2_gga(T70, T65, pC_in_gaa(T70, X162, T65))
pC_in_gaa(T70, T71, T65) → U14_gaa(T70, T71, T65, ackermannF_in_ga(T70, T71))
U14_gaa(T70, T71, T65, ackermannF_out_ga(T70, T71)) → U15_gaa(T70, T71, T65, ackermannA_in_gga(T70, T71, T65))
ackermannA_in_gga(s(T78), s(s(T79)), T65) → U3_gga(T78, T79, T65, pD_in_ggaaa(T78, T79, X181, X182, T65))
pD_in_ggaaa(T78, T79, T80, X182, T65) → U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_in_gga(s(T78), T79, T80))
U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → U17_ggaaa(T78, T79, T80, X182, T65, pJ_in_ggaa(T78, T80, X182, T65))
pJ_in_ggaa(T78, T80, T83, T65) → U18_ggaa(T78, T80, T83, T65, ackermannH_in_gga(T78, T80, T83))
U18_ggaa(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → U19_ggaa(T78, T80, T83, T65, ackermannA_in_gga(T78, T83, T65))
U19_ggaa(T78, T80, T83, T65, ackermannA_out_gga(T78, T83, T65)) → pJ_out_ggaa(T78, T80, T83, T65)
U17_ggaaa(T78, T79, T80, X182, T65, pJ_out_ggaa(T78, T80, X182, T65)) → pD_out_ggaaa(T78, T79, T80, X182, T65)
U3_gga(T78, T79, T65, pD_out_ggaaa(T78, T79, X181, X182, T65)) → ackermannA_out_gga(s(T78), s(s(T79)), T65)
U15_gaa(T70, T71, T65, ackermannA_out_gga(T70, T71, T65)) → pC_out_gaa(T70, T71, T65)
U2_gga(T70, T65, pC_out_gaa(T70, X162, T65)) → ackermannA_out_gga(s(T70), s(0), T65)
U9_gaa(T20, T23, T22, ackermannA_out_gga(T20, T23, T22)) → pB_out_gaa(T20, T23, T22)
U1_gga(T20, T22, pB_out_gaa(T20, X36, T22)) → ackermannA_out_gga(s(s(T20)), 0, T22)

The argument filtering Pi contains the following mapping:
ackermannA_in_gga(x1, x2, x3)  =  ackermannA_in_gga(x1, x2)
0  =  0
ackermannA_out_gga(x1, x2, x3)  =  ackermannA_out_gga(x1, x2, x3)
s(x1)  =  s(x1)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x3)
pB_in_gaa(x1, x2, x3)  =  pB_in_gaa(x1)
U8_gaa(x1, x2, x3, x4)  =  U8_gaa(x1, x4)
ackermannE_in_ga(x1, x2)  =  ackermannE_in_ga(x1)
U4_ga(x1, x2, x3)  =  U4_ga(x1, x3)
ackermannF_in_ga(x1, x2)  =  ackermannF_in_ga(x1)
ackermannF_out_ga(x1, x2)  =  ackermannF_out_ga(x1, x2)
U5_ga(x1, x2, x3)  =  U5_ga(x1, x3)
pG_in_gaa(x1, x2, x3)  =  pG_in_gaa(x1)
U10_gaa(x1, x2, x3, x4)  =  U10_gaa(x1, x4)
ackermannE_out_ga(x1, x2)  =  ackermannE_out_ga(x1, x2)
U11_gaa(x1, x2, x3, x4)  =  U11_gaa(x1, x2, x4)
ackermannH_in_gga(x1, x2, x3)  =  ackermannH_in_gga(x1, x2)
ackermannH_out_gga(x1, x2, x3)  =  ackermannH_out_gga(x1, x2, x3)
U6_gga(x1, x2, x3)  =  U6_gga(x1, x3)
U7_gga(x1, x2, x3, x4)  =  U7_gga(x1, x2, x4)
pI_in_ggaa(x1, x2, x3, x4)  =  pI_in_ggaa(x1, x2)
U12_ggaa(x1, x2, x3, x4, x5)  =  U12_ggaa(x1, x2, x5)
U13_ggaa(x1, x2, x3, x4, x5)  =  U13_ggaa(x1, x2, x3, x5)
pI_out_ggaa(x1, x2, x3, x4)  =  pI_out_ggaa(x1, x2, x3, x4)
pG_out_gaa(x1, x2, x3)  =  pG_out_gaa(x1, x2, x3)
U9_gaa(x1, x2, x3, x4)  =  U9_gaa(x1, x2, x4)
U2_gga(x1, x2, x3)  =  U2_gga(x1, x3)
pC_in_gaa(x1, x2, x3)  =  pC_in_gaa(x1)
U14_gaa(x1, x2, x3, x4)  =  U14_gaa(x1, x4)
U15_gaa(x1, x2, x3, x4)  =  U15_gaa(x1, x2, x4)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
pD_in_ggaaa(x1, x2, x3, x4, x5)  =  pD_in_ggaaa(x1, x2)
U16_ggaaa(x1, x2, x3, x4, x5, x6)  =  U16_ggaaa(x1, x2, x6)
U17_ggaaa(x1, x2, x3, x4, x5, x6)  =  U17_ggaaa(x1, x2, x3, x6)
pJ_in_ggaa(x1, x2, x3, x4)  =  pJ_in_ggaa(x1, x2)
U18_ggaa(x1, x2, x3, x4, x5)  =  U18_ggaa(x1, x2, x5)
U19_ggaa(x1, x2, x3, x4, x5)  =  U19_ggaa(x1, x2, x3, x5)
pJ_out_ggaa(x1, x2, x3, x4)  =  pJ_out_ggaa(x1, x2, x3, x4)
pD_out_ggaaa(x1, x2, x3, x4, x5)  =  pD_out_ggaaa(x1, x2, x3, x4, x5)
pC_out_gaa(x1, x2, x3)  =  pC_out_gaa(x1, x2, x3)
pB_out_gaa(x1, x2, x3)  =  pB_out_gaa(x1, x2, x3)
ACKERMANNA_IN_GGA(x1, x2, x3)  =  ACKERMANNA_IN_GGA(x1, x2)
U1_GGA(x1, x2, x3)  =  U1_GGA(x1, x3)
PB_IN_GAA(x1, x2, x3)  =  PB_IN_GAA(x1)
U8_GAA(x1, x2, x3, x4)  =  U8_GAA(x1, x4)
ACKERMANNE_IN_GA(x1, x2)  =  ACKERMANNE_IN_GA(x1)
U4_GA(x1, x2, x3)  =  U4_GA(x1, x3)
ACKERMANNF_IN_GA(x1, x2)  =  ACKERMANNF_IN_GA(x1)
U5_GA(x1, x2, x3)  =  U5_GA(x1, x3)
PG_IN_GAA(x1, x2, x3)  =  PG_IN_GAA(x1)
U10_GAA(x1, x2, x3, x4)  =  U10_GAA(x1, x4)
U11_GAA(x1, x2, x3, x4)  =  U11_GAA(x1, x2, x4)
ACKERMANNH_IN_GGA(x1, x2, x3)  =  ACKERMANNH_IN_GGA(x1, x2)
U6_GGA(x1, x2, x3)  =  U6_GGA(x1, x3)
U7_GGA(x1, x2, x3, x4)  =  U7_GGA(x1, x2, x4)
PI_IN_GGAA(x1, x2, x3, x4)  =  PI_IN_GGAA(x1, x2)
U12_GGAA(x1, x2, x3, x4, x5)  =  U12_GGAA(x1, x2, x5)
U13_GGAA(x1, x2, x3, x4, x5)  =  U13_GGAA(x1, x2, x3, x5)
U9_GAA(x1, x2, x3, x4)  =  U9_GAA(x1, x2, x4)
U2_GGA(x1, x2, x3)  =  U2_GGA(x1, x3)
PC_IN_GAA(x1, x2, x3)  =  PC_IN_GAA(x1)
U14_GAA(x1, x2, x3, x4)  =  U14_GAA(x1, x4)
U15_GAA(x1, x2, x3, x4)  =  U15_GAA(x1, x2, x4)
U3_GGA(x1, x2, x3, x4)  =  U3_GGA(x1, x2, x4)
PD_IN_GGAAA(x1, x2, x3, x4, x5)  =  PD_IN_GGAAA(x1, x2)
U16_GGAAA(x1, x2, x3, x4, x5, x6)  =  U16_GGAAA(x1, x2, x6)
U17_GGAAA(x1, x2, x3, x4, x5, x6)  =  U17_GGAAA(x1, x2, x3, x6)
PJ_IN_GGAA(x1, x2, x3, x4)  =  PJ_IN_GGAA(x1, x2)
U18_GGAA(x1, x2, x3, x4, x5)  =  U18_GGAA(x1, x2, x5)
U19_GGAA(x1, x2, x3, x4, x5)  =  U19_GGAA(x1, x2, x3, x5)

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

(4) Obligation:

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

ACKERMANNA_IN_GGA(s(s(T20)), 0, T22) → U1_GGA(T20, T22, pB_in_gaa(T20, X36, T22))
ACKERMANNA_IN_GGA(s(s(T20)), 0, T22) → PB_IN_GAA(T20, X36, T22)
PB_IN_GAA(T20, T23, T22) → U8_GAA(T20, T23, T22, ackermannE_in_ga(T20, T23))
PB_IN_GAA(T20, T23, T22) → ACKERMANNE_IN_GA(T20, T23)
ACKERMANNE_IN_GA(T28, X60) → U4_GA(T28, X60, ackermannF_in_ga(T28, X60))
ACKERMANNE_IN_GA(T28, X60) → ACKERMANNF_IN_GA(T28, X60)
ACKERMANNF_IN_GA(s(T32), X83) → U5_GA(T32, X83, pG_in_gaa(T32, X82, X83))
ACKERMANNF_IN_GA(s(T32), X83) → PG_IN_GAA(T32, X82, X83)
PG_IN_GAA(T32, T33, X83) → U10_GAA(T32, T33, X83, ackermannE_in_ga(T32, T33))
PG_IN_GAA(T32, T33, X83) → ACKERMANNE_IN_GA(T32, T33)
U10_GAA(T32, T33, X83, ackermannE_out_ga(T32, T33)) → U11_GAA(T32, T33, X83, ackermannH_in_gga(T32, T33, X83))
U10_GAA(T32, T33, X83, ackermannE_out_ga(T32, T33)) → ACKERMANNH_IN_GGA(T32, T33, X83)
ACKERMANNH_IN_GGA(s(T45), 0, X109) → U6_GGA(T45, X109, ackermannF_in_ga(T45, X109))
ACKERMANNH_IN_GGA(s(T45), 0, X109) → ACKERMANNF_IN_GA(T45, X109)
ACKERMANNH_IN_GGA(s(T50), s(T51), X125) → U7_GGA(T50, T51, X125, pI_in_ggaa(T50, T51, X124, X125))
ACKERMANNH_IN_GGA(s(T50), s(T51), X125) → PI_IN_GGAA(T50, T51, X124, X125)
PI_IN_GGAA(T50, T51, T52, X125) → U12_GGAA(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
PI_IN_GGAA(T50, T51, T52, X125) → ACKERMANNH_IN_GGA(s(T50), T51, T52)
U12_GGAA(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → U13_GGAA(T50, T51, T52, X125, ackermannH_in_gga(T50, T52, X125))
U12_GGAA(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → ACKERMANNH_IN_GGA(T50, T52, X125)
U8_GAA(T20, T23, T22, ackermannE_out_ga(T20, T23)) → U9_GAA(T20, T23, T22, ackermannA_in_gga(T20, T23, T22))
U8_GAA(T20, T23, T22, ackermannE_out_ga(T20, T23)) → ACKERMANNA_IN_GGA(T20, T23, T22)
ACKERMANNA_IN_GGA(s(T70), s(0), T65) → U2_GGA(T70, T65, pC_in_gaa(T70, X162, T65))
ACKERMANNA_IN_GGA(s(T70), s(0), T65) → PC_IN_GAA(T70, X162, T65)
PC_IN_GAA(T70, T71, T65) → U14_GAA(T70, T71, T65, ackermannF_in_ga(T70, T71))
PC_IN_GAA(T70, T71, T65) → ACKERMANNF_IN_GA(T70, T71)
U14_GAA(T70, T71, T65, ackermannF_out_ga(T70, T71)) → U15_GAA(T70, T71, T65, ackermannA_in_gga(T70, T71, T65))
U14_GAA(T70, T71, T65, ackermannF_out_ga(T70, T71)) → ACKERMANNA_IN_GGA(T70, T71, T65)
ACKERMANNA_IN_GGA(s(T78), s(s(T79)), T65) → U3_GGA(T78, T79, T65, pD_in_ggaaa(T78, T79, X181, X182, T65))
ACKERMANNA_IN_GGA(s(T78), s(s(T79)), T65) → PD_IN_GGAAA(T78, T79, X181, X182, T65)
PD_IN_GGAAA(T78, T79, T80, X182, T65) → U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_in_gga(s(T78), T79, T80))
PD_IN_GGAAA(T78, T79, T80, X182, T65) → ACKERMANNH_IN_GGA(s(T78), T79, T80)
U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → U17_GGAAA(T78, T79, T80, X182, T65, pJ_in_ggaa(T78, T80, X182, T65))
U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → PJ_IN_GGAA(T78, T80, X182, T65)
PJ_IN_GGAA(T78, T80, T83, T65) → U18_GGAA(T78, T80, T83, T65, ackermannH_in_gga(T78, T80, T83))
PJ_IN_GGAA(T78, T80, T83, T65) → ACKERMANNH_IN_GGA(T78, T80, T83)
U18_GGAA(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → U19_GGAA(T78, T80, T83, T65, ackermannA_in_gga(T78, T83, T65))
U18_GGAA(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → ACKERMANNA_IN_GGA(T78, T83, T65)

The TRS R consists of the following rules:

ackermannA_in_gga(0, T5, s(T5)) → ackermannA_out_gga(0, T5, s(T5))
ackermannA_in_gga(s(0), 0, s(s(0))) → ackermannA_out_gga(s(0), 0, s(s(0)))
ackermannA_in_gga(s(s(T20)), 0, T22) → U1_gga(T20, T22, pB_in_gaa(T20, X36, T22))
pB_in_gaa(T20, T23, T22) → U8_gaa(T20, T23, T22, ackermannE_in_ga(T20, T23))
ackermannE_in_ga(T28, X60) → U4_ga(T28, X60, ackermannF_in_ga(T28, X60))
ackermannF_in_ga(0, s(s(0))) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32), X83) → U5_ga(T32, X83, pG_in_gaa(T32, X82, X83))
pG_in_gaa(T32, T33, X83) → U10_gaa(T32, T33, X83, ackermannE_in_ga(T32, T33))
U10_gaa(T32, T33, X83, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, X83, ackermannH_in_gga(T32, T33, X83))
ackermannH_in_gga(0, T40, s(T40)) → ackermannH_out_gga(0, T40, s(T40))
ackermannH_in_gga(s(T45), 0, X109) → U6_gga(T45, X109, ackermannF_in_ga(T45, X109))
U6_gga(T45, X109, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
ackermannH_in_gga(s(T50), s(T51), X125) → U7_gga(T50, T51, X125, pI_in_ggaa(T50, T51, X124, X125))
pI_in_ggaa(T50, T51, T52, X125) → U12_ggaa(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
U12_ggaa(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, X125, ackermannH_in_gga(T50, T52, X125))
U13_ggaa(T50, T51, T52, X125, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U7_gga(T50, T51, X125, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
U11_gaa(T32, T33, X83, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)
U5_ga(T32, X83, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U4_ga(T28, X60, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U8_gaa(T20, T23, T22, ackermannE_out_ga(T20, T23)) → U9_gaa(T20, T23, T22, ackermannA_in_gga(T20, T23, T22))
ackermannA_in_gga(s(T70), s(0), T65) → U2_gga(T70, T65, pC_in_gaa(T70, X162, T65))
pC_in_gaa(T70, T71, T65) → U14_gaa(T70, T71, T65, ackermannF_in_ga(T70, T71))
U14_gaa(T70, T71, T65, ackermannF_out_ga(T70, T71)) → U15_gaa(T70, T71, T65, ackermannA_in_gga(T70, T71, T65))
ackermannA_in_gga(s(T78), s(s(T79)), T65) → U3_gga(T78, T79, T65, pD_in_ggaaa(T78, T79, X181, X182, T65))
pD_in_ggaaa(T78, T79, T80, X182, T65) → U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_in_gga(s(T78), T79, T80))
U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → U17_ggaaa(T78, T79, T80, X182, T65, pJ_in_ggaa(T78, T80, X182, T65))
pJ_in_ggaa(T78, T80, T83, T65) → U18_ggaa(T78, T80, T83, T65, ackermannH_in_gga(T78, T80, T83))
U18_ggaa(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → U19_ggaa(T78, T80, T83, T65, ackermannA_in_gga(T78, T83, T65))
U19_ggaa(T78, T80, T83, T65, ackermannA_out_gga(T78, T83, T65)) → pJ_out_ggaa(T78, T80, T83, T65)
U17_ggaaa(T78, T79, T80, X182, T65, pJ_out_ggaa(T78, T80, X182, T65)) → pD_out_ggaaa(T78, T79, T80, X182, T65)
U3_gga(T78, T79, T65, pD_out_ggaaa(T78, T79, X181, X182, T65)) → ackermannA_out_gga(s(T78), s(s(T79)), T65)
U15_gaa(T70, T71, T65, ackermannA_out_gga(T70, T71, T65)) → pC_out_gaa(T70, T71, T65)
U2_gga(T70, T65, pC_out_gaa(T70, X162, T65)) → ackermannA_out_gga(s(T70), s(0), T65)
U9_gaa(T20, T23, T22, ackermannA_out_gga(T20, T23, T22)) → pB_out_gaa(T20, T23, T22)
U1_gga(T20, T22, pB_out_gaa(T20, X36, T22)) → ackermannA_out_gga(s(s(T20)), 0, T22)

The argument filtering Pi contains the following mapping:
ackermannA_in_gga(x1, x2, x3)  =  ackermannA_in_gga(x1, x2)
0  =  0
ackermannA_out_gga(x1, x2, x3)  =  ackermannA_out_gga(x1, x2, x3)
s(x1)  =  s(x1)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x3)
pB_in_gaa(x1, x2, x3)  =  pB_in_gaa(x1)
U8_gaa(x1, x2, x3, x4)  =  U8_gaa(x1, x4)
ackermannE_in_ga(x1, x2)  =  ackermannE_in_ga(x1)
U4_ga(x1, x2, x3)  =  U4_ga(x1, x3)
ackermannF_in_ga(x1, x2)  =  ackermannF_in_ga(x1)
ackermannF_out_ga(x1, x2)  =  ackermannF_out_ga(x1, x2)
U5_ga(x1, x2, x3)  =  U5_ga(x1, x3)
pG_in_gaa(x1, x2, x3)  =  pG_in_gaa(x1)
U10_gaa(x1, x2, x3, x4)  =  U10_gaa(x1, x4)
ackermannE_out_ga(x1, x2)  =  ackermannE_out_ga(x1, x2)
U11_gaa(x1, x2, x3, x4)  =  U11_gaa(x1, x2, x4)
ackermannH_in_gga(x1, x2, x3)  =  ackermannH_in_gga(x1, x2)
ackermannH_out_gga(x1, x2, x3)  =  ackermannH_out_gga(x1, x2, x3)
U6_gga(x1, x2, x3)  =  U6_gga(x1, x3)
U7_gga(x1, x2, x3, x4)  =  U7_gga(x1, x2, x4)
pI_in_ggaa(x1, x2, x3, x4)  =  pI_in_ggaa(x1, x2)
U12_ggaa(x1, x2, x3, x4, x5)  =  U12_ggaa(x1, x2, x5)
U13_ggaa(x1, x2, x3, x4, x5)  =  U13_ggaa(x1, x2, x3, x5)
pI_out_ggaa(x1, x2, x3, x4)  =  pI_out_ggaa(x1, x2, x3, x4)
pG_out_gaa(x1, x2, x3)  =  pG_out_gaa(x1, x2, x3)
U9_gaa(x1, x2, x3, x4)  =  U9_gaa(x1, x2, x4)
U2_gga(x1, x2, x3)  =  U2_gga(x1, x3)
pC_in_gaa(x1, x2, x3)  =  pC_in_gaa(x1)
U14_gaa(x1, x2, x3, x4)  =  U14_gaa(x1, x4)
U15_gaa(x1, x2, x3, x4)  =  U15_gaa(x1, x2, x4)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
pD_in_ggaaa(x1, x2, x3, x4, x5)  =  pD_in_ggaaa(x1, x2)
U16_ggaaa(x1, x2, x3, x4, x5, x6)  =  U16_ggaaa(x1, x2, x6)
U17_ggaaa(x1, x2, x3, x4, x5, x6)  =  U17_ggaaa(x1, x2, x3, x6)
pJ_in_ggaa(x1, x2, x3, x4)  =  pJ_in_ggaa(x1, x2)
U18_ggaa(x1, x2, x3, x4, x5)  =  U18_ggaa(x1, x2, x5)
U19_ggaa(x1, x2, x3, x4, x5)  =  U19_ggaa(x1, x2, x3, x5)
pJ_out_ggaa(x1, x2, x3, x4)  =  pJ_out_ggaa(x1, x2, x3, x4)
pD_out_ggaaa(x1, x2, x3, x4, x5)  =  pD_out_ggaaa(x1, x2, x3, x4, x5)
pC_out_gaa(x1, x2, x3)  =  pC_out_gaa(x1, x2, x3)
pB_out_gaa(x1, x2, x3)  =  pB_out_gaa(x1, x2, x3)
ACKERMANNA_IN_GGA(x1, x2, x3)  =  ACKERMANNA_IN_GGA(x1, x2)
U1_GGA(x1, x2, x3)  =  U1_GGA(x1, x3)
PB_IN_GAA(x1, x2, x3)  =  PB_IN_GAA(x1)
U8_GAA(x1, x2, x3, x4)  =  U8_GAA(x1, x4)
ACKERMANNE_IN_GA(x1, x2)  =  ACKERMANNE_IN_GA(x1)
U4_GA(x1, x2, x3)  =  U4_GA(x1, x3)
ACKERMANNF_IN_GA(x1, x2)  =  ACKERMANNF_IN_GA(x1)
U5_GA(x1, x2, x3)  =  U5_GA(x1, x3)
PG_IN_GAA(x1, x2, x3)  =  PG_IN_GAA(x1)
U10_GAA(x1, x2, x3, x4)  =  U10_GAA(x1, x4)
U11_GAA(x1, x2, x3, x4)  =  U11_GAA(x1, x2, x4)
ACKERMANNH_IN_GGA(x1, x2, x3)  =  ACKERMANNH_IN_GGA(x1, x2)
U6_GGA(x1, x2, x3)  =  U6_GGA(x1, x3)
U7_GGA(x1, x2, x3, x4)  =  U7_GGA(x1, x2, x4)
PI_IN_GGAA(x1, x2, x3, x4)  =  PI_IN_GGAA(x1, x2)
U12_GGAA(x1, x2, x3, x4, x5)  =  U12_GGAA(x1, x2, x5)
U13_GGAA(x1, x2, x3, x4, x5)  =  U13_GGAA(x1, x2, x3, x5)
U9_GAA(x1, x2, x3, x4)  =  U9_GAA(x1, x2, x4)
U2_GGA(x1, x2, x3)  =  U2_GGA(x1, x3)
PC_IN_GAA(x1, x2, x3)  =  PC_IN_GAA(x1)
U14_GAA(x1, x2, x3, x4)  =  U14_GAA(x1, x4)
U15_GAA(x1, x2, x3, x4)  =  U15_GAA(x1, x2, x4)
U3_GGA(x1, x2, x3, x4)  =  U3_GGA(x1, x2, x4)
PD_IN_GGAAA(x1, x2, x3, x4, x5)  =  PD_IN_GGAAA(x1, x2)
U16_GGAAA(x1, x2, x3, x4, x5, x6)  =  U16_GGAAA(x1, x2, x6)
U17_GGAAA(x1, x2, x3, x4, x5, x6)  =  U17_GGAAA(x1, x2, x3, x6)
PJ_IN_GGAA(x1, x2, x3, x4)  =  PJ_IN_GGAA(x1, x2)
U18_GGAA(x1, x2, x3, x4, x5)  =  U18_GGAA(x1, x2, x5)
U19_GGAA(x1, x2, x3, x4, x5)  =  U19_GGAA(x1, x2, x3, 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 17 less nodes.

(6) Complex Obligation (AND)

(7) Obligation:

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

ACKERMANNE_IN_GA(T28, X60) → ACKERMANNF_IN_GA(T28, X60)
ACKERMANNF_IN_GA(s(T32), X83) → PG_IN_GAA(T32, X82, X83)
PG_IN_GAA(T32, T33, X83) → U10_GAA(T32, T33, X83, ackermannE_in_ga(T32, T33))
U10_GAA(T32, T33, X83, ackermannE_out_ga(T32, T33)) → ACKERMANNH_IN_GGA(T32, T33, X83)
ACKERMANNH_IN_GGA(s(T45), 0, X109) → ACKERMANNF_IN_GA(T45, X109)
ACKERMANNH_IN_GGA(s(T50), s(T51), X125) → PI_IN_GGAA(T50, T51, X124, X125)
PI_IN_GGAA(T50, T51, T52, X125) → U12_GGAA(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
U12_GGAA(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → ACKERMANNH_IN_GGA(T50, T52, X125)
PI_IN_GGAA(T50, T51, T52, X125) → ACKERMANNH_IN_GGA(s(T50), T51, T52)
PG_IN_GAA(T32, T33, X83) → ACKERMANNE_IN_GA(T32, T33)

The TRS R consists of the following rules:

ackermannA_in_gga(0, T5, s(T5)) → ackermannA_out_gga(0, T5, s(T5))
ackermannA_in_gga(s(0), 0, s(s(0))) → ackermannA_out_gga(s(0), 0, s(s(0)))
ackermannA_in_gga(s(s(T20)), 0, T22) → U1_gga(T20, T22, pB_in_gaa(T20, X36, T22))
pB_in_gaa(T20, T23, T22) → U8_gaa(T20, T23, T22, ackermannE_in_ga(T20, T23))
ackermannE_in_ga(T28, X60) → U4_ga(T28, X60, ackermannF_in_ga(T28, X60))
ackermannF_in_ga(0, s(s(0))) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32), X83) → U5_ga(T32, X83, pG_in_gaa(T32, X82, X83))
pG_in_gaa(T32, T33, X83) → U10_gaa(T32, T33, X83, ackermannE_in_ga(T32, T33))
U10_gaa(T32, T33, X83, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, X83, ackermannH_in_gga(T32, T33, X83))
ackermannH_in_gga(0, T40, s(T40)) → ackermannH_out_gga(0, T40, s(T40))
ackermannH_in_gga(s(T45), 0, X109) → U6_gga(T45, X109, ackermannF_in_ga(T45, X109))
U6_gga(T45, X109, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
ackermannH_in_gga(s(T50), s(T51), X125) → U7_gga(T50, T51, X125, pI_in_ggaa(T50, T51, X124, X125))
pI_in_ggaa(T50, T51, T52, X125) → U12_ggaa(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
U12_ggaa(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, X125, ackermannH_in_gga(T50, T52, X125))
U13_ggaa(T50, T51, T52, X125, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U7_gga(T50, T51, X125, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
U11_gaa(T32, T33, X83, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)
U5_ga(T32, X83, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U4_ga(T28, X60, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U8_gaa(T20, T23, T22, ackermannE_out_ga(T20, T23)) → U9_gaa(T20, T23, T22, ackermannA_in_gga(T20, T23, T22))
ackermannA_in_gga(s(T70), s(0), T65) → U2_gga(T70, T65, pC_in_gaa(T70, X162, T65))
pC_in_gaa(T70, T71, T65) → U14_gaa(T70, T71, T65, ackermannF_in_ga(T70, T71))
U14_gaa(T70, T71, T65, ackermannF_out_ga(T70, T71)) → U15_gaa(T70, T71, T65, ackermannA_in_gga(T70, T71, T65))
ackermannA_in_gga(s(T78), s(s(T79)), T65) → U3_gga(T78, T79, T65, pD_in_ggaaa(T78, T79, X181, X182, T65))
pD_in_ggaaa(T78, T79, T80, X182, T65) → U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_in_gga(s(T78), T79, T80))
U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → U17_ggaaa(T78, T79, T80, X182, T65, pJ_in_ggaa(T78, T80, X182, T65))
pJ_in_ggaa(T78, T80, T83, T65) → U18_ggaa(T78, T80, T83, T65, ackermannH_in_gga(T78, T80, T83))
U18_ggaa(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → U19_ggaa(T78, T80, T83, T65, ackermannA_in_gga(T78, T83, T65))
U19_ggaa(T78, T80, T83, T65, ackermannA_out_gga(T78, T83, T65)) → pJ_out_ggaa(T78, T80, T83, T65)
U17_ggaaa(T78, T79, T80, X182, T65, pJ_out_ggaa(T78, T80, X182, T65)) → pD_out_ggaaa(T78, T79, T80, X182, T65)
U3_gga(T78, T79, T65, pD_out_ggaaa(T78, T79, X181, X182, T65)) → ackermannA_out_gga(s(T78), s(s(T79)), T65)
U15_gaa(T70, T71, T65, ackermannA_out_gga(T70, T71, T65)) → pC_out_gaa(T70, T71, T65)
U2_gga(T70, T65, pC_out_gaa(T70, X162, T65)) → ackermannA_out_gga(s(T70), s(0), T65)
U9_gaa(T20, T23, T22, ackermannA_out_gga(T20, T23, T22)) → pB_out_gaa(T20, T23, T22)
U1_gga(T20, T22, pB_out_gaa(T20, X36, T22)) → ackermannA_out_gga(s(s(T20)), 0, T22)

The argument filtering Pi contains the following mapping:
ackermannA_in_gga(x1, x2, x3)  =  ackermannA_in_gga(x1, x2)
0  =  0
ackermannA_out_gga(x1, x2, x3)  =  ackermannA_out_gga(x1, x2, x3)
s(x1)  =  s(x1)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x3)
pB_in_gaa(x1, x2, x3)  =  pB_in_gaa(x1)
U8_gaa(x1, x2, x3, x4)  =  U8_gaa(x1, x4)
ackermannE_in_ga(x1, x2)  =  ackermannE_in_ga(x1)
U4_ga(x1, x2, x3)  =  U4_ga(x1, x3)
ackermannF_in_ga(x1, x2)  =  ackermannF_in_ga(x1)
ackermannF_out_ga(x1, x2)  =  ackermannF_out_ga(x1, x2)
U5_ga(x1, x2, x3)  =  U5_ga(x1, x3)
pG_in_gaa(x1, x2, x3)  =  pG_in_gaa(x1)
U10_gaa(x1, x2, x3, x4)  =  U10_gaa(x1, x4)
ackermannE_out_ga(x1, x2)  =  ackermannE_out_ga(x1, x2)
U11_gaa(x1, x2, x3, x4)  =  U11_gaa(x1, x2, x4)
ackermannH_in_gga(x1, x2, x3)  =  ackermannH_in_gga(x1, x2)
ackermannH_out_gga(x1, x2, x3)  =  ackermannH_out_gga(x1, x2, x3)
U6_gga(x1, x2, x3)  =  U6_gga(x1, x3)
U7_gga(x1, x2, x3, x4)  =  U7_gga(x1, x2, x4)
pI_in_ggaa(x1, x2, x3, x4)  =  pI_in_ggaa(x1, x2)
U12_ggaa(x1, x2, x3, x4, x5)  =  U12_ggaa(x1, x2, x5)
U13_ggaa(x1, x2, x3, x4, x5)  =  U13_ggaa(x1, x2, x3, x5)
pI_out_ggaa(x1, x2, x3, x4)  =  pI_out_ggaa(x1, x2, x3, x4)
pG_out_gaa(x1, x2, x3)  =  pG_out_gaa(x1, x2, x3)
U9_gaa(x1, x2, x3, x4)  =  U9_gaa(x1, x2, x4)
U2_gga(x1, x2, x3)  =  U2_gga(x1, x3)
pC_in_gaa(x1, x2, x3)  =  pC_in_gaa(x1)
U14_gaa(x1, x2, x3, x4)  =  U14_gaa(x1, x4)
U15_gaa(x1, x2, x3, x4)  =  U15_gaa(x1, x2, x4)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
pD_in_ggaaa(x1, x2, x3, x4, x5)  =  pD_in_ggaaa(x1, x2)
U16_ggaaa(x1, x2, x3, x4, x5, x6)  =  U16_ggaaa(x1, x2, x6)
U17_ggaaa(x1, x2, x3, x4, x5, x6)  =  U17_ggaaa(x1, x2, x3, x6)
pJ_in_ggaa(x1, x2, x3, x4)  =  pJ_in_ggaa(x1, x2)
U18_ggaa(x1, x2, x3, x4, x5)  =  U18_ggaa(x1, x2, x5)
U19_ggaa(x1, x2, x3, x4, x5)  =  U19_ggaa(x1, x2, x3, x5)
pJ_out_ggaa(x1, x2, x3, x4)  =  pJ_out_ggaa(x1, x2, x3, x4)
pD_out_ggaaa(x1, x2, x3, x4, x5)  =  pD_out_ggaaa(x1, x2, x3, x4, x5)
pC_out_gaa(x1, x2, x3)  =  pC_out_gaa(x1, x2, x3)
pB_out_gaa(x1, x2, x3)  =  pB_out_gaa(x1, x2, x3)
ACKERMANNE_IN_GA(x1, x2)  =  ACKERMANNE_IN_GA(x1)
ACKERMANNF_IN_GA(x1, x2)  =  ACKERMANNF_IN_GA(x1)
PG_IN_GAA(x1, x2, x3)  =  PG_IN_GAA(x1)
U10_GAA(x1, x2, x3, x4)  =  U10_GAA(x1, x4)
ACKERMANNH_IN_GGA(x1, x2, x3)  =  ACKERMANNH_IN_GGA(x1, x2)
PI_IN_GGAA(x1, x2, x3, x4)  =  PI_IN_GGAA(x1, x2)
U12_GGAA(x1, x2, x3, x4, x5)  =  U12_GGAA(x1, x2, x5)

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:

ACKERMANNE_IN_GA(T28, X60) → ACKERMANNF_IN_GA(T28, X60)
ACKERMANNF_IN_GA(s(T32), X83) → PG_IN_GAA(T32, X82, X83)
PG_IN_GAA(T32, T33, X83) → U10_GAA(T32, T33, X83, ackermannE_in_ga(T32, T33))
U10_GAA(T32, T33, X83, ackermannE_out_ga(T32, T33)) → ACKERMANNH_IN_GGA(T32, T33, X83)
ACKERMANNH_IN_GGA(s(T45), 0, X109) → ACKERMANNF_IN_GA(T45, X109)
ACKERMANNH_IN_GGA(s(T50), s(T51), X125) → PI_IN_GGAA(T50, T51, X124, X125)
PI_IN_GGAA(T50, T51, T52, X125) → U12_GGAA(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
U12_GGAA(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → ACKERMANNH_IN_GGA(T50, T52, X125)
PI_IN_GGAA(T50, T51, T52, X125) → ACKERMANNH_IN_GGA(s(T50), T51, T52)
PG_IN_GAA(T32, T33, X83) → ACKERMANNE_IN_GA(T32, T33)

The TRS R consists of the following rules:

ackermannE_in_ga(T28, X60) → U4_ga(T28, X60, ackermannF_in_ga(T28, X60))
ackermannH_in_gga(s(T45), 0, X109) → U6_gga(T45, X109, ackermannF_in_ga(T45, X109))
ackermannH_in_gga(s(T50), s(T51), X125) → U7_gga(T50, T51, X125, pI_in_ggaa(T50, T51, X124, X125))
U4_ga(T28, X60, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U6_gga(T45, X109, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
U7_gga(T50, T51, X125, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
ackermannF_in_ga(0, s(s(0))) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32), X83) → U5_ga(T32, X83, pG_in_gaa(T32, X82, X83))
pI_in_ggaa(T50, T51, T52, X125) → U12_ggaa(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
U5_ga(T32, X83, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U12_ggaa(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, X125, ackermannH_in_gga(T50, T52, X125))
pG_in_gaa(T32, T33, X83) → U10_gaa(T32, T33, X83, ackermannE_in_ga(T32, T33))
U13_ggaa(T50, T51, T52, X125, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U10_gaa(T32, T33, X83, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, X83, ackermannH_in_gga(T32, T33, X83))
ackermannH_in_gga(0, T40, s(T40)) → ackermannH_out_gga(0, T40, s(T40))
U11_gaa(T32, T33, X83, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)

The argument filtering Pi contains the following mapping:
0  =  0
s(x1)  =  s(x1)
ackermannE_in_ga(x1, x2)  =  ackermannE_in_ga(x1)
U4_ga(x1, x2, x3)  =  U4_ga(x1, x3)
ackermannF_in_ga(x1, x2)  =  ackermannF_in_ga(x1)
ackermannF_out_ga(x1, x2)  =  ackermannF_out_ga(x1, x2)
U5_ga(x1, x2, x3)  =  U5_ga(x1, x3)
pG_in_gaa(x1, x2, x3)  =  pG_in_gaa(x1)
U10_gaa(x1, x2, x3, x4)  =  U10_gaa(x1, x4)
ackermannE_out_ga(x1, x2)  =  ackermannE_out_ga(x1, x2)
U11_gaa(x1, x2, x3, x4)  =  U11_gaa(x1, x2, x4)
ackermannH_in_gga(x1, x2, x3)  =  ackermannH_in_gga(x1, x2)
ackermannH_out_gga(x1, x2, x3)  =  ackermannH_out_gga(x1, x2, x3)
U6_gga(x1, x2, x3)  =  U6_gga(x1, x3)
U7_gga(x1, x2, x3, x4)  =  U7_gga(x1, x2, x4)
pI_in_ggaa(x1, x2, x3, x4)  =  pI_in_ggaa(x1, x2)
U12_ggaa(x1, x2, x3, x4, x5)  =  U12_ggaa(x1, x2, x5)
U13_ggaa(x1, x2, x3, x4, x5)  =  U13_ggaa(x1, x2, x3, x5)
pI_out_ggaa(x1, x2, x3, x4)  =  pI_out_ggaa(x1, x2, x3, x4)
pG_out_gaa(x1, x2, x3)  =  pG_out_gaa(x1, x2, x3)
ACKERMANNE_IN_GA(x1, x2)  =  ACKERMANNE_IN_GA(x1)
ACKERMANNF_IN_GA(x1, x2)  =  ACKERMANNF_IN_GA(x1)
PG_IN_GAA(x1, x2, x3)  =  PG_IN_GAA(x1)
U10_GAA(x1, x2, x3, x4)  =  U10_GAA(x1, x4)
ACKERMANNH_IN_GGA(x1, x2, x3)  =  ACKERMANNH_IN_GGA(x1, x2)
PI_IN_GGAA(x1, x2, x3, x4)  =  PI_IN_GGAA(x1, x2)
U12_GGAA(x1, x2, x3, x4, x5)  =  U12_GGAA(x1, x2, x5)

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:

ACKERMANNE_IN_GA(T28) → ACKERMANNF_IN_GA(T28)
ACKERMANNF_IN_GA(s(T32)) → PG_IN_GAA(T32)
PG_IN_GAA(T32) → U10_GAA(T32, ackermannE_in_ga(T32))
U10_GAA(T32, ackermannE_out_ga(T32, T33)) → ACKERMANNH_IN_GGA(T32, T33)
ACKERMANNH_IN_GGA(s(T45), 0) → ACKERMANNF_IN_GA(T45)
ACKERMANNH_IN_GGA(s(T50), s(T51)) → PI_IN_GGAA(T50, T51)
PI_IN_GGAA(T50, T51) → U12_GGAA(T50, T51, ackermannH_in_gga(s(T50), T51))
U12_GGAA(T50, T51, ackermannH_out_gga(s(T50), T51, T52)) → ACKERMANNH_IN_GGA(T50, T52)
PI_IN_GGAA(T50, T51) → ACKERMANNH_IN_GGA(s(T50), T51)
PG_IN_GAA(T32) → ACKERMANNE_IN_GA(T32)

The TRS R consists of the following rules:

ackermannE_in_ga(T28) → U4_ga(T28, ackermannF_in_ga(T28))
ackermannH_in_gga(s(T45), 0) → U6_gga(T45, ackermannF_in_ga(T45))
ackermannH_in_gga(s(T50), s(T51)) → U7_gga(T50, T51, pI_in_ggaa(T50, T51))
U4_ga(T28, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U6_gga(T45, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
U7_gga(T50, T51, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
ackermannF_in_ga(0) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32)) → U5_ga(T32, pG_in_gaa(T32))
pI_in_ggaa(T50, T51) → U12_ggaa(T50, T51, ackermannH_in_gga(s(T50), T51))
U5_ga(T32, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U12_ggaa(T50, T51, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, ackermannH_in_gga(T50, T52))
pG_in_gaa(T32) → U10_gaa(T32, ackermannE_in_ga(T32))
U13_ggaa(T50, T51, T52, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U10_gaa(T32, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, ackermannH_in_gga(T32, T33))
ackermannH_in_gga(0, T40) → ackermannH_out_gga(0, T40, s(T40))
U11_gaa(T32, T33, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)

The set Q consists of the following terms:

ackermannE_in_ga(x0)
ackermannH_in_gga(x0, x1)
U4_ga(x0, x1)
U6_gga(x0, x1)
U7_gga(x0, x1, x2)
ackermannF_in_ga(x0)
pI_in_ggaa(x0, x1)
U5_ga(x0, x1)
U12_ggaa(x0, x1, x2)
pG_in_gaa(x0)
U13_ggaa(x0, x1, x2, x3)
U10_gaa(x0, x1)
U11_gaa(x0, x1, x2)

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

(12) Rewriting (EQUIVALENT transformation)

By rewriting [LPAR04] the rule PG_IN_GAA(T32) → U10_GAA(T32, ackermannE_in_ga(T32)) at position [1] we obtained the following new rules [LPAR04]:

PG_IN_GAA(T32) → U10_GAA(T32, U4_ga(T32, ackermannF_in_ga(T32)))

(13) Obligation:

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

ACKERMANNE_IN_GA(T28) → ACKERMANNF_IN_GA(T28)
ACKERMANNF_IN_GA(s(T32)) → PG_IN_GAA(T32)
U10_GAA(T32, ackermannE_out_ga(T32, T33)) → ACKERMANNH_IN_GGA(T32, T33)
ACKERMANNH_IN_GGA(s(T45), 0) → ACKERMANNF_IN_GA(T45)
ACKERMANNH_IN_GGA(s(T50), s(T51)) → PI_IN_GGAA(T50, T51)
PI_IN_GGAA(T50, T51) → U12_GGAA(T50, T51, ackermannH_in_gga(s(T50), T51))
U12_GGAA(T50, T51, ackermannH_out_gga(s(T50), T51, T52)) → ACKERMANNH_IN_GGA(T50, T52)
PI_IN_GGAA(T50, T51) → ACKERMANNH_IN_GGA(s(T50), T51)
PG_IN_GAA(T32) → ACKERMANNE_IN_GA(T32)
PG_IN_GAA(T32) → U10_GAA(T32, U4_ga(T32, ackermannF_in_ga(T32)))

The TRS R consists of the following rules:

ackermannE_in_ga(T28) → U4_ga(T28, ackermannF_in_ga(T28))
ackermannH_in_gga(s(T45), 0) → U6_gga(T45, ackermannF_in_ga(T45))
ackermannH_in_gga(s(T50), s(T51)) → U7_gga(T50, T51, pI_in_ggaa(T50, T51))
U4_ga(T28, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U6_gga(T45, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
U7_gga(T50, T51, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
ackermannF_in_ga(0) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32)) → U5_ga(T32, pG_in_gaa(T32))
pI_in_ggaa(T50, T51) → U12_ggaa(T50, T51, ackermannH_in_gga(s(T50), T51))
U5_ga(T32, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U12_ggaa(T50, T51, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, ackermannH_in_gga(T50, T52))
pG_in_gaa(T32) → U10_gaa(T32, ackermannE_in_ga(T32))
U13_ggaa(T50, T51, T52, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U10_gaa(T32, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, ackermannH_in_gga(T32, T33))
ackermannH_in_gga(0, T40) → ackermannH_out_gga(0, T40, s(T40))
U11_gaa(T32, T33, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)

The set Q consists of the following terms:

ackermannE_in_ga(x0)
ackermannH_in_gga(x0, x1)
U4_ga(x0, x1)
U6_gga(x0, x1)
U7_gga(x0, x1, x2)
ackermannF_in_ga(x0)
pI_in_ggaa(x0, x1)
U5_ga(x0, x1)
U12_ggaa(x0, x1, x2)
pG_in_gaa(x0)
U13_ggaa(x0, x1, x2, x3)
U10_gaa(x0, x1)
U11_gaa(x0, x1, x2)

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

(14) QDPOrderProof (EQUIVALENT transformation)

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


The following pairs can be oriented strictly and are deleted.


ACKERMANNH_IN_GGA(s(T45), 0) → ACKERMANNF_IN_GA(T45)
PI_IN_GGAA(T50, T51) → U12_GGAA(T50, T51, ackermannH_in_gga(s(T50), T51))
PG_IN_GAA(T32) → ACKERMANNE_IN_GA(T32)
PG_IN_GAA(T32) → U10_GAA(T32, U4_ga(T32, ackermannF_in_ga(T32)))
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:

POL(0) = 1   
POL(ACKERMANNE_IN_GA(x1)) = x1   
POL(ACKERMANNF_IN_GA(x1)) = x1   
POL(ACKERMANNH_IN_GGA(x1, x2)) = x1   
POL(PG_IN_GAA(x1)) = 1 + x1   
POL(PI_IN_GGAA(x1, x2)) = 1 + x1   
POL(U10_GAA(x1, x2)) = x1   
POL(U10_gaa(x1, x2)) = 0   
POL(U11_gaa(x1, x2, x3)) = 0   
POL(U12_GGAA(x1, x2, x3)) = x1   
POL(U12_ggaa(x1, x2, x3)) = 0   
POL(U13_ggaa(x1, x2, x3, x4)) = 0   
POL(U4_ga(x1, x2)) = 0   
POL(U5_ga(x1, x2)) = 0   
POL(U6_gga(x1, x2)) = 0   
POL(U7_gga(x1, x2, x3)) = 0   
POL(ackermannE_in_ga(x1)) = 0   
POL(ackermannE_out_ga(x1, x2)) = 0   
POL(ackermannF_in_ga(x1)) = x1   
POL(ackermannF_out_ga(x1, x2)) = 0   
POL(ackermannH_in_gga(x1, x2)) = 1 + x1 + x2   
POL(ackermannH_out_gga(x1, x2, x3)) = x1   
POL(pG_in_gaa(x1)) = 0   
POL(pG_out_gaa(x1, x2, x3)) = 0   
POL(pI_in_ggaa(x1, x2)) = 0   
POL(pI_out_ggaa(x1, x2, x3, x4)) = 0   
POL(s(x1)) = 1 + x1   

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

(15) Obligation:

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

ACKERMANNE_IN_GA(T28) → ACKERMANNF_IN_GA(T28)
ACKERMANNF_IN_GA(s(T32)) → PG_IN_GAA(T32)
U10_GAA(T32, ackermannE_out_ga(T32, T33)) → ACKERMANNH_IN_GGA(T32, T33)
ACKERMANNH_IN_GGA(s(T50), s(T51)) → PI_IN_GGAA(T50, T51)
U12_GGAA(T50, T51, ackermannH_out_gga(s(T50), T51, T52)) → ACKERMANNH_IN_GGA(T50, T52)
PI_IN_GGAA(T50, T51) → ACKERMANNH_IN_GGA(s(T50), T51)

The TRS R consists of the following rules:

ackermannE_in_ga(T28) → U4_ga(T28, ackermannF_in_ga(T28))
ackermannH_in_gga(s(T45), 0) → U6_gga(T45, ackermannF_in_ga(T45))
ackermannH_in_gga(s(T50), s(T51)) → U7_gga(T50, T51, pI_in_ggaa(T50, T51))
U4_ga(T28, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U6_gga(T45, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
U7_gga(T50, T51, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
ackermannF_in_ga(0) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32)) → U5_ga(T32, pG_in_gaa(T32))
pI_in_ggaa(T50, T51) → U12_ggaa(T50, T51, ackermannH_in_gga(s(T50), T51))
U5_ga(T32, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U12_ggaa(T50, T51, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, ackermannH_in_gga(T50, T52))
pG_in_gaa(T32) → U10_gaa(T32, ackermannE_in_ga(T32))
U13_ggaa(T50, T51, T52, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U10_gaa(T32, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, ackermannH_in_gga(T32, T33))
ackermannH_in_gga(0, T40) → ackermannH_out_gga(0, T40, s(T40))
U11_gaa(T32, T33, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)

The set Q consists of the following terms:

ackermannE_in_ga(x0)
ackermannH_in_gga(x0, x1)
U4_ga(x0, x1)
U6_gga(x0, x1)
U7_gga(x0, x1, x2)
ackermannF_in_ga(x0)
pI_in_ggaa(x0, x1)
U5_ga(x0, x1)
U12_ggaa(x0, x1, x2)
pG_in_gaa(x0)
U13_ggaa(x0, x1, x2, x3)
U10_gaa(x0, x1)
U11_gaa(x0, x1, x2)

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

(16) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes.

(17) Obligation:

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

PI_IN_GGAA(T50, T51) → ACKERMANNH_IN_GGA(s(T50), T51)
ACKERMANNH_IN_GGA(s(T50), s(T51)) → PI_IN_GGAA(T50, T51)

The TRS R consists of the following rules:

ackermannE_in_ga(T28) → U4_ga(T28, ackermannF_in_ga(T28))
ackermannH_in_gga(s(T45), 0) → U6_gga(T45, ackermannF_in_ga(T45))
ackermannH_in_gga(s(T50), s(T51)) → U7_gga(T50, T51, pI_in_ggaa(T50, T51))
U4_ga(T28, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U6_gga(T45, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
U7_gga(T50, T51, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
ackermannF_in_ga(0) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32)) → U5_ga(T32, pG_in_gaa(T32))
pI_in_ggaa(T50, T51) → U12_ggaa(T50, T51, ackermannH_in_gga(s(T50), T51))
U5_ga(T32, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U12_ggaa(T50, T51, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, ackermannH_in_gga(T50, T52))
pG_in_gaa(T32) → U10_gaa(T32, ackermannE_in_ga(T32))
U13_ggaa(T50, T51, T52, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U10_gaa(T32, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, ackermannH_in_gga(T32, T33))
ackermannH_in_gga(0, T40) → ackermannH_out_gga(0, T40, s(T40))
U11_gaa(T32, T33, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)

The set Q consists of the following terms:

ackermannE_in_ga(x0)
ackermannH_in_gga(x0, x1)
U4_ga(x0, x1)
U6_gga(x0, x1)
U7_gga(x0, x1, x2)
ackermannF_in_ga(x0)
pI_in_ggaa(x0, x1)
U5_ga(x0, x1)
U12_ggaa(x0, x1, x2)
pG_in_gaa(x0)
U13_ggaa(x0, x1, x2, x3)
U10_gaa(x0, x1)
U11_gaa(x0, x1, x2)

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

(18) UsableRulesProof (EQUIVALENT transformation)

As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.

(19) Obligation:

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

PI_IN_GGAA(T50, T51) → ACKERMANNH_IN_GGA(s(T50), T51)
ACKERMANNH_IN_GGA(s(T50), s(T51)) → PI_IN_GGAA(T50, T51)

R is empty.
The set Q consists of the following terms:

ackermannE_in_ga(x0)
ackermannH_in_gga(x0, x1)
U4_ga(x0, x1)
U6_gga(x0, x1)
U7_gga(x0, x1, x2)
ackermannF_in_ga(x0)
pI_in_ggaa(x0, x1)
U5_ga(x0, x1)
U12_ggaa(x0, x1, x2)
pG_in_gaa(x0)
U13_ggaa(x0, x1, x2, x3)
U10_gaa(x0, x1)
U11_gaa(x0, x1, x2)

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

(20) QReductionProof (EQUIVALENT transformation)

We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

ackermannE_in_ga(x0)
ackermannH_in_gga(x0, x1)
U4_ga(x0, x1)
U6_gga(x0, x1)
U7_gga(x0, x1, x2)
ackermannF_in_ga(x0)
pI_in_ggaa(x0, x1)
U5_ga(x0, x1)
U12_ggaa(x0, x1, x2)
pG_in_gaa(x0)
U13_ggaa(x0, x1, x2, x3)
U10_gaa(x0, x1)
U11_gaa(x0, x1, x2)

(21) Obligation:

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

PI_IN_GGAA(T50, T51) → ACKERMANNH_IN_GGA(s(T50), T51)
ACKERMANNH_IN_GGA(s(T50), s(T51)) → PI_IN_GGAA(T50, T51)

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

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

  • ACKERMANNH_IN_GGA(s(T50), s(T51)) → PI_IN_GGAA(T50, T51)
    The graph contains the following edges 1 > 1, 2 > 2

  • PI_IN_GGAA(T50, T51) → ACKERMANNH_IN_GGA(s(T50), T51)
    The graph contains the following edges 2 >= 2

(23) YES

(24) Obligation:

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

ACKERMANNA_IN_GGA(s(s(T20)), 0, T22) → PB_IN_GAA(T20, X36, T22)
PB_IN_GAA(T20, T23, T22) → U8_GAA(T20, T23, T22, ackermannE_in_ga(T20, T23))
U8_GAA(T20, T23, T22, ackermannE_out_ga(T20, T23)) → ACKERMANNA_IN_GGA(T20, T23, T22)
ACKERMANNA_IN_GGA(s(T70), s(0), T65) → PC_IN_GAA(T70, X162, T65)
PC_IN_GAA(T70, T71, T65) → U14_GAA(T70, T71, T65, ackermannF_in_ga(T70, T71))
U14_GAA(T70, T71, T65, ackermannF_out_ga(T70, T71)) → ACKERMANNA_IN_GGA(T70, T71, T65)
ACKERMANNA_IN_GGA(s(T78), s(s(T79)), T65) → PD_IN_GGAAA(T78, T79, X181, X182, T65)
PD_IN_GGAAA(T78, T79, T80, X182, T65) → U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_in_gga(s(T78), T79, T80))
U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → PJ_IN_GGAA(T78, T80, X182, T65)
PJ_IN_GGAA(T78, T80, T83, T65) → U18_GGAA(T78, T80, T83, T65, ackermannH_in_gga(T78, T80, T83))
U18_GGAA(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → ACKERMANNA_IN_GGA(T78, T83, T65)

The TRS R consists of the following rules:

ackermannA_in_gga(0, T5, s(T5)) → ackermannA_out_gga(0, T5, s(T5))
ackermannA_in_gga(s(0), 0, s(s(0))) → ackermannA_out_gga(s(0), 0, s(s(0)))
ackermannA_in_gga(s(s(T20)), 0, T22) → U1_gga(T20, T22, pB_in_gaa(T20, X36, T22))
pB_in_gaa(T20, T23, T22) → U8_gaa(T20, T23, T22, ackermannE_in_ga(T20, T23))
ackermannE_in_ga(T28, X60) → U4_ga(T28, X60, ackermannF_in_ga(T28, X60))
ackermannF_in_ga(0, s(s(0))) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32), X83) → U5_ga(T32, X83, pG_in_gaa(T32, X82, X83))
pG_in_gaa(T32, T33, X83) → U10_gaa(T32, T33, X83, ackermannE_in_ga(T32, T33))
U10_gaa(T32, T33, X83, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, X83, ackermannH_in_gga(T32, T33, X83))
ackermannH_in_gga(0, T40, s(T40)) → ackermannH_out_gga(0, T40, s(T40))
ackermannH_in_gga(s(T45), 0, X109) → U6_gga(T45, X109, ackermannF_in_ga(T45, X109))
U6_gga(T45, X109, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
ackermannH_in_gga(s(T50), s(T51), X125) → U7_gga(T50, T51, X125, pI_in_ggaa(T50, T51, X124, X125))
pI_in_ggaa(T50, T51, T52, X125) → U12_ggaa(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
U12_ggaa(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, X125, ackermannH_in_gga(T50, T52, X125))
U13_ggaa(T50, T51, T52, X125, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)
U7_gga(T50, T51, X125, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
U11_gaa(T32, T33, X83, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)
U5_ga(T32, X83, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U4_ga(T28, X60, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U8_gaa(T20, T23, T22, ackermannE_out_ga(T20, T23)) → U9_gaa(T20, T23, T22, ackermannA_in_gga(T20, T23, T22))
ackermannA_in_gga(s(T70), s(0), T65) → U2_gga(T70, T65, pC_in_gaa(T70, X162, T65))
pC_in_gaa(T70, T71, T65) → U14_gaa(T70, T71, T65, ackermannF_in_ga(T70, T71))
U14_gaa(T70, T71, T65, ackermannF_out_ga(T70, T71)) → U15_gaa(T70, T71, T65, ackermannA_in_gga(T70, T71, T65))
ackermannA_in_gga(s(T78), s(s(T79)), T65) → U3_gga(T78, T79, T65, pD_in_ggaaa(T78, T79, X181, X182, T65))
pD_in_ggaaa(T78, T79, T80, X182, T65) → U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_in_gga(s(T78), T79, T80))
U16_ggaaa(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → U17_ggaaa(T78, T79, T80, X182, T65, pJ_in_ggaa(T78, T80, X182, T65))
pJ_in_ggaa(T78, T80, T83, T65) → U18_ggaa(T78, T80, T83, T65, ackermannH_in_gga(T78, T80, T83))
U18_ggaa(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → U19_ggaa(T78, T80, T83, T65, ackermannA_in_gga(T78, T83, T65))
U19_ggaa(T78, T80, T83, T65, ackermannA_out_gga(T78, T83, T65)) → pJ_out_ggaa(T78, T80, T83, T65)
U17_ggaaa(T78, T79, T80, X182, T65, pJ_out_ggaa(T78, T80, X182, T65)) → pD_out_ggaaa(T78, T79, T80, X182, T65)
U3_gga(T78, T79, T65, pD_out_ggaaa(T78, T79, X181, X182, T65)) → ackermannA_out_gga(s(T78), s(s(T79)), T65)
U15_gaa(T70, T71, T65, ackermannA_out_gga(T70, T71, T65)) → pC_out_gaa(T70, T71, T65)
U2_gga(T70, T65, pC_out_gaa(T70, X162, T65)) → ackermannA_out_gga(s(T70), s(0), T65)
U9_gaa(T20, T23, T22, ackermannA_out_gga(T20, T23, T22)) → pB_out_gaa(T20, T23, T22)
U1_gga(T20, T22, pB_out_gaa(T20, X36, T22)) → ackermannA_out_gga(s(s(T20)), 0, T22)

The argument filtering Pi contains the following mapping:
ackermannA_in_gga(x1, x2, x3)  =  ackermannA_in_gga(x1, x2)
0  =  0
ackermannA_out_gga(x1, x2, x3)  =  ackermannA_out_gga(x1, x2, x3)
s(x1)  =  s(x1)
U1_gga(x1, x2, x3)  =  U1_gga(x1, x3)
pB_in_gaa(x1, x2, x3)  =  pB_in_gaa(x1)
U8_gaa(x1, x2, x3, x4)  =  U8_gaa(x1, x4)
ackermannE_in_ga(x1, x2)  =  ackermannE_in_ga(x1)
U4_ga(x1, x2, x3)  =  U4_ga(x1, x3)
ackermannF_in_ga(x1, x2)  =  ackermannF_in_ga(x1)
ackermannF_out_ga(x1, x2)  =  ackermannF_out_ga(x1, x2)
U5_ga(x1, x2, x3)  =  U5_ga(x1, x3)
pG_in_gaa(x1, x2, x3)  =  pG_in_gaa(x1)
U10_gaa(x1, x2, x3, x4)  =  U10_gaa(x1, x4)
ackermannE_out_ga(x1, x2)  =  ackermannE_out_ga(x1, x2)
U11_gaa(x1, x2, x3, x4)  =  U11_gaa(x1, x2, x4)
ackermannH_in_gga(x1, x2, x3)  =  ackermannH_in_gga(x1, x2)
ackermannH_out_gga(x1, x2, x3)  =  ackermannH_out_gga(x1, x2, x3)
U6_gga(x1, x2, x3)  =  U6_gga(x1, x3)
U7_gga(x1, x2, x3, x4)  =  U7_gga(x1, x2, x4)
pI_in_ggaa(x1, x2, x3, x4)  =  pI_in_ggaa(x1, x2)
U12_ggaa(x1, x2, x3, x4, x5)  =  U12_ggaa(x1, x2, x5)
U13_ggaa(x1, x2, x3, x4, x5)  =  U13_ggaa(x1, x2, x3, x5)
pI_out_ggaa(x1, x2, x3, x4)  =  pI_out_ggaa(x1, x2, x3, x4)
pG_out_gaa(x1, x2, x3)  =  pG_out_gaa(x1, x2, x3)
U9_gaa(x1, x2, x3, x4)  =  U9_gaa(x1, x2, x4)
U2_gga(x1, x2, x3)  =  U2_gga(x1, x3)
pC_in_gaa(x1, x2, x3)  =  pC_in_gaa(x1)
U14_gaa(x1, x2, x3, x4)  =  U14_gaa(x1, x4)
U15_gaa(x1, x2, x3, x4)  =  U15_gaa(x1, x2, x4)
U3_gga(x1, x2, x3, x4)  =  U3_gga(x1, x2, x4)
pD_in_ggaaa(x1, x2, x3, x4, x5)  =  pD_in_ggaaa(x1, x2)
U16_ggaaa(x1, x2, x3, x4, x5, x6)  =  U16_ggaaa(x1, x2, x6)
U17_ggaaa(x1, x2, x3, x4, x5, x6)  =  U17_ggaaa(x1, x2, x3, x6)
pJ_in_ggaa(x1, x2, x3, x4)  =  pJ_in_ggaa(x1, x2)
U18_ggaa(x1, x2, x3, x4, x5)  =  U18_ggaa(x1, x2, x5)
U19_ggaa(x1, x2, x3, x4, x5)  =  U19_ggaa(x1, x2, x3, x5)
pJ_out_ggaa(x1, x2, x3, x4)  =  pJ_out_ggaa(x1, x2, x3, x4)
pD_out_ggaaa(x1, x2, x3, x4, x5)  =  pD_out_ggaaa(x1, x2, x3, x4, x5)
pC_out_gaa(x1, x2, x3)  =  pC_out_gaa(x1, x2, x3)
pB_out_gaa(x1, x2, x3)  =  pB_out_gaa(x1, x2, x3)
ACKERMANNA_IN_GGA(x1, x2, x3)  =  ACKERMANNA_IN_GGA(x1, x2)
PB_IN_GAA(x1, x2, x3)  =  PB_IN_GAA(x1)
U8_GAA(x1, x2, x3, x4)  =  U8_GAA(x1, x4)
PC_IN_GAA(x1, x2, x3)  =  PC_IN_GAA(x1)
U14_GAA(x1, x2, x3, x4)  =  U14_GAA(x1, x4)
PD_IN_GGAAA(x1, x2, x3, x4, x5)  =  PD_IN_GGAAA(x1, x2)
U16_GGAAA(x1, x2, x3, x4, x5, x6)  =  U16_GGAAA(x1, x2, x6)
PJ_IN_GGAA(x1, x2, x3, x4)  =  PJ_IN_GGAA(x1, x2)
U18_GGAA(x1, x2, x3, x4, x5)  =  U18_GGAA(x1, x2, x5)

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

(25) UsableRulesProof (EQUIVALENT transformation)

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

(26) Obligation:

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

ACKERMANNA_IN_GGA(s(s(T20)), 0, T22) → PB_IN_GAA(T20, X36, T22)
PB_IN_GAA(T20, T23, T22) → U8_GAA(T20, T23, T22, ackermannE_in_ga(T20, T23))
U8_GAA(T20, T23, T22, ackermannE_out_ga(T20, T23)) → ACKERMANNA_IN_GGA(T20, T23, T22)
ACKERMANNA_IN_GGA(s(T70), s(0), T65) → PC_IN_GAA(T70, X162, T65)
PC_IN_GAA(T70, T71, T65) → U14_GAA(T70, T71, T65, ackermannF_in_ga(T70, T71))
U14_GAA(T70, T71, T65, ackermannF_out_ga(T70, T71)) → ACKERMANNA_IN_GGA(T70, T71, T65)
ACKERMANNA_IN_GGA(s(T78), s(s(T79)), T65) → PD_IN_GGAAA(T78, T79, X181, X182, T65)
PD_IN_GGAAA(T78, T79, T80, X182, T65) → U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_in_gga(s(T78), T79, T80))
U16_GGAAA(T78, T79, T80, X182, T65, ackermannH_out_gga(s(T78), T79, T80)) → PJ_IN_GGAA(T78, T80, X182, T65)
PJ_IN_GGAA(T78, T80, T83, T65) → U18_GGAA(T78, T80, T83, T65, ackermannH_in_gga(T78, T80, T83))
U18_GGAA(T78, T80, T83, T65, ackermannH_out_gga(T78, T80, T83)) → ACKERMANNA_IN_GGA(T78, T83, T65)

The TRS R consists of the following rules:

ackermannE_in_ga(T28, X60) → U4_ga(T28, X60, ackermannF_in_ga(T28, X60))
ackermannF_in_ga(0, s(s(0))) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32), X83) → U5_ga(T32, X83, pG_in_gaa(T32, X82, X83))
ackermannH_in_gga(s(T45), 0, X109) → U6_gga(T45, X109, ackermannF_in_ga(T45, X109))
ackermannH_in_gga(s(T50), s(T51), X125) → U7_gga(T50, T51, X125, pI_in_ggaa(T50, T51, X124, X125))
ackermannH_in_gga(0, T40, s(T40)) → ackermannH_out_gga(0, T40, s(T40))
U4_ga(T28, X60, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U5_ga(T32, X83, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U6_gga(T45, X109, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
U7_gga(T50, T51, X125, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
pG_in_gaa(T32, T33, X83) → U10_gaa(T32, T33, X83, ackermannE_in_ga(T32, T33))
pI_in_ggaa(T50, T51, T52, X125) → U12_ggaa(T50, T51, T52, X125, ackermannH_in_gga(s(T50), T51, T52))
U10_gaa(T32, T33, X83, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, X83, ackermannH_in_gga(T32, T33, X83))
U12_ggaa(T50, T51, T52, X125, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, X125, ackermannH_in_gga(T50, T52, X125))
U11_gaa(T32, T33, X83, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)
U13_ggaa(T50, T51, T52, X125, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)

The argument filtering Pi contains the following mapping:
0  =  0
s(x1)  =  s(x1)
ackermannE_in_ga(x1, x2)  =  ackermannE_in_ga(x1)
U4_ga(x1, x2, x3)  =  U4_ga(x1, x3)
ackermannF_in_ga(x1, x2)  =  ackermannF_in_ga(x1)
ackermannF_out_ga(x1, x2)  =  ackermannF_out_ga(x1, x2)
U5_ga(x1, x2, x3)  =  U5_ga(x1, x3)
pG_in_gaa(x1, x2, x3)  =  pG_in_gaa(x1)
U10_gaa(x1, x2, x3, x4)  =  U10_gaa(x1, x4)
ackermannE_out_ga(x1, x2)  =  ackermannE_out_ga(x1, x2)
U11_gaa(x1, x2, x3, x4)  =  U11_gaa(x1, x2, x4)
ackermannH_in_gga(x1, x2, x3)  =  ackermannH_in_gga(x1, x2)
ackermannH_out_gga(x1, x2, x3)  =  ackermannH_out_gga(x1, x2, x3)
U6_gga(x1, x2, x3)  =  U6_gga(x1, x3)
U7_gga(x1, x2, x3, x4)  =  U7_gga(x1, x2, x4)
pI_in_ggaa(x1, x2, x3, x4)  =  pI_in_ggaa(x1, x2)
U12_ggaa(x1, x2, x3, x4, x5)  =  U12_ggaa(x1, x2, x5)
U13_ggaa(x1, x2, x3, x4, x5)  =  U13_ggaa(x1, x2, x3, x5)
pI_out_ggaa(x1, x2, x3, x4)  =  pI_out_ggaa(x1, x2, x3, x4)
pG_out_gaa(x1, x2, x3)  =  pG_out_gaa(x1, x2, x3)
ACKERMANNA_IN_GGA(x1, x2, x3)  =  ACKERMANNA_IN_GGA(x1, x2)
PB_IN_GAA(x1, x2, x3)  =  PB_IN_GAA(x1)
U8_GAA(x1, x2, x3, x4)  =  U8_GAA(x1, x4)
PC_IN_GAA(x1, x2, x3)  =  PC_IN_GAA(x1)
U14_GAA(x1, x2, x3, x4)  =  U14_GAA(x1, x4)
PD_IN_GGAAA(x1, x2, x3, x4, x5)  =  PD_IN_GGAAA(x1, x2)
U16_GGAAA(x1, x2, x3, x4, x5, x6)  =  U16_GGAAA(x1, x2, x6)
PJ_IN_GGAA(x1, x2, x3, x4)  =  PJ_IN_GGAA(x1, x2)
U18_GGAA(x1, x2, x3, x4, x5)  =  U18_GGAA(x1, x2, x5)

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

(27) PiDPToQDPProof (SOUND transformation)

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

(28) Obligation:

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

ACKERMANNA_IN_GGA(s(s(T20)), 0) → PB_IN_GAA(T20)
PB_IN_GAA(T20) → U8_GAA(T20, ackermannE_in_ga(T20))
U8_GAA(T20, ackermannE_out_ga(T20, T23)) → ACKERMANNA_IN_GGA(T20, T23)
ACKERMANNA_IN_GGA(s(T70), s(0)) → PC_IN_GAA(T70)
PC_IN_GAA(T70) → U14_GAA(T70, ackermannF_in_ga(T70))
U14_GAA(T70, ackermannF_out_ga(T70, T71)) → ACKERMANNA_IN_GGA(T70, T71)
ACKERMANNA_IN_GGA(s(T78), s(s(T79))) → PD_IN_GGAAA(T78, T79)
PD_IN_GGAAA(T78, T79) → U16_GGAAA(T78, T79, ackermannH_in_gga(s(T78), T79))
U16_GGAAA(T78, T79, ackermannH_out_gga(s(T78), T79, T80)) → PJ_IN_GGAA(T78, T80)
PJ_IN_GGAA(T78, T80) → U18_GGAA(T78, T80, ackermannH_in_gga(T78, T80))
U18_GGAA(T78, T80, ackermannH_out_gga(T78, T80, T83)) → ACKERMANNA_IN_GGA(T78, T83)

The TRS R consists of the following rules:

ackermannE_in_ga(T28) → U4_ga(T28, ackermannF_in_ga(T28))
ackermannF_in_ga(0) → ackermannF_out_ga(0, s(s(0)))
ackermannF_in_ga(s(T32)) → U5_ga(T32, pG_in_gaa(T32))
ackermannH_in_gga(s(T45), 0) → U6_gga(T45, ackermannF_in_ga(T45))
ackermannH_in_gga(s(T50), s(T51)) → U7_gga(T50, T51, pI_in_ggaa(T50, T51))
ackermannH_in_gga(0, T40) → ackermannH_out_gga(0, T40, s(T40))
U4_ga(T28, ackermannF_out_ga(T28, X60)) → ackermannE_out_ga(T28, X60)
U5_ga(T32, pG_out_gaa(T32, X82, X83)) → ackermannF_out_ga(s(T32), X83)
U6_gga(T45, ackermannF_out_ga(T45, X109)) → ackermannH_out_gga(s(T45), 0, X109)
U7_gga(T50, T51, pI_out_ggaa(T50, T51, X124, X125)) → ackermannH_out_gga(s(T50), s(T51), X125)
pG_in_gaa(T32) → U10_gaa(T32, ackermannE_in_ga(T32))
pI_in_ggaa(T50, T51) → U12_ggaa(T50, T51, ackermannH_in_gga(s(T50), T51))
U10_gaa(T32, ackermannE_out_ga(T32, T33)) → U11_gaa(T32, T33, ackermannH_in_gga(T32, T33))
U12_ggaa(T50, T51, ackermannH_out_gga(s(T50), T51, T52)) → U13_ggaa(T50, T51, T52, ackermannH_in_gga(T50, T52))
U11_gaa(T32, T33, ackermannH_out_gga(T32, T33, X83)) → pG_out_gaa(T32, T33, X83)
U13_ggaa(T50, T51, T52, ackermannH_out_gga(T50, T52, X125)) → pI_out_ggaa(T50, T51, T52, X125)

The set Q consists of the following terms:

ackermannE_in_ga(x0)
ackermannF_in_ga(x0)
ackermannH_in_gga(x0, x1)
U4_ga(x0, x1)
U5_ga(x0, x1)
U6_gga(x0, x1)
U7_gga(x0, x1, x2)
pG_in_gaa(x0)
pI_in_ggaa(x0, x1)
U10_gaa(x0, x1)
U12_ggaa(x0, x1, x2)
U11_gaa(x0, x1, x2)
U13_ggaa(x0, x1, x2, x3)

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

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

  • PB_IN_GAA(T20) → U8_GAA(T20, ackermannE_in_ga(T20))
    The graph contains the following edges 1 >= 1

  • U8_GAA(T20, ackermannE_out_ga(T20, T23)) → ACKERMANNA_IN_GGA(T20, T23)
    The graph contains the following edges 1 >= 1, 2 > 1, 2 > 2

  • ACKERMANNA_IN_GGA(s(s(T20)), 0) → PB_IN_GAA(T20)
    The graph contains the following edges 1 > 1

  • PC_IN_GAA(T70) → U14_GAA(T70, ackermannF_in_ga(T70))
    The graph contains the following edges 1 >= 1

  • U14_GAA(T70, ackermannF_out_ga(T70, T71)) → ACKERMANNA_IN_GGA(T70, T71)
    The graph contains the following edges 1 >= 1, 2 > 1, 2 > 2

  • U18_GGAA(T78, T80, ackermannH_out_gga(T78, T80, T83)) → ACKERMANNA_IN_GGA(T78, T83)
    The graph contains the following edges 1 >= 1, 3 > 1, 3 > 2

  • ACKERMANNA_IN_GGA(s(T70), s(0)) → PC_IN_GAA(T70)
    The graph contains the following edges 1 > 1

  • ACKERMANNA_IN_GGA(s(T78), s(s(T79))) → PD_IN_GGAAA(T78, T79)
    The graph contains the following edges 1 > 1, 2 > 2

  • PD_IN_GGAAA(T78, T79) → U16_GGAAA(T78, T79, ackermannH_in_gga(s(T78), T79))
    The graph contains the following edges 1 >= 1, 2 >= 2

  • U16_GGAAA(T78, T79, ackermannH_out_gga(s(T78), T79, T80)) → PJ_IN_GGAA(T78, T80)
    The graph contains the following edges 1 >= 1, 3 > 1, 3 > 2

  • PJ_IN_GGAA(T78, T80) → U18_GGAA(T78, T80, ackermannH_in_gga(T78, T80))
    The graph contains the following edges 1 >= 1, 2 >= 2

(30) YES