/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


MAYBE
proof of /export/starexec/sandbox/benchmark/theBenchmark.pl
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Left Termination of the query pattern

sublist(g,a)

w.r.t. the given Prolog program could not be shown:

(0) Prolog
(1) PrologToPiTRSProof [SOUND, 0 ms]
(2) PiTRS
    (3) DependencyPairsProof [EQUIVALENT, 14 ms]
    (4) PiDP
    (5) DependencyGraphProof [EQUIVALENT, 0 ms]
    (6) AND
        (7) PiDP
            (8) UsableRulesProof [EQUIVALENT, 0 ms]
            (9) PiDP
            (10) PiDPToQDPProof [SOUND, 0 ms]
            (11) QDP
            (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (13) YES
        (14) PiDP
            (15) UsableRulesProof [EQUIVALENT, 0 ms]
            (16) PiDP
            (17) PiDPToQDPProof [SOUND, 0 ms]
            (18) QDP
(19) PrologToPiTRSProof [SOUND, 0 ms]
(20) PiTRS
    (21) DependencyPairsProof [EQUIVALENT, 4 ms]
    (22) PiDP
    (23) DependencyGraphProof [EQUIVALENT, 0 ms]
    (24) AND
        (25) PiDP
            (26) UsableRulesProof [EQUIVALENT, 0 ms]
            (27) PiDP
            (28) PiDPToQDPProof [SOUND, 0 ms]
            (29) QDP
            (30) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (31) YES
        (32) PiDP
            (33) UsableRulesProof [EQUIVALENT, 0 ms]
            (34) PiDP
            (35) PiDPToQDPProof [SOUND, 0 ms]
            (36) QDP
(37) PrologToTRSTransformerProof [SOUND, 0 ms]
(38) QTRS
    (39) DependencyPairsProof [EQUIVALENT, 0 ms]
    (40) QDP
    (41) DependencyGraphProof [EQUIVALENT, 0 ms]
    (42) AND
        (43) QDP
            (44) MNOCProof [EQUIVALENT, 0 ms]
            (45) QDP
            (46) UsableRulesProof [EQUIVALENT, 0 ms]
            (47) QDP
            (48) QReductionProof [EQUIVALENT, 0 ms]
            (49) QDP
        (50) QDP
            (51) MNOCProof [EQUIVALENT, 0 ms]
            (52) QDP
            (53) UsableRulesProof [EQUIVALENT, 0 ms]
            (54) QDP
            (55) QReductionProof [EQUIVALENT, 0 ms]
            (56) QDP
(57) PrologToDTProblemTransformerProof [SOUND, 0 ms]
(58) TRIPLES
    (59) TriplesToPiDPProof [SOUND, 0 ms]
    (60) PiDP
    (61) DependencyGraphProof [EQUIVALENT, 0 ms]
    (62) AND
        (63) PiDP
            (64) UsableRulesProof [EQUIVALENT, 0 ms]
            (65) PiDP
            (66) PiDPToQDPProof [SOUND, 0 ms]
            (67) QDP
            (68) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (69) YES
        (70) PiDP
            (71) UsableRulesProof [EQUIVALENT, 0 ms]
            (72) PiDP
            (73) PiDPToQDPProof [SOUND, 0 ms]
            (74) QDP
        (75) PiDP
            (76) UsableRulesProof [EQUIVALENT, 0 ms]
            (77) PiDP
(78) PrologToIRSwTTransformerProof [SOUND, 0 ms]
(79) AND
    (80) IRSwT
        (81) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms]
        (82) TRUE
    (83) IRSwT
        (84) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms]
        (85) IRSwT
        (86) IntTRSCompressionProof [EQUIVALENT, 21 ms]
        (87) IRSwT
        (88) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
        (89) IRSwT
        (90) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms]
        (91) IRSwT
        (92) FilterProof [EQUIVALENT, 0 ms]
        (93) IntTRS
        (94) IntTRSNonPeriodicNontermProof [COMPLETE, 6 ms]
        (95) NO


----------------------------------------

(0)
Obligation:
Clauses:

sublist(X, Y) :- ','(append(U, X, V), append(V, W, Y)).
append([], Ys, Ys).
append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs).


Query: sublist(g,a)
----------------------------------------

(1) PrologToPiTRSProof (SOUND)
We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:

sublist_in_2: (b,f)

append_in_3: (f,b,f) (b,f,f)

Transforming Prolog into the following Term Rewriting System:

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

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x1, x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x2, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x3, x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x1, x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa(x1)

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x2, x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga(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:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x1, x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x2, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x3, x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x1, x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa(x1)

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x2, x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga(x1)



----------------------------------------

(3) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

   SUBLIST_IN_GA(X, Y) -> U1_GA(X, Y, append_in_aga(U, X, V))
   SUBLIST_IN_GA(X, Y) -> APPEND_IN_AGA(U, X, V)
   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> U3_AGA(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AGA(Xs, Ys, Zs)
   U1_GA(X, Y, append_out_aga(U, X, V)) -> U2_GA(X, Y, append_in_gaa(V, W, Y))
   U1_GA(X, Y, append_out_aga(U, X, V)) -> APPEND_IN_GAA(V, W, Y)
   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_GAA(Xs, Ys, Zs)

The TRS R consists of the following rules:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x1, x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x2, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x3, x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x1, x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa(x1)

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x2, x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga(x1)

SUBLIST_IN_GA(x1, x2)  =  SUBLIST_IN_GA(x1)

U1_GA(x1, x2, x3)  =  U1_GA(x1, x3)

APPEND_IN_AGA(x1, x2, x3)  =  APPEND_IN_AGA(x2)

U3_AGA(x1, x2, x3, x4, x5)  =  U3_AGA(x3, x5)

U2_GA(x1, x2, x3)  =  U2_GA(x1, x3)

APPEND_IN_GAA(x1, x2, x3)  =  APPEND_IN_GAA(x1)

U3_GAA(x1, x2, x3, x4, x5)  =  U3_GAA(x2, x5)


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

(4)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   SUBLIST_IN_GA(X, Y) -> U1_GA(X, Y, append_in_aga(U, X, V))
   SUBLIST_IN_GA(X, Y) -> APPEND_IN_AGA(U, X, V)
   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> U3_AGA(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AGA(Xs, Ys, Zs)
   U1_GA(X, Y, append_out_aga(U, X, V)) -> U2_GA(X, Y, append_in_gaa(V, W, Y))
   U1_GA(X, Y, append_out_aga(U, X, V)) -> APPEND_IN_GAA(V, W, Y)
   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_GAA(Xs, Ys, Zs)

The TRS R consists of the following rules:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x1, x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x2, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x3, x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x1, x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa(x1)

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x2, x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga(x1)

SUBLIST_IN_GA(x1, x2)  =  SUBLIST_IN_GA(x1)

U1_GA(x1, x2, x3)  =  U1_GA(x1, x3)

APPEND_IN_AGA(x1, x2, x3)  =  APPEND_IN_AGA(x2)

U3_AGA(x1, x2, x3, x4, x5)  =  U3_AGA(x3, x5)

U2_GA(x1, x2, x3)  =  U2_GA(x1, x3)

APPEND_IN_GAA(x1, x2, x3)  =  APPEND_IN_GAA(x1)

U3_GAA(x1, x2, x3, x4, x5)  =  U3_GAA(x2, x5)


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

(5) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes.
----------------------------------------

(6)
Complex Obligation (AND)

----------------------------------------

(7)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_GAA(Xs, Ys, Zs)

The TRS R consists of the following rules:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x1, x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x2, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x3, x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x1, x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa(x1)

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x2, x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga(x1)

APPEND_IN_GAA(x1, x2, x3)  =  APPEND_IN_GAA(x1)


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

(8) UsableRulesProof (EQUIVALENT)
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_GAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_GAA(Xs, Ys, Zs)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

APPEND_IN_GAA(x1, x2, x3)  =  APPEND_IN_GAA(x1)


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

(10) PiDPToQDPProof (SOUND)
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_GAA(.(Xs)) -> APPEND_IN_GAA(Xs)

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

(12) QDPSizeChangeProof (EQUIVALENT)
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_GAA(.(Xs)) -> APPEND_IN_GAA(Xs)
The graph contains the following edges 1 > 1


----------------------------------------

(13)
YES

----------------------------------------

(14)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AGA(Xs, Ys, Zs)

The TRS R consists of the following rules:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x1, x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x2, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x3, x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x1, x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa(x1)

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x2, x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga(x1)

APPEND_IN_AGA(x1, x2, x3)  =  APPEND_IN_AGA(x2)


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

(15) UsableRulesProof (EQUIVALENT)
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:

   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AGA(Xs, Ys, Zs)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

APPEND_IN_AGA(x1, x2, x3)  =  APPEND_IN_AGA(x2)


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

(17) PiDPToQDPProof (SOUND)
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:

   APPEND_IN_AGA(Ys) -> APPEND_IN_AGA(Ys)

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

(19) PrologToPiTRSProof (SOUND)
We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes:

sublist_in_2: (b,f)

append_in_3: (f,b,f) (b,f,f)

Transforming Prolog into the following Term Rewriting System:

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

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga





Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog



----------------------------------------

(20)
Obligation:
Pi-finite rewrite system:
The TRS R consists of the following rules:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga



----------------------------------------

(21) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

   SUBLIST_IN_GA(X, Y) -> U1_GA(X, Y, append_in_aga(U, X, V))
   SUBLIST_IN_GA(X, Y) -> APPEND_IN_AGA(U, X, V)
   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> U3_AGA(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AGA(Xs, Ys, Zs)
   U1_GA(X, Y, append_out_aga(U, X, V)) -> U2_GA(X, Y, append_in_gaa(V, W, Y))
   U1_GA(X, Y, append_out_aga(U, X, V)) -> APPEND_IN_GAA(V, W, Y)
   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_GAA(Xs, Ys, Zs)

The TRS R consists of the following rules:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga

SUBLIST_IN_GA(x1, x2)  =  SUBLIST_IN_GA(x1)

U1_GA(x1, x2, x3)  =  U1_GA(x3)

APPEND_IN_AGA(x1, x2, x3)  =  APPEND_IN_AGA(x2)

U3_AGA(x1, x2, x3, x4, x5)  =  U3_AGA(x5)

U2_GA(x1, x2, x3)  =  U2_GA(x3)

APPEND_IN_GAA(x1, x2, x3)  =  APPEND_IN_GAA(x1)

U3_GAA(x1, x2, x3, x4, x5)  =  U3_GAA(x5)


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

(22)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   SUBLIST_IN_GA(X, Y) -> U1_GA(X, Y, append_in_aga(U, X, V))
   SUBLIST_IN_GA(X, Y) -> APPEND_IN_AGA(U, X, V)
   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> U3_AGA(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AGA(Xs, Ys, Zs)
   U1_GA(X, Y, append_out_aga(U, X, V)) -> U2_GA(X, Y, append_in_gaa(V, W, Y))
   U1_GA(X, Y, append_out_aga(U, X, V)) -> APPEND_IN_GAA(V, W, Y)
   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_GAA(Xs, Ys, Zs)

The TRS R consists of the following rules:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga

SUBLIST_IN_GA(x1, x2)  =  SUBLIST_IN_GA(x1)

U1_GA(x1, x2, x3)  =  U1_GA(x3)

APPEND_IN_AGA(x1, x2, x3)  =  APPEND_IN_AGA(x2)

U3_AGA(x1, x2, x3, x4, x5)  =  U3_AGA(x5)

U2_GA(x1, x2, x3)  =  U2_GA(x3)

APPEND_IN_GAA(x1, x2, x3)  =  APPEND_IN_GAA(x1)

U3_GAA(x1, x2, x3, x4, x5)  =  U3_GAA(x5)


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

(23) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes.
----------------------------------------

(24)
Complex Obligation (AND)

----------------------------------------

(25)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_GAA(Xs, Ys, Zs)

The TRS R consists of the following rules:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga

APPEND_IN_GAA(x1, x2, x3)  =  APPEND_IN_GAA(x1)


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

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

(27)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPEND_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_GAA(Xs, Ys, Zs)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

APPEND_IN_GAA(x1, x2, x3)  =  APPEND_IN_GAA(x1)


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

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

(29)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APPEND_IN_GAA(.(Xs)) -> APPEND_IN_GAA(Xs)

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

(30) QDPSizeChangeProof (EQUIVALENT)
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_GAA(.(Xs)) -> APPEND_IN_GAA(Xs)
The graph contains the following edges 1 > 1


----------------------------------------

(31)
YES

----------------------------------------

(32)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AGA(Xs, Ys, Zs)

The TRS R consists of the following rules:

   sublist_in_ga(X, Y) -> U1_ga(X, Y, append_in_aga(U, X, V))
   append_in_aga([], Ys, Ys) -> append_out_aga([], Ys, Ys)
   append_in_aga(.(X, Xs), Ys, .(X, Zs)) -> U3_aga(X, Xs, Ys, Zs, append_in_aga(Xs, Ys, Zs))
   U3_aga(X, Xs, Ys, Zs, append_out_aga(Xs, Ys, Zs)) -> append_out_aga(.(X, Xs), Ys, .(X, Zs))
   U1_ga(X, Y, append_out_aga(U, X, V)) -> U2_ga(X, Y, append_in_gaa(V, W, Y))
   append_in_gaa([], Ys, Ys) -> append_out_gaa([], Ys, Ys)
   append_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, append_in_gaa(Xs, Ys, Zs))
   U3_gaa(X, Xs, Ys, Zs, append_out_gaa(Xs, Ys, Zs)) -> append_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ga(X, Y, append_out_gaa(V, W, Y)) -> sublist_out_ga(X, Y)

The argument filtering Pi contains the following mapping:
sublist_in_ga(x1, x2)  =  sublist_in_ga(x1)

U1_ga(x1, x2, x3)  =  U1_ga(x3)

append_in_aga(x1, x2, x3)  =  append_in_aga(x2)

append_out_aga(x1, x2, x3)  =  append_out_aga(x1, x3)

U3_aga(x1, x2, x3, x4, x5)  =  U3_aga(x5)

.(x1, x2)  =  .(x2)

U2_ga(x1, x2, x3)  =  U2_ga(x3)

append_in_gaa(x1, x2, x3)  =  append_in_gaa(x1)

[]  =  []

append_out_gaa(x1, x2, x3)  =  append_out_gaa

U3_gaa(x1, x2, x3, x4, x5)  =  U3_gaa(x5)

sublist_out_ga(x1, x2)  =  sublist_out_ga

APPEND_IN_AGA(x1, x2, x3)  =  APPEND_IN_AGA(x2)


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

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

(34)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPEND_IN_AGA(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AGA(Xs, Ys, Zs)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

APPEND_IN_AGA(x1, x2, x3)  =  APPEND_IN_AGA(x2)


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

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

(36)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APPEND_IN_AGA(Ys) -> APPEND_IN_AGA(Ys)

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

(37) PrologToTRSTransformerProof (SOUND)
Transformed Prolog program to TRS.

{
    "root": 9,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(sublist X Y)",
                "(',' (append U X V) (append V W Y))"
            ],
            [
                "(append ([]) Ys Ys)",
                null
            ],
            [
                "(append (. X Xs) Ys (. X Zs))",
                "(append Xs Ys Zs)"
            ]
        ]
    },
    "graph": {
        "nodes": {
            "190": {
                "goal": [{
                    "clause": 1,
                    "scope": 3,
                    "term": "(append T16 X15 T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "191": {
                "goal": [{
                    "clause": 2,
                    "scope": 3,
                    "term": "(append T16 X15 T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "160": {
                "goal": [{
                    "clause": 2,
                    "scope": 2,
                    "term": "(append X13 T10 X14)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "171": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append X45 T26 X46)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T26"],
                    "free": [
                        "X45",
                        "X46"
                    ],
                    "exprvars": []
                }
            },
            "type": "Nodes",
            "194": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "162": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "195": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "196": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "164": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "197": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append T44 X76 T45)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X76"],
                    "exprvars": []
                }
            },
            "198": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "145": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append X13 T10 X14)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "156": {
                "goal": [
                    {
                        "clause": 1,
                        "scope": 2,
                        "term": "(append X13 T10 X14)"
                    },
                    {
                        "clause": 2,
                        "scope": 2,
                        "term": "(append X13 T10 X14)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "189": {
                "goal": [
                    {
                        "clause": 1,
                        "scope": 3,
                        "term": "(append T16 X15 T12)"
                    },
                    {
                        "clause": 2,
                        "scope": 3,
                        "term": "(append T16 X15 T12)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "147": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append T16 X15 T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "158": {
                "goal": [{
                    "clause": 1,
                    "scope": 2,
                    "term": "(append X13 T10 X14)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "9": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(sublist T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T1"],
                    "free": [],
                    "exprvars": []
                }
            },
            "94": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (append X13 T10 X14) (append X14 X15 T12))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14",
                        "X15"
                    ],
                    "exprvars": []
                }
            },
            "10": {
                "goal": [{
                    "clause": 0,
                    "scope": 1,
                    "term": "(sublist T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T1"],
                    "free": [],
                    "exprvars": []
                }
            }
        },
        "edges": [
            {
                "from": 9,
                "to": 10,
                "label": "CASE"
            },
            {
                "from": 10,
                "to": 94,
                "label": "ONLY EVAL with clause\nsublist(X11, X12) :- ','(append(X13, X11, X14), append(X14, X15, X12)).\nand substitutionT1 -> T10,\nX11 -> T10,\nT2 -> T12,\nX12 -> T12,\nT11 -> T12"
            },
            {
                "from": 94,
                "to": 145,
                "label": "SPLIT 1"
            },
            {
                "from": 94,
                "to": 147,
                "label": "SPLIT 2\nnew knowledge:\nT10 is ground\nreplacements:X13 -> T15,\nX14 -> T16"
            },
            {
                "from": 145,
                "to": 156,
                "label": "CASE"
            },
            {
                "from": 147,
                "to": 189,
                "label": "CASE"
            },
            {
                "from": 156,
                "to": 158,
                "label": "PARALLEL"
            },
            {
                "from": 156,
                "to": 160,
                "label": "PARALLEL"
            },
            {
                "from": 158,
                "to": 162,
                "label": "ONLY EVAL with clause\nappend([], X24, X24).\nand substitutionX13 -> [],\nT10 -> T22,\nX24 -> T22,\nX14 -> T22"
            },
            {
                "from": 160,
                "to": 171,
                "label": "ONLY EVAL with clause\nappend(.(X40, X41), X42, .(X40, X43)) :- append(X41, X42, X43).\nand substitutionX40 -> X44,\nX41 -> X45,\nX13 -> .(X44, X45),\nT10 -> T26,\nX42 -> T26,\nX43 -> X46,\nX14 -> .(X44, X46)"
            },
            {
                "from": 162,
                "to": 164,
                "label": "SUCCESS"
            },
            {
                "from": 171,
                "to": 145,
                "label": "INSTANCE with matching:\nX13 -> X45\nT10 -> T26\nX14 -> X46"
            },
            {
                "from": 189,
                "to": 190,
                "label": "PARALLEL"
            },
            {
                "from": 189,
                "to": 191,
                "label": "PARALLEL"
            },
            {
                "from": 190,
                "to": 194,
                "label": "EVAL with clause\nappend([], X60, X60).\nand substitutionT16 -> [],\nX15 -> T34,\nX60 -> T34,\nT12 -> T34,\nX61 -> T34"
            },
            {
                "from": 190,
                "to": 195,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 191,
                "to": 197,
                "label": "EVAL with clause\nappend(.(X72, X73), X74, .(X72, X75)) :- append(X73, X74, X75).\nand substitutionX72 -> T41,\nX73 -> T44,\nT16 -> .(T41, T44),\nX15 -> X76,\nX74 -> X76,\nX75 -> T45,\nT12 -> .(T41, T45),\nT42 -> T44,\nT43 -> T45"
            },
            {
                "from": 191,
                "to": 198,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 194,
                "to": 196,
                "label": "SUCCESS"
            },
            {
                "from": 197,
                "to": 147,
                "label": "INSTANCE with matching:\nT16 -> T44\nX15 -> X76\nT12 -> T45"
            }
        ],
        "type": "Graph"
    }
}

----------------------------------------

(38)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   f9_in(T10) -> U1(f94_in(T10), T10)
   U1(f94_out1, T10) -> f9_out1
   f145_in(T22) -> f145_out1
   f145_in(T26) -> U2(f145_in(T26), T26)
   U2(f145_out1, T26) -> f145_out1
   f147_in -> f147_out1
   f147_in -> U3(f147_in)
   U3(f147_out1) -> f147_out1
   f94_in(T10) -> U4(f145_in(T10), T10)
   U4(f145_out1, T10) -> U5(f147_in, T10)
   U5(f147_out1, T10) -> f94_out1

Q is empty.

----------------------------------------

(39) DependencyPairsProof (EQUIVALENT)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
----------------------------------------

(40)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F9_IN(T10) -> U1^1(f94_in(T10), T10)
   F9_IN(T10) -> F94_IN(T10)
   F145_IN(T26) -> U2^1(f145_in(T26), T26)
   F145_IN(T26) -> F145_IN(T26)
   F147_IN -> U3^1(f147_in)
   F147_IN -> F147_IN
   F94_IN(T10) -> U4^1(f145_in(T10), T10)
   F94_IN(T10) -> F145_IN(T10)
   U4^1(f145_out1, T10) -> U5^1(f147_in, T10)
   U4^1(f145_out1, T10) -> F147_IN

The TRS R consists of the following rules:

   f9_in(T10) -> U1(f94_in(T10), T10)
   U1(f94_out1, T10) -> f9_out1
   f145_in(T22) -> f145_out1
   f145_in(T26) -> U2(f145_in(T26), T26)
   U2(f145_out1, T26) -> f145_out1
   f147_in -> f147_out1
   f147_in -> U3(f147_in)
   U3(f147_out1) -> f147_out1
   f94_in(T10) -> U4(f145_in(T10), T10)
   U4(f145_out1, T10) -> U5(f147_in, T10)
   U5(f147_out1, T10) -> f94_out1

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

(41) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 8 less nodes.
----------------------------------------

(42)
Complex Obligation (AND)

----------------------------------------

(43)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F147_IN -> F147_IN

The TRS R consists of the following rules:

   f9_in(T10) -> U1(f94_in(T10), T10)
   U1(f94_out1, T10) -> f9_out1
   f145_in(T22) -> f145_out1
   f145_in(T26) -> U2(f145_in(T26), T26)
   U2(f145_out1, T26) -> f145_out1
   f147_in -> f147_out1
   f147_in -> U3(f147_in)
   U3(f147_out1) -> f147_out1
   f94_in(T10) -> U4(f145_in(T10), T10)
   U4(f145_out1, T10) -> U5(f147_in, T10)
   U5(f147_out1, T10) -> f94_out1

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

(44) MNOCProof (EQUIVALENT)
We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
----------------------------------------

(45)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F147_IN -> F147_IN

The TRS R consists of the following rules:

   f9_in(T10) -> U1(f94_in(T10), T10)
   U1(f94_out1, T10) -> f9_out1
   f145_in(T22) -> f145_out1
   f145_in(T26) -> U2(f145_in(T26), T26)
   U2(f145_out1, T26) -> f145_out1
   f147_in -> f147_out1
   f147_in -> U3(f147_in)
   U3(f147_out1) -> f147_out1
   f94_in(T10) -> U4(f145_in(T10), T10)
   U4(f145_out1, T10) -> U5(f147_in, T10)
   U5(f147_out1, T10) -> f94_out1

The set Q consists of the following terms:

   f9_in(x0)
   U1(f94_out1, x0)
   f145_in(x0)
   U2(f145_out1, x0)
   f147_in
   U3(f147_out1)
   f94_in(x0)
   U4(f145_out1, x0)
   U5(f147_out1, x0)

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

(46) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------

(47)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F147_IN -> F147_IN

R is empty.
The set Q consists of the following terms:

   f9_in(x0)
   U1(f94_out1, x0)
   f145_in(x0)
   U2(f145_out1, x0)
   f147_in
   U3(f147_out1)
   f94_in(x0)
   U4(f145_out1, x0)
   U5(f147_out1, x0)

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

(48) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   f9_in(x0)
   U1(f94_out1, x0)
   f145_in(x0)
   U2(f145_out1, x0)
   f147_in
   U3(f147_out1)
   f94_in(x0)
   U4(f145_out1, x0)
   U5(f147_out1, x0)


----------------------------------------

(49)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F147_IN -> F147_IN

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

(50)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F145_IN(T26) -> F145_IN(T26)

The TRS R consists of the following rules:

   f9_in(T10) -> U1(f94_in(T10), T10)
   U1(f94_out1, T10) -> f9_out1
   f145_in(T22) -> f145_out1
   f145_in(T26) -> U2(f145_in(T26), T26)
   U2(f145_out1, T26) -> f145_out1
   f147_in -> f147_out1
   f147_in -> U3(f147_in)
   U3(f147_out1) -> f147_out1
   f94_in(T10) -> U4(f145_in(T10), T10)
   U4(f145_out1, T10) -> U5(f147_in, T10)
   U5(f147_out1, T10) -> f94_out1

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

(51) MNOCProof (EQUIVALENT)
We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
----------------------------------------

(52)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F145_IN(T26) -> F145_IN(T26)

The TRS R consists of the following rules:

   f9_in(T10) -> U1(f94_in(T10), T10)
   U1(f94_out1, T10) -> f9_out1
   f145_in(T22) -> f145_out1
   f145_in(T26) -> U2(f145_in(T26), T26)
   U2(f145_out1, T26) -> f145_out1
   f147_in -> f147_out1
   f147_in -> U3(f147_in)
   U3(f147_out1) -> f147_out1
   f94_in(T10) -> U4(f145_in(T10), T10)
   U4(f145_out1, T10) -> U5(f147_in, T10)
   U5(f147_out1, T10) -> f94_out1

The set Q consists of the following terms:

   f9_in(x0)
   U1(f94_out1, x0)
   f145_in(x0)
   U2(f145_out1, x0)
   f147_in
   U3(f147_out1)
   f94_in(x0)
   U4(f145_out1, x0)
   U5(f147_out1, x0)

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

(53) UsableRulesProof (EQUIVALENT)
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.
----------------------------------------

(54)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F145_IN(T26) -> F145_IN(T26)

R is empty.
The set Q consists of the following terms:

   f9_in(x0)
   U1(f94_out1, x0)
   f145_in(x0)
   U2(f145_out1, x0)
   f147_in
   U3(f147_out1)
   f94_in(x0)
   U4(f145_out1, x0)
   U5(f147_out1, x0)

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

(55) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   f9_in(x0)
   U1(f94_out1, x0)
   f145_in(x0)
   U2(f145_out1, x0)
   f147_in
   U3(f147_out1)
   f94_in(x0)
   U4(f145_out1, x0)
   U5(f147_out1, x0)


----------------------------------------

(56)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F145_IN(T26) -> F145_IN(T26)

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

(57) PrologToDTProblemTransformerProof (SOUND)
Built DT problem from termination graph DT10.

{
    "root": 19,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(sublist X Y)",
                "(',' (append U X V) (append V W Y))"
            ],
            [
                "(append ([]) Ys Ys)",
                null
            ],
            [
                "(append (. X Xs) Ys (. X Zs))",
                "(append Xs Ys Zs)"
            ]
        ]
    },
    "graph": {
        "nodes": {
            "170": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "type": "Nodes",
            "172": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "173": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "174": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append T31 X49 T33)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T31"],
                    "free": ["X49"],
                    "exprvars": []
                }
            },
            "175": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "132": {
                "goal": [{
                    "clause": 1,
                    "scope": 2,
                    "term": "(',' (append X5 T5 X6) (append X6 X7 T7))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T5"],
                    "free": [
                        "X5",
                        "X6",
                        "X7"
                    ],
                    "exprvars": []
                }
            },
            "133": {
                "goal": [{
                    "clause": 2,
                    "scope": 2,
                    "term": "(',' (append X5 T5 X6) (append X6 X7 T7))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T5"],
                    "free": [
                        "X5",
                        "X6",
                        "X7"
                    ],
                    "exprvars": []
                }
            },
            "199": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "212": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append T63 X130 T64)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X130"],
                    "exprvars": []
                }
            },
            "213": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "19": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(sublist T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T1"],
                    "free": [],
                    "exprvars": []
                }
            },
            "180": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (append X76 T39 X77) (append (. X75 X77) X7 T7))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T39"],
                    "free": [
                        "X7",
                        "X75",
                        "X76",
                        "X77"
                    ],
                    "exprvars": []
                }
            },
            "184": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append X76 T39 X77)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T39"],
                    "free": [
                        "X76",
                        "X77"
                    ],
                    "exprvars": []
                }
            },
            "185": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append (. X75 T42) X7 T7)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [
                        "X7",
                        "X75"
                    ],
                    "exprvars": []
                }
            },
            "186": {
                "goal": [
                    {
                        "clause": 1,
                        "scope": 4,
                        "term": "(append X76 T39 X77)"
                    },
                    {
                        "clause": 2,
                        "scope": 4,
                        "term": "(append X76 T39 X77)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T39"],
                    "free": [
                        "X76",
                        "X77"
                    ],
                    "exprvars": []
                }
            },
            "187": {
                "goal": [{
                    "clause": 1,
                    "scope": 4,
                    "term": "(append X76 T39 X77)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T39"],
                    "free": [
                        "X76",
                        "X77"
                    ],
                    "exprvars": []
                }
            },
            "122": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (append X5 T5 X6) (append X6 X7 T7))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T5"],
                    "free": [
                        "X5",
                        "X6",
                        "X7"
                    ],
                    "exprvars": []
                }
            },
            "166": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append T16 X7 T7)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T16"],
                    "free": ["X7"],
                    "exprvars": []
                }
            },
            "188": {
                "goal": [{
                    "clause": 2,
                    "scope": 4,
                    "term": "(append X76 T39 X77)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T39"],
                    "free": [
                        "X76",
                        "X77"
                    ],
                    "exprvars": []
                }
            },
            "167": {
                "goal": [
                    {
                        "clause": 1,
                        "scope": 3,
                        "term": "(append T16 X7 T7)"
                    },
                    {
                        "clause": 2,
                        "scope": 3,
                        "term": "(append T16 X7 T7)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T16"],
                    "free": ["X7"],
                    "exprvars": []
                }
            },
            "200": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "222": {
                "goal": [
                    {
                        "clause": 1,
                        "scope": 6,
                        "term": "(append T63 X130 T64)"
                    },
                    {
                        "clause": 2,
                        "scope": 6,
                        "term": "(append T63 X130 T64)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X130"],
                    "exprvars": []
                }
            },
            "168": {
                "goal": [{
                    "clause": 1,
                    "scope": 3,
                    "term": "(append T16 X7 T7)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T16"],
                    "free": ["X7"],
                    "exprvars": []
                }
            },
            "201": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append X107 T52 X108)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T52"],
                    "free": [
                        "X107",
                        "X108"
                    ],
                    "exprvars": []
                }
            },
            "223": {
                "goal": [{
                    "clause": 1,
                    "scope": 6,
                    "term": "(append T63 X130 T64)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X130"],
                    "exprvars": []
                }
            },
            "125": {
                "goal": [
                    {
                        "clause": 1,
                        "scope": 2,
                        "term": "(',' (append X5 T5 X6) (append X6 X7 T7))"
                    },
                    {
                        "clause": 2,
                        "scope": 2,
                        "term": "(',' (append X5 T5 X6) (append X6 X7 T7))"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T5"],
                    "free": [
                        "X5",
                        "X6",
                        "X7"
                    ],
                    "exprvars": []
                }
            },
            "169": {
                "goal": [{
                    "clause": 2,
                    "scope": 3,
                    "term": "(append T16 X7 T7)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T16"],
                    "free": ["X7"],
                    "exprvars": []
                }
            },
            "202": {
                "goal": [
                    {
                        "clause": 1,
                        "scope": 5,
                        "term": "(append (. X75 T42) X7 T7)"
                    },
                    {
                        "clause": 2,
                        "scope": 5,
                        "term": "(append (. X75 T42) X7 T7)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [
                        "X7",
                        "X75"
                    ],
                    "exprvars": []
                }
            },
            "224": {
                "goal": [{
                    "clause": 2,
                    "scope": 6,
                    "term": "(append T63 X130 T64)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X130"],
                    "exprvars": []
                }
            },
            "203": {
                "goal": [{
                    "clause": 2,
                    "scope": 5,
                    "term": "(append (. X75 T42) X7 T7)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [
                        "X7",
                        "X75"
                    ],
                    "exprvars": []
                }
            },
            "225": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "226": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "227": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "228": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append T81 X159 T82)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X159"],
                    "exprvars": []
                }
            },
            "229": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "20": {
                "goal": [{
                    "clause": 0,
                    "scope": 1,
                    "term": "(sublist T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T1"],
                    "free": [],
                    "exprvars": []
                }
            }
        },
        "edges": [
            {
                "from": 19,
                "to": 20,
                "label": "CASE"
            },
            {
                "from": 20,
                "to": 122,
                "label": "ONLY EVAL with clause\nsublist(X3, X4) :- ','(append(X5, X3, X6), append(X6, X7, X4)).\nand substitutionT1 -> T5,\nX3 -> T5,\nT2 -> T7,\nX4 -> T7,\nT6 -> T7"
            },
            {
                "from": 122,
                "to": 125,
                "label": "CASE"
            },
            {
                "from": 125,
                "to": 132,
                "label": "PARALLEL"
            },
            {
                "from": 125,
                "to": 133,
                "label": "PARALLEL"
            },
            {
                "from": 132,
                "to": 166,
                "label": "ONLY EVAL with clause\nappend([], X20, X20).\nand substitutionX5 -> [],\nT5 -> T16,\nX20 -> T16,\nX6 -> T16"
            },
            {
                "from": 133,
                "to": 180,
                "label": "ONLY EVAL with clause\nappend(.(X71, X72), X73, .(X71, X74)) :- append(X72, X73, X74).\nand substitutionX71 -> X75,\nX72 -> X76,\nX5 -> .(X75, X76),\nT5 -> T39,\nX73 -> T39,\nX74 -> X77,\nX6 -> .(X75, X77)"
            },
            {
                "from": 166,
                "to": 167,
                "label": "CASE"
            },
            {
                "from": 167,
                "to": 168,
                "label": "PARALLEL"
            },
            {
                "from": 167,
                "to": 169,
                "label": "PARALLEL"
            },
            {
                "from": 168,
                "to": 170,
                "label": "EVAL with clause\nappend([], X33, X33).\nand substitutionT16 -> [],\nX7 -> T23,\nX33 -> T23,\nT7 -> T23,\nX34 -> T23"
            },
            {
                "from": 168,
                "to": 172,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 169,
                "to": 174,
                "label": "EVAL with clause\nappend(.(X45, X46), X47, .(X45, X48)) :- append(X46, X47, X48).\nand substitutionX45 -> T30,\nX46 -> T31,\nT16 -> .(T30, T31),\nX7 -> X49,\nX47 -> X49,\nX48 -> T33,\nT7 -> .(T30, T33),\nT32 -> T33"
            },
            {
                "from": 169,
                "to": 175,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 170,
                "to": 173,
                "label": "SUCCESS"
            },
            {
                "from": 174,
                "to": 166,
                "label": "INSTANCE with matching:\nT16 -> T31\nX7 -> X49\nT7 -> T33"
            },
            {
                "from": 180,
                "to": 184,
                "label": "SPLIT 1"
            },
            {
                "from": 180,
                "to": 185,
                "label": "SPLIT 2\nnew knowledge:\nT39 is ground\nreplacements:X76 -> T41,\nX77 -> T42"
            },
            {
                "from": 184,
                "to": 186,
                "label": "CASE"
            },
            {
                "from": 185,
                "to": 202,
                "label": "CASE"
            },
            {
                "from": 186,
                "to": 187,
                "label": "PARALLEL"
            },
            {
                "from": 186,
                "to": 188,
                "label": "PARALLEL"
            },
            {
                "from": 187,
                "to": 199,
                "label": "ONLY EVAL with clause\nappend([], X86, X86).\nand substitutionX76 -> [],\nT39 -> T48,\nX86 -> T48,\nX77 -> T48"
            },
            {
                "from": 188,
                "to": 201,
                "label": "ONLY EVAL with clause\nappend(.(X102, X103), X104, .(X102, X105)) :- append(X103, X104, X105).\nand substitutionX102 -> X106,\nX103 -> X107,\nX76 -> .(X106, X107),\nT39 -> T52,\nX104 -> T52,\nX105 -> X108,\nX77 -> .(X106, X108)"
            },
            {
                "from": 199,
                "to": 200,
                "label": "SUCCESS"
            },
            {
                "from": 201,
                "to": 184,
                "label": "INSTANCE with matching:\nX76 -> X107\nT39 -> T52\nX77 -> X108"
            },
            {
                "from": 202,
                "to": 203,
                "label": "BACKTRACK\nfor clause: append([], Ys, Ys)because of non-unification"
            },
            {
                "from": 203,
                "to": 212,
                "label": "EVAL with clause\nappend(.(X125, X126), X127, .(X125, X128)) :- append(X126, X127, X128).\nand substitutionX75 -> T61,\nX125 -> T61,\nT42 -> T63,\nX126 -> T63,\nX7 -> X130,\nX127 -> X130,\nX129 -> T61,\nX128 -> T64,\nT7 -> .(T61, T64),\nT60 -> T63,\nT62 -> T64"
            },
            {
                "from": 203,
                "to": 213,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 212,
                "to": 222,
                "label": "CASE"
            },
            {
                "from": 222,
                "to": 223,
                "label": "PARALLEL"
            },
            {
                "from": 222,
                "to": 224,
                "label": "PARALLEL"
            },
            {
                "from": 223,
                "to": 225,
                "label": "EVAL with clause\nappend([], X143, X143).\nand substitutionT63 -> [],\nX130 -> T71,\nX143 -> T71,\nT64 -> T71,\nX144 -> T71"
            },
            {
                "from": 223,
                "to": 226,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 224,
                "to": 228,
                "label": "EVAL with clause\nappend(.(X155, X156), X157, .(X155, X158)) :- append(X156, X157, X158).\nand substitutionX155 -> T78,\nX156 -> T81,\nT63 -> .(T78, T81),\nX130 -> X159,\nX157 -> X159,\nX158 -> T82,\nT64 -> .(T78, T82),\nT79 -> T81,\nT80 -> T82"
            },
            {
                "from": 224,
                "to": 229,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 225,
                "to": 227,
                "label": "SUCCESS"
            },
            {
                "from": 228,
                "to": 212,
                "label": "INSTANCE with matching:\nT63 -> T81\nX130 -> X159\nT64 -> T82"
            }
        ],
        "type": "Graph"
    }
}

----------------------------------------

(58)
Obligation:
Triples:

appendA(.(X1, X2), X3, .(X1, X4)) :- appendA(X2, X3, X4).
appendB(.(X1, X2), X3, .(X1, X4)) :- appendB(X2, X3, X4).
appendC(.(X1, X2), X3, .(X1, X4)) :- appendC(X2, X3, X4).
sublistD(X1, X2) :- appendA(X1, X3, X2).
sublistD(X1, X2) :- appendB(X3, X1, X4).
sublistD(X1, .(X2, X3)) :- ','(appendcB(X4, X1, X5), appendC(X5, X6, X3)).

Clauses:

appendcA([], X1, X1).
appendcA(.(X1, X2), X3, .(X1, X4)) :- appendcA(X2, X3, X4).
appendcB([], X1, X1).
appendcB(.(X1, X2), X3, .(X1, X4)) :- appendcB(X2, X3, X4).
appendcC([], X1, X1).
appendcC(.(X1, X2), X3, .(X1, X4)) :- appendcC(X2, X3, X4).

Afs:

sublistD(x1, x2)  =  sublistD(x1)


----------------------------------------

(59) TriplesToPiDPProof (SOUND)
We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes:

sublistD_in_2: (b,f)

appendA_in_3: (b,f,f)

appendB_in_3: (f,b,f)

appendcB_in_3: (f,b,f)

appendC_in_3: (b,f,f)

Transforming TRIPLES into the following Term Rewriting System:

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

   SUBLISTD_IN_GA(X1, X2) -> U4_GA(X1, X2, appendA_in_gaa(X1, X3, X2))
   SUBLISTD_IN_GA(X1, X2) -> APPENDA_IN_GAA(X1, X3, X2)
   APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U1_GAA(X1, X2, X3, X4, appendA_in_gaa(X2, X3, X4))
   APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_GAA(X2, X3, X4)
   SUBLISTD_IN_GA(X1, X2) -> U5_GA(X1, X2, appendB_in_aga(X3, X1, X4))
   SUBLISTD_IN_GA(X1, X2) -> APPENDB_IN_AGA(X3, X1, X4)
   APPENDB_IN_AGA(.(X1, X2), X3, .(X1, X4)) -> U2_AGA(X1, X2, X3, X4, appendB_in_aga(X2, X3, X4))
   APPENDB_IN_AGA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AGA(X2, X3, X4)
   SUBLISTD_IN_GA(X1, .(X2, X3)) -> U6_GA(X1, X2, X3, appendcB_in_aga(X4, X1, X5))
   U6_GA(X1, X2, X3, appendcB_out_aga(X4, X1, X5)) -> U7_GA(X1, X2, X3, appendC_in_gaa(X5, X6, X3))
   U6_GA(X1, X2, X3, appendcB_out_aga(X4, X1, X5)) -> APPENDC_IN_GAA(X5, X6, X3)
   APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U3_GAA(X1, X2, X3, X4, appendC_in_gaa(X2, X3, X4))
   APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4)

The TRS R consists of the following rules:

   appendcB_in_aga([], X1, X1) -> appendcB_out_aga([], X1, X1)
   appendcB_in_aga(.(X1, X2), X3, .(X1, X4)) -> U10_aga(X1, X2, X3, X4, appendcB_in_aga(X2, X3, X4))
   U10_aga(X1, X2, X3, X4, appendcB_out_aga(X2, X3, X4)) -> appendcB_out_aga(.(X1, X2), X3, .(X1, X4))

The argument filtering Pi contains the following mapping:
appendA_in_gaa(x1, x2, x3)  =  appendA_in_gaa(x1)

.(x1, x2)  =  .(x2)

appendB_in_aga(x1, x2, x3)  =  appendB_in_aga(x2)

appendcB_in_aga(x1, x2, x3)  =  appendcB_in_aga(x2)

appendcB_out_aga(x1, x2, x3)  =  appendcB_out_aga(x1, x2, x3)

U10_aga(x1, x2, x3, x4, x5)  =  U10_aga(x3, x5)

appendC_in_gaa(x1, x2, x3)  =  appendC_in_gaa(x1)

SUBLISTD_IN_GA(x1, x2)  =  SUBLISTD_IN_GA(x1)

U4_GA(x1, x2, x3)  =  U4_GA(x1, x3)

APPENDA_IN_GAA(x1, x2, x3)  =  APPENDA_IN_GAA(x1)

U1_GAA(x1, x2, x3, x4, x5)  =  U1_GAA(x2, x5)

U5_GA(x1, x2, x3)  =  U5_GA(x1, x3)

APPENDB_IN_AGA(x1, x2, x3)  =  APPENDB_IN_AGA(x2)

U2_AGA(x1, x2, x3, x4, x5)  =  U2_AGA(x3, x5)

U6_GA(x1, x2, x3, x4)  =  U6_GA(x1, x4)

U7_GA(x1, x2, x3, x4)  =  U7_GA(x1, x4)

APPENDC_IN_GAA(x1, x2, x3)  =  APPENDC_IN_GAA(x1)

U3_GAA(x1, x2, x3, x4, x5)  =  U3_GAA(x2, x5)


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


Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES



----------------------------------------

(60)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   SUBLISTD_IN_GA(X1, X2) -> U4_GA(X1, X2, appendA_in_gaa(X1, X3, X2))
   SUBLISTD_IN_GA(X1, X2) -> APPENDA_IN_GAA(X1, X3, X2)
   APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U1_GAA(X1, X2, X3, X4, appendA_in_gaa(X2, X3, X4))
   APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_GAA(X2, X3, X4)
   SUBLISTD_IN_GA(X1, X2) -> U5_GA(X1, X2, appendB_in_aga(X3, X1, X4))
   SUBLISTD_IN_GA(X1, X2) -> APPENDB_IN_AGA(X3, X1, X4)
   APPENDB_IN_AGA(.(X1, X2), X3, .(X1, X4)) -> U2_AGA(X1, X2, X3, X4, appendB_in_aga(X2, X3, X4))
   APPENDB_IN_AGA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AGA(X2, X3, X4)
   SUBLISTD_IN_GA(X1, .(X2, X3)) -> U6_GA(X1, X2, X3, appendcB_in_aga(X4, X1, X5))
   U6_GA(X1, X2, X3, appendcB_out_aga(X4, X1, X5)) -> U7_GA(X1, X2, X3, appendC_in_gaa(X5, X6, X3))
   U6_GA(X1, X2, X3, appendcB_out_aga(X4, X1, X5)) -> APPENDC_IN_GAA(X5, X6, X3)
   APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U3_GAA(X1, X2, X3, X4, appendC_in_gaa(X2, X3, X4))
   APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4)

The TRS R consists of the following rules:

   appendcB_in_aga([], X1, X1) -> appendcB_out_aga([], X1, X1)
   appendcB_in_aga(.(X1, X2), X3, .(X1, X4)) -> U10_aga(X1, X2, X3, X4, appendcB_in_aga(X2, X3, X4))
   U10_aga(X1, X2, X3, X4, appendcB_out_aga(X2, X3, X4)) -> appendcB_out_aga(.(X1, X2), X3, .(X1, X4))

The argument filtering Pi contains the following mapping:
appendA_in_gaa(x1, x2, x3)  =  appendA_in_gaa(x1)

.(x1, x2)  =  .(x2)

appendB_in_aga(x1, x2, x3)  =  appendB_in_aga(x2)

appendcB_in_aga(x1, x2, x3)  =  appendcB_in_aga(x2)

appendcB_out_aga(x1, x2, x3)  =  appendcB_out_aga(x1, x2, x3)

U10_aga(x1, x2, x3, x4, x5)  =  U10_aga(x3, x5)

appendC_in_gaa(x1, x2, x3)  =  appendC_in_gaa(x1)

SUBLISTD_IN_GA(x1, x2)  =  SUBLISTD_IN_GA(x1)

U4_GA(x1, x2, x3)  =  U4_GA(x1, x3)

APPENDA_IN_GAA(x1, x2, x3)  =  APPENDA_IN_GAA(x1)

U1_GAA(x1, x2, x3, x4, x5)  =  U1_GAA(x2, x5)

U5_GA(x1, x2, x3)  =  U5_GA(x1, x3)

APPENDB_IN_AGA(x1, x2, x3)  =  APPENDB_IN_AGA(x2)

U2_AGA(x1, x2, x3, x4, x5)  =  U2_AGA(x3, x5)

U6_GA(x1, x2, x3, x4)  =  U6_GA(x1, x4)

U7_GA(x1, x2, x3, x4)  =  U7_GA(x1, x4)

APPENDC_IN_GAA(x1, x2, x3)  =  APPENDC_IN_GAA(x1)

U3_GAA(x1, x2, x3, x4, x5)  =  U3_GAA(x2, x5)


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

(61) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 10 less nodes.
----------------------------------------

(62)
Complex Obligation (AND)

----------------------------------------

(63)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4)

The TRS R consists of the following rules:

   appendcB_in_aga([], X1, X1) -> appendcB_out_aga([], X1, X1)
   appendcB_in_aga(.(X1, X2), X3, .(X1, X4)) -> U10_aga(X1, X2, X3, X4, appendcB_in_aga(X2, X3, X4))
   U10_aga(X1, X2, X3, X4, appendcB_out_aga(X2, X3, X4)) -> appendcB_out_aga(.(X1, X2), X3, .(X1, X4))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

appendcB_in_aga(x1, x2, x3)  =  appendcB_in_aga(x2)

appendcB_out_aga(x1, x2, x3)  =  appendcB_out_aga(x1, x2, x3)

U10_aga(x1, x2, x3, x4, x5)  =  U10_aga(x3, x5)

APPENDC_IN_GAA(x1, x2, x3)  =  APPENDC_IN_GAA(x1)


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

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

(65)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

APPENDC_IN_GAA(x1, x2, x3)  =  APPENDC_IN_GAA(x1)


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

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

(67)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APPENDC_IN_GAA(.(X2)) -> APPENDC_IN_GAA(X2)

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

(68) QDPSizeChangeProof (EQUIVALENT)
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:
*APPENDC_IN_GAA(.(X2)) -> APPENDC_IN_GAA(X2)
The graph contains the following edges 1 > 1


----------------------------------------

(69)
YES

----------------------------------------

(70)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPENDB_IN_AGA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AGA(X2, X3, X4)

The TRS R consists of the following rules:

   appendcB_in_aga([], X1, X1) -> appendcB_out_aga([], X1, X1)
   appendcB_in_aga(.(X1, X2), X3, .(X1, X4)) -> U10_aga(X1, X2, X3, X4, appendcB_in_aga(X2, X3, X4))
   U10_aga(X1, X2, X3, X4, appendcB_out_aga(X2, X3, X4)) -> appendcB_out_aga(.(X1, X2), X3, .(X1, X4))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

appendcB_in_aga(x1, x2, x3)  =  appendcB_in_aga(x2)

appendcB_out_aga(x1, x2, x3)  =  appendcB_out_aga(x1, x2, x3)

U10_aga(x1, x2, x3, x4, x5)  =  U10_aga(x3, x5)

APPENDB_IN_AGA(x1, x2, x3)  =  APPENDB_IN_AGA(x2)


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

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

(72)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPENDB_IN_AGA(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AGA(X2, X3, X4)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

APPENDB_IN_AGA(x1, x2, x3)  =  APPENDB_IN_AGA(x2)


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

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

(74)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   APPENDB_IN_AGA(X3) -> APPENDB_IN_AGA(X3)

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

(75)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_GAA(X2, X3, X4)

The TRS R consists of the following rules:

   appendcB_in_aga([], X1, X1) -> appendcB_out_aga([], X1, X1)
   appendcB_in_aga(.(X1, X2), X3, .(X1, X4)) -> U10_aga(X1, X2, X3, X4, appendcB_in_aga(X2, X3, X4))
   U10_aga(X1, X2, X3, X4, appendcB_out_aga(X2, X3, X4)) -> appendcB_out_aga(.(X1, X2), X3, .(X1, X4))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

appendcB_in_aga(x1, x2, x3)  =  appendcB_in_aga(x2)

appendcB_out_aga(x1, x2, x3)  =  appendcB_out_aga(x1, x2, x3)

U10_aga(x1, x2, x3, x4, x5)  =  U10_aga(x3, x5)

APPENDA_IN_GAA(x1, x2, x3)  =  APPENDA_IN_GAA(x1)


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

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

(77)
Obligation:
Pi DP problem:
The TRS P consists of the following rules:

   APPENDA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDA_IN_GAA(X2, X3, X4)

R is empty.
The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x2)

APPENDA_IN_GAA(x1, x2, x3)  =  APPENDA_IN_GAA(x1)


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

(78) PrologToIRSwTTransformerProof (SOUND)
Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert

{
    "root": 6,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(sublist X Y)",
                "(',' (append U X V) (append V W Y))"
            ],
            [
                "(append ([]) Ys Ys)",
                null
            ],
            [
                "(append (. X Xs) Ys (. X Zs))",
                "(append Xs Ys Zs)"
            ]
        ]
    },
    "graph": {
        "nodes": {
            "11": {
                "goal": [{
                    "clause": 0,
                    "scope": 1,
                    "term": "(sublist T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T1"],
                    "free": [],
                    "exprvars": []
                }
            },
            "46": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (append X13 T10 X14) (append X14 X15 T12))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14",
                        "X15"
                    ],
                    "exprvars": []
                }
            },
            "181": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "192": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append T44 X76 T45)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X76"],
                    "exprvars": []
                }
            },
            "182": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "193": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "type": "Nodes",
            "161": {
                "goal": [{
                    "clause": 2,
                    "scope": 2,
                    "term": "(append X13 T10 X14)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "183": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "163": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "154": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append X13 T10 X14)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "165": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "176": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append X45 T26 X46)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T26"],
                    "free": [
                        "X45",
                        "X46"
                    ],
                    "exprvars": []
                }
            },
            "155": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(append T16 X15 T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "177": {
                "goal": [
                    {
                        "clause": 1,
                        "scope": 3,
                        "term": "(append T16 X15 T12)"
                    },
                    {
                        "clause": 2,
                        "scope": 3,
                        "term": "(append T16 X15 T12)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "178": {
                "goal": [{
                    "clause": 1,
                    "scope": 3,
                    "term": "(append T16 X15 T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "157": {
                "goal": [
                    {
                        "clause": 1,
                        "scope": 2,
                        "term": "(append X13 T10 X14)"
                    },
                    {
                        "clause": 2,
                        "scope": 2,
                        "term": "(append X13 T10 X14)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "179": {
                "goal": [{
                    "clause": 2,
                    "scope": 3,
                    "term": "(append T16 X15 T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "159": {
                "goal": [{
                    "clause": 1,
                    "scope": 2,
                    "term": "(append X13 T10 X14)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "6": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(sublist T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T1"],
                    "free": [],
                    "exprvars": []
                }
            }
        },
        "edges": [
            {
                "from": 6,
                "to": 11,
                "label": "CASE"
            },
            {
                "from": 11,
                "to": 46,
                "label": "ONLY EVAL with clause\nsublist(X11, X12) :- ','(append(X13, X11, X14), append(X14, X15, X12)).\nand substitutionT1 -> T10,\nX11 -> T10,\nT2 -> T12,\nX12 -> T12,\nT11 -> T12"
            },
            {
                "from": 46,
                "to": 154,
                "label": "SPLIT 1"
            },
            {
                "from": 46,
                "to": 155,
                "label": "SPLIT 2\nnew knowledge:\nT10 is ground\nreplacements:X13 -> T15,\nX14 -> T16"
            },
            {
                "from": 154,
                "to": 157,
                "label": "CASE"
            },
            {
                "from": 155,
                "to": 177,
                "label": "CASE"
            },
            {
                "from": 157,
                "to": 159,
                "label": "PARALLEL"
            },
            {
                "from": 157,
                "to": 161,
                "label": "PARALLEL"
            },
            {
                "from": 159,
                "to": 163,
                "label": "ONLY EVAL with clause\nappend([], X24, X24).\nand substitutionX13 -> [],\nT10 -> T22,\nX24 -> T22,\nX14 -> T22"
            },
            {
                "from": 161,
                "to": 176,
                "label": "ONLY EVAL with clause\nappend(.(X40, X41), X42, .(X40, X43)) :- append(X41, X42, X43).\nand substitutionX40 -> X44,\nX41 -> X45,\nX13 -> .(X44, X45),\nT10 -> T26,\nX42 -> T26,\nX43 -> X46,\nX14 -> .(X44, X46)"
            },
            {
                "from": 163,
                "to": 165,
                "label": "SUCCESS"
            },
            {
                "from": 176,
                "to": 154,
                "label": "INSTANCE with matching:\nX13 -> X45\nT10 -> T26\nX14 -> X46"
            },
            {
                "from": 177,
                "to": 178,
                "label": "PARALLEL"
            },
            {
                "from": 177,
                "to": 179,
                "label": "PARALLEL"
            },
            {
                "from": 178,
                "to": 181,
                "label": "EVAL with clause\nappend([], X60, X60).\nand substitutionT16 -> [],\nX15 -> T34,\nX60 -> T34,\nT12 -> T34,\nX61 -> T34"
            },
            {
                "from": 178,
                "to": 182,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 179,
                "to": 192,
                "label": "EVAL with clause\nappend(.(X72, X73), X74, .(X72, X75)) :- append(X73, X74, X75).\nand substitutionX72 -> T41,\nX73 -> T44,\nT16 -> .(T41, T44),\nX15 -> X76,\nX74 -> X76,\nX75 -> T45,\nT12 -> .(T41, T45),\nT42 -> T44,\nT43 -> T45"
            },
            {
                "from": 179,
                "to": 193,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 181,
                "to": 183,
                "label": "SUCCESS"
            },
            {
                "from": 192,
                "to": 155,
                "label": "INSTANCE with matching:\nT16 -> T44\nX15 -> X76\nT12 -> T45"
            }
        ],
        "type": "Graph"
    }
}

----------------------------------------

(79)
Complex Obligation (AND)

----------------------------------------

(80)
Obligation:
Rules:
f155_out -> f192_out :|: TRUE
f192_in -> f155_in :|: TRUE
f177_out -> f155_out :|: TRUE
f155_in -> f177_in :|: TRUE
f178_out -> f177_out :|: TRUE
f179_out -> f177_out :|: TRUE
f177_in -> f178_in :|: TRUE
f177_in -> f179_in :|: TRUE
f193_out -> f179_out :|: TRUE
f179_in -> f192_in :|: TRUE
f179_in -> f193_in :|: TRUE
f192_out -> f179_out :|: TRUE
f11_out(T1) -> f6_out(T1) :|: TRUE
f6_in(x) -> f11_in(x) :|: TRUE
f11_in(T10) -> f46_in(T10) :|: TRUE
f46_out(x1) -> f11_out(x1) :|: TRUE
f154_out(x2) -> f155_in :|: TRUE
f46_in(x3) -> f154_in(x3) :|: TRUE
f155_out -> f46_out(x4) :|: TRUE
Start term: f6_in(T1)

----------------------------------------

(81) IRSwTSimpleDependencyGraphProof (EQUIVALENT)
Constructed simple dependency graph.

Simplified to the following IRSwTs:


----------------------------------------

(82)
TRUE

----------------------------------------

(83)
Obligation:
Rules:
f161_in(T26) -> f176_in(T26) :|: TRUE
f176_out(x) -> f161_out(x) :|: TRUE
f176_in(x1) -> f154_in(x1) :|: TRUE
f154_out(x2) -> f176_out(x2) :|: TRUE
f157_out(T10) -> f154_out(T10) :|: TRUE
f154_in(x3) -> f157_in(x3) :|: TRUE
f161_out(x4) -> f157_out(x4) :|: TRUE
f157_in(x5) -> f159_in(x5) :|: TRUE
f159_out(x6) -> f157_out(x6) :|: TRUE
f157_in(x7) -> f161_in(x7) :|: TRUE
f11_out(T1) -> f6_out(T1) :|: TRUE
f6_in(x8) -> f11_in(x8) :|: TRUE
f11_in(x9) -> f46_in(x9) :|: TRUE
f46_out(x10) -> f11_out(x10) :|: TRUE
f154_out(x11) -> f155_in :|: TRUE
f46_in(x12) -> f154_in(x12) :|: TRUE
f155_out -> f46_out(x13) :|: TRUE
Start term: f6_in(T1)

----------------------------------------

(84) IRSwTSimpleDependencyGraphProof (EQUIVALENT)
Constructed simple dependency graph.

Simplified to the following IRSwTs:

intTRSProblem:
f161_in(T26) -> f176_in(T26) :|: TRUE
f176_in(x1) -> f154_in(x1) :|: TRUE
f154_in(x3) -> f157_in(x3) :|: TRUE
f157_in(x7) -> f161_in(x7) :|: TRUE


----------------------------------------

(85)
Obligation:
Rules:
f161_in(T26) -> f176_in(T26) :|: TRUE
f176_in(x1) -> f154_in(x1) :|: TRUE
f154_in(x3) -> f157_in(x3) :|: TRUE
f157_in(x7) -> f161_in(x7) :|: TRUE

----------------------------------------

(86) IntTRSCompressionProof (EQUIVALENT)
Compressed rules.
----------------------------------------

(87)
Obligation:
Rules:
f161_in(T26:0) -> f161_in(T26:0) :|: TRUE

----------------------------------------

(88) IRSFormatTransformerProof (EQUIVALENT)
Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %).
----------------------------------------

(89)
Obligation:
Rules:
f161_in(T26:0) -> f161_in(T26:0) :|: TRUE

----------------------------------------

(90) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f161_in(T26:0) -> f161_in(T26:0) :|: TRUE

Arcs:
(1) -> (1)

This digraph is fully evaluated!
----------------------------------------

(91)
Obligation:

Termination digraph:
Nodes:
(1) f161_in(T26:0) -> f161_in(T26:0) :|: TRUE

Arcs:
(1) -> (1)

This digraph is fully evaluated!

----------------------------------------

(92) FilterProof (EQUIVALENT)
Used the following sort dictionary for filtering: 
f161_in(VARIABLE)
Replaced non-predefined constructor symbols by 0.
----------------------------------------

(93)
Obligation:
Rules:
f161_in(T26:0) -> f161_in(T26:0) :|: TRUE

----------------------------------------

(94) IntTRSNonPeriodicNontermProof (COMPLETE)
Normalized system to the following form:
f(pc, T26:0) -> f(1, T26:0) :|: pc = 1 && TRUE
Proved unsatisfiability of the following formula, indicating that the system is never left after entering:
(((run2_0 = ((1 * 1)) and run2_1 = ((run1_1 * 1))) and (((run1_0 * 1)) = ((1 * 1)) and T)) and !(((run2_0 * 1)) = ((1 * 1)) and T))
Proved satisfiability of the following formula, indicating that the system is entered at least once:
((run2_0 = ((1 * 1)) and run2_1 = ((run1_1 * 1))) and (((run1_0 * 1)) = ((1 * 1)) and T))

----------------------------------------

(95)
NO