/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

perm(a,g)

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

(0) Prolog
(1) PrologToPiTRSProof [SOUND, 0 ms]
(2) PiTRS
    (3) DependencyPairsProof [EQUIVALENT, 13 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) NonTerminationLoopProof [COMPLETE, 0 ms]
            (20) NO
        (21) PiDP
            (22) UsableRulesProof [EQUIVALENT, 0 ms]
            (23) PiDP
            (24) PiDPToQDPProof [SOUND, 2 ms]
            (25) QDP
            (26) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (27) YES
(28) PrologToPiTRSProof [SOUND, 0 ms]
(29) PiTRS
    (30) DependencyPairsProof [EQUIVALENT, 7 ms]
    (31) PiDP
    (32) DependencyGraphProof [EQUIVALENT, 0 ms]
    (33) AND
        (34) PiDP
            (35) UsableRulesProof [EQUIVALENT, 0 ms]
            (36) PiDP
            (37) PiDPToQDPProof [SOUND, 0 ms]
            (38) QDP
            (39) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (40) YES
        (41) PiDP
            (42) UsableRulesProof [EQUIVALENT, 0 ms]
            (43) PiDP
            (44) PiDPToQDPProof [SOUND, 0 ms]
            (45) QDP
            (46) NonTerminationLoopProof [COMPLETE, 0 ms]
            (47) NO
        (48) PiDP
            (49) UsableRulesProof [EQUIVALENT, 0 ms]
            (50) PiDP
            (51) PiDPToQDPProof [SOUND, 0 ms]
            (52) QDP
            (53) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (54) YES
(55) PrologToTRSTransformerProof [SOUND, 0 ms]
(56) QTRS
    (57) DependencyPairsProof [EQUIVALENT, 0 ms]
    (58) QDP
    (59) DependencyGraphProof [EQUIVALENT, 0 ms]
    (60) AND
        (61) QDP
            (62) MNOCProof [EQUIVALENT, 0 ms]
            (63) QDP
            (64) UsableRulesProof [EQUIVALENT, 0 ms]
            (65) QDP
            (66) QReductionProof [EQUIVALENT, 0 ms]
            (67) QDP
            (68) NonTerminationLoopProof [COMPLETE, 0 ms]
            (69) NO
        (70) QDP
            (71) MNOCProof [EQUIVALENT, 0 ms]
            (72) QDP
            (73) UsableRulesProof [EQUIVALENT, 0 ms]
            (74) QDP
            (75) QReductionProof [EQUIVALENT, 0 ms]
            (76) QDP
            (77) NonTerminationLoopProof [COMPLETE, 0 ms]
            (78) NO
        (79) QDP
            (80) MNOCProof [EQUIVALENT, 0 ms]
            (81) QDP
            (82) UsableRulesProof [EQUIVALENT, 0 ms]
            (83) QDP
            (84) QReductionProof [EQUIVALENT, 0 ms]
            (85) QDP
            (86) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (87) YES
(88) PrologToIRSwTTransformerProof [SOUND, 50 ms]
(89) AND
    (90) IRSwT
        (91) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms]
        (92) TRUE
    (93) IRSwT
        (94) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms]
        (95) IRSwT
        (96) IntTRSCompressionProof [EQUIVALENT, 21 ms]
        (97) IRSwT
        (98) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
        (99) IRSwT
        (100) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms]
        (101) IRSwT
        (102) FilterProof [EQUIVALENT, 0 ms]
        (103) IntTRS
        (104) IntTRSPeriodicNontermProof [COMPLETE, 6 ms]
        (105) NO
    (106) IRSwT
        (107) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms]
        (108) IRSwT
        (109) IntTRSCompressionProof [EQUIVALENT, 18 ms]
        (110) IRSwT
        (111) IRSFormatTransformerProof [EQUIVALENT, 0 ms]
        (112) IRSwT
(113) PrologToDTProblemTransformerProof [SOUND, 50 ms]
(114) TRIPLES
    (115) TriplesToPiDPProof [SOUND, 0 ms]
    (116) PiDP
    (117) DependencyGraphProof [EQUIVALENT, 0 ms]
    (118) AND
        (119) PiDP
            (120) UsableRulesProof [EQUIVALENT, 0 ms]
            (121) PiDP
            (122) PiDPToQDPProof [SOUND, 0 ms]
            (123) QDP
            (124) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (125) YES
        (126) PiDP
            (127) UsableRulesProof [EQUIVALENT, 0 ms]
            (128) PiDP
            (129) PiDPToQDPProof [SOUND, 0 ms]
            (130) QDP
            (131) NonTerminationLoopProof [COMPLETE, 0 ms]
            (132) NO
        (133) PiDP
            (134) PiDPToQDPProof [SOUND, 0 ms]
            (135) QDP
            (136) QDPSizeChangeProof [EQUIVALENT, 0 ms]
            (137) YES


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

(0)
Obligation:
Clauses:

perm([], []).
perm(Xs, .(X, Ys)) :- ','(app(X1s, .(X, X2s), Xs), ','(app(X1s, X2s, Zs), perm(Zs, Ys))).
app([], X, X).
app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs).


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

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

perm_in_2: (f,b)

app_in_3: (f,f,f) (b,f,f)

Transforming Prolog into the following Term Rewriting System:

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

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag(x2)

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)

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

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





Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog



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

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

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag(x2)

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)

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

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



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

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

   PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   PERM_IN_AG(Xs, .(X, Ys)) -> APP_IN_AAA(X1s, .(X, X2s), Xs)
   APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U4_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs)
   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> APP_IN_GAA(X1s, X2s, Zs)
   APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U4_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs)
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_AG(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys)

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag(x2)

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)

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

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

PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)

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

APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA

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

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

APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)

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

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


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

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

   PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   PERM_IN_AG(Xs, .(X, Ys)) -> APP_IN_AAA(X1s, .(X, X2s), Xs)
   APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U4_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs)
   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> APP_IN_GAA(X1s, X2s, Zs)
   APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U4_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs)
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_AG(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys)

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag(x2)

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)

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

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

PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)

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

APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA

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

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

APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)

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

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


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

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

(6)
Complex Obligation (AND)

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

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

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

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag(x2)

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)

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

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

APP_IN_GAA(x1, x2, x3)  =  APP_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:

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

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

APP_IN_GAA(x1, x2, x3)  =  APP_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:

   APP_IN_GAA(.(Xs)) -> APP_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:
*APP_IN_GAA(.(Xs)) -> APP_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:

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

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag(x2)

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)

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

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

APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA


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:

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

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

APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA


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:

   APP_IN_AAA -> APP_IN_AAA

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

(19) NonTerminationLoopProof (COMPLETE)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = APP_IN_AAA evaluates to  t =APP_IN_AAA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
* Matcher: [ ]
* Semiunifier: [ ]

--------------------------------------------------------------------------------
Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from APP_IN_AAA to APP_IN_AAA.




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

(20)
NO

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

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

   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys)
   PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag(x2)

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)

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

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

PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)

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

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


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

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

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

   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys)
   PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))

The TRS R consists of the following rules:

   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))

The argument filtering Pi contains the following mapping:
[]  =  []

.(x1, x2)  =  .(x2)

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa(x1)

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

PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)

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

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


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

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

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

   U1_AG(Ys, app_out_aaa(X1s)) -> U2_AG(Ys, app_in_gaa(X1s))
   U2_AG(Ys, app_out_gaa(X1s)) -> PERM_IN_AG(Ys)
   PERM_IN_AG(.(Ys)) -> U1_AG(Ys, app_in_aaa)

The TRS R consists of the following rules:

   app_in_gaa([]) -> app_out_gaa([])
   app_in_gaa(.(Xs)) -> U4_gaa(Xs, app_in_gaa(Xs))
   app_in_aaa -> app_out_aaa([])
   app_in_aaa -> U4_aaa(app_in_aaa)
   U4_gaa(Xs, app_out_gaa(Xs)) -> app_out_gaa(.(Xs))
   U4_aaa(app_out_aaa(Xs)) -> app_out_aaa(.(Xs))

The set Q consists of the following terms:

   app_in_gaa(x0)
   app_in_aaa
   U4_gaa(x0, x1)
   U4_aaa(x0)

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

(26) 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:
*U2_AG(Ys, app_out_gaa(X1s)) -> PERM_IN_AG(Ys)
The graph contains the following edges 1 >= 1


*PERM_IN_AG(.(Ys)) -> U1_AG(Ys, app_in_aaa)
The graph contains the following edges 1 > 1


*U1_AG(Ys, app_out_aaa(X1s)) -> U2_AG(Ys, app_in_gaa(X1s))
The graph contains the following edges 1 >= 1


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

(27)
YES

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

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

perm_in_2: (f,b)

app_in_3: (f,f,f) (b,f,f)

Transforming Prolog into the following Term Rewriting System:

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

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa

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

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





Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog



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

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

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa

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

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



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

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

   PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   PERM_IN_AG(Xs, .(X, Ys)) -> APP_IN_AAA(X1s, .(X, X2s), Xs)
   APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U4_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs)
   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> APP_IN_GAA(X1s, X2s, Zs)
   APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U4_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs)
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_AG(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys)

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa

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

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

PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)

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

APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA

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

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

APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)

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

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


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

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

   PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   PERM_IN_AG(Xs, .(X, Ys)) -> APP_IN_AAA(X1s, .(X, X2s), Xs)
   APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U4_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs)
   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> APP_IN_GAA(X1s, X2s, Zs)
   APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U4_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs)
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_AG(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys)

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa

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

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

PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)

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

APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA

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

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

APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)

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

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


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

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

(33)
Complex Obligation (AND)

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

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

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

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa

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

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

APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)


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

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

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

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

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

APP_IN_GAA(x1, x2, x3)  =  APP_IN_GAA(x1)


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

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

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

   APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs)

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

(39) 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:
*APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs)
The graph contains the following edges 1 > 1


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

(40)
YES

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

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

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

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa

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

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

APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA


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

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

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

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

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

APP_IN_AAA(x1, x2, x3)  =  APP_IN_AAA


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

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

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

   APP_IN_AAA -> APP_IN_AAA

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

(46) NonTerminationLoopProof (COMPLETE)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = APP_IN_AAA evaluates to  t =APP_IN_AAA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
* Matcher: [ ]
* Semiunifier: [ ]

--------------------------------------------------------------------------------
Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from APP_IN_AAA to APP_IN_AAA.




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

(47)
NO

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

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

   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys)
   PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))

The TRS R consists of the following rules:

   perm_in_ag([], []) -> perm_out_ag([], [])
   perm_in_ag(Xs, .(X, Ys)) -> U1_ag(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))
   U1_ag(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_ag(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U2_ag(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> U3_ag(Xs, X, Ys, perm_in_ag(Zs, Ys))
   U3_ag(Xs, X, Ys, perm_out_ag(Zs, Ys)) -> perm_out_ag(Xs, .(X, Ys))

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

[]  =  []

perm_out_ag(x1, x2)  =  perm_out_ag

.(x1, x2)  =  .(x2)

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

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa

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

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

PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)

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

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


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

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

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

   U1_AG(Xs, X, Ys, app_out_aaa(X1s, .(X, X2s), Xs)) -> U2_AG(Xs, X, Ys, app_in_gaa(X1s, X2s, Zs))
   U2_AG(Xs, X, Ys, app_out_gaa(X1s, X2s, Zs)) -> PERM_IN_AG(Zs, Ys)
   PERM_IN_AG(Xs, .(X, Ys)) -> U1_AG(Xs, X, Ys, app_in_aaa(X1s, .(X, X2s), Xs))

The TRS R consists of the following rules:

   app_in_gaa([], X, X) -> app_out_gaa([], X, X)
   app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U4_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs))
   app_in_aaa([], X, X) -> app_out_aaa([], X, X)
   app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U4_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs))
   U4_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs))
   U4_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs))

The argument filtering Pi contains the following mapping:
[]  =  []

.(x1, x2)  =  .(x2)

app_in_aaa(x1, x2, x3)  =  app_in_aaa

app_out_aaa(x1, x2, x3)  =  app_out_aaa(x1)

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

app_in_gaa(x1, x2, x3)  =  app_in_gaa(x1)

app_out_gaa(x1, x2, x3)  =  app_out_gaa

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

PERM_IN_AG(x1, x2)  =  PERM_IN_AG(x2)

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

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


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

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

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

   U1_AG(Ys, app_out_aaa(X1s)) -> U2_AG(Ys, app_in_gaa(X1s))
   U2_AG(Ys, app_out_gaa) -> PERM_IN_AG(Ys)
   PERM_IN_AG(.(Ys)) -> U1_AG(Ys, app_in_aaa)

The TRS R consists of the following rules:

   app_in_gaa([]) -> app_out_gaa
   app_in_gaa(.(Xs)) -> U4_gaa(app_in_gaa(Xs))
   app_in_aaa -> app_out_aaa([])
   app_in_aaa -> U4_aaa(app_in_aaa)
   U4_gaa(app_out_gaa) -> app_out_gaa
   U4_aaa(app_out_aaa(Xs)) -> app_out_aaa(.(Xs))

The set Q consists of the following terms:

   app_in_gaa(x0)
   app_in_aaa
   U4_gaa(x0)
   U4_aaa(x0)

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

(53) 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:
*U2_AG(Ys, app_out_gaa) -> PERM_IN_AG(Ys)
The graph contains the following edges 1 >= 1


*PERM_IN_AG(.(Ys)) -> U1_AG(Ys, app_in_aaa)
The graph contains the following edges 1 > 1


*U1_AG(Ys, app_out_aaa(X1s)) -> U2_AG(Ys, app_in_gaa(X1s))
The graph contains the following edges 1 >= 1


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

(54)
YES

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

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

{
    "root": 1,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(perm ([]) ([]))",
                null
            ],
            [
                "(perm Xs (. X Ys))",
                "(',' (app X1s (. X X2s) Xs) (',' (app X1s X2s Zs) (perm Zs Ys)))"
            ],
            [
                "(app ([]) X X)",
                null
            ],
            [
                "(app (. X Xs) Ys (. X Zs))",
                "(app Xs Ys Zs)"
            ]
        ]
    },
    "graph": {
        "nodes": {
            "44": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (app X13 (. T10 X14) T12) (',' (app X13 X14 X15) (perm X15 T11)))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [
                        "T10",
                        "T11"
                    ],
                    "free": [
                        "X13",
                        "X14",
                        "X15"
                    ],
                    "exprvars": []
                }
            },
            "46": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "28": {
                "goal": [
                    {
                        "clause": 0,
                        "scope": 1,
                        "term": "(perm T1 T2)"
                    },
                    {
                        "clause": 1,
                        "scope": 1,
                        "term": "(perm T1 T2)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "type": "Nodes",
            "212": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app X13 (. T10 X14) T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "213": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (app T17 T18 X15) (perm X15 T11))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T11"],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "259": {
                "goal": [
                    {
                        "clause": 2,
                        "scope": 3,
                        "term": "(app T17 T18 X15)"
                    },
                    {
                        "clause": 3,
                        "scope": 3,
                        "term": "(app T17 T18 X15)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "217": {
                "goal": [
                    {
                        "clause": 2,
                        "scope": 2,
                        "term": "(app X13 (. T10 X14) T12)"
                    },
                    {
                        "clause": 3,
                        "scope": 2,
                        "term": "(app X13 (. T10 X14) T12)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "239": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app T17 T18 X15)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "218": {
                "goal": [{
                    "clause": 2,
                    "scope": 2,
                    "term": "(app X13 (. T10 X14) T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "219": {
                "goal": [{
                    "clause": 3,
                    "scope": 2,
                    "term": "(app X13 (. T10 X14) T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "31": {
                "goal": [{
                    "clause": 0,
                    "scope": 1,
                    "term": "(perm T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "32": {
                "goal": [{
                    "clause": 1,
                    "scope": 1,
                    "term": "(perm T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "33": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "34": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "36": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "240": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(perm T49 T11)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T11"],
                    "free": [],
                    "exprvars": []
                }
            },
            "220": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "1": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(perm T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "221": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "222": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "300": {
                "goal": [{
                    "clause": 2,
                    "scope": 3,
                    "term": "(app T17 T18 X15)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "301": {
                "goal": [{
                    "clause": 3,
                    "scope": 3,
                    "term": "(app T17 T18 X15)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "225": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app X53 (. T39 X54) T42)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T39"],
                    "free": [
                        "X53",
                        "X54"
                    ],
                    "exprvars": []
                }
            },
            "302": {
                "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": []
                }
            },
            "303": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "305": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "307": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app T66 T67 X82)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X82"],
                    "exprvars": []
                }
            },
            "308": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            }
        },
        "edges": [
            {
                "from": 1,
                "to": 28,
                "label": "CASE"
            },
            {
                "from": 28,
                "to": 31,
                "label": "PARALLEL"
            },
            {
                "from": 28,
                "to": 32,
                "label": "PARALLEL"
            },
            {
                "from": 31,
                "to": 33,
                "label": "EVAL with clause\nperm([], []).\nand substitutionT1 -> [],\nT2 -> []"
            },
            {
                "from": 31,
                "to": 34,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 32,
                "to": 44,
                "label": "EVAL with clause\nperm(X10, .(X11, X12)) :- ','(app(X13, .(X11, X14), X10), ','(app(X13, X14, X15), perm(X15, X12))).\nand substitutionT1 -> T12,\nX10 -> T12,\nX11 -> T10,\nX12 -> T11,\nT2 -> .(T10, T11),\nT9 -> T12"
            },
            {
                "from": 32,
                "to": 46,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 33,
                "to": 36,
                "label": "SUCCESS"
            },
            {
                "from": 44,
                "to": 212,
                "label": "SPLIT 1"
            },
            {
                "from": 44,
                "to": 213,
                "label": "SPLIT 2\nreplacements:X13 -> T17,\nX14 -> T18"
            },
            {
                "from": 212,
                "to": 217,
                "label": "CASE"
            },
            {
                "from": 213,
                "to": 239,
                "label": "SPLIT 1"
            },
            {
                "from": 213,
                "to": 240,
                "label": "SPLIT 2\nreplacements:X15 -> T49"
            },
            {
                "from": 217,
                "to": 218,
                "label": "PARALLEL"
            },
            {
                "from": 217,
                "to": 219,
                "label": "PARALLEL"
            },
            {
                "from": 218,
                "to": 220,
                "label": "EVAL with clause\napp([], X32, X32).\nand substitutionX13 -> [],\nT10 -> T31,\nX14 -> T32,\nX32 -> .(T31, T32),\nX33 -> T32,\nT12 -> .(T31, T32)"
            },
            {
                "from": 218,
                "to": 221,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 219,
                "to": 225,
                "label": "EVAL with clause\napp(.(X48, X49), X50, .(X48, X51)) :- app(X49, X50, X51).\nand substitutionX48 -> T40,\nX49 -> X53,\nX13 -> .(T40, X53),\nT10 -> T39,\nX14 -> X54,\nX50 -> .(T39, X54),\nX52 -> T40,\nX51 -> T42,\nT12 -> .(T40, T42),\nT41 -> T42"
            },
            {
                "from": 219,
                "to": 226,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 220,
                "to": 222,
                "label": "SUCCESS"
            },
            {
                "from": 225,
                "to": 212,
                "label": "INSTANCE with matching:\nX13 -> X53\nT10 -> T39\nX14 -> X54\nT12 -> T42"
            },
            {
                "from": 239,
                "to": 259,
                "label": "CASE"
            },
            {
                "from": 240,
                "to": 1,
                "label": "INSTANCE with matching:\nT1 -> T49\nT2 -> T11"
            },
            {
                "from": 259,
                "to": 300,
                "label": "PARALLEL"
            },
            {
                "from": 259,
                "to": 301,
                "label": "PARALLEL"
            },
            {
                "from": 300,
                "to": 302,
                "label": "EVAL with clause\napp([], X67, X67).\nand substitutionT17 -> [],\nT18 -> T56,\nX67 -> T56,\nX15 -> T56"
            },
            {
                "from": 300,
                "to": 303,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 301,
                "to": 307,
                "label": "EVAL with clause\napp(.(X78, X79), X80, .(X78, X81)) :- app(X79, X80, X81).\nand substitutionX78 -> T63,\nX79 -> T66,\nT17 -> .(T63, T66),\nT18 -> T67,\nX80 -> T67,\nX81 -> X82,\nX15 -> .(T63, X82),\nT64 -> T66,\nT65 -> T67"
            },
            {
                "from": 301,
                "to": 308,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 302,
                "to": 305,
                "label": "SUCCESS"
            },
            {
                "from": 307,
                "to": 239,
                "label": "INSTANCE with matching:\nT17 -> T66\nT18 -> T67\nX15 -> X82"
            }
        ],
        "type": "Graph"
    }
}

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

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

   f1_in([]) -> f1_out1
   f1_in(.(T10, T11)) -> U1(f44_in(T10, T11), .(T10, T11))
   U1(f44_out1, .(T10, T11)) -> f1_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1
   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f44_in(T10, T11) -> U4(f212_in(T10), T10, T11)
   U4(f212_out1, T10, T11) -> U5(f213_in(T11), T10, T11)
   U5(f213_out1, T10, T11) -> f44_out1
   f213_in(T11) -> U6(f239_in, T11)
   U6(f239_out1, T11) -> U7(f1_in(T11), T11)
   U7(f1_out1, T11) -> f213_out1

Q is empty.

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

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

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

   F1_IN(.(T10, T11)) -> U1^1(f44_in(T10, T11), .(T10, T11))
   F1_IN(.(T10, T11)) -> F44_IN(T10, T11)
   F212_IN(T39) -> U2^1(f212_in(T39), T39)
   F212_IN(T39) -> F212_IN(T39)
   F239_IN -> U3^1(f239_in)
   F239_IN -> F239_IN
   F44_IN(T10, T11) -> U4^1(f212_in(T10), T10, T11)
   F44_IN(T10, T11) -> F212_IN(T10)
   U4^1(f212_out1, T10, T11) -> U5^1(f213_in(T11), T10, T11)
   U4^1(f212_out1, T10, T11) -> F213_IN(T11)
   F213_IN(T11) -> U6^1(f239_in, T11)
   F213_IN(T11) -> F239_IN
   U6^1(f239_out1, T11) -> U7^1(f1_in(T11), T11)
   U6^1(f239_out1, T11) -> F1_IN(T11)

The TRS R consists of the following rules:

   f1_in([]) -> f1_out1
   f1_in(.(T10, T11)) -> U1(f44_in(T10, T11), .(T10, T11))
   U1(f44_out1, .(T10, T11)) -> f1_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1
   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f44_in(T10, T11) -> U4(f212_in(T10), T10, T11)
   U4(f212_out1, T10, T11) -> U5(f213_in(T11), T10, T11)
   U5(f213_out1, T10, T11) -> f44_out1
   f213_in(T11) -> U6(f239_in, T11)
   U6(f239_out1, T11) -> U7(f1_in(T11), T11)
   U7(f1_out1, T11) -> f213_out1

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

(59) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 7 less nodes.
----------------------------------------

(60)
Complex Obligation (AND)

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

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

   F239_IN -> F239_IN

The TRS R consists of the following rules:

   f1_in([]) -> f1_out1
   f1_in(.(T10, T11)) -> U1(f44_in(T10, T11), .(T10, T11))
   U1(f44_out1, .(T10, T11)) -> f1_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1
   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f44_in(T10, T11) -> U4(f212_in(T10), T10, T11)
   U4(f212_out1, T10, T11) -> U5(f213_in(T11), T10, T11)
   U5(f213_out1, T10, T11) -> f44_out1
   f213_in(T11) -> U6(f239_in, T11)
   U6(f239_out1, T11) -> U7(f1_in(T11), T11)
   U7(f1_out1, T11) -> f213_out1

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

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

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

   F239_IN -> F239_IN

The TRS R consists of the following rules:

   f1_in([]) -> f1_out1
   f1_in(.(T10, T11)) -> U1(f44_in(T10, T11), .(T10, T11))
   U1(f44_out1, .(T10, T11)) -> f1_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1
   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f44_in(T10, T11) -> U4(f212_in(T10), T10, T11)
   U4(f212_out1, T10, T11) -> U5(f213_in(T11), T10, T11)
   U5(f213_out1, T10, T11) -> f44_out1
   f213_in(T11) -> U6(f239_in, T11)
   U6(f239_out1, T11) -> U7(f1_in(T11), T11)
   U7(f1_out1, T11) -> f213_out1

The set Q consists of the following terms:

   f1_in([])
   f1_in(.(x0, x1))
   U1(f44_out1, .(x0, x1))
   f212_in(x0)
   U2(f212_out1, x0)
   f239_in
   U3(f239_out1)
   f44_in(x0, x1)
   U4(f212_out1, x0, x1)
   U5(f213_out1, x0, x1)
   f213_in(x0)
   U6(f239_out1, x0)
   U7(f1_out1, x0)

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

(64) 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.
----------------------------------------

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

   F239_IN -> F239_IN

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

   f1_in([])
   f1_in(.(x0, x1))
   U1(f44_out1, .(x0, x1))
   f212_in(x0)
   U2(f212_out1, x0)
   f239_in
   U3(f239_out1)
   f44_in(x0, x1)
   U4(f212_out1, x0, x1)
   U5(f213_out1, x0, x1)
   f213_in(x0)
   U6(f239_out1, x0)
   U7(f1_out1, x0)

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

(66) 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].

   f1_in([])
   f1_in(.(x0, x1))
   U1(f44_out1, .(x0, x1))
   f212_in(x0)
   U2(f212_out1, x0)
   f239_in
   U3(f239_out1)
   f44_in(x0, x1)
   U4(f212_out1, x0, x1)
   U5(f213_out1, x0, x1)
   f213_in(x0)
   U6(f239_out1, x0)
   U7(f1_out1, x0)


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

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

   F239_IN -> F239_IN

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

(68) NonTerminationLoopProof (COMPLETE)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = F239_IN evaluates to  t =F239_IN

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
* Matcher: [ ]
* Semiunifier: [ ]

--------------------------------------------------------------------------------
Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from F239_IN to F239_IN.




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

(69)
NO

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

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

   F212_IN(T39) -> F212_IN(T39)

The TRS R consists of the following rules:

   f1_in([]) -> f1_out1
   f1_in(.(T10, T11)) -> U1(f44_in(T10, T11), .(T10, T11))
   U1(f44_out1, .(T10, T11)) -> f1_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1
   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f44_in(T10, T11) -> U4(f212_in(T10), T10, T11)
   U4(f212_out1, T10, T11) -> U5(f213_in(T11), T10, T11)
   U5(f213_out1, T10, T11) -> f44_out1
   f213_in(T11) -> U6(f239_in, T11)
   U6(f239_out1, T11) -> U7(f1_in(T11), T11)
   U7(f1_out1, T11) -> f213_out1

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

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

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

   F212_IN(T39) -> F212_IN(T39)

The TRS R consists of the following rules:

   f1_in([]) -> f1_out1
   f1_in(.(T10, T11)) -> U1(f44_in(T10, T11), .(T10, T11))
   U1(f44_out1, .(T10, T11)) -> f1_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1
   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f44_in(T10, T11) -> U4(f212_in(T10), T10, T11)
   U4(f212_out1, T10, T11) -> U5(f213_in(T11), T10, T11)
   U5(f213_out1, T10, T11) -> f44_out1
   f213_in(T11) -> U6(f239_in, T11)
   U6(f239_out1, T11) -> U7(f1_in(T11), T11)
   U7(f1_out1, T11) -> f213_out1

The set Q consists of the following terms:

   f1_in([])
   f1_in(.(x0, x1))
   U1(f44_out1, .(x0, x1))
   f212_in(x0)
   U2(f212_out1, x0)
   f239_in
   U3(f239_out1)
   f44_in(x0, x1)
   U4(f212_out1, x0, x1)
   U5(f213_out1, x0, x1)
   f213_in(x0)
   U6(f239_out1, x0)
   U7(f1_out1, x0)

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

(73) 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.
----------------------------------------

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

   F212_IN(T39) -> F212_IN(T39)

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

   f1_in([])
   f1_in(.(x0, x1))
   U1(f44_out1, .(x0, x1))
   f212_in(x0)
   U2(f212_out1, x0)
   f239_in
   U3(f239_out1)
   f44_in(x0, x1)
   U4(f212_out1, x0, x1)
   U5(f213_out1, x0, x1)
   f213_in(x0)
   U6(f239_out1, x0)
   U7(f1_out1, x0)

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

(75) 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].

   f1_in([])
   f1_in(.(x0, x1))
   U1(f44_out1, .(x0, x1))
   f212_in(x0)
   U2(f212_out1, x0)
   f239_in
   U3(f239_out1)
   f44_in(x0, x1)
   U4(f212_out1, x0, x1)
   U5(f213_out1, x0, x1)
   f213_in(x0)
   U6(f239_out1, x0)
   U7(f1_out1, x0)


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

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

   F212_IN(T39) -> F212_IN(T39)

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

(77) NonTerminationLoopProof (COMPLETE)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = F212_IN(T39) evaluates to  t =F212_IN(T39)

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
* Matcher: [ ]
* Semiunifier: [ ]

--------------------------------------------------------------------------------
Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from F212_IN(T39) to F212_IN(T39).




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

(78)
NO

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

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

   F1_IN(.(T10, T11)) -> F44_IN(T10, T11)
   F44_IN(T10, T11) -> U4^1(f212_in(T10), T10, T11)
   U4^1(f212_out1, T10, T11) -> F213_IN(T11)
   F213_IN(T11) -> U6^1(f239_in, T11)
   U6^1(f239_out1, T11) -> F1_IN(T11)

The TRS R consists of the following rules:

   f1_in([]) -> f1_out1
   f1_in(.(T10, T11)) -> U1(f44_in(T10, T11), .(T10, T11))
   U1(f44_out1, .(T10, T11)) -> f1_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1
   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f44_in(T10, T11) -> U4(f212_in(T10), T10, T11)
   U4(f212_out1, T10, T11) -> U5(f213_in(T11), T10, T11)
   U5(f213_out1, T10, T11) -> f44_out1
   f213_in(T11) -> U6(f239_in, T11)
   U6(f239_out1, T11) -> U7(f1_in(T11), T11)
   U7(f1_out1, T11) -> f213_out1

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

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

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

   F1_IN(.(T10, T11)) -> F44_IN(T10, T11)
   F44_IN(T10, T11) -> U4^1(f212_in(T10), T10, T11)
   U4^1(f212_out1, T10, T11) -> F213_IN(T11)
   F213_IN(T11) -> U6^1(f239_in, T11)
   U6^1(f239_out1, T11) -> F1_IN(T11)

The TRS R consists of the following rules:

   f1_in([]) -> f1_out1
   f1_in(.(T10, T11)) -> U1(f44_in(T10, T11), .(T10, T11))
   U1(f44_out1, .(T10, T11)) -> f1_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1
   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f44_in(T10, T11) -> U4(f212_in(T10), T10, T11)
   U4(f212_out1, T10, T11) -> U5(f213_in(T11), T10, T11)
   U5(f213_out1, T10, T11) -> f44_out1
   f213_in(T11) -> U6(f239_in, T11)
   U6(f239_out1, T11) -> U7(f1_in(T11), T11)
   U7(f1_out1, T11) -> f213_out1

The set Q consists of the following terms:

   f1_in([])
   f1_in(.(x0, x1))
   U1(f44_out1, .(x0, x1))
   f212_in(x0)
   U2(f212_out1, x0)
   f239_in
   U3(f239_out1)
   f44_in(x0, x1)
   U4(f212_out1, x0, x1)
   U5(f213_out1, x0, x1)
   f213_in(x0)
   U6(f239_out1, x0)
   U7(f1_out1, x0)

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

(82) 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.
----------------------------------------

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

   F1_IN(.(T10, T11)) -> F44_IN(T10, T11)
   F44_IN(T10, T11) -> U4^1(f212_in(T10), T10, T11)
   U4^1(f212_out1, T10, T11) -> F213_IN(T11)
   F213_IN(T11) -> U6^1(f239_in, T11)
   U6^1(f239_out1, T11) -> F1_IN(T11)

The TRS R consists of the following rules:

   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1

The set Q consists of the following terms:

   f1_in([])
   f1_in(.(x0, x1))
   U1(f44_out1, .(x0, x1))
   f212_in(x0)
   U2(f212_out1, x0)
   f239_in
   U3(f239_out1)
   f44_in(x0, x1)
   U4(f212_out1, x0, x1)
   U5(f213_out1, x0, x1)
   f213_in(x0)
   U6(f239_out1, x0)
   U7(f1_out1, x0)

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

(84) 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].

   f1_in([])
   f1_in(.(x0, x1))
   U1(f44_out1, .(x0, x1))
   f44_in(x0, x1)
   U4(f212_out1, x0, x1)
   U5(f213_out1, x0, x1)
   f213_in(x0)
   U6(f239_out1, x0)
   U7(f1_out1, x0)


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

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

   F1_IN(.(T10, T11)) -> F44_IN(T10, T11)
   F44_IN(T10, T11) -> U4^1(f212_in(T10), T10, T11)
   U4^1(f212_out1, T10, T11) -> F213_IN(T11)
   F213_IN(T11) -> U6^1(f239_in, T11)
   U6^1(f239_out1, T11) -> F1_IN(T11)

The TRS R consists of the following rules:

   f239_in -> f239_out1
   f239_in -> U3(f239_in)
   U3(f239_out1) -> f239_out1
   f212_in(T31) -> f212_out1
   f212_in(T39) -> U2(f212_in(T39), T39)
   U2(f212_out1, T39) -> f212_out1

The set Q consists of the following terms:

   f212_in(x0)
   U2(f212_out1, x0)
   f239_in
   U3(f239_out1)

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

(86) 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:
*F44_IN(T10, T11) -> U4^1(f212_in(T10), T10, T11)
The graph contains the following edges 1 >= 2, 2 >= 3


*U6^1(f239_out1, T11) -> F1_IN(T11)
The graph contains the following edges 2 >= 1


*U4^1(f212_out1, T10, T11) -> F213_IN(T11)
The graph contains the following edges 3 >= 1


*F1_IN(.(T10, T11)) -> F44_IN(T10, T11)
The graph contains the following edges 1 > 1, 1 > 2


*F213_IN(T11) -> U6^1(f239_in, T11)
The graph contains the following edges 1 >= 2


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

(87)
YES

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

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

{
    "root": 3,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(perm ([]) ([]))",
                null
            ],
            [
                "(perm Xs (. X Ys))",
                "(',' (app X1s (. X X2s) Xs) (',' (app X1s X2s Zs) (perm Zs Ys)))"
            ],
            [
                "(app ([]) X X)",
                null
            ],
            [
                "(app (. X Xs) Ys (. X Zs))",
                "(app Xs Ys Zs)"
            ]
        ]
    },
    "graph": {
        "nodes": {
            "24": {
                "goal": [{
                    "clause": 0,
                    "scope": 1,
                    "term": "(perm T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "25": {
                "goal": [{
                    "clause": 1,
                    "scope": 1,
                    "term": "(perm T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "47": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (app X13 (. T10 X14) T12) (',' (app X13 X14 X15) (perm X15 T11)))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [
                        "T10",
                        "T11"
                    ],
                    "free": [
                        "X13",
                        "X14",
                        "X15"
                    ],
                    "exprvars": []
                }
            },
            "48": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "29": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "290": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app T66 T67 X82)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X82"],
                    "exprvars": []
                }
            },
            "291": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "type": "Nodes",
            "199": {
                "goal": [
                    {
                        "clause": 2,
                        "scope": 2,
                        "term": "(app X13 (. T10 X14) T12)"
                    },
                    {
                        "clause": 3,
                        "scope": 2,
                        "term": "(app X13 (. T10 X14) T12)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "233": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app X53 (. T39 X54) T42)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T39"],
                    "free": [
                        "X53",
                        "X54"
                    ],
                    "exprvars": []
                }
            },
            "234": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "214": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "215": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "216": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "118": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app X13 (. T10 X14) T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "119": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (app T17 T18 X15) (perm X15 T11))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T11"],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "30": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "260": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app T17 T18 X15)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "261": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(perm T49 T11)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T11"],
                    "free": [],
                    "exprvars": []
                }
            },
            "262": {
                "goal": [
                    {
                        "clause": 2,
                        "scope": 3,
                        "term": "(app T17 T18 X15)"
                    },
                    {
                        "clause": 3,
                        "scope": 3,
                        "term": "(app T17 T18 X15)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "263": {
                "goal": [{
                    "clause": 2,
                    "scope": 3,
                    "term": "(app T17 T18 X15)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "264": {
                "goal": [{
                    "clause": 3,
                    "scope": 3,
                    "term": "(app T17 T18 X15)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X15"],
                    "exprvars": []
                }
            },
            "265": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "266": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "3": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(perm T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "267": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "7": {
                "goal": [
                    {
                        "clause": 0,
                        "scope": 1,
                        "term": "(perm T1 T2)"
                    },
                    {
                        "clause": 1,
                        "scope": 1,
                        "term": "(perm T1 T2)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "206": {
                "goal": [{
                    "clause": 2,
                    "scope": 2,
                    "term": "(app X13 (. T10 X14) T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "208": {
                "goal": [{
                    "clause": 3,
                    "scope": 2,
                    "term": "(app X13 (. T10 X14) T12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T10"],
                    "free": [
                        "X13",
                        "X14"
                    ],
                    "exprvars": []
                }
            },
            "43": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            }
        },
        "edges": [
            {
                "from": 3,
                "to": 7,
                "label": "CASE"
            },
            {
                "from": 7,
                "to": 24,
                "label": "PARALLEL"
            },
            {
                "from": 7,
                "to": 25,
                "label": "PARALLEL"
            },
            {
                "from": 24,
                "to": 29,
                "label": "EVAL with clause\nperm([], []).\nand substitutionT1 -> [],\nT2 -> []"
            },
            {
                "from": 24,
                "to": 30,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 25,
                "to": 47,
                "label": "EVAL with clause\nperm(X10, .(X11, X12)) :- ','(app(X13, .(X11, X14), X10), ','(app(X13, X14, X15), perm(X15, X12))).\nand substitutionT1 -> T12,\nX10 -> T12,\nX11 -> T10,\nX12 -> T11,\nT2 -> .(T10, T11),\nT9 -> T12"
            },
            {
                "from": 25,
                "to": 48,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 29,
                "to": 43,
                "label": "SUCCESS"
            },
            {
                "from": 47,
                "to": 118,
                "label": "SPLIT 1"
            },
            {
                "from": 47,
                "to": 119,
                "label": "SPLIT 2\nreplacements:X13 -> T17,\nX14 -> T18"
            },
            {
                "from": 118,
                "to": 199,
                "label": "CASE"
            },
            {
                "from": 119,
                "to": 260,
                "label": "SPLIT 1"
            },
            {
                "from": 119,
                "to": 261,
                "label": "SPLIT 2\nreplacements:X15 -> T49"
            },
            {
                "from": 199,
                "to": 206,
                "label": "PARALLEL"
            },
            {
                "from": 199,
                "to": 208,
                "label": "PARALLEL"
            },
            {
                "from": 206,
                "to": 214,
                "label": "EVAL with clause\napp([], X32, X32).\nand substitutionX13 -> [],\nT10 -> T31,\nX14 -> T32,\nX32 -> .(T31, T32),\nX33 -> T32,\nT12 -> .(T31, T32)"
            },
            {
                "from": 206,
                "to": 215,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 208,
                "to": 233,
                "label": "EVAL with clause\napp(.(X48, X49), X50, .(X48, X51)) :- app(X49, X50, X51).\nand substitutionX48 -> T40,\nX49 -> X53,\nX13 -> .(T40, X53),\nT10 -> T39,\nX14 -> X54,\nX50 -> .(T39, X54),\nX52 -> T40,\nX51 -> T42,\nT12 -> .(T40, T42),\nT41 -> T42"
            },
            {
                "from": 208,
                "to": 234,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 214,
                "to": 216,
                "label": "SUCCESS"
            },
            {
                "from": 233,
                "to": 118,
                "label": "INSTANCE with matching:\nX13 -> X53\nT10 -> T39\nX14 -> X54\nT12 -> T42"
            },
            {
                "from": 260,
                "to": 262,
                "label": "CASE"
            },
            {
                "from": 261,
                "to": 3,
                "label": "INSTANCE with matching:\nT1 -> T49\nT2 -> T11"
            },
            {
                "from": 262,
                "to": 263,
                "label": "PARALLEL"
            },
            {
                "from": 262,
                "to": 264,
                "label": "PARALLEL"
            },
            {
                "from": 263,
                "to": 265,
                "label": "EVAL with clause\napp([], X67, X67).\nand substitutionT17 -> [],\nT18 -> T56,\nX67 -> T56,\nX15 -> T56"
            },
            {
                "from": 263,
                "to": 266,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 264,
                "to": 290,
                "label": "EVAL with clause\napp(.(X78, X79), X80, .(X78, X81)) :- app(X79, X80, X81).\nand substitutionX78 -> T63,\nX79 -> T66,\nT17 -> .(T63, T66),\nT18 -> T67,\nX80 -> T67,\nX81 -> X82,\nX15 -> .(T63, X82),\nT64 -> T66,\nT65 -> T67"
            },
            {
                "from": 264,
                "to": 291,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 265,
                "to": 267,
                "label": "SUCCESS"
            },
            {
                "from": 290,
                "to": 260,
                "label": "INSTANCE with matching:\nT17 -> T66\nT18 -> T67\nX15 -> X82"
            }
        ],
        "type": "Graph"
    }
}

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

(89)
Complex Obligation (AND)

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

(90)
Obligation:
Rules:
f262_in -> f263_in :|: TRUE
f262_in -> f264_in :|: TRUE
f264_out -> f262_out :|: TRUE
f263_out -> f262_out :|: TRUE
f260_in -> f262_in :|: TRUE
f262_out -> f260_out :|: TRUE
f264_in -> f290_in :|: TRUE
f291_out -> f264_out :|: TRUE
f290_out -> f264_out :|: TRUE
f264_in -> f291_in :|: TRUE
f260_out -> f290_out :|: TRUE
f290_in -> f260_in :|: TRUE
f3_in(T2) -> f7_in(T2) :|: TRUE
f7_out(x) -> f3_out(x) :|: TRUE
f7_in(x1) -> f24_in(x1) :|: TRUE
f24_out(x2) -> f7_out(x2) :|: TRUE
f25_out(x3) -> f7_out(x3) :|: TRUE
f7_in(x4) -> f25_in(x4) :|: TRUE
f48_out -> f25_out(x5) :|: TRUE
f47_out(T10, T11) -> f25_out(.(T10, T11)) :|: TRUE
f25_in(.(x6, x7)) -> f47_in(x6, x7) :|: TRUE
f25_in(x8) -> f48_in :|: TRUE
f118_out(x9) -> f119_in(x10) :|: TRUE
f119_out(x11) -> f47_out(x12, x11) :|: TRUE
f47_in(x13, x14) -> f118_in(x13) :|: TRUE
f260_out -> f261_in(x15) :|: TRUE
f119_in(x16) -> f260_in :|: TRUE
f261_out(x17) -> f119_out(x17) :|: TRUE
Start term: f3_in(T2)

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

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

Simplified to the following IRSwTs:


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

(92)
TRUE

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

(93)
Obligation:
Rules:
f199_in(T10) -> f208_in(T10) :|: TRUE
f199_in(x) -> f206_in(x) :|: TRUE
f208_out(x1) -> f199_out(x1) :|: TRUE
f206_out(x2) -> f199_out(x2) :|: TRUE
f118_out(T39) -> f233_out(T39) :|: TRUE
f233_in(x3) -> f118_in(x3) :|: TRUE
f199_out(x4) -> f118_out(x4) :|: TRUE
f118_in(x5) -> f199_in(x5) :|: TRUE
f208_in(x6) -> f234_in :|: TRUE
f234_out -> f208_out(x7) :|: TRUE
f233_out(x8) -> f208_out(x8) :|: TRUE
f208_in(x9) -> f233_in(x9) :|: TRUE
f3_in(T2) -> f7_in(T2) :|: TRUE
f7_out(x10) -> f3_out(x10) :|: TRUE
f7_in(x11) -> f24_in(x11) :|: TRUE
f24_out(x12) -> f7_out(x12) :|: TRUE
f25_out(x13) -> f7_out(x13) :|: TRUE
f7_in(x14) -> f25_in(x14) :|: TRUE
f48_out -> f25_out(x15) :|: TRUE
f47_out(x16, x17) -> f25_out(.(x16, x17)) :|: TRUE
f25_in(.(x18, x19)) -> f47_in(x18, x19) :|: TRUE
f25_in(x20) -> f48_in :|: TRUE
f118_out(x21) -> f119_in(x22) :|: TRUE
f119_out(x23) -> f47_out(x24, x23) :|: TRUE
f47_in(x25, x26) -> f118_in(x25) :|: TRUE
Start term: f3_in(T2)

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

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

Simplified to the following IRSwTs:

intTRSProblem:
f199_in(T10) -> f208_in(T10) :|: TRUE
f233_in(x3) -> f118_in(x3) :|: TRUE
f118_in(x5) -> f199_in(x5) :|: TRUE
f208_in(x9) -> f233_in(x9) :|: TRUE


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

(95)
Obligation:
Rules:
f199_in(T10) -> f208_in(T10) :|: TRUE
f233_in(x3) -> f118_in(x3) :|: TRUE
f118_in(x5) -> f199_in(x5) :|: TRUE
f208_in(x9) -> f233_in(x9) :|: TRUE

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

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

(97)
Obligation:
Rules:
f233_in(x3:0) -> f233_in(x3:0) :|: TRUE

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

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

(99)
Obligation:
Rules:
f233_in(x3:0) -> f233_in(x3:0) :|: TRUE

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

(100) IRSwTTerminationDigraphProof (EQUIVALENT)
Constructed termination digraph!
Nodes:
(1) f233_in(x3:0) -> f233_in(x3:0) :|: TRUE

Arcs:
(1) -> (1)

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

(101)
Obligation:

Termination digraph:
Nodes:
(1) f233_in(x3:0) -> f233_in(x3:0) :|: TRUE

Arcs:
(1) -> (1)

This digraph is fully evaluated!

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

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

(103)
Obligation:
Rules:
f233_in(x3:0) -> f233_in(x3:0) :|: TRUE

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

(104) IntTRSPeriodicNontermProof (COMPLETE)
Normalized system to the following form:
f(pc, x3:0) -> f(1, x3:0) :|: pc = 1 && TRUE
Witness term starting non-terminating reduction: f(1, -8)
----------------------------------------

(105)
NO

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

(106)
Obligation:
Rules:
f261_in(T11) -> f3_in(T11) :|: TRUE
f3_out(x) -> f261_out(x) :|: TRUE
f3_in(T2) -> f7_in(T2) :|: TRUE
f7_out(x1) -> f3_out(x1) :|: TRUE
f7_in(x2) -> f24_in(x2) :|: TRUE
f24_out(x3) -> f7_out(x3) :|: TRUE
f25_out(x4) -> f7_out(x4) :|: TRUE
f7_in(x5) -> f25_in(x5) :|: TRUE
f260_in -> f262_in :|: TRUE
f262_out -> f260_out :|: TRUE
f118_out(T39) -> f233_out(T39) :|: TRUE
f233_in(x6) -> f118_in(x6) :|: TRUE
f118_out(x7) -> f119_in(x8) :|: TRUE
f119_out(x9) -> f47_out(x10, x9) :|: TRUE
f47_in(x11, x12) -> f118_in(x11) :|: TRUE
f214_in -> f214_out :|: TRUE
f48_out -> f25_out(x13) :|: TRUE
f47_out(x14, x15) -> f25_out(.(x14, x15)) :|: TRUE
f25_in(.(x16, x17)) -> f47_in(x16, x17) :|: TRUE
f25_in(x18) -> f48_in :|: TRUE
f214_out -> f206_out(T31) :|: TRUE
f215_out -> f206_out(T10) :|: TRUE
f206_in(x19) -> f214_in :|: TRUE
f206_in(x20) -> f215_in :|: TRUE
f264_in -> f290_in :|: TRUE
f291_out -> f264_out :|: TRUE
f290_out -> f264_out :|: TRUE
f264_in -> f291_in :|: TRUE
f266_out -> f263_out :|: TRUE
f263_in -> f265_in :|: TRUE
f265_out -> f263_out :|: TRUE
f263_in -> f266_in :|: TRUE
f199_in(x21) -> f208_in(x21) :|: TRUE
f199_in(x22) -> f206_in(x22) :|: TRUE
f208_out(x23) -> f199_out(x23) :|: TRUE
f206_out(x24) -> f199_out(x24) :|: TRUE
f262_in -> f263_in :|: TRUE
f262_in -> f264_in :|: TRUE
f264_out -> f262_out :|: TRUE
f263_out -> f262_out :|: TRUE
f265_in -> f265_out :|: TRUE
f260_out -> f261_in(x25) :|: TRUE
f119_in(x26) -> f260_in :|: TRUE
f261_out(x27) -> f119_out(x27) :|: TRUE
f199_out(x28) -> f118_out(x28) :|: TRUE
f118_in(x29) -> f199_in(x29) :|: TRUE
f208_in(x30) -> f234_in :|: TRUE
f234_out -> f208_out(x31) :|: TRUE
f233_out(x32) -> f208_out(x32) :|: TRUE
f208_in(x33) -> f233_in(x33) :|: TRUE
f260_out -> f290_out :|: TRUE
f290_in -> f260_in :|: TRUE
Start term: f3_in(T2)

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

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

Simplified to the following IRSwTs:

intTRSProblem:
f261_in(T11) -> f3_in(T11) :|: TRUE
f3_in(T2) -> f7_in(T2) :|: TRUE
f7_in(x5) -> f25_in(x5) :|: TRUE
f260_in -> f262_in :|: TRUE
f262_out -> f260_out :|: TRUE
f118_out(T39) -> f233_out(T39) :|: TRUE
f233_in(x6) -> f118_in(x6) :|: TRUE
f118_out(x7) -> f119_in(x8) :|: TRUE
f47_in(x11, x12) -> f118_in(x11) :|: TRUE
f214_in -> f214_out :|: TRUE
f25_in(.(x16, x17)) -> f47_in(x16, x17) :|: TRUE
f214_out -> f206_out(T31) :|: TRUE
f206_in(x19) -> f214_in :|: TRUE
f264_in -> f290_in :|: TRUE
f290_out -> f264_out :|: TRUE
f263_in -> f265_in :|: TRUE
f265_out -> f263_out :|: TRUE
f199_in(x21) -> f208_in(x21) :|: TRUE
f199_in(x22) -> f206_in(x22) :|: TRUE
f208_out(x23) -> f199_out(x23) :|: TRUE
f206_out(x24) -> f199_out(x24) :|: TRUE
f262_in -> f263_in :|: TRUE
f262_in -> f264_in :|: TRUE
f264_out -> f262_out :|: TRUE
f263_out -> f262_out :|: TRUE
f265_in -> f265_out :|: TRUE
f260_out -> f261_in(x25) :|: TRUE
f119_in(x26) -> f260_in :|: TRUE
f199_out(x28) -> f118_out(x28) :|: TRUE
f118_in(x29) -> f199_in(x29) :|: TRUE
f233_out(x32) -> f208_out(x32) :|: TRUE
f208_in(x33) -> f233_in(x33) :|: TRUE
f260_out -> f290_out :|: TRUE
f290_in -> f260_in :|: TRUE


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

(108)
Obligation:
Rules:
f261_in(T11) -> f3_in(T11) :|: TRUE
f3_in(T2) -> f7_in(T2) :|: TRUE
f7_in(x5) -> f25_in(x5) :|: TRUE
f260_in -> f262_in :|: TRUE
f262_out -> f260_out :|: TRUE
f118_out(T39) -> f233_out(T39) :|: TRUE
f233_in(x6) -> f118_in(x6) :|: TRUE
f118_out(x7) -> f119_in(x8) :|: TRUE
f47_in(x11, x12) -> f118_in(x11) :|: TRUE
f214_in -> f214_out :|: TRUE
f25_in(.(x16, x17)) -> f47_in(x16, x17) :|: TRUE
f214_out -> f206_out(T31) :|: TRUE
f206_in(x19) -> f214_in :|: TRUE
f264_in -> f290_in :|: TRUE
f290_out -> f264_out :|: TRUE
f263_in -> f265_in :|: TRUE
f265_out -> f263_out :|: TRUE
f199_in(x21) -> f208_in(x21) :|: TRUE
f199_in(x22) -> f206_in(x22) :|: TRUE
f208_out(x23) -> f199_out(x23) :|: TRUE
f206_out(x24) -> f199_out(x24) :|: TRUE
f262_in -> f263_in :|: TRUE
f262_in -> f264_in :|: TRUE
f264_out -> f262_out :|: TRUE
f263_out -> f262_out :|: TRUE
f265_in -> f265_out :|: TRUE
f260_out -> f261_in(x25) :|: TRUE
f119_in(x26) -> f260_in :|: TRUE
f199_out(x28) -> f118_out(x28) :|: TRUE
f118_in(x29) -> f199_in(x29) :|: TRUE
f233_out(x32) -> f208_out(x32) :|: TRUE
f208_in(x33) -> f233_in(x33) :|: TRUE
f260_out -> f290_out :|: TRUE
f290_in -> f260_in :|: TRUE

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

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

(110)
Obligation:
Rules:
f260_in -> f262_out :|: TRUE
f118_out(T39:0) -> f118_out(T39:0) :|: TRUE
f262_out -> f262_out :|: TRUE
f199_in(x21:0) -> f199_in(x21:0) :|: TRUE
f118_out(x7:0) -> f260_in :|: TRUE
f262_out -> f199_in(x16:0) :|: TRUE
f260_in -> f260_in :|: TRUE
f199_in(x22:0) -> f118_out(T31:0) :|: TRUE

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

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

(112)
Obligation:
Rules:
f260_in -> f262_out :|: TRUE
f118_out(T39:0) -> f118_out(T39:0) :|: TRUE
f262_out -> f262_out :|: TRUE
f199_in(x21:0) -> f199_in(x21:0) :|: TRUE
f118_out(x7:0) -> f260_in :|: TRUE
f262_out -> f199_in(x16:0) :|: TRUE
f260_in -> f260_in :|: TRUE
f199_in(x22:0) -> f118_out(T31:0) :|: TRUE

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

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

{
    "root": 2,
    "program": {
        "directives": [],
        "clauses": [
            [
                "(perm ([]) ([]))",
                null
            ],
            [
                "(perm Xs (. X Ys))",
                "(',' (app X1s (. X X2s) Xs) (',' (app X1s X2s Zs) (perm Zs Ys)))"
            ],
            [
                "(app ([]) X X)",
                null
            ],
            [
                "(app (. X Xs) Ys (. X Zs))",
                "(app Xs Ys Zs)"
            ]
        ]
    },
    "graph": {
        "nodes": {
            "45": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [
                        "T8",
                        "T9"
                    ],
                    "free": [
                        "X10",
                        "X11",
                        "X12"
                    ],
                    "exprvars": []
                }
            },
            "26": {
                "goal": [
                    {
                        "clause": -1,
                        "scope": -1,
                        "term": "(true)"
                    },
                    {
                        "clause": 1,
                        "scope": 1,
                        "term": "(perm T1 ([]))"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "27": {
                "goal": [{
                    "clause": 1,
                    "scope": 1,
                    "term": "(perm T1 T2)"
                }],
                "kb": {
                    "nonunifying": [[
                        "(perm T1 T2)",
                        "(perm ([]) ([]))"
                    ]],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "49": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "292": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app X53 (. T36 X54) T39)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T36"],
                    "free": [
                        "X53",
                        "X54"
                    ],
                    "exprvars": []
                }
            },
            "type": "Nodes",
            "293": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (app (. T47 T45) T46 X12) (perm X12 T9))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T9"],
                    "free": ["X12"],
                    "exprvars": []
                }
            },
            "294": {
                "goal": [
                    {
                        "clause": 2,
                        "scope": 4,
                        "term": "(app X53 (. T36 X54) T39)"
                    },
                    {
                        "clause": 3,
                        "scope": 4,
                        "term": "(app X53 (. T36 X54) T39)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T36"],
                    "free": [
                        "X53",
                        "X54"
                    ],
                    "exprvars": []
                }
            },
            "295": {
                "goal": [{
                    "clause": 2,
                    "scope": 4,
                    "term": "(app X53 (. T36 X54) T39)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T36"],
                    "free": [
                        "X53",
                        "X54"
                    ],
                    "exprvars": []
                }
            },
            "230": {
                "goal": [{
                    "clause": 2,
                    "scope": 3,
                    "term": "(app ([]) T21 X12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X12"],
                    "exprvars": []
                }
            },
            "296": {
                "goal": [{
                    "clause": 3,
                    "scope": 4,
                    "term": "(app X53 (. T36 X54) T39)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T36"],
                    "free": [
                        "X53",
                        "X54"
                    ],
                    "exprvars": []
                }
            },
            "231": {
                "goal": [{
                    "clause": 3,
                    "scope": 3,
                    "term": "(app ([]) T21 X12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X12"],
                    "exprvars": []
                }
            },
            "297": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "232": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "298": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "299": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "310": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(perm T76 T9)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T9"],
                    "free": [],
                    "exprvars": []
                }
            },
            "278": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (app X53 (. T36 X54) T39) (',' (app (. T40 X53) X54 X12) (perm X12 T9)))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [
                        "T9",
                        "T36"
                    ],
                    "free": [
                        "X12",
                        "X53",
                        "X54"
                    ],
                    "exprvars": []
                }
            },
            "311": {
                "goal": [
                    {
                        "clause": 2,
                        "scope": 5,
                        "term": "(app (. T47 T45) T46 X12)"
                    },
                    {
                        "clause": 3,
                        "scope": 5,
                        "term": "(app (. T47 T45) T46 X12)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X12"],
                    "exprvars": []
                }
            },
            "312": {
                "goal": [{
                    "clause": 3,
                    "scope": 5,
                    "term": "(app (. T47 T45) T46 X12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X12"],
                    "exprvars": []
                }
            },
            "313": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app T90 T91 X119)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X119"],
                    "exprvars": []
                }
            },
            "237": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "314": {
                "goal": [
                    {
                        "clause": 2,
                        "scope": 6,
                        "term": "(app T90 T91 X119)"
                    },
                    {
                        "clause": 3,
                        "scope": 6,
                        "term": "(app T90 T91 X119)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X119"],
                    "exprvars": []
                }
            },
            "238": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "315": {
                "goal": [{
                    "clause": 2,
                    "scope": 6,
                    "term": "(app T90 T91 X119)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X119"],
                    "exprvars": []
                }
            },
            "316": {
                "goal": [{
                    "clause": 3,
                    "scope": 6,
                    "term": "(app T90 T91 X119)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X119"],
                    "exprvars": []
                }
            },
            "53": {
                "goal": [
                    {
                        "clause": 2,
                        "scope": 2,
                        "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))"
                    },
                    {
                        "clause": 3,
                        "scope": 2,
                        "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [
                        "T8",
                        "T9"
                    ],
                    "free": [
                        "X10",
                        "X11",
                        "X12"
                    ],
                    "exprvars": []
                }
            },
            "56": {
                "goal": [{
                    "clause": 2,
                    "scope": 2,
                    "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [
                        "T8",
                        "T9"
                    ],
                    "free": [
                        "X10",
                        "X11",
                        "X12"
                    ],
                    "exprvars": []
                }
            },
            "35": {
                "goal": [{
                    "clause": 1,
                    "scope": 1,
                    "term": "(perm T1 ([]))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "57": {
                "goal": [{
                    "clause": 3,
                    "scope": 2,
                    "term": "(',' (app X10 (. T8 X11) T10) (',' (app X10 X11 X12) (perm X12 T9)))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [
                        "T8",
                        "T9"
                    ],
                    "free": [
                        "X10",
                        "X11",
                        "X12"
                    ],
                    "exprvars": []
                }
            },
            "281": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "340": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app T108 T109 X141)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X141"],
                    "exprvars": []
                }
            },
            "341": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "2": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(perm T1 T2)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "223": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(',' (app ([]) T21 X12) (perm X12 T9))"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T9"],
                    "free": ["X12"],
                    "exprvars": []
                }
            },
            "224": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "6": {
                "goal": [
                    {
                        "clause": 0,
                        "scope": 1,
                        "term": "(perm T1 T2)"
                    },
                    {
                        "clause": 1,
                        "scope": 1,
                        "term": "(perm T1 T2)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T2"],
                    "free": [],
                    "exprvars": []
                }
            },
            "227": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app ([]) T21 X12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X12"],
                    "exprvars": []
                }
            },
            "304": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app X92 (. T68 X93) T71)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T68"],
                    "free": [
                        "X92",
                        "X93"
                    ],
                    "exprvars": []
                }
            },
            "228": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(perm T23 T9)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": ["T9"],
                    "free": [],
                    "exprvars": []
                }
            },
            "327": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(true)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "229": {
                "goal": [
                    {
                        "clause": 2,
                        "scope": 3,
                        "term": "(app ([]) T21 X12)"
                    },
                    {
                        "clause": 3,
                        "scope": 3,
                        "term": "(app ([]) T21 X12)"
                    }
                ],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X12"],
                    "exprvars": []
                }
            },
            "306": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "328": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "329": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "40": {
                "goal": [],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": [],
                    "exprvars": []
                }
            },
            "309": {
                "goal": [{
                    "clause": -1,
                    "scope": -1,
                    "term": "(app (. T47 T45) T46 X12)"
                }],
                "kb": {
                    "nonunifying": [],
                    "intvars": {},
                    "arithmetic": {
                        "type": "PlainIntegerRelationState",
                        "relations": []
                    },
                    "ground": [],
                    "free": ["X12"],
                    "exprvars": []
                }
            }
        },
        "edges": [
            {
                "from": 2,
                "to": 6,
                "label": "CASE"
            },
            {
                "from": 6,
                "to": 26,
                "label": "EVAL with clause\nperm([], []).\nand substitutionT1 -> [],\nT2 -> []"
            },
            {
                "from": 6,
                "to": 27,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 26,
                "to": 35,
                "label": "SUCCESS"
            },
            {
                "from": 27,
                "to": 45,
                "label": "EVAL with clause\nperm(X7, .(X8, X9)) :- ','(app(X10, .(X8, X11), X7), ','(app(X10, X11, X12), perm(X12, X9))).\nand substitutionT1 -> T10,\nX7 -> T10,\nX8 -> T8,\nX9 -> T9,\nT2 -> .(T8, T9),\nT7 -> T10"
            },
            {
                "from": 27,
                "to": 49,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 35,
                "to": 40,
                "label": "BACKTRACK\nfor clause: perm(Xs, .(X, Ys)) :- ','(app(X1s, .(X, X2s), Xs), ','(app(X1s, X2s, Zs), perm(Zs, Ys)))because of non-unification"
            },
            {
                "from": 45,
                "to": 53,
                "label": "CASE"
            },
            {
                "from": 53,
                "to": 56,
                "label": "PARALLEL"
            },
            {
                "from": 53,
                "to": 57,
                "label": "PARALLEL"
            },
            {
                "from": 56,
                "to": 223,
                "label": "EVAL with clause\napp([], X21, X21).\nand substitutionX10 -> [],\nT8 -> T19,\nX11 -> T21,\nX21 -> .(T19, T21),\nX22 -> T21,\nT10 -> .(T19, T21),\nT20 -> T21"
            },
            {
                "from": 56,
                "to": 224,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 57,
                "to": 278,
                "label": "EVAL with clause\napp(.(X48, X49), X50, .(X48, X51)) :- app(X49, X50, X51).\nand substitutionX48 -> T40,\nX49 -> X53,\nX10 -> .(T40, X53),\nT8 -> T36,\nX11 -> X54,\nX50 -> .(T36, X54),\nX52 -> T40,\nX51 -> T39,\nT10 -> .(T40, T39),\nT38 -> T39,\nT37 -> T40"
            },
            {
                "from": 57,
                "to": 281,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 223,
                "to": 227,
                "label": "SPLIT 1"
            },
            {
                "from": 223,
                "to": 228,
                "label": "SPLIT 2\nreplacements:X12 -> T23"
            },
            {
                "from": 227,
                "to": 229,
                "label": "CASE"
            },
            {
                "from": 228,
                "to": 2,
                "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T9"
            },
            {
                "from": 229,
                "to": 230,
                "label": "PARALLEL"
            },
            {
                "from": 229,
                "to": 231,
                "label": "PARALLEL"
            },
            {
                "from": 230,
                "to": 232,
                "label": "ONLY EVAL with clause\napp([], X29, X29).\nand substitutionT21 -> T29,\nX29 -> T29,\nX12 -> T29"
            },
            {
                "from": 231,
                "to": 238,
                "label": "BACKTRACK\nfor clause: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs)because of non-unification"
            },
            {
                "from": 232,
                "to": 237,
                "label": "SUCCESS"
            },
            {
                "from": 278,
                "to": 292,
                "label": "SPLIT 1"
            },
            {
                "from": 278,
                "to": 293,
                "label": "SPLIT 2\nreplacements:X53 -> T45,\nX54 -> T46,\nT40 -> T47"
            },
            {
                "from": 292,
                "to": 294,
                "label": "CASE"
            },
            {
                "from": 293,
                "to": 309,
                "label": "SPLIT 1"
            },
            {
                "from": 293,
                "to": 310,
                "label": "SPLIT 2\nreplacements:X12 -> T76"
            },
            {
                "from": 294,
                "to": 295,
                "label": "PARALLEL"
            },
            {
                "from": 294,
                "to": 296,
                "label": "PARALLEL"
            },
            {
                "from": 295,
                "to": 297,
                "label": "EVAL with clause\napp([], X71, X71).\nand substitutionX53 -> [],\nT36 -> T60,\nX54 -> T61,\nX71 -> .(T60, T61),\nX72 -> T61,\nT39 -> .(T60, T61)"
            },
            {
                "from": 295,
                "to": 298,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 296,
                "to": 304,
                "label": "EVAL with clause\napp(.(X87, X88), X89, .(X87, X90)) :- app(X88, X89, X90).\nand substitutionX87 -> T69,\nX88 -> X92,\nX53 -> .(T69, X92),\nT36 -> T68,\nX54 -> X93,\nX89 -> .(T68, X93),\nX91 -> T69,\nX90 -> T71,\nT39 -> .(T69, T71),\nT70 -> T71"
            },
            {
                "from": 296,
                "to": 306,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 297,
                "to": 299,
                "label": "SUCCESS"
            },
            {
                "from": 304,
                "to": 292,
                "label": "INSTANCE with matching:\nX53 -> X92\nT36 -> T68\nX54 -> X93\nT39 -> T71"
            },
            {
                "from": 309,
                "to": 311,
                "label": "CASE"
            },
            {
                "from": 310,
                "to": 2,
                "label": "INSTANCE with matching:\nT1 -> T76\nT2 -> T9"
            },
            {
                "from": 311,
                "to": 312,
                "label": "BACKTRACK\nfor clause: app([], X, X)because of non-unification"
            },
            {
                "from": 312,
                "to": 313,
                "label": "ONLY EVAL with clause\napp(.(X115, X116), X117, .(X115, X118)) :- app(X116, X117, X118).\nand substitutionT47 -> T87,\nX115 -> T87,\nT45 -> T90,\nX116 -> T90,\nT46 -> T91,\nX117 -> T91,\nX118 -> X119,\nX12 -> .(T87, X119),\nT88 -> T90,\nT89 -> T91"
            },
            {
                "from": 313,
                "to": 314,
                "label": "CASE"
            },
            {
                "from": 314,
                "to": 315,
                "label": "PARALLEL"
            },
            {
                "from": 314,
                "to": 316,
                "label": "PARALLEL"
            },
            {
                "from": 315,
                "to": 327,
                "label": "EVAL with clause\napp([], X126, X126).\nand substitutionT90 -> [],\nT91 -> T98,\nX126 -> T98,\nX119 -> T98"
            },
            {
                "from": 315,
                "to": 328,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 316,
                "to": 340,
                "label": "EVAL with clause\napp(.(X137, X138), X139, .(X137, X140)) :- app(X138, X139, X140).\nand substitutionX137 -> T105,\nX138 -> T108,\nT90 -> .(T105, T108),\nT91 -> T109,\nX139 -> T109,\nX140 -> X141,\nX119 -> .(T105, X141),\nT106 -> T108,\nT107 -> T109"
            },
            {
                "from": 316,
                "to": 341,
                "label": "EVAL-BACKTRACK"
            },
            {
                "from": 327,
                "to": 329,
                "label": "SUCCESS"
            },
            {
                "from": 340,
                "to": 313,
                "label": "INSTANCE with matching:\nT90 -> T108\nT91 -> T109\nX119 -> X141"
            }
        ],
        "type": "Graph"
    }
}

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

(114)
Obligation:
Triples:

appC(.(X1, X2), X3, X4, .(X1, X5)) :- appC(X2, X3, X4, X5).
appE(.(X1, X2), X3, .(X1, X4)) :- appE(X2, X3, X4).
permA(.(X1, X2), .(X1, X3)) :- ','(appcB(X2, X4), permA(X4, X3)).
permA(.(X1, X2), .(X3, X4)) :- appC(X5, X3, X6, X2).
permA(.(X1, X2), .(X3, X4)) :- ','(appcC(X5, X3, X6, X2), appE(X5, X6, X7)).
permA(.(X1, X2), .(X3, X4)) :- ','(appcC(X5, X3, X6, X2), ','(appcD(X1, X5, X6, X7), permA(X7, X4))).

Clauses:

permcA([], []).
permcA(.(X1, X2), .(X1, X3)) :- ','(appcB(X2, X4), permcA(X4, X3)).
permcA(.(X1, X2), .(X3, X4)) :- ','(appcC(X5, X3, X6, X2), ','(appcD(X1, X5, X6, X7), permcA(X7, X4))).
appcC([], X1, X2, .(X1, X2)).
appcC(.(X1, X2), X3, X4, .(X1, X5)) :- appcC(X2, X3, X4, X5).
appcE([], X1, X1).
appcE(.(X1, X2), X3, .(X1, X4)) :- appcE(X2, X3, X4).
appcB(X1, X1).
appcD(X1, X2, X3, .(X1, X4)) :- appcE(X2, X3, X4).

Afs:

permA(x1, x2)  =  permA(x2)


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

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

permA_in_2: (f,b)

appC_in_4: (f,f,f,f)

appcC_in_4: (f,f,f,f)

appE_in_3: (b,f,f)

appcD_in_4: (f,b,f,f)

appcE_in_3: (b,f,f)

Transforming TRIPLES into the following Term Rewriting System:

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

   PERMA_IN_AG(.(X1, X2), .(X1, X3)) -> U3_AG(X1, X2, X3, appcB_in_aa(X2, X4))
   U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> U4_AG(X1, X2, X3, permA_in_ag(X4, X3))
   U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> PERMA_IN_AG(X4, X3)
   PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U5_AG(X1, X2, X3, X4, appC_in_aaaa(X5, X3, X6, X2))
   PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> APPC_IN_AAAA(X5, X3, X6, X2)
   APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> U1_AAAA(X1, X2, X3, X4, X5, appC_in_aaaa(X2, X3, X4, X5))
   APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_AAAA(X2, X3, X4, X5)
   PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U6_AG(X1, X2, X3, X4, appcC_in_aaaa(X5, X3, X6, X2))
   U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U7_AG(X1, X2, X3, X4, appE_in_gaa(X5, X6, X7))
   U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> APPE_IN_GAA(X5, X6, X7)
   APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U2_GAA(X1, X2, X3, X4, appE_in_gaa(X2, X3, X4))
   APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPE_IN_GAA(X2, X3, X4)
   U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U8_AG(X1, X2, X3, X4, appcD_in_agaa(X1, X5, X6, X7))
   U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> U9_AG(X1, X2, X3, X4, permA_in_ag(X7, X4))
   U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> PERMA_IN_AG(X7, X4)

The TRS R consists of the following rules:

   appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1)
   appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2))
   appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5))
   U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5))
   appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1)
   appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4))
   U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4))

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

.(x1, x2)  =  .(x2)

appcB_in_aa(x1, x2)  =  appcB_in_aa

appcB_out_aa(x1, x2)  =  appcB_out_aa

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

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

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

U16_aaaa(x1, x2, x3, x4, x5, x6)  =  U16_aaaa(x6)

appE_in_gaa(x1, x2, x3)  =  appE_in_gaa(x1)

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

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

appcE_in_gaa(x1, x2, x3)  =  appcE_in_gaa(x1)

[]  =  []

appcE_out_gaa(x1, x2, x3)  =  appcE_out_gaa(x1)

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

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

PERMA_IN_AG(x1, x2)  =  PERMA_IN_AG(x2)

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

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

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

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

U1_AAAA(x1, x2, x3, x4, x5, x6)  =  U1_AAAA(x6)

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

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

APPE_IN_GAA(x1, x2, x3)  =  APPE_IN_GAA(x1)

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

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

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


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


Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES



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

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

   PERMA_IN_AG(.(X1, X2), .(X1, X3)) -> U3_AG(X1, X2, X3, appcB_in_aa(X2, X4))
   U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> U4_AG(X1, X2, X3, permA_in_ag(X4, X3))
   U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> PERMA_IN_AG(X4, X3)
   PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U5_AG(X1, X2, X3, X4, appC_in_aaaa(X5, X3, X6, X2))
   PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> APPC_IN_AAAA(X5, X3, X6, X2)
   APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> U1_AAAA(X1, X2, X3, X4, X5, appC_in_aaaa(X2, X3, X4, X5))
   APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_AAAA(X2, X3, X4, X5)
   PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U6_AG(X1, X2, X3, X4, appcC_in_aaaa(X5, X3, X6, X2))
   U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U7_AG(X1, X2, X3, X4, appE_in_gaa(X5, X6, X7))
   U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> APPE_IN_GAA(X5, X6, X7)
   APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U2_GAA(X1, X2, X3, X4, appE_in_gaa(X2, X3, X4))
   APPE_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPE_IN_GAA(X2, X3, X4)
   U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U8_AG(X1, X2, X3, X4, appcD_in_agaa(X1, X5, X6, X7))
   U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> U9_AG(X1, X2, X3, X4, permA_in_ag(X7, X4))
   U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> PERMA_IN_AG(X7, X4)

The TRS R consists of the following rules:

   appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1)
   appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2))
   appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5))
   U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5))
   appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1)
   appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4))
   U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4))

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

.(x1, x2)  =  .(x2)

appcB_in_aa(x1, x2)  =  appcB_in_aa

appcB_out_aa(x1, x2)  =  appcB_out_aa

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

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

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

U16_aaaa(x1, x2, x3, x4, x5, x6)  =  U16_aaaa(x6)

appE_in_gaa(x1, x2, x3)  =  appE_in_gaa(x1)

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

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

appcE_in_gaa(x1, x2, x3)  =  appcE_in_gaa(x1)

[]  =  []

appcE_out_gaa(x1, x2, x3)  =  appcE_out_gaa(x1)

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

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

PERMA_IN_AG(x1, x2)  =  PERMA_IN_AG(x2)

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

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

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

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

U1_AAAA(x1, x2, x3, x4, x5, x6)  =  U1_AAAA(x6)

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

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

APPE_IN_GAA(x1, x2, x3)  =  APPE_IN_GAA(x1)

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

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

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


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

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

(118)
Complex Obligation (AND)

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

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

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

The TRS R consists of the following rules:

   appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1)
   appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2))
   appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5))
   U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5))
   appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1)
   appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4))
   U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4))

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

appcB_in_aa(x1, x2)  =  appcB_in_aa

appcB_out_aa(x1, x2)  =  appcB_out_aa

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

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

U16_aaaa(x1, x2, x3, x4, x5, x6)  =  U16_aaaa(x6)

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

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

appcE_in_gaa(x1, x2, x3)  =  appcE_in_gaa(x1)

[]  =  []

appcE_out_gaa(x1, x2, x3)  =  appcE_out_gaa(x1)

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

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

APPE_IN_GAA(x1, x2, x3)  =  APPE_IN_GAA(x1)


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

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

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

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

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

APPE_IN_GAA(x1, x2, x3)  =  APPE_IN_GAA(x1)


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

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

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

   APPE_IN_GAA(.(X2)) -> APPE_IN_GAA(X2)

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

(124) 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:
*APPE_IN_GAA(.(X2)) -> APPE_IN_GAA(X2)
The graph contains the following edges 1 > 1


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

(125)
YES

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

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

   APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_AAAA(X2, X3, X4, X5)

The TRS R consists of the following rules:

   appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1)
   appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2))
   appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5))
   U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5))
   appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1)
   appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4))
   U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4))

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

appcB_in_aa(x1, x2)  =  appcB_in_aa

appcB_out_aa(x1, x2)  =  appcB_out_aa

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

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

U16_aaaa(x1, x2, x3, x4, x5, x6)  =  U16_aaaa(x6)

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

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

appcE_in_gaa(x1, x2, x3)  =  appcE_in_gaa(x1)

[]  =  []

appcE_out_gaa(x1, x2, x3)  =  appcE_out_gaa(x1)

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

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

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


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

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

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

   APPC_IN_AAAA(.(X1, X2), X3, X4, .(X1, X5)) -> APPC_IN_AAAA(X2, X3, X4, X5)

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

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


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

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

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

   APPC_IN_AAAA -> APPC_IN_AAAA

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

(131) NonTerminationLoopProof (COMPLETE)
We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.

s = APPC_IN_AAAA evaluates to  t =APPC_IN_AAAA

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
* Matcher: [ ]
* Semiunifier: [ ]

--------------------------------------------------------------------------------
Rewriting sequence

The DP semiunifies directly so there is only one rewrite step from APPC_IN_AAAA to APPC_IN_AAAA.




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

(132)
NO

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

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

   U3_AG(X1, X2, X3, appcB_out_aa(X2, X4)) -> PERMA_IN_AG(X4, X3)
   PERMA_IN_AG(.(X1, X2), .(X1, X3)) -> U3_AG(X1, X2, X3, appcB_in_aa(X2, X4))
   PERMA_IN_AG(.(X1, X2), .(X3, X4)) -> U6_AG(X1, X2, X3, X4, appcC_in_aaaa(X5, X3, X6, X2))
   U6_AG(X1, X2, X3, X4, appcC_out_aaaa(X5, X3, X6, X2)) -> U8_AG(X1, X2, X3, X4, appcD_in_agaa(X1, X5, X6, X7))
   U8_AG(X1, X2, X3, X4, appcD_out_agaa(X1, X5, X6, X7)) -> PERMA_IN_AG(X7, X4)

The TRS R consists of the following rules:

   appcB_in_aa(X1, X1) -> appcB_out_aa(X1, X1)
   appcC_in_aaaa([], X1, X2, .(X1, X2)) -> appcC_out_aaaa([], X1, X2, .(X1, X2))
   appcC_in_aaaa(.(X1, X2), X3, X4, .(X1, X5)) -> U16_aaaa(X1, X2, X3, X4, X5, appcC_in_aaaa(X2, X3, X4, X5))
   U16_aaaa(X1, X2, X3, X4, X5, appcC_out_aaaa(X2, X3, X4, X5)) -> appcC_out_aaaa(.(X1, X2), X3, X4, .(X1, X5))
   appcD_in_agaa(X1, X2, X3, .(X1, X4)) -> U18_agaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   appcE_in_gaa([], X1, X1) -> appcE_out_gaa([], X1, X1)
   appcE_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U17_gaa(X1, X2, X3, X4, appcE_in_gaa(X2, X3, X4))
   U17_gaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcE_out_gaa(.(X1, X2), X3, .(X1, X4))
   U18_agaa(X1, X2, X3, X4, appcE_out_gaa(X2, X3, X4)) -> appcD_out_agaa(X1, X2, X3, .(X1, X4))

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

appcB_in_aa(x1, x2)  =  appcB_in_aa

appcB_out_aa(x1, x2)  =  appcB_out_aa

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

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

U16_aaaa(x1, x2, x3, x4, x5, x6)  =  U16_aaaa(x6)

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

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

appcE_in_gaa(x1, x2, x3)  =  appcE_in_gaa(x1)

[]  =  []

appcE_out_gaa(x1, x2, x3)  =  appcE_out_gaa(x1)

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

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

PERMA_IN_AG(x1, x2)  =  PERMA_IN_AG(x2)

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

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

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


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

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

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

   U3_AG(X3, appcB_out_aa) -> PERMA_IN_AG(X3)
   PERMA_IN_AG(.(X3)) -> U3_AG(X3, appcB_in_aa)
   PERMA_IN_AG(.(X4)) -> U6_AG(X4, appcC_in_aaaa)
   U6_AG(X4, appcC_out_aaaa(X5)) -> U8_AG(X4, appcD_in_agaa(X5))
   U8_AG(X4, appcD_out_agaa(X5)) -> PERMA_IN_AG(X4)

The TRS R consists of the following rules:

   appcB_in_aa -> appcB_out_aa
   appcC_in_aaaa -> appcC_out_aaaa([])
   appcC_in_aaaa -> U16_aaaa(appcC_in_aaaa)
   U16_aaaa(appcC_out_aaaa(X2)) -> appcC_out_aaaa(.(X2))
   appcD_in_agaa(X2) -> U18_agaa(X2, appcE_in_gaa(X2))
   appcE_in_gaa([]) -> appcE_out_gaa([])
   appcE_in_gaa(.(X2)) -> U17_gaa(X2, appcE_in_gaa(X2))
   U17_gaa(X2, appcE_out_gaa(X2)) -> appcE_out_gaa(.(X2))
   U18_agaa(X2, appcE_out_gaa(X2)) -> appcD_out_agaa(X2)

The set Q consists of the following terms:

   appcB_in_aa
   appcC_in_aaaa
   U16_aaaa(x0)
   appcD_in_agaa(x0)
   appcE_in_gaa(x0)
   U17_gaa(x0, x1)
   U18_agaa(x0, x1)

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

(136) 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:
*PERMA_IN_AG(.(X3)) -> U3_AG(X3, appcB_in_aa)
The graph contains the following edges 1 > 1


*PERMA_IN_AG(.(X4)) -> U6_AG(X4, appcC_in_aaaa)
The graph contains the following edges 1 > 1


*U3_AG(X3, appcB_out_aa) -> PERMA_IN_AG(X3)
The graph contains the following edges 1 >= 1


*U8_AG(X4, appcD_out_agaa(X5)) -> PERMA_IN_AG(X4)
The graph contains the following edges 1 >= 1


*U6_AG(X4, appcC_out_aaaa(X5)) -> U8_AG(X4, appcD_in_agaa(X5))
The graph contains the following edges 1 >= 1


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

(137)
YES