(0) Obligation:

Clauses:

member(X, .(Y, Xs)) :- member(X, Xs).
member(X, .(X, Xs)).
subset(.(X, Xs), Ys) :- ','(member(X, Ys), subset(Xs, Ys)).
subset([], Ys).
member1(X, .(Y, Xs)) :- member1(X, Xs).
member1(X, .(X, Xs)).
subset1(.(X, Xs), Ys) :- ','(member1(X, Ys), subset1(Xs, Ys)).
subset1([], Ys).

Queries:

subset(g,g).

(1) PrologToPrologProblemTransformerProof (SOUND transformation)

Built Prolog problem from termination graph.

(2) Obligation:

Clauses:

member10(T42, .(T43, T44)) :- member10(T42, T44).
member10(T52, .(T52, T53)).
subset11(.(T21, T7), .(T22, T23)) :- member10(T21, T23).
subset11(.(T21, T7), .(T22, T23)) :- ','(member10(T21, T23), subset11(T7, .(T22, T23))).
subset11(.(T66, T7), .(T66, T67)) :- subset11(T7, .(T66, T67)).
subset11([], T73).

Queries:

subset11(g,g).

(3) PrologToPiTRSProof (SOUND transformation)

We use the technique of [LOPSTR]. With regard to the inferred argument filtering the predicates were used in the following modes:
subset11_in: (b,b)
member10_in: (b,b)
Transforming Prolog into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:

subset11_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, member10_in_gg(T21, T23))
member10_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, member10_in_gg(T42, T44))
member10_in_gg(T52, .(T52, T53)) → member10_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, member10_out_gg(T42, T44)) → member10_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → subset11_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subset11_in_gg(T7, .(T22, T23)))
subset11_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subset11_in_gg(T7, .(T66, T67)))
subset11_in_gg([], T73) → subset11_out_gg([], T73)
U4_gg(T66, T7, T67, subset11_out_gg(T7, .(T66, T67))) → subset11_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subset11_out_gg(T7, .(T22, T23))) → subset11_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subset11_in_gg(x1, x2)  =  subset11_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
member10_in_gg(x1, x2)  =  member10_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
member10_out_gg(x1, x2)  =  member10_out_gg
subset11_out_gg(x1, x2)  =  subset11_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog

(4) Obligation:

Pi-finite rewrite system:
The TRS R consists of the following rules:

subset11_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, member10_in_gg(T21, T23))
member10_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, member10_in_gg(T42, T44))
member10_in_gg(T52, .(T52, T53)) → member10_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, member10_out_gg(T42, T44)) → member10_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → subset11_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subset11_in_gg(T7, .(T22, T23)))
subset11_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subset11_in_gg(T7, .(T66, T67)))
subset11_in_gg([], T73) → subset11_out_gg([], T73)
U4_gg(T66, T7, T67, subset11_out_gg(T7, .(T66, T67))) → subset11_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subset11_out_gg(T7, .(T22, T23))) → subset11_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subset11_in_gg(x1, x2)  =  subset11_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
member10_in_gg(x1, x2)  =  member10_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
member10_out_gg(x1, x2)  =  member10_out_gg
subset11_out_gg(x1, x2)  =  subset11_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []

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

SUBSET11_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T21, T7, T22, T23, member10_in_gg(T21, T23))
SUBSET11_IN_GG(.(T21, T7), .(T22, T23)) → MEMBER10_IN_GG(T21, T23)
MEMBER10_IN_GG(T42, .(T43, T44)) → U1_GG(T42, T43, T44, member10_in_gg(T42, T44))
MEMBER10_IN_GG(T42, .(T43, T44)) → MEMBER10_IN_GG(T42, T44)
U2_GG(T21, T7, T22, T23, member10_out_gg(T21, T23)) → U3_GG(T21, T7, T22, T23, subset11_in_gg(T7, .(T22, T23)))
U2_GG(T21, T7, T22, T23, member10_out_gg(T21, T23)) → SUBSET11_IN_GG(T7, .(T22, T23))
SUBSET11_IN_GG(.(T66, T7), .(T66, T67)) → U4_GG(T66, T7, T67, subset11_in_gg(T7, .(T66, T67)))
SUBSET11_IN_GG(.(T66, T7), .(T66, T67)) → SUBSET11_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

subset11_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, member10_in_gg(T21, T23))
member10_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, member10_in_gg(T42, T44))
member10_in_gg(T52, .(T52, T53)) → member10_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, member10_out_gg(T42, T44)) → member10_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → subset11_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subset11_in_gg(T7, .(T22, T23)))
subset11_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subset11_in_gg(T7, .(T66, T67)))
subset11_in_gg([], T73) → subset11_out_gg([], T73)
U4_gg(T66, T7, T67, subset11_out_gg(T7, .(T66, T67))) → subset11_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subset11_out_gg(T7, .(T22, T23))) → subset11_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subset11_in_gg(x1, x2)  =  subset11_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
member10_in_gg(x1, x2)  =  member10_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
member10_out_gg(x1, x2)  =  member10_out_gg
subset11_out_gg(x1, x2)  =  subset11_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []
SUBSET11_IN_GG(x1, x2)  =  SUBSET11_IN_GG(x1, x2)
U2_GG(x1, x2, x3, x4, x5)  =  U2_GG(x2, x3, x4, x5)
MEMBER10_IN_GG(x1, x2)  =  MEMBER10_IN_GG(x1, x2)
U1_GG(x1, x2, x3, x4)  =  U1_GG(x4)
U3_GG(x1, x2, x3, x4, x5)  =  U3_GG(x5)
U4_GG(x1, x2, x3, x4)  =  U4_GG(x4)

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

(6) Obligation:

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

SUBSET11_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T21, T7, T22, T23, member10_in_gg(T21, T23))
SUBSET11_IN_GG(.(T21, T7), .(T22, T23)) → MEMBER10_IN_GG(T21, T23)
MEMBER10_IN_GG(T42, .(T43, T44)) → U1_GG(T42, T43, T44, member10_in_gg(T42, T44))
MEMBER10_IN_GG(T42, .(T43, T44)) → MEMBER10_IN_GG(T42, T44)
U2_GG(T21, T7, T22, T23, member10_out_gg(T21, T23)) → U3_GG(T21, T7, T22, T23, subset11_in_gg(T7, .(T22, T23)))
U2_GG(T21, T7, T22, T23, member10_out_gg(T21, T23)) → SUBSET11_IN_GG(T7, .(T22, T23))
SUBSET11_IN_GG(.(T66, T7), .(T66, T67)) → U4_GG(T66, T7, T67, subset11_in_gg(T7, .(T66, T67)))
SUBSET11_IN_GG(.(T66, T7), .(T66, T67)) → SUBSET11_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

subset11_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, member10_in_gg(T21, T23))
member10_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, member10_in_gg(T42, T44))
member10_in_gg(T52, .(T52, T53)) → member10_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, member10_out_gg(T42, T44)) → member10_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → subset11_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subset11_in_gg(T7, .(T22, T23)))
subset11_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subset11_in_gg(T7, .(T66, T67)))
subset11_in_gg([], T73) → subset11_out_gg([], T73)
U4_gg(T66, T7, T67, subset11_out_gg(T7, .(T66, T67))) → subset11_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subset11_out_gg(T7, .(T22, T23))) → subset11_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subset11_in_gg(x1, x2)  =  subset11_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
member10_in_gg(x1, x2)  =  member10_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
member10_out_gg(x1, x2)  =  member10_out_gg
subset11_out_gg(x1, x2)  =  subset11_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []
SUBSET11_IN_GG(x1, x2)  =  SUBSET11_IN_GG(x1, x2)
U2_GG(x1, x2, x3, x4, x5)  =  U2_GG(x2, x3, x4, x5)
MEMBER10_IN_GG(x1, x2)  =  MEMBER10_IN_GG(x1, x2)
U1_GG(x1, x2, x3, x4)  =  U1_GG(x4)
U3_GG(x1, x2, x3, x4, x5)  =  U3_GG(x5)
U4_GG(x1, x2, x3, x4)  =  U4_GG(x4)

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

(7) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes.

(8) Complex Obligation (AND)

(9) Obligation:

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

MEMBER10_IN_GG(T42, .(T43, T44)) → MEMBER10_IN_GG(T42, T44)

The TRS R consists of the following rules:

subset11_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, member10_in_gg(T21, T23))
member10_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, member10_in_gg(T42, T44))
member10_in_gg(T52, .(T52, T53)) → member10_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, member10_out_gg(T42, T44)) → member10_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → subset11_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subset11_in_gg(T7, .(T22, T23)))
subset11_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subset11_in_gg(T7, .(T66, T67)))
subset11_in_gg([], T73) → subset11_out_gg([], T73)
U4_gg(T66, T7, T67, subset11_out_gg(T7, .(T66, T67))) → subset11_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subset11_out_gg(T7, .(T22, T23))) → subset11_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subset11_in_gg(x1, x2)  =  subset11_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
member10_in_gg(x1, x2)  =  member10_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
member10_out_gg(x1, x2)  =  member10_out_gg
subset11_out_gg(x1, x2)  =  subset11_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []
MEMBER10_IN_GG(x1, x2)  =  MEMBER10_IN_GG(x1, x2)

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

(10) UsableRulesProof (EQUIVALENT transformation)

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

(11) Obligation:

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

MEMBER10_IN_GG(T42, .(T43, T44)) → MEMBER10_IN_GG(T42, T44)

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

(12) PiDPToQDPProof (EQUIVALENT transformation)

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

(13) Obligation:

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

MEMBER10_IN_GG(T42, .(T43, T44)) → MEMBER10_IN_GG(T42, T44)

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

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

  • MEMBER10_IN_GG(T42, .(T43, T44)) → MEMBER10_IN_GG(T42, T44)
    The graph contains the following edges 1 >= 1, 2 > 2

(15) YES

(16) Obligation:

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

U2_GG(T21, T7, T22, T23, member10_out_gg(T21, T23)) → SUBSET11_IN_GG(T7, .(T22, T23))
SUBSET11_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T21, T7, T22, T23, member10_in_gg(T21, T23))
SUBSET11_IN_GG(.(T66, T7), .(T66, T67)) → SUBSET11_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

subset11_in_gg(.(T21, T7), .(T22, T23)) → U2_gg(T21, T7, T22, T23, member10_in_gg(T21, T23))
member10_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, member10_in_gg(T42, T44))
member10_in_gg(T52, .(T52, T53)) → member10_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, member10_out_gg(T42, T44)) → member10_out_gg(T42, .(T43, T44))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → subset11_out_gg(.(T21, T7), .(T22, T23))
U2_gg(T21, T7, T22, T23, member10_out_gg(T21, T23)) → U3_gg(T21, T7, T22, T23, subset11_in_gg(T7, .(T22, T23)))
subset11_in_gg(.(T66, T7), .(T66, T67)) → U4_gg(T66, T7, T67, subset11_in_gg(T7, .(T66, T67)))
subset11_in_gg([], T73) → subset11_out_gg([], T73)
U4_gg(T66, T7, T67, subset11_out_gg(T7, .(T66, T67))) → subset11_out_gg(.(T66, T7), .(T66, T67))
U3_gg(T21, T7, T22, T23, subset11_out_gg(T7, .(T22, T23))) → subset11_out_gg(.(T21, T7), .(T22, T23))

The argument filtering Pi contains the following mapping:
subset11_in_gg(x1, x2)  =  subset11_in_gg(x1, x2)
.(x1, x2)  =  .(x1, x2)
U2_gg(x1, x2, x3, x4, x5)  =  U2_gg(x2, x3, x4, x5)
member10_in_gg(x1, x2)  =  member10_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
member10_out_gg(x1, x2)  =  member10_out_gg
subset11_out_gg(x1, x2)  =  subset11_out_gg
U3_gg(x1, x2, x3, x4, x5)  =  U3_gg(x5)
U4_gg(x1, x2, x3, x4)  =  U4_gg(x4)
[]  =  []
SUBSET11_IN_GG(x1, x2)  =  SUBSET11_IN_GG(x1, x2)
U2_GG(x1, x2, x3, x4, x5)  =  U2_GG(x2, x3, x4, x5)

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

(17) UsableRulesProof (EQUIVALENT transformation)

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

(18) Obligation:

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

U2_GG(T21, T7, T22, T23, member10_out_gg(T21, T23)) → SUBSET11_IN_GG(T7, .(T22, T23))
SUBSET11_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T21, T7, T22, T23, member10_in_gg(T21, T23))
SUBSET11_IN_GG(.(T66, T7), .(T66, T67)) → SUBSET11_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

member10_in_gg(T42, .(T43, T44)) → U1_gg(T42, T43, T44, member10_in_gg(T42, T44))
member10_in_gg(T52, .(T52, T53)) → member10_out_gg(T52, .(T52, T53))
U1_gg(T42, T43, T44, member10_out_gg(T42, T44)) → member10_out_gg(T42, .(T43, T44))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
member10_in_gg(x1, x2)  =  member10_in_gg(x1, x2)
U1_gg(x1, x2, x3, x4)  =  U1_gg(x4)
member10_out_gg(x1, x2)  =  member10_out_gg
SUBSET11_IN_GG(x1, x2)  =  SUBSET11_IN_GG(x1, x2)
U2_GG(x1, x2, x3, x4, x5)  =  U2_GG(x2, x3, x4, x5)

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

(19) PiDPToQDPProof (SOUND transformation)

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

(20) Obligation:

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

U2_GG(T7, T22, T23, member10_out_gg) → SUBSET11_IN_GG(T7, .(T22, T23))
SUBSET11_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T7, T22, T23, member10_in_gg(T21, T23))
SUBSET11_IN_GG(.(T66, T7), .(T66, T67)) → SUBSET11_IN_GG(T7, .(T66, T67))

The TRS R consists of the following rules:

member10_in_gg(T42, .(T43, T44)) → U1_gg(member10_in_gg(T42, T44))
member10_in_gg(T52, .(T52, T53)) → member10_out_gg
U1_gg(member10_out_gg) → member10_out_gg

The set Q consists of the following terms:

member10_in_gg(x0, x1)
U1_gg(x0)

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

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

  • SUBSET11_IN_GG(.(T21, T7), .(T22, T23)) → U2_GG(T7, T22, T23, member10_in_gg(T21, T23))
    The graph contains the following edges 1 > 1, 2 > 2, 2 > 3

  • SUBSET11_IN_GG(.(T66, T7), .(T66, T67)) → SUBSET11_IN_GG(T7, .(T66, T67))
    The graph contains the following edges 1 > 1, 2 >= 2

  • U2_GG(T7, T22, T23, member10_out_gg) → SUBSET11_IN_GG(T7, .(T22, T23))
    The graph contains the following edges 1 >= 1

(22) YES