/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- Graph construction failed Graph construction failed Graph construction failed MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern type(g,g,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) UndefinedPredicateHandlerProof [SOUND, 0 ms] (2) Prolog (3) PrologToPiTRSProof [SOUND, 0 ms] (4) PiTRS (5) DependencyPairsProof [EQUIVALENT, 31 ms] (6) PiDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) PiDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) PiDP (12) PiDPToQDPProof [SOUND, 0 ms] (13) QDP (14) TransformationProof [EQUIVALENT, 0 ms] (15) QDP (16) UsableRulesProof [EQUIVALENT, 0 ms] (17) QDP (18) QReductionProof [EQUIVALENT, 0 ms] (19) QDP (20) NonTerminationLoopProof [COMPLETE, 0 ms] (21) NO (22) PiDP (23) UsableRulesProof [EQUIVALENT, 0 ms] (24) PiDP (25) PiDPToQDPProof [SOUND, 0 ms] (26) QDP (27) QDPSizeChangeProof [EQUIVALENT, 0 ms] (28) YES (29) PiDP (30) UsableRulesProof [EQUIVALENT, 0 ms] (31) PiDP (32) PiDPToQDPProof [SOUND, 0 ms] (33) QDP (34) QDPSizeChangeProof [EQUIVALENT, 0 ms] (35) YES (36) PiDP (37) PiDPToQDPProof [SOUND, 0 ms] (38) QDP (39) QDPSizeChangeProof [EQUIVALENT, 0 ms] (40) YES (41) PrologToPiTRSProof [SOUND, 0 ms] (42) PiTRS (43) DependencyPairsProof [EQUIVALENT, 33 ms] (44) PiDP (45) DependencyGraphProof [EQUIVALENT, 0 ms] (46) AND (47) PiDP (48) UsableRulesProof [EQUIVALENT, 0 ms] (49) PiDP (50) PiDPToQDPProof [SOUND, 0 ms] (51) QDP (52) TransformationProof [EQUIVALENT, 0 ms] (53) QDP (54) UsableRulesProof [EQUIVALENT, 0 ms] (55) QDP (56) QReductionProof [EQUIVALENT, 0 ms] (57) QDP (58) NonTerminationLoopProof [COMPLETE, 8 ms] (59) NO (60) PiDP (61) UsableRulesProof [EQUIVALENT, 0 ms] (62) PiDP (63) PiDPToQDPProof [SOUND, 0 ms] (64) QDP (65) QDPSizeChangeProof [EQUIVALENT, 0 ms] (66) YES (67) PiDP (68) UsableRulesProof [EQUIVALENT, 0 ms] (69) PiDP (70) PiDPToQDPProof [EQUIVALENT, 0 ms] (71) QDP (72) QDPSizeChangeProof [EQUIVALENT, 0 ms] (73) YES (74) PiDP (75) PiDPToQDPProof [SOUND, 0 ms] (76) QDP (77) QDPSizeChangeProof [EQUIVALENT, 0 ms] (78) YES ---------------------------------------- (0) Obligation: Clauses: type(E, var(X), T) :- in(E, X, T). type(E, apply(M, N), T) :- ','(type(E, M, arrow(S, T)), type(E, N, S)). type(E, lambda(X, M), arrow(S, T)) :- type(.(','(X, S), E), M, T). in(.(','(X, T), E), X, T). in(.(','(Y, T), E), X, T) :- ','(\==(X, Y), in(E, X, T)). Query: type(g,g,a) ---------------------------------------- (1) UndefinedPredicateHandlerProof (SOUND) Added facts for all undefined predicates [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: type(E, var(X), T) :- in(E, X, T). type(E, apply(M, N), T) :- ','(type(E, M, arrow(S, T)), type(E, N, S)). type(E, lambda(X, M), arrow(S, T)) :- type(.(','(X, S), E), M, T). in(.(','(X, T), E), X, T). in(.(','(Y, T), E), X, T) :- ','(\==(X, Y), in(E, X, T)). \==(X0, X1). Query: type(g,g,a) ---------------------------------------- (3) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: type_in_3: (b,b,f) (f,b,f) in_in_3: (b,b,f) (b,b,b) (f,b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg U6_gga(x1, x2, x3, x4, x5) = U6_gga(x2, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x5) type_out_gga(x1, x2, x3) = type_out_gga apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga U6_aga(x1, x2, x3, x4, x5) = U6_aga(x5) type_out_aga(x1, x2, x3) = type_out_aga U2_aga(x1, x2, x3, x4, x5) = U2_aga(x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (4) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg U6_gga(x1, x2, x3, x4, x5) = U6_gga(x2, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x5) type_out_gga(x1, x2, x3) = type_out_gga apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga U6_aga(x1, x2, x3, x4, x5) = U6_aga(x5) type_out_aga(x1, x2, x3) = type_out_aga U2_aga(x1, x2, x3, x4, x5) = U2_aga(x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) ---------------------------------------- (5) 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: TYPE_IN_GGA(E, var(X), T) -> U1_GGA(E, X, T, in_in_gga(E, X, T)) TYPE_IN_GGA(E, var(X), T) -> IN_IN_GGA(E, X, T) IN_IN_GGA(.(','(Y, T), E), X, T) -> U5_GGA(Y, T, E, X, \==_in_gg(X, Y)) IN_IN_GGA(.(','(Y, T), E), X, T) -> \==_IN_GG(X, Y) U5_GGA(Y, T, E, X, \==_out_gg(X, Y)) -> U6_GGA(Y, T, E, X, in_in_ggg(E, X, T)) U5_GGA(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) IN_IN_GGG(.(','(Y, T), E), X, T) -> \==_IN_GG(X, Y) U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> U6_GGG(Y, T, E, X, in_in_ggg(E, X, T)) U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) TYPE_IN_GGA(E, apply(M, N), T) -> U2_GGA(E, M, N, T, type_in_gga(E, M, arrow(S, T))) TYPE_IN_GGA(E, apply(M, N), T) -> TYPE_IN_GGA(E, M, arrow(S, T)) TYPE_IN_GGA(E, lambda(X, M), arrow(S, T)) -> U4_GGA(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) TYPE_IN_GGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) TYPE_IN_AGA(E, var(X), T) -> U1_AGA(E, X, T, in_in_aga(E, X, T)) TYPE_IN_AGA(E, var(X), T) -> IN_IN_AGA(E, X, T) IN_IN_AGA(.(','(Y, T), E), X, T) -> U5_AGA(Y, T, E, X, \==_in_ga(X, Y)) IN_IN_AGA(.(','(Y, T), E), X, T) -> \==_IN_GA(X, Y) U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> U6_AGA(Y, T, E, X, in_in_aga(E, X, T)) U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> IN_IN_AGA(E, X, T) TYPE_IN_AGA(E, apply(M, N), T) -> U2_AGA(E, M, N, T, type_in_aga(E, M, arrow(S, T))) TYPE_IN_AGA(E, apply(M, N), T) -> TYPE_IN_AGA(E, M, arrow(S, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> U4_AGA(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_AGA(E, M, N, T, type_in_aga(E, N, S)) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> TYPE_IN_AGA(E, N, S) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_GGA(E, M, N, T, type_in_gga(E, N, S)) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> TYPE_IN_GGA(E, N, S) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg U6_gga(x1, x2, x3, x4, x5) = U6_gga(x2, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x5) type_out_gga(x1, x2, x3) = type_out_gga apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga U6_aga(x1, x2, x3, x4, x5) = U6_aga(x5) type_out_aga(x1, x2, x3) = type_out_aga U2_aga(x1, x2, x3, x4, x5) = U2_aga(x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) TYPE_IN_GGA(x1, x2, x3) = TYPE_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x4) IN_IN_GGA(x1, x2, x3) = IN_IN_GGA(x1, x2) U5_GGA(x1, x2, x3, x4, x5) = U5_GGA(x2, x3, x4, x5) \==_IN_GG(x1, x2) = \==_IN_GG(x1, x2) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x2, x5) IN_IN_GGG(x1, x2, x3) = IN_IN_GGG(x1, x2, x3) U5_GGG(x1, x2, x3, x4, x5) = U5_GGG(x2, x3, x4, x5) U6_GGG(x1, x2, x3, x4, x5) = U6_GGG(x5) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x1, x3, x5) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x6) TYPE_IN_AGA(x1, x2, x3) = TYPE_IN_AGA(x2) U1_AGA(x1, x2, x3, x4) = U1_AGA(x4) IN_IN_AGA(x1, x2, x3) = IN_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x4, x5) \==_IN_GA(x1, x2) = \==_IN_GA(x1) U6_AGA(x1, x2, x3, x4, x5) = U6_AGA(x5) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x3, x5) U4_AGA(x1, x2, x3, x4, x5, x6) = U4_AGA(x6) U3_AGA(x1, x2, x3, x4, x5) = U3_AGA(x5) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: TYPE_IN_GGA(E, var(X), T) -> U1_GGA(E, X, T, in_in_gga(E, X, T)) TYPE_IN_GGA(E, var(X), T) -> IN_IN_GGA(E, X, T) IN_IN_GGA(.(','(Y, T), E), X, T) -> U5_GGA(Y, T, E, X, \==_in_gg(X, Y)) IN_IN_GGA(.(','(Y, T), E), X, T) -> \==_IN_GG(X, Y) U5_GGA(Y, T, E, X, \==_out_gg(X, Y)) -> U6_GGA(Y, T, E, X, in_in_ggg(E, X, T)) U5_GGA(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) IN_IN_GGG(.(','(Y, T), E), X, T) -> \==_IN_GG(X, Y) U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> U6_GGG(Y, T, E, X, in_in_ggg(E, X, T)) U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) TYPE_IN_GGA(E, apply(M, N), T) -> U2_GGA(E, M, N, T, type_in_gga(E, M, arrow(S, T))) TYPE_IN_GGA(E, apply(M, N), T) -> TYPE_IN_GGA(E, M, arrow(S, T)) TYPE_IN_GGA(E, lambda(X, M), arrow(S, T)) -> U4_GGA(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) TYPE_IN_GGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) TYPE_IN_AGA(E, var(X), T) -> U1_AGA(E, X, T, in_in_aga(E, X, T)) TYPE_IN_AGA(E, var(X), T) -> IN_IN_AGA(E, X, T) IN_IN_AGA(.(','(Y, T), E), X, T) -> U5_AGA(Y, T, E, X, \==_in_ga(X, Y)) IN_IN_AGA(.(','(Y, T), E), X, T) -> \==_IN_GA(X, Y) U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> U6_AGA(Y, T, E, X, in_in_aga(E, X, T)) U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> IN_IN_AGA(E, X, T) TYPE_IN_AGA(E, apply(M, N), T) -> U2_AGA(E, M, N, T, type_in_aga(E, M, arrow(S, T))) TYPE_IN_AGA(E, apply(M, N), T) -> TYPE_IN_AGA(E, M, arrow(S, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> U4_AGA(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_AGA(E, M, N, T, type_in_aga(E, N, S)) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> TYPE_IN_AGA(E, N, S) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_GGA(E, M, N, T, type_in_gga(E, N, S)) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> TYPE_IN_GGA(E, N, S) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg U6_gga(x1, x2, x3, x4, x5) = U6_gga(x2, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x5) type_out_gga(x1, x2, x3) = type_out_gga apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga U6_aga(x1, x2, x3, x4, x5) = U6_aga(x5) type_out_aga(x1, x2, x3) = type_out_aga U2_aga(x1, x2, x3, x4, x5) = U2_aga(x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) TYPE_IN_GGA(x1, x2, x3) = TYPE_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x4) IN_IN_GGA(x1, x2, x3) = IN_IN_GGA(x1, x2) U5_GGA(x1, x2, x3, x4, x5) = U5_GGA(x2, x3, x4, x5) \==_IN_GG(x1, x2) = \==_IN_GG(x1, x2) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x2, x5) IN_IN_GGG(x1, x2, x3) = IN_IN_GGG(x1, x2, x3) U5_GGG(x1, x2, x3, x4, x5) = U5_GGG(x2, x3, x4, x5) U6_GGG(x1, x2, x3, x4, x5) = U6_GGG(x5) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x1, x3, x5) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x6) TYPE_IN_AGA(x1, x2, x3) = TYPE_IN_AGA(x2) U1_AGA(x1, x2, x3, x4) = U1_AGA(x4) IN_IN_AGA(x1, x2, x3) = IN_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x4, x5) \==_IN_GA(x1, x2) = \==_IN_GA(x1) U6_AGA(x1, x2, x3, x4, x5) = U6_AGA(x5) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x3, x5) U4_AGA(x1, x2, x3, x4, x5, x6) = U4_AGA(x6) U3_AGA(x1, x2, x3, x4, x5) = U3_AGA(x5) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 17 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> IN_IN_AGA(E, X, T) IN_IN_AGA(.(','(Y, T), E), X, T) -> U5_AGA(Y, T, E, X, \==_in_ga(X, Y)) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg U6_gga(x1, x2, x3, x4, x5) = U6_gga(x2, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x5) type_out_gga(x1, x2, x3) = type_out_gga apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga U6_aga(x1, x2, x3, x4, x5) = U6_aga(x5) type_out_aga(x1, x2, x3) = type_out_aga U2_aga(x1, x2, x3, x4, x5) = U2_aga(x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) IN_IN_AGA(x1, x2, x3) = IN_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) UsableRulesProof (EQUIVALENT) 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: U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> IN_IN_AGA(E, X, T) IN_IN_AGA(.(','(Y, T), E), X, T) -> U5_AGA(Y, T, E, X, \==_in_ga(X, Y)) The TRS R consists of the following rules: \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga IN_IN_AGA(x1, x2, x3) = IN_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (12) PiDPToQDPProof (SOUND) 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: U5_AGA(X, \==_out_ga) -> IN_IN_AGA(X) IN_IN_AGA(X) -> U5_AGA(X, \==_in_ga(X)) The TRS R consists of the following rules: \==_in_ga(X0) -> \==_out_ga The set Q consists of the following terms: \==_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (14) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule IN_IN_AGA(X) -> U5_AGA(X, \==_in_ga(X)) at position [1] we obtained the following new rules [LPAR04]: (IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga),IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga)) ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: U5_AGA(X, \==_out_ga) -> IN_IN_AGA(X) IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga) The TRS R consists of the following rules: \==_in_ga(X0) -> \==_out_ga The set Q consists of the following terms: \==_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (16) 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. ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: U5_AGA(X, \==_out_ga) -> IN_IN_AGA(X) IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga) R is empty. The set Q consists of the following terms: \==_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (18) 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]. \==_in_ga(x0) ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: U5_AGA(X, \==_out_ga) -> IN_IN_AGA(X) IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (20) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = IN_IN_AGA(X') evaluates to t =IN_IN_AGA(X') Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence IN_IN_AGA(X') -> U5_AGA(X', \==_out_ga) with rule IN_IN_AGA(X'') -> U5_AGA(X'', \==_out_ga) at position [] and matcher [X'' / X'] U5_AGA(X', \==_out_ga) -> IN_IN_AGA(X') with rule U5_AGA(X, \==_out_ga) -> IN_IN_AGA(X) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (21) NO ---------------------------------------- (22) Obligation: Pi DP problem: The TRS P consists of the following rules: TYPE_IN_AGA(E, apply(M, N), T) -> U2_AGA(E, M, N, T, type_in_aga(E, M, arrow(S, T))) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> TYPE_IN_AGA(E, N, S) TYPE_IN_AGA(E, apply(M, N), T) -> TYPE_IN_AGA(E, M, arrow(S, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg U6_gga(x1, x2, x3, x4, x5) = U6_gga(x2, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x5) type_out_gga(x1, x2, x3) = type_out_gga apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga U6_aga(x1, x2, x3, x4, x5) = U6_aga(x5) type_out_aga(x1, x2, x3) = type_out_aga U2_aga(x1, x2, x3, x4, x5) = U2_aga(x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) TYPE_IN_AGA(x1, x2, x3) = TYPE_IN_AGA(x2) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (23) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (24) Obligation: Pi DP problem: The TRS P consists of the following rules: TYPE_IN_AGA(E, apply(M, N), T) -> U2_AGA(E, M, N, T, type_in_aga(E, M, arrow(S, T))) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> TYPE_IN_AGA(E, N, S) TYPE_IN_AGA(E, apply(M, N), T) -> TYPE_IN_AGA(E, M, arrow(S, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) The TRS R consists of the following rules: type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) The argument filtering Pi contains the following mapping: var(x1) = var(x1) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) apply(x1, x2) = apply(x1, x2) lambda(x1, x2) = lambda(x1, x2) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga U6_aga(x1, x2, x3, x4, x5) = U6_aga(x5) type_out_aga(x1, x2, x3) = type_out_aga U2_aga(x1, x2, x3, x4, x5) = U2_aga(x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x5) TYPE_IN_AGA(x1, x2, x3) = TYPE_IN_AGA(x2) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (25) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: TYPE_IN_AGA(apply(M, N)) -> U2_AGA(N, type_in_aga(M)) U2_AGA(N, type_out_aga) -> TYPE_IN_AGA(N) TYPE_IN_AGA(apply(M, N)) -> TYPE_IN_AGA(M) TYPE_IN_AGA(lambda(X, M)) -> TYPE_IN_AGA(M) The TRS R consists of the following rules: type_in_aga(var(X)) -> U1_aga(in_in_aga(X)) type_in_aga(apply(M, N)) -> U2_aga(N, type_in_aga(M)) type_in_aga(lambda(X, M)) -> U4_aga(type_in_aga(M)) U1_aga(in_out_aga) -> type_out_aga U2_aga(N, type_out_aga) -> U3_aga(type_in_aga(N)) U4_aga(type_out_aga) -> type_out_aga in_in_aga(X) -> in_out_aga in_in_aga(X) -> U5_aga(X, \==_in_ga(X)) U3_aga(type_out_aga) -> type_out_aga U5_aga(X, \==_out_ga) -> U6_aga(in_in_aga(X)) \==_in_ga(X0) -> \==_out_ga U6_aga(in_out_aga) -> in_out_aga The set Q consists of the following terms: type_in_aga(x0) U1_aga(x0) U2_aga(x0, x1) U4_aga(x0) in_in_aga(x0) U3_aga(x0) U5_aga(x0, x1) \==_in_ga(x0) U6_aga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (27) 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_AGA(N, type_out_aga) -> TYPE_IN_AGA(N) The graph contains the following edges 1 >= 1 *TYPE_IN_AGA(apply(M, N)) -> U2_AGA(N, type_in_aga(M)) The graph contains the following edges 1 > 1 *TYPE_IN_AGA(apply(M, N)) -> TYPE_IN_AGA(M) The graph contains the following edges 1 > 1 *TYPE_IN_AGA(lambda(X, M)) -> TYPE_IN_AGA(M) The graph contains the following edges 1 > 1 ---------------------------------------- (28) YES ---------------------------------------- (29) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg U6_gga(x1, x2, x3, x4, x5) = U6_gga(x2, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x5) type_out_gga(x1, x2, x3) = type_out_gga apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga U6_aga(x1, x2, x3, x4, x5) = U6_aga(x5) type_out_aga(x1, x2, x3) = type_out_aga U2_aga(x1, x2, x3, x4, x5) = U2_aga(x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) IN_IN_GGG(x1, x2, x3) = IN_IN_GGG(x1, x2, x3) U5_GGG(x1, x2, x3, x4, x5) = U5_GGG(x2, x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (30) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (31) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) The TRS R consists of the following rules: \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg IN_IN_GGG(x1, x2, x3) = IN_IN_GGG(x1, x2, x3) U5_GGG(x1, x2, x3, x4, x5) = U5_GGG(x2, x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (32) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: U5_GGG(T, E, X, \==_out_gg) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(T, E, X, \==_in_gg(X, Y)) The TRS R consists of the following rules: \==_in_gg(X0, X1) -> \==_out_gg The set Q consists of the following terms: \==_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (34) 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: *IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(T, E, X, \==_in_gg(X, Y)) The graph contains the following edges 1 > 1, 3 >= 1, 1 > 2, 2 >= 3 *U5_GGG(T, E, X, \==_out_gg) -> IN_IN_GGG(E, X, T) The graph contains the following edges 2 >= 1, 3 >= 2, 1 >= 3 ---------------------------------------- (35) YES ---------------------------------------- (36) Obligation: Pi DP problem: The TRS P consists of the following rules: TYPE_IN_GGA(E, apply(M, N), T) -> U2_GGA(E, M, N, T, type_in_gga(E, M, arrow(S, T))) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> TYPE_IN_GGA(E, N, S) TYPE_IN_GGA(E, apply(M, N), T) -> TYPE_IN_GGA(E, M, arrow(S, T)) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg U6_gga(x1, x2, x3, x4, x5) = U6_gga(x2, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x5) type_out_gga(x1, x2, x3) = type_out_gga apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga U6_aga(x1, x2, x3, x4, x5) = U6_aga(x5) type_out_aga(x1, x2, x3) = type_out_aga U2_aga(x1, x2, x3, x4, x5) = U2_aga(x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) TYPE_IN_GGA(x1, x2, x3) = TYPE_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x1, x3, x5) 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: TYPE_IN_GGA(E, apply(M, N)) -> U2_GGA(E, N, type_in_gga(E, M)) U2_GGA(E, N, type_out_gga) -> TYPE_IN_GGA(E, N) TYPE_IN_GGA(E, apply(M, N)) -> TYPE_IN_GGA(E, M) The TRS R consists of the following rules: type_in_gga(E, var(X)) -> U1_gga(in_in_gga(E, X)) in_in_gga(.(','(X, T), E), X) -> in_out_gga(T) in_in_gga(.(','(Y, T), E), X) -> U5_gga(T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg U5_gga(T, E, X, \==_out_gg) -> U6_gga(T, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(T, E, X, \==_in_gg(X, Y)) U5_ggg(T, E, X, \==_out_gg) -> U6_ggg(in_in_ggg(E, X, T)) U6_ggg(in_out_ggg) -> in_out_ggg U6_gga(T, in_out_ggg) -> in_out_gga(T) U1_gga(in_out_gga(T)) -> type_out_gga type_in_gga(E, apply(M, N)) -> U2_gga(E, N, type_in_gga(E, M)) type_in_gga(E, lambda(X, M)) -> U4_gga(type_in_aga(M)) type_in_aga(var(X)) -> U1_aga(in_in_aga(X)) in_in_aga(X) -> in_out_aga in_in_aga(X) -> U5_aga(X, \==_in_ga(X)) \==_in_ga(X0) -> \==_out_ga U5_aga(X, \==_out_ga) -> U6_aga(in_in_aga(X)) U6_aga(in_out_aga) -> in_out_aga U1_aga(in_out_aga) -> type_out_aga type_in_aga(apply(M, N)) -> U2_aga(N, type_in_aga(M)) type_in_aga(lambda(X, M)) -> U4_aga(type_in_aga(M)) U4_aga(type_out_aga) -> type_out_aga U2_aga(N, type_out_aga) -> U3_aga(type_in_aga(N)) U3_aga(type_out_aga) -> type_out_aga U4_gga(type_out_aga) -> type_out_gga U2_gga(E, N, type_out_gga) -> U3_gga(type_in_gga(E, N)) U3_gga(type_out_gga) -> type_out_gga The set Q consists of the following terms: type_in_gga(x0, x1) in_in_gga(x0, x1) \==_in_gg(x0, x1) U5_gga(x0, x1, x2, x3) in_in_ggg(x0, x1, x2) U5_ggg(x0, x1, x2, x3) U6_ggg(x0) U6_gga(x0, x1) U1_gga(x0) type_in_aga(x0) in_in_aga(x0) \==_in_ga(x0) U5_aga(x0, x1) U6_aga(x0) U1_aga(x0) U4_aga(x0) U2_aga(x0, x1) U3_aga(x0) U4_gga(x0) U2_gga(x0, x1, x2) U3_gga(x0) 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: *U2_GGA(E, N, type_out_gga) -> TYPE_IN_GGA(E, N) The graph contains the following edges 1 >= 1, 2 >= 2 *TYPE_IN_GGA(E, apply(M, N)) -> TYPE_IN_GGA(E, M) The graph contains the following edges 1 >= 1, 2 > 2 *TYPE_IN_GGA(E, apply(M, N)) -> U2_GGA(E, N, type_in_gga(E, M)) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (40) YES ---------------------------------------- (41) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: type_in_3: (b,b,f) (f,b,f) in_in_3: (b,b,f) (b,b,b) (f,b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x1, x2, x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x1, x2, x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg(x1, x2) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x4, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg(x1, x2, x3) U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x1, x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x1, x2, x3, x4, x5) type_out_gga(x1, x2, x3) = type_out_gga(x1, x2) apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x2, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x1, x2, x3, x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x2, x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga(x2) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) U6_aga(x1, x2, x3, x4, x5) = U6_aga(x4, x5) type_out_aga(x1, x2, x3) = type_out_aga(x2) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x2, x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x2, x3, x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x2, x3, x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (42) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x1, x2, x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x1, x2, x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg(x1, x2) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x4, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg(x1, x2, x3) U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x1, x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x1, x2, x3, x4, x5) type_out_gga(x1, x2, x3) = type_out_gga(x1, x2) apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x2, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x1, x2, x3, x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x2, x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga(x2) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) U6_aga(x1, x2, x3, x4, x5) = U6_aga(x4, x5) type_out_aga(x1, x2, x3) = type_out_aga(x2) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x2, x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x2, x3, x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x2, x3, x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) ---------------------------------------- (43) 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: TYPE_IN_GGA(E, var(X), T) -> U1_GGA(E, X, T, in_in_gga(E, X, T)) TYPE_IN_GGA(E, var(X), T) -> IN_IN_GGA(E, X, T) IN_IN_GGA(.(','(Y, T), E), X, T) -> U5_GGA(Y, T, E, X, \==_in_gg(X, Y)) IN_IN_GGA(.(','(Y, T), E), X, T) -> \==_IN_GG(X, Y) U5_GGA(Y, T, E, X, \==_out_gg(X, Y)) -> U6_GGA(Y, T, E, X, in_in_ggg(E, X, T)) U5_GGA(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) IN_IN_GGG(.(','(Y, T), E), X, T) -> \==_IN_GG(X, Y) U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> U6_GGG(Y, T, E, X, in_in_ggg(E, X, T)) U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) TYPE_IN_GGA(E, apply(M, N), T) -> U2_GGA(E, M, N, T, type_in_gga(E, M, arrow(S, T))) TYPE_IN_GGA(E, apply(M, N), T) -> TYPE_IN_GGA(E, M, arrow(S, T)) TYPE_IN_GGA(E, lambda(X, M), arrow(S, T)) -> U4_GGA(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) TYPE_IN_GGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) TYPE_IN_AGA(E, var(X), T) -> U1_AGA(E, X, T, in_in_aga(E, X, T)) TYPE_IN_AGA(E, var(X), T) -> IN_IN_AGA(E, X, T) IN_IN_AGA(.(','(Y, T), E), X, T) -> U5_AGA(Y, T, E, X, \==_in_ga(X, Y)) IN_IN_AGA(.(','(Y, T), E), X, T) -> \==_IN_GA(X, Y) U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> U6_AGA(Y, T, E, X, in_in_aga(E, X, T)) U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> IN_IN_AGA(E, X, T) TYPE_IN_AGA(E, apply(M, N), T) -> U2_AGA(E, M, N, T, type_in_aga(E, M, arrow(S, T))) TYPE_IN_AGA(E, apply(M, N), T) -> TYPE_IN_AGA(E, M, arrow(S, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> U4_AGA(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_AGA(E, M, N, T, type_in_aga(E, N, S)) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> TYPE_IN_AGA(E, N, S) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_GGA(E, M, N, T, type_in_gga(E, N, S)) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> TYPE_IN_GGA(E, N, S) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x1, x2, x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x1, x2, x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg(x1, x2) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x4, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg(x1, x2, x3) U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x1, x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x1, x2, x3, x4, x5) type_out_gga(x1, x2, x3) = type_out_gga(x1, x2) apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x2, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x1, x2, x3, x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x2, x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga(x2) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) U6_aga(x1, x2, x3, x4, x5) = U6_aga(x4, x5) type_out_aga(x1, x2, x3) = type_out_aga(x2) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x2, x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x2, x3, x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x2, x3, x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) TYPE_IN_GGA(x1, x2, x3) = TYPE_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) IN_IN_GGA(x1, x2, x3) = IN_IN_GGA(x1, x2) U5_GGA(x1, x2, x3, x4, x5) = U5_GGA(x1, x2, x3, x4, x5) \==_IN_GG(x1, x2) = \==_IN_GG(x1, x2) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x1, x2, x3, x4, x5) IN_IN_GGG(x1, x2, x3) = IN_IN_GGG(x1, x2, x3) U5_GGG(x1, x2, x3, x4, x5) = U5_GGG(x1, x2, x3, x4, x5) U6_GGG(x1, x2, x3, x4, x5) = U6_GGG(x1, x2, x3, x4, x5) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x1, x2, x3, x5) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x1, x2, x3, x6) TYPE_IN_AGA(x1, x2, x3) = TYPE_IN_AGA(x2) U1_AGA(x1, x2, x3, x4) = U1_AGA(x2, x4) IN_IN_AGA(x1, x2, x3) = IN_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x4, x5) \==_IN_GA(x1, x2) = \==_IN_GA(x1) U6_AGA(x1, x2, x3, x4, x5) = U6_AGA(x4, x5) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x2, x3, x5) U4_AGA(x1, x2, x3, x4, x5, x6) = U4_AGA(x2, x3, x6) U3_AGA(x1, x2, x3, x4, x5) = U3_AGA(x2, x3, x5) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (44) Obligation: Pi DP problem: The TRS P consists of the following rules: TYPE_IN_GGA(E, var(X), T) -> U1_GGA(E, X, T, in_in_gga(E, X, T)) TYPE_IN_GGA(E, var(X), T) -> IN_IN_GGA(E, X, T) IN_IN_GGA(.(','(Y, T), E), X, T) -> U5_GGA(Y, T, E, X, \==_in_gg(X, Y)) IN_IN_GGA(.(','(Y, T), E), X, T) -> \==_IN_GG(X, Y) U5_GGA(Y, T, E, X, \==_out_gg(X, Y)) -> U6_GGA(Y, T, E, X, in_in_ggg(E, X, T)) U5_GGA(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) IN_IN_GGG(.(','(Y, T), E), X, T) -> \==_IN_GG(X, Y) U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> U6_GGG(Y, T, E, X, in_in_ggg(E, X, T)) U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) TYPE_IN_GGA(E, apply(M, N), T) -> U2_GGA(E, M, N, T, type_in_gga(E, M, arrow(S, T))) TYPE_IN_GGA(E, apply(M, N), T) -> TYPE_IN_GGA(E, M, arrow(S, T)) TYPE_IN_GGA(E, lambda(X, M), arrow(S, T)) -> U4_GGA(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) TYPE_IN_GGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) TYPE_IN_AGA(E, var(X), T) -> U1_AGA(E, X, T, in_in_aga(E, X, T)) TYPE_IN_AGA(E, var(X), T) -> IN_IN_AGA(E, X, T) IN_IN_AGA(.(','(Y, T), E), X, T) -> U5_AGA(Y, T, E, X, \==_in_ga(X, Y)) IN_IN_AGA(.(','(Y, T), E), X, T) -> \==_IN_GA(X, Y) U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> U6_AGA(Y, T, E, X, in_in_aga(E, X, T)) U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> IN_IN_AGA(E, X, T) TYPE_IN_AGA(E, apply(M, N), T) -> U2_AGA(E, M, N, T, type_in_aga(E, M, arrow(S, T))) TYPE_IN_AGA(E, apply(M, N), T) -> TYPE_IN_AGA(E, M, arrow(S, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> U4_AGA(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_AGA(E, M, N, T, type_in_aga(E, N, S)) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> TYPE_IN_AGA(E, N, S) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_GGA(E, M, N, T, type_in_gga(E, N, S)) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> TYPE_IN_GGA(E, N, S) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x1, x2, x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x1, x2, x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg(x1, x2) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x4, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg(x1, x2, x3) U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x1, x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x1, x2, x3, x4, x5) type_out_gga(x1, x2, x3) = type_out_gga(x1, x2) apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x2, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x1, x2, x3, x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x2, x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga(x2) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) U6_aga(x1, x2, x3, x4, x5) = U6_aga(x4, x5) type_out_aga(x1, x2, x3) = type_out_aga(x2) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x2, x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x2, x3, x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x2, x3, x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) TYPE_IN_GGA(x1, x2, x3) = TYPE_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) IN_IN_GGA(x1, x2, x3) = IN_IN_GGA(x1, x2) U5_GGA(x1, x2, x3, x4, x5) = U5_GGA(x1, x2, x3, x4, x5) \==_IN_GG(x1, x2) = \==_IN_GG(x1, x2) U6_GGA(x1, x2, x3, x4, x5) = U6_GGA(x1, x2, x3, x4, x5) IN_IN_GGG(x1, x2, x3) = IN_IN_GGG(x1, x2, x3) U5_GGG(x1, x2, x3, x4, x5) = U5_GGG(x1, x2, x3, x4, x5) U6_GGG(x1, x2, x3, x4, x5) = U6_GGG(x1, x2, x3, x4, x5) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x1, x2, x3, x5) U4_GGA(x1, x2, x3, x4, x5, x6) = U4_GGA(x1, x2, x3, x6) TYPE_IN_AGA(x1, x2, x3) = TYPE_IN_AGA(x2) U1_AGA(x1, x2, x3, x4) = U1_AGA(x2, x4) IN_IN_AGA(x1, x2, x3) = IN_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x4, x5) \==_IN_GA(x1, x2) = \==_IN_GA(x1) U6_AGA(x1, x2, x3, x4, x5) = U6_AGA(x4, x5) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x2, x3, x5) U4_AGA(x1, x2, x3, x4, x5, x6) = U4_AGA(x2, x3, x6) U3_AGA(x1, x2, x3, x4, x5) = U3_AGA(x2, x3, x5) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (45) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 4 SCCs with 17 less nodes. ---------------------------------------- (46) Complex Obligation (AND) ---------------------------------------- (47) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> IN_IN_AGA(E, X, T) IN_IN_AGA(.(','(Y, T), E), X, T) -> U5_AGA(Y, T, E, X, \==_in_ga(X, Y)) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x1, x2, x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x1, x2, x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg(x1, x2) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x4, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg(x1, x2, x3) U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x1, x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x1, x2, x3, x4, x5) type_out_gga(x1, x2, x3) = type_out_gga(x1, x2) apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x2, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x1, x2, x3, x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x2, x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga(x2) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) U6_aga(x1, x2, x3, x4, x5) = U6_aga(x4, x5) type_out_aga(x1, x2, x3) = type_out_aga(x2) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x2, x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x2, x3, x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x2, x3, x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) IN_IN_AGA(x1, x2, x3) = IN_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (48) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (49) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_AGA(Y, T, E, X, \==_out_ga(X, Y)) -> IN_IN_AGA(E, X, T) IN_IN_AGA(.(','(Y, T), E), X, T) -> U5_AGA(Y, T, E, X, \==_in_ga(X, Y)) The TRS R consists of the following rules: \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) IN_IN_AGA(x1, x2, x3) = IN_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5) = U5_AGA(x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (50) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: U5_AGA(X, \==_out_ga(X)) -> IN_IN_AGA(X) IN_IN_AGA(X) -> U5_AGA(X, \==_in_ga(X)) The TRS R consists of the following rules: \==_in_ga(X0) -> \==_out_ga(X0) The set Q consists of the following terms: \==_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (52) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule IN_IN_AGA(X) -> U5_AGA(X, \==_in_ga(X)) at position [1] we obtained the following new rules [LPAR04]: (IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga(X)),IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga(X))) ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: U5_AGA(X, \==_out_ga(X)) -> IN_IN_AGA(X) IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga(X)) The TRS R consists of the following rules: \==_in_ga(X0) -> \==_out_ga(X0) The set Q consists of the following terms: \==_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (54) 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. ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: U5_AGA(X, \==_out_ga(X)) -> IN_IN_AGA(X) IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga(X)) R is empty. The set Q consists of the following terms: \==_in_ga(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (56) 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]. \==_in_ga(x0) ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: U5_AGA(X, \==_out_ga(X)) -> IN_IN_AGA(X) IN_IN_AGA(X) -> U5_AGA(X, \==_out_ga(X)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (58) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = IN_IN_AGA(X') evaluates to t =IN_IN_AGA(X') Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence IN_IN_AGA(X') -> U5_AGA(X', \==_out_ga(X')) with rule IN_IN_AGA(X'') -> U5_AGA(X'', \==_out_ga(X'')) at position [] and matcher [X'' / X'] U5_AGA(X', \==_out_ga(X')) -> IN_IN_AGA(X') with rule U5_AGA(X, \==_out_ga(X)) -> IN_IN_AGA(X) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (59) NO ---------------------------------------- (60) Obligation: Pi DP problem: The TRS P consists of the following rules: TYPE_IN_AGA(E, apply(M, N), T) -> U2_AGA(E, M, N, T, type_in_aga(E, M, arrow(S, T))) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> TYPE_IN_AGA(E, N, S) TYPE_IN_AGA(E, apply(M, N), T) -> TYPE_IN_AGA(E, M, arrow(S, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x1, x2, x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x1, x2, x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg(x1, x2) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x4, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg(x1, x2, x3) U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x1, x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x1, x2, x3, x4, x5) type_out_gga(x1, x2, x3) = type_out_gga(x1, x2) apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x2, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x1, x2, x3, x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x2, x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga(x2) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) U6_aga(x1, x2, x3, x4, x5) = U6_aga(x4, x5) type_out_aga(x1, x2, x3) = type_out_aga(x2) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x2, x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x2, x3, x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x2, x3, x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) TYPE_IN_AGA(x1, x2, x3) = TYPE_IN_AGA(x2) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (61) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (62) Obligation: Pi DP problem: The TRS P consists of the following rules: TYPE_IN_AGA(E, apply(M, N), T) -> U2_AGA(E, M, N, T, type_in_aga(E, M, arrow(S, T))) U2_AGA(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> TYPE_IN_AGA(E, N, S) TYPE_IN_AGA(E, apply(M, N), T) -> TYPE_IN_AGA(E, M, arrow(S, T)) TYPE_IN_AGA(E, lambda(X, M), arrow(S, T)) -> TYPE_IN_AGA(.(','(X, S), E), M, T) The TRS R consists of the following rules: type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) The argument filtering Pi contains the following mapping: var(x1) = var(x1) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) apply(x1, x2) = apply(x1, x2) lambda(x1, x2) = lambda(x1, x2) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x2, x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga(x2) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) U6_aga(x1, x2, x3, x4, x5) = U6_aga(x4, x5) type_out_aga(x1, x2, x3) = type_out_aga(x2) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x2, x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x2, x3, x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x2, x3, x5) TYPE_IN_AGA(x1, x2, x3) = TYPE_IN_AGA(x2) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (63) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: TYPE_IN_AGA(apply(M, N)) -> U2_AGA(M, N, type_in_aga(M)) U2_AGA(M, N, type_out_aga(M)) -> TYPE_IN_AGA(N) TYPE_IN_AGA(apply(M, N)) -> TYPE_IN_AGA(M) TYPE_IN_AGA(lambda(X, M)) -> TYPE_IN_AGA(M) The TRS R consists of the following rules: type_in_aga(var(X)) -> U1_aga(X, in_in_aga(X)) type_in_aga(apply(M, N)) -> U2_aga(M, N, type_in_aga(M)) type_in_aga(lambda(X, M)) -> U4_aga(X, M, type_in_aga(M)) U1_aga(X, in_out_aga(X)) -> type_out_aga(var(X)) U2_aga(M, N, type_out_aga(M)) -> U3_aga(M, N, type_in_aga(N)) U4_aga(X, M, type_out_aga(M)) -> type_out_aga(lambda(X, M)) in_in_aga(X) -> in_out_aga(X) in_in_aga(X) -> U5_aga(X, \==_in_ga(X)) U3_aga(M, N, type_out_aga(N)) -> type_out_aga(apply(M, N)) U5_aga(X, \==_out_ga(X)) -> U6_aga(X, in_in_aga(X)) \==_in_ga(X0) -> \==_out_ga(X0) U6_aga(X, in_out_aga(X)) -> in_out_aga(X) The set Q consists of the following terms: type_in_aga(x0) U1_aga(x0, x1) U2_aga(x0, x1, x2) U4_aga(x0, x1, x2) in_in_aga(x0) U3_aga(x0, x1, x2) U5_aga(x0, x1) \==_in_ga(x0) U6_aga(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (65) 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_AGA(M, N, type_out_aga(M)) -> TYPE_IN_AGA(N) The graph contains the following edges 2 >= 1 *TYPE_IN_AGA(apply(M, N)) -> U2_AGA(M, N, type_in_aga(M)) The graph contains the following edges 1 > 1, 1 > 2 *TYPE_IN_AGA(apply(M, N)) -> TYPE_IN_AGA(M) The graph contains the following edges 1 > 1 *TYPE_IN_AGA(lambda(X, M)) -> TYPE_IN_AGA(M) The graph contains the following edges 1 > 1 ---------------------------------------- (66) YES ---------------------------------------- (67) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x1, x2, x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x1, x2, x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg(x1, x2) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x4, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg(x1, x2, x3) U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x1, x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x1, x2, x3, x4, x5) type_out_gga(x1, x2, x3) = type_out_gga(x1, x2) apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x2, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x1, x2, x3, x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x2, x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga(x2) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) U6_aga(x1, x2, x3, x4, x5) = U6_aga(x4, x5) type_out_aga(x1, x2, x3) = type_out_aga(x2) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x2, x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x2, x3, x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x2, x3, x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) IN_IN_GGG(x1, x2, x3) = IN_IN_GGG(x1, x2, x3) U5_GGG(x1, x2, x3, x4, x5) = U5_GGG(x1, x2, x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (68) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (69) Obligation: Pi DP problem: The TRS P consists of the following rules: U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) The TRS R consists of the following rules: \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (70) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) The TRS R consists of the following rules: \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) The set Q consists of the following terms: \==_in_gg(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (72) 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: *IN_IN_GGG(.(','(Y, T), E), X, T) -> U5_GGG(Y, T, E, X, \==_in_gg(X, Y)) The graph contains the following edges 1 > 1, 1 > 2, 3 >= 2, 1 > 3, 2 >= 4 *U5_GGG(Y, T, E, X, \==_out_gg(X, Y)) -> IN_IN_GGG(E, X, T) The graph contains the following edges 3 >= 1, 4 >= 2, 5 > 2, 2 >= 3 ---------------------------------------- (73) YES ---------------------------------------- (74) Obligation: Pi DP problem: The TRS P consists of the following rules: TYPE_IN_GGA(E, apply(M, N), T) -> U2_GGA(E, M, N, T, type_in_gga(E, M, arrow(S, T))) U2_GGA(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> TYPE_IN_GGA(E, N, S) TYPE_IN_GGA(E, apply(M, N), T) -> TYPE_IN_GGA(E, M, arrow(S, T)) The TRS R consists of the following rules: type_in_gga(E, var(X), T) -> U1_gga(E, X, T, in_in_gga(E, X, T)) in_in_gga(.(','(X, T), E), X, T) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X, T) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, T, in_out_gga(E, X, T)) -> type_out_gga(E, var(X), T) type_in_gga(E, apply(M, N), T) -> U2_gga(E, M, N, T, type_in_gga(E, M, arrow(S, T))) type_in_gga(E, lambda(X, M), arrow(S, T)) -> U4_gga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) type_in_aga(E, var(X), T) -> U1_aga(E, X, T, in_in_aga(E, X, T)) in_in_aga(.(','(X, T), E), X, T) -> in_out_aga(.(','(X, T), E), X, T) in_in_aga(.(','(Y, T), E), X, T) -> U5_aga(Y, T, E, X, \==_in_ga(X, Y)) \==_in_ga(X0, X1) -> \==_out_ga(X0, X1) U5_aga(Y, T, E, X, \==_out_ga(X, Y)) -> U6_aga(Y, T, E, X, in_in_aga(E, X, T)) U6_aga(Y, T, E, X, in_out_aga(E, X, T)) -> in_out_aga(.(','(Y, T), E), X, T) U1_aga(E, X, T, in_out_aga(E, X, T)) -> type_out_aga(E, var(X), T) type_in_aga(E, apply(M, N), T) -> U2_aga(E, M, N, T, type_in_aga(E, M, arrow(S, T))) type_in_aga(E, lambda(X, M), arrow(S, T)) -> U4_aga(E, X, M, S, T, type_in_aga(.(','(X, S), E), M, T)) U4_aga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_aga(E, lambda(X, M), arrow(S, T)) U2_aga(E, M, N, T, type_out_aga(E, M, arrow(S, T))) -> U3_aga(E, M, N, T, type_in_aga(E, N, S)) U3_aga(E, M, N, T, type_out_aga(E, N, S)) -> type_out_aga(E, apply(M, N), T) U4_gga(E, X, M, S, T, type_out_aga(.(','(X, S), E), M, T)) -> type_out_gga(E, lambda(X, M), arrow(S, T)) U2_gga(E, M, N, T, type_out_gga(E, M, arrow(S, T))) -> U3_gga(E, M, N, T, type_in_gga(E, N, S)) U3_gga(E, M, N, T, type_out_gga(E, N, S)) -> type_out_gga(E, apply(M, N), T) The argument filtering Pi contains the following mapping: type_in_gga(x1, x2, x3) = type_in_gga(x1, x2) var(x1) = var(x1) U1_gga(x1, x2, x3, x4) = U1_gga(x1, x2, x4) in_in_gga(x1, x2, x3) = in_in_gga(x1, x2) .(x1, x2) = .(x1, x2) ','(x1, x2) = ','(x1, x2) in_out_gga(x1, x2, x3) = in_out_gga(x1, x2, x3) U5_gga(x1, x2, x3, x4, x5) = U5_gga(x1, x2, x3, x4, x5) \==_in_gg(x1, x2) = \==_in_gg(x1, x2) \==_out_gg(x1, x2) = \==_out_gg(x1, x2) U6_gga(x1, x2, x3, x4, x5) = U6_gga(x1, x2, x3, x4, x5) in_in_ggg(x1, x2, x3) = in_in_ggg(x1, x2, x3) in_out_ggg(x1, x2, x3) = in_out_ggg(x1, x2, x3) U5_ggg(x1, x2, x3, x4, x5) = U5_ggg(x1, x2, x3, x4, x5) U6_ggg(x1, x2, x3, x4, x5) = U6_ggg(x1, x2, x3, x4, x5) type_out_gga(x1, x2, x3) = type_out_gga(x1, x2) apply(x1, x2) = apply(x1, x2) U2_gga(x1, x2, x3, x4, x5) = U2_gga(x1, x2, x3, x5) lambda(x1, x2) = lambda(x1, x2) U4_gga(x1, x2, x3, x4, x5, x6) = U4_gga(x1, x2, x3, x6) type_in_aga(x1, x2, x3) = type_in_aga(x2) U1_aga(x1, x2, x3, x4) = U1_aga(x2, x4) in_in_aga(x1, x2, x3) = in_in_aga(x2) in_out_aga(x1, x2, x3) = in_out_aga(x2) U5_aga(x1, x2, x3, x4, x5) = U5_aga(x4, x5) \==_in_ga(x1, x2) = \==_in_ga(x1) \==_out_ga(x1, x2) = \==_out_ga(x1) U6_aga(x1, x2, x3, x4, x5) = U6_aga(x4, x5) type_out_aga(x1, x2, x3) = type_out_aga(x2) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x2, x3, x5) U4_aga(x1, x2, x3, x4, x5, x6) = U4_aga(x2, x3, x6) U3_aga(x1, x2, x3, x4, x5) = U3_aga(x2, x3, x5) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x1, x2, x3, x5) TYPE_IN_GGA(x1, x2, x3) = TYPE_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4, x5) = U2_GGA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (75) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: TYPE_IN_GGA(E, apply(M, N)) -> U2_GGA(E, M, N, type_in_gga(E, M)) U2_GGA(E, M, N, type_out_gga(E, M)) -> TYPE_IN_GGA(E, N) TYPE_IN_GGA(E, apply(M, N)) -> TYPE_IN_GGA(E, M) The TRS R consists of the following rules: type_in_gga(E, var(X)) -> U1_gga(E, X, in_in_gga(E, X)) in_in_gga(.(','(X, T), E), X) -> in_out_gga(.(','(X, T), E), X, T) in_in_gga(.(','(Y, T), E), X) -> U5_gga(Y, T, E, X, \==_in_gg(X, Y)) \==_in_gg(X0, X1) -> \==_out_gg(X0, X1) U5_gga(Y, T, E, X, \==_out_gg(X, Y)) -> U6_gga(Y, T, E, X, in_in_ggg(E, X, T)) in_in_ggg(.(','(X, T), E), X, T) -> in_out_ggg(.(','(X, T), E), X, T) in_in_ggg(.(','(Y, T), E), X, T) -> U5_ggg(Y, T, E, X, \==_in_gg(X, Y)) U5_ggg(Y, T, E, X, \==_out_gg(X, Y)) -> U6_ggg(Y, T, E, X, in_in_ggg(E, X, T)) U6_ggg(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_ggg(.(','(Y, T), E), X, T) U6_gga(Y, T, E, X, in_out_ggg(E, X, T)) -> in_out_gga(.(','(Y, T), E), X, T) U1_gga(E, X, in_out_gga(E, X, T)) -> type_out_gga(E, var(X)) type_in_gga(E, apply(M, N)) -> U2_gga(E, M, N, type_in_gga(E, M)) type_in_gga(E, lambda(X, M)) -> U4_gga(E, X, M, type_in_aga(M)) type_in_aga(var(X)) -> U1_aga(X, in_in_aga(X)) in_in_aga(X) -> in_out_aga(X) in_in_aga(X) -> U5_aga(X, \==_in_ga(X)) \==_in_ga(X0) -> \==_out_ga(X0) U5_aga(X, \==_out_ga(X)) -> U6_aga(X, in_in_aga(X)) U6_aga(X, in_out_aga(X)) -> in_out_aga(X) U1_aga(X, in_out_aga(X)) -> type_out_aga(var(X)) type_in_aga(apply(M, N)) -> U2_aga(M, N, type_in_aga(M)) type_in_aga(lambda(X, M)) -> U4_aga(X, M, type_in_aga(M)) U4_aga(X, M, type_out_aga(M)) -> type_out_aga(lambda(X, M)) U2_aga(M, N, type_out_aga(M)) -> U3_aga(M, N, type_in_aga(N)) U3_aga(M, N, type_out_aga(N)) -> type_out_aga(apply(M, N)) U4_gga(E, X, M, type_out_aga(M)) -> type_out_gga(E, lambda(X, M)) U2_gga(E, M, N, type_out_gga(E, M)) -> U3_gga(E, M, N, type_in_gga(E, N)) U3_gga(E, M, N, type_out_gga(E, N)) -> type_out_gga(E, apply(M, N)) The set Q consists of the following terms: type_in_gga(x0, x1) in_in_gga(x0, x1) \==_in_gg(x0, x1) U5_gga(x0, x1, x2, x3, x4) in_in_ggg(x0, x1, x2) U5_ggg(x0, x1, x2, x3, x4) U6_ggg(x0, x1, x2, x3, x4) U6_gga(x0, x1, x2, x3, x4) U1_gga(x0, x1, x2) type_in_aga(x0) in_in_aga(x0) \==_in_ga(x0) U5_aga(x0, x1) U6_aga(x0, x1) U1_aga(x0, x1) U4_aga(x0, x1, x2) U2_aga(x0, x1, x2) U3_aga(x0, x1, x2) U4_gga(x0, x1, x2, x3) U2_gga(x0, x1, x2, x3) U3_gga(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (77) 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_GGA(E, M, N, type_out_gga(E, M)) -> TYPE_IN_GGA(E, N) The graph contains the following edges 1 >= 1, 4 > 1, 3 >= 2 *TYPE_IN_GGA(E, apply(M, N)) -> TYPE_IN_GGA(E, M) The graph contains the following edges 1 >= 1, 2 > 2 *TYPE_IN_GGA(E, apply(M, N)) -> U2_GGA(E, M, N, type_in_gga(E, M)) The graph contains the following edges 1 >= 1, 2 > 2, 2 > 3 ---------------------------------------- (78) YES