8.17/2.94 MAYBE 8.17/2.97 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 8.17/2.97 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.17/2.97 8.17/2.97 8.17/2.97 Left Termination of the query pattern 8.17/2.97 8.17/2.97 subset1(a,g) 8.17/2.97 8.17/2.97 w.r.t. the given Prolog program could not be shown: 8.17/2.97 8.17/2.97 (0) Prolog 8.17/2.97 (1) PrologToPiTRSProof [SOUND, 0 ms] 8.17/2.97 (2) PiTRS 8.17/2.97 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 8.17/2.97 (4) PiDP 8.17/2.97 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 8.17/2.97 (6) AND 8.17/2.97 (7) PiDP 8.17/2.97 (8) UsableRulesProof [EQUIVALENT, 0 ms] 8.17/2.97 (9) PiDP 8.17/2.97 (10) PiDPToQDPProof [SOUND, 0 ms] 8.17/2.97 (11) QDP 8.17/2.97 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.17/2.97 (13) YES 8.17/2.97 (14) PiDP 8.17/2.97 (15) UsableRulesProof [EQUIVALENT, 0 ms] 8.17/2.97 (16) PiDP 8.17/2.97 (17) PiDPToQDPProof [SOUND, 0 ms] 8.17/2.97 (18) QDP 8.17/2.97 (19) TransformationProof [SOUND, 0 ms] 8.17/2.97 (20) QDP 8.17/2.97 (21) TransformationProof [EQUIVALENT, 0 ms] 8.17/2.97 (22) QDP 8.17/2.97 (23) PrologToPiTRSProof [SOUND, 0 ms] 8.17/2.97 (24) PiTRS 8.17/2.97 (25) DependencyPairsProof [EQUIVALENT, 0 ms] 8.17/2.97 (26) PiDP 8.17/2.97 (27) DependencyGraphProof [EQUIVALENT, 0 ms] 8.17/2.97 (28) AND 8.17/2.97 (29) PiDP 8.17/2.97 (30) UsableRulesProof [EQUIVALENT, 0 ms] 8.17/2.97 (31) PiDP 8.17/2.97 (32) PiDPToQDPProof [SOUND, 0 ms] 8.17/2.97 (33) QDP 8.17/2.97 (34) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.17/2.97 (35) YES 8.17/2.97 (36) PiDP 8.17/2.97 (37) UsableRulesProof [EQUIVALENT, 0 ms] 8.17/2.97 (38) PiDP 8.17/2.97 (39) PiDPToQDPProof [SOUND, 0 ms] 8.17/2.97 (40) QDP 8.17/2.97 (41) TransformationProof [SOUND, 0 ms] 8.17/2.97 (42) QDP 8.17/2.97 (43) TransformationProof [EQUIVALENT, 0 ms] 8.17/2.97 (44) QDP 8.17/2.97 (45) PrologToTRSTransformerProof [SOUND, 0 ms] 8.17/2.97 (46) QTRS 8.17/2.97 (47) DependencyPairsProof [EQUIVALENT, 0 ms] 8.17/2.97 (48) QDP 8.17/2.97 (49) DependencyGraphProof [EQUIVALENT, 0 ms] 8.17/2.97 (50) AND 8.17/2.97 (51) QDP 8.17/2.97 (52) UsableRulesProof [EQUIVALENT, 0 ms] 8.17/2.97 (53) QDP 8.17/2.97 (54) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.17/2.97 (55) YES 8.17/2.97 (56) QDP 8.17/2.97 (57) NonTerminationLoopProof [COMPLETE, 0 ms] 8.17/2.97 (58) NO 8.17/2.97 (59) PrologToDTProblemTransformerProof [SOUND, 0 ms] 8.17/2.97 (60) TRIPLES 8.17/2.97 (61) TriplesToPiDPProof [SOUND, 0 ms] 8.17/2.97 (62) PiDP 8.17/2.97 (63) DependencyGraphProof [EQUIVALENT, 0 ms] 8.17/2.97 (64) AND 8.17/2.97 (65) PiDP 8.17/2.97 (66) UsableRulesProof [EQUIVALENT, 0 ms] 8.17/2.97 (67) PiDP 8.17/2.97 (68) PiDPToQDPProof [SOUND, 0 ms] 8.17/2.97 (69) QDP 8.17/2.97 (70) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.17/2.97 (71) YES 8.17/2.97 (72) PiDP 8.17/2.97 (73) PiDPToQDPProof [SOUND, 0 ms] 8.17/2.97 (74) QDP 8.17/2.97 (75) TransformationProof [SOUND, 0 ms] 8.17/2.97 (76) QDP 8.17/2.97 (77) TransformationProof [EQUIVALENT, 0 ms] 8.17/2.97 (78) QDP 8.17/2.97 (79) PrologToIRSwTTransformerProof [SOUND, 31 ms] 8.17/2.97 (80) AND 8.17/2.97 (81) IRSwT 8.17/2.97 (82) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 8.17/2.97 (83) IRSwT 8.17/2.97 (84) IntTRSCompressionProof [EQUIVALENT, 19 ms] 8.17/2.97 (85) IRSwT 8.17/2.97 (86) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.17/2.97 (87) IRSwT 8.17/2.97 (88) IRSwTTerminationDigraphProof [EQUIVALENT, 7 ms] 8.17/2.97 (89) IRSwT 8.17/2.97 (90) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 25 ms] 8.17/2.97 (91) IRSwT 8.17/2.97 (92) TempFilterProof [SOUND, 2 ms] 8.17/2.97 (93) IRSwT 8.17/2.97 (94) IRSwTToQDPProof [SOUND, 0 ms] 8.17/2.97 (95) QDP 8.17/2.97 (96) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.17/2.97 (97) YES 8.17/2.97 (98) IRSwT 8.17/2.97 (99) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 8.17/2.97 (100) IRSwT 8.17/2.97 (101) IntTRSCompressionProof [EQUIVALENT, 15 ms] 8.17/2.97 (102) IRSwT 8.17/2.97 (103) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 8.17/2.97 (104) IRSwT 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (0) 8.17/2.97 Obligation: 8.17/2.97 Clauses: 8.17/2.97 8.17/2.97 member(X, .(Y, Xs)) :- member(X, Xs). 8.17/2.97 member(X, .(X, Xs)). 8.17/2.97 subset(.(X, Xs), Ys) :- ','(member(X, Ys), subset(Xs, Ys)). 8.17/2.97 subset([], Ys). 8.17/2.97 member1(X, .(Y, Xs)) :- member1(X, Xs). 8.17/2.97 member1(X, .(X, Xs)). 8.17/2.97 subset1(.(X, Xs), Ys) :- ','(member1(X, Ys), subset1(Xs, Ys)). 8.17/2.97 subset1([], Ys). 8.17/2.97 8.17/2.97 8.17/2.97 Query: subset1(a,g) 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (1) PrologToPiTRSProof (SOUND) 8.17/2.97 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.17/2.97 8.17/2.97 subset1_in_2: (f,b) 8.17/2.97 8.17/2.97 member1_in_2: (f,b) 8.17/2.97 8.17/2.97 Transforming Prolog into the following Term Rewriting System: 8.17/2.97 8.17/2.97 Pi-finite rewrite system: 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1) 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (2) 8.17/2.97 Obligation: 8.17/2.97 Pi-finite rewrite system: 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1) 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (3) DependencyPairsProof (EQUIVALENT) 8.17/2.97 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> U5_AG(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> MEMBER1_IN_AG(X, Ys) 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> U4_AG(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> MEMBER1_IN_AG(X, Xs) 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_AG(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Xs, Ys) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1) 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(x1, x2) = SUBSET1_IN_AG(x2) 8.17/2.97 8.17/2.97 U5_AG(x1, x2, x3, x4) = U5_AG(x3, x4) 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) 8.17/2.97 8.17/2.97 U4_AG(x1, x2, x3, x4) = U4_AG(x4) 8.17/2.97 8.17/2.97 U6_AG(x1, x2, x3, x4) = U6_AG(x1, x4) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (4) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> U5_AG(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> MEMBER1_IN_AG(X, Ys) 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> U4_AG(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> MEMBER1_IN_AG(X, Xs) 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_AG(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Xs, Ys) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1) 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(x1, x2) = SUBSET1_IN_AG(x2) 8.17/2.97 8.17/2.97 U5_AG(x1, x2, x3, x4) = U5_AG(x3, x4) 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) 8.17/2.97 8.17/2.97 U4_AG(x1, x2, x3, x4) = U4_AG(x4) 8.17/2.97 8.17/2.97 U6_AG(x1, x2, x3, x4) = U6_AG(x1, x4) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (5) DependencyGraphProof (EQUIVALENT) 8.17/2.97 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (6) 8.17/2.97 Complex Obligation (AND) 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (7) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> MEMBER1_IN_AG(X, Xs) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1) 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (8) UsableRulesProof (EQUIVALENT) 8.17/2.97 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (9) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> MEMBER1_IN_AG(X, Xs) 8.17/2.97 8.17/2.97 R is empty. 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (10) PiDPToQDPProof (SOUND) 8.17/2.97 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (11) 8.17/2.97 Obligation: 8.17/2.97 Q DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(.(Y, Xs)) -> MEMBER1_IN_AG(Xs) 8.17/2.97 8.17/2.97 R is empty. 8.17/2.97 Q is empty. 8.17/2.97 We have to consider all (P,Q,R)-chains. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (12) QDPSizeChangeProof (EQUIVALENT) 8.17/2.97 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. 8.17/2.97 8.17/2.97 From the DPs we obtained the following set of size-change graphs: 8.17/2.97 *MEMBER1_IN_AG(.(Y, Xs)) -> MEMBER1_IN_AG(Xs) 8.17/2.97 The graph contains the following edges 1 > 1 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (13) 8.17/2.97 YES 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (14) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Xs, Ys) 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> U5_AG(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1) 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(x1, x2) = SUBSET1_IN_AG(x2) 8.17/2.97 8.17/2.97 U5_AG(x1, x2, x3, x4) = U5_AG(x3, x4) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (15) UsableRulesProof (EQUIVALENT) 8.17/2.97 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (16) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Xs, Ys) 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> U5_AG(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1) 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(x1, x2) = SUBSET1_IN_AG(x2) 8.17/2.97 8.17/2.97 U5_AG(x1, x2, x3, x4) = U5_AG(x3, x4) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (17) PiDPToQDPProof (SOUND) 8.17/2.97 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (18) 8.17/2.97 Obligation: 8.17/2.97 Q DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 U5_AG(Ys, member1_out_ag(X)) -> SUBSET1_IN_AG(Ys) 8.17/2.97 SUBSET1_IN_AG(Ys) -> U5_AG(Ys, member1_in_ag(Ys)) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 member1_in_ag(.(Y, Xs)) -> U4_ag(member1_in_ag(Xs)) 8.17/2.97 member1_in_ag(.(X, Xs)) -> member1_out_ag(X) 8.17/2.97 U4_ag(member1_out_ag(X)) -> member1_out_ag(X) 8.17/2.97 8.17/2.97 The set Q consists of the following terms: 8.17/2.97 8.17/2.97 member1_in_ag(x0) 8.17/2.97 U4_ag(x0) 8.17/2.97 8.17/2.97 We have to consider all (P,Q,R)-chains. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (19) TransformationProof (SOUND) 8.17/2.97 By narrowing [LPAR04] the rule SUBSET1_IN_AG(Ys) -> U5_AG(Ys, member1_in_ag(Ys)) at position [1] we obtained the following new rules [LPAR04]: 8.17/2.97 8.17/2.97 (SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), U4_ag(member1_in_ag(x1))),SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), U4_ag(member1_in_ag(x1)))) 8.17/2.97 (SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), member1_out_ag(x0)),SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), member1_out_ag(x0))) 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (20) 8.17/2.97 Obligation: 8.17/2.97 Q DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 U5_AG(Ys, member1_out_ag(X)) -> SUBSET1_IN_AG(Ys) 8.17/2.97 SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), U4_ag(member1_in_ag(x1))) 8.17/2.97 SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), member1_out_ag(x0)) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 member1_in_ag(.(Y, Xs)) -> U4_ag(member1_in_ag(Xs)) 8.17/2.97 member1_in_ag(.(X, Xs)) -> member1_out_ag(X) 8.17/2.97 U4_ag(member1_out_ag(X)) -> member1_out_ag(X) 8.17/2.97 8.17/2.97 The set Q consists of the following terms: 8.17/2.97 8.17/2.97 member1_in_ag(x0) 8.17/2.97 U4_ag(x0) 8.17/2.97 8.17/2.97 We have to consider all (P,Q,R)-chains. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (21) TransformationProof (EQUIVALENT) 8.17/2.97 By instantiating [LPAR04] the rule U5_AG(Ys, member1_out_ag(X)) -> SUBSET1_IN_AG(Ys) we obtained the following new rules [LPAR04]: 8.17/2.97 8.17/2.97 (U5_AG(.(z0, z1), member1_out_ag(x1)) -> SUBSET1_IN_AG(.(z0, z1)),U5_AG(.(z0, z1), member1_out_ag(x1)) -> SUBSET1_IN_AG(.(z0, z1))) 8.17/2.97 (U5_AG(.(z0, z1), member1_out_ag(z0)) -> SUBSET1_IN_AG(.(z0, z1)),U5_AG(.(z0, z1), member1_out_ag(z0)) -> SUBSET1_IN_AG(.(z0, z1))) 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (22) 8.17/2.97 Obligation: 8.17/2.97 Q DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), U4_ag(member1_in_ag(x1))) 8.17/2.97 SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), member1_out_ag(x0)) 8.17/2.97 U5_AG(.(z0, z1), member1_out_ag(x1)) -> SUBSET1_IN_AG(.(z0, z1)) 8.17/2.97 U5_AG(.(z0, z1), member1_out_ag(z0)) -> SUBSET1_IN_AG(.(z0, z1)) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 member1_in_ag(.(Y, Xs)) -> U4_ag(member1_in_ag(Xs)) 8.17/2.97 member1_in_ag(.(X, Xs)) -> member1_out_ag(X) 8.17/2.97 U4_ag(member1_out_ag(X)) -> member1_out_ag(X) 8.17/2.97 8.17/2.97 The set Q consists of the following terms: 8.17/2.97 8.17/2.97 member1_in_ag(x0) 8.17/2.97 U4_ag(x0) 8.17/2.97 8.17/2.97 We have to consider all (P,Q,R)-chains. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (23) PrologToPiTRSProof (SOUND) 8.17/2.97 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.17/2.97 8.17/2.97 subset1_in_2: (f,b) 8.17/2.97 8.17/2.97 member1_in_2: (f,b) 8.17/2.97 8.17/2.97 Transforming Prolog into the following Term Rewriting System: 8.17/2.97 8.17/2.97 Pi-finite rewrite system: 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x2, x3, x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x3, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (24) 8.17/2.97 Obligation: 8.17/2.97 Pi-finite rewrite system: 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x2, x3, x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x3, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (25) DependencyPairsProof (EQUIVALENT) 8.17/2.97 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> U5_AG(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> MEMBER1_IN_AG(X, Ys) 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> U4_AG(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> MEMBER1_IN_AG(X, Xs) 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_AG(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Xs, Ys) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x2, x3, x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x3, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(x1, x2) = SUBSET1_IN_AG(x2) 8.17/2.97 8.17/2.97 U5_AG(x1, x2, x3, x4) = U5_AG(x3, x4) 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) 8.17/2.97 8.17/2.97 U4_AG(x1, x2, x3, x4) = U4_AG(x2, x3, x4) 8.17/2.97 8.17/2.97 U6_AG(x1, x2, x3, x4) = U6_AG(x1, x3, x4) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (26) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> U5_AG(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> MEMBER1_IN_AG(X, Ys) 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> U4_AG(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> MEMBER1_IN_AG(X, Xs) 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_AG(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Xs, Ys) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x2, x3, x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x3, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(x1, x2) = SUBSET1_IN_AG(x2) 8.17/2.97 8.17/2.97 U5_AG(x1, x2, x3, x4) = U5_AG(x3, x4) 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) 8.17/2.97 8.17/2.97 U4_AG(x1, x2, x3, x4) = U4_AG(x2, x3, x4) 8.17/2.97 8.17/2.97 U6_AG(x1, x2, x3, x4) = U6_AG(x1, x3, x4) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (27) DependencyGraphProof (EQUIVALENT) 8.17/2.97 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (28) 8.17/2.97 Complex Obligation (AND) 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (29) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> MEMBER1_IN_AG(X, Xs) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x2, x3, x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x3, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (30) UsableRulesProof (EQUIVALENT) 8.17/2.97 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (31) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(X, .(Y, Xs)) -> MEMBER1_IN_AG(X, Xs) 8.17/2.97 8.17/2.97 R is empty. 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(x1, x2) = MEMBER1_IN_AG(x2) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (32) PiDPToQDPProof (SOUND) 8.17/2.97 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (33) 8.17/2.97 Obligation: 8.17/2.97 Q DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 MEMBER1_IN_AG(.(Y, Xs)) -> MEMBER1_IN_AG(Xs) 8.17/2.97 8.17/2.97 R is empty. 8.17/2.97 Q is empty. 8.17/2.97 We have to consider all (P,Q,R)-chains. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (34) QDPSizeChangeProof (EQUIVALENT) 8.17/2.97 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. 8.17/2.97 8.17/2.97 From the DPs we obtained the following set of size-change graphs: 8.17/2.97 *MEMBER1_IN_AG(.(Y, Xs)) -> MEMBER1_IN_AG(Xs) 8.17/2.97 The graph contains the following edges 1 > 1 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (35) 8.17/2.97 YES 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (36) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Xs, Ys) 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> U5_AG(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 subset1_in_ag(.(X, Xs), Ys) -> U5_ag(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 U5_ag(X, Xs, Ys, member1_out_ag(X, Ys)) -> U6_ag(X, Xs, Ys, subset1_in_ag(Xs, Ys)) 8.17/2.97 subset1_in_ag([], Ys) -> subset1_out_ag([], Ys) 8.17/2.97 U6_ag(X, Xs, Ys, subset1_out_ag(Xs, Ys)) -> subset1_out_ag(.(X, Xs), Ys) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 subset1_in_ag(x1, x2) = subset1_in_ag(x2) 8.17/2.97 8.17/2.97 U5_ag(x1, x2, x3, x4) = U5_ag(x3, x4) 8.17/2.97 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x2, x3, x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 U6_ag(x1, x2, x3, x4) = U6_ag(x1, x3, x4) 8.17/2.97 8.17/2.97 subset1_out_ag(x1, x2) = subset1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(x1, x2) = SUBSET1_IN_AG(x2) 8.17/2.97 8.17/2.97 U5_AG(x1, x2, x3, x4) = U5_AG(x3, x4) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (37) UsableRulesProof (EQUIVALENT) 8.17/2.97 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (38) 8.17/2.97 Obligation: 8.17/2.97 Pi DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 U5_AG(X, Xs, Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Xs, Ys) 8.17/2.97 SUBSET1_IN_AG(.(X, Xs), Ys) -> U5_AG(X, Xs, Ys, member1_in_ag(X, Ys)) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 member1_in_ag(X, .(Y, Xs)) -> U4_ag(X, Y, Xs, member1_in_ag(X, Xs)) 8.17/2.97 member1_in_ag(X, .(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(X, Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 8.17/2.97 The argument filtering Pi contains the following mapping: 8.17/2.97 member1_in_ag(x1, x2) = member1_in_ag(x2) 8.17/2.97 8.17/2.97 .(x1, x2) = .(x1, x2) 8.17/2.97 8.17/2.97 U4_ag(x1, x2, x3, x4) = U4_ag(x2, x3, x4) 8.17/2.97 8.17/2.97 member1_out_ag(x1, x2) = member1_out_ag(x1, x2) 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(x1, x2) = SUBSET1_IN_AG(x2) 8.17/2.97 8.17/2.97 U5_AG(x1, x2, x3, x4) = U5_AG(x3, x4) 8.17/2.97 8.17/2.97 8.17/2.97 We have to consider all (P,R,Pi)-chains 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (39) PiDPToQDPProof (SOUND) 8.17/2.97 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (40) 8.17/2.97 Obligation: 8.17/2.97 Q DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 U5_AG(Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Ys) 8.17/2.97 SUBSET1_IN_AG(Ys) -> U5_AG(Ys, member1_in_ag(Ys)) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 member1_in_ag(.(Y, Xs)) -> U4_ag(Y, Xs, member1_in_ag(Xs)) 8.17/2.97 member1_in_ag(.(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 8.17/2.97 The set Q consists of the following terms: 8.17/2.97 8.17/2.97 member1_in_ag(x0) 8.17/2.97 U4_ag(x0, x1, x2) 8.17/2.97 8.17/2.97 We have to consider all (P,Q,R)-chains. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (41) TransformationProof (SOUND) 8.17/2.97 By narrowing [LPAR04] the rule SUBSET1_IN_AG(Ys) -> U5_AG(Ys, member1_in_ag(Ys)) at position [1] we obtained the following new rules [LPAR04]: 8.17/2.97 8.17/2.97 (SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), U4_ag(x0, x1, member1_in_ag(x1))),SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), U4_ag(x0, x1, member1_in_ag(x1)))) 8.17/2.97 (SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), member1_out_ag(x0, .(x0, x1))),SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), member1_out_ag(x0, .(x0, x1)))) 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (42) 8.17/2.97 Obligation: 8.17/2.97 Q DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 U5_AG(Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Ys) 8.17/2.97 SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), U4_ag(x0, x1, member1_in_ag(x1))) 8.17/2.97 SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), member1_out_ag(x0, .(x0, x1))) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 member1_in_ag(.(Y, Xs)) -> U4_ag(Y, Xs, member1_in_ag(Xs)) 8.17/2.97 member1_in_ag(.(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 8.17/2.97 The set Q consists of the following terms: 8.17/2.97 8.17/2.97 member1_in_ag(x0) 8.17/2.97 U4_ag(x0, x1, x2) 8.17/2.97 8.17/2.97 We have to consider all (P,Q,R)-chains. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (43) TransformationProof (EQUIVALENT) 8.17/2.97 By instantiating [LPAR04] the rule U5_AG(Ys, member1_out_ag(X, Ys)) -> SUBSET1_IN_AG(Ys) we obtained the following new rules [LPAR04]: 8.17/2.97 8.17/2.97 (U5_AG(.(z0, z1), member1_out_ag(x1, .(z0, z1))) -> SUBSET1_IN_AG(.(z0, z1)),U5_AG(.(z0, z1), member1_out_ag(x1, .(z0, z1))) -> SUBSET1_IN_AG(.(z0, z1))) 8.17/2.97 (U5_AG(.(z0, z1), member1_out_ag(z0, .(z0, z1))) -> SUBSET1_IN_AG(.(z0, z1)),U5_AG(.(z0, z1), member1_out_ag(z0, .(z0, z1))) -> SUBSET1_IN_AG(.(z0, z1))) 8.17/2.97 8.17/2.97 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (44) 8.17/2.97 Obligation: 8.17/2.97 Q DP problem: 8.17/2.97 The TRS P consists of the following rules: 8.17/2.97 8.17/2.97 SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), U4_ag(x0, x1, member1_in_ag(x1))) 8.17/2.97 SUBSET1_IN_AG(.(x0, x1)) -> U5_AG(.(x0, x1), member1_out_ag(x0, .(x0, x1))) 8.17/2.97 U5_AG(.(z0, z1), member1_out_ag(x1, .(z0, z1))) -> SUBSET1_IN_AG(.(z0, z1)) 8.17/2.97 U5_AG(.(z0, z1), member1_out_ag(z0, .(z0, z1))) -> SUBSET1_IN_AG(.(z0, z1)) 8.17/2.97 8.17/2.97 The TRS R consists of the following rules: 8.17/2.97 8.17/2.97 member1_in_ag(.(Y, Xs)) -> U4_ag(Y, Xs, member1_in_ag(Xs)) 8.17/2.97 member1_in_ag(.(X, Xs)) -> member1_out_ag(X, .(X, Xs)) 8.17/2.97 U4_ag(Y, Xs, member1_out_ag(X, Xs)) -> member1_out_ag(X, .(Y, Xs)) 8.17/2.97 8.17/2.97 The set Q consists of the following terms: 8.17/2.97 8.17/2.97 member1_in_ag(x0) 8.17/2.97 U4_ag(x0, x1, x2) 8.17/2.97 8.17/2.97 We have to consider all (P,Q,R)-chains. 8.17/2.97 ---------------------------------------- 8.17/2.97 8.17/2.97 (45) PrologToTRSTransformerProof (SOUND) 8.17/2.97 Transformed Prolog program to TRS. 8.17/2.97 8.17/2.97 { 8.17/2.97 "root": 1, 8.17/2.97 "program": { 8.17/2.97 "directives": [], 8.17/2.97 "clauses": [ 8.17/2.97 [ 8.17/2.97 "(member X (. Y Xs))", 8.17/2.97 "(member X Xs)" 8.17/2.97 ], 8.17/2.97 [ 8.17/2.97 "(member X (. X Xs))", 8.17/2.97 null 8.17/2.97 ], 8.17/2.97 [ 8.17/2.97 "(subset (. X Xs) Ys)", 8.17/2.97 "(',' (member X Ys) (subset Xs Ys))" 8.17/2.97 ], 8.17/2.97 [ 8.17/2.97 "(subset ([]) Ys)", 8.17/2.97 null 8.17/2.97 ], 8.17/2.97 [ 8.17/2.97 "(member1 X (. Y Xs))", 8.17/2.97 "(member1 X Xs)" 8.17/2.97 ], 8.17/2.97 [ 8.17/2.97 "(member1 X (. X Xs))", 8.17/2.97 null 8.17/2.97 ], 8.17/2.97 [ 8.17/2.97 "(subset1 (. X Xs) Ys)", 8.17/2.97 "(',' (member1 X Ys) (subset1 Xs Ys))" 8.17/2.97 ], 8.17/2.97 [ 8.17/2.97 "(subset1 ([]) Ys)", 8.17/2.97 null 8.17/2.97 ] 8.17/2.97 ] 8.17/2.97 }, 8.17/2.97 "graph": { 8.17/2.97 "nodes": { 8.17/2.97 "79": { 8.17/2.97 "goal": [{ 8.17/2.97 "clause": -1, 8.17/2.97 "scope": -1, 8.17/2.97 "term": "(',' (member1 T18 T17) (subset1 T19 T17))" 8.17/2.97 }], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": ["T17"], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "280": { 8.17/2.97 "goal": [], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": [], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "281": { 8.17/2.97 "goal": [], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": [], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "type": "Nodes", 8.17/2.97 "150": { 8.17/2.97 "goal": [{ 8.17/2.97 "clause": -1, 8.17/2.97 "scope": -1, 8.17/2.97 "term": "(member1 T42 T41)" 8.17/2.97 }], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": ["T41"], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "151": { 8.17/2.97 "goal": [], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": [], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "284": { 8.17/2.97 "goal": [{ 8.17/2.97 "clause": -1, 8.17/2.97 "scope": -1, 8.17/2.97 "term": "(true)" 8.17/2.97 }], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": [], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "285": { 8.17/2.97 "goal": [], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": [], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "1": { 8.17/2.97 "goal": [{ 8.17/2.97 "clause": -1, 8.17/2.97 "scope": -1, 8.17/2.97 "term": "(subset1 T1 T2)" 8.17/2.97 }], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": ["T2"], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "144": { 8.17/2.97 "goal": [ 8.17/2.97 { 8.17/2.97 "clause": 4, 8.17/2.97 "scope": 2, 8.17/2.97 "term": "(member1 T18 T17)" 8.17/2.97 }, 8.17/2.97 { 8.17/2.97 "clause": 5, 8.17/2.97 "scope": 2, 8.17/2.97 "term": "(member1 T18 T17)" 8.17/2.97 } 8.17/2.97 ], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": ["T17"], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "287": { 8.17/2.97 "goal": [], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": [], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "3": { 8.17/2.97 "goal": [ 8.17/2.97 { 8.17/2.97 "clause": 6, 8.17/2.97 "scope": 1, 8.17/2.97 "term": "(subset1 T1 T2)" 8.17/2.97 }, 8.17/2.97 { 8.17/2.97 "clause": 7, 8.17/2.97 "scope": 1, 8.17/2.97 "term": "(subset1 T1 T2)" 8.17/2.97 } 8.17/2.97 ], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": ["T2"], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "279": { 8.17/2.97 "goal": [{ 8.17/2.97 "clause": -1, 8.17/2.97 "scope": -1, 8.17/2.97 "term": "(true)" 8.17/2.97 }], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": [], 8.17/2.97 "free": [], 8.17/2.97 "exprvars": [] 8.17/2.97 } 8.17/2.97 }, 8.17/2.97 "148": { 8.17/2.97 "goal": [{ 8.17/2.97 "clause": 4, 8.17/2.97 "scope": 2, 8.17/2.97 "term": "(member1 T18 T17)" 8.17/2.97 }], 8.17/2.97 "kb": { 8.17/2.97 "nonunifying": [], 8.17/2.97 "intvars": {}, 8.17/2.97 "arithmetic": { 8.17/2.97 "type": "PlainIntegerRelationState", 8.17/2.97 "relations": [] 8.17/2.97 }, 8.17/2.97 "ground": ["T17"], 8.17/2.97 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "138": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(member1 T18 T17)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T17"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "149": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 5, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(member1 T18 T17)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T17"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "139": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(subset1 T23 T17)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T17"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "85": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "42": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 6, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T2"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "43": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T2"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "edges": [ 8.17/2.98 { 8.17/2.98 "from": 1, 8.17/2.98 "to": 3, 8.17/2.98 "label": "CASE" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 3, 8.17/2.98 "to": 42, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 3, 8.17/2.98 "to": 43, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 42, 8.17/2.98 "to": 79, 8.17/2.98 "label": "EVAL with clause\nsubset1(.(X13, X14), X15) :- ','(member1(X13, X15), subset1(X14, X15)).\nand substitutionX13 -> T18,\nX14 -> T19,\nT1 -> .(T18, T19),\nT2 -> T17,\nX15 -> T17,\nT15 -> T18,\nT16 -> T19" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 42, 8.17/2.98 "to": 85, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 43, 8.17/2.98 "to": 284, 8.17/2.98 "label": "EVAL with clause\nsubset1([], X51).\nand substitutionT1 -> [],\nT2 -> T57,\nX51 -> T57" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 43, 8.17/2.98 "to": 285, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 79, 8.17/2.98 "to": 138, 8.17/2.98 "label": "SPLIT 1" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 79, 8.17/2.98 "to": 139, 8.17/2.98 "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nT17 is ground\nreplacements:T19 -> T23" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 138, 8.17/2.98 "to": 144, 8.17/2.98 "label": "CASE" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 139, 8.17/2.98 "to": 1, 8.17/2.98 "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T17" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 144, 8.17/2.98 "to": 148, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 144, 8.17/2.98 "to": 149, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 148, 8.17/2.98 "to": 150, 8.17/2.98 "label": "EVAL with clause\nmember1(X34, .(X35, X36)) :- member1(X34, X36).\nand substitutionT18 -> T42,\nX34 -> T42,\nX35 -> T40,\nX36 -> T41,\nT17 -> .(T40, T41),\nT39 -> T42" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 148, 8.17/2.98 "to": 151, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 149, 8.17/2.98 "to": 279, 8.17/2.98 "label": "EVAL with clause\nmember1(X44, .(X44, X45)).\nand substitutionT18 -> T50,\nX44 -> T50,\nX45 -> T51,\nT17 -> .(T50, T51)" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 149, 8.17/2.98 "to": 280, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 150, 8.17/2.98 "to": 138, 8.17/2.98 "label": "INSTANCE with matching:\nT18 -> T42\nT17 -> T41" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 279, 8.17/2.98 "to": 281, 8.17/2.98 "label": "SUCCESS" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 284, 8.17/2.98 "to": 287, 8.17/2.98 "label": "SUCCESS" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "type": "Graph" 8.17/2.98 } 8.17/2.98 } 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (46) 8.17/2.98 Obligation: 8.17/2.98 Q restricted rewrite system: 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 f1_in(T17) -> U1(f79_in(T17), T17) 8.17/2.98 U1(f79_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) 8.17/2.98 f1_in(T57) -> f1_out1([]) 8.17/2.98 f138_in(.(T40, T41)) -> U2(f138_in(T41), .(T40, T41)) 8.17/2.98 U2(f138_out1(T42), .(T40, T41)) -> f138_out1(T42) 8.17/2.98 f138_in(.(T50, T51)) -> f138_out1(T50) 8.17/2.98 f79_in(T17) -> U3(f138_in(T17), T17) 8.17/2.98 U3(f138_out1(T18), T17) -> U4(f1_in(T17), T17, T18) 8.17/2.98 U4(f1_out1(T23), T17, T18) -> f79_out1(T18, T23) 8.17/2.98 8.17/2.98 Q is empty. 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (47) DependencyPairsProof (EQUIVALENT) 8.17/2.98 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (48) 8.17/2.98 Obligation: 8.17/2.98 Q DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 F1_IN(T17) -> U1^1(f79_in(T17), T17) 8.17/2.98 F1_IN(T17) -> F79_IN(T17) 8.17/2.98 F138_IN(.(T40, T41)) -> U2^1(f138_in(T41), .(T40, T41)) 8.17/2.98 F138_IN(.(T40, T41)) -> F138_IN(T41) 8.17/2.98 F79_IN(T17) -> U3^1(f138_in(T17), T17) 8.17/2.98 F79_IN(T17) -> F138_IN(T17) 8.17/2.98 U3^1(f138_out1(T18), T17) -> U4^1(f1_in(T17), T17, T18) 8.17/2.98 U3^1(f138_out1(T18), T17) -> F1_IN(T17) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 f1_in(T17) -> U1(f79_in(T17), T17) 8.17/2.98 U1(f79_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) 8.17/2.98 f1_in(T57) -> f1_out1([]) 8.17/2.98 f138_in(.(T40, T41)) -> U2(f138_in(T41), .(T40, T41)) 8.17/2.98 U2(f138_out1(T42), .(T40, T41)) -> f138_out1(T42) 8.17/2.98 f138_in(.(T50, T51)) -> f138_out1(T50) 8.17/2.98 f79_in(T17) -> U3(f138_in(T17), T17) 8.17/2.98 U3(f138_out1(T18), T17) -> U4(f1_in(T17), T17, T18) 8.17/2.98 U4(f1_out1(T23), T17, T18) -> f79_out1(T18, T23) 8.17/2.98 8.17/2.98 Q is empty. 8.17/2.98 We have to consider all minimal (P,Q,R)-chains. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (49) DependencyGraphProof (EQUIVALENT) 8.17/2.98 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (50) 8.17/2.98 Complex Obligation (AND) 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (51) 8.17/2.98 Obligation: 8.17/2.98 Q DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 F138_IN(.(T40, T41)) -> F138_IN(T41) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 f1_in(T17) -> U1(f79_in(T17), T17) 8.17/2.98 U1(f79_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) 8.17/2.98 f1_in(T57) -> f1_out1([]) 8.17/2.98 f138_in(.(T40, T41)) -> U2(f138_in(T41), .(T40, T41)) 8.17/2.98 U2(f138_out1(T42), .(T40, T41)) -> f138_out1(T42) 8.17/2.98 f138_in(.(T50, T51)) -> f138_out1(T50) 8.17/2.98 f79_in(T17) -> U3(f138_in(T17), T17) 8.17/2.98 U3(f138_out1(T18), T17) -> U4(f1_in(T17), T17, T18) 8.17/2.98 U4(f1_out1(T23), T17, T18) -> f79_out1(T18, T23) 8.17/2.98 8.17/2.98 Q is empty. 8.17/2.98 We have to consider all minimal (P,Q,R)-chains. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (52) UsableRulesProof (EQUIVALENT) 8.17/2.98 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (53) 8.17/2.98 Obligation: 8.17/2.98 Q DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 F138_IN(.(T40, T41)) -> F138_IN(T41) 8.17/2.98 8.17/2.98 R is empty. 8.17/2.98 Q is empty. 8.17/2.98 We have to consider all minimal (P,Q,R)-chains. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (54) QDPSizeChangeProof (EQUIVALENT) 8.17/2.98 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. 8.17/2.98 8.17/2.98 From the DPs we obtained the following set of size-change graphs: 8.17/2.98 *F138_IN(.(T40, T41)) -> F138_IN(T41) 8.17/2.98 The graph contains the following edges 1 > 1 8.17/2.98 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (55) 8.17/2.98 YES 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (56) 8.17/2.98 Obligation: 8.17/2.98 Q DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 F1_IN(T17) -> F79_IN(T17) 8.17/2.98 F79_IN(T17) -> U3^1(f138_in(T17), T17) 8.17/2.98 U3^1(f138_out1(T18), T17) -> F1_IN(T17) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 f1_in(T17) -> U1(f79_in(T17), T17) 8.17/2.98 U1(f79_out1(T18, T19), T17) -> f1_out1(.(T18, T19)) 8.17/2.98 f1_in(T57) -> f1_out1([]) 8.17/2.98 f138_in(.(T40, T41)) -> U2(f138_in(T41), .(T40, T41)) 8.17/2.98 U2(f138_out1(T42), .(T40, T41)) -> f138_out1(T42) 8.17/2.98 f138_in(.(T50, T51)) -> f138_out1(T50) 8.17/2.98 f79_in(T17) -> U3(f138_in(T17), T17) 8.17/2.98 U3(f138_out1(T18), T17) -> U4(f1_in(T17), T17, T18) 8.17/2.98 U4(f1_out1(T23), T17, T18) -> f79_out1(T18, T23) 8.17/2.98 8.17/2.98 Q is empty. 8.17/2.98 We have to consider all minimal (P,Q,R)-chains. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (57) NonTerminationLoopProof (COMPLETE) 8.17/2.98 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 8.17/2.98 Found a loop by narrowing to the left: 8.17/2.98 8.17/2.98 s = F79_IN(.(T50, T51)) evaluates to t =F79_IN(.(T50, T51)) 8.17/2.98 8.17/2.98 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 8.17/2.98 * Matcher: [ ] 8.17/2.98 * Semiunifier: [ ] 8.17/2.98 8.17/2.98 -------------------------------------------------------------------------------- 8.17/2.98 Rewriting sequence 8.17/2.98 8.17/2.98 F79_IN(.(T50, T51)) -> U3^1(f138_in(.(T50, T51)), .(T50, T51)) 8.17/2.98 with rule F79_IN(T17) -> U3^1(f138_in(T17), T17) at position [] and matcher [T17 / .(T50, T51)] 8.17/2.98 8.17/2.98 U3^1(f138_in(.(T50, T51)), .(T50, T51)) -> U3^1(f138_out1(T50), .(T50, T51)) 8.17/2.98 with rule f138_in(.(T50', T51')) -> f138_out1(T50') at position [0] and matcher [T50' / T50, T51' / T51] 8.17/2.98 8.17/2.98 U3^1(f138_out1(T50), .(T50, T51)) -> F1_IN(.(T50, T51)) 8.17/2.98 with rule U3^1(f138_out1(T18), T17') -> F1_IN(T17') at position [] and matcher [T18 / T50, T17' / .(T50, T51)] 8.17/2.98 8.17/2.98 F1_IN(.(T50, T51)) -> F79_IN(.(T50, T51)) 8.17/2.98 with rule F1_IN(T17) -> F79_IN(T17) 8.17/2.98 8.17/2.98 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 8.17/2.98 8.17/2.98 8.17/2.98 All these steps are and every following step will be a correct step w.r.t to Q. 8.17/2.98 8.17/2.98 8.17/2.98 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (58) 8.17/2.98 NO 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (59) PrologToDTProblemTransformerProof (SOUND) 8.17/2.98 Built DT problem from termination graph DT10. 8.17/2.98 8.17/2.98 { 8.17/2.98 "root": 6, 8.17/2.98 "program": { 8.17/2.98 "directives": [], 8.17/2.98 "clauses": [ 8.17/2.98 [ 8.17/2.98 "(member X (. Y Xs))", 8.17/2.98 "(member X Xs)" 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(member X (. X Xs))", 8.17/2.98 null 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(subset (. X Xs) Ys)", 8.17/2.98 "(',' (member X Ys) (subset Xs Ys))" 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(subset ([]) Ys)", 8.17/2.98 null 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(member1 X (. Y Xs))", 8.17/2.98 "(member1 X Xs)" 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(member1 X (. X Xs))", 8.17/2.98 null 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(subset1 (. X Xs) Ys)", 8.17/2.98 "(',' (member1 X Ys) (subset1 Xs Ys))" 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(subset1 ([]) Ys)", 8.17/2.98 null 8.17/2.98 ] 8.17/2.98 ] 8.17/2.98 }, 8.17/2.98 "graph": { 8.17/2.98 "nodes": { 8.17/2.98 "46": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 4, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(',' (member1 T9 T8) (subset1 T10 T8))" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T8"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "47": { 8.17/2.98 "goal": [ 8.17/2.98 { 8.17/2.98 "clause": 5, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(',' (member1 T9 T8) (subset1 T10 T8))" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": -1, 8.17/2.98 "scope": 2, 8.17/2.98 "term": null 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T8)" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T8"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "290": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(true)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "291": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "270": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(subset1 T31 (. T24 T25))" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [ 8.17/2.98 "T24", 8.17/2.98 "T25" 8.17/2.98 ], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "292": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "type": "Nodes", 8.17/2.98 "271": { 8.17/2.98 "goal": [ 8.17/2.98 { 8.17/2.98 "clause": 4, 8.17/2.98 "scope": 3, 8.17/2.98 "term": "(member1 T26 T25)" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": 5, 8.17/2.98 "scope": 3, 8.17/2.98 "term": "(member1 T26 T25)" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T25"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "293": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(true)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "272": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 4, 8.17/2.98 "scope": 3, 8.17/2.98 "term": "(member1 T26 T25)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T25"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "294": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "273": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 5, 8.17/2.98 "scope": 3, 8.17/2.98 "term": "(member1 T26 T25)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T25"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "295": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "274": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(member1 T50 T49)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T49"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "275": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "276": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(true)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "277": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "278": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "96": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(',' (member1 T26 T25) (subset1 T27 (. T24 T25)))" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [ 8.17/2.98 "T24", 8.17/2.98 "T25" 8.17/2.98 ], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "39": { 8.17/2.98 "goal": [ 8.17/2.98 { 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(',' (member1 T9 T8) (subset1 T10 T8))" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T8)" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T8"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "282": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 5, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(',' (member1 T9 T8) (subset1 T10 T8))" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T8"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "283": { 8.17/2.98 "goal": [ 8.17/2.98 { 8.17/2.98 "clause": -1, 8.17/2.98 "scope": 2, 8.17/2.98 "term": null 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T8)" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T8"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "286": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(subset1 T74 (. T72 T73))" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [ 8.17/2.98 "T72", 8.17/2.98 "T73" 8.17/2.98 ], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "288": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "289": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T8)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T8"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "269": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(member1 T26 T25)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T25"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "6": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T2"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "105": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "7": { 8.17/2.98 "goal": [ 8.17/2.98 { 8.17/2.98 "clause": 6, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T2"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "40": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [[ 8.17/2.98 "(subset1 T1 T2)", 8.17/2.98 "(subset1 (. X4 X5) X6)" 8.17/2.98 ]], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T2"], 8.17/2.98 "free": [ 8.17/2.98 "X4", 8.17/2.98 "X5", 8.17/2.98 "X6" 8.17/2.98 ], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "41": { 8.17/2.98 "goal": [ 8.17/2.98 { 8.17/2.98 "clause": 4, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(',' (member1 T9 T8) (subset1 T10 T8))" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": 5, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(',' (member1 T9 T8) (subset1 T10 T8))" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": -1, 8.17/2.98 "scope": 2, 8.17/2.98 "term": null 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T8)" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T8"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "edges": [ 8.17/2.98 { 8.17/2.98 "from": 6, 8.17/2.98 "to": 7, 8.17/2.98 "label": "CASE" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 7, 8.17/2.98 "to": 39, 8.17/2.98 "label": "EVAL with clause\nsubset1(.(X4, X5), X6) :- ','(member1(X4, X6), subset1(X5, X6)).\nand substitutionX4 -> T9,\nX5 -> T10,\nT1 -> .(T9, T10),\nT2 -> T8,\nX6 -> T8,\nT6 -> T9,\nT7 -> T10" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 7, 8.17/2.98 "to": 40, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 39, 8.17/2.98 "to": 41, 8.17/2.98 "label": "CASE" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 40, 8.17/2.98 "to": 293, 8.17/2.98 "label": "EVAL with clause\nsubset1([], X72).\nand substitutionT1 -> [],\nT2 -> T83,\nX72 -> T83" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 40, 8.17/2.98 "to": 294, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 41, 8.17/2.98 "to": 46, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 41, 8.17/2.98 "to": 47, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 46, 8.17/2.98 "to": 96, 8.17/2.98 "label": "EVAL with clause\nmember1(X19, .(X20, X21)) :- member1(X19, X21).\nand substitutionT9 -> T26,\nX19 -> T26,\nX20 -> T24,\nX21 -> T25,\nT8 -> .(T24, T25),\nT23 -> T26,\nT10 -> T27" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 46, 8.17/2.98 "to": 105, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 47, 8.17/2.98 "to": 282, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 47, 8.17/2.98 "to": 283, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 96, 8.17/2.98 "to": 269, 8.17/2.98 "label": "SPLIT 1" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 96, 8.17/2.98 "to": 270, 8.17/2.98 "label": "SPLIT 2\nnew knowledge:\nT26 is ground\nT25 is ground\nreplacements:T27 -> T31" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 269, 8.17/2.98 "to": 271, 8.17/2.98 "label": "CASE" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 270, 8.17/2.98 "to": 6, 8.17/2.98 "label": "INSTANCE with matching:\nT1 -> T31\nT2 -> .(T24, T25)" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 271, 8.17/2.98 "to": 272, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 271, 8.17/2.98 "to": 273, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 272, 8.17/2.98 "to": 274, 8.17/2.98 "label": "EVAL with clause\nmember1(X40, .(X41, X42)) :- member1(X40, X42).\nand substitutionT26 -> T50,\nX40 -> T50,\nX41 -> T48,\nX42 -> T49,\nT25 -> .(T48, T49),\nT47 -> T50" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 272, 8.17/2.98 "to": 275, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 273, 8.17/2.98 "to": 276, 8.17/2.98 "label": "EVAL with clause\nmember1(X50, .(X50, X51)).\nand substitutionT26 -> T58,\nX50 -> T58,\nX51 -> T59,\nT25 -> .(T58, T59)" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 273, 8.17/2.98 "to": 277, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 274, 8.17/2.98 "to": 269, 8.17/2.98 "label": "INSTANCE with matching:\nT26 -> T50\nT25 -> T49" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 276, 8.17/2.98 "to": 278, 8.17/2.98 "label": "SUCCESS" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 282, 8.17/2.98 "to": 286, 8.17/2.98 "label": "EVAL with clause\nmember1(X63, .(X63, X64)).\nand substitutionT9 -> T72,\nX63 -> T72,\nX64 -> T73,\nT8 -> .(T72, T73),\nT10 -> T74" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 282, 8.17/2.98 "to": 288, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 283, 8.17/2.98 "to": 289, 8.17/2.98 "label": "FAILURE" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 286, 8.17/2.98 "to": 6, 8.17/2.98 "label": "INSTANCE with matching:\nT1 -> T74\nT2 -> .(T72, T73)" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 289, 8.17/2.98 "to": 290, 8.17/2.98 "label": "EVAL with clause\nsubset1([], X70).\nand substitutionT1 -> [],\nT8 -> T81,\nX70 -> T81" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 289, 8.17/2.98 "to": 291, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 290, 8.17/2.98 "to": 292, 8.17/2.98 "label": "SUCCESS" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 293, 8.17/2.98 "to": 295, 8.17/2.98 "label": "SUCCESS" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "type": "Graph" 8.17/2.98 } 8.17/2.98 } 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (60) 8.17/2.98 Obligation: 8.17/2.98 Triples: 8.17/2.98 8.17/2.98 member1B(X1, .(X2, X3)) :- member1B(X1, X3). 8.17/2.98 subset1A(.(X1, X2), .(X3, X4)) :- member1B(X1, X4). 8.17/2.98 subset1A(.(X1, X2), .(X3, X4)) :- ','(member1cB(X1, X4), subset1A(X2, .(X3, X4))). 8.17/2.98 subset1A(.(X1, X2), .(X1, X3)) :- subset1A(X2, .(X1, X3)). 8.17/2.98 8.17/2.98 Clauses: 8.17/2.98 8.17/2.98 subset1cA(.(X1, X2), .(X3, X4)) :- ','(member1cB(X1, X4), subset1cA(X2, .(X3, X4))). 8.17/2.98 subset1cA(.(X1, X2), .(X1, X3)) :- subset1cA(X2, .(X1, X3)). 8.17/2.98 subset1cA([], X1). 8.17/2.98 subset1cA([], X1). 8.17/2.98 member1cB(X1, .(X2, X3)) :- member1cB(X1, X3). 8.17/2.98 member1cB(X1, .(X1, X2)). 8.17/2.98 8.17/2.98 Afs: 8.17/2.98 8.17/2.98 subset1A(x1, x2) = subset1A(x2) 8.17/2.98 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (61) TriplesToPiDPProof (SOUND) 8.17/2.98 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 8.17/2.98 8.17/2.98 subset1A_in_2: (f,b) 8.17/2.98 8.17/2.98 member1B_in_2: (f,b) 8.17/2.98 8.17/2.98 member1cB_in_2: (f,b) 8.17/2.98 8.17/2.98 Transforming TRIPLES into the following Term Rewriting System: 8.17/2.98 8.17/2.98 Pi DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X3, X4)) -> U2_AG(X1, X2, X3, X4, member1B_in_ag(X1, X4)) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X3, X4)) -> MEMBER1B_IN_AG(X1, X4) 8.17/2.98 MEMBER1B_IN_AG(X1, .(X2, X3)) -> U1_AG(X1, X2, X3, member1B_in_ag(X1, X3)) 8.17/2.98 MEMBER1B_IN_AG(X1, .(X2, X3)) -> MEMBER1B_IN_AG(X1, X3) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X3, X4)) -> U3_AG(X1, X2, X3, X4, member1cB_in_ag(X1, X4)) 8.17/2.98 U3_AG(X1, X2, X3, X4, member1cB_out_ag(X1, X4)) -> U4_AG(X1, X2, X3, X4, subset1A_in_ag(X2, .(X3, X4))) 8.17/2.98 U3_AG(X1, X2, X3, X4, member1cB_out_ag(X1, X4)) -> SUBSET1A_IN_AG(X2, .(X3, X4)) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X1, X3)) -> U5_AG(X1, X2, X3, subset1A_in_ag(X2, .(X1, X3))) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X1, X3)) -> SUBSET1A_IN_AG(X2, .(X1, X3)) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 member1cB_in_ag(X1, .(X2, X3)) -> U10_ag(X1, X2, X3, member1cB_in_ag(X1, X3)) 8.17/2.98 member1cB_in_ag(X1, .(X1, X2)) -> member1cB_out_ag(X1, .(X1, X2)) 8.17/2.98 U10_ag(X1, X2, X3, member1cB_out_ag(X1, X3)) -> member1cB_out_ag(X1, .(X2, X3)) 8.17/2.98 8.17/2.98 The argument filtering Pi contains the following mapping: 8.17/2.98 subset1A_in_ag(x1, x2) = subset1A_in_ag(x2) 8.17/2.98 8.17/2.98 .(x1, x2) = .(x1, x2) 8.17/2.98 8.17/2.98 member1B_in_ag(x1, x2) = member1B_in_ag(x2) 8.17/2.98 8.17/2.98 member1cB_in_ag(x1, x2) = member1cB_in_ag(x2) 8.17/2.98 8.17/2.98 U10_ag(x1, x2, x3, x4) = U10_ag(x2, x3, x4) 8.17/2.98 8.17/2.98 member1cB_out_ag(x1, x2) = member1cB_out_ag(x1, x2) 8.17/2.98 8.17/2.98 SUBSET1A_IN_AG(x1, x2) = SUBSET1A_IN_AG(x2) 8.17/2.98 8.17/2.98 U2_AG(x1, x2, x3, x4, x5) = U2_AG(x3, x4, x5) 8.17/2.98 8.17/2.98 MEMBER1B_IN_AG(x1, x2) = MEMBER1B_IN_AG(x2) 8.17/2.98 8.17/2.98 U1_AG(x1, x2, x3, x4) = U1_AG(x2, x3, x4) 8.17/2.98 8.17/2.98 U3_AG(x1, x2, x3, x4, x5) = U3_AG(x3, x4, x5) 8.17/2.98 8.17/2.98 U4_AG(x1, x2, x3, x4, x5) = U4_AG(x3, x4, x5) 8.17/2.98 8.17/2.98 U5_AG(x1, x2, x3, x4) = U5_AG(x1, x3, x4) 8.17/2.98 8.17/2.98 8.17/2.98 We have to consider all (P,R,Pi)-chains 8.17/2.98 8.17/2.98 8.17/2.98 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 8.17/2.98 8.17/2.98 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (62) 8.17/2.98 Obligation: 8.17/2.98 Pi DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X3, X4)) -> U2_AG(X1, X2, X3, X4, member1B_in_ag(X1, X4)) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X3, X4)) -> MEMBER1B_IN_AG(X1, X4) 8.17/2.98 MEMBER1B_IN_AG(X1, .(X2, X3)) -> U1_AG(X1, X2, X3, member1B_in_ag(X1, X3)) 8.17/2.98 MEMBER1B_IN_AG(X1, .(X2, X3)) -> MEMBER1B_IN_AG(X1, X3) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X3, X4)) -> U3_AG(X1, X2, X3, X4, member1cB_in_ag(X1, X4)) 8.17/2.98 U3_AG(X1, X2, X3, X4, member1cB_out_ag(X1, X4)) -> U4_AG(X1, X2, X3, X4, subset1A_in_ag(X2, .(X3, X4))) 8.17/2.98 U3_AG(X1, X2, X3, X4, member1cB_out_ag(X1, X4)) -> SUBSET1A_IN_AG(X2, .(X3, X4)) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X1, X3)) -> U5_AG(X1, X2, X3, subset1A_in_ag(X2, .(X1, X3))) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X1, X3)) -> SUBSET1A_IN_AG(X2, .(X1, X3)) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 member1cB_in_ag(X1, .(X2, X3)) -> U10_ag(X1, X2, X3, member1cB_in_ag(X1, X3)) 8.17/2.98 member1cB_in_ag(X1, .(X1, X2)) -> member1cB_out_ag(X1, .(X1, X2)) 8.17/2.98 U10_ag(X1, X2, X3, member1cB_out_ag(X1, X3)) -> member1cB_out_ag(X1, .(X2, X3)) 8.17/2.98 8.17/2.98 The argument filtering Pi contains the following mapping: 8.17/2.98 subset1A_in_ag(x1, x2) = subset1A_in_ag(x2) 8.17/2.98 8.17/2.98 .(x1, x2) = .(x1, x2) 8.17/2.98 8.17/2.98 member1B_in_ag(x1, x2) = member1B_in_ag(x2) 8.17/2.98 8.17/2.98 member1cB_in_ag(x1, x2) = member1cB_in_ag(x2) 8.17/2.98 8.17/2.98 U10_ag(x1, x2, x3, x4) = U10_ag(x2, x3, x4) 8.17/2.98 8.17/2.98 member1cB_out_ag(x1, x2) = member1cB_out_ag(x1, x2) 8.17/2.98 8.17/2.98 SUBSET1A_IN_AG(x1, x2) = SUBSET1A_IN_AG(x2) 8.17/2.98 8.17/2.98 U2_AG(x1, x2, x3, x4, x5) = U2_AG(x3, x4, x5) 8.17/2.98 8.17/2.98 MEMBER1B_IN_AG(x1, x2) = MEMBER1B_IN_AG(x2) 8.17/2.98 8.17/2.98 U1_AG(x1, x2, x3, x4) = U1_AG(x2, x3, x4) 8.17/2.98 8.17/2.98 U3_AG(x1, x2, x3, x4, x5) = U3_AG(x3, x4, x5) 8.17/2.98 8.17/2.98 U4_AG(x1, x2, x3, x4, x5) = U4_AG(x3, x4, x5) 8.17/2.98 8.17/2.98 U5_AG(x1, x2, x3, x4) = U5_AG(x1, x3, x4) 8.17/2.98 8.17/2.98 8.17/2.98 We have to consider all (P,R,Pi)-chains 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (63) DependencyGraphProof (EQUIVALENT) 8.17/2.98 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 5 less nodes. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (64) 8.17/2.98 Complex Obligation (AND) 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (65) 8.17/2.98 Obligation: 8.17/2.98 Pi DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 MEMBER1B_IN_AG(X1, .(X2, X3)) -> MEMBER1B_IN_AG(X1, X3) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 member1cB_in_ag(X1, .(X2, X3)) -> U10_ag(X1, X2, X3, member1cB_in_ag(X1, X3)) 8.17/2.98 member1cB_in_ag(X1, .(X1, X2)) -> member1cB_out_ag(X1, .(X1, X2)) 8.17/2.98 U10_ag(X1, X2, X3, member1cB_out_ag(X1, X3)) -> member1cB_out_ag(X1, .(X2, X3)) 8.17/2.98 8.17/2.98 The argument filtering Pi contains the following mapping: 8.17/2.98 .(x1, x2) = .(x1, x2) 8.17/2.98 8.17/2.98 member1cB_in_ag(x1, x2) = member1cB_in_ag(x2) 8.17/2.98 8.17/2.98 U10_ag(x1, x2, x3, x4) = U10_ag(x2, x3, x4) 8.17/2.98 8.17/2.98 member1cB_out_ag(x1, x2) = member1cB_out_ag(x1, x2) 8.17/2.98 8.17/2.98 MEMBER1B_IN_AG(x1, x2) = MEMBER1B_IN_AG(x2) 8.17/2.98 8.17/2.98 8.17/2.98 We have to consider all (P,R,Pi)-chains 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (66) UsableRulesProof (EQUIVALENT) 8.17/2.98 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (67) 8.17/2.98 Obligation: 8.17/2.98 Pi DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 MEMBER1B_IN_AG(X1, .(X2, X3)) -> MEMBER1B_IN_AG(X1, X3) 8.17/2.98 8.17/2.98 R is empty. 8.17/2.98 The argument filtering Pi contains the following mapping: 8.17/2.98 .(x1, x2) = .(x1, x2) 8.17/2.98 8.17/2.98 MEMBER1B_IN_AG(x1, x2) = MEMBER1B_IN_AG(x2) 8.17/2.98 8.17/2.98 8.17/2.98 We have to consider all (P,R,Pi)-chains 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (68) PiDPToQDPProof (SOUND) 8.17/2.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (69) 8.17/2.98 Obligation: 8.17/2.98 Q DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 MEMBER1B_IN_AG(.(X2, X3)) -> MEMBER1B_IN_AG(X3) 8.17/2.98 8.17/2.98 R is empty. 8.17/2.98 Q is empty. 8.17/2.98 We have to consider all (P,Q,R)-chains. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (70) QDPSizeChangeProof (EQUIVALENT) 8.17/2.98 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. 8.17/2.98 8.17/2.98 From the DPs we obtained the following set of size-change graphs: 8.17/2.98 *MEMBER1B_IN_AG(.(X2, X3)) -> MEMBER1B_IN_AG(X3) 8.17/2.98 The graph contains the following edges 1 > 1 8.17/2.98 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (71) 8.17/2.98 YES 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (72) 8.17/2.98 Obligation: 8.17/2.98 Pi DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X3, X4)) -> U3_AG(X1, X2, X3, X4, member1cB_in_ag(X1, X4)) 8.17/2.98 U3_AG(X1, X2, X3, X4, member1cB_out_ag(X1, X4)) -> SUBSET1A_IN_AG(X2, .(X3, X4)) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X2), .(X1, X3)) -> SUBSET1A_IN_AG(X2, .(X1, X3)) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 member1cB_in_ag(X1, .(X2, X3)) -> U10_ag(X1, X2, X3, member1cB_in_ag(X1, X3)) 8.17/2.98 member1cB_in_ag(X1, .(X1, X2)) -> member1cB_out_ag(X1, .(X1, X2)) 8.17/2.98 U10_ag(X1, X2, X3, member1cB_out_ag(X1, X3)) -> member1cB_out_ag(X1, .(X2, X3)) 8.17/2.98 8.17/2.98 The argument filtering Pi contains the following mapping: 8.17/2.98 .(x1, x2) = .(x1, x2) 8.17/2.98 8.17/2.98 member1cB_in_ag(x1, x2) = member1cB_in_ag(x2) 8.17/2.98 8.17/2.98 U10_ag(x1, x2, x3, x4) = U10_ag(x2, x3, x4) 8.17/2.98 8.17/2.98 member1cB_out_ag(x1, x2) = member1cB_out_ag(x1, x2) 8.17/2.98 8.17/2.98 SUBSET1A_IN_AG(x1, x2) = SUBSET1A_IN_AG(x2) 8.17/2.98 8.17/2.98 U3_AG(x1, x2, x3, x4, x5) = U3_AG(x3, x4, x5) 8.17/2.98 8.17/2.98 8.17/2.98 We have to consider all (P,R,Pi)-chains 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (73) PiDPToQDPProof (SOUND) 8.17/2.98 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (74) 8.17/2.98 Obligation: 8.17/2.98 Q DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 SUBSET1A_IN_AG(.(X3, X4)) -> U3_AG(X3, X4, member1cB_in_ag(X4)) 8.17/2.98 U3_AG(X3, X4, member1cB_out_ag(X1, X4)) -> SUBSET1A_IN_AG(.(X3, X4)) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X3)) -> SUBSET1A_IN_AG(.(X1, X3)) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 member1cB_in_ag(.(X2, X3)) -> U10_ag(X2, X3, member1cB_in_ag(X3)) 8.17/2.98 member1cB_in_ag(.(X1, X2)) -> member1cB_out_ag(X1, .(X1, X2)) 8.17/2.98 U10_ag(X2, X3, member1cB_out_ag(X1, X3)) -> member1cB_out_ag(X1, .(X2, X3)) 8.17/2.98 8.17/2.98 The set Q consists of the following terms: 8.17/2.98 8.17/2.98 member1cB_in_ag(x0) 8.17/2.98 U10_ag(x0, x1, x2) 8.17/2.98 8.17/2.98 We have to consider all (P,Q,R)-chains. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (75) TransformationProof (SOUND) 8.17/2.98 By narrowing [LPAR04] the rule SUBSET1A_IN_AG(.(X3, X4)) -> U3_AG(X3, X4, member1cB_in_ag(X4)) at position [2] we obtained the following new rules [LPAR04]: 8.17/2.98 8.17/2.98 (SUBSET1A_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), U10_ag(x0, x1, member1cB_in_ag(x1))),SUBSET1A_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), U10_ag(x0, x1, member1cB_in_ag(x1)))) 8.17/2.98 (SUBSET1A_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), member1cB_out_ag(x0, .(x0, x1))),SUBSET1A_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), member1cB_out_ag(x0, .(x0, x1)))) 8.17/2.98 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (76) 8.17/2.98 Obligation: 8.17/2.98 Q DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 U3_AG(X3, X4, member1cB_out_ag(X1, X4)) -> SUBSET1A_IN_AG(.(X3, X4)) 8.17/2.98 SUBSET1A_IN_AG(.(X1, X3)) -> SUBSET1A_IN_AG(.(X1, X3)) 8.17/2.98 SUBSET1A_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), U10_ag(x0, x1, member1cB_in_ag(x1))) 8.17/2.98 SUBSET1A_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), member1cB_out_ag(x0, .(x0, x1))) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 member1cB_in_ag(.(X2, X3)) -> U10_ag(X2, X3, member1cB_in_ag(X3)) 8.17/2.98 member1cB_in_ag(.(X1, X2)) -> member1cB_out_ag(X1, .(X1, X2)) 8.17/2.98 U10_ag(X2, X3, member1cB_out_ag(X1, X3)) -> member1cB_out_ag(X1, .(X2, X3)) 8.17/2.98 8.17/2.98 The set Q consists of the following terms: 8.17/2.98 8.17/2.98 member1cB_in_ag(x0) 8.17/2.98 U10_ag(x0, x1, x2) 8.17/2.98 8.17/2.98 We have to consider all (P,Q,R)-chains. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (77) TransformationProof (EQUIVALENT) 8.17/2.98 By instantiating [LPAR04] the rule U3_AG(X3, X4, member1cB_out_ag(X1, X4)) -> SUBSET1A_IN_AG(.(X3, X4)) we obtained the following new rules [LPAR04]: 8.17/2.98 8.17/2.98 (U3_AG(z0, .(z1, z2), member1cB_out_ag(x2, .(z1, z2))) -> SUBSET1A_IN_AG(.(z0, .(z1, z2))),U3_AG(z0, .(z1, z2), member1cB_out_ag(x2, .(z1, z2))) -> SUBSET1A_IN_AG(.(z0, .(z1, z2)))) 8.17/2.98 (U3_AG(z0, .(z1, z2), member1cB_out_ag(z1, .(z1, z2))) -> SUBSET1A_IN_AG(.(z0, .(z1, z2))),U3_AG(z0, .(z1, z2), member1cB_out_ag(z1, .(z1, z2))) -> SUBSET1A_IN_AG(.(z0, .(z1, z2)))) 8.17/2.98 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (78) 8.17/2.98 Obligation: 8.17/2.98 Q DP problem: 8.17/2.98 The TRS P consists of the following rules: 8.17/2.98 8.17/2.98 SUBSET1A_IN_AG(.(X1, X3)) -> SUBSET1A_IN_AG(.(X1, X3)) 8.17/2.98 SUBSET1A_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), U10_ag(x0, x1, member1cB_in_ag(x1))) 8.17/2.98 SUBSET1A_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), member1cB_out_ag(x0, .(x0, x1))) 8.17/2.98 U3_AG(z0, .(z1, z2), member1cB_out_ag(x2, .(z1, z2))) -> SUBSET1A_IN_AG(.(z0, .(z1, z2))) 8.17/2.98 U3_AG(z0, .(z1, z2), member1cB_out_ag(z1, .(z1, z2))) -> SUBSET1A_IN_AG(.(z0, .(z1, z2))) 8.17/2.98 8.17/2.98 The TRS R consists of the following rules: 8.17/2.98 8.17/2.98 member1cB_in_ag(.(X2, X3)) -> U10_ag(X2, X3, member1cB_in_ag(X3)) 8.17/2.98 member1cB_in_ag(.(X1, X2)) -> member1cB_out_ag(X1, .(X1, X2)) 8.17/2.98 U10_ag(X2, X3, member1cB_out_ag(X1, X3)) -> member1cB_out_ag(X1, .(X2, X3)) 8.17/2.98 8.17/2.98 The set Q consists of the following terms: 8.17/2.98 8.17/2.98 member1cB_in_ag(x0) 8.17/2.98 U10_ag(x0, x1, x2) 8.17/2.98 8.17/2.98 We have to consider all (P,Q,R)-chains. 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (79) PrologToIRSwTTransformerProof (SOUND) 8.17/2.98 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 8.17/2.98 8.17/2.98 { 8.17/2.98 "root": 2, 8.17/2.98 "program": { 8.17/2.98 "directives": [], 8.17/2.98 "clauses": [ 8.17/2.98 [ 8.17/2.98 "(member X (. Y Xs))", 8.17/2.98 "(member X Xs)" 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(member X (. X Xs))", 8.17/2.98 null 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(subset (. X Xs) Ys)", 8.17/2.98 "(',' (member X Ys) (subset Xs Ys))" 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(subset ([]) Ys)", 8.17/2.98 null 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(member1 X (. Y Xs))", 8.17/2.98 "(member1 X Xs)" 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(member1 X (. X Xs))", 8.17/2.98 null 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(subset1 (. X Xs) Ys)", 8.17/2.98 "(',' (member1 X Ys) (subset1 Xs Ys))" 8.17/2.98 ], 8.17/2.98 [ 8.17/2.98 "(subset1 ([]) Ys)", 8.17/2.98 null 8.17/2.98 ] 8.17/2.98 ] 8.17/2.98 }, 8.17/2.98 "graph": { 8.17/2.98 "nodes": { 8.17/2.98 "37": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 6, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T2"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "38": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T2"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "160": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "type": "Nodes", 8.17/2.98 "250": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "152": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(',' (member1 T18 T17) (subset1 T19 T17))" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T17"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "153": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "154": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(member1 T18 T17)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T17"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "155": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(subset1 T23 T17)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T17"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "2": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T2"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "156": { 8.17/2.98 "goal": [ 8.17/2.98 { 8.17/2.98 "clause": 4, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(member1 T18 T17)" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": 5, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(member1 T18 T17)" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T17"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "266": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(true)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "157": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 4, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(member1 T18 T17)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T17"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "245": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "267": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "4": { 8.17/2.98 "goal": [ 8.17/2.98 { 8.17/2.98 "clause": 6, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "clause": 7, 8.17/2.98 "scope": 1, 8.17/2.98 "term": "(subset1 T1 T2)" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T2"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "158": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": 5, 8.17/2.98 "scope": 2, 8.17/2.98 "term": "(member1 T18 T17)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T17"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "268": { 8.17/2.98 "goal": [], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "159": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(member1 T42 T41)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": ["T41"], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "237": { 8.17/2.98 "goal": [{ 8.17/2.98 "clause": -1, 8.17/2.98 "scope": -1, 8.17/2.98 "term": "(true)" 8.17/2.98 }], 8.17/2.98 "kb": { 8.17/2.98 "nonunifying": [], 8.17/2.98 "intvars": {}, 8.17/2.98 "arithmetic": { 8.17/2.98 "type": "PlainIntegerRelationState", 8.17/2.98 "relations": [] 8.17/2.98 }, 8.17/2.98 "ground": [], 8.17/2.98 "free": [], 8.17/2.98 "exprvars": [] 8.17/2.98 } 8.17/2.98 } 8.17/2.98 }, 8.17/2.98 "edges": [ 8.17/2.98 { 8.17/2.98 "from": 2, 8.17/2.98 "to": 4, 8.17/2.98 "label": "CASE" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 4, 8.17/2.98 "to": 37, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 4, 8.17/2.98 "to": 38, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 37, 8.17/2.98 "to": 152, 8.17/2.98 "label": "EVAL with clause\nsubset1(.(X13, X14), X15) :- ','(member1(X13, X15), subset1(X14, X15)).\nand substitutionX13 -> T18,\nX14 -> T19,\nT1 -> .(T18, T19),\nT2 -> T17,\nX15 -> T17,\nT15 -> T18,\nT16 -> T19" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 37, 8.17/2.98 "to": 153, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 38, 8.17/2.98 "to": 266, 8.17/2.98 "label": "EVAL with clause\nsubset1([], X51).\nand substitutionT1 -> [],\nT2 -> T57,\nX51 -> T57" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 38, 8.17/2.98 "to": 267, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 152, 8.17/2.98 "to": 154, 8.17/2.98 "label": "SPLIT 1" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 152, 8.17/2.98 "to": 155, 8.17/2.98 "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nT17 is ground\nreplacements:T19 -> T23" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 154, 8.17/2.98 "to": 156, 8.17/2.98 "label": "CASE" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 155, 8.17/2.98 "to": 2, 8.17/2.98 "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T17" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 156, 8.17/2.98 "to": 157, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 156, 8.17/2.98 "to": 158, 8.17/2.98 "label": "PARALLEL" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 157, 8.17/2.98 "to": 159, 8.17/2.98 "label": "EVAL with clause\nmember1(X34, .(X35, X36)) :- member1(X34, X36).\nand substitutionT18 -> T42,\nX34 -> T42,\nX35 -> T40,\nX36 -> T41,\nT17 -> .(T40, T41),\nT39 -> T42" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 157, 8.17/2.98 "to": 160, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 158, 8.17/2.98 "to": 237, 8.17/2.98 "label": "EVAL with clause\nmember1(X44, .(X44, X45)).\nand substitutionT18 -> T50,\nX44 -> T50,\nX45 -> T51,\nT17 -> .(T50, T51)" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 158, 8.17/2.98 "to": 245, 8.17/2.98 "label": "EVAL-BACKTRACK" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 159, 8.17/2.98 "to": 154, 8.17/2.98 "label": "INSTANCE with matching:\nT18 -> T42\nT17 -> T41" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 237, 8.17/2.98 "to": 250, 8.17/2.98 "label": "SUCCESS" 8.17/2.98 }, 8.17/2.98 { 8.17/2.98 "from": 266, 8.17/2.98 "to": 268, 8.17/2.98 "label": "SUCCESS" 8.17/2.98 } 8.17/2.98 ], 8.17/2.98 "type": "Graph" 8.17/2.98 } 8.17/2.98 } 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (80) 8.17/2.98 Complex Obligation (AND) 8.17/2.98 8.17/2.98 ---------------------------------------- 8.17/2.98 8.17/2.98 (81) 8.17/2.98 Obligation: 8.17/2.98 Rules: 8.17/2.98 f154_out(T41) -> f159_out(T41) :|: TRUE 8.17/2.98 f159_in(x) -> f154_in(x) :|: TRUE 8.17/2.98 f160_out -> f157_out(T17) :|: TRUE 8.17/2.98 f157_in(x1) -> f160_in :|: TRUE 8.17/2.98 f159_out(x2) -> f157_out(.(x3, x2)) :|: TRUE 8.17/2.98 f157_in(.(x4, x5)) -> f159_in(x5) :|: TRUE 8.17/2.98 f154_in(x6) -> f156_in(x6) :|: TRUE 8.17/2.98 f156_out(x7) -> f154_out(x7) :|: TRUE 8.17/2.98 f156_in(x8) -> f157_in(x8) :|: TRUE 8.17/2.98 f158_out(x9) -> f156_out(x9) :|: TRUE 8.17/2.98 f156_in(x10) -> f158_in(x10) :|: TRUE 8.17/2.98 f157_out(x11) -> f156_out(x11) :|: TRUE 8.17/2.98 f2_in(T2) -> f4_in(T2) :|: TRUE 8.17/2.98 f4_out(x12) -> f2_out(x12) :|: TRUE 8.17/2.99 f4_in(x13) -> f37_in(x13) :|: TRUE 8.17/2.99 f37_out(x14) -> f4_out(x14) :|: TRUE 8.17/2.99 f4_in(x15) -> f38_in(x15) :|: TRUE 8.17/2.99 f38_out(x16) -> f4_out(x16) :|: TRUE 8.17/2.99 f152_out(x17) -> f37_out(x17) :|: TRUE 8.17/2.99 f153_out -> f37_out(x18) :|: TRUE 8.17/2.99 f37_in(x19) -> f152_in(x19) :|: TRUE 8.17/2.99 f37_in(x20) -> f153_in :|: TRUE 8.17/2.99 f155_out(x21) -> f152_out(x21) :|: TRUE 8.17/2.99 f152_in(x22) -> f154_in(x22) :|: TRUE 8.17/2.99 f154_out(x23) -> f155_in(x23) :|: TRUE 8.17/2.99 Start term: f2_in(T2) 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (82) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 8.17/2.99 Constructed simple dependency graph. 8.17/2.99 8.17/2.99 Simplified to the following IRSwTs: 8.17/2.99 8.17/2.99 intTRSProblem: 8.17/2.99 f159_in(x) -> f154_in(x) :|: TRUE 8.17/2.99 f157_in(.(x4, x5)) -> f159_in(x5) :|: TRUE 8.17/2.99 f154_in(x6) -> f156_in(x6) :|: TRUE 8.17/2.99 f156_in(x8) -> f157_in(x8) :|: TRUE 8.17/2.99 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (83) 8.17/2.99 Obligation: 8.17/2.99 Rules: 8.17/2.99 f159_in(x) -> f154_in(x) :|: TRUE 8.17/2.99 f157_in(.(x4, x5)) -> f159_in(x5) :|: TRUE 8.17/2.99 f154_in(x6) -> f156_in(x6) :|: TRUE 8.17/2.99 f156_in(x8) -> f157_in(x8) :|: TRUE 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (84) IntTRSCompressionProof (EQUIVALENT) 8.17/2.99 Compressed rules. 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (85) 8.17/2.99 Obligation: 8.17/2.99 Rules: 8.17/2.99 f157_in(.(x4:0, x5:0)) -> f157_in(x5:0) :|: TRUE 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (86) IRSFormatTransformerProof (EQUIVALENT) 8.17/2.99 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (87) 8.17/2.99 Obligation: 8.17/2.99 Rules: 8.17/2.99 f157_in(.(x4:0, x5:0)) -> f157_in(x5:0) :|: TRUE 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (88) IRSwTTerminationDigraphProof (EQUIVALENT) 8.17/2.99 Constructed termination digraph! 8.17/2.99 Nodes: 8.17/2.99 (1) f157_in(.(x4:0, x5:0)) -> f157_in(x5:0) :|: TRUE 8.17/2.99 8.17/2.99 Arcs: 8.17/2.99 (1) -> (1) 8.17/2.99 8.17/2.99 This digraph is fully evaluated! 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (89) 8.17/2.99 Obligation: 8.17/2.99 8.17/2.99 Termination digraph: 8.17/2.99 Nodes: 8.17/2.99 (1) f157_in(.(x4:0, x5:0)) -> f157_in(x5:0) :|: TRUE 8.17/2.99 8.17/2.99 Arcs: 8.17/2.99 (1) -> (1) 8.17/2.99 8.17/2.99 This digraph is fully evaluated! 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (90) IntTRSUnneededArgumentFilterProof (EQUIVALENT) 8.17/2.99 Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: 8.17/2.99 8.17/2.99 .(x1, x2) -> .(x2) 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (91) 8.17/2.99 Obligation: 8.17/2.99 Rules: 8.17/2.99 f157_in(.(x5:0)) -> f157_in(x5:0) :|: TRUE 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (92) TempFilterProof (SOUND) 8.17/2.99 Used the following sort dictionary for filtering: 8.17/2.99 f157_in(VARIABLE) 8.17/2.99 .(VARIABLE) 8.17/2.99 Removed predefined arithmetic. 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (93) 8.17/2.99 Obligation: 8.17/2.99 Rules: 8.17/2.99 f157_in(.(x5:0)) -> f157_in(x5:0) 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (94) IRSwTToQDPProof (SOUND) 8.17/2.99 Removed the integers and created a QDP-Problem. 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (95) 8.17/2.99 Obligation: 8.17/2.99 Q DP problem: 8.17/2.99 The TRS P consists of the following rules: 8.17/2.99 8.17/2.99 f157_in(.(x5:0)) -> f157_in(x5:0) 8.17/2.99 8.17/2.99 R is empty. 8.17/2.99 Q is empty. 8.17/2.99 We have to consider all (P,Q,R)-chains. 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (96) QDPSizeChangeProof (EQUIVALENT) 8.17/2.99 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. 8.17/2.99 8.17/2.99 From the DPs we obtained the following set of size-change graphs: 8.17/2.99 *f157_in(.(x5:0)) -> f157_in(x5:0) 8.17/2.99 The graph contains the following edges 1 > 1 8.17/2.99 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (97) 8.17/2.99 YES 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (98) 8.17/2.99 Obligation: 8.17/2.99 Rules: 8.17/2.99 f4_in(T2) -> f37_in(T2) :|: TRUE 8.17/2.99 f37_out(x) -> f4_out(x) :|: TRUE 8.17/2.99 f4_in(x1) -> f38_in(x1) :|: TRUE 8.17/2.99 f38_out(x2) -> f4_out(x2) :|: TRUE 8.17/2.99 f2_out(T17) -> f155_out(T17) :|: TRUE 8.17/2.99 f155_in(x3) -> f2_in(x3) :|: TRUE 8.17/2.99 f2_in(x4) -> f4_in(x4) :|: TRUE 8.17/2.99 f4_out(x5) -> f2_out(x5) :|: TRUE 8.17/2.99 f155_out(x6) -> f152_out(x6) :|: TRUE 8.17/2.99 f152_in(x7) -> f154_in(x7) :|: TRUE 8.17/2.99 f154_out(x8) -> f155_in(x8) :|: TRUE 8.17/2.99 f237_in -> f237_out :|: TRUE 8.17/2.99 f152_out(x9) -> f37_out(x9) :|: TRUE 8.17/2.99 f153_out -> f37_out(x10) :|: TRUE 8.17/2.99 f37_in(x11) -> f152_in(x11) :|: TRUE 8.17/2.99 f37_in(x12) -> f153_in :|: TRUE 8.17/2.99 f154_out(T41) -> f159_out(T41) :|: TRUE 8.17/2.99 f159_in(x13) -> f154_in(x13) :|: TRUE 8.17/2.99 f154_in(x14) -> f156_in(x14) :|: TRUE 8.17/2.99 f156_out(x15) -> f154_out(x15) :|: TRUE 8.17/2.99 f160_out -> f157_out(x16) :|: TRUE 8.17/2.99 f157_in(x17) -> f160_in :|: TRUE 8.17/2.99 f159_out(x18) -> f157_out(.(x19, x18)) :|: TRUE 8.17/2.99 f157_in(.(x20, x21)) -> f159_in(x21) :|: TRUE 8.17/2.99 f158_in(x22) -> f245_in :|: TRUE 8.17/2.99 f158_in(.(T50, T51)) -> f237_in :|: TRUE 8.17/2.99 f245_out -> f158_out(x23) :|: TRUE 8.17/2.99 f237_out -> f158_out(.(x24, x25)) :|: TRUE 8.17/2.99 f156_in(x26) -> f157_in(x26) :|: TRUE 8.17/2.99 f158_out(x27) -> f156_out(x27) :|: TRUE 8.17/2.99 f156_in(x28) -> f158_in(x28) :|: TRUE 8.17/2.99 f157_out(x29) -> f156_out(x29) :|: TRUE 8.17/2.99 Start term: f2_in(T2) 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (99) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 8.17/2.99 Constructed simple dependency graph. 8.17/2.99 8.17/2.99 Simplified to the following IRSwTs: 8.17/2.99 8.17/2.99 intTRSProblem: 8.17/2.99 f4_in(T2) -> f37_in(T2) :|: TRUE 8.17/2.99 f155_in(x3) -> f2_in(x3) :|: TRUE 8.17/2.99 f2_in(x4) -> f4_in(x4) :|: TRUE 8.17/2.99 f152_in(x7) -> f154_in(x7) :|: TRUE 8.17/2.99 f154_out(x8) -> f155_in(x8) :|: TRUE 8.17/2.99 f237_in -> f237_out :|: TRUE 8.17/2.99 f37_in(x11) -> f152_in(x11) :|: TRUE 8.17/2.99 f154_out(T41) -> f159_out(T41) :|: TRUE 8.17/2.99 f159_in(x13) -> f154_in(x13) :|: TRUE 8.17/2.99 f154_in(x14) -> f156_in(x14) :|: TRUE 8.17/2.99 f156_out(x15) -> f154_out(x15) :|: TRUE 8.17/2.99 f159_out(x18) -> f157_out(.(x19, x18)) :|: TRUE 8.17/2.99 f157_in(.(x20, x21)) -> f159_in(x21) :|: TRUE 8.17/2.99 f158_in(.(T50, T51)) -> f237_in :|: TRUE 8.17/2.99 f237_out -> f158_out(.(x24, x25)) :|: TRUE 8.17/2.99 f156_in(x26) -> f157_in(x26) :|: TRUE 8.17/2.99 f158_out(x27) -> f156_out(x27) :|: TRUE 8.17/2.99 f156_in(x28) -> f158_in(x28) :|: TRUE 8.17/2.99 f157_out(x29) -> f156_out(x29) :|: TRUE 8.17/2.99 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (100) 8.17/2.99 Obligation: 8.17/2.99 Rules: 8.17/2.99 f4_in(T2) -> f37_in(T2) :|: TRUE 8.17/2.99 f155_in(x3) -> f2_in(x3) :|: TRUE 8.17/2.99 f2_in(x4) -> f4_in(x4) :|: TRUE 8.17/2.99 f152_in(x7) -> f154_in(x7) :|: TRUE 8.17/2.99 f154_out(x8) -> f155_in(x8) :|: TRUE 8.17/2.99 f237_in -> f237_out :|: TRUE 8.17/2.99 f37_in(x11) -> f152_in(x11) :|: TRUE 8.17/2.99 f154_out(T41) -> f159_out(T41) :|: TRUE 8.17/2.99 f159_in(x13) -> f154_in(x13) :|: TRUE 8.17/2.99 f154_in(x14) -> f156_in(x14) :|: TRUE 8.17/2.99 f156_out(x15) -> f154_out(x15) :|: TRUE 8.17/2.99 f159_out(x18) -> f157_out(.(x19, x18)) :|: TRUE 8.17/2.99 f157_in(.(x20, x21)) -> f159_in(x21) :|: TRUE 8.17/2.99 f158_in(.(T50, T51)) -> f237_in :|: TRUE 8.17/2.99 f237_out -> f158_out(.(x24, x25)) :|: TRUE 8.17/2.99 f156_in(x26) -> f157_in(x26) :|: TRUE 8.17/2.99 f158_out(x27) -> f156_out(x27) :|: TRUE 8.17/2.99 f156_in(x28) -> f158_in(x28) :|: TRUE 8.17/2.99 f157_out(x29) -> f156_out(x29) :|: TRUE 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (101) IntTRSCompressionProof (EQUIVALENT) 8.17/2.99 Compressed rules. 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (102) 8.17/2.99 Obligation: 8.17/2.99 Rules: 8.17/2.99 f156_out(x15:0) -> f156_in(x15:0) :|: TRUE 8.17/2.99 f156_out(x) -> f156_out(.(x1, x)) :|: TRUE 8.17/2.99 f156_in(.(T50:0, T51:0)) -> f156_out(.(x24:0, x25:0)) :|: TRUE 8.17/2.99 f156_in(.(x20:0, x21:0)) -> f156_in(x21:0) :|: TRUE 8.17/2.99 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (103) IRSFormatTransformerProof (EQUIVALENT) 8.17/2.99 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 8.17/2.99 ---------------------------------------- 8.17/2.99 8.17/2.99 (104) 8.17/2.99 Obligation: 8.17/2.99 Rules: 8.17/2.99 f156_out(x15:0) -> f156_in(x15:0) :|: TRUE 8.17/2.99 f156_out(x) -> f156_out(.(x1, x)) :|: TRUE 8.17/2.99 f156_in(.(T50:0, T51:0)) -> f156_out(.(x24:0, x25:0)) :|: TRUE 8.17/2.99 f156_in(.(x20:0, x21:0)) -> f156_in(x21:0) :|: TRUE 8.38/3.01 EOF