4.70/2.12 YES 5.07/2.13 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.07/2.13 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.07/2.13 5.07/2.13 5.07/2.13 Left Termination of the query pattern 5.07/2.13 5.07/2.13 perm1(g,g) 5.07/2.13 5.07/2.13 w.r.t. the given Prolog program could successfully be proven: 5.07/2.13 5.07/2.13 (0) Prolog 5.07/2.13 (1) PrologToPiTRSProof [SOUND, 0 ms] 5.07/2.13 (2) PiTRS 5.07/2.13 (3) DependencyPairsProof [EQUIVALENT, 9 ms] 5.07/2.13 (4) PiDP 5.07/2.13 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 5.07/2.13 (6) AND 5.07/2.13 (7) PiDP 5.07/2.13 (8) UsableRulesProof [EQUIVALENT, 0 ms] 5.07/2.13 (9) PiDP 5.07/2.13 (10) PiDPToQDPProof [EQUIVALENT, 0 ms] 5.07/2.13 (11) QDP 5.07/2.13 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.07/2.13 (13) YES 5.07/2.13 (14) PiDP 5.07/2.13 (15) UsableRulesProof [EQUIVALENT, 0 ms] 5.07/2.13 (16) PiDP 5.07/2.13 (17) PiDPToQDPProof [SOUND, 0 ms] 5.07/2.13 (18) QDP 5.07/2.13 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.07/2.13 (20) YES 5.07/2.13 (21) PiDP 5.07/2.13 (22) UsableRulesProof [EQUIVALENT, 0 ms] 5.07/2.13 (23) PiDP 5.07/2.13 (24) PiDPToQDPProof [EQUIVALENT, 0 ms] 5.07/2.13 (25) QDP 5.07/2.13 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.07/2.13 (27) YES 5.07/2.13 5.07/2.13 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (0) 5.07/2.13 Obligation: 5.07/2.13 Clauses: 5.07/2.13 5.07/2.13 perm1(L, M) :- ','(eq_len1(L, M), same_sets(L, M)). 5.07/2.13 eq_len1([], []). 5.07/2.13 eq_len1(.(X1, Xs), .(X2, Ys)) :- eq_len1(Xs, Ys). 5.07/2.13 member(X, .(X, X3)). 5.07/2.13 member(X, .(X4, T)) :- member(X, T). 5.07/2.13 same_sets([], X5). 5.07/2.13 same_sets(.(X, Xs), L) :- ','(member(X, L), same_sets(Xs, L)). 5.07/2.13 5.07/2.13 5.07/2.13 Query: perm1(g,g) 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (1) PrologToPiTRSProof (SOUND) 5.07/2.13 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 5.07/2.13 5.07/2.13 perm1_in_2: (b,b) 5.07/2.13 5.07/2.13 eq_len1_in_2: (b,b) 5.07/2.13 5.07/2.13 same_sets_in_2: (b,b) 5.07/2.13 5.07/2.13 member_in_2: (b,b) 5.07/2.13 5.07/2.13 Transforming Prolog into the following Term Rewriting System: 5.07/2.13 5.07/2.13 Pi-finite rewrite system: 5.07/2.13 The TRS R consists of the following rules: 5.07/2.13 5.07/2.13 perm1_in_gg(L, M) -> U1_gg(L, M, eq_len1_in_gg(L, M)) 5.07/2.13 eq_len1_in_gg([], []) -> eq_len1_out_gg([], []) 5.07/2.13 eq_len1_in_gg(.(X1, Xs), .(X2, Ys)) -> U3_gg(X1, Xs, X2, Ys, eq_len1_in_gg(Xs, Ys)) 5.07/2.13 U3_gg(X1, Xs, X2, Ys, eq_len1_out_gg(Xs, Ys)) -> eq_len1_out_gg(.(X1, Xs), .(X2, Ys)) 5.07/2.13 U1_gg(L, M, eq_len1_out_gg(L, M)) -> U2_gg(L, M, same_sets_in_gg(L, M)) 5.07/2.13 same_sets_in_gg([], X5) -> same_sets_out_gg([], X5) 5.07/2.13 same_sets_in_gg(.(X, Xs), L) -> U5_gg(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 member_in_gg(X, .(X, X3)) -> member_out_gg(X, .(X, X3)) 5.07/2.13 member_in_gg(X, .(X4, T)) -> U4_gg(X, X4, T, member_in_gg(X, T)) 5.07/2.13 U4_gg(X, X4, T, member_out_gg(X, T)) -> member_out_gg(X, .(X4, T)) 5.07/2.13 U5_gg(X, Xs, L, member_out_gg(X, L)) -> U6_gg(X, Xs, L, same_sets_in_gg(Xs, L)) 5.07/2.13 U6_gg(X, Xs, L, same_sets_out_gg(Xs, L)) -> same_sets_out_gg(.(X, Xs), L) 5.07/2.13 U2_gg(L, M, same_sets_out_gg(L, M)) -> perm1_out_gg(L, M) 5.07/2.13 5.07/2.13 The argument filtering Pi contains the following mapping: 5.07/2.13 perm1_in_gg(x1, x2) = perm1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 U1_gg(x1, x2, x3) = U1_gg(x1, x2, x3) 5.07/2.13 5.07/2.13 eq_len1_in_gg(x1, x2) = eq_len1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 [] = [] 5.07/2.13 5.07/2.13 eq_len1_out_gg(x1, x2) = eq_len1_out_gg 5.07/2.13 5.07/2.13 .(x1, x2) = .(x1, x2) 5.07/2.13 5.07/2.13 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.07/2.13 5.07/2.13 U2_gg(x1, x2, x3) = U2_gg(x3) 5.07/2.13 5.07/2.13 same_sets_in_gg(x1, x2) = same_sets_in_gg(x1, x2) 5.07/2.13 5.07/2.13 same_sets_out_gg(x1, x2) = same_sets_out_gg 5.07/2.13 5.07/2.13 U5_gg(x1, x2, x3, x4) = U5_gg(x2, x3, x4) 5.07/2.13 5.07/2.13 member_in_gg(x1, x2) = member_in_gg(x1, x2) 5.07/2.13 5.07/2.13 member_out_gg(x1, x2) = member_out_gg 5.07/2.13 5.07/2.13 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 5.07/2.13 5.07/2.13 U6_gg(x1, x2, x3, x4) = U6_gg(x4) 5.07/2.13 5.07/2.13 perm1_out_gg(x1, x2) = perm1_out_gg 5.07/2.13 5.07/2.13 5.07/2.13 5.07/2.13 5.07/2.13 5.07/2.13 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 5.07/2.13 5.07/2.13 5.07/2.13 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (2) 5.07/2.13 Obligation: 5.07/2.13 Pi-finite rewrite system: 5.07/2.13 The TRS R consists of the following rules: 5.07/2.13 5.07/2.13 perm1_in_gg(L, M) -> U1_gg(L, M, eq_len1_in_gg(L, M)) 5.07/2.13 eq_len1_in_gg([], []) -> eq_len1_out_gg([], []) 5.07/2.13 eq_len1_in_gg(.(X1, Xs), .(X2, Ys)) -> U3_gg(X1, Xs, X2, Ys, eq_len1_in_gg(Xs, Ys)) 5.07/2.13 U3_gg(X1, Xs, X2, Ys, eq_len1_out_gg(Xs, Ys)) -> eq_len1_out_gg(.(X1, Xs), .(X2, Ys)) 5.07/2.13 U1_gg(L, M, eq_len1_out_gg(L, M)) -> U2_gg(L, M, same_sets_in_gg(L, M)) 5.07/2.13 same_sets_in_gg([], X5) -> same_sets_out_gg([], X5) 5.07/2.13 same_sets_in_gg(.(X, Xs), L) -> U5_gg(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 member_in_gg(X, .(X, X3)) -> member_out_gg(X, .(X, X3)) 5.07/2.13 member_in_gg(X, .(X4, T)) -> U4_gg(X, X4, T, member_in_gg(X, T)) 5.07/2.13 U4_gg(X, X4, T, member_out_gg(X, T)) -> member_out_gg(X, .(X4, T)) 5.07/2.13 U5_gg(X, Xs, L, member_out_gg(X, L)) -> U6_gg(X, Xs, L, same_sets_in_gg(Xs, L)) 5.07/2.13 U6_gg(X, Xs, L, same_sets_out_gg(Xs, L)) -> same_sets_out_gg(.(X, Xs), L) 5.07/2.13 U2_gg(L, M, same_sets_out_gg(L, M)) -> perm1_out_gg(L, M) 5.07/2.13 5.07/2.13 The argument filtering Pi contains the following mapping: 5.07/2.13 perm1_in_gg(x1, x2) = perm1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 U1_gg(x1, x2, x3) = U1_gg(x1, x2, x3) 5.07/2.13 5.07/2.13 eq_len1_in_gg(x1, x2) = eq_len1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 [] = [] 5.07/2.13 5.07/2.13 eq_len1_out_gg(x1, x2) = eq_len1_out_gg 5.07/2.13 5.07/2.13 .(x1, x2) = .(x1, x2) 5.07/2.13 5.07/2.13 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.07/2.13 5.07/2.13 U2_gg(x1, x2, x3) = U2_gg(x3) 5.07/2.13 5.07/2.13 same_sets_in_gg(x1, x2) = same_sets_in_gg(x1, x2) 5.07/2.13 5.07/2.13 same_sets_out_gg(x1, x2) = same_sets_out_gg 5.07/2.13 5.07/2.13 U5_gg(x1, x2, x3, x4) = U5_gg(x2, x3, x4) 5.07/2.13 5.07/2.13 member_in_gg(x1, x2) = member_in_gg(x1, x2) 5.07/2.13 5.07/2.13 member_out_gg(x1, x2) = member_out_gg 5.07/2.13 5.07/2.13 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 5.07/2.13 5.07/2.13 U6_gg(x1, x2, x3, x4) = U6_gg(x4) 5.07/2.13 5.07/2.13 perm1_out_gg(x1, x2) = perm1_out_gg 5.07/2.13 5.07/2.13 5.07/2.13 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (3) DependencyPairsProof (EQUIVALENT) 5.07/2.13 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 5.07/2.13 Pi DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 PERM1_IN_GG(L, M) -> U1_GG(L, M, eq_len1_in_gg(L, M)) 5.07/2.13 PERM1_IN_GG(L, M) -> EQ_LEN1_IN_GG(L, M) 5.07/2.13 EQ_LEN1_IN_GG(.(X1, Xs), .(X2, Ys)) -> U3_GG(X1, Xs, X2, Ys, eq_len1_in_gg(Xs, Ys)) 5.07/2.13 EQ_LEN1_IN_GG(.(X1, Xs), .(X2, Ys)) -> EQ_LEN1_IN_GG(Xs, Ys) 5.07/2.13 U1_GG(L, M, eq_len1_out_gg(L, M)) -> U2_GG(L, M, same_sets_in_gg(L, M)) 5.07/2.13 U1_GG(L, M, eq_len1_out_gg(L, M)) -> SAME_SETS_IN_GG(L, M) 5.07/2.13 SAME_SETS_IN_GG(.(X, Xs), L) -> U5_GG(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 SAME_SETS_IN_GG(.(X, Xs), L) -> MEMBER_IN_GG(X, L) 5.07/2.13 MEMBER_IN_GG(X, .(X4, T)) -> U4_GG(X, X4, T, member_in_gg(X, T)) 5.07/2.13 MEMBER_IN_GG(X, .(X4, T)) -> MEMBER_IN_GG(X, T) 5.07/2.13 U5_GG(X, Xs, L, member_out_gg(X, L)) -> U6_GG(X, Xs, L, same_sets_in_gg(Xs, L)) 5.07/2.13 U5_GG(X, Xs, L, member_out_gg(X, L)) -> SAME_SETS_IN_GG(Xs, L) 5.07/2.13 5.07/2.13 The TRS R consists of the following rules: 5.07/2.13 5.07/2.13 perm1_in_gg(L, M) -> U1_gg(L, M, eq_len1_in_gg(L, M)) 5.07/2.13 eq_len1_in_gg([], []) -> eq_len1_out_gg([], []) 5.07/2.13 eq_len1_in_gg(.(X1, Xs), .(X2, Ys)) -> U3_gg(X1, Xs, X2, Ys, eq_len1_in_gg(Xs, Ys)) 5.07/2.13 U3_gg(X1, Xs, X2, Ys, eq_len1_out_gg(Xs, Ys)) -> eq_len1_out_gg(.(X1, Xs), .(X2, Ys)) 5.07/2.13 U1_gg(L, M, eq_len1_out_gg(L, M)) -> U2_gg(L, M, same_sets_in_gg(L, M)) 5.07/2.13 same_sets_in_gg([], X5) -> same_sets_out_gg([], X5) 5.07/2.13 same_sets_in_gg(.(X, Xs), L) -> U5_gg(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 member_in_gg(X, .(X, X3)) -> member_out_gg(X, .(X, X3)) 5.07/2.13 member_in_gg(X, .(X4, T)) -> U4_gg(X, X4, T, member_in_gg(X, T)) 5.07/2.13 U4_gg(X, X4, T, member_out_gg(X, T)) -> member_out_gg(X, .(X4, T)) 5.07/2.13 U5_gg(X, Xs, L, member_out_gg(X, L)) -> U6_gg(X, Xs, L, same_sets_in_gg(Xs, L)) 5.07/2.13 U6_gg(X, Xs, L, same_sets_out_gg(Xs, L)) -> same_sets_out_gg(.(X, Xs), L) 5.07/2.13 U2_gg(L, M, same_sets_out_gg(L, M)) -> perm1_out_gg(L, M) 5.07/2.13 5.07/2.13 The argument filtering Pi contains the following mapping: 5.07/2.13 perm1_in_gg(x1, x2) = perm1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 U1_gg(x1, x2, x3) = U1_gg(x1, x2, x3) 5.07/2.13 5.07/2.13 eq_len1_in_gg(x1, x2) = eq_len1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 [] = [] 5.07/2.13 5.07/2.13 eq_len1_out_gg(x1, x2) = eq_len1_out_gg 5.07/2.13 5.07/2.13 .(x1, x2) = .(x1, x2) 5.07/2.13 5.07/2.13 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.07/2.13 5.07/2.13 U2_gg(x1, x2, x3) = U2_gg(x3) 5.07/2.13 5.07/2.13 same_sets_in_gg(x1, x2) = same_sets_in_gg(x1, x2) 5.07/2.13 5.07/2.13 same_sets_out_gg(x1, x2) = same_sets_out_gg 5.07/2.13 5.07/2.13 U5_gg(x1, x2, x3, x4) = U5_gg(x2, x3, x4) 5.07/2.13 5.07/2.13 member_in_gg(x1, x2) = member_in_gg(x1, x2) 5.07/2.13 5.07/2.13 member_out_gg(x1, x2) = member_out_gg 5.07/2.13 5.07/2.13 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 5.07/2.13 5.07/2.13 U6_gg(x1, x2, x3, x4) = U6_gg(x4) 5.07/2.13 5.07/2.13 perm1_out_gg(x1, x2) = perm1_out_gg 5.07/2.13 5.07/2.13 PERM1_IN_GG(x1, x2) = PERM1_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U1_GG(x1, x2, x3) = U1_GG(x1, x2, x3) 5.07/2.13 5.07/2.13 EQ_LEN1_IN_GG(x1, x2) = EQ_LEN1_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U3_GG(x1, x2, x3, x4, x5) = U3_GG(x5) 5.07/2.13 5.07/2.13 U2_GG(x1, x2, x3) = U2_GG(x3) 5.07/2.13 5.07/2.13 SAME_SETS_IN_GG(x1, x2) = SAME_SETS_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U5_GG(x1, x2, x3, x4) = U5_GG(x2, x3, x4) 5.07/2.13 5.07/2.13 MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U4_GG(x1, x2, x3, x4) = U4_GG(x4) 5.07/2.13 5.07/2.13 U6_GG(x1, x2, x3, x4) = U6_GG(x4) 5.07/2.13 5.07/2.13 5.07/2.13 We have to consider all (P,R,Pi)-chains 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (4) 5.07/2.13 Obligation: 5.07/2.13 Pi DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 PERM1_IN_GG(L, M) -> U1_GG(L, M, eq_len1_in_gg(L, M)) 5.07/2.13 PERM1_IN_GG(L, M) -> EQ_LEN1_IN_GG(L, M) 5.07/2.13 EQ_LEN1_IN_GG(.(X1, Xs), .(X2, Ys)) -> U3_GG(X1, Xs, X2, Ys, eq_len1_in_gg(Xs, Ys)) 5.07/2.13 EQ_LEN1_IN_GG(.(X1, Xs), .(X2, Ys)) -> EQ_LEN1_IN_GG(Xs, Ys) 5.07/2.13 U1_GG(L, M, eq_len1_out_gg(L, M)) -> U2_GG(L, M, same_sets_in_gg(L, M)) 5.07/2.13 U1_GG(L, M, eq_len1_out_gg(L, M)) -> SAME_SETS_IN_GG(L, M) 5.07/2.13 SAME_SETS_IN_GG(.(X, Xs), L) -> U5_GG(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 SAME_SETS_IN_GG(.(X, Xs), L) -> MEMBER_IN_GG(X, L) 5.07/2.13 MEMBER_IN_GG(X, .(X4, T)) -> U4_GG(X, X4, T, member_in_gg(X, T)) 5.07/2.13 MEMBER_IN_GG(X, .(X4, T)) -> MEMBER_IN_GG(X, T) 5.07/2.13 U5_GG(X, Xs, L, member_out_gg(X, L)) -> U6_GG(X, Xs, L, same_sets_in_gg(Xs, L)) 5.07/2.13 U5_GG(X, Xs, L, member_out_gg(X, L)) -> SAME_SETS_IN_GG(Xs, L) 5.07/2.13 5.07/2.13 The TRS R consists of the following rules: 5.07/2.13 5.07/2.13 perm1_in_gg(L, M) -> U1_gg(L, M, eq_len1_in_gg(L, M)) 5.07/2.13 eq_len1_in_gg([], []) -> eq_len1_out_gg([], []) 5.07/2.13 eq_len1_in_gg(.(X1, Xs), .(X2, Ys)) -> U3_gg(X1, Xs, X2, Ys, eq_len1_in_gg(Xs, Ys)) 5.07/2.13 U3_gg(X1, Xs, X2, Ys, eq_len1_out_gg(Xs, Ys)) -> eq_len1_out_gg(.(X1, Xs), .(X2, Ys)) 5.07/2.13 U1_gg(L, M, eq_len1_out_gg(L, M)) -> U2_gg(L, M, same_sets_in_gg(L, M)) 5.07/2.13 same_sets_in_gg([], X5) -> same_sets_out_gg([], X5) 5.07/2.13 same_sets_in_gg(.(X, Xs), L) -> U5_gg(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 member_in_gg(X, .(X, X3)) -> member_out_gg(X, .(X, X3)) 5.07/2.13 member_in_gg(X, .(X4, T)) -> U4_gg(X, X4, T, member_in_gg(X, T)) 5.07/2.13 U4_gg(X, X4, T, member_out_gg(X, T)) -> member_out_gg(X, .(X4, T)) 5.07/2.13 U5_gg(X, Xs, L, member_out_gg(X, L)) -> U6_gg(X, Xs, L, same_sets_in_gg(Xs, L)) 5.07/2.13 U6_gg(X, Xs, L, same_sets_out_gg(Xs, L)) -> same_sets_out_gg(.(X, Xs), L) 5.07/2.13 U2_gg(L, M, same_sets_out_gg(L, M)) -> perm1_out_gg(L, M) 5.07/2.13 5.07/2.13 The argument filtering Pi contains the following mapping: 5.07/2.13 perm1_in_gg(x1, x2) = perm1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 U1_gg(x1, x2, x3) = U1_gg(x1, x2, x3) 5.07/2.13 5.07/2.13 eq_len1_in_gg(x1, x2) = eq_len1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 [] = [] 5.07/2.13 5.07/2.13 eq_len1_out_gg(x1, x2) = eq_len1_out_gg 5.07/2.13 5.07/2.13 .(x1, x2) = .(x1, x2) 5.07/2.13 5.07/2.13 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.07/2.13 5.07/2.13 U2_gg(x1, x2, x3) = U2_gg(x3) 5.07/2.13 5.07/2.13 same_sets_in_gg(x1, x2) = same_sets_in_gg(x1, x2) 5.07/2.13 5.07/2.13 same_sets_out_gg(x1, x2) = same_sets_out_gg 5.07/2.13 5.07/2.13 U5_gg(x1, x2, x3, x4) = U5_gg(x2, x3, x4) 5.07/2.13 5.07/2.13 member_in_gg(x1, x2) = member_in_gg(x1, x2) 5.07/2.13 5.07/2.13 member_out_gg(x1, x2) = member_out_gg 5.07/2.13 5.07/2.13 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 5.07/2.13 5.07/2.13 U6_gg(x1, x2, x3, x4) = U6_gg(x4) 5.07/2.13 5.07/2.13 perm1_out_gg(x1, x2) = perm1_out_gg 5.07/2.13 5.07/2.13 PERM1_IN_GG(x1, x2) = PERM1_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U1_GG(x1, x2, x3) = U1_GG(x1, x2, x3) 5.07/2.13 5.07/2.13 EQ_LEN1_IN_GG(x1, x2) = EQ_LEN1_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U3_GG(x1, x2, x3, x4, x5) = U3_GG(x5) 5.07/2.13 5.07/2.13 U2_GG(x1, x2, x3) = U2_GG(x3) 5.07/2.13 5.07/2.13 SAME_SETS_IN_GG(x1, x2) = SAME_SETS_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U5_GG(x1, x2, x3, x4) = U5_GG(x2, x3, x4) 5.07/2.13 5.07/2.13 MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U4_GG(x1, x2, x3, x4) = U4_GG(x4) 5.07/2.13 5.07/2.13 U6_GG(x1, x2, x3, x4) = U6_GG(x4) 5.07/2.13 5.07/2.13 5.07/2.13 We have to consider all (P,R,Pi)-chains 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (5) DependencyGraphProof (EQUIVALENT) 5.07/2.13 The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 8 less nodes. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (6) 5.07/2.13 Complex Obligation (AND) 5.07/2.13 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (7) 5.07/2.13 Obligation: 5.07/2.13 Pi DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 MEMBER_IN_GG(X, .(X4, T)) -> MEMBER_IN_GG(X, T) 5.07/2.13 5.07/2.13 The TRS R consists of the following rules: 5.07/2.13 5.07/2.13 perm1_in_gg(L, M) -> U1_gg(L, M, eq_len1_in_gg(L, M)) 5.07/2.13 eq_len1_in_gg([], []) -> eq_len1_out_gg([], []) 5.07/2.13 eq_len1_in_gg(.(X1, Xs), .(X2, Ys)) -> U3_gg(X1, Xs, X2, Ys, eq_len1_in_gg(Xs, Ys)) 5.07/2.13 U3_gg(X1, Xs, X2, Ys, eq_len1_out_gg(Xs, Ys)) -> eq_len1_out_gg(.(X1, Xs), .(X2, Ys)) 5.07/2.13 U1_gg(L, M, eq_len1_out_gg(L, M)) -> U2_gg(L, M, same_sets_in_gg(L, M)) 5.07/2.13 same_sets_in_gg([], X5) -> same_sets_out_gg([], X5) 5.07/2.13 same_sets_in_gg(.(X, Xs), L) -> U5_gg(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 member_in_gg(X, .(X, X3)) -> member_out_gg(X, .(X, X3)) 5.07/2.13 member_in_gg(X, .(X4, T)) -> U4_gg(X, X4, T, member_in_gg(X, T)) 5.07/2.13 U4_gg(X, X4, T, member_out_gg(X, T)) -> member_out_gg(X, .(X4, T)) 5.07/2.13 U5_gg(X, Xs, L, member_out_gg(X, L)) -> U6_gg(X, Xs, L, same_sets_in_gg(Xs, L)) 5.07/2.13 U6_gg(X, Xs, L, same_sets_out_gg(Xs, L)) -> same_sets_out_gg(.(X, Xs), L) 5.07/2.13 U2_gg(L, M, same_sets_out_gg(L, M)) -> perm1_out_gg(L, M) 5.07/2.13 5.07/2.13 The argument filtering Pi contains the following mapping: 5.07/2.13 perm1_in_gg(x1, x2) = perm1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 U1_gg(x1, x2, x3) = U1_gg(x1, x2, x3) 5.07/2.13 5.07/2.13 eq_len1_in_gg(x1, x2) = eq_len1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 [] = [] 5.07/2.13 5.07/2.13 eq_len1_out_gg(x1, x2) = eq_len1_out_gg 5.07/2.13 5.07/2.13 .(x1, x2) = .(x1, x2) 5.07/2.13 5.07/2.13 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.07/2.13 5.07/2.13 U2_gg(x1, x2, x3) = U2_gg(x3) 5.07/2.13 5.07/2.13 same_sets_in_gg(x1, x2) = same_sets_in_gg(x1, x2) 5.07/2.13 5.07/2.13 same_sets_out_gg(x1, x2) = same_sets_out_gg 5.07/2.13 5.07/2.13 U5_gg(x1, x2, x3, x4) = U5_gg(x2, x3, x4) 5.07/2.13 5.07/2.13 member_in_gg(x1, x2) = member_in_gg(x1, x2) 5.07/2.13 5.07/2.13 member_out_gg(x1, x2) = member_out_gg 5.07/2.13 5.07/2.13 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 5.07/2.13 5.07/2.13 U6_gg(x1, x2, x3, x4) = U6_gg(x4) 5.07/2.13 5.07/2.13 perm1_out_gg(x1, x2) = perm1_out_gg 5.07/2.13 5.07/2.13 MEMBER_IN_GG(x1, x2) = MEMBER_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 5.07/2.13 We have to consider all (P,R,Pi)-chains 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (8) UsableRulesProof (EQUIVALENT) 5.07/2.13 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (9) 5.07/2.13 Obligation: 5.07/2.13 Pi DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 MEMBER_IN_GG(X, .(X4, T)) -> MEMBER_IN_GG(X, T) 5.07/2.13 5.07/2.13 R is empty. 5.07/2.13 Pi is empty. 5.07/2.13 We have to consider all (P,R,Pi)-chains 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (10) PiDPToQDPProof (EQUIVALENT) 5.07/2.13 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (11) 5.07/2.13 Obligation: 5.07/2.13 Q DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 MEMBER_IN_GG(X, .(X4, T)) -> MEMBER_IN_GG(X, T) 5.07/2.13 5.07/2.13 R is empty. 5.07/2.13 Q is empty. 5.07/2.13 We have to consider all (P,Q,R)-chains. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (12) QDPSizeChangeProof (EQUIVALENT) 5.07/2.13 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 5.07/2.13 5.07/2.13 From the DPs we obtained the following set of size-change graphs: 5.07/2.13 *MEMBER_IN_GG(X, .(X4, T)) -> MEMBER_IN_GG(X, T) 5.07/2.13 The graph contains the following edges 1 >= 1, 2 > 2 5.07/2.13 5.07/2.13 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (13) 5.07/2.13 YES 5.07/2.13 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (14) 5.07/2.13 Obligation: 5.07/2.13 Pi DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 U5_GG(X, Xs, L, member_out_gg(X, L)) -> SAME_SETS_IN_GG(Xs, L) 5.07/2.13 SAME_SETS_IN_GG(.(X, Xs), L) -> U5_GG(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 5.07/2.13 The TRS R consists of the following rules: 5.07/2.13 5.07/2.13 perm1_in_gg(L, M) -> U1_gg(L, M, eq_len1_in_gg(L, M)) 5.07/2.13 eq_len1_in_gg([], []) -> eq_len1_out_gg([], []) 5.07/2.13 eq_len1_in_gg(.(X1, Xs), .(X2, Ys)) -> U3_gg(X1, Xs, X2, Ys, eq_len1_in_gg(Xs, Ys)) 5.07/2.13 U3_gg(X1, Xs, X2, Ys, eq_len1_out_gg(Xs, Ys)) -> eq_len1_out_gg(.(X1, Xs), .(X2, Ys)) 5.07/2.13 U1_gg(L, M, eq_len1_out_gg(L, M)) -> U2_gg(L, M, same_sets_in_gg(L, M)) 5.07/2.13 same_sets_in_gg([], X5) -> same_sets_out_gg([], X5) 5.07/2.13 same_sets_in_gg(.(X, Xs), L) -> U5_gg(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 member_in_gg(X, .(X, X3)) -> member_out_gg(X, .(X, X3)) 5.07/2.13 member_in_gg(X, .(X4, T)) -> U4_gg(X, X4, T, member_in_gg(X, T)) 5.07/2.13 U4_gg(X, X4, T, member_out_gg(X, T)) -> member_out_gg(X, .(X4, T)) 5.07/2.13 U5_gg(X, Xs, L, member_out_gg(X, L)) -> U6_gg(X, Xs, L, same_sets_in_gg(Xs, L)) 5.07/2.13 U6_gg(X, Xs, L, same_sets_out_gg(Xs, L)) -> same_sets_out_gg(.(X, Xs), L) 5.07/2.13 U2_gg(L, M, same_sets_out_gg(L, M)) -> perm1_out_gg(L, M) 5.07/2.13 5.07/2.13 The argument filtering Pi contains the following mapping: 5.07/2.13 perm1_in_gg(x1, x2) = perm1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 U1_gg(x1, x2, x3) = U1_gg(x1, x2, x3) 5.07/2.13 5.07/2.13 eq_len1_in_gg(x1, x2) = eq_len1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 [] = [] 5.07/2.13 5.07/2.13 eq_len1_out_gg(x1, x2) = eq_len1_out_gg 5.07/2.13 5.07/2.13 .(x1, x2) = .(x1, x2) 5.07/2.13 5.07/2.13 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.07/2.13 5.07/2.13 U2_gg(x1, x2, x3) = U2_gg(x3) 5.07/2.13 5.07/2.13 same_sets_in_gg(x1, x2) = same_sets_in_gg(x1, x2) 5.07/2.13 5.07/2.13 same_sets_out_gg(x1, x2) = same_sets_out_gg 5.07/2.13 5.07/2.13 U5_gg(x1, x2, x3, x4) = U5_gg(x2, x3, x4) 5.07/2.13 5.07/2.13 member_in_gg(x1, x2) = member_in_gg(x1, x2) 5.07/2.13 5.07/2.13 member_out_gg(x1, x2) = member_out_gg 5.07/2.13 5.07/2.13 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 5.07/2.13 5.07/2.13 U6_gg(x1, x2, x3, x4) = U6_gg(x4) 5.07/2.13 5.07/2.13 perm1_out_gg(x1, x2) = perm1_out_gg 5.07/2.13 5.07/2.13 SAME_SETS_IN_GG(x1, x2) = SAME_SETS_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U5_GG(x1, x2, x3, x4) = U5_GG(x2, x3, x4) 5.07/2.13 5.07/2.13 5.07/2.13 We have to consider all (P,R,Pi)-chains 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (15) UsableRulesProof (EQUIVALENT) 5.07/2.13 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (16) 5.07/2.13 Obligation: 5.07/2.13 Pi DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 U5_GG(X, Xs, L, member_out_gg(X, L)) -> SAME_SETS_IN_GG(Xs, L) 5.07/2.13 SAME_SETS_IN_GG(.(X, Xs), L) -> U5_GG(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 5.07/2.13 The TRS R consists of the following rules: 5.07/2.13 5.07/2.13 member_in_gg(X, .(X, X3)) -> member_out_gg(X, .(X, X3)) 5.07/2.13 member_in_gg(X, .(X4, T)) -> U4_gg(X, X4, T, member_in_gg(X, T)) 5.07/2.13 U4_gg(X, X4, T, member_out_gg(X, T)) -> member_out_gg(X, .(X4, T)) 5.07/2.13 5.07/2.13 The argument filtering Pi contains the following mapping: 5.07/2.13 .(x1, x2) = .(x1, x2) 5.07/2.13 5.07/2.13 member_in_gg(x1, x2) = member_in_gg(x1, x2) 5.07/2.13 5.07/2.13 member_out_gg(x1, x2) = member_out_gg 5.07/2.13 5.07/2.13 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 5.07/2.13 5.07/2.13 SAME_SETS_IN_GG(x1, x2) = SAME_SETS_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 U5_GG(x1, x2, x3, x4) = U5_GG(x2, x3, x4) 5.07/2.13 5.07/2.13 5.07/2.13 We have to consider all (P,R,Pi)-chains 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (17) PiDPToQDPProof (SOUND) 5.07/2.13 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (18) 5.07/2.13 Obligation: 5.07/2.13 Q DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 U5_GG(Xs, L, member_out_gg) -> SAME_SETS_IN_GG(Xs, L) 5.07/2.13 SAME_SETS_IN_GG(.(X, Xs), L) -> U5_GG(Xs, L, member_in_gg(X, L)) 5.07/2.13 5.07/2.13 The TRS R consists of the following rules: 5.07/2.13 5.07/2.13 member_in_gg(X, .(X, X3)) -> member_out_gg 5.07/2.13 member_in_gg(X, .(X4, T)) -> U4_gg(member_in_gg(X, T)) 5.07/2.13 U4_gg(member_out_gg) -> member_out_gg 5.07/2.13 5.07/2.13 The set Q consists of the following terms: 5.07/2.13 5.07/2.13 member_in_gg(x0, x1) 5.07/2.13 U4_gg(x0) 5.07/2.13 5.07/2.13 We have to consider all (P,Q,R)-chains. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (19) QDPSizeChangeProof (EQUIVALENT) 5.07/2.13 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 5.07/2.13 5.07/2.13 From the DPs we obtained the following set of size-change graphs: 5.07/2.13 *SAME_SETS_IN_GG(.(X, Xs), L) -> U5_GG(Xs, L, member_in_gg(X, L)) 5.07/2.13 The graph contains the following edges 1 > 1, 2 >= 2 5.07/2.13 5.07/2.13 5.07/2.13 *U5_GG(Xs, L, member_out_gg) -> SAME_SETS_IN_GG(Xs, L) 5.07/2.13 The graph contains the following edges 1 >= 1, 2 >= 2 5.07/2.13 5.07/2.13 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (20) 5.07/2.13 YES 5.07/2.13 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (21) 5.07/2.13 Obligation: 5.07/2.13 Pi DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 EQ_LEN1_IN_GG(.(X1, Xs), .(X2, Ys)) -> EQ_LEN1_IN_GG(Xs, Ys) 5.07/2.13 5.07/2.13 The TRS R consists of the following rules: 5.07/2.13 5.07/2.13 perm1_in_gg(L, M) -> U1_gg(L, M, eq_len1_in_gg(L, M)) 5.07/2.13 eq_len1_in_gg([], []) -> eq_len1_out_gg([], []) 5.07/2.13 eq_len1_in_gg(.(X1, Xs), .(X2, Ys)) -> U3_gg(X1, Xs, X2, Ys, eq_len1_in_gg(Xs, Ys)) 5.07/2.13 U3_gg(X1, Xs, X2, Ys, eq_len1_out_gg(Xs, Ys)) -> eq_len1_out_gg(.(X1, Xs), .(X2, Ys)) 5.07/2.13 U1_gg(L, M, eq_len1_out_gg(L, M)) -> U2_gg(L, M, same_sets_in_gg(L, M)) 5.07/2.13 same_sets_in_gg([], X5) -> same_sets_out_gg([], X5) 5.07/2.13 same_sets_in_gg(.(X, Xs), L) -> U5_gg(X, Xs, L, member_in_gg(X, L)) 5.07/2.13 member_in_gg(X, .(X, X3)) -> member_out_gg(X, .(X, X3)) 5.07/2.13 member_in_gg(X, .(X4, T)) -> U4_gg(X, X4, T, member_in_gg(X, T)) 5.07/2.13 U4_gg(X, X4, T, member_out_gg(X, T)) -> member_out_gg(X, .(X4, T)) 5.07/2.13 U5_gg(X, Xs, L, member_out_gg(X, L)) -> U6_gg(X, Xs, L, same_sets_in_gg(Xs, L)) 5.07/2.13 U6_gg(X, Xs, L, same_sets_out_gg(Xs, L)) -> same_sets_out_gg(.(X, Xs), L) 5.07/2.13 U2_gg(L, M, same_sets_out_gg(L, M)) -> perm1_out_gg(L, M) 5.07/2.13 5.07/2.13 The argument filtering Pi contains the following mapping: 5.07/2.13 perm1_in_gg(x1, x2) = perm1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 U1_gg(x1, x2, x3) = U1_gg(x1, x2, x3) 5.07/2.13 5.07/2.13 eq_len1_in_gg(x1, x2) = eq_len1_in_gg(x1, x2) 5.07/2.13 5.07/2.13 [] = [] 5.07/2.13 5.07/2.13 eq_len1_out_gg(x1, x2) = eq_len1_out_gg 5.07/2.13 5.07/2.13 .(x1, x2) = .(x1, x2) 5.07/2.13 5.07/2.13 U3_gg(x1, x2, x3, x4, x5) = U3_gg(x5) 5.07/2.13 5.07/2.13 U2_gg(x1, x2, x3) = U2_gg(x3) 5.07/2.13 5.07/2.13 same_sets_in_gg(x1, x2) = same_sets_in_gg(x1, x2) 5.07/2.13 5.07/2.13 same_sets_out_gg(x1, x2) = same_sets_out_gg 5.07/2.13 5.07/2.13 U5_gg(x1, x2, x3, x4) = U5_gg(x2, x3, x4) 5.07/2.13 5.07/2.13 member_in_gg(x1, x2) = member_in_gg(x1, x2) 5.07/2.13 5.07/2.13 member_out_gg(x1, x2) = member_out_gg 5.07/2.13 5.07/2.13 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 5.07/2.13 5.07/2.13 U6_gg(x1, x2, x3, x4) = U6_gg(x4) 5.07/2.13 5.07/2.13 perm1_out_gg(x1, x2) = perm1_out_gg 5.07/2.13 5.07/2.13 EQ_LEN1_IN_GG(x1, x2) = EQ_LEN1_IN_GG(x1, x2) 5.07/2.13 5.07/2.13 5.07/2.13 We have to consider all (P,R,Pi)-chains 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (22) UsableRulesProof (EQUIVALENT) 5.07/2.13 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (23) 5.07/2.13 Obligation: 5.07/2.13 Pi DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 EQ_LEN1_IN_GG(.(X1, Xs), .(X2, Ys)) -> EQ_LEN1_IN_GG(Xs, Ys) 5.07/2.13 5.07/2.13 R is empty. 5.07/2.13 Pi is empty. 5.07/2.13 We have to consider all (P,R,Pi)-chains 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (24) PiDPToQDPProof (EQUIVALENT) 5.07/2.13 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (25) 5.07/2.13 Obligation: 5.07/2.13 Q DP problem: 5.07/2.13 The TRS P consists of the following rules: 5.07/2.13 5.07/2.13 EQ_LEN1_IN_GG(.(X1, Xs), .(X2, Ys)) -> EQ_LEN1_IN_GG(Xs, Ys) 5.07/2.13 5.07/2.13 R is empty. 5.07/2.13 Q is empty. 5.07/2.13 We have to consider all (P,Q,R)-chains. 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (26) QDPSizeChangeProof (EQUIVALENT) 5.07/2.13 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 5.07/2.13 5.07/2.13 From the DPs we obtained the following set of size-change graphs: 5.07/2.13 *EQ_LEN1_IN_GG(.(X1, Xs), .(X2, Ys)) -> EQ_LEN1_IN_GG(Xs, Ys) 5.07/2.13 The graph contains the following edges 1 > 1, 2 > 2 5.07/2.13 5.07/2.13 5.07/2.13 ---------------------------------------- 5.07/2.13 5.07/2.13 (27) 5.07/2.13 YES 5.07/2.17 EOF