0 Prolog
↳1 PrologToPrologProblemTransformerProof (⇒, 276 ms)
↳2 Prolog
↳3 PrologToPiTRSProof (⇒, 5 ms)
↳4 PiTRS
↳5 DependencyPairsProof (⇔, 0 ms)
↳6 PiDP
↳7 DependencyGraphProof (⇔, 0 ms)
↳8 AND
↳9 PiDP
↳10 UsableRulesProof (⇔, 0 ms)
↳11 PiDP
↳12 PiDPToQDPProof (⇒, 6 ms)
↳13 QDP
↳14 QDPSizeChangeProof (⇔, 0 ms)
↳15 YES
↳16 PiDP
↳17 UsableRulesProof (⇔, 0 ms)
↳18 PiDP
↳19 PiDPToQDPProof (⇒, 0 ms)
↳20 QDP
↳21 QDPOrderProof (⇔, 93 ms)
↳22 QDP
↳23 DependencyGraphProof (⇔, 0 ms)
↳24 TRUE
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)
Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
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)
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)
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)
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)
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)
MINUSA_IN_GGA(s(T167), s(T168), X274) → MINUSA_IN_GGA(T167, T168, X274)
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)
MINUSA_IN_GGA(s(T167), s(T168), X274) → MINUSA_IN_GGA(T167, T168, X274)
MINUSA_IN_GGA(s(T167), s(T168)) → MINUSA_IN_GGA(T167, T168)
From the DPs we obtained the following set of size-change graphs:
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)
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)
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)
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)
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)
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)
minusB_in_gga(x0, x1)
U2_gga(x0)
minusA_in_gga(x0, x1)
U1_gga(x0)
The following pairs can be oriented strictly and are deleted.
The remaining pairs can at least be oriented weakly.
U4_GGAA(T135, minusB_out_gga(T144)) → DIVC_IN_GGAA(T144, T135)
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
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)
DIVC_IN_GGAA(T121, T135) → U4_GGAA(T135, minusB_in_gga(T121, T135))
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)
minusB_in_gga(x0, x1)
U2_gga(x0)
minusA_in_gga(x0, x1)
U1_gga(x0)