(0) Obligation:
Clauses:
fl([], [], 0).
fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z)).
append([], X, X).
append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs).
Queries:
fl(a,g,a).
(1) PrologToPiTRSProof (SOUND transformation)
We use the technique of [LOPSTR]. With regard to the inferred argument filtering the predicates were used in the following modes:
fl_in: (f,b,f)
append_in: (f,f,b)
Transforming
Prolog into the following
Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x2,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x3,
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2,
x3)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x4,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x3,
x5)
s(
x1) =
s(
x1)
Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
(2) Obligation:
Pi-finite rewrite system:
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x2,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x3,
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2,
x3)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x4,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x3,
x5)
s(
x1) =
s(
x1)
(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:
FL_IN_AGA(.(E, X), R, s(Z)) → U1_AGA(E, X, R, Z, append_in_aag(E, Y, R))
FL_IN_AGA(.(E, X), R, s(Z)) → APPEND_IN_AAG(E, Y, R)
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → APPEND_IN_AAG(Xs, Ys, Zs)
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z))
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → FL_IN_AGA(X, Y, Z)
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x2,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x3,
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2,
x3)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x4,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x3,
x5)
s(
x1) =
s(
x1)
FL_IN_AGA(
x1,
x2,
x3) =
FL_IN_AGA(
x2)
U1_AGA(
x1,
x2,
x3,
x4,
x5) =
U1_AGA(
x3,
x5)
APPEND_IN_AAG(
x1,
x2,
x3) =
APPEND_IN_AAG(
x3)
U3_AAG(
x1,
x2,
x3,
x4,
x5) =
U3_AAG(
x1,
x4,
x5)
U2_AGA(
x1,
x2,
x3,
x4,
x5) =
U2_AGA(
x1,
x3,
x5)
We have to consider all (P,R,Pi)-chains
(4) Obligation:
Pi DP problem:
The TRS P consists of the following rules:
FL_IN_AGA(.(E, X), R, s(Z)) → U1_AGA(E, X, R, Z, append_in_aag(E, Y, R))
FL_IN_AGA(.(E, X), R, s(Z)) → APPEND_IN_AAG(E, Y, R)
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → APPEND_IN_AAG(Xs, Ys, Zs)
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z))
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → FL_IN_AGA(X, Y, Z)
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x2,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x3,
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2,
x3)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x4,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x3,
x5)
s(
x1) =
s(
x1)
FL_IN_AGA(
x1,
x2,
x3) =
FL_IN_AGA(
x2)
U1_AGA(
x1,
x2,
x3,
x4,
x5) =
U1_AGA(
x3,
x5)
APPEND_IN_AAG(
x1,
x2,
x3) =
APPEND_IN_AAG(
x3)
U3_AAG(
x1,
x2,
x3,
x4,
x5) =
U3_AAG(
x1,
x4,
x5)
U2_AGA(
x1,
x2,
x3,
x4,
x5) =
U2_AGA(
x1,
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 3 less nodes.
(6) Complex Obligation (AND)
(7) Obligation:
Pi DP problem:
The TRS P consists of the following rules:
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → APPEND_IN_AAG(Xs, Ys, Zs)
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x2,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x3,
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2,
x3)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x4,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x3,
x5)
s(
x1) =
s(
x1)
APPEND_IN_AAG(
x1,
x2,
x3) =
APPEND_IN_AAG(
x3)
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:
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → APPEND_IN_AAG(Xs, Ys, Zs)
R is empty.
The argument filtering Pi contains the following mapping:
.(
x1,
x2) =
.(
x1,
x2)
APPEND_IN_AAG(
x1,
x2,
x3) =
APPEND_IN_AAG(
x3)
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:
APPEND_IN_AAG(.(X, Zs)) → APPEND_IN_AAG(Zs)
R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
(12) 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:
- APPEND_IN_AAG(.(X, Zs)) → APPEND_IN_AAG(Zs)
The graph contains the following edges 1 > 1
(13) TRUE
(14) Obligation:
Pi DP problem:
The TRS P consists of the following rules:
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → FL_IN_AGA(X, Y, Z)
FL_IN_AGA(.(E, X), R, s(Z)) → U1_AGA(E, X, R, Z, append_in_aag(E, Y, R))
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x2,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x3,
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2,
x3)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x4,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x3,
x5)
s(
x1) =
s(
x1)
FL_IN_AGA(
x1,
x2,
x3) =
FL_IN_AGA(
x2)
U1_AGA(
x1,
x2,
x3,
x4,
x5) =
U1_AGA(
x3,
x5)
We have to consider all (P,R,Pi)-chains
(15) UsableRulesProof (EQUIVALENT transformation)
For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
(16) Obligation:
Pi DP problem:
The TRS P consists of the following rules:
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → FL_IN_AGA(X, Y, Z)
FL_IN_AGA(.(E, X), R, s(Z)) → U1_AGA(E, X, R, Z, append_in_aag(E, Y, R))
The TRS R consists of the following rules:
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
The argument filtering Pi contains the following mapping:
[] =
[]
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2,
x3)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x4,
x5)
s(
x1) =
s(
x1)
FL_IN_AGA(
x1,
x2,
x3) =
FL_IN_AGA(
x2)
U1_AGA(
x1,
x2,
x3,
x4,
x5) =
U1_AGA(
x3,
x5)
We have to consider all (P,R,Pi)-chains
(17) PiDPToQDPProof (SOUND transformation)
Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
(18) Obligation:
Q DP problem:
The TRS P consists of the following rules:
U1_AGA(R, append_out_aag(E, Y, R)) → FL_IN_AGA(Y)
FL_IN_AGA(R) → U1_AGA(R, append_in_aag(R))
The TRS R consists of the following rules:
append_in_aag(X) → append_out_aag([], X, X)
append_in_aag(.(X, Zs)) → U3_aag(X, Zs, append_in_aag(Zs))
U3_aag(X, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
The set Q consists of the following terms:
append_in_aag(x0)
U3_aag(x0, x1, x2)
We have to consider all (P,Q,R)-chains.
(19) Narrowing (SOUND transformation)
By narrowing [LPAR04] the rule
FL_IN_AGA(
R) →
U1_AGA(
R,
append_in_aag(
R)) at position [1] we obtained the following new rules [LPAR04]:
FL_IN_AGA(x0) → U1_AGA(x0, append_out_aag([], x0, x0))
FL_IN_AGA(.(x0, x1)) → U1_AGA(.(x0, x1), U3_aag(x0, x1, append_in_aag(x1)))
(20) Obligation:
Q DP problem:
The TRS P consists of the following rules:
U1_AGA(R, append_out_aag(E, Y, R)) → FL_IN_AGA(Y)
FL_IN_AGA(x0) → U1_AGA(x0, append_out_aag([], x0, x0))
FL_IN_AGA(.(x0, x1)) → U1_AGA(.(x0, x1), U3_aag(x0, x1, append_in_aag(x1)))
The TRS R consists of the following rules:
append_in_aag(X) → append_out_aag([], X, X)
append_in_aag(.(X, Zs)) → U3_aag(X, Zs, append_in_aag(Zs))
U3_aag(X, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
The set Q consists of the following terms:
append_in_aag(x0)
U3_aag(x0, x1, x2)
We have to consider all (P,Q,R)-chains.
(21) Instantiation (EQUIVALENT transformation)
By instantiating [LPAR04] the rule
U1_AGA(
R,
append_out_aag(
E,
Y,
R)) →
FL_IN_AGA(
Y) we obtained the following new rules [LPAR04]:
U1_AGA(z0, append_out_aag([], z0, z0)) → FL_IN_AGA(z0)
U1_AGA(.(z0, z1), append_out_aag(x1, x2, .(z0, z1))) → FL_IN_AGA(x2)
(22) Obligation:
Q DP problem:
The TRS P consists of the following rules:
FL_IN_AGA(x0) → U1_AGA(x0, append_out_aag([], x0, x0))
FL_IN_AGA(.(x0, x1)) → U1_AGA(.(x0, x1), U3_aag(x0, x1, append_in_aag(x1)))
U1_AGA(z0, append_out_aag([], z0, z0)) → FL_IN_AGA(z0)
U1_AGA(.(z0, z1), append_out_aag(x1, x2, .(z0, z1))) → FL_IN_AGA(x2)
The TRS R consists of the following rules:
append_in_aag(X) → append_out_aag([], X, X)
append_in_aag(.(X, Zs)) → U3_aag(X, Zs, append_in_aag(Zs))
U3_aag(X, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
The set Q consists of the following terms:
append_in_aag(x0)
U3_aag(x0, x1, x2)
We have to consider all (P,Q,R)-chains.
(23) QDPOrderProof (EQUIVALENT transformation)
We use the reduction pair processor [LPAR04].
The following pairs can be oriented strictly and are deleted.
FL_IN_AGA(.(x0, x1)) → U1_AGA(.(x0, x1), U3_aag(x0, x1, append_in_aag(x1)))
The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial interpretation [POLO]:
POL(.(x1, x2)) = 1 + x1 + x2
POL(FL_IN_AGA(x1)) = x1
POL(U1_AGA(x1, x2)) = x2
POL(U3_aag(x1, x2, x3)) = x1 + x3
POL([]) = 0
POL(append_in_aag(x1)) = x1
POL(append_out_aag(x1, x2, x3)) = x2
The following usable rules [FROCOS05] were oriented:
append_in_aag(X) → append_out_aag([], X, X)
append_in_aag(.(X, Zs)) → U3_aag(X, Zs, append_in_aag(Zs))
U3_aag(X, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
(24) Obligation:
Q DP problem:
The TRS P consists of the following rules:
FL_IN_AGA(x0) → U1_AGA(x0, append_out_aag([], x0, x0))
U1_AGA(z0, append_out_aag([], z0, z0)) → FL_IN_AGA(z0)
U1_AGA(.(z0, z1), append_out_aag(x1, x2, .(z0, z1))) → FL_IN_AGA(x2)
The TRS R consists of the following rules:
append_in_aag(X) → append_out_aag([], X, X)
append_in_aag(.(X, Zs)) → U3_aag(X, Zs, append_in_aag(Zs))
U3_aag(X, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
The set Q consists of the following terms:
append_in_aag(x0)
U3_aag(x0, x1, x2)
We have to consider all (P,Q,R)-chains.
(25) 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.
(26) Obligation:
Q DP problem:
The TRS P consists of the following rules:
FL_IN_AGA(x0) → U1_AGA(x0, append_out_aag([], x0, x0))
U1_AGA(z0, append_out_aag([], z0, z0)) → FL_IN_AGA(z0)
U1_AGA(.(z0, z1), append_out_aag(x1, x2, .(z0, z1))) → FL_IN_AGA(x2)
R is empty.
The set Q consists of the following terms:
append_in_aag(x0)
U3_aag(x0, x1, x2)
We have to consider all (P,Q,R)-chains.
(27) 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].
append_in_aag(x0)
U3_aag(x0, x1, x2)
(28) Obligation:
Q DP problem:
The TRS P consists of the following rules:
FL_IN_AGA(x0) → U1_AGA(x0, append_out_aag([], x0, x0))
U1_AGA(z0, append_out_aag([], z0, z0)) → FL_IN_AGA(z0)
U1_AGA(.(z0, z1), append_out_aag(x1, x2, .(z0, z1))) → FL_IN_AGA(x2)
R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
(29) Instantiation (EQUIVALENT transformation)
By instantiating [LPAR04] the rule
U1_AGA(
.(
z0,
z1),
append_out_aag(
x1,
x2,
.(
z0,
z1))) →
FL_IN_AGA(
x2) we obtained the following new rules [LPAR04]:
U1_AGA(.(x0, x1), append_out_aag([], .(x0, x1), .(x0, x1))) → FL_IN_AGA(.(x0, x1))
(30) Obligation:
Q DP problem:
The TRS P consists of the following rules:
FL_IN_AGA(x0) → U1_AGA(x0, append_out_aag([], x0, x0))
U1_AGA(z0, append_out_aag([], z0, z0)) → FL_IN_AGA(z0)
U1_AGA(.(x0, x1), append_out_aag([], .(x0, x1), .(x0, x1))) → FL_IN_AGA(.(x0, x1))
R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
(31) Instantiation (EQUIVALENT transformation)
By instantiating [LPAR04] the rule
U1_AGA(
.(
z0,
z1),
append_out_aag(
x1,
x2,
.(
z0,
z1))) →
FL_IN_AGA(
x2) we obtained the following new rules [LPAR04]:
U1_AGA(.(x0, x1), append_out_aag([], .(x0, x1), .(x0, x1))) → FL_IN_AGA(.(x0, x1))
(32) Obligation:
Q DP problem:
The TRS P consists of the following rules:
FL_IN_AGA(x0) → U1_AGA(x0, append_out_aag([], x0, x0))
U1_AGA(z0, append_out_aag([], z0, z0)) → FL_IN_AGA(z0)
U1_AGA(.(x0, x1), append_out_aag([], .(x0, x1), .(x0, x1))) → FL_IN_AGA(.(x0, x1))
R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
(33) NonTerminationProof (EQUIVALENT transformation)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by narrowing to the left:
s =
U1_AGA(
z0,
append_out_aag(
[],
z0,
z0)) evaluates to t =
U1_AGA(
z0,
append_out_aag(
[],
z0,
z0))
Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
- Matcher: [ ]
- Semiunifier: [ ]
Rewriting sequenceU1_AGA(z0, append_out_aag([], z0, z0)) →
FL_IN_AGA(
z0)
with rule
U1_AGA(
z0',
append_out_aag(
[],
z0',
z0')) →
FL_IN_AGA(
z0') at position [] and matcher [
z0' /
z0]
FL_IN_AGA(z0) →
U1_AGA(
z0,
append_out_aag(
[],
z0,
z0))
with rule
FL_IN_AGA(
x0) →
U1_AGA(
x0,
append_out_aag(
[],
x0,
x0))
Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence
All these steps are and every following step will be a correct step w.r.t to Q.
(34) FALSE
(35) PrologToPiTRSProof (SOUND transformation)
We use the technique of [LOPSTR]. With regard to the inferred argument filtering the predicates were used in the following modes:
fl_in: (f,b,f)
append_in: (f,f,b)
Transforming
Prolog into the following
Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x5)
s(
x1) =
s(
x1)
Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog
(36) Obligation:
Pi-finite rewrite system:
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x5)
s(
x1) =
s(
x1)
(37) 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:
FL_IN_AGA(.(E, X), R, s(Z)) → U1_AGA(E, X, R, Z, append_in_aag(E, Y, R))
FL_IN_AGA(.(E, X), R, s(Z)) → APPEND_IN_AAG(E, Y, R)
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → APPEND_IN_AAG(Xs, Ys, Zs)
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z))
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → FL_IN_AGA(X, Y, Z)
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x5)
s(
x1) =
s(
x1)
FL_IN_AGA(
x1,
x2,
x3) =
FL_IN_AGA(
x2)
U1_AGA(
x1,
x2,
x3,
x4,
x5) =
U1_AGA(
x5)
APPEND_IN_AAG(
x1,
x2,
x3) =
APPEND_IN_AAG(
x3)
U3_AAG(
x1,
x2,
x3,
x4,
x5) =
U3_AAG(
x1,
x5)
U2_AGA(
x1,
x2,
x3,
x4,
x5) =
U2_AGA(
x1,
x5)
We have to consider all (P,R,Pi)-chains
(38) Obligation:
Pi DP problem:
The TRS P consists of the following rules:
FL_IN_AGA(.(E, X), R, s(Z)) → U1_AGA(E, X, R, Z, append_in_aag(E, Y, R))
FL_IN_AGA(.(E, X), R, s(Z)) → APPEND_IN_AAG(E, Y, R)
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → APPEND_IN_AAG(Xs, Ys, Zs)
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z))
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → FL_IN_AGA(X, Y, Z)
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x5)
s(
x1) =
s(
x1)
FL_IN_AGA(
x1,
x2,
x3) =
FL_IN_AGA(
x2)
U1_AGA(
x1,
x2,
x3,
x4,
x5) =
U1_AGA(
x5)
APPEND_IN_AAG(
x1,
x2,
x3) =
APPEND_IN_AAG(
x3)
U3_AAG(
x1,
x2,
x3,
x4,
x5) =
U3_AAG(
x1,
x5)
U2_AGA(
x1,
x2,
x3,
x4,
x5) =
U2_AGA(
x1,
x5)
We have to consider all (P,R,Pi)-chains
(39) DependencyGraphProof (EQUIVALENT transformation)
The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes.
(40) Complex Obligation (AND)
(41) Obligation:
Pi DP problem:
The TRS P consists of the following rules:
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → APPEND_IN_AAG(Xs, Ys, Zs)
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x5)
s(
x1) =
s(
x1)
APPEND_IN_AAG(
x1,
x2,
x3) =
APPEND_IN_AAG(
x3)
We have to consider all (P,R,Pi)-chains
(42) UsableRulesProof (EQUIVALENT transformation)
For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
(43) Obligation:
Pi DP problem:
The TRS P consists of the following rules:
APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) → APPEND_IN_AAG(Xs, Ys, Zs)
R is empty.
The argument filtering Pi contains the following mapping:
.(
x1,
x2) =
.(
x1,
x2)
APPEND_IN_AAG(
x1,
x2,
x3) =
APPEND_IN_AAG(
x3)
We have to consider all (P,R,Pi)-chains
(44) PiDPToQDPProof (SOUND transformation)
Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
(45) Obligation:
Q DP problem:
The TRS P consists of the following rules:
APPEND_IN_AAG(.(X, Zs)) → APPEND_IN_AAG(Zs)
R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
(46) 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:
- APPEND_IN_AAG(.(X, Zs)) → APPEND_IN_AAG(Zs)
The graph contains the following edges 1 > 1
(47) TRUE
(48) Obligation:
Pi DP problem:
The TRS P consists of the following rules:
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → FL_IN_AGA(X, Y, Z)
FL_IN_AGA(.(E, X), R, s(Z)) → U1_AGA(E, X, R, Z, append_in_aag(E, Y, R))
The TRS R consists of the following rules:
fl_in_aga([], [], 0) → fl_out_aga([], [], 0)
fl_in_aga(.(E, X), R, s(Z)) → U1_aga(E, X, R, Z, append_in_aag(E, Y, R))
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) → U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z))
U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) → fl_out_aga(.(E, X), R, s(Z))
The argument filtering Pi contains the following mapping:
fl_in_aga(
x1,
x2,
x3) =
fl_in_aga(
x2)
[] =
[]
fl_out_aga(
x1,
x2,
x3) =
fl_out_aga(
x1,
x3)
U1_aga(
x1,
x2,
x3,
x4,
x5) =
U1_aga(
x5)
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x5)
U2_aga(
x1,
x2,
x3,
x4,
x5) =
U2_aga(
x1,
x5)
s(
x1) =
s(
x1)
FL_IN_AGA(
x1,
x2,
x3) =
FL_IN_AGA(
x2)
U1_AGA(
x1,
x2,
x3,
x4,
x5) =
U1_AGA(
x5)
We have to consider all (P,R,Pi)-chains
(49) UsableRulesProof (EQUIVALENT transformation)
For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R.
(50) Obligation:
Pi DP problem:
The TRS P consists of the following rules:
U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) → FL_IN_AGA(X, Y, Z)
FL_IN_AGA(.(E, X), R, s(Z)) → U1_AGA(E, X, R, Z, append_in_aag(E, Y, R))
The TRS R consists of the following rules:
append_in_aag([], X, X) → append_out_aag([], X, X)
append_in_aag(.(X, Xs), Ys, .(X, Zs)) → U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs))
U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) → append_out_aag(.(X, Xs), Ys, .(X, Zs))
The argument filtering Pi contains the following mapping:
[] =
[]
append_in_aag(
x1,
x2,
x3) =
append_in_aag(
x3)
append_out_aag(
x1,
x2,
x3) =
append_out_aag(
x1,
x2)
.(
x1,
x2) =
.(
x1,
x2)
U3_aag(
x1,
x2,
x3,
x4,
x5) =
U3_aag(
x1,
x5)
s(
x1) =
s(
x1)
FL_IN_AGA(
x1,
x2,
x3) =
FL_IN_AGA(
x2)
U1_AGA(
x1,
x2,
x3,
x4,
x5) =
U1_AGA(
x5)
We have to consider all (P,R,Pi)-chains
(51) PiDPToQDPProof (SOUND transformation)
Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi.
(52) Obligation:
Q DP problem:
The TRS P consists of the following rules:
U1_AGA(append_out_aag(E, Y)) → FL_IN_AGA(Y)
FL_IN_AGA(R) → U1_AGA(append_in_aag(R))
The TRS R consists of the following rules:
append_in_aag(X) → append_out_aag([], X)
append_in_aag(.(X, Zs)) → U3_aag(X, append_in_aag(Zs))
U3_aag(X, append_out_aag(Xs, Ys)) → append_out_aag(.(X, Xs), Ys)
The set Q consists of the following terms:
append_in_aag(x0)
U3_aag(x0, x1)
We have to consider all (P,Q,R)-chains.
(53) MRRProof (EQUIVALENT transformation)
By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
Strictly oriented rules of the TRS R:
append_in_aag(.(X, Zs)) → U3_aag(X, append_in_aag(Zs))
Used ordering: Polynomial interpretation [POLO]:
POL(.(x1, x2)) = 1 + 2·x1 + x2
POL(FL_IN_AGA(x1)) = 2·x1
POL(U1_AGA(x1)) = x1
POL(U3_aag(x1, x2)) = 1 + 2·x1 + x2
POL([]) = 0
POL(append_in_aag(x1)) = 2·x1
POL(append_out_aag(x1, x2)) = x1 + 2·x2
(54) Obligation:
Q DP problem:
The TRS P consists of the following rules:
U1_AGA(append_out_aag(E, Y)) → FL_IN_AGA(Y)
FL_IN_AGA(R) → U1_AGA(append_in_aag(R))
The TRS R consists of the following rules:
append_in_aag(X) → append_out_aag([], X)
U3_aag(X, append_out_aag(Xs, Ys)) → append_out_aag(.(X, Xs), Ys)
The set Q consists of the following terms:
append_in_aag(x0)
U3_aag(x0, x1)
We have to consider all (P,Q,R)-chains.
(55) 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.
(56) Obligation:
Q DP problem:
The TRS P consists of the following rules:
U1_AGA(append_out_aag(E, Y)) → FL_IN_AGA(Y)
FL_IN_AGA(R) → U1_AGA(append_in_aag(R))
The TRS R consists of the following rules:
append_in_aag(X) → append_out_aag([], X)
The set Q consists of the following terms:
append_in_aag(x0)
U3_aag(x0, x1)
We have to consider all (P,Q,R)-chains.
(57) 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].
U3_aag(x0, x1)
(58) Obligation:
Q DP problem:
The TRS P consists of the following rules:
U1_AGA(append_out_aag(E, Y)) → FL_IN_AGA(Y)
FL_IN_AGA(R) → U1_AGA(append_in_aag(R))
The TRS R consists of the following rules:
append_in_aag(X) → append_out_aag([], X)
The set Q consists of the following terms:
append_in_aag(x0)
We have to consider all (P,Q,R)-chains.
(59) Rewriting (EQUIVALENT transformation)
By rewriting [LPAR04] the rule
FL_IN_AGA(
R) →
U1_AGA(
append_in_aag(
R)) at position [0] we obtained the following new rules [LPAR04]:
FL_IN_AGA(R) → U1_AGA(append_out_aag([], R))
(60) Obligation:
Q DP problem:
The TRS P consists of the following rules:
U1_AGA(append_out_aag(E, Y)) → FL_IN_AGA(Y)
FL_IN_AGA(R) → U1_AGA(append_out_aag([], R))
The TRS R consists of the following rules:
append_in_aag(X) → append_out_aag([], X)
The set Q consists of the following terms:
append_in_aag(x0)
We have to consider all (P,Q,R)-chains.
(61) 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.
(62) Obligation:
Q DP problem:
The TRS P consists of the following rules:
U1_AGA(append_out_aag(E, Y)) → FL_IN_AGA(Y)
FL_IN_AGA(R) → U1_AGA(append_out_aag([], R))
R is empty.
The set Q consists of the following terms:
append_in_aag(x0)
We have to consider all (P,Q,R)-chains.
(63) 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].
append_in_aag(x0)
(64) Obligation:
Q DP problem:
The TRS P consists of the following rules:
U1_AGA(append_out_aag(E, Y)) → FL_IN_AGA(Y)
FL_IN_AGA(R) → U1_AGA(append_out_aag([], R))
R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
(65) Instantiation (EQUIVALENT transformation)
By instantiating [LPAR04] the rule
U1_AGA(
append_out_aag(
E,
Y)) →
FL_IN_AGA(
Y) we obtained the following new rules [LPAR04]:
U1_AGA(append_out_aag([], z0)) → FL_IN_AGA(z0)
(66) Obligation:
Q DP problem:
The TRS P consists of the following rules:
FL_IN_AGA(R) → U1_AGA(append_out_aag([], R))
U1_AGA(append_out_aag([], z0)) → FL_IN_AGA(z0)
R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
(67) NonTerminationProof (EQUIVALENT transformation)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by narrowing to the left:
s =
U1_AGA(
append_out_aag(
[],
z0)) evaluates to t =
U1_AGA(
append_out_aag(
[],
z0))
Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
- Semiunifier: [ ]
- Matcher: [ ]
Rewriting sequenceU1_AGA(append_out_aag([], z0)) →
FL_IN_AGA(
z0)
with rule
U1_AGA(
append_out_aag(
[],
z0')) →
FL_IN_AGA(
z0') at position [] and matcher [
z0' /
z0]
FL_IN_AGA(z0) →
U1_AGA(
append_out_aag(
[],
z0))
with rule
FL_IN_AGA(
R) →
U1_AGA(
append_out_aag(
[],
R))
Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence
All these steps are and every following step will be a correct step w.r.t to Q.
(68) FALSE