(0) Obligation:

Clauses:

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

Queries:

perm(g,a).

(1) PrologToPrologProblemTransformerProof (SOUND transformation)

Built Prolog problem from termination graph.

(2) Obligation:

Clauses:

app10(.(X98, X99), T40, X100, .(X98, T39)) :- app10(X99, T40, X100, T39).
app10([], T45, X117, .(T45, X117)).
app25(.(T83, T84), T85, .(T83, X200)) :- app25(T84, T85, X200).
app25([], T91, T91).
app40(.(X294, X295), T131, X296, .(X294, T130)) :- app40(X295, T131, X296, T130).
app40([], T136, X313, .(T136, X313)).
perm21(T110, .(T111, T112)) :- app40(X242, T111, X243, T110).
perm21(T110, .(T111, T117)) :- ','(app40(T115, T111, T116, T110), app50(T115, T116, X244)).
perm21(T110, .(T111, T141)) :- ','(app40(T115, T111, T116, T110), ','(app50(T115, T116, T140), perm21(T140, T141))).
perm21([], []).
app50(.(T157, T160), T161, .(T157, X349)) :- app50(T160, T161, X349).
app50([], T167, T167).
app20(X169, T66, T67, .(X169, X170)) :- app25(T66, T67, X170).
app67(X408, X408).
perm1(.(X45, T20), .(T21, T22)) :- app10(X46, T21, X47, T20).
perm1(.(X45, T20), .(T21, T27)) :- ','(app10(T25, T21, T26, T20), app20(X45, T25, T26, X9)).
perm1(.(T48, T20), .(T21, T27)) :- ','(app10(T25, T21, T26, T20), ','(app20(T48, T25, T26, T49), perm21(T49, T27))).
perm1(.(T175, X378), .(T175, T176)) :- app67(X378, X9).
perm1(.(T175, T179), .(T175, T176)) :- ','(app67(T179, T180), perm21(T180, T176)).
perm1([], []).
perm1([], []).

Queries:

perm1(g,a).

(3) PrologToPiTRSProof (SOUND transformation)

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

perm1_in_ga(.(X45, T20), .(T21, T22)) → U12_ga(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
app10_in_aaag(.(X98, X99), T40, X100, .(X98, T39)) → U1_aaag(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
app10_in_aaag([], T45, X117, .(T45, X117)) → app10_out_aaag([], T45, X117, .(T45, X117))
U1_aaag(X98, X99, T40, X100, T39, app10_out_aaag(X99, T40, X100, T39)) → app10_out_aaag(.(X98, X99), T40, X100, .(X98, T39))
U12_ga(X45, T20, T21, T22, app10_out_aaag(X46, T21, X47, T20)) → perm1_out_ga(.(X45, T20), .(T21, T22))
perm1_in_ga(.(X45, T20), .(T21, T27)) → U13_ga(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_ga(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_ga(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
app20_in_ggga(X169, T66, T67, .(X169, X170)) → U11_ggga(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
app25_in_gga(.(T83, T84), T85, .(T83, X200)) → U2_gga(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
app25_in_gga([], T91, T91) → app25_out_gga([], T91, T91)
U2_gga(T83, T84, T85, X200, app25_out_gga(T84, T85, X200)) → app25_out_gga(.(T83, T84), T85, .(T83, X200))
U11_ggga(X169, T66, T67, X170, app25_out_gga(T66, T67, X170)) → app20_out_ggga(X169, T66, T67, .(X169, X170))
U14_ga(X45, T20, T21, T27, app20_out_ggga(X45, T25, T26, X9)) → perm1_out_ga(.(X45, T20), .(T21, T27))
perm1_in_ga(.(T48, T20), .(T21, T27)) → U15_ga(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_ga(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_ga(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U16_ga(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_ga(T48, T20, T21, T27, perm21_in_ga(T49, T27))
perm21_in_ga(T110, .(T111, T112)) → U4_ga(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U4_ga(T110, T111, T112, app40_out_aaag(X242, T111, X243, T110)) → perm21_out_ga(T110, .(T111, T112))
perm21_in_ga(T110, .(T111, T117)) → U5_ga(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_ga(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_ga(T110, T111, T117, app50_in_gga(T115, T116, X244))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))
U6_ga(T110, T111, T117, app50_out_gga(T115, T116, X244)) → perm21_out_ga(T110, .(T111, T117))
perm21_in_ga(T110, .(T111, T141)) → U7_ga(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_ga(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_ga(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_ga(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_ga(T110, T111, T141, perm21_in_ga(T140, T141))
perm21_in_ga([], []) → perm21_out_ga([], [])
U9_ga(T110, T111, T141, perm21_out_ga(T140, T141)) → perm21_out_ga(T110, .(T111, T141))
U17_ga(T48, T20, T21, T27, perm21_out_ga(T49, T27)) → perm1_out_ga(.(T48, T20), .(T21, T27))
perm1_in_ga(.(T175, X378), .(T175, T176)) → U18_ga(T175, X378, T176, app67_in_ga(X378, X9))
app67_in_ga(X408, X408) → app67_out_ga(X408, X408)
U18_ga(T175, X378, T176, app67_out_ga(X378, X9)) → perm1_out_ga(.(T175, X378), .(T175, T176))
perm1_in_ga(.(T175, T179), .(T175, T176)) → U19_ga(T175, T179, T176, app67_in_ga(T179, T180))
U19_ga(T175, T179, T176, app67_out_ga(T179, T180)) → U20_ga(T175, T179, T176, perm21_in_ga(T180, T176))
U20_ga(T175, T179, T176, perm21_out_ga(T180, T176)) → perm1_out_ga(.(T175, T179), .(T175, T176))
perm1_in_ga([], []) → perm1_out_ga([], [])

The argument filtering Pi contains the following mapping:
perm1_in_ga(x1, x2)  =  perm1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
U12_ga(x1, x2, x3, x4, x5)  =  U12_ga(x5)
app10_in_aaag(x1, x2, x3, x4)  =  app10_in_aaag(x4)
U1_aaag(x1, x2, x3, x4, x5, x6)  =  U1_aaag(x1, x6)
app10_out_aaag(x1, x2, x3, x4)  =  app10_out_aaag(x1, x2, x3)
perm1_out_ga(x1, x2)  =  perm1_out_ga
U13_ga(x1, x2, x3, x4, x5)  =  U13_ga(x1, x5)
U14_ga(x1, x2, x3, x4, x5)  =  U14_ga(x5)
app20_in_ggga(x1, x2, x3, x4)  =  app20_in_ggga(x1, x2, x3)
U11_ggga(x1, x2, x3, x4, x5)  =  U11_ggga(x1, x5)
app25_in_gga(x1, x2, x3)  =  app25_in_gga(x1, x2)
U2_gga(x1, x2, x3, x4, x5)  =  U2_gga(x1, x5)
[]  =  []
app25_out_gga(x1, x2, x3)  =  app25_out_gga(x3)
app20_out_ggga(x1, x2, x3, x4)  =  app20_out_ggga(x4)
U15_ga(x1, x2, x3, x4, x5)  =  U15_ga(x1, x5)
U16_ga(x1, x2, x3, x4, x5)  =  U16_ga(x5)
U17_ga(x1, x2, x3, x4, x5)  =  U17_ga(x5)
perm21_in_ga(x1, x2)  =  perm21_in_ga(x1)
U4_ga(x1, x2, x3, x4)  =  U4_ga(x4)
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
perm21_out_ga(x1, x2)  =  perm21_out_ga
U5_ga(x1, x2, x3, x4)  =  U5_ga(x4)
U6_ga(x1, x2, x3, x4)  =  U6_ga(x4)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
U7_ga(x1, x2, x3, x4)  =  U7_ga(x4)
U8_ga(x1, x2, x3, x4)  =  U8_ga(x4)
U9_ga(x1, x2, x3, x4)  =  U9_ga(x4)
U18_ga(x1, x2, x3, x4)  =  U18_ga(x4)
app67_in_ga(x1, x2)  =  app67_in_ga(x1)
app67_out_ga(x1, x2)  =  app67_out_ga(x2)
U19_ga(x1, x2, x3, x4)  =  U19_ga(x4)
U20_ga(x1, x2, x3, x4)  =  U20_ga(x4)

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog

(4) Obligation:

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

perm1_in_ga(.(X45, T20), .(T21, T22)) → U12_ga(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
app10_in_aaag(.(X98, X99), T40, X100, .(X98, T39)) → U1_aaag(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
app10_in_aaag([], T45, X117, .(T45, X117)) → app10_out_aaag([], T45, X117, .(T45, X117))
U1_aaag(X98, X99, T40, X100, T39, app10_out_aaag(X99, T40, X100, T39)) → app10_out_aaag(.(X98, X99), T40, X100, .(X98, T39))
U12_ga(X45, T20, T21, T22, app10_out_aaag(X46, T21, X47, T20)) → perm1_out_ga(.(X45, T20), .(T21, T22))
perm1_in_ga(.(X45, T20), .(T21, T27)) → U13_ga(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_ga(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_ga(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
app20_in_ggga(X169, T66, T67, .(X169, X170)) → U11_ggga(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
app25_in_gga(.(T83, T84), T85, .(T83, X200)) → U2_gga(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
app25_in_gga([], T91, T91) → app25_out_gga([], T91, T91)
U2_gga(T83, T84, T85, X200, app25_out_gga(T84, T85, X200)) → app25_out_gga(.(T83, T84), T85, .(T83, X200))
U11_ggga(X169, T66, T67, X170, app25_out_gga(T66, T67, X170)) → app20_out_ggga(X169, T66, T67, .(X169, X170))
U14_ga(X45, T20, T21, T27, app20_out_ggga(X45, T25, T26, X9)) → perm1_out_ga(.(X45, T20), .(T21, T27))
perm1_in_ga(.(T48, T20), .(T21, T27)) → U15_ga(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_ga(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_ga(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U16_ga(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_ga(T48, T20, T21, T27, perm21_in_ga(T49, T27))
perm21_in_ga(T110, .(T111, T112)) → U4_ga(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U4_ga(T110, T111, T112, app40_out_aaag(X242, T111, X243, T110)) → perm21_out_ga(T110, .(T111, T112))
perm21_in_ga(T110, .(T111, T117)) → U5_ga(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_ga(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_ga(T110, T111, T117, app50_in_gga(T115, T116, X244))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))
U6_ga(T110, T111, T117, app50_out_gga(T115, T116, X244)) → perm21_out_ga(T110, .(T111, T117))
perm21_in_ga(T110, .(T111, T141)) → U7_ga(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_ga(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_ga(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_ga(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_ga(T110, T111, T141, perm21_in_ga(T140, T141))
perm21_in_ga([], []) → perm21_out_ga([], [])
U9_ga(T110, T111, T141, perm21_out_ga(T140, T141)) → perm21_out_ga(T110, .(T111, T141))
U17_ga(T48, T20, T21, T27, perm21_out_ga(T49, T27)) → perm1_out_ga(.(T48, T20), .(T21, T27))
perm1_in_ga(.(T175, X378), .(T175, T176)) → U18_ga(T175, X378, T176, app67_in_ga(X378, X9))
app67_in_ga(X408, X408) → app67_out_ga(X408, X408)
U18_ga(T175, X378, T176, app67_out_ga(X378, X9)) → perm1_out_ga(.(T175, X378), .(T175, T176))
perm1_in_ga(.(T175, T179), .(T175, T176)) → U19_ga(T175, T179, T176, app67_in_ga(T179, T180))
U19_ga(T175, T179, T176, app67_out_ga(T179, T180)) → U20_ga(T175, T179, T176, perm21_in_ga(T180, T176))
U20_ga(T175, T179, T176, perm21_out_ga(T180, T176)) → perm1_out_ga(.(T175, T179), .(T175, T176))
perm1_in_ga([], []) → perm1_out_ga([], [])

The argument filtering Pi contains the following mapping:
perm1_in_ga(x1, x2)  =  perm1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
U12_ga(x1, x2, x3, x4, x5)  =  U12_ga(x5)
app10_in_aaag(x1, x2, x3, x4)  =  app10_in_aaag(x4)
U1_aaag(x1, x2, x3, x4, x5, x6)  =  U1_aaag(x1, x6)
app10_out_aaag(x1, x2, x3, x4)  =  app10_out_aaag(x1, x2, x3)
perm1_out_ga(x1, x2)  =  perm1_out_ga
U13_ga(x1, x2, x3, x4, x5)  =  U13_ga(x1, x5)
U14_ga(x1, x2, x3, x4, x5)  =  U14_ga(x5)
app20_in_ggga(x1, x2, x3, x4)  =  app20_in_ggga(x1, x2, x3)
U11_ggga(x1, x2, x3, x4, x5)  =  U11_ggga(x1, x5)
app25_in_gga(x1, x2, x3)  =  app25_in_gga(x1, x2)
U2_gga(x1, x2, x3, x4, x5)  =  U2_gga(x1, x5)
[]  =  []
app25_out_gga(x1, x2, x3)  =  app25_out_gga(x3)
app20_out_ggga(x1, x2, x3, x4)  =  app20_out_ggga(x4)
U15_ga(x1, x2, x3, x4, x5)  =  U15_ga(x1, x5)
U16_ga(x1, x2, x3, x4, x5)  =  U16_ga(x5)
U17_ga(x1, x2, x3, x4, x5)  =  U17_ga(x5)
perm21_in_ga(x1, x2)  =  perm21_in_ga(x1)
U4_ga(x1, x2, x3, x4)  =  U4_ga(x4)
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
perm21_out_ga(x1, x2)  =  perm21_out_ga
U5_ga(x1, x2, x3, x4)  =  U5_ga(x4)
U6_ga(x1, x2, x3, x4)  =  U6_ga(x4)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
U7_ga(x1, x2, x3, x4)  =  U7_ga(x4)
U8_ga(x1, x2, x3, x4)  =  U8_ga(x4)
U9_ga(x1, x2, x3, x4)  =  U9_ga(x4)
U18_ga(x1, x2, x3, x4)  =  U18_ga(x4)
app67_in_ga(x1, x2)  =  app67_in_ga(x1)
app67_out_ga(x1, x2)  =  app67_out_ga(x2)
U19_ga(x1, x2, x3, x4)  =  U19_ga(x4)
U20_ga(x1, x2, x3, x4)  =  U20_ga(x4)

(5) DependencyPairsProof (EQUIVALENT transformation)

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

PERM1_IN_GA(.(X45, T20), .(T21, T22)) → U12_GA(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
PERM1_IN_GA(.(X45, T20), .(T21, T22)) → APP10_IN_AAAG(X46, T21, X47, T20)
APP10_IN_AAAG(.(X98, X99), T40, X100, .(X98, T39)) → U1_AAAG(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
APP10_IN_AAAG(.(X98, X99), T40, X100, .(X98, T39)) → APP10_IN_AAAG(X99, T40, X100, T39)
PERM1_IN_GA(.(X45, T20), .(T21, T27)) → U13_GA(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_GA(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_GA(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
U13_GA(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → APP20_IN_GGGA(X45, T25, T26, X9)
APP20_IN_GGGA(X169, T66, T67, .(X169, X170)) → U11_GGGA(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
APP20_IN_GGGA(X169, T66, T67, .(X169, X170)) → APP25_IN_GGA(T66, T67, X170)
APP25_IN_GGA(.(T83, T84), T85, .(T83, X200)) → U2_GGA(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
APP25_IN_GGA(.(T83, T84), T85, .(T83, X200)) → APP25_IN_GGA(T84, T85, X200)
PERM1_IN_GA(.(T48, T20), .(T21, T27)) → U15_GA(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_GA(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_GA(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U15_GA(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → APP20_IN_GGGA(T48, T25, T26, T49)
U16_GA(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_GA(T48, T20, T21, T27, perm21_in_ga(T49, T27))
U16_GA(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → PERM21_IN_GA(T49, T27)
PERM21_IN_GA(T110, .(T111, T112)) → U4_GA(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
PERM21_IN_GA(T110, .(T111, T112)) → APP40_IN_AAAG(X242, T111, X243, T110)
APP40_IN_AAAG(.(X294, X295), T131, X296, .(X294, T130)) → U3_AAAG(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
APP40_IN_AAAG(.(X294, X295), T131, X296, .(X294, T130)) → APP40_IN_AAAG(X295, T131, X296, T130)
PERM21_IN_GA(T110, .(T111, T117)) → U5_GA(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_GA(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_GA(T110, T111, T117, app50_in_gga(T115, T116, X244))
U5_GA(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → APP50_IN_GGA(T115, T116, X244)
APP50_IN_GGA(.(T157, T160), T161, .(T157, X349)) → U10_GGA(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
APP50_IN_GGA(.(T157, T160), T161, .(T157, X349)) → APP50_IN_GGA(T160, T161, X349)
PERM21_IN_GA(T110, .(T111, T141)) → U7_GA(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_GA(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_GA(T110, T111, T141, app50_in_gga(T115, T116, T140))
U7_GA(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → APP50_IN_GGA(T115, T116, T140)
U8_GA(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_GA(T110, T111, T141, perm21_in_ga(T140, T141))
U8_GA(T110, T111, T141, app50_out_gga(T115, T116, T140)) → PERM21_IN_GA(T140, T141)
PERM1_IN_GA(.(T175, X378), .(T175, T176)) → U18_GA(T175, X378, T176, app67_in_ga(X378, X9))
PERM1_IN_GA(.(T175, X378), .(T175, T176)) → APP67_IN_GA(X378, X9)
PERM1_IN_GA(.(T175, T179), .(T175, T176)) → U19_GA(T175, T179, T176, app67_in_ga(T179, T180))
U19_GA(T175, T179, T176, app67_out_ga(T179, T180)) → U20_GA(T175, T179, T176, perm21_in_ga(T180, T176))
U19_GA(T175, T179, T176, app67_out_ga(T179, T180)) → PERM21_IN_GA(T180, T176)

The TRS R consists of the following rules:

perm1_in_ga(.(X45, T20), .(T21, T22)) → U12_ga(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
app10_in_aaag(.(X98, X99), T40, X100, .(X98, T39)) → U1_aaag(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
app10_in_aaag([], T45, X117, .(T45, X117)) → app10_out_aaag([], T45, X117, .(T45, X117))
U1_aaag(X98, X99, T40, X100, T39, app10_out_aaag(X99, T40, X100, T39)) → app10_out_aaag(.(X98, X99), T40, X100, .(X98, T39))
U12_ga(X45, T20, T21, T22, app10_out_aaag(X46, T21, X47, T20)) → perm1_out_ga(.(X45, T20), .(T21, T22))
perm1_in_ga(.(X45, T20), .(T21, T27)) → U13_ga(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_ga(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_ga(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
app20_in_ggga(X169, T66, T67, .(X169, X170)) → U11_ggga(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
app25_in_gga(.(T83, T84), T85, .(T83, X200)) → U2_gga(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
app25_in_gga([], T91, T91) → app25_out_gga([], T91, T91)
U2_gga(T83, T84, T85, X200, app25_out_gga(T84, T85, X200)) → app25_out_gga(.(T83, T84), T85, .(T83, X200))
U11_ggga(X169, T66, T67, X170, app25_out_gga(T66, T67, X170)) → app20_out_ggga(X169, T66, T67, .(X169, X170))
U14_ga(X45, T20, T21, T27, app20_out_ggga(X45, T25, T26, X9)) → perm1_out_ga(.(X45, T20), .(T21, T27))
perm1_in_ga(.(T48, T20), .(T21, T27)) → U15_ga(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_ga(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_ga(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U16_ga(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_ga(T48, T20, T21, T27, perm21_in_ga(T49, T27))
perm21_in_ga(T110, .(T111, T112)) → U4_ga(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U4_ga(T110, T111, T112, app40_out_aaag(X242, T111, X243, T110)) → perm21_out_ga(T110, .(T111, T112))
perm21_in_ga(T110, .(T111, T117)) → U5_ga(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_ga(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_ga(T110, T111, T117, app50_in_gga(T115, T116, X244))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))
U6_ga(T110, T111, T117, app50_out_gga(T115, T116, X244)) → perm21_out_ga(T110, .(T111, T117))
perm21_in_ga(T110, .(T111, T141)) → U7_ga(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_ga(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_ga(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_ga(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_ga(T110, T111, T141, perm21_in_ga(T140, T141))
perm21_in_ga([], []) → perm21_out_ga([], [])
U9_ga(T110, T111, T141, perm21_out_ga(T140, T141)) → perm21_out_ga(T110, .(T111, T141))
U17_ga(T48, T20, T21, T27, perm21_out_ga(T49, T27)) → perm1_out_ga(.(T48, T20), .(T21, T27))
perm1_in_ga(.(T175, X378), .(T175, T176)) → U18_ga(T175, X378, T176, app67_in_ga(X378, X9))
app67_in_ga(X408, X408) → app67_out_ga(X408, X408)
U18_ga(T175, X378, T176, app67_out_ga(X378, X9)) → perm1_out_ga(.(T175, X378), .(T175, T176))
perm1_in_ga(.(T175, T179), .(T175, T176)) → U19_ga(T175, T179, T176, app67_in_ga(T179, T180))
U19_ga(T175, T179, T176, app67_out_ga(T179, T180)) → U20_ga(T175, T179, T176, perm21_in_ga(T180, T176))
U20_ga(T175, T179, T176, perm21_out_ga(T180, T176)) → perm1_out_ga(.(T175, T179), .(T175, T176))
perm1_in_ga([], []) → perm1_out_ga([], [])

The argument filtering Pi contains the following mapping:
perm1_in_ga(x1, x2)  =  perm1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
U12_ga(x1, x2, x3, x4, x5)  =  U12_ga(x5)
app10_in_aaag(x1, x2, x3, x4)  =  app10_in_aaag(x4)
U1_aaag(x1, x2, x3, x4, x5, x6)  =  U1_aaag(x1, x6)
app10_out_aaag(x1, x2, x3, x4)  =  app10_out_aaag(x1, x2, x3)
perm1_out_ga(x1, x2)  =  perm1_out_ga
U13_ga(x1, x2, x3, x4, x5)  =  U13_ga(x1, x5)
U14_ga(x1, x2, x3, x4, x5)  =  U14_ga(x5)
app20_in_ggga(x1, x2, x3, x4)  =  app20_in_ggga(x1, x2, x3)
U11_ggga(x1, x2, x3, x4, x5)  =  U11_ggga(x1, x5)
app25_in_gga(x1, x2, x3)  =  app25_in_gga(x1, x2)
U2_gga(x1, x2, x3, x4, x5)  =  U2_gga(x1, x5)
[]  =  []
app25_out_gga(x1, x2, x3)  =  app25_out_gga(x3)
app20_out_ggga(x1, x2, x3, x4)  =  app20_out_ggga(x4)
U15_ga(x1, x2, x3, x4, x5)  =  U15_ga(x1, x5)
U16_ga(x1, x2, x3, x4, x5)  =  U16_ga(x5)
U17_ga(x1, x2, x3, x4, x5)  =  U17_ga(x5)
perm21_in_ga(x1, x2)  =  perm21_in_ga(x1)
U4_ga(x1, x2, x3, x4)  =  U4_ga(x4)
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
perm21_out_ga(x1, x2)  =  perm21_out_ga
U5_ga(x1, x2, x3, x4)  =  U5_ga(x4)
U6_ga(x1, x2, x3, x4)  =  U6_ga(x4)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
U7_ga(x1, x2, x3, x4)  =  U7_ga(x4)
U8_ga(x1, x2, x3, x4)  =  U8_ga(x4)
U9_ga(x1, x2, x3, x4)  =  U9_ga(x4)
U18_ga(x1, x2, x3, x4)  =  U18_ga(x4)
app67_in_ga(x1, x2)  =  app67_in_ga(x1)
app67_out_ga(x1, x2)  =  app67_out_ga(x2)
U19_ga(x1, x2, x3, x4)  =  U19_ga(x4)
U20_ga(x1, x2, x3, x4)  =  U20_ga(x4)
PERM1_IN_GA(x1, x2)  =  PERM1_IN_GA(x1)
U12_GA(x1, x2, x3, x4, x5)  =  U12_GA(x5)
APP10_IN_AAAG(x1, x2, x3, x4)  =  APP10_IN_AAAG(x4)
U1_AAAG(x1, x2, x3, x4, x5, x6)  =  U1_AAAG(x1, x6)
U13_GA(x1, x2, x3, x4, x5)  =  U13_GA(x1, x5)
U14_GA(x1, x2, x3, x4, x5)  =  U14_GA(x5)
APP20_IN_GGGA(x1, x2, x3, x4)  =  APP20_IN_GGGA(x1, x2, x3)
U11_GGGA(x1, x2, x3, x4, x5)  =  U11_GGGA(x1, x5)
APP25_IN_GGA(x1, x2, x3)  =  APP25_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4, x5)  =  U2_GGA(x1, x5)
U15_GA(x1, x2, x3, x4, x5)  =  U15_GA(x1, x5)
U16_GA(x1, x2, x3, x4, x5)  =  U16_GA(x5)
U17_GA(x1, x2, x3, x4, x5)  =  U17_GA(x5)
PERM21_IN_GA(x1, x2)  =  PERM21_IN_GA(x1)
U4_GA(x1, x2, x3, x4)  =  U4_GA(x4)
APP40_IN_AAAG(x1, x2, x3, x4)  =  APP40_IN_AAAG(x4)
U3_AAAG(x1, x2, x3, x4, x5, x6)  =  U3_AAAG(x1, x6)
U5_GA(x1, x2, x3, x4)  =  U5_GA(x4)
U6_GA(x1, x2, x3, x4)  =  U6_GA(x4)
APP50_IN_GGA(x1, x2, x3)  =  APP50_IN_GGA(x1, x2)
U10_GGA(x1, x2, x3, x4, x5)  =  U10_GGA(x1, x5)
U7_GA(x1, x2, x3, x4)  =  U7_GA(x4)
U8_GA(x1, x2, x3, x4)  =  U8_GA(x4)
U9_GA(x1, x2, x3, x4)  =  U9_GA(x4)
U18_GA(x1, x2, x3, x4)  =  U18_GA(x4)
APP67_IN_GA(x1, x2)  =  APP67_IN_GA(x1)
U19_GA(x1, x2, x3, x4)  =  U19_GA(x4)
U20_GA(x1, x2, x3, x4)  =  U20_GA(x4)

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

(6) Obligation:

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

PERM1_IN_GA(.(X45, T20), .(T21, T22)) → U12_GA(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
PERM1_IN_GA(.(X45, T20), .(T21, T22)) → APP10_IN_AAAG(X46, T21, X47, T20)
APP10_IN_AAAG(.(X98, X99), T40, X100, .(X98, T39)) → U1_AAAG(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
APP10_IN_AAAG(.(X98, X99), T40, X100, .(X98, T39)) → APP10_IN_AAAG(X99, T40, X100, T39)
PERM1_IN_GA(.(X45, T20), .(T21, T27)) → U13_GA(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_GA(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_GA(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
U13_GA(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → APP20_IN_GGGA(X45, T25, T26, X9)
APP20_IN_GGGA(X169, T66, T67, .(X169, X170)) → U11_GGGA(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
APP20_IN_GGGA(X169, T66, T67, .(X169, X170)) → APP25_IN_GGA(T66, T67, X170)
APP25_IN_GGA(.(T83, T84), T85, .(T83, X200)) → U2_GGA(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
APP25_IN_GGA(.(T83, T84), T85, .(T83, X200)) → APP25_IN_GGA(T84, T85, X200)
PERM1_IN_GA(.(T48, T20), .(T21, T27)) → U15_GA(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_GA(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_GA(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U15_GA(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → APP20_IN_GGGA(T48, T25, T26, T49)
U16_GA(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_GA(T48, T20, T21, T27, perm21_in_ga(T49, T27))
U16_GA(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → PERM21_IN_GA(T49, T27)
PERM21_IN_GA(T110, .(T111, T112)) → U4_GA(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
PERM21_IN_GA(T110, .(T111, T112)) → APP40_IN_AAAG(X242, T111, X243, T110)
APP40_IN_AAAG(.(X294, X295), T131, X296, .(X294, T130)) → U3_AAAG(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
APP40_IN_AAAG(.(X294, X295), T131, X296, .(X294, T130)) → APP40_IN_AAAG(X295, T131, X296, T130)
PERM21_IN_GA(T110, .(T111, T117)) → U5_GA(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_GA(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_GA(T110, T111, T117, app50_in_gga(T115, T116, X244))
U5_GA(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → APP50_IN_GGA(T115, T116, X244)
APP50_IN_GGA(.(T157, T160), T161, .(T157, X349)) → U10_GGA(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
APP50_IN_GGA(.(T157, T160), T161, .(T157, X349)) → APP50_IN_GGA(T160, T161, X349)
PERM21_IN_GA(T110, .(T111, T141)) → U7_GA(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_GA(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_GA(T110, T111, T141, app50_in_gga(T115, T116, T140))
U7_GA(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → APP50_IN_GGA(T115, T116, T140)
U8_GA(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_GA(T110, T111, T141, perm21_in_ga(T140, T141))
U8_GA(T110, T111, T141, app50_out_gga(T115, T116, T140)) → PERM21_IN_GA(T140, T141)
PERM1_IN_GA(.(T175, X378), .(T175, T176)) → U18_GA(T175, X378, T176, app67_in_ga(X378, X9))
PERM1_IN_GA(.(T175, X378), .(T175, T176)) → APP67_IN_GA(X378, X9)
PERM1_IN_GA(.(T175, T179), .(T175, T176)) → U19_GA(T175, T179, T176, app67_in_ga(T179, T180))
U19_GA(T175, T179, T176, app67_out_ga(T179, T180)) → U20_GA(T175, T179, T176, perm21_in_ga(T180, T176))
U19_GA(T175, T179, T176, app67_out_ga(T179, T180)) → PERM21_IN_GA(T180, T176)

The TRS R consists of the following rules:

perm1_in_ga(.(X45, T20), .(T21, T22)) → U12_ga(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
app10_in_aaag(.(X98, X99), T40, X100, .(X98, T39)) → U1_aaag(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
app10_in_aaag([], T45, X117, .(T45, X117)) → app10_out_aaag([], T45, X117, .(T45, X117))
U1_aaag(X98, X99, T40, X100, T39, app10_out_aaag(X99, T40, X100, T39)) → app10_out_aaag(.(X98, X99), T40, X100, .(X98, T39))
U12_ga(X45, T20, T21, T22, app10_out_aaag(X46, T21, X47, T20)) → perm1_out_ga(.(X45, T20), .(T21, T22))
perm1_in_ga(.(X45, T20), .(T21, T27)) → U13_ga(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_ga(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_ga(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
app20_in_ggga(X169, T66, T67, .(X169, X170)) → U11_ggga(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
app25_in_gga(.(T83, T84), T85, .(T83, X200)) → U2_gga(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
app25_in_gga([], T91, T91) → app25_out_gga([], T91, T91)
U2_gga(T83, T84, T85, X200, app25_out_gga(T84, T85, X200)) → app25_out_gga(.(T83, T84), T85, .(T83, X200))
U11_ggga(X169, T66, T67, X170, app25_out_gga(T66, T67, X170)) → app20_out_ggga(X169, T66, T67, .(X169, X170))
U14_ga(X45, T20, T21, T27, app20_out_ggga(X45, T25, T26, X9)) → perm1_out_ga(.(X45, T20), .(T21, T27))
perm1_in_ga(.(T48, T20), .(T21, T27)) → U15_ga(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_ga(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_ga(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U16_ga(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_ga(T48, T20, T21, T27, perm21_in_ga(T49, T27))
perm21_in_ga(T110, .(T111, T112)) → U4_ga(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U4_ga(T110, T111, T112, app40_out_aaag(X242, T111, X243, T110)) → perm21_out_ga(T110, .(T111, T112))
perm21_in_ga(T110, .(T111, T117)) → U5_ga(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_ga(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_ga(T110, T111, T117, app50_in_gga(T115, T116, X244))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))
U6_ga(T110, T111, T117, app50_out_gga(T115, T116, X244)) → perm21_out_ga(T110, .(T111, T117))
perm21_in_ga(T110, .(T111, T141)) → U7_ga(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_ga(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_ga(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_ga(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_ga(T110, T111, T141, perm21_in_ga(T140, T141))
perm21_in_ga([], []) → perm21_out_ga([], [])
U9_ga(T110, T111, T141, perm21_out_ga(T140, T141)) → perm21_out_ga(T110, .(T111, T141))
U17_ga(T48, T20, T21, T27, perm21_out_ga(T49, T27)) → perm1_out_ga(.(T48, T20), .(T21, T27))
perm1_in_ga(.(T175, X378), .(T175, T176)) → U18_ga(T175, X378, T176, app67_in_ga(X378, X9))
app67_in_ga(X408, X408) → app67_out_ga(X408, X408)
U18_ga(T175, X378, T176, app67_out_ga(X378, X9)) → perm1_out_ga(.(T175, X378), .(T175, T176))
perm1_in_ga(.(T175, T179), .(T175, T176)) → U19_ga(T175, T179, T176, app67_in_ga(T179, T180))
U19_ga(T175, T179, T176, app67_out_ga(T179, T180)) → U20_ga(T175, T179, T176, perm21_in_ga(T180, T176))
U20_ga(T175, T179, T176, perm21_out_ga(T180, T176)) → perm1_out_ga(.(T175, T179), .(T175, T176))
perm1_in_ga([], []) → perm1_out_ga([], [])

The argument filtering Pi contains the following mapping:
perm1_in_ga(x1, x2)  =  perm1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
U12_ga(x1, x2, x3, x4, x5)  =  U12_ga(x5)
app10_in_aaag(x1, x2, x3, x4)  =  app10_in_aaag(x4)
U1_aaag(x1, x2, x3, x4, x5, x6)  =  U1_aaag(x1, x6)
app10_out_aaag(x1, x2, x3, x4)  =  app10_out_aaag(x1, x2, x3)
perm1_out_ga(x1, x2)  =  perm1_out_ga
U13_ga(x1, x2, x3, x4, x5)  =  U13_ga(x1, x5)
U14_ga(x1, x2, x3, x4, x5)  =  U14_ga(x5)
app20_in_ggga(x1, x2, x3, x4)  =  app20_in_ggga(x1, x2, x3)
U11_ggga(x1, x2, x3, x4, x5)  =  U11_ggga(x1, x5)
app25_in_gga(x1, x2, x3)  =  app25_in_gga(x1, x2)
U2_gga(x1, x2, x3, x4, x5)  =  U2_gga(x1, x5)
[]  =  []
app25_out_gga(x1, x2, x3)  =  app25_out_gga(x3)
app20_out_ggga(x1, x2, x3, x4)  =  app20_out_ggga(x4)
U15_ga(x1, x2, x3, x4, x5)  =  U15_ga(x1, x5)
U16_ga(x1, x2, x3, x4, x5)  =  U16_ga(x5)
U17_ga(x1, x2, x3, x4, x5)  =  U17_ga(x5)
perm21_in_ga(x1, x2)  =  perm21_in_ga(x1)
U4_ga(x1, x2, x3, x4)  =  U4_ga(x4)
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
perm21_out_ga(x1, x2)  =  perm21_out_ga
U5_ga(x1, x2, x3, x4)  =  U5_ga(x4)
U6_ga(x1, x2, x3, x4)  =  U6_ga(x4)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
U7_ga(x1, x2, x3, x4)  =  U7_ga(x4)
U8_ga(x1, x2, x3, x4)  =  U8_ga(x4)
U9_ga(x1, x2, x3, x4)  =  U9_ga(x4)
U18_ga(x1, x2, x3, x4)  =  U18_ga(x4)
app67_in_ga(x1, x2)  =  app67_in_ga(x1)
app67_out_ga(x1, x2)  =  app67_out_ga(x2)
U19_ga(x1, x2, x3, x4)  =  U19_ga(x4)
U20_ga(x1, x2, x3, x4)  =  U20_ga(x4)
PERM1_IN_GA(x1, x2)  =  PERM1_IN_GA(x1)
U12_GA(x1, x2, x3, x4, x5)  =  U12_GA(x5)
APP10_IN_AAAG(x1, x2, x3, x4)  =  APP10_IN_AAAG(x4)
U1_AAAG(x1, x2, x3, x4, x5, x6)  =  U1_AAAG(x1, x6)
U13_GA(x1, x2, x3, x4, x5)  =  U13_GA(x1, x5)
U14_GA(x1, x2, x3, x4, x5)  =  U14_GA(x5)
APP20_IN_GGGA(x1, x2, x3, x4)  =  APP20_IN_GGGA(x1, x2, x3)
U11_GGGA(x1, x2, x3, x4, x5)  =  U11_GGGA(x1, x5)
APP25_IN_GGA(x1, x2, x3)  =  APP25_IN_GGA(x1, x2)
U2_GGA(x1, x2, x3, x4, x5)  =  U2_GGA(x1, x5)
U15_GA(x1, x2, x3, x4, x5)  =  U15_GA(x1, x5)
U16_GA(x1, x2, x3, x4, x5)  =  U16_GA(x5)
U17_GA(x1, x2, x3, x4, x5)  =  U17_GA(x5)
PERM21_IN_GA(x1, x2)  =  PERM21_IN_GA(x1)
U4_GA(x1, x2, x3, x4)  =  U4_GA(x4)
APP40_IN_AAAG(x1, x2, x3, x4)  =  APP40_IN_AAAG(x4)
U3_AAAG(x1, x2, x3, x4, x5, x6)  =  U3_AAAG(x1, x6)
U5_GA(x1, x2, x3, x4)  =  U5_GA(x4)
U6_GA(x1, x2, x3, x4)  =  U6_GA(x4)
APP50_IN_GGA(x1, x2, x3)  =  APP50_IN_GGA(x1, x2)
U10_GGA(x1, x2, x3, x4, x5)  =  U10_GGA(x1, x5)
U7_GA(x1, x2, x3, x4)  =  U7_GA(x4)
U8_GA(x1, x2, x3, x4)  =  U8_GA(x4)
U9_GA(x1, x2, x3, x4)  =  U9_GA(x4)
U18_GA(x1, x2, x3, x4)  =  U18_GA(x4)
APP67_IN_GA(x1, x2)  =  APP67_IN_GA(x1)
U19_GA(x1, x2, x3, x4)  =  U19_GA(x4)
U20_GA(x1, x2, x3, x4)  =  U20_GA(x4)

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

(7) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 28 less nodes.

(8) Complex Obligation (AND)

(9) Obligation:

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

APP50_IN_GGA(.(T157, T160), T161, .(T157, X349)) → APP50_IN_GGA(T160, T161, X349)

The TRS R consists of the following rules:

perm1_in_ga(.(X45, T20), .(T21, T22)) → U12_ga(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
app10_in_aaag(.(X98, X99), T40, X100, .(X98, T39)) → U1_aaag(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
app10_in_aaag([], T45, X117, .(T45, X117)) → app10_out_aaag([], T45, X117, .(T45, X117))
U1_aaag(X98, X99, T40, X100, T39, app10_out_aaag(X99, T40, X100, T39)) → app10_out_aaag(.(X98, X99), T40, X100, .(X98, T39))
U12_ga(X45, T20, T21, T22, app10_out_aaag(X46, T21, X47, T20)) → perm1_out_ga(.(X45, T20), .(T21, T22))
perm1_in_ga(.(X45, T20), .(T21, T27)) → U13_ga(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_ga(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_ga(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
app20_in_ggga(X169, T66, T67, .(X169, X170)) → U11_ggga(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
app25_in_gga(.(T83, T84), T85, .(T83, X200)) → U2_gga(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
app25_in_gga([], T91, T91) → app25_out_gga([], T91, T91)
U2_gga(T83, T84, T85, X200, app25_out_gga(T84, T85, X200)) → app25_out_gga(.(T83, T84), T85, .(T83, X200))
U11_ggga(X169, T66, T67, X170, app25_out_gga(T66, T67, X170)) → app20_out_ggga(X169, T66, T67, .(X169, X170))
U14_ga(X45, T20, T21, T27, app20_out_ggga(X45, T25, T26, X9)) → perm1_out_ga(.(X45, T20), .(T21, T27))
perm1_in_ga(.(T48, T20), .(T21, T27)) → U15_ga(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_ga(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_ga(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U16_ga(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_ga(T48, T20, T21, T27, perm21_in_ga(T49, T27))
perm21_in_ga(T110, .(T111, T112)) → U4_ga(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U4_ga(T110, T111, T112, app40_out_aaag(X242, T111, X243, T110)) → perm21_out_ga(T110, .(T111, T112))
perm21_in_ga(T110, .(T111, T117)) → U5_ga(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_ga(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_ga(T110, T111, T117, app50_in_gga(T115, T116, X244))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))
U6_ga(T110, T111, T117, app50_out_gga(T115, T116, X244)) → perm21_out_ga(T110, .(T111, T117))
perm21_in_ga(T110, .(T111, T141)) → U7_ga(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_ga(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_ga(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_ga(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_ga(T110, T111, T141, perm21_in_ga(T140, T141))
perm21_in_ga([], []) → perm21_out_ga([], [])
U9_ga(T110, T111, T141, perm21_out_ga(T140, T141)) → perm21_out_ga(T110, .(T111, T141))
U17_ga(T48, T20, T21, T27, perm21_out_ga(T49, T27)) → perm1_out_ga(.(T48, T20), .(T21, T27))
perm1_in_ga(.(T175, X378), .(T175, T176)) → U18_ga(T175, X378, T176, app67_in_ga(X378, X9))
app67_in_ga(X408, X408) → app67_out_ga(X408, X408)
U18_ga(T175, X378, T176, app67_out_ga(X378, X9)) → perm1_out_ga(.(T175, X378), .(T175, T176))
perm1_in_ga(.(T175, T179), .(T175, T176)) → U19_ga(T175, T179, T176, app67_in_ga(T179, T180))
U19_ga(T175, T179, T176, app67_out_ga(T179, T180)) → U20_ga(T175, T179, T176, perm21_in_ga(T180, T176))
U20_ga(T175, T179, T176, perm21_out_ga(T180, T176)) → perm1_out_ga(.(T175, T179), .(T175, T176))
perm1_in_ga([], []) → perm1_out_ga([], [])

The argument filtering Pi contains the following mapping:
perm1_in_ga(x1, x2)  =  perm1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
U12_ga(x1, x2, x3, x4, x5)  =  U12_ga(x5)
app10_in_aaag(x1, x2, x3, x4)  =  app10_in_aaag(x4)
U1_aaag(x1, x2, x3, x4, x5, x6)  =  U1_aaag(x1, x6)
app10_out_aaag(x1, x2, x3, x4)  =  app10_out_aaag(x1, x2, x3)
perm1_out_ga(x1, x2)  =  perm1_out_ga
U13_ga(x1, x2, x3, x4, x5)  =  U13_ga(x1, x5)
U14_ga(x1, x2, x3, x4, x5)  =  U14_ga(x5)
app20_in_ggga(x1, x2, x3, x4)  =  app20_in_ggga(x1, x2, x3)
U11_ggga(x1, x2, x3, x4, x5)  =  U11_ggga(x1, x5)
app25_in_gga(x1, x2, x3)  =  app25_in_gga(x1, x2)
U2_gga(x1, x2, x3, x4, x5)  =  U2_gga(x1, x5)
[]  =  []
app25_out_gga(x1, x2, x3)  =  app25_out_gga(x3)
app20_out_ggga(x1, x2, x3, x4)  =  app20_out_ggga(x4)
U15_ga(x1, x2, x3, x4, x5)  =  U15_ga(x1, x5)
U16_ga(x1, x2, x3, x4, x5)  =  U16_ga(x5)
U17_ga(x1, x2, x3, x4, x5)  =  U17_ga(x5)
perm21_in_ga(x1, x2)  =  perm21_in_ga(x1)
U4_ga(x1, x2, x3, x4)  =  U4_ga(x4)
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
perm21_out_ga(x1, x2)  =  perm21_out_ga
U5_ga(x1, x2, x3, x4)  =  U5_ga(x4)
U6_ga(x1, x2, x3, x4)  =  U6_ga(x4)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
U7_ga(x1, x2, x3, x4)  =  U7_ga(x4)
U8_ga(x1, x2, x3, x4)  =  U8_ga(x4)
U9_ga(x1, x2, x3, x4)  =  U9_ga(x4)
U18_ga(x1, x2, x3, x4)  =  U18_ga(x4)
app67_in_ga(x1, x2)  =  app67_in_ga(x1)
app67_out_ga(x1, x2)  =  app67_out_ga(x2)
U19_ga(x1, x2, x3, x4)  =  U19_ga(x4)
U20_ga(x1, x2, x3, x4)  =  U20_ga(x4)
APP50_IN_GGA(x1, x2, x3)  =  APP50_IN_GGA(x1, x2)

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

(10) UsableRulesProof (EQUIVALENT transformation)

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

(11) Obligation:

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

APP50_IN_GGA(.(T157, T160), T161, .(T157, X349)) → APP50_IN_GGA(T160, T161, X349)

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

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

(12) PiDPToQDPProof (SOUND transformation)

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

(13) Obligation:

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

APP50_IN_GGA(.(T157, T160), T161) → APP50_IN_GGA(T160, T161)

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

(14) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • APP50_IN_GGA(.(T157, T160), T161) → APP50_IN_GGA(T160, T161)
    The graph contains the following edges 1 > 1, 2 >= 2

(15) YES

(16) Obligation:

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

APP40_IN_AAAG(.(X294, X295), T131, X296, .(X294, T130)) → APP40_IN_AAAG(X295, T131, X296, T130)

The TRS R consists of the following rules:

perm1_in_ga(.(X45, T20), .(T21, T22)) → U12_ga(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
app10_in_aaag(.(X98, X99), T40, X100, .(X98, T39)) → U1_aaag(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
app10_in_aaag([], T45, X117, .(T45, X117)) → app10_out_aaag([], T45, X117, .(T45, X117))
U1_aaag(X98, X99, T40, X100, T39, app10_out_aaag(X99, T40, X100, T39)) → app10_out_aaag(.(X98, X99), T40, X100, .(X98, T39))
U12_ga(X45, T20, T21, T22, app10_out_aaag(X46, T21, X47, T20)) → perm1_out_ga(.(X45, T20), .(T21, T22))
perm1_in_ga(.(X45, T20), .(T21, T27)) → U13_ga(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_ga(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_ga(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
app20_in_ggga(X169, T66, T67, .(X169, X170)) → U11_ggga(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
app25_in_gga(.(T83, T84), T85, .(T83, X200)) → U2_gga(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
app25_in_gga([], T91, T91) → app25_out_gga([], T91, T91)
U2_gga(T83, T84, T85, X200, app25_out_gga(T84, T85, X200)) → app25_out_gga(.(T83, T84), T85, .(T83, X200))
U11_ggga(X169, T66, T67, X170, app25_out_gga(T66, T67, X170)) → app20_out_ggga(X169, T66, T67, .(X169, X170))
U14_ga(X45, T20, T21, T27, app20_out_ggga(X45, T25, T26, X9)) → perm1_out_ga(.(X45, T20), .(T21, T27))
perm1_in_ga(.(T48, T20), .(T21, T27)) → U15_ga(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_ga(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_ga(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U16_ga(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_ga(T48, T20, T21, T27, perm21_in_ga(T49, T27))
perm21_in_ga(T110, .(T111, T112)) → U4_ga(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U4_ga(T110, T111, T112, app40_out_aaag(X242, T111, X243, T110)) → perm21_out_ga(T110, .(T111, T112))
perm21_in_ga(T110, .(T111, T117)) → U5_ga(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_ga(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_ga(T110, T111, T117, app50_in_gga(T115, T116, X244))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))
U6_ga(T110, T111, T117, app50_out_gga(T115, T116, X244)) → perm21_out_ga(T110, .(T111, T117))
perm21_in_ga(T110, .(T111, T141)) → U7_ga(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_ga(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_ga(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_ga(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_ga(T110, T111, T141, perm21_in_ga(T140, T141))
perm21_in_ga([], []) → perm21_out_ga([], [])
U9_ga(T110, T111, T141, perm21_out_ga(T140, T141)) → perm21_out_ga(T110, .(T111, T141))
U17_ga(T48, T20, T21, T27, perm21_out_ga(T49, T27)) → perm1_out_ga(.(T48, T20), .(T21, T27))
perm1_in_ga(.(T175, X378), .(T175, T176)) → U18_ga(T175, X378, T176, app67_in_ga(X378, X9))
app67_in_ga(X408, X408) → app67_out_ga(X408, X408)
U18_ga(T175, X378, T176, app67_out_ga(X378, X9)) → perm1_out_ga(.(T175, X378), .(T175, T176))
perm1_in_ga(.(T175, T179), .(T175, T176)) → U19_ga(T175, T179, T176, app67_in_ga(T179, T180))
U19_ga(T175, T179, T176, app67_out_ga(T179, T180)) → U20_ga(T175, T179, T176, perm21_in_ga(T180, T176))
U20_ga(T175, T179, T176, perm21_out_ga(T180, T176)) → perm1_out_ga(.(T175, T179), .(T175, T176))
perm1_in_ga([], []) → perm1_out_ga([], [])

The argument filtering Pi contains the following mapping:
perm1_in_ga(x1, x2)  =  perm1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
U12_ga(x1, x2, x3, x4, x5)  =  U12_ga(x5)
app10_in_aaag(x1, x2, x3, x4)  =  app10_in_aaag(x4)
U1_aaag(x1, x2, x3, x4, x5, x6)  =  U1_aaag(x1, x6)
app10_out_aaag(x1, x2, x3, x4)  =  app10_out_aaag(x1, x2, x3)
perm1_out_ga(x1, x2)  =  perm1_out_ga
U13_ga(x1, x2, x3, x4, x5)  =  U13_ga(x1, x5)
U14_ga(x1, x2, x3, x4, x5)  =  U14_ga(x5)
app20_in_ggga(x1, x2, x3, x4)  =  app20_in_ggga(x1, x2, x3)
U11_ggga(x1, x2, x3, x4, x5)  =  U11_ggga(x1, x5)
app25_in_gga(x1, x2, x3)  =  app25_in_gga(x1, x2)
U2_gga(x1, x2, x3, x4, x5)  =  U2_gga(x1, x5)
[]  =  []
app25_out_gga(x1, x2, x3)  =  app25_out_gga(x3)
app20_out_ggga(x1, x2, x3, x4)  =  app20_out_ggga(x4)
U15_ga(x1, x2, x3, x4, x5)  =  U15_ga(x1, x5)
U16_ga(x1, x2, x3, x4, x5)  =  U16_ga(x5)
U17_ga(x1, x2, x3, x4, x5)  =  U17_ga(x5)
perm21_in_ga(x1, x2)  =  perm21_in_ga(x1)
U4_ga(x1, x2, x3, x4)  =  U4_ga(x4)
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
perm21_out_ga(x1, x2)  =  perm21_out_ga
U5_ga(x1, x2, x3, x4)  =  U5_ga(x4)
U6_ga(x1, x2, x3, x4)  =  U6_ga(x4)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
U7_ga(x1, x2, x3, x4)  =  U7_ga(x4)
U8_ga(x1, x2, x3, x4)  =  U8_ga(x4)
U9_ga(x1, x2, x3, x4)  =  U9_ga(x4)
U18_ga(x1, x2, x3, x4)  =  U18_ga(x4)
app67_in_ga(x1, x2)  =  app67_in_ga(x1)
app67_out_ga(x1, x2)  =  app67_out_ga(x2)
U19_ga(x1, x2, x3, x4)  =  U19_ga(x4)
U20_ga(x1, x2, x3, x4)  =  U20_ga(x4)
APP40_IN_AAAG(x1, x2, x3, x4)  =  APP40_IN_AAAG(x4)

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

(17) UsableRulesProof (EQUIVALENT transformation)

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

(18) Obligation:

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

APP40_IN_AAAG(.(X294, X295), T131, X296, .(X294, T130)) → APP40_IN_AAAG(X295, T131, X296, T130)

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

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

(19) PiDPToQDPProof (SOUND transformation)

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

(20) Obligation:

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

APP40_IN_AAAG(.(X294, T130)) → APP40_IN_AAAG(T130)

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

(21) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • APP40_IN_AAAG(.(X294, T130)) → APP40_IN_AAAG(T130)
    The graph contains the following edges 1 > 1

(22) YES

(23) Obligation:

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

PERM21_IN_GA(T110, .(T111, T141)) → U7_GA(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_GA(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_GA(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_GA(T110, T111, T141, app50_out_gga(T115, T116, T140)) → PERM21_IN_GA(T140, T141)

The TRS R consists of the following rules:

perm1_in_ga(.(X45, T20), .(T21, T22)) → U12_ga(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
app10_in_aaag(.(X98, X99), T40, X100, .(X98, T39)) → U1_aaag(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
app10_in_aaag([], T45, X117, .(T45, X117)) → app10_out_aaag([], T45, X117, .(T45, X117))
U1_aaag(X98, X99, T40, X100, T39, app10_out_aaag(X99, T40, X100, T39)) → app10_out_aaag(.(X98, X99), T40, X100, .(X98, T39))
U12_ga(X45, T20, T21, T22, app10_out_aaag(X46, T21, X47, T20)) → perm1_out_ga(.(X45, T20), .(T21, T22))
perm1_in_ga(.(X45, T20), .(T21, T27)) → U13_ga(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_ga(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_ga(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
app20_in_ggga(X169, T66, T67, .(X169, X170)) → U11_ggga(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
app25_in_gga(.(T83, T84), T85, .(T83, X200)) → U2_gga(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
app25_in_gga([], T91, T91) → app25_out_gga([], T91, T91)
U2_gga(T83, T84, T85, X200, app25_out_gga(T84, T85, X200)) → app25_out_gga(.(T83, T84), T85, .(T83, X200))
U11_ggga(X169, T66, T67, X170, app25_out_gga(T66, T67, X170)) → app20_out_ggga(X169, T66, T67, .(X169, X170))
U14_ga(X45, T20, T21, T27, app20_out_ggga(X45, T25, T26, X9)) → perm1_out_ga(.(X45, T20), .(T21, T27))
perm1_in_ga(.(T48, T20), .(T21, T27)) → U15_ga(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_ga(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_ga(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U16_ga(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_ga(T48, T20, T21, T27, perm21_in_ga(T49, T27))
perm21_in_ga(T110, .(T111, T112)) → U4_ga(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U4_ga(T110, T111, T112, app40_out_aaag(X242, T111, X243, T110)) → perm21_out_ga(T110, .(T111, T112))
perm21_in_ga(T110, .(T111, T117)) → U5_ga(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_ga(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_ga(T110, T111, T117, app50_in_gga(T115, T116, X244))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))
U6_ga(T110, T111, T117, app50_out_gga(T115, T116, X244)) → perm21_out_ga(T110, .(T111, T117))
perm21_in_ga(T110, .(T111, T141)) → U7_ga(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_ga(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_ga(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_ga(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_ga(T110, T111, T141, perm21_in_ga(T140, T141))
perm21_in_ga([], []) → perm21_out_ga([], [])
U9_ga(T110, T111, T141, perm21_out_ga(T140, T141)) → perm21_out_ga(T110, .(T111, T141))
U17_ga(T48, T20, T21, T27, perm21_out_ga(T49, T27)) → perm1_out_ga(.(T48, T20), .(T21, T27))
perm1_in_ga(.(T175, X378), .(T175, T176)) → U18_ga(T175, X378, T176, app67_in_ga(X378, X9))
app67_in_ga(X408, X408) → app67_out_ga(X408, X408)
U18_ga(T175, X378, T176, app67_out_ga(X378, X9)) → perm1_out_ga(.(T175, X378), .(T175, T176))
perm1_in_ga(.(T175, T179), .(T175, T176)) → U19_ga(T175, T179, T176, app67_in_ga(T179, T180))
U19_ga(T175, T179, T176, app67_out_ga(T179, T180)) → U20_ga(T175, T179, T176, perm21_in_ga(T180, T176))
U20_ga(T175, T179, T176, perm21_out_ga(T180, T176)) → perm1_out_ga(.(T175, T179), .(T175, T176))
perm1_in_ga([], []) → perm1_out_ga([], [])

The argument filtering Pi contains the following mapping:
perm1_in_ga(x1, x2)  =  perm1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
U12_ga(x1, x2, x3, x4, x5)  =  U12_ga(x5)
app10_in_aaag(x1, x2, x3, x4)  =  app10_in_aaag(x4)
U1_aaag(x1, x2, x3, x4, x5, x6)  =  U1_aaag(x1, x6)
app10_out_aaag(x1, x2, x3, x4)  =  app10_out_aaag(x1, x2, x3)
perm1_out_ga(x1, x2)  =  perm1_out_ga
U13_ga(x1, x2, x3, x4, x5)  =  U13_ga(x1, x5)
U14_ga(x1, x2, x3, x4, x5)  =  U14_ga(x5)
app20_in_ggga(x1, x2, x3, x4)  =  app20_in_ggga(x1, x2, x3)
U11_ggga(x1, x2, x3, x4, x5)  =  U11_ggga(x1, x5)
app25_in_gga(x1, x2, x3)  =  app25_in_gga(x1, x2)
U2_gga(x1, x2, x3, x4, x5)  =  U2_gga(x1, x5)
[]  =  []
app25_out_gga(x1, x2, x3)  =  app25_out_gga(x3)
app20_out_ggga(x1, x2, x3, x4)  =  app20_out_ggga(x4)
U15_ga(x1, x2, x3, x4, x5)  =  U15_ga(x1, x5)
U16_ga(x1, x2, x3, x4, x5)  =  U16_ga(x5)
U17_ga(x1, x2, x3, x4, x5)  =  U17_ga(x5)
perm21_in_ga(x1, x2)  =  perm21_in_ga(x1)
U4_ga(x1, x2, x3, x4)  =  U4_ga(x4)
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
perm21_out_ga(x1, x2)  =  perm21_out_ga
U5_ga(x1, x2, x3, x4)  =  U5_ga(x4)
U6_ga(x1, x2, x3, x4)  =  U6_ga(x4)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
U7_ga(x1, x2, x3, x4)  =  U7_ga(x4)
U8_ga(x1, x2, x3, x4)  =  U8_ga(x4)
U9_ga(x1, x2, x3, x4)  =  U9_ga(x4)
U18_ga(x1, x2, x3, x4)  =  U18_ga(x4)
app67_in_ga(x1, x2)  =  app67_in_ga(x1)
app67_out_ga(x1, x2)  =  app67_out_ga(x2)
U19_ga(x1, x2, x3, x4)  =  U19_ga(x4)
U20_ga(x1, x2, x3, x4)  =  U20_ga(x4)
PERM21_IN_GA(x1, x2)  =  PERM21_IN_GA(x1)
U7_GA(x1, x2, x3, x4)  =  U7_GA(x4)
U8_GA(x1, x2, x3, x4)  =  U8_GA(x4)

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

(24) UsableRulesProof (EQUIVALENT transformation)

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

(25) Obligation:

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

PERM21_IN_GA(T110, .(T111, T141)) → U7_GA(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_GA(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_GA(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_GA(T110, T111, T141, app50_out_gga(T115, T116, T140)) → PERM21_IN_GA(T140, T141)

The TRS R consists of the following rules:

app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))

The argument filtering Pi contains the following mapping:
.(x1, x2)  =  .(x1, x2)
[]  =  []
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
PERM21_IN_GA(x1, x2)  =  PERM21_IN_GA(x1)
U7_GA(x1, x2, x3, x4)  =  U7_GA(x4)
U8_GA(x1, x2, x3, x4)  =  U8_GA(x4)

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

(26) PiDPToQDPProof (SOUND transformation)

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

(27) Obligation:

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

PERM21_IN_GA(T110) → U7_GA(app40_in_aaag(T110))
U7_GA(app40_out_aaag(T115, T111, T116)) → U8_GA(app50_in_gga(T115, T116))
U8_GA(app50_out_gga(T140)) → PERM21_IN_GA(T140)

The TRS R consists of the following rules:

app40_in_aaag(.(X294, T130)) → U3_aaag(X294, app40_in_aaag(T130))
app40_in_aaag(.(T136, X313)) → app40_out_aaag([], T136, X313)
app50_in_gga(.(T157, T160), T161) → U10_gga(T157, app50_in_gga(T160, T161))
app50_in_gga([], T167) → app50_out_gga(T167)
U3_aaag(X294, app40_out_aaag(X295, T131, X296)) → app40_out_aaag(.(X294, X295), T131, X296)
U10_gga(T157, app50_out_gga(X349)) → app50_out_gga(.(T157, X349))

The set Q consists of the following terms:

app40_in_aaag(x0)
app50_in_gga(x0, x1)
U3_aaag(x0, x1)
U10_gga(x0, x1)

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

(28) MRRProof (EQUIVALENT transformation)

By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
Strictly oriented dependency pairs:

PERM21_IN_GA(T110) → U7_GA(app40_in_aaag(T110))
U7_GA(app40_out_aaag(T115, T111, T116)) → U8_GA(app50_in_gga(T115, T116))
U8_GA(app50_out_gga(T140)) → PERM21_IN_GA(T140)

Strictly oriented rules of the TRS R:

app40_in_aaag(.(T136, X313)) → app40_out_aaag([], T136, X313)
app50_in_gga([], T167) → app50_out_gga(T167)

Used ordering: Polynomial interpretation [POLO]:

POL(.(x1, x2)) = 5 + x1 + x2   
POL(PERM21_IN_GA(x1)) = 1 + x1   
POL(U10_gga(x1, x2)) = 5 + x1 + x2   
POL(U3_aaag(x1, x2)) = 5 + x1 + x2   
POL(U7_GA(x1)) = x1   
POL(U8_GA(x1)) = x1   
POL([]) = 0   
POL(app40_in_aaag(x1)) = x1   
POL(app40_out_aaag(x1, x2, x3)) = 4 + x1 + x2 + x3   
POL(app50_in_gga(x1, x2)) = 3 + x1 + x2   
POL(app50_out_gga(x1)) = 2 + x1   

(29) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

app40_in_aaag(.(X294, T130)) → U3_aaag(X294, app40_in_aaag(T130))
app50_in_gga(.(T157, T160), T161) → U10_gga(T157, app50_in_gga(T160, T161))
U3_aaag(X294, app40_out_aaag(X295, T131, X296)) → app40_out_aaag(.(X294, X295), T131, X296)
U10_gga(T157, app50_out_gga(X349)) → app50_out_gga(.(T157, X349))

The set Q consists of the following terms:

app40_in_aaag(x0)
app50_in_gga(x0, x1)
U3_aaag(x0, x1)
U10_gga(x0, x1)

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

(30) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(31) YES

(32) Obligation:

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

APP25_IN_GGA(.(T83, T84), T85, .(T83, X200)) → APP25_IN_GGA(T84, T85, X200)

The TRS R consists of the following rules:

perm1_in_ga(.(X45, T20), .(T21, T22)) → U12_ga(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
app10_in_aaag(.(X98, X99), T40, X100, .(X98, T39)) → U1_aaag(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
app10_in_aaag([], T45, X117, .(T45, X117)) → app10_out_aaag([], T45, X117, .(T45, X117))
U1_aaag(X98, X99, T40, X100, T39, app10_out_aaag(X99, T40, X100, T39)) → app10_out_aaag(.(X98, X99), T40, X100, .(X98, T39))
U12_ga(X45, T20, T21, T22, app10_out_aaag(X46, T21, X47, T20)) → perm1_out_ga(.(X45, T20), .(T21, T22))
perm1_in_ga(.(X45, T20), .(T21, T27)) → U13_ga(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_ga(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_ga(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
app20_in_ggga(X169, T66, T67, .(X169, X170)) → U11_ggga(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
app25_in_gga(.(T83, T84), T85, .(T83, X200)) → U2_gga(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
app25_in_gga([], T91, T91) → app25_out_gga([], T91, T91)
U2_gga(T83, T84, T85, X200, app25_out_gga(T84, T85, X200)) → app25_out_gga(.(T83, T84), T85, .(T83, X200))
U11_ggga(X169, T66, T67, X170, app25_out_gga(T66, T67, X170)) → app20_out_ggga(X169, T66, T67, .(X169, X170))
U14_ga(X45, T20, T21, T27, app20_out_ggga(X45, T25, T26, X9)) → perm1_out_ga(.(X45, T20), .(T21, T27))
perm1_in_ga(.(T48, T20), .(T21, T27)) → U15_ga(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_ga(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_ga(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U16_ga(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_ga(T48, T20, T21, T27, perm21_in_ga(T49, T27))
perm21_in_ga(T110, .(T111, T112)) → U4_ga(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U4_ga(T110, T111, T112, app40_out_aaag(X242, T111, X243, T110)) → perm21_out_ga(T110, .(T111, T112))
perm21_in_ga(T110, .(T111, T117)) → U5_ga(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_ga(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_ga(T110, T111, T117, app50_in_gga(T115, T116, X244))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))
U6_ga(T110, T111, T117, app50_out_gga(T115, T116, X244)) → perm21_out_ga(T110, .(T111, T117))
perm21_in_ga(T110, .(T111, T141)) → U7_ga(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_ga(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_ga(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_ga(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_ga(T110, T111, T141, perm21_in_ga(T140, T141))
perm21_in_ga([], []) → perm21_out_ga([], [])
U9_ga(T110, T111, T141, perm21_out_ga(T140, T141)) → perm21_out_ga(T110, .(T111, T141))
U17_ga(T48, T20, T21, T27, perm21_out_ga(T49, T27)) → perm1_out_ga(.(T48, T20), .(T21, T27))
perm1_in_ga(.(T175, X378), .(T175, T176)) → U18_ga(T175, X378, T176, app67_in_ga(X378, X9))
app67_in_ga(X408, X408) → app67_out_ga(X408, X408)
U18_ga(T175, X378, T176, app67_out_ga(X378, X9)) → perm1_out_ga(.(T175, X378), .(T175, T176))
perm1_in_ga(.(T175, T179), .(T175, T176)) → U19_ga(T175, T179, T176, app67_in_ga(T179, T180))
U19_ga(T175, T179, T176, app67_out_ga(T179, T180)) → U20_ga(T175, T179, T176, perm21_in_ga(T180, T176))
U20_ga(T175, T179, T176, perm21_out_ga(T180, T176)) → perm1_out_ga(.(T175, T179), .(T175, T176))
perm1_in_ga([], []) → perm1_out_ga([], [])

The argument filtering Pi contains the following mapping:
perm1_in_ga(x1, x2)  =  perm1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
U12_ga(x1, x2, x3, x4, x5)  =  U12_ga(x5)
app10_in_aaag(x1, x2, x3, x4)  =  app10_in_aaag(x4)
U1_aaag(x1, x2, x3, x4, x5, x6)  =  U1_aaag(x1, x6)
app10_out_aaag(x1, x2, x3, x4)  =  app10_out_aaag(x1, x2, x3)
perm1_out_ga(x1, x2)  =  perm1_out_ga
U13_ga(x1, x2, x3, x4, x5)  =  U13_ga(x1, x5)
U14_ga(x1, x2, x3, x4, x5)  =  U14_ga(x5)
app20_in_ggga(x1, x2, x3, x4)  =  app20_in_ggga(x1, x2, x3)
U11_ggga(x1, x2, x3, x4, x5)  =  U11_ggga(x1, x5)
app25_in_gga(x1, x2, x3)  =  app25_in_gga(x1, x2)
U2_gga(x1, x2, x3, x4, x5)  =  U2_gga(x1, x5)
[]  =  []
app25_out_gga(x1, x2, x3)  =  app25_out_gga(x3)
app20_out_ggga(x1, x2, x3, x4)  =  app20_out_ggga(x4)
U15_ga(x1, x2, x3, x4, x5)  =  U15_ga(x1, x5)
U16_ga(x1, x2, x3, x4, x5)  =  U16_ga(x5)
U17_ga(x1, x2, x3, x4, x5)  =  U17_ga(x5)
perm21_in_ga(x1, x2)  =  perm21_in_ga(x1)
U4_ga(x1, x2, x3, x4)  =  U4_ga(x4)
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
perm21_out_ga(x1, x2)  =  perm21_out_ga
U5_ga(x1, x2, x3, x4)  =  U5_ga(x4)
U6_ga(x1, x2, x3, x4)  =  U6_ga(x4)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
U7_ga(x1, x2, x3, x4)  =  U7_ga(x4)
U8_ga(x1, x2, x3, x4)  =  U8_ga(x4)
U9_ga(x1, x2, x3, x4)  =  U9_ga(x4)
U18_ga(x1, x2, x3, x4)  =  U18_ga(x4)
app67_in_ga(x1, x2)  =  app67_in_ga(x1)
app67_out_ga(x1, x2)  =  app67_out_ga(x2)
U19_ga(x1, x2, x3, x4)  =  U19_ga(x4)
U20_ga(x1, x2, x3, x4)  =  U20_ga(x4)
APP25_IN_GGA(x1, x2, x3)  =  APP25_IN_GGA(x1, x2)

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

(33) UsableRulesProof (EQUIVALENT transformation)

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

(34) Obligation:

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

APP25_IN_GGA(.(T83, T84), T85, .(T83, X200)) → APP25_IN_GGA(T84, T85, X200)

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

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

(35) PiDPToQDPProof (SOUND transformation)

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

(36) Obligation:

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

APP25_IN_GGA(.(T83, T84), T85) → APP25_IN_GGA(T84, T85)

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

(37) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • APP25_IN_GGA(.(T83, T84), T85) → APP25_IN_GGA(T84, T85)
    The graph contains the following edges 1 > 1, 2 >= 2

(38) YES

(39) Obligation:

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

APP10_IN_AAAG(.(X98, X99), T40, X100, .(X98, T39)) → APP10_IN_AAAG(X99, T40, X100, T39)

The TRS R consists of the following rules:

perm1_in_ga(.(X45, T20), .(T21, T22)) → U12_ga(X45, T20, T21, T22, app10_in_aaag(X46, T21, X47, T20))
app10_in_aaag(.(X98, X99), T40, X100, .(X98, T39)) → U1_aaag(X98, X99, T40, X100, T39, app10_in_aaag(X99, T40, X100, T39))
app10_in_aaag([], T45, X117, .(T45, X117)) → app10_out_aaag([], T45, X117, .(T45, X117))
U1_aaag(X98, X99, T40, X100, T39, app10_out_aaag(X99, T40, X100, T39)) → app10_out_aaag(.(X98, X99), T40, X100, .(X98, T39))
U12_ga(X45, T20, T21, T22, app10_out_aaag(X46, T21, X47, T20)) → perm1_out_ga(.(X45, T20), .(T21, T22))
perm1_in_ga(.(X45, T20), .(T21, T27)) → U13_ga(X45, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U13_ga(X45, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U14_ga(X45, T20, T21, T27, app20_in_ggga(X45, T25, T26, X9))
app20_in_ggga(X169, T66, T67, .(X169, X170)) → U11_ggga(X169, T66, T67, X170, app25_in_gga(T66, T67, X170))
app25_in_gga(.(T83, T84), T85, .(T83, X200)) → U2_gga(T83, T84, T85, X200, app25_in_gga(T84, T85, X200))
app25_in_gga([], T91, T91) → app25_out_gga([], T91, T91)
U2_gga(T83, T84, T85, X200, app25_out_gga(T84, T85, X200)) → app25_out_gga(.(T83, T84), T85, .(T83, X200))
U11_ggga(X169, T66, T67, X170, app25_out_gga(T66, T67, X170)) → app20_out_ggga(X169, T66, T67, .(X169, X170))
U14_ga(X45, T20, T21, T27, app20_out_ggga(X45, T25, T26, X9)) → perm1_out_ga(.(X45, T20), .(T21, T27))
perm1_in_ga(.(T48, T20), .(T21, T27)) → U15_ga(T48, T20, T21, T27, app10_in_aaag(T25, T21, T26, T20))
U15_ga(T48, T20, T21, T27, app10_out_aaag(T25, T21, T26, T20)) → U16_ga(T48, T20, T21, T27, app20_in_ggga(T48, T25, T26, T49))
U16_ga(T48, T20, T21, T27, app20_out_ggga(T48, T25, T26, T49)) → U17_ga(T48, T20, T21, T27, perm21_in_ga(T49, T27))
perm21_in_ga(T110, .(T111, T112)) → U4_ga(T110, T111, T112, app40_in_aaag(X242, T111, X243, T110))
app40_in_aaag(.(X294, X295), T131, X296, .(X294, T130)) → U3_aaag(X294, X295, T131, X296, T130, app40_in_aaag(X295, T131, X296, T130))
app40_in_aaag([], T136, X313, .(T136, X313)) → app40_out_aaag([], T136, X313, .(T136, X313))
U3_aaag(X294, X295, T131, X296, T130, app40_out_aaag(X295, T131, X296, T130)) → app40_out_aaag(.(X294, X295), T131, X296, .(X294, T130))
U4_ga(T110, T111, T112, app40_out_aaag(X242, T111, X243, T110)) → perm21_out_ga(T110, .(T111, T112))
perm21_in_ga(T110, .(T111, T117)) → U5_ga(T110, T111, T117, app40_in_aaag(T115, T111, T116, T110))
U5_ga(T110, T111, T117, app40_out_aaag(T115, T111, T116, T110)) → U6_ga(T110, T111, T117, app50_in_gga(T115, T116, X244))
app50_in_gga(.(T157, T160), T161, .(T157, X349)) → U10_gga(T157, T160, T161, X349, app50_in_gga(T160, T161, X349))
app50_in_gga([], T167, T167) → app50_out_gga([], T167, T167)
U10_gga(T157, T160, T161, X349, app50_out_gga(T160, T161, X349)) → app50_out_gga(.(T157, T160), T161, .(T157, X349))
U6_ga(T110, T111, T117, app50_out_gga(T115, T116, X244)) → perm21_out_ga(T110, .(T111, T117))
perm21_in_ga(T110, .(T111, T141)) → U7_ga(T110, T111, T141, app40_in_aaag(T115, T111, T116, T110))
U7_ga(T110, T111, T141, app40_out_aaag(T115, T111, T116, T110)) → U8_ga(T110, T111, T141, app50_in_gga(T115, T116, T140))
U8_ga(T110, T111, T141, app50_out_gga(T115, T116, T140)) → U9_ga(T110, T111, T141, perm21_in_ga(T140, T141))
perm21_in_ga([], []) → perm21_out_ga([], [])
U9_ga(T110, T111, T141, perm21_out_ga(T140, T141)) → perm21_out_ga(T110, .(T111, T141))
U17_ga(T48, T20, T21, T27, perm21_out_ga(T49, T27)) → perm1_out_ga(.(T48, T20), .(T21, T27))
perm1_in_ga(.(T175, X378), .(T175, T176)) → U18_ga(T175, X378, T176, app67_in_ga(X378, X9))
app67_in_ga(X408, X408) → app67_out_ga(X408, X408)
U18_ga(T175, X378, T176, app67_out_ga(X378, X9)) → perm1_out_ga(.(T175, X378), .(T175, T176))
perm1_in_ga(.(T175, T179), .(T175, T176)) → U19_ga(T175, T179, T176, app67_in_ga(T179, T180))
U19_ga(T175, T179, T176, app67_out_ga(T179, T180)) → U20_ga(T175, T179, T176, perm21_in_ga(T180, T176))
U20_ga(T175, T179, T176, perm21_out_ga(T180, T176)) → perm1_out_ga(.(T175, T179), .(T175, T176))
perm1_in_ga([], []) → perm1_out_ga([], [])

The argument filtering Pi contains the following mapping:
perm1_in_ga(x1, x2)  =  perm1_in_ga(x1)
.(x1, x2)  =  .(x1, x2)
U12_ga(x1, x2, x3, x4, x5)  =  U12_ga(x5)
app10_in_aaag(x1, x2, x3, x4)  =  app10_in_aaag(x4)
U1_aaag(x1, x2, x3, x4, x5, x6)  =  U1_aaag(x1, x6)
app10_out_aaag(x1, x2, x3, x4)  =  app10_out_aaag(x1, x2, x3)
perm1_out_ga(x1, x2)  =  perm1_out_ga
U13_ga(x1, x2, x3, x4, x5)  =  U13_ga(x1, x5)
U14_ga(x1, x2, x3, x4, x5)  =  U14_ga(x5)
app20_in_ggga(x1, x2, x3, x4)  =  app20_in_ggga(x1, x2, x3)
U11_ggga(x1, x2, x3, x4, x5)  =  U11_ggga(x1, x5)
app25_in_gga(x1, x2, x3)  =  app25_in_gga(x1, x2)
U2_gga(x1, x2, x3, x4, x5)  =  U2_gga(x1, x5)
[]  =  []
app25_out_gga(x1, x2, x3)  =  app25_out_gga(x3)
app20_out_ggga(x1, x2, x3, x4)  =  app20_out_ggga(x4)
U15_ga(x1, x2, x3, x4, x5)  =  U15_ga(x1, x5)
U16_ga(x1, x2, x3, x4, x5)  =  U16_ga(x5)
U17_ga(x1, x2, x3, x4, x5)  =  U17_ga(x5)
perm21_in_ga(x1, x2)  =  perm21_in_ga(x1)
U4_ga(x1, x2, x3, x4)  =  U4_ga(x4)
app40_in_aaag(x1, x2, x3, x4)  =  app40_in_aaag(x4)
U3_aaag(x1, x2, x3, x4, x5, x6)  =  U3_aaag(x1, x6)
app40_out_aaag(x1, x2, x3, x4)  =  app40_out_aaag(x1, x2, x3)
perm21_out_ga(x1, x2)  =  perm21_out_ga
U5_ga(x1, x2, x3, x4)  =  U5_ga(x4)
U6_ga(x1, x2, x3, x4)  =  U6_ga(x4)
app50_in_gga(x1, x2, x3)  =  app50_in_gga(x1, x2)
U10_gga(x1, x2, x3, x4, x5)  =  U10_gga(x1, x5)
app50_out_gga(x1, x2, x3)  =  app50_out_gga(x3)
U7_ga(x1, x2, x3, x4)  =  U7_ga(x4)
U8_ga(x1, x2, x3, x4)  =  U8_ga(x4)
U9_ga(x1, x2, x3, x4)  =  U9_ga(x4)
U18_ga(x1, x2, x3, x4)  =  U18_ga(x4)
app67_in_ga(x1, x2)  =  app67_in_ga(x1)
app67_out_ga(x1, x2)  =  app67_out_ga(x2)
U19_ga(x1, x2, x3, x4)  =  U19_ga(x4)
U20_ga(x1, x2, x3, x4)  =  U20_ga(x4)
APP10_IN_AAAG(x1, x2, x3, x4)  =  APP10_IN_AAAG(x4)

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

(40) UsableRulesProof (EQUIVALENT transformation)

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

(41) Obligation:

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

APP10_IN_AAAG(.(X98, X99), T40, X100, .(X98, T39)) → APP10_IN_AAAG(X99, T40, X100, T39)

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

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

(42) PiDPToQDPProof (SOUND transformation)

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

(43) Obligation:

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

APP10_IN_AAAG(.(X98, T39)) → APP10_IN_AAAG(T39)

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

(44) QDPSizeChangeProof (EQUIVALENT transformation)

By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

  • APP10_IN_AAAG(.(X98, T39)) → APP10_IN_AAAG(T39)
    The graph contains the following edges 1 > 1

(45) YES