0 Prolog
↳1 PrologToDTProblemTransformerProof (⇐)
↳2 TRIPLES
↳3 TriplesToPiDPProof (⇐)
↳4 PiDP
↳5 DependencyGraphProof (⇔)
↳6 AND
↳7 PiDP
↳8 UsableRulesProof (⇔)
↳9 PiDP
↳10 PiDPToQDPProof (⇔)
↳11 QDP
↳12 QDPSizeChangeProof (⇔)
↳13 YES
↳14 PiDP
↳15 UsableRulesProof (⇔)
↳16 PiDP
↳17 PiDPToQDPProof (⇔)
↳18 QDP
↳19 QDPSizeChangeProof (⇔)
↳20 YES
↳21 PiDP
↳22 PiDPToQDPProof (⇔)
↳23 QDP
↳24 MRRProof (⇔)
↳25 QDP
↳26 MRRProof (⇔)
↳27 QDP
↳28 DependencyGraphProof (⇔)
↳29 TRUE
ORDERED1_IN_G(.(s(T72), .(T77, T48))) → U4_G(T72, T77, T48, less80_in_gg(T72, T77))
ORDERED1_IN_G(.(s(T72), .(T77, T48))) → LESS80_IN_GG(T72, T77)
LESS80_IN_GG(s(T99), 0) → U2_GG(T99, less107_in_g(T99))
LESS80_IN_GG(s(T99), 0) → LESS107_IN_G(T99)
LESS107_IN_G(s(T112)) → U1_G(T112, less107_in_g(T112))
LESS107_IN_G(s(T112)) → LESS107_IN_G(T112)
LESS80_IN_GG(s(T99), s(T118)) → U3_GG(T99, T118, less80_in_gg(T99, T118))
LESS80_IN_GG(s(T99), s(T118)) → LESS80_IN_GG(T99, T118)
ORDERED1_IN_G(.(T31, .(T47, T48))) → U5_G(T31, T47, T48, lessc53_in_gg(T31, T47))
U5_G(T31, T47, T48, lessc53_out_gg(T31, T47)) → U6_G(T31, T47, T48, ordered1_in_g(.(T47, T48)))
U5_G(T31, T47, T48, lessc53_out_gg(T31, T47)) → ORDERED1_IN_G(.(T47, T48))
lessc53_in_gg(0, T57) → lessc53_out_gg(0, T57)
lessc53_in_gg(s(T72), T77) → U13_gg(T72, T77, lessc80_in_gg(T72, T77))
lessc80_in_gg(0, s(T84)) → lessc80_out_gg(0, s(T84))
lessc80_in_gg(s(T99), 0) → U11_gg(T99, lessc107_in_g(T99))
lessc107_in_g(s(T112)) → U10_g(T112, lessc107_in_g(T112))
U10_g(T112, lessc107_out_g(T112)) → lessc107_out_g(s(T112))
U11_gg(T99, lessc107_out_g(T99)) → lessc80_out_gg(s(T99), 0)
lessc80_in_gg(s(T99), s(T118)) → U12_gg(T99, T118, lessc80_in_gg(T99, T118))
U12_gg(T99, T118, lessc80_out_gg(T99, T118)) → lessc80_out_gg(s(T99), s(T118))
U13_gg(T72, T77, lessc80_out_gg(T72, T77)) → lessc53_out_gg(s(T72), T77)
Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES
ORDERED1_IN_G(.(s(T72), .(T77, T48))) → U4_G(T72, T77, T48, less80_in_gg(T72, T77))
ORDERED1_IN_G(.(s(T72), .(T77, T48))) → LESS80_IN_GG(T72, T77)
LESS80_IN_GG(s(T99), 0) → U2_GG(T99, less107_in_g(T99))
LESS80_IN_GG(s(T99), 0) → LESS107_IN_G(T99)
LESS107_IN_G(s(T112)) → U1_G(T112, less107_in_g(T112))
LESS107_IN_G(s(T112)) → LESS107_IN_G(T112)
LESS80_IN_GG(s(T99), s(T118)) → U3_GG(T99, T118, less80_in_gg(T99, T118))
LESS80_IN_GG(s(T99), s(T118)) → LESS80_IN_GG(T99, T118)
ORDERED1_IN_G(.(T31, .(T47, T48))) → U5_G(T31, T47, T48, lessc53_in_gg(T31, T47))
U5_G(T31, T47, T48, lessc53_out_gg(T31, T47)) → U6_G(T31, T47, T48, ordered1_in_g(.(T47, T48)))
U5_G(T31, T47, T48, lessc53_out_gg(T31, T47)) → ORDERED1_IN_G(.(T47, T48))
lessc53_in_gg(0, T57) → lessc53_out_gg(0, T57)
lessc53_in_gg(s(T72), T77) → U13_gg(T72, T77, lessc80_in_gg(T72, T77))
lessc80_in_gg(0, s(T84)) → lessc80_out_gg(0, s(T84))
lessc80_in_gg(s(T99), 0) → U11_gg(T99, lessc107_in_g(T99))
lessc107_in_g(s(T112)) → U10_g(T112, lessc107_in_g(T112))
U10_g(T112, lessc107_out_g(T112)) → lessc107_out_g(s(T112))
U11_gg(T99, lessc107_out_g(T99)) → lessc80_out_gg(s(T99), 0)
lessc80_in_gg(s(T99), s(T118)) → U12_gg(T99, T118, lessc80_in_gg(T99, T118))
U12_gg(T99, T118, lessc80_out_gg(T99, T118)) → lessc80_out_gg(s(T99), s(T118))
U13_gg(T72, T77, lessc80_out_gg(T72, T77)) → lessc53_out_gg(s(T72), T77)
LESS107_IN_G(s(T112)) → LESS107_IN_G(T112)
lessc53_in_gg(0, T57) → lessc53_out_gg(0, T57)
lessc53_in_gg(s(T72), T77) → U13_gg(T72, T77, lessc80_in_gg(T72, T77))
lessc80_in_gg(0, s(T84)) → lessc80_out_gg(0, s(T84))
lessc80_in_gg(s(T99), 0) → U11_gg(T99, lessc107_in_g(T99))
lessc107_in_g(s(T112)) → U10_g(T112, lessc107_in_g(T112))
U10_g(T112, lessc107_out_g(T112)) → lessc107_out_g(s(T112))
U11_gg(T99, lessc107_out_g(T99)) → lessc80_out_gg(s(T99), 0)
lessc80_in_gg(s(T99), s(T118)) → U12_gg(T99, T118, lessc80_in_gg(T99, T118))
U12_gg(T99, T118, lessc80_out_gg(T99, T118)) → lessc80_out_gg(s(T99), s(T118))
U13_gg(T72, T77, lessc80_out_gg(T72, T77)) → lessc53_out_gg(s(T72), T77)
LESS107_IN_G(s(T112)) → LESS107_IN_G(T112)
LESS107_IN_G(s(T112)) → LESS107_IN_G(T112)
From the DPs we obtained the following set of size-change graphs:
LESS80_IN_GG(s(T99), s(T118)) → LESS80_IN_GG(T99, T118)
lessc53_in_gg(0, T57) → lessc53_out_gg(0, T57)
lessc53_in_gg(s(T72), T77) → U13_gg(T72, T77, lessc80_in_gg(T72, T77))
lessc80_in_gg(0, s(T84)) → lessc80_out_gg(0, s(T84))
lessc80_in_gg(s(T99), 0) → U11_gg(T99, lessc107_in_g(T99))
lessc107_in_g(s(T112)) → U10_g(T112, lessc107_in_g(T112))
U10_g(T112, lessc107_out_g(T112)) → lessc107_out_g(s(T112))
U11_gg(T99, lessc107_out_g(T99)) → lessc80_out_gg(s(T99), 0)
lessc80_in_gg(s(T99), s(T118)) → U12_gg(T99, T118, lessc80_in_gg(T99, T118))
U12_gg(T99, T118, lessc80_out_gg(T99, T118)) → lessc80_out_gg(s(T99), s(T118))
U13_gg(T72, T77, lessc80_out_gg(T72, T77)) → lessc53_out_gg(s(T72), T77)
LESS80_IN_GG(s(T99), s(T118)) → LESS80_IN_GG(T99, T118)
LESS80_IN_GG(s(T99), s(T118)) → LESS80_IN_GG(T99, T118)
From the DPs we obtained the following set of size-change graphs:
ORDERED1_IN_G(.(T31, .(T47, T48))) → U5_G(T31, T47, T48, lessc53_in_gg(T31, T47))
U5_G(T31, T47, T48, lessc53_out_gg(T31, T47)) → ORDERED1_IN_G(.(T47, T48))
lessc53_in_gg(0, T57) → lessc53_out_gg(0, T57)
lessc53_in_gg(s(T72), T77) → U13_gg(T72, T77, lessc80_in_gg(T72, T77))
lessc80_in_gg(0, s(T84)) → lessc80_out_gg(0, s(T84))
lessc80_in_gg(s(T99), 0) → U11_gg(T99, lessc107_in_g(T99))
lessc107_in_g(s(T112)) → U10_g(T112, lessc107_in_g(T112))
U10_g(T112, lessc107_out_g(T112)) → lessc107_out_g(s(T112))
U11_gg(T99, lessc107_out_g(T99)) → lessc80_out_gg(s(T99), 0)
lessc80_in_gg(s(T99), s(T118)) → U12_gg(T99, T118, lessc80_in_gg(T99, T118))
U12_gg(T99, T118, lessc80_out_gg(T99, T118)) → lessc80_out_gg(s(T99), s(T118))
U13_gg(T72, T77, lessc80_out_gg(T72, T77)) → lessc53_out_gg(s(T72), T77)
ORDERED1_IN_G(.(T31, .(T47, T48))) → U5_G(T31, T47, T48, lessc53_in_gg(T31, T47))
U5_G(T31, T47, T48, lessc53_out_gg(T31, T47)) → ORDERED1_IN_G(.(T47, T48))
lessc53_in_gg(0, T57) → lessc53_out_gg(0, T57)
lessc53_in_gg(s(T72), T77) → U13_gg(T72, T77, lessc80_in_gg(T72, T77))
lessc80_in_gg(0, s(T84)) → lessc80_out_gg(0, s(T84))
lessc80_in_gg(s(T99), 0) → U11_gg(T99, lessc107_in_g(T99))
lessc107_in_g(s(T112)) → U10_g(T112, lessc107_in_g(T112))
U10_g(T112, lessc107_out_g(T112)) → lessc107_out_g(s(T112))
U11_gg(T99, lessc107_out_g(T99)) → lessc80_out_gg(s(T99), 0)
lessc80_in_gg(s(T99), s(T118)) → U12_gg(T99, T118, lessc80_in_gg(T99, T118))
U12_gg(T99, T118, lessc80_out_gg(T99, T118)) → lessc80_out_gg(s(T99), s(T118))
U13_gg(T72, T77, lessc80_out_gg(T72, T77)) → lessc53_out_gg(s(T72), T77)
lessc53_in_gg(x0, x1)
lessc80_in_gg(x0, x1)
lessc107_in_g(x0)
U10_g(x0, x1)
U11_gg(x0, x1)
U12_gg(x0, x1, x2)
U13_gg(x0, x1, x2)
U11_gg(T99, lessc107_out_g(T99)) → lessc80_out_gg(s(T99), 0)
POL(.(x1, x2)) = 2·x1 + x2
POL(0) = 0
POL(ORDERED1_IN_G(x1)) = 2·x1
POL(U10_g(x1, x2)) = x1 + x2
POL(U11_gg(x1, x2)) = x1 + x2
POL(U12_gg(x1, x2, x3)) = x1 + x2 + x3
POL(U13_gg(x1, x2, x3)) = x1 + x2 + x3
POL(U5_G(x1, x2, x3, x4)) = 2·x1 + 2·x2 + 2·x3 + x4
POL(lessc107_in_g(x1)) = x1
POL(lessc107_out_g(x1)) = 1 + x1
POL(lessc53_in_gg(x1, x2)) = x1 + 2·x2
POL(lessc53_out_gg(x1, x2)) = x1 + 2·x2
POL(lessc80_in_gg(x1, x2)) = x1 + x2
POL(lessc80_out_gg(x1, x2)) = x1 + x2
POL(s(x1)) = 2·x1
ORDERED1_IN_G(.(T31, .(T47, T48))) → U5_G(T31, T47, T48, lessc53_in_gg(T31, T47))
U5_G(T31, T47, T48, lessc53_out_gg(T31, T47)) → ORDERED1_IN_G(.(T47, T48))
lessc53_in_gg(0, T57) → lessc53_out_gg(0, T57)
lessc53_in_gg(s(T72), T77) → U13_gg(T72, T77, lessc80_in_gg(T72, T77))
lessc80_in_gg(0, s(T84)) → lessc80_out_gg(0, s(T84))
lessc80_in_gg(s(T99), 0) → U11_gg(T99, lessc107_in_g(T99))
lessc107_in_g(s(T112)) → U10_g(T112, lessc107_in_g(T112))
U10_g(T112, lessc107_out_g(T112)) → lessc107_out_g(s(T112))
lessc80_in_gg(s(T99), s(T118)) → U12_gg(T99, T118, lessc80_in_gg(T99, T118))
U12_gg(T99, T118, lessc80_out_gg(T99, T118)) → lessc80_out_gg(s(T99), s(T118))
U13_gg(T72, T77, lessc80_out_gg(T72, T77)) → lessc53_out_gg(s(T72), T77)
lessc53_in_gg(x0, x1)
lessc80_in_gg(x0, x1)
lessc107_in_g(x0)
U10_g(x0, x1)
U11_gg(x0, x1)
U12_gg(x0, x1, x2)
U13_gg(x0, x1, x2)
ORDERED1_IN_G(.(T31, .(T47, T48))) → U5_G(T31, T47, T48, lessc53_in_gg(T31, T47))
POL(.(x1, x2)) = 1 + 2·x1 + 2·x2
POL(0) = 0
POL(ORDERED1_IN_G(x1)) = x1
POL(U10_g(x1, x2)) = x1 + x2
POL(U11_gg(x1, x2)) = x1 + x2
POL(U12_gg(x1, x2, x3)) = x1 + x2 + x3
POL(U13_gg(x1, x2, x3)) = x1 + x2 + x3
POL(U5_G(x1, x2, x3, x4)) = 1 + x1 + 2·x2 + 2·x3 + x4
POL(lessc107_in_g(x1)) = x1
POL(lessc107_out_g(x1)) = x1
POL(lessc53_in_gg(x1, x2)) = x1 + 2·x2
POL(lessc53_out_gg(x1, x2)) = x1 + 2·x2
POL(lessc80_in_gg(x1, x2)) = x1 + x2
POL(lessc80_out_gg(x1, x2)) = x1 + x2
POL(s(x1)) = 2·x1
U5_G(T31, T47, T48, lessc53_out_gg(T31, T47)) → ORDERED1_IN_G(.(T47, T48))
lessc53_in_gg(0, T57) → lessc53_out_gg(0, T57)
lessc53_in_gg(s(T72), T77) → U13_gg(T72, T77, lessc80_in_gg(T72, T77))
lessc80_in_gg(0, s(T84)) → lessc80_out_gg(0, s(T84))
lessc80_in_gg(s(T99), 0) → U11_gg(T99, lessc107_in_g(T99))
lessc107_in_g(s(T112)) → U10_g(T112, lessc107_in_g(T112))
U10_g(T112, lessc107_out_g(T112)) → lessc107_out_g(s(T112))
lessc80_in_gg(s(T99), s(T118)) → U12_gg(T99, T118, lessc80_in_gg(T99, T118))
U12_gg(T99, T118, lessc80_out_gg(T99, T118)) → lessc80_out_gg(s(T99), s(T118))
U13_gg(T72, T77, lessc80_out_gg(T72, T77)) → lessc53_out_gg(s(T72), T77)
lessc53_in_gg(x0, x1)
lessc80_in_gg(x0, x1)
lessc107_in_g(x0)
U10_g(x0, x1)
U11_gg(x0, x1)
U12_gg(x0, x1, x2)
U13_gg(x0, x1, x2)