4.11/1.80 YES 4.34/1.88 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 4.34/1.88 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.34/1.88 4.34/1.88 4.34/1.88 Left Termination of the query pattern 4.34/1.88 4.34/1.88 overlap(g,g) 4.34/1.88 4.34/1.88 w.r.t. the given Prolog program could successfully be proven: 4.34/1.88 4.34/1.88 (0) Prolog 4.34/1.88 (1) PrologToPiTRSProof [SOUND, 0 ms] 4.34/1.88 (2) PiTRS 4.34/1.88 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.34/1.88 (4) PiDP 4.34/1.88 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.34/1.88 (6) AND 4.34/1.88 (7) PiDP 4.34/1.88 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.34/1.88 (9) PiDP 4.34/1.88 (10) PiDPToQDPProof [EQUIVALENT, 0 ms] 4.34/1.88 (11) QDP 4.34/1.88 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.34/1.88 (13) YES 4.34/1.88 (14) PiDP 4.34/1.88 (15) UsableRulesProof [EQUIVALENT, 0 ms] 4.34/1.88 (16) PiDP 4.34/1.88 (17) PiDPToQDPProof [SOUND, 0 ms] 4.34/1.88 (18) QDP 4.34/1.88 (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.34/1.88 (20) YES 4.34/1.88 4.34/1.88 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (0) 4.34/1.88 Obligation: 4.34/1.88 Clauses: 4.34/1.88 4.34/1.88 overlap(Xs, Ys) :- ','(member2(X, Xs), member1(X, Ys)). 4.34/1.88 has_a_or_b(Xs) :- overlap(Xs, .(a, .(b, []))). 4.34/1.88 member1(X, .(Y, Xs)) :- member1(X, Xs). 4.34/1.88 member1(X, .(X, Xs)). 4.34/1.88 member2(X, .(Y, Xs)) :- member2(X, Xs). 4.34/1.88 member2(X, .(X, Xs)). 4.34/1.88 4.34/1.88 4.34/1.88 Query: overlap(g,g) 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (1) PrologToPiTRSProof (SOUND) 4.34/1.88 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 4.34/1.88 4.34/1.88 overlap_in_2: (b,b) 4.34/1.88 4.34/1.88 member2_in_2: (f,b) 4.34/1.88 4.34/1.88 member1_in_2: (b,b) 4.34/1.88 4.34/1.88 Transforming Prolog into the following Term Rewriting System: 4.34/1.88 4.34/1.88 Pi-finite rewrite system: 4.34/1.88 The TRS R consists of the following rules: 4.34/1.88 4.34/1.88 overlap_in_gg(Xs, Ys) -> U1_gg(Xs, Ys, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(Y, Xs)) -> U5_ag(X, Y, Xs, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(X, Xs)) -> member2_out_ag(X, .(X, Xs)) 4.34/1.88 U5_ag(X, Y, Xs, member2_out_ag(X, Xs)) -> member2_out_ag(X, .(Y, Xs)) 4.34/1.88 U1_gg(Xs, Ys, member2_out_ag(X, Xs)) -> U2_gg(Xs, Ys, member1_in_gg(X, Ys)) 4.34/1.88 member1_in_gg(X, .(Y, Xs)) -> U4_gg(X, Y, Xs, member1_in_gg(X, Xs)) 4.34/1.88 member1_in_gg(X, .(X, Xs)) -> member1_out_gg(X, .(X, Xs)) 4.34/1.88 U4_gg(X, Y, Xs, member1_out_gg(X, Xs)) -> member1_out_gg(X, .(Y, Xs)) 4.34/1.88 U2_gg(Xs, Ys, member1_out_gg(X, Ys)) -> overlap_out_gg(Xs, Ys) 4.34/1.88 4.34/1.88 The argument filtering Pi contains the following mapping: 4.34/1.88 overlap_in_gg(x1, x2) = overlap_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U1_gg(x1, x2, x3) = U1_gg(x2, x3) 4.34/1.88 4.34/1.88 member2_in_ag(x1, x2) = member2_in_ag(x2) 4.34/1.88 4.34/1.88 .(x1, x2) = .(x1, x2) 4.34/1.88 4.34/1.88 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.34/1.88 4.34/1.88 member2_out_ag(x1, x2) = member2_out_ag(x1) 4.34/1.88 4.34/1.88 U2_gg(x1, x2, x3) = U2_gg(x3) 4.34/1.88 4.34/1.88 member1_in_gg(x1, x2) = member1_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 4.34/1.88 4.34/1.88 member1_out_gg(x1, x2) = member1_out_gg 4.34/1.88 4.34/1.88 overlap_out_gg(x1, x2) = overlap_out_gg 4.34/1.88 4.34/1.88 4.34/1.88 4.34/1.88 4.34/1.88 4.34/1.88 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 4.34/1.88 4.34/1.88 4.34/1.88 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (2) 4.34/1.88 Obligation: 4.34/1.88 Pi-finite rewrite system: 4.34/1.88 The TRS R consists of the following rules: 4.34/1.88 4.34/1.88 overlap_in_gg(Xs, Ys) -> U1_gg(Xs, Ys, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(Y, Xs)) -> U5_ag(X, Y, Xs, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(X, Xs)) -> member2_out_ag(X, .(X, Xs)) 4.34/1.88 U5_ag(X, Y, Xs, member2_out_ag(X, Xs)) -> member2_out_ag(X, .(Y, Xs)) 4.34/1.88 U1_gg(Xs, Ys, member2_out_ag(X, Xs)) -> U2_gg(Xs, Ys, member1_in_gg(X, Ys)) 4.34/1.88 member1_in_gg(X, .(Y, Xs)) -> U4_gg(X, Y, Xs, member1_in_gg(X, Xs)) 4.34/1.88 member1_in_gg(X, .(X, Xs)) -> member1_out_gg(X, .(X, Xs)) 4.34/1.88 U4_gg(X, Y, Xs, member1_out_gg(X, Xs)) -> member1_out_gg(X, .(Y, Xs)) 4.34/1.88 U2_gg(Xs, Ys, member1_out_gg(X, Ys)) -> overlap_out_gg(Xs, Ys) 4.34/1.88 4.34/1.88 The argument filtering Pi contains the following mapping: 4.34/1.88 overlap_in_gg(x1, x2) = overlap_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U1_gg(x1, x2, x3) = U1_gg(x2, x3) 4.34/1.88 4.34/1.88 member2_in_ag(x1, x2) = member2_in_ag(x2) 4.34/1.88 4.34/1.88 .(x1, x2) = .(x1, x2) 4.34/1.88 4.34/1.88 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.34/1.88 4.34/1.88 member2_out_ag(x1, x2) = member2_out_ag(x1) 4.34/1.88 4.34/1.88 U2_gg(x1, x2, x3) = U2_gg(x3) 4.34/1.88 4.34/1.88 member1_in_gg(x1, x2) = member1_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 4.34/1.88 4.34/1.88 member1_out_gg(x1, x2) = member1_out_gg 4.34/1.88 4.34/1.88 overlap_out_gg(x1, x2) = overlap_out_gg 4.34/1.88 4.34/1.88 4.34/1.88 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (3) DependencyPairsProof (EQUIVALENT) 4.34/1.88 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 4.34/1.88 Pi DP problem: 4.34/1.88 The TRS P consists of the following rules: 4.34/1.88 4.34/1.88 OVERLAP_IN_GG(Xs, Ys) -> U1_GG(Xs, Ys, member2_in_ag(X, Xs)) 4.34/1.88 OVERLAP_IN_GG(Xs, Ys) -> MEMBER2_IN_AG(X, Xs) 4.34/1.88 MEMBER2_IN_AG(X, .(Y, Xs)) -> U5_AG(X, Y, Xs, member2_in_ag(X, Xs)) 4.34/1.88 MEMBER2_IN_AG(X, .(Y, Xs)) -> MEMBER2_IN_AG(X, Xs) 4.34/1.88 U1_GG(Xs, Ys, member2_out_ag(X, Xs)) -> U2_GG(Xs, Ys, member1_in_gg(X, Ys)) 4.34/1.88 U1_GG(Xs, Ys, member2_out_ag(X, Xs)) -> MEMBER1_IN_GG(X, Ys) 4.34/1.88 MEMBER1_IN_GG(X, .(Y, Xs)) -> U4_GG(X, Y, Xs, member1_in_gg(X, Xs)) 4.34/1.88 MEMBER1_IN_GG(X, .(Y, Xs)) -> MEMBER1_IN_GG(X, Xs) 4.34/1.88 4.34/1.88 The TRS R consists of the following rules: 4.34/1.88 4.34/1.88 overlap_in_gg(Xs, Ys) -> U1_gg(Xs, Ys, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(Y, Xs)) -> U5_ag(X, Y, Xs, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(X, Xs)) -> member2_out_ag(X, .(X, Xs)) 4.34/1.88 U5_ag(X, Y, Xs, member2_out_ag(X, Xs)) -> member2_out_ag(X, .(Y, Xs)) 4.34/1.88 U1_gg(Xs, Ys, member2_out_ag(X, Xs)) -> U2_gg(Xs, Ys, member1_in_gg(X, Ys)) 4.34/1.88 member1_in_gg(X, .(Y, Xs)) -> U4_gg(X, Y, Xs, member1_in_gg(X, Xs)) 4.34/1.88 member1_in_gg(X, .(X, Xs)) -> member1_out_gg(X, .(X, Xs)) 4.34/1.88 U4_gg(X, Y, Xs, member1_out_gg(X, Xs)) -> member1_out_gg(X, .(Y, Xs)) 4.34/1.88 U2_gg(Xs, Ys, member1_out_gg(X, Ys)) -> overlap_out_gg(Xs, Ys) 4.34/1.88 4.34/1.88 The argument filtering Pi contains the following mapping: 4.34/1.88 overlap_in_gg(x1, x2) = overlap_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U1_gg(x1, x2, x3) = U1_gg(x2, x3) 4.34/1.88 4.34/1.88 member2_in_ag(x1, x2) = member2_in_ag(x2) 4.34/1.88 4.34/1.88 .(x1, x2) = .(x1, x2) 4.34/1.88 4.34/1.88 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.34/1.88 4.34/1.88 member2_out_ag(x1, x2) = member2_out_ag(x1) 4.34/1.88 4.34/1.88 U2_gg(x1, x2, x3) = U2_gg(x3) 4.34/1.88 4.34/1.88 member1_in_gg(x1, x2) = member1_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 4.34/1.88 4.34/1.88 member1_out_gg(x1, x2) = member1_out_gg 4.34/1.88 4.34/1.88 overlap_out_gg(x1, x2) = overlap_out_gg 4.34/1.88 4.34/1.88 OVERLAP_IN_GG(x1, x2) = OVERLAP_IN_GG(x1, x2) 4.34/1.88 4.34/1.88 U1_GG(x1, x2, x3) = U1_GG(x2, x3) 4.34/1.88 4.34/1.88 MEMBER2_IN_AG(x1, x2) = MEMBER2_IN_AG(x2) 4.34/1.88 4.34/1.88 U5_AG(x1, x2, x3, x4) = U5_AG(x4) 4.34/1.88 4.34/1.88 U2_GG(x1, x2, x3) = U2_GG(x3) 4.34/1.88 4.34/1.88 MEMBER1_IN_GG(x1, x2) = MEMBER1_IN_GG(x1, x2) 4.34/1.88 4.34/1.88 U4_GG(x1, x2, x3, x4) = U4_GG(x4) 4.34/1.88 4.34/1.88 4.34/1.88 We have to consider all (P,R,Pi)-chains 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (4) 4.34/1.88 Obligation: 4.34/1.88 Pi DP problem: 4.34/1.88 The TRS P consists of the following rules: 4.34/1.88 4.34/1.88 OVERLAP_IN_GG(Xs, Ys) -> U1_GG(Xs, Ys, member2_in_ag(X, Xs)) 4.34/1.88 OVERLAP_IN_GG(Xs, Ys) -> MEMBER2_IN_AG(X, Xs) 4.34/1.88 MEMBER2_IN_AG(X, .(Y, Xs)) -> U5_AG(X, Y, Xs, member2_in_ag(X, Xs)) 4.34/1.88 MEMBER2_IN_AG(X, .(Y, Xs)) -> MEMBER2_IN_AG(X, Xs) 4.34/1.88 U1_GG(Xs, Ys, member2_out_ag(X, Xs)) -> U2_GG(Xs, Ys, member1_in_gg(X, Ys)) 4.34/1.88 U1_GG(Xs, Ys, member2_out_ag(X, Xs)) -> MEMBER1_IN_GG(X, Ys) 4.34/1.88 MEMBER1_IN_GG(X, .(Y, Xs)) -> U4_GG(X, Y, Xs, member1_in_gg(X, Xs)) 4.34/1.88 MEMBER1_IN_GG(X, .(Y, Xs)) -> MEMBER1_IN_GG(X, Xs) 4.34/1.88 4.34/1.88 The TRS R consists of the following rules: 4.34/1.88 4.34/1.88 overlap_in_gg(Xs, Ys) -> U1_gg(Xs, Ys, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(Y, Xs)) -> U5_ag(X, Y, Xs, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(X, Xs)) -> member2_out_ag(X, .(X, Xs)) 4.34/1.88 U5_ag(X, Y, Xs, member2_out_ag(X, Xs)) -> member2_out_ag(X, .(Y, Xs)) 4.34/1.88 U1_gg(Xs, Ys, member2_out_ag(X, Xs)) -> U2_gg(Xs, Ys, member1_in_gg(X, Ys)) 4.34/1.88 member1_in_gg(X, .(Y, Xs)) -> U4_gg(X, Y, Xs, member1_in_gg(X, Xs)) 4.34/1.88 member1_in_gg(X, .(X, Xs)) -> member1_out_gg(X, .(X, Xs)) 4.34/1.88 U4_gg(X, Y, Xs, member1_out_gg(X, Xs)) -> member1_out_gg(X, .(Y, Xs)) 4.34/1.88 U2_gg(Xs, Ys, member1_out_gg(X, Ys)) -> overlap_out_gg(Xs, Ys) 4.34/1.88 4.34/1.88 The argument filtering Pi contains the following mapping: 4.34/1.88 overlap_in_gg(x1, x2) = overlap_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U1_gg(x1, x2, x3) = U1_gg(x2, x3) 4.34/1.88 4.34/1.88 member2_in_ag(x1, x2) = member2_in_ag(x2) 4.34/1.88 4.34/1.88 .(x1, x2) = .(x1, x2) 4.34/1.88 4.34/1.88 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.34/1.88 4.34/1.88 member2_out_ag(x1, x2) = member2_out_ag(x1) 4.34/1.88 4.34/1.88 U2_gg(x1, x2, x3) = U2_gg(x3) 4.34/1.88 4.34/1.88 member1_in_gg(x1, x2) = member1_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 4.34/1.88 4.34/1.88 member1_out_gg(x1, x2) = member1_out_gg 4.34/1.88 4.34/1.88 overlap_out_gg(x1, x2) = overlap_out_gg 4.34/1.88 4.34/1.88 OVERLAP_IN_GG(x1, x2) = OVERLAP_IN_GG(x1, x2) 4.34/1.88 4.34/1.88 U1_GG(x1, x2, x3) = U1_GG(x2, x3) 4.34/1.88 4.34/1.88 MEMBER2_IN_AG(x1, x2) = MEMBER2_IN_AG(x2) 4.34/1.88 4.34/1.88 U5_AG(x1, x2, x3, x4) = U5_AG(x4) 4.34/1.88 4.34/1.88 U2_GG(x1, x2, x3) = U2_GG(x3) 4.34/1.88 4.34/1.88 MEMBER1_IN_GG(x1, x2) = MEMBER1_IN_GG(x1, x2) 4.34/1.88 4.34/1.88 U4_GG(x1, x2, x3, x4) = U4_GG(x4) 4.34/1.88 4.34/1.88 4.34/1.88 We have to consider all (P,R,Pi)-chains 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (5) DependencyGraphProof (EQUIVALENT) 4.34/1.88 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (6) 4.34/1.88 Complex Obligation (AND) 4.34/1.88 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (7) 4.34/1.88 Obligation: 4.34/1.88 Pi DP problem: 4.34/1.88 The TRS P consists of the following rules: 4.34/1.88 4.34/1.88 MEMBER1_IN_GG(X, .(Y, Xs)) -> MEMBER1_IN_GG(X, Xs) 4.34/1.88 4.34/1.88 The TRS R consists of the following rules: 4.34/1.88 4.34/1.88 overlap_in_gg(Xs, Ys) -> U1_gg(Xs, Ys, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(Y, Xs)) -> U5_ag(X, Y, Xs, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(X, Xs)) -> member2_out_ag(X, .(X, Xs)) 4.34/1.88 U5_ag(X, Y, Xs, member2_out_ag(X, Xs)) -> member2_out_ag(X, .(Y, Xs)) 4.34/1.88 U1_gg(Xs, Ys, member2_out_ag(X, Xs)) -> U2_gg(Xs, Ys, member1_in_gg(X, Ys)) 4.34/1.88 member1_in_gg(X, .(Y, Xs)) -> U4_gg(X, Y, Xs, member1_in_gg(X, Xs)) 4.34/1.88 member1_in_gg(X, .(X, Xs)) -> member1_out_gg(X, .(X, Xs)) 4.34/1.88 U4_gg(X, Y, Xs, member1_out_gg(X, Xs)) -> member1_out_gg(X, .(Y, Xs)) 4.34/1.88 U2_gg(Xs, Ys, member1_out_gg(X, Ys)) -> overlap_out_gg(Xs, Ys) 4.34/1.88 4.34/1.88 The argument filtering Pi contains the following mapping: 4.34/1.88 overlap_in_gg(x1, x2) = overlap_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U1_gg(x1, x2, x3) = U1_gg(x2, x3) 4.34/1.88 4.34/1.88 member2_in_ag(x1, x2) = member2_in_ag(x2) 4.34/1.88 4.34/1.88 .(x1, x2) = .(x1, x2) 4.34/1.88 4.34/1.88 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.34/1.88 4.34/1.88 member2_out_ag(x1, x2) = member2_out_ag(x1) 4.34/1.88 4.34/1.88 U2_gg(x1, x2, x3) = U2_gg(x3) 4.34/1.88 4.34/1.88 member1_in_gg(x1, x2) = member1_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 4.34/1.88 4.34/1.88 member1_out_gg(x1, x2) = member1_out_gg 4.34/1.88 4.34/1.88 overlap_out_gg(x1, x2) = overlap_out_gg 4.34/1.88 4.34/1.88 MEMBER1_IN_GG(x1, x2) = MEMBER1_IN_GG(x1, x2) 4.34/1.88 4.34/1.88 4.34/1.88 We have to consider all (P,R,Pi)-chains 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (8) UsableRulesProof (EQUIVALENT) 4.34/1.88 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (9) 4.34/1.88 Obligation: 4.34/1.88 Pi DP problem: 4.34/1.88 The TRS P consists of the following rules: 4.34/1.88 4.34/1.88 MEMBER1_IN_GG(X, .(Y, Xs)) -> MEMBER1_IN_GG(X, Xs) 4.34/1.88 4.34/1.88 R is empty. 4.34/1.88 Pi is empty. 4.34/1.88 We have to consider all (P,R,Pi)-chains 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (10) PiDPToQDPProof (EQUIVALENT) 4.34/1.88 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (11) 4.34/1.88 Obligation: 4.34/1.88 Q DP problem: 4.34/1.88 The TRS P consists of the following rules: 4.34/1.88 4.34/1.88 MEMBER1_IN_GG(X, .(Y, Xs)) -> MEMBER1_IN_GG(X, Xs) 4.34/1.88 4.34/1.88 R is empty. 4.34/1.88 Q is empty. 4.34/1.88 We have to consider all (P,Q,R)-chains. 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (12) QDPSizeChangeProof (EQUIVALENT) 4.34/1.88 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. 4.34/1.88 4.34/1.88 From the DPs we obtained the following set of size-change graphs: 4.34/1.88 *MEMBER1_IN_GG(X, .(Y, Xs)) -> MEMBER1_IN_GG(X, Xs) 4.34/1.88 The graph contains the following edges 1 >= 1, 2 > 2 4.34/1.88 4.34/1.88 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (13) 4.34/1.88 YES 4.34/1.88 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (14) 4.34/1.88 Obligation: 4.34/1.88 Pi DP problem: 4.34/1.88 The TRS P consists of the following rules: 4.34/1.88 4.34/1.88 MEMBER2_IN_AG(X, .(Y, Xs)) -> MEMBER2_IN_AG(X, Xs) 4.34/1.88 4.34/1.88 The TRS R consists of the following rules: 4.34/1.88 4.34/1.88 overlap_in_gg(Xs, Ys) -> U1_gg(Xs, Ys, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(Y, Xs)) -> U5_ag(X, Y, Xs, member2_in_ag(X, Xs)) 4.34/1.88 member2_in_ag(X, .(X, Xs)) -> member2_out_ag(X, .(X, Xs)) 4.34/1.88 U5_ag(X, Y, Xs, member2_out_ag(X, Xs)) -> member2_out_ag(X, .(Y, Xs)) 4.34/1.88 U1_gg(Xs, Ys, member2_out_ag(X, Xs)) -> U2_gg(Xs, Ys, member1_in_gg(X, Ys)) 4.34/1.88 member1_in_gg(X, .(Y, Xs)) -> U4_gg(X, Y, Xs, member1_in_gg(X, Xs)) 4.34/1.88 member1_in_gg(X, .(X, Xs)) -> member1_out_gg(X, .(X, Xs)) 4.34/1.88 U4_gg(X, Y, Xs, member1_out_gg(X, Xs)) -> member1_out_gg(X, .(Y, Xs)) 4.34/1.88 U2_gg(Xs, Ys, member1_out_gg(X, Ys)) -> overlap_out_gg(Xs, Ys) 4.34/1.88 4.34/1.88 The argument filtering Pi contains the following mapping: 4.34/1.88 overlap_in_gg(x1, x2) = overlap_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U1_gg(x1, x2, x3) = U1_gg(x2, x3) 4.34/1.88 4.34/1.88 member2_in_ag(x1, x2) = member2_in_ag(x2) 4.34/1.88 4.34/1.88 .(x1, x2) = .(x1, x2) 4.34/1.88 4.34/1.88 U5_ag(x1, x2, x3, x4) = U5_ag(x4) 4.34/1.88 4.34/1.88 member2_out_ag(x1, x2) = member2_out_ag(x1) 4.34/1.88 4.34/1.88 U2_gg(x1, x2, x3) = U2_gg(x3) 4.34/1.88 4.34/1.88 member1_in_gg(x1, x2) = member1_in_gg(x1, x2) 4.34/1.88 4.34/1.88 U4_gg(x1, x2, x3, x4) = U4_gg(x4) 4.34/1.88 4.34/1.88 member1_out_gg(x1, x2) = member1_out_gg 4.34/1.88 4.34/1.88 overlap_out_gg(x1, x2) = overlap_out_gg 4.34/1.88 4.34/1.88 MEMBER2_IN_AG(x1, x2) = MEMBER2_IN_AG(x2) 4.34/1.88 4.34/1.88 4.34/1.88 We have to consider all (P,R,Pi)-chains 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (15) UsableRulesProof (EQUIVALENT) 4.34/1.88 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 4.34/1.88 ---------------------------------------- 4.34/1.88 4.34/1.88 (16) 4.34/1.88 Obligation: 4.34/1.88 Pi DP problem: 4.34/1.88 The TRS P consists of the following rules: 4.34/1.88 4.34/1.88 MEMBER2_IN_AG(X, .(Y, Xs)) -> MEMBER2_IN_AG(X, Xs) 4.34/1.88 4.34/1.88 R is empty. 4.34/1.88 The argument filtering Pi contains the following mapping: 4.34/1.88 .(x1, x2) = .(x1, x2) 4.34/1.88 4.34/1.88 MEMBER2_IN_AG(x1, x2) = MEMBER2_IN_AG(x2) 4.34/1.88 4.34/1.88 4.34/1.88 We have to consider all (P,R,Pi)-chains 4.34/1.89 ---------------------------------------- 4.34/1.89 4.34/1.89 (17) PiDPToQDPProof (SOUND) 4.34/1.89 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 4.34/1.89 ---------------------------------------- 4.34/1.89 4.34/1.89 (18) 4.34/1.89 Obligation: 4.34/1.89 Q DP problem: 4.34/1.89 The TRS P consists of the following rules: 4.34/1.89 4.34/1.89 MEMBER2_IN_AG(.(Y, Xs)) -> MEMBER2_IN_AG(Xs) 4.34/1.89 4.34/1.89 R is empty. 4.34/1.89 Q is empty. 4.34/1.89 We have to consider all (P,Q,R)-chains. 4.34/1.89 ---------------------------------------- 4.34/1.89 4.34/1.89 (19) QDPSizeChangeProof (EQUIVALENT) 4.34/1.89 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. 4.34/1.89 4.34/1.89 From the DPs we obtained the following set of size-change graphs: 4.34/1.89 *MEMBER2_IN_AG(.(Y, Xs)) -> MEMBER2_IN_AG(Xs) 4.34/1.89 The graph contains the following edges 1 > 1 4.34/1.89 4.34/1.89 4.34/1.89 ---------------------------------------- 4.34/1.89 4.34/1.89 (20) 4.34/1.89 YES 4.34/1.92 EOF