↳ PROLOG
↳ PrologToPiTRSProof
With regard to the inferred argument filtering the predicates were used in the following modes:
sum3: (b,b,f)
add3: (b,b,f)
Transforming PROLOG into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:
sum_3_in_gga3([]_0, []_0, []_0) -> sum_3_out_gga3([]_0, []_0, []_0)
sum_3_in_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
add_3_in_gga3(0_0, X, X) -> add_3_out_gga3(0_0, X, X)
add_3_in_gga3(s_11(X), Y, s_11(Z)) -> if_add_3_in_1_gga4(X, Y, Z, add_3_in_gga3(X, Y, Z))
if_add_3_in_1_gga4(X, Y, Z, add_3_out_gga3(X, Y, Z)) -> add_3_out_gga3(s_11(X), Y, s_11(Z))
if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_in_gga3(Y1, Y2, Y3))
if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_out_gga3(Y1, Y2, Y3)) -> sum_3_out_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3))
Infinitary Constructor Rewriting Termination of PiTRS implies Termination of PROLOG
↳ PROLOG
↳ PrologToPiTRSProof
↳ PiTRS
↳ DependencyPairsProof
sum_3_in_gga3([]_0, []_0, []_0) -> sum_3_out_gga3([]_0, []_0, []_0)
sum_3_in_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
add_3_in_gga3(0_0, X, X) -> add_3_out_gga3(0_0, X, X)
add_3_in_gga3(s_11(X), Y, s_11(Z)) -> if_add_3_in_1_gga4(X, Y, Z, add_3_in_gga3(X, Y, Z))
if_add_3_in_1_gga4(X, Y, Z, add_3_out_gga3(X, Y, Z)) -> add_3_out_gga3(s_11(X), Y, s_11(Z))
if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_in_gga3(Y1, Y2, Y3))
if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_out_gga3(Y1, Y2, Y3)) -> sum_3_out_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3))
SUM_3_IN_GGA3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
SUM_3_IN_GGA3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> ADD_3_IN_GGA3(X1, X2, X3)
ADD_3_IN_GGA3(s_11(X), Y, s_11(Z)) -> IF_ADD_3_IN_1_GGA4(X, Y, Z, add_3_in_gga3(X, Y, Z))
ADD_3_IN_GGA3(s_11(X), Y, s_11(Z)) -> ADD_3_IN_GGA3(X, Y, Z)
IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> IF_SUM_3_IN_2_GGA7(X1, Y1, X2, Y2, X3, Y3, sum_3_in_gga3(Y1, Y2, Y3))
IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> SUM_3_IN_GGA3(Y1, Y2, Y3)
sum_3_in_gga3([]_0, []_0, []_0) -> sum_3_out_gga3([]_0, []_0, []_0)
sum_3_in_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
add_3_in_gga3(0_0, X, X) -> add_3_out_gga3(0_0, X, X)
add_3_in_gga3(s_11(X), Y, s_11(Z)) -> if_add_3_in_1_gga4(X, Y, Z, add_3_in_gga3(X, Y, Z))
if_add_3_in_1_gga4(X, Y, Z, add_3_out_gga3(X, Y, Z)) -> add_3_out_gga3(s_11(X), Y, s_11(Z))
if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_in_gga3(Y1, Y2, Y3))
if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_out_gga3(Y1, Y2, Y3)) -> sum_3_out_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3))
↳ PROLOG
↳ PrologToPiTRSProof
↳ PiTRS
↳ DependencyPairsProof
↳ PiDP
↳ DependencyGraphProof
SUM_3_IN_GGA3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
SUM_3_IN_GGA3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> ADD_3_IN_GGA3(X1, X2, X3)
ADD_3_IN_GGA3(s_11(X), Y, s_11(Z)) -> IF_ADD_3_IN_1_GGA4(X, Y, Z, add_3_in_gga3(X, Y, Z))
ADD_3_IN_GGA3(s_11(X), Y, s_11(Z)) -> ADD_3_IN_GGA3(X, Y, Z)
IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> IF_SUM_3_IN_2_GGA7(X1, Y1, X2, Y2, X3, Y3, sum_3_in_gga3(Y1, Y2, Y3))
IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> SUM_3_IN_GGA3(Y1, Y2, Y3)
sum_3_in_gga3([]_0, []_0, []_0) -> sum_3_out_gga3([]_0, []_0, []_0)
sum_3_in_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
add_3_in_gga3(0_0, X, X) -> add_3_out_gga3(0_0, X, X)
add_3_in_gga3(s_11(X), Y, s_11(Z)) -> if_add_3_in_1_gga4(X, Y, Z, add_3_in_gga3(X, Y, Z))
if_add_3_in_1_gga4(X, Y, Z, add_3_out_gga3(X, Y, Z)) -> add_3_out_gga3(s_11(X), Y, s_11(Z))
if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_in_gga3(Y1, Y2, Y3))
if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_out_gga3(Y1, Y2, Y3)) -> sum_3_out_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3))
↳ PROLOG
↳ PrologToPiTRSProof
↳ PiTRS
↳ DependencyPairsProof
↳ PiDP
↳ DependencyGraphProof
↳ AND
↳ PiDP
↳ UsableRulesProof
↳ PiDP
ADD_3_IN_GGA3(s_11(X), Y, s_11(Z)) -> ADD_3_IN_GGA3(X, Y, Z)
sum_3_in_gga3([]_0, []_0, []_0) -> sum_3_out_gga3([]_0, []_0, []_0)
sum_3_in_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
add_3_in_gga3(0_0, X, X) -> add_3_out_gga3(0_0, X, X)
add_3_in_gga3(s_11(X), Y, s_11(Z)) -> if_add_3_in_1_gga4(X, Y, Z, add_3_in_gga3(X, Y, Z))
if_add_3_in_1_gga4(X, Y, Z, add_3_out_gga3(X, Y, Z)) -> add_3_out_gga3(s_11(X), Y, s_11(Z))
if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_in_gga3(Y1, Y2, Y3))
if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_out_gga3(Y1, Y2, Y3)) -> sum_3_out_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3))
↳ PROLOG
↳ PrologToPiTRSProof
↳ PiTRS
↳ DependencyPairsProof
↳ PiDP
↳ DependencyGraphProof
↳ AND
↳ PiDP
↳ UsableRulesProof
↳ PiDP
↳ PiDPToQDPProof
↳ PiDP
ADD_3_IN_GGA3(s_11(X), Y, s_11(Z)) -> ADD_3_IN_GGA3(X, Y, Z)
↳ PROLOG
↳ PrologToPiTRSProof
↳ PiTRS
↳ DependencyPairsProof
↳ PiDP
↳ DependencyGraphProof
↳ AND
↳ PiDP
↳ UsableRulesProof
↳ PiDP
↳ PiDPToQDPProof
↳ QDP
↳ QDPSizeChangeProof
↳ PiDP
ADD_3_IN_GGA2(s_11(X), Y) -> ADD_3_IN_GGA2(X, Y)
From the DPs we obtained the following set of size-change graphs:
↳ PROLOG
↳ PrologToPiTRSProof
↳ PiTRS
↳ DependencyPairsProof
↳ PiDP
↳ DependencyGraphProof
↳ AND
↳ PiDP
↳ PiDP
↳ UsableRulesProof
IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> SUM_3_IN_GGA3(Y1, Y2, Y3)
SUM_3_IN_GGA3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
sum_3_in_gga3([]_0, []_0, []_0) -> sum_3_out_gga3([]_0, []_0, []_0)
sum_3_in_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
add_3_in_gga3(0_0, X, X) -> add_3_out_gga3(0_0, X, X)
add_3_in_gga3(s_11(X), Y, s_11(Z)) -> if_add_3_in_1_gga4(X, Y, Z, add_3_in_gga3(X, Y, Z))
if_add_3_in_1_gga4(X, Y, Z, add_3_out_gga3(X, Y, Z)) -> add_3_out_gga3(s_11(X), Y, s_11(Z))
if_sum_3_in_1_gga7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_in_gga3(Y1, Y2, Y3))
if_sum_3_in_2_gga7(X1, Y1, X2, Y2, X3, Y3, sum_3_out_gga3(Y1, Y2, Y3)) -> sum_3_out_gga3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3))
↳ PROLOG
↳ PrologToPiTRSProof
↳ PiTRS
↳ DependencyPairsProof
↳ PiDP
↳ DependencyGraphProof
↳ AND
↳ PiDP
↳ PiDP
↳ UsableRulesProof
↳ PiDP
↳ PiDPToQDPProof
IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_out_gga3(X1, X2, X3)) -> SUM_3_IN_GGA3(Y1, Y2, Y3)
SUM_3_IN_GGA3(._22(X1, Y1), ._22(X2, Y2), ._22(X3, Y3)) -> IF_SUM_3_IN_1_GGA7(X1, Y1, X2, Y2, X3, Y3, add_3_in_gga3(X1, X2, X3))
add_3_in_gga3(0_0, X, X) -> add_3_out_gga3(0_0, X, X)
add_3_in_gga3(s_11(X), Y, s_11(Z)) -> if_add_3_in_1_gga4(X, Y, Z, add_3_in_gga3(X, Y, Z))
if_add_3_in_1_gga4(X, Y, Z, add_3_out_gga3(X, Y, Z)) -> add_3_out_gga3(s_11(X), Y, s_11(Z))
↳ PROLOG
↳ PrologToPiTRSProof
↳ PiTRS
↳ DependencyPairsProof
↳ PiDP
↳ DependencyGraphProof
↳ AND
↳ PiDP
↳ PiDP
↳ UsableRulesProof
↳ PiDP
↳ PiDPToQDPProof
↳ QDP
↳ QDPSizeChangeProof
IF_SUM_3_IN_1_GGA3(Y1, Y2, add_3_out_gga1(X3)) -> SUM_3_IN_GGA2(Y1, Y2)
SUM_3_IN_GGA2(._22(X1, Y1), ._22(X2, Y2)) -> IF_SUM_3_IN_1_GGA3(Y1, Y2, add_3_in_gga2(X1, X2))
add_3_in_gga2(0_0, X) -> add_3_out_gga1(X)
add_3_in_gga2(s_11(X), Y) -> if_add_3_in_1_gga1(add_3_in_gga2(X, Y))
if_add_3_in_1_gga1(add_3_out_gga1(Z)) -> add_3_out_gga1(s_11(Z))
add_3_in_gga2(x0, x1)
if_add_3_in_1_gga1(x0)
From the DPs we obtained the following set of size-change graphs: