/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern flatten(g,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) CutEliminatorProof [SOUND, 0 ms] (2) Prolog (3) PrologToPiTRSProof [SOUND, 0 ms] (4) PiTRS (5) DependencyPairsProof [EQUIVALENT, 0 ms] (6) PiDP (7) DependencyGraphProof [EQUIVALENT, 2 ms] (8) AND (9) PiDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) PiDP (12) PiDPToQDPProof [SOUND, 1 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) TransformationProof [EQUIVALENT, 0 ms] (21) QDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) QDP (24) QReductionProof [EQUIVALENT, 0 ms] (25) QDP (26) TransformationProof [EQUIVALENT, 0 ms] (27) QDP (28) TransformationProof [EQUIVALENT, 0 ms] (29) QDP (30) UsableRulesProof [EQUIVALENT, 0 ms] (31) QDP (32) QReductionProof [EQUIVALENT, 0 ms] (33) QDP (34) TransformationProof [EQUIVALENT, 0 ms] (35) QDP (36) UsableRulesProof [EQUIVALENT, 0 ms] (37) QDP (38) QReductionProof [EQUIVALENT, 0 ms] (39) QDP (40) PiDP (41) UsableRulesProof [EQUIVALENT, 0 ms] (42) PiDP (43) PrologToPiTRSProof [SOUND, 31 ms] (44) PiTRS (45) DependencyPairsProof [EQUIVALENT, 0 ms] (46) PiDP (47) DependencyGraphProof [EQUIVALENT, 0 ms] (48) AND (49) PiDP (50) UsableRulesProof [EQUIVALENT, 0 ms] (51) PiDP (52) PiDPToQDPProof [SOUND, 0 ms] (53) QDP (54) TransformationProof [EQUIVALENT, 0 ms] (55) QDP (56) UsableRulesProof [EQUIVALENT, 0 ms] (57) QDP (58) QReductionProof [EQUIVALENT, 0 ms] (59) QDP (60) TransformationProof [EQUIVALENT, 0 ms] (61) QDP (62) UsableRulesProof [EQUIVALENT, 0 ms] (63) QDP (64) QReductionProof [EQUIVALENT, 0 ms] (65) QDP (66) TransformationProof [EQUIVALENT, 0 ms] (67) QDP (68) TransformationProof [EQUIVALENT, 0 ms] (69) QDP (70) UsableRulesProof [EQUIVALENT, 0 ms] (71) QDP (72) QReductionProof [EQUIVALENT, 0 ms] (73) QDP (74) TransformationProof [EQUIVALENT, 0 ms] (75) QDP (76) UsableRulesProof [EQUIVALENT, 0 ms] (77) QDP (78) QReductionProof [EQUIVALENT, 0 ms] (79) QDP (80) PiDP (81) UsableRulesProof [EQUIVALENT, 0 ms] (82) PiDP (83) PrologToDTProblemTransformerProof [SOUND, 50 ms] (84) TRIPLES (85) TriplesToPiDPProof [SOUND, 0 ms] (86) PiDP (87) DependencyGraphProof [EQUIVALENT, 0 ms] (88) AND (89) PiDP (90) PiDPToQDPProof [SOUND, 18 ms] (91) QDP (92) NonTerminationLoopProof [COMPLETE, 0 ms] (93) NO (94) PiDP (95) PiDPToQDPProof [SOUND, 0 ms] (96) QDP (97) PrologToTRSTransformerProof [SOUND, 27 ms] (98) QTRS (99) Overlay + Local Confluence [EQUIVALENT, 0 ms] (100) QTRS (101) DependencyPairsProof [EQUIVALENT, 0 ms] (102) QDP (103) DependencyGraphProof [EQUIVALENT, 0 ms] (104) AND (105) QDP (106) UsableRulesProof [EQUIVALENT, 0 ms] (107) QDP (108) QReductionProof [EQUIVALENT, 0 ms] (109) QDP (110) NonTerminationLoopProof [COMPLETE, 0 ms] (111) NO (112) QDP (113) UsableRulesProof [EQUIVALENT, 0 ms] (114) QDP (115) QReductionProof [EQUIVALENT, 0 ms] (116) QDP (117) UsableRulesReductionPairsProof [EQUIVALENT, 6 ms] (118) QDP (119) PisEmptyProof [EQUIVALENT, 0 ms] (120) YES ---------------------------------------- (0) Obligation: Clauses: flatten(atom(X), Y) :- ','(!, eq(Y, .(X, []))). flatten(L, Y) :- ','(head(L, atom(H)), ','(!, ','(eq(Y, .(H, Z)), ','(tail(L, T), flatten(T, Z))))). flatten(L, X) :- ','(head(L, cons(U, V)), ','(tail(L, W), flatten(cons(U, cons(V, W)), X))). head(nil, X1). head(cons(H, X2), H). tail(nil, nil). tail(cons(X3, T), T). eq(X, X). Query: flatten(g,a) ---------------------------------------- (1) CutEliminatorProof (SOUND) Eliminated all cuts by simply ignoring them[PROLOG]. ---------------------------------------- (2) Obligation: Clauses: flatten(atom(X), Y) :- eq(Y, .(X, [])). flatten(L, Y) :- ','(head(L, atom(H)), ','(eq(Y, .(H, Z)), ','(tail(L, T), flatten(T, Z)))). flatten(L, X) :- ','(head(L, cons(U, V)), ','(tail(L, W), flatten(cons(U, cons(V, W)), X))). head(nil, X1). head(cons(H, X2), H). tail(nil, nil). tail(cons(X3, T), T). eq(X, X). Query: flatten(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: flatten_in_2: (b,f) (f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1, x2) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga(x1) U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg(x1, x2) cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U7_ga(x1, x2, x3, x4, x5) = U7_ga(x1, x5) U8_ga(x1, x2, x3) = U8_ga(x1, x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag(x2) U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (4) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1, x2) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga(x1) U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg(x1, x2) cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U7_ga(x1, x2, x3, x4, x5) = U7_ga(x1, x5) U8_ga(x1, x2, x3) = U8_ga(x1, x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag(x2) U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) ---------------------------------------- (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: FLATTEN_IN_GA(atom(X), Y) -> U1_GA(X, Y, eq_in_ag(Y, .(X, []))) FLATTEN_IN_GA(atom(X), Y) -> EQ_IN_AG(Y, .(X, [])) FLATTEN_IN_GA(L, Y) -> U2_GA(L, Y, head_in_gg(L, atom(H))) FLATTEN_IN_GA(L, Y) -> HEAD_IN_GG(L, atom(H)) U2_GA(L, Y, head_out_gg(L, atom(H))) -> U3_GA(L, Y, H, eq_in_aa(Y, .(H, Z))) U2_GA(L, Y, head_out_gg(L, atom(H))) -> EQ_IN_AA(Y, .(H, Z)) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_GA(L, Y, H, Z, tail_in_ga(L, T)) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> TAIL_IN_GA(L, T) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> U5_GA(L, Y, flatten_in_ga(T, Z)) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> FLATTEN_IN_GA(T, Z) FLATTEN_IN_GA(L, X) -> U6_GA(L, X, head_in_ga(L, cons(U, V))) FLATTEN_IN_GA(L, X) -> HEAD_IN_GA(L, cons(U, V)) U6_GA(L, X, head_out_ga(L, cons(U, V))) -> U7_GA(L, X, U, V, tail_in_ga(L, W)) U6_GA(L, X, head_out_ga(L, cons(U, V))) -> TAIL_IN_GA(L, W) U7_GA(L, X, U, V, tail_out_ga(L, W)) -> U8_GA(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U7_GA(L, X, U, V, tail_out_ga(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) FLATTEN_IN_AA(atom(X), Y) -> U1_AA(X, Y, eq_in_ag(Y, .(X, []))) FLATTEN_IN_AA(atom(X), Y) -> EQ_IN_AG(Y, .(X, [])) FLATTEN_IN_AA(L, Y) -> U2_AA(L, Y, head_in_ag(L, atom(H))) FLATTEN_IN_AA(L, Y) -> HEAD_IN_AG(L, atom(H)) U2_AA(L, Y, head_out_ag(L, atom(H))) -> U3_AA(L, Y, H, eq_in_aa(Y, .(H, Z))) U2_AA(L, Y, head_out_ag(L, atom(H))) -> EQ_IN_AA(Y, .(H, Z)) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_AA(L, Y, H, Z, tail_in_aa(L, T)) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> TAIL_IN_AA(L, T) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> U5_AA(L, Y, flatten_in_aa(T, Z)) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> FLATTEN_IN_AA(T, Z) FLATTEN_IN_AA(L, X) -> U6_AA(L, X, head_in_aa(L, cons(U, V))) FLATTEN_IN_AA(L, X) -> HEAD_IN_AA(L, cons(U, V)) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> U7_AA(L, X, U, V, tail_in_aa(L, W)) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> TAIL_IN_AA(L, W) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> U8_AA(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1, x2) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga(x1) U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg(x1, x2) cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U7_ga(x1, x2, x3, x4, x5) = U7_ga(x1, x5) U8_ga(x1, x2, x3) = U8_ga(x1, x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag(x2) U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) FLATTEN_IN_GA(x1, x2) = FLATTEN_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x3) EQ_IN_AG(x1, x2) = EQ_IN_AG(x2) U2_GA(x1, x2, x3) = U2_GA(x1, x3) HEAD_IN_GG(x1, x2) = HEAD_IN_GG(x1, x2) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) EQ_IN_AA(x1, x2) = EQ_IN_AA U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x5) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x1, x3) U6_GA(x1, x2, x3) = U6_GA(x1, x3) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U7_GA(x1, x2, x3, x4, x5) = U7_GA(x1, x5) U8_GA(x1, x2, x3) = U8_GA(x1, x3) FLATTEN_IN_AA(x1, x2) = FLATTEN_IN_AA U1_AA(x1, x2, x3) = U1_AA(x3) U2_AA(x1, x2, x3) = U2_AA(x3) HEAD_IN_AG(x1, x2) = HEAD_IN_AG(x2) U3_AA(x1, x2, x3, x4) = U3_AA(x4) U4_AA(x1, x2, x3, x4, x5) = U4_AA(x5) TAIL_IN_AA(x1, x2) = TAIL_IN_AA U5_AA(x1, x2, x3) = U5_AA(x3) U6_AA(x1, x2, x3) = U6_AA(x3) HEAD_IN_AA(x1, x2) = HEAD_IN_AA U7_AA(x1, x2, x3, x4, x5) = U7_AA(x5) U8_AA(x1, x2, x3) = U8_AA(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTEN_IN_GA(atom(X), Y) -> U1_GA(X, Y, eq_in_ag(Y, .(X, []))) FLATTEN_IN_GA(atom(X), Y) -> EQ_IN_AG(Y, .(X, [])) FLATTEN_IN_GA(L, Y) -> U2_GA(L, Y, head_in_gg(L, atom(H))) FLATTEN_IN_GA(L, Y) -> HEAD_IN_GG(L, atom(H)) U2_GA(L, Y, head_out_gg(L, atom(H))) -> U3_GA(L, Y, H, eq_in_aa(Y, .(H, Z))) U2_GA(L, Y, head_out_gg(L, atom(H))) -> EQ_IN_AA(Y, .(H, Z)) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_GA(L, Y, H, Z, tail_in_ga(L, T)) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> TAIL_IN_GA(L, T) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> U5_GA(L, Y, flatten_in_ga(T, Z)) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> FLATTEN_IN_GA(T, Z) FLATTEN_IN_GA(L, X) -> U6_GA(L, X, head_in_ga(L, cons(U, V))) FLATTEN_IN_GA(L, X) -> HEAD_IN_GA(L, cons(U, V)) U6_GA(L, X, head_out_ga(L, cons(U, V))) -> U7_GA(L, X, U, V, tail_in_ga(L, W)) U6_GA(L, X, head_out_ga(L, cons(U, V))) -> TAIL_IN_GA(L, W) U7_GA(L, X, U, V, tail_out_ga(L, W)) -> U8_GA(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U7_GA(L, X, U, V, tail_out_ga(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) FLATTEN_IN_AA(atom(X), Y) -> U1_AA(X, Y, eq_in_ag(Y, .(X, []))) FLATTEN_IN_AA(atom(X), Y) -> EQ_IN_AG(Y, .(X, [])) FLATTEN_IN_AA(L, Y) -> U2_AA(L, Y, head_in_ag(L, atom(H))) FLATTEN_IN_AA(L, Y) -> HEAD_IN_AG(L, atom(H)) U2_AA(L, Y, head_out_ag(L, atom(H))) -> U3_AA(L, Y, H, eq_in_aa(Y, .(H, Z))) U2_AA(L, Y, head_out_ag(L, atom(H))) -> EQ_IN_AA(Y, .(H, Z)) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_AA(L, Y, H, Z, tail_in_aa(L, T)) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> TAIL_IN_AA(L, T) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> U5_AA(L, Y, flatten_in_aa(T, Z)) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> FLATTEN_IN_AA(T, Z) FLATTEN_IN_AA(L, X) -> U6_AA(L, X, head_in_aa(L, cons(U, V))) FLATTEN_IN_AA(L, X) -> HEAD_IN_AA(L, cons(U, V)) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> U7_AA(L, X, U, V, tail_in_aa(L, W)) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> TAIL_IN_AA(L, W) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> U8_AA(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1, x2) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga(x1) U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg(x1, x2) cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U7_ga(x1, x2, x3, x4, x5) = U7_ga(x1, x5) U8_ga(x1, x2, x3) = U8_ga(x1, x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag(x2) U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) FLATTEN_IN_GA(x1, x2) = FLATTEN_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x3) EQ_IN_AG(x1, x2) = EQ_IN_AG(x2) U2_GA(x1, x2, x3) = U2_GA(x1, x3) HEAD_IN_GG(x1, x2) = HEAD_IN_GG(x1, x2) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) EQ_IN_AA(x1, x2) = EQ_IN_AA U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x5) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x1, x3) U6_GA(x1, x2, x3) = U6_GA(x1, x3) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U7_GA(x1, x2, x3, x4, x5) = U7_GA(x1, x5) U8_GA(x1, x2, x3) = U8_GA(x1, x3) FLATTEN_IN_AA(x1, x2) = FLATTEN_IN_AA U1_AA(x1, x2, x3) = U1_AA(x3) U2_AA(x1, x2, x3) = U2_AA(x3) HEAD_IN_AG(x1, x2) = HEAD_IN_AG(x2) U3_AA(x1, x2, x3, x4) = U3_AA(x4) U4_AA(x1, x2, x3, x4, x5) = U4_AA(x5) TAIL_IN_AA(x1, x2) = TAIL_IN_AA U5_AA(x1, x2, x3) = U5_AA(x3) U6_AA(x1, x2, x3) = U6_AA(x3) HEAD_IN_AA(x1, x2) = HEAD_IN_AA U7_AA(x1, x2, x3, x4, x5) = U7_AA(x5) U8_AA(x1, x2, x3) = U8_AA(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 21 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTEN_IN_AA(L, Y) -> U2_AA(L, Y, head_in_ag(L, atom(H))) U2_AA(L, Y, head_out_ag(L, atom(H))) -> U3_AA(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_AA(L, Y, H, Z, tail_in_aa(L, T)) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> FLATTEN_IN_AA(T, Z) FLATTEN_IN_AA(L, X) -> U6_AA(L, X, head_in_aa(L, cons(U, V))) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> U7_AA(L, X, U, V, tail_in_aa(L, W)) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1, x2) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga(x1) U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg(x1, x2) cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U7_ga(x1, x2, x3, x4, x5) = U7_ga(x1, x5) U8_ga(x1, x2, x3) = U8_ga(x1, x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag(x2) U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) FLATTEN_IN_AA(x1, x2) = FLATTEN_IN_AA U2_AA(x1, x2, x3) = U2_AA(x3) U3_AA(x1, x2, x3, x4) = U3_AA(x4) U4_AA(x1, x2, x3, x4, x5) = U4_AA(x5) U6_AA(x1, x2, x3) = U6_AA(x3) U7_AA(x1, x2, x3, x4, x5) = U7_AA(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: FLATTEN_IN_AA(L, Y) -> U2_AA(L, Y, head_in_ag(L, atom(H))) U2_AA(L, Y, head_out_ag(L, atom(H))) -> U3_AA(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_AA(L, Y, H, Z, tail_in_aa(L, T)) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> FLATTEN_IN_AA(T, Z) FLATTEN_IN_AA(L, X) -> U6_AA(L, X, head_in_aa(L, cons(U, V))) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> U7_AA(L, X, U, V, tail_in_aa(L, W)) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) The TRS R consists of the following rules: head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) eq_in_aa(X, X) -> eq_out_aa(X, X) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) The argument filtering Pi contains the following mapping: atom(x1) = atom .(x1, x2) = .(x2) nil = nil cons(x1, x2) = cons(x1, x2) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag(x2) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa FLATTEN_IN_AA(x1, x2) = FLATTEN_IN_AA U2_AA(x1, x2, x3) = U2_AA(x3) U3_AA(x1, x2, x3, x4) = U3_AA(x4) U4_AA(x1, x2, x3, x4, x5) = U4_AA(x5) U6_AA(x1, x2, x3) = U6_AA(x3) U7_AA(x1, x2, x3, x4, x5) = U7_AA(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: FLATTEN_IN_AA -> U2_AA(head_in_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_in_aa) U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA The TRS R consists of the following rules: head_in_ag(X1) -> head_out_ag(X1) eq_in_aa -> eq_out_aa tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: head_in_ag(x0) eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (14) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule FLATTEN_IN_AA -> U2_AA(head_in_ag(atom)) at position [0] we obtained the following new rules [LPAR04]: (FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)),FLATTEN_IN_AA -> U2_AA(head_out_ag(atom))) ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AA(head_out_ag(atom)) -> U3_AA(eq_in_aa) U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) The TRS R consists of the following rules: head_in_ag(X1) -> head_out_ag(X1) eq_in_aa -> eq_out_aa tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: head_in_ag(x0) eq_in_aa tail_in_aa head_in_aa 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: U2_AA(head_out_ag(atom)) -> U3_AA(eq_in_aa) U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa eq_in_aa -> eq_out_aa The set Q consists of the following terms: head_in_ag(x0) eq_in_aa tail_in_aa head_in_aa 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]. head_in_ag(x0) ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AA(head_out_ag(atom)) -> U3_AA(eq_in_aa) U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa eq_in_aa -> eq_out_aa The set Q consists of the following terms: eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (20) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U2_AA(head_out_ag(atom)) -> U3_AA(eq_in_aa) at position [0] we obtained the following new rules [LPAR04]: (U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa),U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa)) ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa eq_in_aa -> eq_out_aa The set Q consists of the following terms: eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (22) 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. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (24) 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]. eq_in_aa ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) at position [0] we obtained the following new rules [LPAR04]: (U3_AA(eq_out_aa) -> U4_AA(tail_out_aa),U3_AA(eq_out_aa) -> U4_AA(tail_out_aa)) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (28) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule FLATTEN_IN_AA -> U6_AA(head_in_aa) at position [0] we obtained the following new rules [LPAR04]: (FLATTEN_IN_AA -> U6_AA(head_out_aa),FLATTEN_IN_AA -> U6_AA(head_out_aa)) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (30) 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. ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa The set Q consists of the following terms: tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (32) 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]. head_in_aa ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa The set Q consists of the following terms: tail_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (34) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U6_AA(head_out_aa) -> U7_AA(tail_in_aa) at position [0] we obtained the following new rules [LPAR04]: (U6_AA(head_out_aa) -> U7_AA(tail_out_aa),U6_AA(head_out_aa) -> U7_AA(tail_out_aa)) ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) U6_AA(head_out_aa) -> U7_AA(tail_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa The set Q consists of the following terms: tail_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (36) 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. ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) U6_AA(head_out_aa) -> U7_AA(tail_out_aa) R is empty. The set Q consists of the following terms: tail_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (38) 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]. tail_in_aa ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag(atom)) U2_AA(head_out_ag(atom)) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) U6_AA(head_out_aa) -> U7_AA(tail_out_aa) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (40) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTEN_IN_GA(L, Y) -> U2_GA(L, Y, head_in_gg(L, atom(H))) U2_GA(L, Y, head_out_gg(L, atom(H))) -> U3_GA(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_GA(L, Y, H, Z, tail_in_ga(L, T)) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> FLATTEN_IN_GA(T, Z) The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1, x2) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga(x1) U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg(x1, x2) cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x1, x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) U5_ga(x1, x2, x3) = U5_ga(x1, x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga(x1) U7_ga(x1, x2, x3, x4, x5) = U7_ga(x1, x5) U8_ga(x1, x2, x3) = U8_ga(x1, x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag(x2) U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) FLATTEN_IN_GA(x1, x2) = FLATTEN_IN_GA(x1) U2_GA(x1, x2, x3) = U2_GA(x1, x3) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (41) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (42) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTEN_IN_GA(L, Y) -> U2_GA(L, Y, head_in_gg(L, atom(H))) U2_GA(L, Y, head_out_gg(L, atom(H))) -> U3_GA(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_GA(L, Y, H, Z, tail_in_ga(L, T)) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> FLATTEN_IN_GA(T, Z) The TRS R consists of the following rules: head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) eq_in_aa(X, X) -> eq_out_aa(X, X) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) The argument filtering Pi contains the following mapping: atom(x1) = atom .(x1, x2) = .(x2) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg(x1, x2) cons(x1, x2) = cons(x1, x2) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x1, x2) FLATTEN_IN_GA(x1, x2) = FLATTEN_IN_GA(x1) U2_GA(x1, x2, x3) = U2_GA(x1, x3) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (43) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: flatten_in_2: (b,f) (f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U5_ga(x1, x2, x3) = U5_ga(x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U7_ga(x1, x2, x3, x4, x5) = U7_ga(x5) U8_ga(x1, x2, x3) = U8_ga(x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (44) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U5_ga(x1, x2, x3) = U5_ga(x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U7_ga(x1, x2, x3, x4, x5) = U7_ga(x5) U8_ga(x1, x2, x3) = U8_ga(x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) ---------------------------------------- (45) 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: FLATTEN_IN_GA(atom(X), Y) -> U1_GA(X, Y, eq_in_ag(Y, .(X, []))) FLATTEN_IN_GA(atom(X), Y) -> EQ_IN_AG(Y, .(X, [])) FLATTEN_IN_GA(L, Y) -> U2_GA(L, Y, head_in_gg(L, atom(H))) FLATTEN_IN_GA(L, Y) -> HEAD_IN_GG(L, atom(H)) U2_GA(L, Y, head_out_gg(L, atom(H))) -> U3_GA(L, Y, H, eq_in_aa(Y, .(H, Z))) U2_GA(L, Y, head_out_gg(L, atom(H))) -> EQ_IN_AA(Y, .(H, Z)) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_GA(L, Y, H, Z, tail_in_ga(L, T)) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> TAIL_IN_GA(L, T) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> U5_GA(L, Y, flatten_in_ga(T, Z)) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> FLATTEN_IN_GA(T, Z) FLATTEN_IN_GA(L, X) -> U6_GA(L, X, head_in_ga(L, cons(U, V))) FLATTEN_IN_GA(L, X) -> HEAD_IN_GA(L, cons(U, V)) U6_GA(L, X, head_out_ga(L, cons(U, V))) -> U7_GA(L, X, U, V, tail_in_ga(L, W)) U6_GA(L, X, head_out_ga(L, cons(U, V))) -> TAIL_IN_GA(L, W) U7_GA(L, X, U, V, tail_out_ga(L, W)) -> U8_GA(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U7_GA(L, X, U, V, tail_out_ga(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) FLATTEN_IN_AA(atom(X), Y) -> U1_AA(X, Y, eq_in_ag(Y, .(X, []))) FLATTEN_IN_AA(atom(X), Y) -> EQ_IN_AG(Y, .(X, [])) FLATTEN_IN_AA(L, Y) -> U2_AA(L, Y, head_in_ag(L, atom(H))) FLATTEN_IN_AA(L, Y) -> HEAD_IN_AG(L, atom(H)) U2_AA(L, Y, head_out_ag(L, atom(H))) -> U3_AA(L, Y, H, eq_in_aa(Y, .(H, Z))) U2_AA(L, Y, head_out_ag(L, atom(H))) -> EQ_IN_AA(Y, .(H, Z)) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_AA(L, Y, H, Z, tail_in_aa(L, T)) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> TAIL_IN_AA(L, T) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> U5_AA(L, Y, flatten_in_aa(T, Z)) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> FLATTEN_IN_AA(T, Z) FLATTEN_IN_AA(L, X) -> U6_AA(L, X, head_in_aa(L, cons(U, V))) FLATTEN_IN_AA(L, X) -> HEAD_IN_AA(L, cons(U, V)) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> U7_AA(L, X, U, V, tail_in_aa(L, W)) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> TAIL_IN_AA(L, W) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> U8_AA(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U5_ga(x1, x2, x3) = U5_ga(x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U7_ga(x1, x2, x3, x4, x5) = U7_ga(x5) U8_ga(x1, x2, x3) = U8_ga(x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) FLATTEN_IN_GA(x1, x2) = FLATTEN_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x3) EQ_IN_AG(x1, x2) = EQ_IN_AG(x2) U2_GA(x1, x2, x3) = U2_GA(x1, x3) HEAD_IN_GG(x1, x2) = HEAD_IN_GG(x1, x2) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) EQ_IN_AA(x1, x2) = EQ_IN_AA U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x3) U6_GA(x1, x2, x3) = U6_GA(x1, x3) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U7_GA(x1, x2, x3, x4, x5) = U7_GA(x5) U8_GA(x1, x2, x3) = U8_GA(x3) FLATTEN_IN_AA(x1, x2) = FLATTEN_IN_AA U1_AA(x1, x2, x3) = U1_AA(x3) U2_AA(x1, x2, x3) = U2_AA(x3) HEAD_IN_AG(x1, x2) = HEAD_IN_AG(x2) U3_AA(x1, x2, x3, x4) = U3_AA(x4) U4_AA(x1, x2, x3, x4, x5) = U4_AA(x5) TAIL_IN_AA(x1, x2) = TAIL_IN_AA U5_AA(x1, x2, x3) = U5_AA(x3) U6_AA(x1, x2, x3) = U6_AA(x3) HEAD_IN_AA(x1, x2) = HEAD_IN_AA U7_AA(x1, x2, x3, x4, x5) = U7_AA(x5) U8_AA(x1, x2, x3) = U8_AA(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (46) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTEN_IN_GA(atom(X), Y) -> U1_GA(X, Y, eq_in_ag(Y, .(X, []))) FLATTEN_IN_GA(atom(X), Y) -> EQ_IN_AG(Y, .(X, [])) FLATTEN_IN_GA(L, Y) -> U2_GA(L, Y, head_in_gg(L, atom(H))) FLATTEN_IN_GA(L, Y) -> HEAD_IN_GG(L, atom(H)) U2_GA(L, Y, head_out_gg(L, atom(H))) -> U3_GA(L, Y, H, eq_in_aa(Y, .(H, Z))) U2_GA(L, Y, head_out_gg(L, atom(H))) -> EQ_IN_AA(Y, .(H, Z)) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_GA(L, Y, H, Z, tail_in_ga(L, T)) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> TAIL_IN_GA(L, T) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> U5_GA(L, Y, flatten_in_ga(T, Z)) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> FLATTEN_IN_GA(T, Z) FLATTEN_IN_GA(L, X) -> U6_GA(L, X, head_in_ga(L, cons(U, V))) FLATTEN_IN_GA(L, X) -> HEAD_IN_GA(L, cons(U, V)) U6_GA(L, X, head_out_ga(L, cons(U, V))) -> U7_GA(L, X, U, V, tail_in_ga(L, W)) U6_GA(L, X, head_out_ga(L, cons(U, V))) -> TAIL_IN_GA(L, W) U7_GA(L, X, U, V, tail_out_ga(L, W)) -> U8_GA(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U7_GA(L, X, U, V, tail_out_ga(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) FLATTEN_IN_AA(atom(X), Y) -> U1_AA(X, Y, eq_in_ag(Y, .(X, []))) FLATTEN_IN_AA(atom(X), Y) -> EQ_IN_AG(Y, .(X, [])) FLATTEN_IN_AA(L, Y) -> U2_AA(L, Y, head_in_ag(L, atom(H))) FLATTEN_IN_AA(L, Y) -> HEAD_IN_AG(L, atom(H)) U2_AA(L, Y, head_out_ag(L, atom(H))) -> U3_AA(L, Y, H, eq_in_aa(Y, .(H, Z))) U2_AA(L, Y, head_out_ag(L, atom(H))) -> EQ_IN_AA(Y, .(H, Z)) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_AA(L, Y, H, Z, tail_in_aa(L, T)) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> TAIL_IN_AA(L, T) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> U5_AA(L, Y, flatten_in_aa(T, Z)) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> FLATTEN_IN_AA(T, Z) FLATTEN_IN_AA(L, X) -> U6_AA(L, X, head_in_aa(L, cons(U, V))) FLATTEN_IN_AA(L, X) -> HEAD_IN_AA(L, cons(U, V)) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> U7_AA(L, X, U, V, tail_in_aa(L, W)) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> TAIL_IN_AA(L, W) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> U8_AA(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U5_ga(x1, x2, x3) = U5_ga(x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U7_ga(x1, x2, x3, x4, x5) = U7_ga(x5) U8_ga(x1, x2, x3) = U8_ga(x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) FLATTEN_IN_GA(x1, x2) = FLATTEN_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x3) EQ_IN_AG(x1, x2) = EQ_IN_AG(x2) U2_GA(x1, x2, x3) = U2_GA(x1, x3) HEAD_IN_GG(x1, x2) = HEAD_IN_GG(x1, x2) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) EQ_IN_AA(x1, x2) = EQ_IN_AA U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) TAIL_IN_GA(x1, x2) = TAIL_IN_GA(x1) U5_GA(x1, x2, x3) = U5_GA(x3) U6_GA(x1, x2, x3) = U6_GA(x1, x3) HEAD_IN_GA(x1, x2) = HEAD_IN_GA(x1) U7_GA(x1, x2, x3, x4, x5) = U7_GA(x5) U8_GA(x1, x2, x3) = U8_GA(x3) FLATTEN_IN_AA(x1, x2) = FLATTEN_IN_AA U1_AA(x1, x2, x3) = U1_AA(x3) U2_AA(x1, x2, x3) = U2_AA(x3) HEAD_IN_AG(x1, x2) = HEAD_IN_AG(x2) U3_AA(x1, x2, x3, x4) = U3_AA(x4) U4_AA(x1, x2, x3, x4, x5) = U4_AA(x5) TAIL_IN_AA(x1, x2) = TAIL_IN_AA U5_AA(x1, x2, x3) = U5_AA(x3) U6_AA(x1, x2, x3) = U6_AA(x3) HEAD_IN_AA(x1, x2) = HEAD_IN_AA U7_AA(x1, x2, x3, x4, x5) = U7_AA(x5) U8_AA(x1, x2, x3) = U8_AA(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (47) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 21 less nodes. ---------------------------------------- (48) Complex Obligation (AND) ---------------------------------------- (49) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTEN_IN_AA(L, Y) -> U2_AA(L, Y, head_in_ag(L, atom(H))) U2_AA(L, Y, head_out_ag(L, atom(H))) -> U3_AA(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_AA(L, Y, H, Z, tail_in_aa(L, T)) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> FLATTEN_IN_AA(T, Z) FLATTEN_IN_AA(L, X) -> U6_AA(L, X, head_in_aa(L, cons(U, V))) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> U7_AA(L, X, U, V, tail_in_aa(L, W)) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U5_ga(x1, x2, x3) = U5_ga(x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U7_ga(x1, x2, x3, x4, x5) = U7_ga(x5) U8_ga(x1, x2, x3) = U8_ga(x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) FLATTEN_IN_AA(x1, x2) = FLATTEN_IN_AA U2_AA(x1, x2, x3) = U2_AA(x3) U3_AA(x1, x2, x3, x4) = U3_AA(x4) U4_AA(x1, x2, x3, x4, x5) = U4_AA(x5) U6_AA(x1, x2, x3) = U6_AA(x3) U7_AA(x1, x2, x3, x4, x5) = U7_AA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (50) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (51) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTEN_IN_AA(L, Y) -> U2_AA(L, Y, head_in_ag(L, atom(H))) U2_AA(L, Y, head_out_ag(L, atom(H))) -> U3_AA(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_AA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_AA(L, Y, H, Z, tail_in_aa(L, T)) U4_AA(L, Y, H, Z, tail_out_aa(L, T)) -> FLATTEN_IN_AA(T, Z) FLATTEN_IN_AA(L, X) -> U6_AA(L, X, head_in_aa(L, cons(U, V))) U6_AA(L, X, head_out_aa(L, cons(U, V))) -> U7_AA(L, X, U, V, tail_in_aa(L, W)) U7_AA(L, X, U, V, tail_out_aa(L, W)) -> FLATTEN_IN_AA(cons(U, cons(V, W)), X) The TRS R consists of the following rules: head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) eq_in_aa(X, X) -> eq_out_aa(X, X) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) The argument filtering Pi contains the following mapping: atom(x1) = atom .(x1, x2) = .(x2) nil = nil cons(x1, x2) = cons(x1, x2) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa FLATTEN_IN_AA(x1, x2) = FLATTEN_IN_AA U2_AA(x1, x2, x3) = U2_AA(x3) U3_AA(x1, x2, x3, x4) = U3_AA(x4) U4_AA(x1, x2, x3, x4, x5) = U4_AA(x5) U6_AA(x1, x2, x3) = U6_AA(x3) U7_AA(x1, x2, x3, x4, x5) = U7_AA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (52) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: FLATTEN_IN_AA -> U2_AA(head_in_ag(atom)) U2_AA(head_out_ag) -> U3_AA(eq_in_aa) U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA The TRS R consists of the following rules: head_in_ag(X1) -> head_out_ag eq_in_aa -> eq_out_aa tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: head_in_ag(x0) eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (54) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule FLATTEN_IN_AA -> U2_AA(head_in_ag(atom)) at position [0] we obtained the following new rules [LPAR04]: (FLATTEN_IN_AA -> U2_AA(head_out_ag),FLATTEN_IN_AA -> U2_AA(head_out_ag)) ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AA(head_out_ag) -> U3_AA(eq_in_aa) U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) The TRS R consists of the following rules: head_in_ag(X1) -> head_out_ag eq_in_aa -> eq_out_aa tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: head_in_ag(x0) eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (56) 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. ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AA(head_out_ag) -> U3_AA(eq_in_aa) U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa eq_in_aa -> eq_out_aa The set Q consists of the following terms: head_in_ag(x0) eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (58) 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]. head_in_ag(x0) ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: U2_AA(head_out_ag) -> U3_AA(eq_in_aa) U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa eq_in_aa -> eq_out_aa The set Q consists of the following terms: eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (60) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U2_AA(head_out_ag) -> U3_AA(eq_in_aa) at position [0] we obtained the following new rules [LPAR04]: (U2_AA(head_out_ag) -> U3_AA(eq_out_aa),U2_AA(head_out_ag) -> U3_AA(eq_out_aa)) ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa eq_in_aa -> eq_out_aa The set Q consists of the following terms: eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (62) 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. ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: eq_in_aa tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (64) 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]. eq_in_aa ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (66) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U3_AA(eq_out_aa) -> U4_AA(tail_in_aa) at position [0] we obtained the following new rules [LPAR04]: (U3_AA(eq_out_aa) -> U4_AA(tail_out_aa),U3_AA(eq_out_aa) -> U4_AA(tail_out_aa)) ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U6_AA(head_in_aa) U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (68) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule FLATTEN_IN_AA -> U6_AA(head_in_aa) at position [0] we obtained the following new rules [LPAR04]: (FLATTEN_IN_AA -> U6_AA(head_out_aa),FLATTEN_IN_AA -> U6_AA(head_out_aa)) ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa head_in_aa -> head_out_aa The set Q consists of the following terms: tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (70) 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. ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa The set Q consists of the following terms: tail_in_aa head_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (72) 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]. head_in_aa ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U6_AA(head_out_aa) -> U7_AA(tail_in_aa) U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa The set Q consists of the following terms: tail_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (74) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule U6_AA(head_out_aa) -> U7_AA(tail_in_aa) at position [0] we obtained the following new rules [LPAR04]: (U6_AA(head_out_aa) -> U7_AA(tail_out_aa),U6_AA(head_out_aa) -> U7_AA(tail_out_aa)) ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) U6_AA(head_out_aa) -> U7_AA(tail_out_aa) The TRS R consists of the following rules: tail_in_aa -> tail_out_aa The set Q consists of the following terms: tail_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (76) 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. ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) U6_AA(head_out_aa) -> U7_AA(tail_out_aa) R is empty. The set Q consists of the following terms: tail_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (78) 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]. tail_in_aa ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: U4_AA(tail_out_aa) -> FLATTEN_IN_AA U7_AA(tail_out_aa) -> FLATTEN_IN_AA FLATTEN_IN_AA -> U2_AA(head_out_ag) U2_AA(head_out_ag) -> U3_AA(eq_out_aa) U3_AA(eq_out_aa) -> U4_AA(tail_out_aa) FLATTEN_IN_AA -> U6_AA(head_out_aa) U6_AA(head_out_aa) -> U7_AA(tail_out_aa) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (80) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTEN_IN_GA(L, Y) -> U2_GA(L, Y, head_in_gg(L, atom(H))) U2_GA(L, Y, head_out_gg(L, atom(H))) -> U3_GA(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_GA(L, Y, H, Z, tail_in_ga(L, T)) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> FLATTEN_IN_GA(T, Z) The TRS R consists of the following rules: flatten_in_ga(atom(X), Y) -> U1_ga(X, Y, eq_in_ag(Y, .(X, []))) eq_in_ag(X, X) -> eq_out_ag(X, X) U1_ga(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_ga(atom(X), Y) flatten_in_ga(L, Y) -> U2_ga(L, Y, head_in_gg(L, atom(H))) head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) U2_ga(L, Y, head_out_gg(L, atom(H))) -> U3_ga(L, Y, H, eq_in_aa(Y, .(H, Z))) eq_in_aa(X, X) -> eq_out_aa(X, X) U3_ga(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_ga(L, Y, H, Z, tail_in_ga(L, T)) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) U4_ga(L, Y, H, Z, tail_out_ga(L, T)) -> U5_ga(L, Y, flatten_in_ga(T, Z)) flatten_in_ga(L, X) -> U6_ga(L, X, head_in_ga(L, cons(U, V))) head_in_ga(nil, X1) -> head_out_ga(nil, X1) head_in_ga(cons(H, X2), H) -> head_out_ga(cons(H, X2), H) U6_ga(L, X, head_out_ga(L, cons(U, V))) -> U7_ga(L, X, U, V, tail_in_ga(L, W)) U7_ga(L, X, U, V, tail_out_ga(L, W)) -> U8_ga(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) flatten_in_aa(atom(X), Y) -> U1_aa(X, Y, eq_in_ag(Y, .(X, []))) U1_aa(X, Y, eq_out_ag(Y, .(X, []))) -> flatten_out_aa(atom(X), Y) flatten_in_aa(L, Y) -> U2_aa(L, Y, head_in_ag(L, atom(H))) head_in_ag(nil, X1) -> head_out_ag(nil, X1) head_in_ag(cons(H, X2), H) -> head_out_ag(cons(H, X2), H) U2_aa(L, Y, head_out_ag(L, atom(H))) -> U3_aa(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_aa(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_aa(L, Y, H, Z, tail_in_aa(L, T)) tail_in_aa(nil, nil) -> tail_out_aa(nil, nil) tail_in_aa(cons(X3, T), T) -> tail_out_aa(cons(X3, T), T) U4_aa(L, Y, H, Z, tail_out_aa(L, T)) -> U5_aa(L, Y, flatten_in_aa(T, Z)) flatten_in_aa(L, X) -> U6_aa(L, X, head_in_aa(L, cons(U, V))) head_in_aa(nil, X1) -> head_out_aa(nil, X1) head_in_aa(cons(H, X2), H) -> head_out_aa(cons(H, X2), H) U6_aa(L, X, head_out_aa(L, cons(U, V))) -> U7_aa(L, X, U, V, tail_in_aa(L, W)) U7_aa(L, X, U, V, tail_out_aa(L, W)) -> U8_aa(L, X, flatten_in_aa(cons(U, cons(V, W)), X)) U8_aa(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_aa(L, X) U5_aa(L, Y, flatten_out_aa(T, Z)) -> flatten_out_aa(L, Y) U8_ga(L, X, flatten_out_aa(cons(U, cons(V, W)), X)) -> flatten_out_ga(L, X) U5_ga(L, Y, flatten_out_ga(T, Z)) -> flatten_out_ga(L, Y) The argument filtering Pi contains the following mapping: flatten_in_ga(x1, x2) = flatten_in_ga(x1) atom(x1) = atom U1_ga(x1, x2, x3) = U1_ga(x3) eq_in_ag(x1, x2) = eq_in_ag(x2) eq_out_ag(x1, x2) = eq_out_ag(x1) .(x1, x2) = .(x2) [] = [] flatten_out_ga(x1, x2) = flatten_out_ga U2_ga(x1, x2, x3) = U2_ga(x1, x3) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg cons(x1, x2) = cons(x1, x2) U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa U4_ga(x1, x2, x3, x4, x5) = U4_ga(x5) tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) U5_ga(x1, x2, x3) = U5_ga(x3) U6_ga(x1, x2, x3) = U6_ga(x1, x3) head_in_ga(x1, x2) = head_in_ga(x1) head_out_ga(x1, x2) = head_out_ga U7_ga(x1, x2, x3, x4, x5) = U7_ga(x5) U8_ga(x1, x2, x3) = U8_ga(x3) flatten_in_aa(x1, x2) = flatten_in_aa U1_aa(x1, x2, x3) = U1_aa(x3) flatten_out_aa(x1, x2) = flatten_out_aa U2_aa(x1, x2, x3) = U2_aa(x3) head_in_ag(x1, x2) = head_in_ag(x2) head_out_ag(x1, x2) = head_out_ag U3_aa(x1, x2, x3, x4) = U3_aa(x4) U4_aa(x1, x2, x3, x4, x5) = U4_aa(x5) tail_in_aa(x1, x2) = tail_in_aa tail_out_aa(x1, x2) = tail_out_aa U5_aa(x1, x2, x3) = U5_aa(x3) U6_aa(x1, x2, x3) = U6_aa(x3) head_in_aa(x1, x2) = head_in_aa head_out_aa(x1, x2) = head_out_aa U7_aa(x1, x2, x3, x4, x5) = U7_aa(x5) U8_aa(x1, x2, x3) = U8_aa(x3) FLATTEN_IN_GA(x1, x2) = FLATTEN_IN_GA(x1) U2_GA(x1, x2, x3) = U2_GA(x1, x3) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (81) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (82) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTEN_IN_GA(L, Y) -> U2_GA(L, Y, head_in_gg(L, atom(H))) U2_GA(L, Y, head_out_gg(L, atom(H))) -> U3_GA(L, Y, H, eq_in_aa(Y, .(H, Z))) U3_GA(L, Y, H, eq_out_aa(Y, .(H, Z))) -> U4_GA(L, Y, H, Z, tail_in_ga(L, T)) U4_GA(L, Y, H, Z, tail_out_ga(L, T)) -> FLATTEN_IN_GA(T, Z) The TRS R consists of the following rules: head_in_gg(nil, X1) -> head_out_gg(nil, X1) head_in_gg(cons(H, X2), H) -> head_out_gg(cons(H, X2), H) eq_in_aa(X, X) -> eq_out_aa(X, X) tail_in_ga(nil, nil) -> tail_out_ga(nil, nil) tail_in_ga(cons(X3, T), T) -> tail_out_ga(cons(X3, T), T) The argument filtering Pi contains the following mapping: atom(x1) = atom .(x1, x2) = .(x2) head_in_gg(x1, x2) = head_in_gg(x1, x2) nil = nil head_out_gg(x1, x2) = head_out_gg cons(x1, x2) = cons(x1, x2) eq_in_aa(x1, x2) = eq_in_aa eq_out_aa(x1, x2) = eq_out_aa tail_in_ga(x1, x2) = tail_in_ga(x1) tail_out_ga(x1, x2) = tail_out_ga(x2) FLATTEN_IN_GA(x1, x2) = FLATTEN_IN_GA(x1) U2_GA(x1, x2, x3) = U2_GA(x1, x3) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (83) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(flatten (atom X) Y)", "(',' (!) (eq Y (. X ([]))))" ], [ "(flatten L Y)", "(',' (head L (atom H)) (',' (!) (',' (eq Y (. H Z)) (',' (tail L T) (flatten T Z)))))" ], [ "(flatten L X)", "(',' (head L (cons U V)) (',' (tail L W) (flatten (cons U (cons V W)) X)))" ], [ "(head (nil) X1)", null ], [ "(head (cons H X2) H)", null ], [ "(tail (nil) (nil))", null ], [ "(tail (cons X3 T) T)", null ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "44": { "goal": [{ "clause": 7, "scope": 2, "term": "(eq T7 (. T5 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "49": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "290": { "goal": [ { "clause": 4, "scope": 3, "term": "(',' (head T16 (atom X15)) (',' (!_1) (',' (eq T18 (. X15 X16)) (',' (tail T16 X17) (flatten X17 X16)))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten T16 T2)" } ], "kb": { "nonunifying": [ [ "(flatten T16 T2)", "(flatten (atom X6) X7)" ], [ "(head T16 (atom X15))", "(head (nil) X22)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": [ "X6", "X7", "X15", "X16", "X17", "X22" ], "exprvars": [] } }, "type": "Nodes", "293": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (eq T18 (. X23 X16)) (',' (tail (nil) X17) (flatten X17 X16)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X16", "X17", "X23" ], "exprvars": [] } }, "294": { "goal": [{ "clause": 7, "scope": 4, "term": "(',' (eq T18 (. X23 X16)) (',' (tail (nil) X17) (flatten X17 X16)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X16", "X17", "X23" ], "exprvars": [] } }, "591": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (eq T18 (. T38 X16)) (',' (tail (cons (atom T38) T37) X17) (flatten X17 X16)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T37" ], "free": [ "X16", "X17" ], "exprvars": [] } }, "295": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (nil) X17) (flatten X17 T28))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X17"], "exprvars": [] } }, "770": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (cons (cons T78 T79) T77) X81) (flatten (cons T78 (cons T79 X81)) T67))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T79", "T77" ], "free": ["X81"], "exprvars": [] } }, "111": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (head T16 (atom X15)) (',' (!_1) (',' (eq T18 (. X15 X16)) (',' (tail T16 X17) (flatten X17 X16)))))" }, { "clause": 2, "scope": 1, "term": "(flatten T16 T2)" } ], "kb": { "nonunifying": [[ "(flatten T16 T2)", "(flatten (atom X6) X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": [ "X6", "X7", "X15", "X16", "X17" ], "exprvars": [] } }, "771": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "652": { "goal": [{ "clause": -1, "scope": -1, "term": "(flatten T57 T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T57"], "free": [], "exprvars": [] } }, "773": { "goal": [ { "clause": 5, "scope": 9, "term": "(',' (tail (cons (cons T78 T79) T77) X81) (flatten (cons T78 (cons T79 X81)) T67))" }, { "clause": 6, "scope": 9, "term": "(',' (tail (cons (cons T78 T79) T77) X81) (flatten (cons T78 (cons T79 X81)) T67))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T79", "T77" ], "free": ["X81"], "exprvars": [] } }, "598": { "goal": [{ "clause": 7, "scope": 6, "term": "(',' (eq T18 (. T38 X16)) (',' (tail (cons (atom T38) T37) X17) (flatten X17 X16)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T37" ], "free": [ "X16", "X17" ], "exprvars": [] } }, "774": { "goal": [{ "clause": 6, "scope": 9, "term": "(',' (tail (cons (cons T78 T79) T77) X81) (flatten (cons T78 (cons T79 X81)) T67))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T78", "T79", "T77" ], "free": ["X81"], "exprvars": [] } }, "776": { "goal": [{ "clause": -1, "scope": -1, "term": "(flatten (cons T86 (cons T87 T88)) T67)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T86", "T87", "T88" ], "free": [], "exprvars": [] } }, "436": { "goal": [ { "clause": 5, "scope": 5, "term": "(',' (tail (nil) X17) (flatten X17 T28))" }, { "clause": 6, "scope": 5, "term": "(',' (tail (nil) X17) (flatten X17 T28))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X17"], "exprvars": [] } }, "613": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (cons (atom T46) T37) X17) (flatten X17 T48))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T37", "T46" ], "free": ["X17"], "exprvars": [] } }, "757": { "goal": [{ "clause": 2, "scope": 1, "term": "(flatten T16 T2)" }], "kb": { "nonunifying": [ [ "(flatten T16 T2)", "(flatten (atom X6) X7)" ], [ "(head T16 (atom X15))", "(head (nil) X22)" ], [ "(head T16 (atom X15))", "(head (cons X46 X47) X46)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": [ "X6", "X7", "X15", "X22", "X46", "X47" ], "exprvars": [] } }, "50": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "616": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "51": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "581": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (eq T18 (. T38 X16)) (',' (tail (cons (atom T38) T37) X17) (flatten X17 X16))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten (cons (atom T38) T37) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T37" ], "free": [ "X16", "X17" ], "exprvars": [] } }, "441": { "goal": [{ "clause": 5, "scope": 5, "term": "(',' (tail (nil) X17) (flatten X17 T28))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X17"], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(flatten T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "288": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (eq T18 (. X23 X16)) (',' (tail (nil) X17) (flatten X17 X16))))" }, { "clause": 4, "scope": 3, "term": "(',' (head (nil) (atom X15)) (',' (!_1) (',' (eq T18 (. X15 X16)) (',' (tail (nil) X17) (flatten X17 X16)))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten (nil) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X15", "X16", "X17", "X23" ], "exprvars": [] } }, "761": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T65 (cons X79 X80)) (',' (tail T65 X81) (flatten (cons X79 (cons X80 X81)) T67)))" }], "kb": { "nonunifying": [ [ "(flatten T65 T2)", "(flatten (atom X6) X7)" ], [ "(head T65 (atom X15))", "(head (nil) X22)" ], [ "(head T65 (atom X15))", "(head (cons X46 X47) X46)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T65"], "free": [ "X6", "X7", "X15", "X22", "X46", "X47", "X79", "X80", "X81" ], "exprvars": [] } }, "443": { "goal": [{ "clause": 6, "scope": 5, "term": "(',' (tail (nil) X17) (flatten X17 T28))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X17"], "exprvars": [] } }, "148": { "goal": [ { "clause": 3, "scope": 3, "term": "(',' (head T16 (atom X15)) (',' (!_1) (',' (eq T18 (. X15 X16)) (',' (tail T16 X17) (flatten X17 X16)))))" }, { "clause": 4, "scope": 3, "term": "(',' (head T16 (atom X15)) (',' (!_1) (',' (eq T18 (. X15 X16)) (',' (tail T16 X17) (flatten X17 X16)))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten T16 T2)" } ], "kb": { "nonunifying": [[ "(flatten T16 T2)", "(flatten (atom X6) X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": [ "X6", "X7", "X15", "X16", "X17" ], "exprvars": [] } }, "566": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "588": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten T16 T2)" } ], "kb": { "nonunifying": [ [ "(flatten T16 T2)", "(flatten (atom X6) X7)" ], [ "(head T16 (atom X15))", "(head (nil) X22)" ], [ "(head T16 (atom X15))", "(head (cons X46 X47) X46)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": [ "X6", "X7", "X15", "X22", "X46", "X47" ], "exprvars": [] } }, "764": { "goal": [ { "clause": 3, "scope": 8, "term": "(',' (head T65 (cons X79 X80)) (',' (tail T65 X81) (flatten (cons X79 (cons X80 X81)) T67)))" }, { "clause": 4, "scope": 8, "term": "(',' (head T65 (cons X79 X80)) (',' (tail T65 X81) (flatten (cons X79 (cons X80 X81)) T67)))" } ], "kb": { "nonunifying": [ [ "(flatten T65 T2)", "(flatten (atom X6) X7)" ], [ "(head T65 (atom X15))", "(head (nil) X22)" ], [ "(head T65 (atom X15))", "(head (cons X46 X47) X46)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T65"], "free": [ "X6", "X7", "X15", "X22", "X46", "X47", "X79", "X80", "X81" ], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(flatten T1 T2)" }, { "clause": 1, "scope": 1, "term": "(flatten T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flatten T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "765": { "goal": [{ "clause": 4, "scope": 8, "term": "(',' (head T65 (cons X79 X80)) (',' (tail T65 X81) (flatten (cons X79 (cons X80 X81)) T67)))" }], "kb": { "nonunifying": [ [ "(flatten T65 T2)", "(flatten (atom X6) X7)" ], [ "(head T65 (atom X15))", "(head (nil) X22)" ], [ "(head T65 (atom X15))", "(head (cons X46 X47) X46)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T65"], "free": [ "X6", "X7", "X15", "X22", "X46", "X47", "X79", "X80", "X81" ], "exprvars": [] } }, "623": { "goal": [ { "clause": 5, "scope": 7, "term": "(',' (tail (cons (atom T46) T37) X17) (flatten X17 T48))" }, { "clause": 6, "scope": 7, "term": "(',' (tail (cons (atom T46) T37) X17) (flatten X17 T48))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T37", "T46" ], "free": ["X17"], "exprvars": [] } }, "449": { "goal": [{ "clause": -1, "scope": -1, "term": "(flatten (nil) T28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "627": { "goal": [{ "clause": 6, "scope": 7, "term": "(',' (tail (cons (atom T46) T37) X17) (flatten X17 T48))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T37", "T46" ], "free": ["X17"], "exprvars": [] } }, "309": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "41": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (eq T7 (. T5 ([]))))" }, { "clause": 1, "scope": 1, "term": "(flatten (atom T5) T2)" }, { "clause": 2, "scope": 1, "term": "(flatten (atom T5) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "42": { "goal": [ { "clause": 1, "scope": 1, "term": "(flatten T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flatten T1 T2)" } ], "kb": { "nonunifying": [[ "(flatten T1 T2)", "(flatten (atom X6) X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X6", "X7" ], "exprvars": [] } }, "43": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T7 (. T5 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 41, "label": "EVAL with clause\nflatten(atom(X6), X7) :- ','(!_1, eq(X7, .(X6, []))).\nand substitutionX6 -> T5,\nT1 -> atom(T5),\nT2 -> T7,\nX7 -> T7,\nT6 -> T7" }, { "from": 6, "to": 42, "label": "EVAL-BACKTRACK" }, { "from": 41, "to": 43, "label": "CUT" }, { "from": 42, "to": 111, "label": "ONLY EVAL with clause\nflatten(X13, X14) :- ','(head(X13, atom(X15)), ','(!_1, ','(eq(X14, .(X15, X16)), ','(tail(X13, X17), flatten(X17, X16))))).\nand substitutionT1 -> T16,\nX13 -> T16,\nT2 -> T18,\nX14 -> T18,\nT17 -> T18" }, { "from": 43, "to": 44, "label": "CASE" }, { "from": 44, "to": 49, "label": "EVAL with clause\neq(X10, X10).\nand substitutionT7 -> .(T13, []),\nX10 -> .(T13, []),\nT5 -> T13,\nT12 -> .(T13, [])" }, { "from": 44, "to": 50, "label": "EVAL-BACKTRACK" }, { "from": 49, "to": 51, "label": "SUCCESS" }, { "from": 111, "to": 148, "label": "CASE" }, { "from": 148, "to": 288, "label": "EVAL with clause\nhead(nil, X22).\nand substitutionT16 -> nil,\nX15 -> X23,\nX22 -> atom(X23)" }, { "from": 148, "to": 290, "label": "EVAL-BACKTRACK" }, { "from": 288, "to": 293, "label": "CUT" }, { "from": 290, "to": 581, "label": "EVAL with clause\nhead(cons(X46, X47), X46).\nand substitutionX46 -> atom(T38),\nX47 -> T37,\nT16 -> cons(atom(T38), T37),\nX15 -> T38,\nT36 -> atom(T38)" }, { "from": 290, "to": 588, "label": "EVAL-BACKTRACK" }, { "from": 293, "to": 294, "label": "CASE" }, { "from": 294, "to": 295, "label": "EVAL with clause\neq(X30, X30).\nand substitutionT18 -> .(T26, T28),\nX30 -> .(T26, T28),\nX23 -> T26,\nX16 -> T28,\nT25 -> .(T26, T28),\nT27 -> T28" }, { "from": 294, "to": 309, "label": "EVAL-BACKTRACK" }, { "from": 295, "to": 436, "label": "CASE" }, { "from": 436, "to": 441, "label": "PARALLEL" }, { "from": 436, "to": 443, "label": "PARALLEL" }, { "from": 441, "to": 449, "label": "ONLY EVAL with clause\ntail(nil, nil).\nand substitutionX17 -> nil" }, { "from": 443, "to": 566, "label": "BACKTRACK\nfor clause: tail(cons(X3, T), T)because of non-unification" }, { "from": 449, "to": 2, "label": "INSTANCE with matching:\nT1 -> nil\nT2 -> T28" }, { "from": 581, "to": 591, "label": "CUT" }, { "from": 588, "to": 757, "label": "FAILURE" }, { "from": 591, "to": 598, "label": "CASE" }, { "from": 598, "to": 613, "label": "EVAL with clause\neq(X54, X54).\nand substitutionT18 -> .(T46, T48),\nX54 -> .(T46, T48),\nT38 -> T46,\nX16 -> T48,\nT45 -> .(T46, T48),\nT47 -> T48" }, { "from": 598, "to": 616, "label": "EVAL-BACKTRACK" }, { "from": 613, "to": 623, "label": "CASE" }, { "from": 623, "to": 627, "label": "BACKTRACK\nfor clause: tail(nil, nil)because of non-unification" }, { "from": 627, "to": 652, "label": "ONLY EVAL with clause\ntail(cons(X64, X65), X65).\nand substitutionT46 -> T56,\nX64 -> atom(T56),\nT37 -> T57,\nX65 -> T57,\nX17 -> T57" }, { "from": 652, "to": 2, "label": "INSTANCE with matching:\nT1 -> T57\nT2 -> T48" }, { "from": 757, "to": 761, "label": "ONLY EVAL with clause\nflatten(X77, X78) :- ','(head(X77, cons(X79, X80)), ','(tail(X77, X81), flatten(cons(X79, cons(X80, X81)), X78))).\nand substitutionT16 -> T65,\nX77 -> T65,\nT2 -> T67,\nX78 -> T67,\nT66 -> T67" }, { "from": 761, "to": 764, "label": "CASE" }, { "from": 764, "to": 765, "label": "BACKTRACK\nfor clause: head(nil, X1)\nwith clash: (head(T65, atom(X15)), head(nil, X22))" }, { "from": 765, "to": 770, "label": "EVAL with clause\nhead(cons(X91, X92), X91).\nand substitutionX91 -> cons(T78, T79),\nX92 -> T77,\nT65 -> cons(cons(T78, T79), T77),\nX79 -> T78,\nX80 -> T79,\nT76 -> cons(T78, T79)" }, { "from": 765, "to": 771, "label": "EVAL-BACKTRACK" }, { "from": 770, "to": 773, "label": "CASE" }, { "from": 773, "to": 774, "label": "BACKTRACK\nfor clause: tail(nil, nil)because of non-unification" }, { "from": 774, "to": 776, "label": "ONLY EVAL with clause\ntail(cons(X101, X102), X102).\nand substitutionT78 -> T86,\nT79 -> T87,\nX101 -> cons(T86, T87),\nT77 -> T88,\nX102 -> T88,\nX81 -> T88" }, { "from": 776, "to": 2, "label": "INSTANCE with matching:\nT1 -> cons(T86, cons(T87, T88))\nT2 -> T67" } ], "type": "Graph" } } ---------------------------------------- (84) Obligation: Triples: flattenA(nil, .(X1, X2)) :- flattenA(nil, X2). flattenA(cons(atom(X1), X2), .(X1, X3)) :- flattenA(X2, X3). flattenA(cons(cons(X1, X2), X3), X4) :- flattenA(cons(X1, cons(X2, X3)), X4). Clauses: flattencA(atom(X1), .(X1, [])). flattencA(nil, .(X1, X2)) :- flattencA(nil, X2). flattencA(cons(atom(X1), X2), .(X1, X3)) :- flattencA(X2, X3). flattencA(cons(cons(X1, X2), X3), X4) :- flattencA(cons(X1, cons(X2, X3)), X4). Afs: flattenA(x1, x2) = flattenA(x1) ---------------------------------------- (85) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: flattenA_in_2: (b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: FLATTENA_IN_GA(nil, .(X1, X2)) -> U1_GA(X1, X2, flattenA_in_ga(nil, X2)) FLATTENA_IN_GA(nil, .(X1, X2)) -> FLATTENA_IN_GA(nil, X2) FLATTENA_IN_GA(cons(atom(X1), X2), .(X1, X3)) -> U2_GA(X1, X2, X3, flattenA_in_ga(X2, X3)) FLATTENA_IN_GA(cons(atom(X1), X2), .(X1, X3)) -> FLATTENA_IN_GA(X2, X3) FLATTENA_IN_GA(cons(cons(X1, X2), X3), X4) -> U3_GA(X1, X2, X3, X4, flattenA_in_ga(cons(X1, cons(X2, X3)), X4)) FLATTENA_IN_GA(cons(cons(X1, X2), X3), X4) -> FLATTENA_IN_GA(cons(X1, cons(X2, X3)), X4) R is empty. The argument filtering Pi contains the following mapping: flattenA_in_ga(x1, x2) = flattenA_in_ga(x1) nil = nil cons(x1, x2) = cons(x1, x2) atom(x1) = atom(x1) .(x1, x2) = .(x2) FLATTENA_IN_GA(x1, x2) = FLATTENA_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x3) U2_GA(x1, x2, x3, x4) = U2_GA(x1, x2, x4) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (86) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTENA_IN_GA(nil, .(X1, X2)) -> U1_GA(X1, X2, flattenA_in_ga(nil, X2)) FLATTENA_IN_GA(nil, .(X1, X2)) -> FLATTENA_IN_GA(nil, X2) FLATTENA_IN_GA(cons(atom(X1), X2), .(X1, X3)) -> U2_GA(X1, X2, X3, flattenA_in_ga(X2, X3)) FLATTENA_IN_GA(cons(atom(X1), X2), .(X1, X3)) -> FLATTENA_IN_GA(X2, X3) FLATTENA_IN_GA(cons(cons(X1, X2), X3), X4) -> U3_GA(X1, X2, X3, X4, flattenA_in_ga(cons(X1, cons(X2, X3)), X4)) FLATTENA_IN_GA(cons(cons(X1, X2), X3), X4) -> FLATTENA_IN_GA(cons(X1, cons(X2, X3)), X4) R is empty. The argument filtering Pi contains the following mapping: flattenA_in_ga(x1, x2) = flattenA_in_ga(x1) nil = nil cons(x1, x2) = cons(x1, x2) atom(x1) = atom(x1) .(x1, x2) = .(x2) FLATTENA_IN_GA(x1, x2) = FLATTENA_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x3) U2_GA(x1, x2, x3, x4) = U2_GA(x1, x2, x4) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (87) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (88) Complex Obligation (AND) ---------------------------------------- (89) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTENA_IN_GA(nil, .(X1, X2)) -> FLATTENA_IN_GA(nil, X2) R is empty. The argument filtering Pi contains the following mapping: nil = nil .(x1, x2) = .(x2) FLATTENA_IN_GA(x1, x2) = FLATTENA_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (90) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (91) Obligation: Q DP problem: The TRS P consists of the following rules: FLATTENA_IN_GA(nil) -> FLATTENA_IN_GA(nil) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (92) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = FLATTENA_IN_GA(nil) evaluates to t =FLATTENA_IN_GA(nil) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from FLATTENA_IN_GA(nil) to FLATTENA_IN_GA(nil). ---------------------------------------- (93) NO ---------------------------------------- (94) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATTENA_IN_GA(cons(cons(X1, X2), X3), X4) -> FLATTENA_IN_GA(cons(X1, cons(X2, X3)), X4) FLATTENA_IN_GA(cons(atom(X1), X2), .(X1, X3)) -> FLATTENA_IN_GA(X2, X3) R is empty. The argument filtering Pi contains the following mapping: cons(x1, x2) = cons(x1, x2) atom(x1) = atom(x1) .(x1, x2) = .(x2) FLATTENA_IN_GA(x1, x2) = FLATTENA_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (95) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: FLATTENA_IN_GA(cons(cons(X1, X2), X3)) -> FLATTENA_IN_GA(cons(X1, cons(X2, X3))) FLATTENA_IN_GA(cons(atom(X1), X2)) -> FLATTENA_IN_GA(X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (97) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 1, "program": { "directives": [], "clauses": [ [ "(flatten (atom X) Y)", "(',' (!) (eq Y (. X ([]))))" ], [ "(flatten L Y)", "(',' (head L (atom H)) (',' (!) (',' (eq Y (. H Z)) (',' (tail L T) (flatten T Z)))))" ], [ "(flatten L X)", "(',' (head L (cons U V)) (',' (tail L W) (flatten (cons U (cons V W)) X)))" ], [ "(head (nil) X1)", null ], [ "(head (cons H X2) H)", null ], [ "(tail (nil) (nil))", null ], [ "(tail (cons X3 T) T)", null ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "type": "Nodes", "772": { "goal": [{ "clause": -1, "scope": -1, "term": "(flatten T62 T53)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T62"], "free": [], "exprvars": [] } }, "333": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (nil) X24) (flatten X24 T33))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X24"], "exprvars": [] } }, "775": { "goal": [{ "clause": 2, "scope": 1, "term": "(flatten T21 T2)" }], "kb": { "nonunifying": [ [ "(flatten T21 T2)", "(flatten (atom X8) X9)" ], [ "(head T21 (atom X22))", "(head (nil) X29)" ], [ "(head T21 (atom X22))", "(head (cons X53 X54) X53)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [ "X8", "X9", "X22", "X29", "X53", "X54" ], "exprvars": [] } }, "336": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "315": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (head T21 (atom X22)) (',' (!_1) (',' (eq T23 (. X22 X23)) (',' (tail T21 X24) (flatten X24 X23)))))" }, { "clause": 2, "scope": 1, "term": "(flatten T21 T2)" } ], "kb": { "nonunifying": [[ "(flatten T21 T2)", "(flatten (atom X8) X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [ "X8", "X9", "X22", "X23", "X24" ], "exprvars": [] } }, "777": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T70 (cons X86 X87)) (',' (tail T70 X88) (flatten (cons X86 (cons X87 X88)) T72)))" }], "kb": { "nonunifying": [ [ "(flatten T70 T2)", "(flatten (atom X8) X9)" ], [ "(head T70 (atom X22))", "(head (nil) X29)" ], [ "(head T70 (atom X22))", "(head (cons X53 X54) X53)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T70"], "free": [ "X8", "X9", "X22", "X29", "X53", "X54", "X86", "X87", "X88" ], "exprvars": [] } }, "316": { "goal": [ { "clause": 3, "scope": 3, "term": "(',' (head T21 (atom X22)) (',' (!_1) (',' (eq T23 (. X22 X23)) (',' (tail T21 X24) (flatten X24 X23)))))" }, { "clause": 4, "scope": 3, "term": "(',' (head T21 (atom X22)) (',' (!_1) (',' (eq T23 (. X22 X23)) (',' (tail T21 X24) (flatten X24 X23)))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten T21 T2)" } ], "kb": { "nonunifying": [[ "(flatten T21 T2)", "(flatten (atom X8) X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [ "X8", "X9", "X22", "X23", "X24" ], "exprvars": [] } }, "778": { "goal": [ { "clause": 3, "scope": 8, "term": "(',' (head T70 (cons X86 X87)) (',' (tail T70 X88) (flatten (cons X86 (cons X87 X88)) T72)))" }, { "clause": 4, "scope": 8, "term": "(',' (head T70 (cons X86 X87)) (',' (tail T70 X88) (flatten (cons X86 (cons X87 X88)) T72)))" } ], "kb": { "nonunifying": [ [ "(flatten T70 T2)", "(flatten (atom X8) X9)" ], [ "(head T70 (atom X22))", "(head (nil) X29)" ], [ "(head T70 (atom X22))", "(head (cons X53 X54) X53)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T70"], "free": [ "X8", "X9", "X22", "X29", "X53", "X54", "X86", "X87", "X88" ], "exprvars": [] } }, "317": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (eq T23 (. X30 X23)) (',' (tail (nil) X24) (flatten X24 X23))))" }, { "clause": 4, "scope": 3, "term": "(',' (head (nil) (atom X22)) (',' (!_1) (',' (eq T23 (. X22 X23)) (',' (tail (nil) X24) (flatten X24 X23)))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten (nil) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X22", "X23", "X24", "X30" ], "exprvars": [] } }, "779": { "goal": [{ "clause": 4, "scope": 8, "term": "(',' (head T70 (cons X86 X87)) (',' (tail T70 X88) (flatten (cons X86 (cons X87 X88)) T72)))" }], "kb": { "nonunifying": [ [ "(flatten T70 T2)", "(flatten (atom X8) X9)" ], [ "(head T70 (atom X22))", "(head (nil) X29)" ], [ "(head T70 (atom X22))", "(head (cons X53 X54) X53)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T70"], "free": [ "X8", "X9", "X22", "X29", "X53", "X54", "X86", "X87", "X88" ], "exprvars": [] } }, "318": { "goal": [ { "clause": 4, "scope": 3, "term": "(',' (head T21 (atom X22)) (',' (!_1) (',' (eq T23 (. X22 X23)) (',' (tail T21 X24) (flatten X24 X23)))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten T21 T2)" } ], "kb": { "nonunifying": [ [ "(flatten T21 T2)", "(flatten (atom X8) X9)" ], [ "(head T21 (atom X22))", "(head (nil) X29)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [ "X8", "X9", "X22", "X23", "X24", "X29" ], "exprvars": [] } }, "758": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "319": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (eq T23 (. X30 X23)) (',' (tail (nil) X24) (flatten X24 X23)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X23", "X24", "X30" ], "exprvars": [] } }, "759": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (eq T23 (. T43 X23)) (',' (tail (cons (atom T43) T42) X24) (flatten X24 X23))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten (cons (atom T43) T42) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T42" ], "free": [ "X23", "X24" ], "exprvars": [] } }, "280": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (eq T9 (. T7 ([]))))" }, { "clause": 1, "scope": 1, "term": "(flatten (atom T7) T2)" }, { "clause": 2, "scope": 1, "term": "(flatten (atom T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "281": { "goal": [ { "clause": 1, "scope": 1, "term": "(flatten T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flatten T1 T2)" } ], "kb": { "nonunifying": [[ "(flatten T1 T2)", "(flatten (atom X8) X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X8", "X9" ], "exprvars": [] } }, "282": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T9 (. T7 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "283": { "goal": [{ "clause": 7, "scope": 2, "term": "(eq T9 (. T7 ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "284": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "285": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "340": { "goal": [ { "clause": 5, "scope": 5, "term": "(',' (tail (nil) X24) (flatten X24 T33))" }, { "clause": 6, "scope": 5, "term": "(',' (tail (nil) X24) (flatten X24 T33))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X24"], "exprvars": [] } }, "780": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (cons (cons T83 T84) T82) X88) (flatten (cons T83 (cons T84 X88)) T72))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84", "T82" ], "free": ["X88"], "exprvars": [] } }, "286": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "341": { "goal": [{ "clause": 5, "scope": 5, "term": "(',' (tail (nil) X24) (flatten X24 T33))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X24"], "exprvars": [] } }, "781": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(flatten T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "342": { "goal": [{ "clause": 6, "scope": 5, "term": "(',' (tail (nil) X24) (flatten X24 T33))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X24"], "exprvars": [] } }, "760": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flatten T21 T2)" } ], "kb": { "nonunifying": [ [ "(flatten T21 T2)", "(flatten (atom X8) X9)" ], [ "(head T21 (atom X22))", "(head (nil) X29)" ], [ "(head T21 (atom X22))", "(head (cons X53 X54) X53)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [ "X8", "X9", "X22", "X29", "X53", "X54" ], "exprvars": [] } }, "782": { "goal": [ { "clause": 5, "scope": 9, "term": "(',' (tail (cons (cons T83 T84) T82) X88) (flatten (cons T83 (cons T84 X88)) T72))" }, { "clause": 6, "scope": 9, "term": "(',' (tail (cons (cons T83 T84) T82) X88) (flatten (cons T83 (cons T84 X88)) T72))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84", "T82" ], "free": ["X88"], "exprvars": [] } }, "783": { "goal": [{ "clause": 6, "scope": 9, "term": "(',' (tail (cons (cons T83 T84) T82) X88) (flatten (cons T83 (cons T84 X88)) T72))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T83", "T84", "T82" ], "free": ["X88"], "exprvars": [] } }, "322": { "goal": [{ "clause": 7, "scope": 4, "term": "(',' (eq T23 (. X30 X23)) (',' (tail (nil) X24) (flatten X24 X23)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X23", "X24", "X30" ], "exprvars": [] } }, "344": { "goal": [{ "clause": -1, "scope": -1, "term": "(flatten (nil) T33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "762": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (eq T23 (. T43 X23)) (',' (tail (cons (atom T43) T42) X24) (flatten X24 X23)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T42" ], "free": [ "X23", "X24" ], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(flatten T1 T2)" }, { "clause": 1, "scope": 1, "term": "(flatten T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flatten T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "763": { "goal": [{ "clause": 7, "scope": 6, "term": "(',' (eq T23 (. T43 X23)) (',' (tail (cons (atom T43) T42) X24) (flatten X24 X23)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T42" ], "free": [ "X23", "X24" ], "exprvars": [] } }, "766": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (cons (atom T51) T42) X24) (flatten X24 T53))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T42", "T51" ], "free": ["X24"], "exprvars": [] } }, "767": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "768": { "goal": [ { "clause": 5, "scope": 7, "term": "(',' (tail (cons (atom T51) T42) X24) (flatten X24 T53))" }, { "clause": 6, "scope": 7, "term": "(',' (tail (cons (atom T51) T42) X24) (flatten X24 T53))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T42", "T51" ], "free": ["X24"], "exprvars": [] } }, "769": { "goal": [{ "clause": 6, "scope": 7, "term": "(',' (tail (cons (atom T51) T42) X24) (flatten X24 T53))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T42", "T51" ], "free": ["X24"], "exprvars": [] } }, "804": { "goal": [{ "clause": -1, "scope": -1, "term": "(flatten (cons T91 (cons T92 T93)) T72)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T91", "T92", "T93" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 280, "label": "EVAL with clause\nflatten(atom(X8), X9) :- ','(!_1, eq(X9, .(X8, []))).\nand substitutionX8 -> T7,\nT1 -> atom(T7),\nT2 -> T9,\nX9 -> T9,\nT8 -> T9" }, { "from": 4, "to": 281, "label": "EVAL-BACKTRACK" }, { "from": 280, "to": 282, "label": "CUT" }, { "from": 281, "to": 315, "label": "ONLY EVAL with clause\nflatten(X20, X21) :- ','(head(X20, atom(X22)), ','(!_1, ','(eq(X21, .(X22, X23)), ','(tail(X20, X24), flatten(X24, X23))))).\nand substitutionT1 -> T21,\nX20 -> T21,\nT2 -> T23,\nX21 -> T23,\nT22 -> T23" }, { "from": 282, "to": 283, "label": "CASE" }, { "from": 283, "to": 284, "label": "EVAL with clause\neq(X12, X12).\nand substitutionT9 -> .(T15, []),\nX12 -> .(T15, []),\nT7 -> T15,\nT14 -> .(T15, [])" }, { "from": 283, "to": 285, "label": "EVAL-BACKTRACK" }, { "from": 284, "to": 286, "label": "SUCCESS" }, { "from": 315, "to": 316, "label": "CASE" }, { "from": 316, "to": 317, "label": "EVAL with clause\nhead(nil, X29).\nand substitutionT21 -> nil,\nX22 -> X30,\nX29 -> atom(X30)" }, { "from": 316, "to": 318, "label": "EVAL-BACKTRACK" }, { "from": 317, "to": 319, "label": "CUT" }, { "from": 318, "to": 759, "label": "EVAL with clause\nhead(cons(X53, X54), X53).\nand substitutionX53 -> atom(T43),\nX54 -> T42,\nT21 -> cons(atom(T43), T42),\nX22 -> T43,\nT41 -> atom(T43)" }, { "from": 318, "to": 760, "label": "EVAL-BACKTRACK" }, { "from": 319, "to": 322, "label": "CASE" }, { "from": 322, "to": 333, "label": "EVAL with clause\neq(X37, X37).\nand substitutionT23 -> .(T31, T33),\nX37 -> .(T31, T33),\nX30 -> T31,\nX23 -> T33,\nT30 -> .(T31, T33),\nT32 -> T33" }, { "from": 322, "to": 336, "label": "EVAL-BACKTRACK" }, { "from": 333, "to": 340, "label": "CASE" }, { "from": 340, "to": 341, "label": "PARALLEL" }, { "from": 340, "to": 342, "label": "PARALLEL" }, { "from": 341, "to": 344, "label": "ONLY EVAL with clause\ntail(nil, nil).\nand substitutionX24 -> nil" }, { "from": 342, "to": 758, "label": "BACKTRACK\nfor clause: tail(cons(X3, T), T)because of non-unification" }, { "from": 344, "to": 1, "label": "INSTANCE with matching:\nT1 -> nil\nT2 -> T33" }, { "from": 759, "to": 762, "label": "CUT" }, { "from": 760, "to": 775, "label": "FAILURE" }, { "from": 762, "to": 763, "label": "CASE" }, { "from": 763, "to": 766, "label": "EVAL with clause\neq(X61, X61).\nand substitutionT23 -> .(T51, T53),\nX61 -> .(T51, T53),\nT43 -> T51,\nX23 -> T53,\nT50 -> .(T51, T53),\nT52 -> T53" }, { "from": 763, "to": 767, "label": "EVAL-BACKTRACK" }, { "from": 766, "to": 768, "label": "CASE" }, { "from": 768, "to": 769, "label": "BACKTRACK\nfor clause: tail(nil, nil)because of non-unification" }, { "from": 769, "to": 772, "label": "ONLY EVAL with clause\ntail(cons(X71, X72), X72).\nand substitutionT51 -> T61,\nX71 -> atom(T61),\nT42 -> T62,\nX72 -> T62,\nX24 -> T62" }, { "from": 772, "to": 1, "label": "INSTANCE with matching:\nT1 -> T62\nT2 -> T53" }, { "from": 775, "to": 777, "label": "ONLY EVAL with clause\nflatten(X84, X85) :- ','(head(X84, cons(X86, X87)), ','(tail(X84, X88), flatten(cons(X86, cons(X87, X88)), X85))).\nand substitutionT21 -> T70,\nX84 -> T70,\nT2 -> T72,\nX85 -> T72,\nT71 -> T72" }, { "from": 777, "to": 778, "label": "CASE" }, { "from": 778, "to": 779, "label": "BACKTRACK\nfor clause: head(nil, X1)\nwith clash: (head(T70, atom(X22)), head(nil, X29))" }, { "from": 779, "to": 780, "label": "EVAL with clause\nhead(cons(X98, X99), X98).\nand substitutionX98 -> cons(T83, T84),\nX99 -> T82,\nT70 -> cons(cons(T83, T84), T82),\nX86 -> T83,\nX87 -> T84,\nT81 -> cons(T83, T84)" }, { "from": 779, "to": 781, "label": "EVAL-BACKTRACK" }, { "from": 780, "to": 782, "label": "CASE" }, { "from": 782, "to": 783, "label": "BACKTRACK\nfor clause: tail(nil, nil)because of non-unification" }, { "from": 783, "to": 804, "label": "ONLY EVAL with clause\ntail(cons(X108, X109), X109).\nand substitutionT83 -> T91,\nT84 -> T92,\nX108 -> cons(T91, T92),\nT82 -> T93,\nX109 -> T93,\nX88 -> T93" }, { "from": 804, "to": 1, "label": "INSTANCE with matching:\nT1 -> cons(T91, cons(T92, T93))\nT2 -> T72" } ], "type": "Graph" } } ---------------------------------------- (98) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(atom(T15)) -> f1_out1 f1_in(nil) -> U1(f1_in(nil), nil) U1(f1_out1, nil) -> f1_out1 f1_in(cons(atom(T61), T62)) -> U2(f1_in(T62), cons(atom(T61), T62)) U2(f1_out1, cons(atom(T61), T62)) -> f1_out1 f1_in(cons(cons(T91, T92), T93)) -> U3(f1_in(cons(T91, cons(T92, T93))), cons(cons(T91, T92), T93)) U3(f1_out1, cons(cons(T91, T92), T93)) -> f1_out1 Q is empty. ---------------------------------------- (99) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (100) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(atom(T15)) -> f1_out1 f1_in(nil) -> U1(f1_in(nil), nil) U1(f1_out1, nil) -> f1_out1 f1_in(cons(atom(T61), T62)) -> U2(f1_in(T62), cons(atom(T61), T62)) U2(f1_out1, cons(atom(T61), T62)) -> f1_out1 f1_in(cons(cons(T91, T92), T93)) -> U3(f1_in(cons(T91, cons(T92, T93))), cons(cons(T91, T92), T93)) U3(f1_out1, cons(cons(T91, T92), T93)) -> f1_out1 The set Q consists of the following terms: f1_in(atom(x0)) f1_in(nil) U1(f1_out1, nil) f1_in(cons(atom(x0), x1)) U2(f1_out1, cons(atom(x0), x1)) f1_in(cons(cons(x0, x1), x2)) U3(f1_out1, cons(cons(x0, x1), x2)) ---------------------------------------- (101) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (102) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(nil) -> U1^1(f1_in(nil), nil) F1_IN(nil) -> F1_IN(nil) F1_IN(cons(atom(T61), T62)) -> U2^1(f1_in(T62), cons(atom(T61), T62)) F1_IN(cons(atom(T61), T62)) -> F1_IN(T62) F1_IN(cons(cons(T91, T92), T93)) -> U3^1(f1_in(cons(T91, cons(T92, T93))), cons(cons(T91, T92), T93)) F1_IN(cons(cons(T91, T92), T93)) -> F1_IN(cons(T91, cons(T92, T93))) The TRS R consists of the following rules: f1_in(atom(T15)) -> f1_out1 f1_in(nil) -> U1(f1_in(nil), nil) U1(f1_out1, nil) -> f1_out1 f1_in(cons(atom(T61), T62)) -> U2(f1_in(T62), cons(atom(T61), T62)) U2(f1_out1, cons(atom(T61), T62)) -> f1_out1 f1_in(cons(cons(T91, T92), T93)) -> U3(f1_in(cons(T91, cons(T92, T93))), cons(cons(T91, T92), T93)) U3(f1_out1, cons(cons(T91, T92), T93)) -> f1_out1 The set Q consists of the following terms: f1_in(atom(x0)) f1_in(nil) U1(f1_out1, nil) f1_in(cons(atom(x0), x1)) U2(f1_out1, cons(atom(x0), x1)) f1_in(cons(cons(x0, x1), x2)) U3(f1_out1, cons(cons(x0, x1), x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (103) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (104) Complex Obligation (AND) ---------------------------------------- (105) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(nil) -> F1_IN(nil) The TRS R consists of the following rules: f1_in(atom(T15)) -> f1_out1 f1_in(nil) -> U1(f1_in(nil), nil) U1(f1_out1, nil) -> f1_out1 f1_in(cons(atom(T61), T62)) -> U2(f1_in(T62), cons(atom(T61), T62)) U2(f1_out1, cons(atom(T61), T62)) -> f1_out1 f1_in(cons(cons(T91, T92), T93)) -> U3(f1_in(cons(T91, cons(T92, T93))), cons(cons(T91, T92), T93)) U3(f1_out1, cons(cons(T91, T92), T93)) -> f1_out1 The set Q consists of the following terms: f1_in(atom(x0)) f1_in(nil) U1(f1_out1, nil) f1_in(cons(atom(x0), x1)) U2(f1_out1, cons(atom(x0), x1)) f1_in(cons(cons(x0, x1), x2)) U3(f1_out1, cons(cons(x0, x1), x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (106) 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. ---------------------------------------- (107) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(nil) -> F1_IN(nil) R is empty. The set Q consists of the following terms: f1_in(atom(x0)) f1_in(nil) U1(f1_out1, nil) f1_in(cons(atom(x0), x1)) U2(f1_out1, cons(atom(x0), x1)) f1_in(cons(cons(x0, x1), x2)) U3(f1_out1, cons(cons(x0, x1), x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (108) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f1_in(atom(x0)) f1_in(nil) U1(f1_out1, nil) f1_in(cons(atom(x0), x1)) U2(f1_out1, cons(atom(x0), x1)) f1_in(cons(cons(x0, x1), x2)) U3(f1_out1, cons(cons(x0, x1), x2)) ---------------------------------------- (109) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(nil) -> F1_IN(nil) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (110) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = F1_IN(nil) evaluates to t =F1_IN(nil) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from F1_IN(nil) to F1_IN(nil). ---------------------------------------- (111) NO ---------------------------------------- (112) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(cons(cons(T91, T92), T93)) -> F1_IN(cons(T91, cons(T92, T93))) F1_IN(cons(atom(T61), T62)) -> F1_IN(T62) The TRS R consists of the following rules: f1_in(atom(T15)) -> f1_out1 f1_in(nil) -> U1(f1_in(nil), nil) U1(f1_out1, nil) -> f1_out1 f1_in(cons(atom(T61), T62)) -> U2(f1_in(T62), cons(atom(T61), T62)) U2(f1_out1, cons(atom(T61), T62)) -> f1_out1 f1_in(cons(cons(T91, T92), T93)) -> U3(f1_in(cons(T91, cons(T92, T93))), cons(cons(T91, T92), T93)) U3(f1_out1, cons(cons(T91, T92), T93)) -> f1_out1 The set Q consists of the following terms: f1_in(atom(x0)) f1_in(nil) U1(f1_out1, nil) f1_in(cons(atom(x0), x1)) U2(f1_out1, cons(atom(x0), x1)) f1_in(cons(cons(x0, x1), x2)) U3(f1_out1, cons(cons(x0, x1), x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (113) 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. ---------------------------------------- (114) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(cons(cons(T91, T92), T93)) -> F1_IN(cons(T91, cons(T92, T93))) F1_IN(cons(atom(T61), T62)) -> F1_IN(T62) R is empty. The set Q consists of the following terms: f1_in(atom(x0)) f1_in(nil) U1(f1_out1, nil) f1_in(cons(atom(x0), x1)) U2(f1_out1, cons(atom(x0), x1)) f1_in(cons(cons(x0, x1), x2)) U3(f1_out1, cons(cons(x0, x1), x2)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (115) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f1_in(atom(x0)) f1_in(nil) U1(f1_out1, nil) f1_in(cons(atom(x0), x1)) U2(f1_out1, cons(atom(x0), x1)) f1_in(cons(cons(x0, x1), x2)) U3(f1_out1, cons(cons(x0, x1), x2)) ---------------------------------------- (116) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(cons(cons(T91, T92), T93)) -> F1_IN(cons(T91, cons(T92, T93))) F1_IN(cons(atom(T61), T62)) -> F1_IN(T62) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (117) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: F1_IN(cons(cons(T91, T92), T93)) -> F1_IN(cons(T91, cons(T92, T93))) F1_IN(cons(atom(T61), T62)) -> F1_IN(T62) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(F1_IN(x_1)) = 2*x_1 POL(atom(x_1)) = x_1 POL(cons(x_1, x_2)) = 1 + 2*x_1 + x_2 ---------------------------------------- (118) Obligation: Q DP problem: P is empty. R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (119) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (120) YES