8.89/3.20 MAYBE 9.05/3.21 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 9.05/3.21 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.05/3.21 9.05/3.21 9.05/3.21 Left Termination of the query pattern 9.05/3.21 9.05/3.21 subset(a,g) 9.05/3.21 9.05/3.21 w.r.t. the given Prolog program could not be shown: 9.05/3.21 9.05/3.21 (0) Prolog 9.05/3.21 (1) PrologToPiTRSProof [SOUND, 0 ms] 9.05/3.21 (2) PiTRS 9.05/3.21 (3) DependencyPairsProof [EQUIVALENT, 5 ms] 9.05/3.21 (4) PiDP 9.05/3.21 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 9.05/3.21 (6) AND 9.05/3.21 (7) PiDP 9.05/3.21 (8) UsableRulesProof [EQUIVALENT, 0 ms] 9.05/3.21 (9) PiDP 9.05/3.21 (10) PiDPToQDPProof [SOUND, 0 ms] 9.05/3.21 (11) QDP 9.05/3.21 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.05/3.21 (13) YES 9.05/3.21 (14) PiDP 9.05/3.21 (15) UsableRulesProof [EQUIVALENT, 0 ms] 9.05/3.21 (16) PiDP 9.05/3.21 (17) PiDPToQDPProof [SOUND, 0 ms] 9.05/3.21 (18) QDP 9.05/3.21 (19) TransformationProof [SOUND, 0 ms] 9.05/3.21 (20) QDP 9.05/3.21 (21) TransformationProof [EQUIVALENT, 0 ms] 9.05/3.21 (22) QDP 9.05/3.21 (23) PrologToPiTRSProof [SOUND, 0 ms] 9.05/3.21 (24) PiTRS 9.05/3.21 (25) DependencyPairsProof [EQUIVALENT, 0 ms] 9.05/3.21 (26) PiDP 9.05/3.21 (27) DependencyGraphProof [EQUIVALENT, 0 ms] 9.05/3.21 (28) AND 9.05/3.21 (29) PiDP 9.05/3.21 (30) UsableRulesProof [EQUIVALENT, 0 ms] 9.05/3.21 (31) PiDP 9.05/3.21 (32) PiDPToQDPProof [SOUND, 0 ms] 9.05/3.21 (33) QDP 9.05/3.21 (34) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.05/3.21 (35) YES 9.05/3.21 (36) PiDP 9.05/3.21 (37) UsableRulesProof [EQUIVALENT, 0 ms] 9.05/3.21 (38) PiDP 9.05/3.21 (39) PiDPToQDPProof [SOUND, 0 ms] 9.05/3.21 (40) QDP 9.05/3.21 (41) TransformationProof [SOUND, 0 ms] 9.05/3.21 (42) QDP 9.05/3.21 (43) TransformationProof [EQUIVALENT, 0 ms] 9.05/3.21 (44) QDP 9.05/3.21 (45) PrologToTRSTransformerProof [SOUND, 0 ms] 9.05/3.21 (46) QTRS 9.05/3.21 (47) DependencyPairsProof [EQUIVALENT, 0 ms] 9.05/3.21 (48) QDP 9.05/3.21 (49) DependencyGraphProof [EQUIVALENT, 0 ms] 9.05/3.21 (50) AND 9.05/3.21 (51) QDP 9.05/3.21 (52) UsableRulesProof [EQUIVALENT, 0 ms] 9.05/3.21 (53) QDP 9.05/3.21 (54) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.05/3.21 (55) YES 9.05/3.21 (56) QDP 9.05/3.21 (57) NonTerminationLoopProof [COMPLETE, 0 ms] 9.05/3.21 (58) NO 9.05/3.21 (59) PrologToIRSwTTransformerProof [SOUND, 0 ms] 9.05/3.21 (60) AND 9.05/3.21 (61) IRSwT 9.05/3.21 (62) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 9.05/3.21 (63) IRSwT 9.05/3.21 (64) IntTRSCompressionProof [EQUIVALENT, 35 ms] 9.05/3.21 (65) IRSwT 9.05/3.21 (66) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 9.05/3.21 (67) IRSwT 9.05/3.21 (68) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] 9.05/3.21 (69) IRSwT 9.05/3.21 (70) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 3 ms] 9.05/3.21 (71) IRSwT 9.05/3.21 (72) TempFilterProof [SOUND, 2 ms] 9.05/3.21 (73) IRSwT 9.05/3.21 (74) IRSwTToQDPProof [SOUND, 0 ms] 9.05/3.21 (75) QDP 9.05/3.21 (76) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.05/3.21 (77) YES 9.05/3.21 (78) IRSwT 9.05/3.21 (79) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 9.05/3.21 (80) IRSwT 9.05/3.21 (81) IntTRSCompressionProof [EQUIVALENT, 6 ms] 9.05/3.21 (82) IRSwT 9.05/3.21 (83) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 9.05/3.21 (84) IRSwT 9.05/3.21 (85) IRSwTTerminationDigraphProof [EQUIVALENT, 13 ms] 9.05/3.21 (86) IRSwT 9.05/3.21 (87) PrologToDTProblemTransformerProof [SOUND, 0 ms] 9.05/3.21 (88) TRIPLES 9.05/3.21 (89) TriplesToPiDPProof [SOUND, 0 ms] 9.05/3.21 (90) PiDP 9.05/3.21 (91) DependencyGraphProof [EQUIVALENT, 0 ms] 9.05/3.21 (92) AND 9.05/3.21 (93) PiDP 9.05/3.21 (94) UsableRulesProof [EQUIVALENT, 0 ms] 9.05/3.21 (95) PiDP 9.05/3.21 (96) PiDPToQDPProof [SOUND, 0 ms] 9.05/3.21 (97) QDP 9.05/3.21 (98) QDPSizeChangeProof [EQUIVALENT, 0 ms] 9.05/3.21 (99) YES 9.05/3.21 (100) PiDP 9.05/3.21 (101) PiDPToQDPProof [SOUND, 0 ms] 9.05/3.21 (102) QDP 9.05/3.21 (103) TransformationProof [SOUND, 0 ms] 9.05/3.21 (104) QDP 9.05/3.21 (105) TransformationProof [EQUIVALENT, 0 ms] 9.05/3.21 (106) QDP 9.05/3.21 9.05/3.21 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (0) 9.05/3.21 Obligation: 9.05/3.21 Clauses: 9.05/3.21 9.05/3.21 member(X, .(Y, Xs)) :- member(X, Xs). 9.05/3.21 member(X, .(X, Xs)). 9.05/3.21 subset(.(X, Xs), Ys) :- ','(member(X, Ys), subset(Xs, Ys)). 9.05/3.21 subset([], Ys). 9.05/3.21 9.05/3.21 9.05/3.21 Query: subset(a,g) 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (1) PrologToPiTRSProof (SOUND) 9.05/3.21 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 9.05/3.21 9.05/3.21 subset_in_2: (f,b) 9.05/3.21 9.05/3.21 member_in_2: (f,b) 9.05/3.21 9.05/3.21 Transforming Prolog into the following Term Rewriting System: 9.05/3.21 9.05/3.21 Pi-finite rewrite system: 9.05/3.21 The TRS R consists of the following rules: 9.05/3.21 9.05/3.21 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.21 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.21 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.21 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.21 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.21 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.21 9.05/3.21 The argument filtering Pi contains the following mapping: 9.05/3.21 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.21 9.05/3.21 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.21 9.05/3.21 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.21 9.05/3.21 .(x1, x2) = .(x1, x2) 9.05/3.21 9.05/3.21 U1_ag(x1, x2, x3, x4) = U1_ag(x4) 9.05/3.21 9.05/3.21 member_out_ag(x1, x2) = member_out_ag(x1) 9.05/3.21 9.05/3.21 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x4) 9.05/3.21 9.05/3.21 subset_out_ag(x1, x2) = subset_out_ag(x1) 9.05/3.21 9.05/3.21 9.05/3.21 9.05/3.21 9.05/3.21 9.05/3.21 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 9.05/3.21 9.05/3.21 9.05/3.21 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (2) 9.05/3.21 Obligation: 9.05/3.21 Pi-finite rewrite system: 9.05/3.21 The TRS R consists of the following rules: 9.05/3.21 9.05/3.21 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.21 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.21 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.21 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.21 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.21 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.21 9.05/3.21 The argument filtering Pi contains the following mapping: 9.05/3.21 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.21 9.05/3.21 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.21 9.05/3.21 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.21 9.05/3.21 .(x1, x2) = .(x1, x2) 9.05/3.21 9.05/3.21 U1_ag(x1, x2, x3, x4) = U1_ag(x4) 9.05/3.21 9.05/3.21 member_out_ag(x1, x2) = member_out_ag(x1) 9.05/3.21 9.05/3.21 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x4) 9.05/3.21 9.05/3.21 subset_out_ag(x1, x2) = subset_out_ag(x1) 9.05/3.21 9.05/3.21 9.05/3.21 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (3) DependencyPairsProof (EQUIVALENT) 9.05/3.21 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 9.05/3.21 Pi DP problem: 9.05/3.21 The TRS P consists of the following rules: 9.05/3.21 9.05/3.21 SUBSET_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 SUBSET_IN_AG(.(X, Xs), Ys) -> MEMBER_IN_AG(X, Ys) 9.05/3.21 MEMBER_IN_AG(X, .(Y, Xs)) -> U1_AG(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.21 MEMBER_IN_AG(X, .(Y, Xs)) -> MEMBER_IN_AG(X, Xs) 9.05/3.21 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_AG(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.21 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Xs, Ys) 9.05/3.21 9.05/3.21 The TRS R consists of the following rules: 9.05/3.21 9.05/3.21 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.21 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.21 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.21 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.21 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.21 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.21 9.05/3.21 The argument filtering Pi contains the following mapping: 9.05/3.21 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.21 9.05/3.21 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.21 9.05/3.21 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.21 9.05/3.21 .(x1, x2) = .(x1, x2) 9.05/3.21 9.05/3.21 U1_ag(x1, x2, x3, x4) = U1_ag(x4) 9.05/3.21 9.05/3.21 member_out_ag(x1, x2) = member_out_ag(x1) 9.05/3.21 9.05/3.21 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x4) 9.05/3.21 9.05/3.21 subset_out_ag(x1, x2) = subset_out_ag(x1) 9.05/3.21 9.05/3.21 SUBSET_IN_AG(x1, x2) = SUBSET_IN_AG(x2) 9.05/3.21 9.05/3.21 U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) 9.05/3.21 9.05/3.21 MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) 9.05/3.21 9.05/3.21 U1_AG(x1, x2, x3, x4) = U1_AG(x4) 9.05/3.21 9.05/3.21 U3_AG(x1, x2, x3, x4) = U3_AG(x1, x4) 9.05/3.21 9.05/3.21 9.05/3.21 We have to consider all (P,R,Pi)-chains 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (4) 9.05/3.21 Obligation: 9.05/3.21 Pi DP problem: 9.05/3.21 The TRS P consists of the following rules: 9.05/3.21 9.05/3.21 SUBSET_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 SUBSET_IN_AG(.(X, Xs), Ys) -> MEMBER_IN_AG(X, Ys) 9.05/3.21 MEMBER_IN_AG(X, .(Y, Xs)) -> U1_AG(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.21 MEMBER_IN_AG(X, .(Y, Xs)) -> MEMBER_IN_AG(X, Xs) 9.05/3.21 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_AG(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.21 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Xs, Ys) 9.05/3.21 9.05/3.21 The TRS R consists of the following rules: 9.05/3.21 9.05/3.21 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.21 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.21 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.21 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.21 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.21 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.21 9.05/3.21 The argument filtering Pi contains the following mapping: 9.05/3.21 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.21 9.05/3.21 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.21 9.05/3.21 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.21 9.05/3.21 .(x1, x2) = .(x1, x2) 9.05/3.21 9.05/3.21 U1_ag(x1, x2, x3, x4) = U1_ag(x4) 9.05/3.21 9.05/3.21 member_out_ag(x1, x2) = member_out_ag(x1) 9.05/3.21 9.05/3.21 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x4) 9.05/3.21 9.05/3.21 subset_out_ag(x1, x2) = subset_out_ag(x1) 9.05/3.21 9.05/3.21 SUBSET_IN_AG(x1, x2) = SUBSET_IN_AG(x2) 9.05/3.21 9.05/3.21 U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) 9.05/3.21 9.05/3.21 MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) 9.05/3.21 9.05/3.21 U1_AG(x1, x2, x3, x4) = U1_AG(x4) 9.05/3.21 9.05/3.21 U3_AG(x1, x2, x3, x4) = U3_AG(x1, x4) 9.05/3.21 9.05/3.21 9.05/3.21 We have to consider all (P,R,Pi)-chains 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (5) DependencyGraphProof (EQUIVALENT) 9.05/3.21 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (6) 9.05/3.21 Complex Obligation (AND) 9.05/3.21 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (7) 9.05/3.21 Obligation: 9.05/3.21 Pi DP problem: 9.05/3.21 The TRS P consists of the following rules: 9.05/3.21 9.05/3.21 MEMBER_IN_AG(X, .(Y, Xs)) -> MEMBER_IN_AG(X, Xs) 9.05/3.21 9.05/3.21 The TRS R consists of the following rules: 9.05/3.21 9.05/3.21 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.21 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.21 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.21 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.21 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.21 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.21 9.05/3.21 The argument filtering Pi contains the following mapping: 9.05/3.21 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.21 9.05/3.21 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.21 9.05/3.21 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.21 9.05/3.21 .(x1, x2) = .(x1, x2) 9.05/3.21 9.05/3.21 U1_ag(x1, x2, x3, x4) = U1_ag(x4) 9.05/3.21 9.05/3.21 member_out_ag(x1, x2) = member_out_ag(x1) 9.05/3.21 9.05/3.21 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x4) 9.05/3.21 9.05/3.21 subset_out_ag(x1, x2) = subset_out_ag(x1) 9.05/3.21 9.05/3.21 MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) 9.05/3.21 9.05/3.21 9.05/3.21 We have to consider all (P,R,Pi)-chains 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (8) UsableRulesProof (EQUIVALENT) 9.05/3.21 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (9) 9.05/3.21 Obligation: 9.05/3.21 Pi DP problem: 9.05/3.21 The TRS P consists of the following rules: 9.05/3.21 9.05/3.21 MEMBER_IN_AG(X, .(Y, Xs)) -> MEMBER_IN_AG(X, Xs) 9.05/3.21 9.05/3.21 R is empty. 9.05/3.21 The argument filtering Pi contains the following mapping: 9.05/3.21 .(x1, x2) = .(x1, x2) 9.05/3.21 9.05/3.21 MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) 9.05/3.21 9.05/3.21 9.05/3.21 We have to consider all (P,R,Pi)-chains 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (10) PiDPToQDPProof (SOUND) 9.05/3.21 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (11) 9.05/3.21 Obligation: 9.05/3.21 Q DP problem: 9.05/3.21 The TRS P consists of the following rules: 9.05/3.21 9.05/3.21 MEMBER_IN_AG(.(Y, Xs)) -> MEMBER_IN_AG(Xs) 9.05/3.21 9.05/3.21 R is empty. 9.05/3.21 Q is empty. 9.05/3.21 We have to consider all (P,Q,R)-chains. 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (12) QDPSizeChangeProof (EQUIVALENT) 9.05/3.21 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. 9.05/3.21 9.05/3.21 From the DPs we obtained the following set of size-change graphs: 9.05/3.21 *MEMBER_IN_AG(.(Y, Xs)) -> MEMBER_IN_AG(Xs) 9.05/3.21 The graph contains the following edges 1 > 1 9.05/3.21 9.05/3.21 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (13) 9.05/3.21 YES 9.05/3.21 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (14) 9.05/3.21 Obligation: 9.05/3.21 Pi DP problem: 9.05/3.21 The TRS P consists of the following rules: 9.05/3.21 9.05/3.21 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Xs, Ys) 9.05/3.21 SUBSET_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 9.05/3.21 The TRS R consists of the following rules: 9.05/3.21 9.05/3.21 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.21 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.21 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.21 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.21 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.21 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.21 9.05/3.21 The argument filtering Pi contains the following mapping: 9.05/3.21 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.21 9.05/3.21 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.21 9.05/3.21 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.21 9.05/3.21 .(x1, x2) = .(x1, x2) 9.05/3.21 9.05/3.21 U1_ag(x1, x2, x3, x4) = U1_ag(x4) 9.05/3.21 9.05/3.21 member_out_ag(x1, x2) = member_out_ag(x1) 9.05/3.21 9.05/3.21 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x4) 9.05/3.21 9.05/3.21 subset_out_ag(x1, x2) = subset_out_ag(x1) 9.05/3.21 9.05/3.21 SUBSET_IN_AG(x1, x2) = SUBSET_IN_AG(x2) 9.05/3.21 9.05/3.21 U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) 9.05/3.21 9.05/3.21 9.05/3.21 We have to consider all (P,R,Pi)-chains 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (15) UsableRulesProof (EQUIVALENT) 9.05/3.21 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (16) 9.05/3.21 Obligation: 9.05/3.21 Pi DP problem: 9.05/3.21 The TRS P consists of the following rules: 9.05/3.21 9.05/3.21 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Xs, Ys) 9.05/3.21 SUBSET_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.21 9.05/3.21 The TRS R consists of the following rules: 9.05/3.21 9.05/3.21 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.21 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.21 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.21 9.05/3.21 The argument filtering Pi contains the following mapping: 9.05/3.21 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.21 9.05/3.21 .(x1, x2) = .(x1, x2) 9.05/3.21 9.05/3.21 U1_ag(x1, x2, x3, x4) = U1_ag(x4) 9.05/3.21 9.05/3.21 member_out_ag(x1, x2) = member_out_ag(x1) 9.05/3.21 9.05/3.21 SUBSET_IN_AG(x1, x2) = SUBSET_IN_AG(x2) 9.05/3.21 9.05/3.21 U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) 9.05/3.21 9.05/3.21 9.05/3.21 We have to consider all (P,R,Pi)-chains 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (17) PiDPToQDPProof (SOUND) 9.05/3.21 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (18) 9.05/3.21 Obligation: 9.05/3.21 Q DP problem: 9.05/3.21 The TRS P consists of the following rules: 9.05/3.21 9.05/3.21 U2_AG(Ys, member_out_ag(X)) -> SUBSET_IN_AG(Ys) 9.05/3.21 SUBSET_IN_AG(Ys) -> U2_AG(Ys, member_in_ag(Ys)) 9.05/3.21 9.05/3.21 The TRS R consists of the following rules: 9.05/3.21 9.05/3.21 member_in_ag(.(Y, Xs)) -> U1_ag(member_in_ag(Xs)) 9.05/3.21 member_in_ag(.(X, Xs)) -> member_out_ag(X) 9.05/3.21 U1_ag(member_out_ag(X)) -> member_out_ag(X) 9.05/3.21 9.05/3.21 The set Q consists of the following terms: 9.05/3.21 9.05/3.21 member_in_ag(x0) 9.05/3.21 U1_ag(x0) 9.05/3.21 9.05/3.21 We have to consider all (P,Q,R)-chains. 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (19) TransformationProof (SOUND) 9.05/3.21 By narrowing [LPAR04] the rule SUBSET_IN_AG(Ys) -> U2_AG(Ys, member_in_ag(Ys)) at position [1] we obtained the following new rules [LPAR04]: 9.05/3.21 9.05/3.21 (SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), U1_ag(member_in_ag(x1))),SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), U1_ag(member_in_ag(x1)))) 9.05/3.21 (SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), member_out_ag(x0)),SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), member_out_ag(x0))) 9.05/3.21 9.05/3.21 9.05/3.21 ---------------------------------------- 9.05/3.21 9.05/3.21 (20) 9.05/3.21 Obligation: 9.05/3.21 Q DP problem: 9.05/3.21 The TRS P consists of the following rules: 9.05/3.21 9.05/3.21 U2_AG(Ys, member_out_ag(X)) -> SUBSET_IN_AG(Ys) 9.05/3.21 SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), U1_ag(member_in_ag(x1))) 9.05/3.21 SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), member_out_ag(x0)) 9.05/3.21 9.05/3.21 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 member_in_ag(.(Y, Xs)) -> U1_ag(member_in_ag(Xs)) 9.05/3.23 member_in_ag(.(X, Xs)) -> member_out_ag(X) 9.05/3.23 U1_ag(member_out_ag(X)) -> member_out_ag(X) 9.05/3.23 9.05/3.23 The set Q consists of the following terms: 9.05/3.23 9.05/3.23 member_in_ag(x0) 9.05/3.23 U1_ag(x0) 9.05/3.23 9.05/3.23 We have to consider all (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (21) TransformationProof (EQUIVALENT) 9.05/3.23 By instantiating [LPAR04] the rule U2_AG(Ys, member_out_ag(X)) -> SUBSET_IN_AG(Ys) we obtained the following new rules [LPAR04]: 9.05/3.23 9.05/3.23 (U2_AG(.(z0, z1), member_out_ag(x1)) -> SUBSET_IN_AG(.(z0, z1)),U2_AG(.(z0, z1), member_out_ag(x1)) -> SUBSET_IN_AG(.(z0, z1))) 9.05/3.23 (U2_AG(.(z0, z1), member_out_ag(z0)) -> SUBSET_IN_AG(.(z0, z1)),U2_AG(.(z0, z1), member_out_ag(z0)) -> SUBSET_IN_AG(.(z0, z1))) 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (22) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), U1_ag(member_in_ag(x1))) 9.05/3.23 SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), member_out_ag(x0)) 9.05/3.23 U2_AG(.(z0, z1), member_out_ag(x1)) -> SUBSET_IN_AG(.(z0, z1)) 9.05/3.23 U2_AG(.(z0, z1), member_out_ag(z0)) -> SUBSET_IN_AG(.(z0, z1)) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 member_in_ag(.(Y, Xs)) -> U1_ag(member_in_ag(Xs)) 9.05/3.23 member_in_ag(.(X, Xs)) -> member_out_ag(X) 9.05/3.23 U1_ag(member_out_ag(X)) -> member_out_ag(X) 9.05/3.23 9.05/3.23 The set Q consists of the following terms: 9.05/3.23 9.05/3.23 member_in_ag(x0) 9.05/3.23 U1_ag(x0) 9.05/3.23 9.05/3.23 We have to consider all (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (23) PrologToPiTRSProof (SOUND) 9.05/3.23 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 9.05/3.23 9.05/3.23 subset_in_2: (f,b) 9.05/3.23 9.05/3.23 member_in_2: (f,b) 9.05/3.23 9.05/3.23 Transforming Prolog into the following Term Rewriting System: 9.05/3.23 9.05/3.23 Pi-finite rewrite system: 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.23 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.23 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.23 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.23 9.05/3.23 The argument filtering Pi contains the following mapping: 9.05/3.23 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.23 9.05/3.23 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.23 9.05/3.23 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.23 9.05/3.23 .(x1, x2) = .(x1, x2) 9.05/3.23 9.05/3.23 U1_ag(x1, x2, x3, x4) = U1_ag(x2, x3, x4) 9.05/3.23 9.05/3.23 member_out_ag(x1, x2) = member_out_ag(x1, x2) 9.05/3.23 9.05/3.23 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x3, x4) 9.05/3.23 9.05/3.23 subset_out_ag(x1, x2) = subset_out_ag(x1, x2) 9.05/3.23 9.05/3.23 9.05/3.23 9.05/3.23 9.05/3.23 9.05/3.23 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 9.05/3.23 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (24) 9.05/3.23 Obligation: 9.05/3.23 Pi-finite rewrite system: 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.23 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.23 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.23 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.23 9.05/3.23 The argument filtering Pi contains the following mapping: 9.05/3.23 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.23 9.05/3.23 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.23 9.05/3.23 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.23 9.05/3.23 .(x1, x2) = .(x1, x2) 9.05/3.23 9.05/3.23 U1_ag(x1, x2, x3, x4) = U1_ag(x2, x3, x4) 9.05/3.23 9.05/3.23 member_out_ag(x1, x2) = member_out_ag(x1, x2) 9.05/3.23 9.05/3.23 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x3, x4) 9.05/3.23 9.05/3.23 subset_out_ag(x1, x2) = subset_out_ag(x1, x2) 9.05/3.23 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (25) DependencyPairsProof (EQUIVALENT) 9.05/3.23 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 9.05/3.23 Pi DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 SUBSET_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 SUBSET_IN_AG(.(X, Xs), Ys) -> MEMBER_IN_AG(X, Ys) 9.05/3.23 MEMBER_IN_AG(X, .(Y, Xs)) -> U1_AG(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.23 MEMBER_IN_AG(X, .(Y, Xs)) -> MEMBER_IN_AG(X, Xs) 9.05/3.23 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_AG(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.23 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Xs, Ys) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.23 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.23 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.23 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.23 9.05/3.23 The argument filtering Pi contains the following mapping: 9.05/3.23 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.23 9.05/3.23 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.23 9.05/3.23 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.23 9.05/3.23 .(x1, x2) = .(x1, x2) 9.05/3.23 9.05/3.23 U1_ag(x1, x2, x3, x4) = U1_ag(x2, x3, x4) 9.05/3.23 9.05/3.23 member_out_ag(x1, x2) = member_out_ag(x1, x2) 9.05/3.23 9.05/3.23 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x3, x4) 9.05/3.23 9.05/3.23 subset_out_ag(x1, x2) = subset_out_ag(x1, x2) 9.05/3.23 9.05/3.23 SUBSET_IN_AG(x1, x2) = SUBSET_IN_AG(x2) 9.05/3.23 9.05/3.23 U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) 9.05/3.23 9.05/3.23 MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) 9.05/3.23 9.05/3.23 U1_AG(x1, x2, x3, x4) = U1_AG(x2, x3, x4) 9.05/3.23 9.05/3.23 U3_AG(x1, x2, x3, x4) = U3_AG(x1, x3, x4) 9.05/3.23 9.05/3.23 9.05/3.23 We have to consider all (P,R,Pi)-chains 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (26) 9.05/3.23 Obligation: 9.05/3.23 Pi DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 SUBSET_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 SUBSET_IN_AG(.(X, Xs), Ys) -> MEMBER_IN_AG(X, Ys) 9.05/3.23 MEMBER_IN_AG(X, .(Y, Xs)) -> U1_AG(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.23 MEMBER_IN_AG(X, .(Y, Xs)) -> MEMBER_IN_AG(X, Xs) 9.05/3.23 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_AG(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.23 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Xs, Ys) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.23 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.23 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.23 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.23 9.05/3.23 The argument filtering Pi contains the following mapping: 9.05/3.23 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.23 9.05/3.23 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.23 9.05/3.23 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.23 9.05/3.23 .(x1, x2) = .(x1, x2) 9.05/3.23 9.05/3.23 U1_ag(x1, x2, x3, x4) = U1_ag(x2, x3, x4) 9.05/3.23 9.05/3.23 member_out_ag(x1, x2) = member_out_ag(x1, x2) 9.05/3.23 9.05/3.23 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x3, x4) 9.05/3.23 9.05/3.23 subset_out_ag(x1, x2) = subset_out_ag(x1, x2) 9.05/3.23 9.05/3.23 SUBSET_IN_AG(x1, x2) = SUBSET_IN_AG(x2) 9.05/3.23 9.05/3.23 U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) 9.05/3.23 9.05/3.23 MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) 9.05/3.23 9.05/3.23 U1_AG(x1, x2, x3, x4) = U1_AG(x2, x3, x4) 9.05/3.23 9.05/3.23 U3_AG(x1, x2, x3, x4) = U3_AG(x1, x3, x4) 9.05/3.23 9.05/3.23 9.05/3.23 We have to consider all (P,R,Pi)-chains 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (27) DependencyGraphProof (EQUIVALENT) 9.05/3.23 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (28) 9.05/3.23 Complex Obligation (AND) 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (29) 9.05/3.23 Obligation: 9.05/3.23 Pi DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 MEMBER_IN_AG(X, .(Y, Xs)) -> MEMBER_IN_AG(X, Xs) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.23 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.23 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.23 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.23 9.05/3.23 The argument filtering Pi contains the following mapping: 9.05/3.23 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.23 9.05/3.23 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.23 9.05/3.23 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.23 9.05/3.23 .(x1, x2) = .(x1, x2) 9.05/3.23 9.05/3.23 U1_ag(x1, x2, x3, x4) = U1_ag(x2, x3, x4) 9.05/3.23 9.05/3.23 member_out_ag(x1, x2) = member_out_ag(x1, x2) 9.05/3.23 9.05/3.23 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x3, x4) 9.05/3.23 9.05/3.23 subset_out_ag(x1, x2) = subset_out_ag(x1, x2) 9.05/3.23 9.05/3.23 MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) 9.05/3.23 9.05/3.23 9.05/3.23 We have to consider all (P,R,Pi)-chains 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (30) UsableRulesProof (EQUIVALENT) 9.05/3.23 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (31) 9.05/3.23 Obligation: 9.05/3.23 Pi DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 MEMBER_IN_AG(X, .(Y, Xs)) -> MEMBER_IN_AG(X, Xs) 9.05/3.23 9.05/3.23 R is empty. 9.05/3.23 The argument filtering Pi contains the following mapping: 9.05/3.23 .(x1, x2) = .(x1, x2) 9.05/3.23 9.05/3.23 MEMBER_IN_AG(x1, x2) = MEMBER_IN_AG(x2) 9.05/3.23 9.05/3.23 9.05/3.23 We have to consider all (P,R,Pi)-chains 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (32) PiDPToQDPProof (SOUND) 9.05/3.23 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (33) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 MEMBER_IN_AG(.(Y, Xs)) -> MEMBER_IN_AG(Xs) 9.05/3.23 9.05/3.23 R is empty. 9.05/3.23 Q is empty. 9.05/3.23 We have to consider all (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (34) QDPSizeChangeProof (EQUIVALENT) 9.05/3.23 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. 9.05/3.23 9.05/3.23 From the DPs we obtained the following set of size-change graphs: 9.05/3.23 *MEMBER_IN_AG(.(Y, Xs)) -> MEMBER_IN_AG(Xs) 9.05/3.23 The graph contains the following edges 1 > 1 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (35) 9.05/3.23 YES 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (36) 9.05/3.23 Obligation: 9.05/3.23 Pi DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Xs, Ys) 9.05/3.23 SUBSET_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 subset_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.23 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 U2_ag(X, Xs, Ys, member_out_ag(X, Ys)) -> U3_ag(X, Xs, Ys, subset_in_ag(Xs, Ys)) 9.05/3.23 subset_in_ag([], Ys) -> subset_out_ag([], Ys) 9.05/3.23 U3_ag(X, Xs, Ys, subset_out_ag(Xs, Ys)) -> subset_out_ag(.(X, Xs), Ys) 9.05/3.23 9.05/3.23 The argument filtering Pi contains the following mapping: 9.05/3.23 subset_in_ag(x1, x2) = subset_in_ag(x2) 9.05/3.23 9.05/3.23 U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) 9.05/3.23 9.05/3.23 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.23 9.05/3.23 .(x1, x2) = .(x1, x2) 9.05/3.23 9.05/3.23 U1_ag(x1, x2, x3, x4) = U1_ag(x2, x3, x4) 9.05/3.23 9.05/3.23 member_out_ag(x1, x2) = member_out_ag(x1, x2) 9.05/3.23 9.05/3.23 U3_ag(x1, x2, x3, x4) = U3_ag(x1, x3, x4) 9.05/3.23 9.05/3.23 subset_out_ag(x1, x2) = subset_out_ag(x1, x2) 9.05/3.23 9.05/3.23 SUBSET_IN_AG(x1, x2) = SUBSET_IN_AG(x2) 9.05/3.23 9.05/3.23 U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) 9.05/3.23 9.05/3.23 9.05/3.23 We have to consider all (P,R,Pi)-chains 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (37) UsableRulesProof (EQUIVALENT) 9.05/3.23 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (38) 9.05/3.23 Obligation: 9.05/3.23 Pi DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 U2_AG(X, Xs, Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Xs, Ys) 9.05/3.23 SUBSET_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, member_in_ag(X, Ys)) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 member_in_ag(X, .(Y, Xs)) -> U1_ag(X, Y, Xs, member_in_ag(X, Xs)) 9.05/3.23 member_in_ag(X, .(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(X, Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 9.05/3.23 The argument filtering Pi contains the following mapping: 9.05/3.23 member_in_ag(x1, x2) = member_in_ag(x2) 9.05/3.23 9.05/3.23 .(x1, x2) = .(x1, x2) 9.05/3.23 9.05/3.23 U1_ag(x1, x2, x3, x4) = U1_ag(x2, x3, x4) 9.05/3.23 9.05/3.23 member_out_ag(x1, x2) = member_out_ag(x1, x2) 9.05/3.23 9.05/3.23 SUBSET_IN_AG(x1, x2) = SUBSET_IN_AG(x2) 9.05/3.23 9.05/3.23 U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) 9.05/3.23 9.05/3.23 9.05/3.23 We have to consider all (P,R,Pi)-chains 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (39) PiDPToQDPProof (SOUND) 9.05/3.23 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (40) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 U2_AG(Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Ys) 9.05/3.23 SUBSET_IN_AG(Ys) -> U2_AG(Ys, member_in_ag(Ys)) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 member_in_ag(.(Y, Xs)) -> U1_ag(Y, Xs, member_in_ag(Xs)) 9.05/3.23 member_in_ag(.(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 9.05/3.23 The set Q consists of the following terms: 9.05/3.23 9.05/3.23 member_in_ag(x0) 9.05/3.23 U1_ag(x0, x1, x2) 9.05/3.23 9.05/3.23 We have to consider all (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (41) TransformationProof (SOUND) 9.05/3.23 By narrowing [LPAR04] the rule SUBSET_IN_AG(Ys) -> U2_AG(Ys, member_in_ag(Ys)) at position [1] we obtained the following new rules [LPAR04]: 9.05/3.23 9.05/3.23 (SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), U1_ag(x0, x1, member_in_ag(x1))),SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), U1_ag(x0, x1, member_in_ag(x1)))) 9.05/3.23 (SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), member_out_ag(x0, .(x0, x1))),SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), member_out_ag(x0, .(x0, x1)))) 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (42) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 U2_AG(Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Ys) 9.05/3.23 SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), U1_ag(x0, x1, member_in_ag(x1))) 9.05/3.23 SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), member_out_ag(x0, .(x0, x1))) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 member_in_ag(.(Y, Xs)) -> U1_ag(Y, Xs, member_in_ag(Xs)) 9.05/3.23 member_in_ag(.(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 9.05/3.23 The set Q consists of the following terms: 9.05/3.23 9.05/3.23 member_in_ag(x0) 9.05/3.23 U1_ag(x0, x1, x2) 9.05/3.23 9.05/3.23 We have to consider all (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (43) TransformationProof (EQUIVALENT) 9.05/3.23 By instantiating [LPAR04] the rule U2_AG(Ys, member_out_ag(X, Ys)) -> SUBSET_IN_AG(Ys) we obtained the following new rules [LPAR04]: 9.05/3.23 9.05/3.23 (U2_AG(.(z0, z1), member_out_ag(x1, .(z0, z1))) -> SUBSET_IN_AG(.(z0, z1)),U2_AG(.(z0, z1), member_out_ag(x1, .(z0, z1))) -> SUBSET_IN_AG(.(z0, z1))) 9.05/3.23 (U2_AG(.(z0, z1), member_out_ag(z0, .(z0, z1))) -> SUBSET_IN_AG(.(z0, z1)),U2_AG(.(z0, z1), member_out_ag(z0, .(z0, z1))) -> SUBSET_IN_AG(.(z0, z1))) 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (44) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), U1_ag(x0, x1, member_in_ag(x1))) 9.05/3.23 SUBSET_IN_AG(.(x0, x1)) -> U2_AG(.(x0, x1), member_out_ag(x0, .(x0, x1))) 9.05/3.23 U2_AG(.(z0, z1), member_out_ag(x1, .(z0, z1))) -> SUBSET_IN_AG(.(z0, z1)) 9.05/3.23 U2_AG(.(z0, z1), member_out_ag(z0, .(z0, z1))) -> SUBSET_IN_AG(.(z0, z1)) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 member_in_ag(.(Y, Xs)) -> U1_ag(Y, Xs, member_in_ag(Xs)) 9.05/3.23 member_in_ag(.(X, Xs)) -> member_out_ag(X, .(X, Xs)) 9.05/3.23 U1_ag(Y, Xs, member_out_ag(X, Xs)) -> member_out_ag(X, .(Y, Xs)) 9.05/3.23 9.05/3.23 The set Q consists of the following terms: 9.05/3.23 9.05/3.23 member_in_ag(x0) 9.05/3.23 U1_ag(x0, x1, x2) 9.05/3.23 9.05/3.23 We have to consider all (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (45) PrologToTRSTransformerProof (SOUND) 9.05/3.23 Transformed Prolog program to TRS. 9.05/3.23 9.05/3.23 { 9.05/3.23 "root": 10, 9.05/3.23 "program": { 9.05/3.23 "directives": [], 9.05/3.23 "clauses": [ 9.05/3.23 [ 9.05/3.23 "(member X (. Y Xs))", 9.05/3.23 "(member X Xs)" 9.05/3.23 ], 9.05/3.23 [ 9.05/3.23 "(member X (. X Xs))", 9.05/3.23 null 9.05/3.23 ], 9.05/3.23 [ 9.05/3.23 "(subset (. X Xs) Ys)", 9.05/3.23 "(',' (member X Ys) (subset Xs Ys))" 9.05/3.23 ], 9.05/3.23 [ 9.05/3.23 "(subset ([]) Ys)", 9.05/3.23 null 9.05/3.23 ] 9.05/3.23 ] 9.05/3.23 }, 9.05/3.23 "graph": { 9.05/3.23 "nodes": { 9.05/3.23 "34": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(',' (member T18 T17) (subset T19 T17))" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "35": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "14": { 9.05/3.23 "goal": [ 9.05/3.23 { 9.05/3.23 "clause": 2, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "clause": 3, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 } 9.05/3.23 ], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T2"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "25": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 2, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T2"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "26": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 3, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T2"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "180": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(true)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "170": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(member T42 T41)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T41"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "171": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "182": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "type": "Nodes", 9.05/3.23 "172": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(true)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "183": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "174": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "165": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "166": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(subset T23 T17)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "177": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "167": { 9.05/3.23 "goal": [ 9.05/3.23 { 9.05/3.23 "clause": 0, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "clause": 1, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 } 9.05/3.23 ], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "168": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 0, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "169": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 1, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "10": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T2"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "edges": [ 9.05/3.23 { 9.05/3.23 "from": 10, 9.05/3.23 "to": 14, 9.05/3.23 "label": "CASE" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 14, 9.05/3.23 "to": 25, 9.05/3.23 "label": "PARALLEL" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 14, 9.05/3.23 "to": 26, 9.05/3.23 "label": "PARALLEL" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 25, 9.05/3.23 "to": 34, 9.05/3.23 "label": "EVAL with clause\nsubset(.(X13, X14), X15) :- ','(member(X13, X15), subset(X14, X15)).\nand substitutionX13 -> T18,\nX14 -> T19,\nT1 -> .(T18, T19),\nT2 -> T17,\nX15 -> T17,\nT15 -> T18,\nT16 -> T19" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 25, 9.05/3.23 "to": 35, 9.05/3.23 "label": "EVAL-BACKTRACK" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 26, 9.05/3.23 "to": 180, 9.05/3.23 "label": "EVAL with clause\nsubset([], X51).\nand substitutionT1 -> [],\nT2 -> T57,\nX51 -> T57" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 26, 9.05/3.23 "to": 182, 9.05/3.23 "label": "EVAL-BACKTRACK" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 34, 9.05/3.23 "to": 165, 9.05/3.23 "label": "SPLIT 1" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 34, 9.05/3.23 "to": 166, 9.05/3.23 "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nT17 is ground\nreplacements:T19 -> T23" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 165, 9.05/3.23 "to": 167, 9.05/3.23 "label": "CASE" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 166, 9.05/3.23 "to": 10, 9.05/3.23 "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T17" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 167, 9.05/3.23 "to": 168, 9.05/3.23 "label": "PARALLEL" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 167, 9.05/3.23 "to": 169, 9.05/3.23 "label": "PARALLEL" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 168, 9.05/3.23 "to": 170, 9.05/3.23 "label": "EVAL with clause\nmember(X34, .(X35, X36)) :- member(X34, X36).\nand substitutionT18 -> T42,\nX34 -> T42,\nX35 -> T40,\nX36 -> T41,\nT17 -> .(T40, T41),\nT39 -> T42" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 168, 9.05/3.23 "to": 171, 9.05/3.23 "label": "EVAL-BACKTRACK" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 169, 9.05/3.23 "to": 172, 9.05/3.23 "label": "EVAL with clause\nmember(X44, .(X44, X45)).\nand substitutionT18 -> T50,\nX44 -> T50,\nX45 -> T51,\nT17 -> .(T50, T51)" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 169, 9.05/3.23 "to": 174, 9.05/3.23 "label": "EVAL-BACKTRACK" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 170, 9.05/3.23 "to": 165, 9.05/3.23 "label": "INSTANCE with matching:\nT18 -> T42\nT17 -> T41" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 172, 9.05/3.23 "to": 177, 9.05/3.23 "label": "SUCCESS" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 180, 9.05/3.23 "to": 183, 9.05/3.23 "label": "SUCCESS" 9.05/3.23 } 9.05/3.23 ], 9.05/3.23 "type": "Graph" 9.05/3.23 } 9.05/3.23 } 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (46) 9.05/3.23 Obligation: 9.05/3.23 Q restricted rewrite system: 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 f10_in(T17) -> U1(f34_in(T17), T17) 9.05/3.23 U1(f34_out1(T18, T19), T17) -> f10_out1(.(T18, T19)) 9.05/3.23 f10_in(T57) -> f10_out1([]) 9.05/3.23 f165_in(.(T40, T41)) -> U2(f165_in(T41), .(T40, T41)) 9.05/3.23 U2(f165_out1(T42), .(T40, T41)) -> f165_out1(T42) 9.05/3.23 f165_in(.(T50, T51)) -> f165_out1(T50) 9.05/3.23 f34_in(T17) -> U3(f165_in(T17), T17) 9.05/3.23 U3(f165_out1(T18), T17) -> U4(f10_in(T17), T17, T18) 9.05/3.23 U4(f10_out1(T23), T17, T18) -> f34_out1(T18, T23) 9.05/3.23 9.05/3.23 Q is empty. 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (47) DependencyPairsProof (EQUIVALENT) 9.05/3.23 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (48) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 F10_IN(T17) -> U1^1(f34_in(T17), T17) 9.05/3.23 F10_IN(T17) -> F34_IN(T17) 9.05/3.23 F165_IN(.(T40, T41)) -> U2^1(f165_in(T41), .(T40, T41)) 9.05/3.23 F165_IN(.(T40, T41)) -> F165_IN(T41) 9.05/3.23 F34_IN(T17) -> U3^1(f165_in(T17), T17) 9.05/3.23 F34_IN(T17) -> F165_IN(T17) 9.05/3.23 U3^1(f165_out1(T18), T17) -> U4^1(f10_in(T17), T17, T18) 9.05/3.23 U3^1(f165_out1(T18), T17) -> F10_IN(T17) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 f10_in(T17) -> U1(f34_in(T17), T17) 9.05/3.23 U1(f34_out1(T18, T19), T17) -> f10_out1(.(T18, T19)) 9.05/3.23 f10_in(T57) -> f10_out1([]) 9.05/3.23 f165_in(.(T40, T41)) -> U2(f165_in(T41), .(T40, T41)) 9.05/3.23 U2(f165_out1(T42), .(T40, T41)) -> f165_out1(T42) 9.05/3.23 f165_in(.(T50, T51)) -> f165_out1(T50) 9.05/3.23 f34_in(T17) -> U3(f165_in(T17), T17) 9.05/3.23 U3(f165_out1(T18), T17) -> U4(f10_in(T17), T17, T18) 9.05/3.23 U4(f10_out1(T23), T17, T18) -> f34_out1(T18, T23) 9.05/3.23 9.05/3.23 Q is empty. 9.05/3.23 We have to consider all minimal (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (49) DependencyGraphProof (EQUIVALENT) 9.05/3.23 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (50) 9.05/3.23 Complex Obligation (AND) 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (51) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 F165_IN(.(T40, T41)) -> F165_IN(T41) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 f10_in(T17) -> U1(f34_in(T17), T17) 9.05/3.23 U1(f34_out1(T18, T19), T17) -> f10_out1(.(T18, T19)) 9.05/3.23 f10_in(T57) -> f10_out1([]) 9.05/3.23 f165_in(.(T40, T41)) -> U2(f165_in(T41), .(T40, T41)) 9.05/3.23 U2(f165_out1(T42), .(T40, T41)) -> f165_out1(T42) 9.05/3.23 f165_in(.(T50, T51)) -> f165_out1(T50) 9.05/3.23 f34_in(T17) -> U3(f165_in(T17), T17) 9.05/3.23 U3(f165_out1(T18), T17) -> U4(f10_in(T17), T17, T18) 9.05/3.23 U4(f10_out1(T23), T17, T18) -> f34_out1(T18, T23) 9.05/3.23 9.05/3.23 Q is empty. 9.05/3.23 We have to consider all minimal (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (52) UsableRulesProof (EQUIVALENT) 9.05/3.23 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. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (53) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 F165_IN(.(T40, T41)) -> F165_IN(T41) 9.05/3.23 9.05/3.23 R is empty. 9.05/3.23 Q is empty. 9.05/3.23 We have to consider all minimal (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (54) QDPSizeChangeProof (EQUIVALENT) 9.05/3.23 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. 9.05/3.23 9.05/3.23 From the DPs we obtained the following set of size-change graphs: 9.05/3.23 *F165_IN(.(T40, T41)) -> F165_IN(T41) 9.05/3.23 The graph contains the following edges 1 > 1 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (55) 9.05/3.23 YES 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (56) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 F10_IN(T17) -> F34_IN(T17) 9.05/3.23 F34_IN(T17) -> U3^1(f165_in(T17), T17) 9.05/3.23 U3^1(f165_out1(T18), T17) -> F10_IN(T17) 9.05/3.23 9.05/3.23 The TRS R consists of the following rules: 9.05/3.23 9.05/3.23 f10_in(T17) -> U1(f34_in(T17), T17) 9.05/3.23 U1(f34_out1(T18, T19), T17) -> f10_out1(.(T18, T19)) 9.05/3.23 f10_in(T57) -> f10_out1([]) 9.05/3.23 f165_in(.(T40, T41)) -> U2(f165_in(T41), .(T40, T41)) 9.05/3.23 U2(f165_out1(T42), .(T40, T41)) -> f165_out1(T42) 9.05/3.23 f165_in(.(T50, T51)) -> f165_out1(T50) 9.05/3.23 f34_in(T17) -> U3(f165_in(T17), T17) 9.05/3.23 U3(f165_out1(T18), T17) -> U4(f10_in(T17), T17, T18) 9.05/3.23 U4(f10_out1(T23), T17, T18) -> f34_out1(T18, T23) 9.05/3.23 9.05/3.23 Q is empty. 9.05/3.23 We have to consider all minimal (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (57) NonTerminationLoopProof (COMPLETE) 9.05/3.23 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 9.05/3.23 Found a loop by narrowing to the left: 9.05/3.23 9.05/3.23 s = F34_IN(.(T50, T51)) evaluates to t =F34_IN(.(T50, T51)) 9.05/3.23 9.05/3.23 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 9.05/3.23 * Matcher: [ ] 9.05/3.23 * Semiunifier: [ ] 9.05/3.23 9.05/3.23 -------------------------------------------------------------------------------- 9.05/3.23 Rewriting sequence 9.05/3.23 9.05/3.23 F34_IN(.(T50, T51)) -> U3^1(f165_in(.(T50, T51)), .(T50, T51)) 9.05/3.23 with rule F34_IN(T17) -> U3^1(f165_in(T17), T17) at position [] and matcher [T17 / .(T50, T51)] 9.05/3.23 9.05/3.23 U3^1(f165_in(.(T50, T51)), .(T50, T51)) -> U3^1(f165_out1(T50), .(T50, T51)) 9.05/3.23 with rule f165_in(.(T50', T51')) -> f165_out1(T50') at position [0] and matcher [T50' / T50, T51' / T51] 9.05/3.23 9.05/3.23 U3^1(f165_out1(T50), .(T50, T51)) -> F10_IN(.(T50, T51)) 9.05/3.23 with rule U3^1(f165_out1(T18), T17') -> F10_IN(T17') at position [] and matcher [T18 / T50, T17' / .(T50, T51)] 9.05/3.23 9.05/3.23 F10_IN(.(T50, T51)) -> F34_IN(.(T50, T51)) 9.05/3.23 with rule F10_IN(T17) -> F34_IN(T17) 9.05/3.23 9.05/3.23 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 9.05/3.23 9.05/3.23 9.05/3.23 All these steps are and every following step will be a correct step w.r.t to Q. 9.05/3.23 9.05/3.23 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (58) 9.05/3.23 NO 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (59) PrologToIRSwTTransformerProof (SOUND) 9.05/3.23 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 9.05/3.23 9.05/3.23 { 9.05/3.23 "root": 11, 9.05/3.23 "program": { 9.05/3.23 "directives": [], 9.05/3.23 "clauses": [ 9.05/3.23 [ 9.05/3.23 "(member X (. Y Xs))", 9.05/3.23 "(member X Xs)" 9.05/3.23 ], 9.05/3.23 [ 9.05/3.23 "(member X (. X Xs))", 9.05/3.23 null 9.05/3.23 ], 9.05/3.23 [ 9.05/3.23 "(subset (. X Xs) Ys)", 9.05/3.23 "(',' (member X Ys) (subset Xs Ys))" 9.05/3.23 ], 9.05/3.23 [ 9.05/3.23 "(subset ([]) Ys)", 9.05/3.23 null 9.05/3.23 ] 9.05/3.23 ] 9.05/3.23 }, 9.05/3.23 "graph": { 9.05/3.23 "nodes": { 9.05/3.23 "11": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T2"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "12": { 9.05/3.23 "goal": [ 9.05/3.23 { 9.05/3.23 "clause": 2, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "clause": 3, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 } 9.05/3.23 ], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T2"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "23": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 2, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T2"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "24": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 3, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T2"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "36": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(',' (member T18 T17) (subset T19 T17))" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "37": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "181": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "160": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 1, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "type": "Nodes", 9.05/3.23 "173": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(true)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "163": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(member T42 T41)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T41"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "153": { 9.05/3.23 "goal": [ 9.05/3.23 { 9.05/3.23 "clause": 0, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "clause": 1, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 } 9.05/3.23 ], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "164": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "175": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "176": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "178": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(true)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "179": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "158": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 0, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "86": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(member T18 T17)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "87": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(subset T23 T17)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T17"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "edges": [ 9.05/3.23 { 9.05/3.23 "from": 11, 9.05/3.23 "to": 12, 9.05/3.23 "label": "CASE" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 12, 9.05/3.23 "to": 23, 9.05/3.23 "label": "PARALLEL" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 12, 9.05/3.23 "to": 24, 9.05/3.23 "label": "PARALLEL" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 23, 9.05/3.23 "to": 36, 9.05/3.23 "label": "EVAL with clause\nsubset(.(X13, X14), X15) :- ','(member(X13, X15), subset(X14, X15)).\nand substitutionX13 -> T18,\nX14 -> T19,\nT1 -> .(T18, T19),\nT2 -> T17,\nX15 -> T17,\nT15 -> T18,\nT16 -> T19" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 23, 9.05/3.23 "to": 37, 9.05/3.23 "label": "EVAL-BACKTRACK" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 24, 9.05/3.23 "to": 178, 9.05/3.23 "label": "EVAL with clause\nsubset([], X51).\nand substitutionT1 -> [],\nT2 -> T57,\nX51 -> T57" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 24, 9.05/3.23 "to": 179, 9.05/3.23 "label": "EVAL-BACKTRACK" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 36, 9.05/3.23 "to": 86, 9.05/3.23 "label": "SPLIT 1" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 36, 9.05/3.23 "to": 87, 9.05/3.23 "label": "SPLIT 2\nnew knowledge:\nT18 is ground\nT17 is ground\nreplacements:T19 -> T23" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 86, 9.05/3.23 "to": 153, 9.05/3.23 "label": "CASE" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 87, 9.05/3.23 "to": 11, 9.05/3.23 "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T17" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 153, 9.05/3.23 "to": 158, 9.05/3.23 "label": "PARALLEL" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 153, 9.05/3.23 "to": 160, 9.05/3.23 "label": "PARALLEL" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 158, 9.05/3.23 "to": 163, 9.05/3.23 "label": "EVAL with clause\nmember(X34, .(X35, X36)) :- member(X34, X36).\nand substitutionT18 -> T42,\nX34 -> T42,\nX35 -> T40,\nX36 -> T41,\nT17 -> .(T40, T41),\nT39 -> T42" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 158, 9.05/3.23 "to": 164, 9.05/3.23 "label": "EVAL-BACKTRACK" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 160, 9.05/3.23 "to": 173, 9.05/3.23 "label": "EVAL with clause\nmember(X44, .(X44, X45)).\nand substitutionT18 -> T50,\nX44 -> T50,\nX45 -> T51,\nT17 -> .(T50, T51)" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 160, 9.05/3.23 "to": 175, 9.05/3.23 "label": "EVAL-BACKTRACK" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 163, 9.05/3.23 "to": 86, 9.05/3.23 "label": "INSTANCE with matching:\nT18 -> T42\nT17 -> T41" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 173, 9.05/3.23 "to": 176, 9.05/3.23 "label": "SUCCESS" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "from": 178, 9.05/3.23 "to": 181, 9.05/3.23 "label": "SUCCESS" 9.05/3.23 } 9.05/3.23 ], 9.05/3.23 "type": "Graph" 9.05/3.23 } 9.05/3.23 } 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (60) 9.05/3.23 Complex Obligation (AND) 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (61) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f164_out -> f158_out(T17) :|: TRUE 9.05/3.23 f158_in(.(T40, T41)) -> f163_in(T41) :|: TRUE 9.05/3.23 f158_in(x) -> f164_in :|: TRUE 9.05/3.23 f163_out(x1) -> f158_out(.(x2, x1)) :|: TRUE 9.05/3.23 f163_in(x3) -> f86_in(x3) :|: TRUE 9.05/3.23 f86_out(x4) -> f163_out(x4) :|: TRUE 9.05/3.23 f153_out(x5) -> f86_out(x5) :|: TRUE 9.05/3.23 f86_in(x6) -> f153_in(x6) :|: TRUE 9.05/3.23 f153_in(x7) -> f160_in(x7) :|: TRUE 9.05/3.23 f160_out(x8) -> f153_out(x8) :|: TRUE 9.05/3.23 f153_in(x9) -> f158_in(x9) :|: TRUE 9.05/3.23 f158_out(x10) -> f153_out(x10) :|: TRUE 9.05/3.23 f12_out(T2) -> f11_out(T2) :|: TRUE 9.05/3.23 f11_in(x11) -> f12_in(x11) :|: TRUE 9.05/3.23 f12_in(x12) -> f23_in(x12) :|: TRUE 9.05/3.23 f23_out(x13) -> f12_out(x13) :|: TRUE 9.05/3.23 f24_out(x14) -> f12_out(x14) :|: TRUE 9.05/3.23 f12_in(x15) -> f24_in(x15) :|: TRUE 9.05/3.23 f23_in(x16) -> f37_in :|: TRUE 9.05/3.23 f37_out -> f23_out(x17) :|: TRUE 9.05/3.23 f36_out(x18) -> f23_out(x18) :|: TRUE 9.05/3.23 f23_in(x19) -> f36_in(x19) :|: TRUE 9.05/3.23 f87_out(x20) -> f36_out(x20) :|: TRUE 9.05/3.23 f36_in(x21) -> f86_in(x21) :|: TRUE 9.05/3.23 f86_out(x22) -> f87_in(x22) :|: TRUE 9.05/3.23 Start term: f11_in(T2) 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (62) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 9.05/3.23 Constructed simple dependency graph. 9.05/3.23 9.05/3.23 Simplified to the following IRSwTs: 9.05/3.23 9.05/3.23 intTRSProblem: 9.05/3.23 f158_in(.(T40, T41)) -> f163_in(T41) :|: TRUE 9.05/3.23 f163_in(x3) -> f86_in(x3) :|: TRUE 9.05/3.23 f86_in(x6) -> f153_in(x6) :|: TRUE 9.05/3.23 f153_in(x9) -> f158_in(x9) :|: TRUE 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (63) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f158_in(.(T40, T41)) -> f163_in(T41) :|: TRUE 9.05/3.23 f163_in(x3) -> f86_in(x3) :|: TRUE 9.05/3.23 f86_in(x6) -> f153_in(x6) :|: TRUE 9.05/3.23 f153_in(x9) -> f158_in(x9) :|: TRUE 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (64) IntTRSCompressionProof (EQUIVALENT) 9.05/3.23 Compressed rules. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (65) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f158_in(.(T40:0, T41:0)) -> f158_in(T41:0) :|: TRUE 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (66) IRSFormatTransformerProof (EQUIVALENT) 9.05/3.23 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (67) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f158_in(.(T40:0, T41:0)) -> f158_in(T41:0) :|: TRUE 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (68) IRSwTTerminationDigraphProof (EQUIVALENT) 9.05/3.23 Constructed termination digraph! 9.05/3.23 Nodes: 9.05/3.23 (1) f158_in(.(T40:0, T41:0)) -> f158_in(T41:0) :|: TRUE 9.05/3.23 9.05/3.23 Arcs: 9.05/3.23 (1) -> (1) 9.05/3.23 9.05/3.23 This digraph is fully evaluated! 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (69) 9.05/3.23 Obligation: 9.05/3.23 9.05/3.23 Termination digraph: 9.05/3.23 Nodes: 9.05/3.23 (1) f158_in(.(T40:0, T41:0)) -> f158_in(T41:0) :|: TRUE 9.05/3.23 9.05/3.23 Arcs: 9.05/3.23 (1) -> (1) 9.05/3.23 9.05/3.23 This digraph is fully evaluated! 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (70) IntTRSUnneededArgumentFilterProof (EQUIVALENT) 9.05/3.23 Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: 9.05/3.23 9.05/3.23 .(x1, x2) -> .(x2) 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (71) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f158_in(.(T41:0)) -> f158_in(T41:0) :|: TRUE 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (72) TempFilterProof (SOUND) 9.05/3.23 Used the following sort dictionary for filtering: 9.05/3.23 f158_in(VARIABLE) 9.05/3.23 .(VARIABLE) 9.05/3.23 Removed predefined arithmetic. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (73) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f158_in(.(T41:0)) -> f158_in(T41:0) 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (74) IRSwTToQDPProof (SOUND) 9.05/3.23 Removed the integers and created a QDP-Problem. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (75) 9.05/3.23 Obligation: 9.05/3.23 Q DP problem: 9.05/3.23 The TRS P consists of the following rules: 9.05/3.23 9.05/3.23 f158_in(.(T41:0)) -> f158_in(T41:0) 9.05/3.23 9.05/3.23 R is empty. 9.05/3.23 Q is empty. 9.05/3.23 We have to consider all (P,Q,R)-chains. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (76) QDPSizeChangeProof (EQUIVALENT) 9.05/3.23 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. 9.05/3.23 9.05/3.23 From the DPs we obtained the following set of size-change graphs: 9.05/3.23 *f158_in(.(T41:0)) -> f158_in(T41:0) 9.05/3.23 The graph contains the following edges 1 > 1 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (77) 9.05/3.23 YES 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (78) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f164_out -> f158_out(T17) :|: TRUE 9.05/3.23 f158_in(.(T40, T41)) -> f163_in(T41) :|: TRUE 9.05/3.23 f158_in(x) -> f164_in :|: TRUE 9.05/3.23 f163_out(x1) -> f158_out(.(x2, x1)) :|: TRUE 9.05/3.23 f12_in(T2) -> f23_in(T2) :|: TRUE 9.05/3.23 f23_out(x3) -> f12_out(x3) :|: TRUE 9.05/3.23 f24_out(x4) -> f12_out(x4) :|: TRUE 9.05/3.23 f12_in(x5) -> f24_in(x5) :|: TRUE 9.05/3.23 f160_in(.(T50, T51)) -> f173_in :|: TRUE 9.05/3.23 f173_out -> f160_out(.(x6, x7)) :|: TRUE 9.05/3.23 f175_out -> f160_out(x8) :|: TRUE 9.05/3.23 f160_in(x9) -> f175_in :|: TRUE 9.05/3.23 f87_in(x10) -> f11_in(x10) :|: TRUE 9.05/3.23 f11_out(x11) -> f87_out(x11) :|: TRUE 9.05/3.23 f153_out(x12) -> f86_out(x12) :|: TRUE 9.05/3.23 f86_in(x13) -> f153_in(x13) :|: TRUE 9.05/3.23 f12_out(x14) -> f11_out(x14) :|: TRUE 9.05/3.23 f11_in(x15) -> f12_in(x15) :|: TRUE 9.05/3.23 f173_in -> f173_out :|: TRUE 9.05/3.23 f87_out(x16) -> f36_out(x16) :|: TRUE 9.05/3.23 f36_in(x17) -> f86_in(x17) :|: TRUE 9.05/3.23 f86_out(x18) -> f87_in(x18) :|: TRUE 9.05/3.23 f23_in(x19) -> f37_in :|: TRUE 9.05/3.23 f37_out -> f23_out(x20) :|: TRUE 9.05/3.23 f36_out(x21) -> f23_out(x21) :|: TRUE 9.05/3.23 f23_in(x22) -> f36_in(x22) :|: TRUE 9.05/3.23 f163_in(x23) -> f86_in(x23) :|: TRUE 9.05/3.23 f86_out(x24) -> f163_out(x24) :|: TRUE 9.05/3.23 f153_in(x25) -> f160_in(x25) :|: TRUE 9.05/3.23 f160_out(x26) -> f153_out(x26) :|: TRUE 9.05/3.23 f153_in(x27) -> f158_in(x27) :|: TRUE 9.05/3.23 f158_out(x28) -> f153_out(x28) :|: TRUE 9.05/3.23 Start term: f11_in(T2) 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (79) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 9.05/3.23 Constructed simple dependency graph. 9.05/3.23 9.05/3.23 Simplified to the following IRSwTs: 9.05/3.23 9.05/3.23 intTRSProblem: 9.05/3.23 f158_in(.(T40, T41)) -> f163_in(T41) :|: TRUE 9.05/3.23 f163_out(x1) -> f158_out(.(x2, x1)) :|: TRUE 9.05/3.23 f12_in(T2) -> f23_in(T2) :|: TRUE 9.05/3.23 f160_in(.(T50, T51)) -> f173_in :|: TRUE 9.05/3.23 f173_out -> f160_out(.(x6, x7)) :|: TRUE 9.05/3.23 f87_in(x10) -> f11_in(x10) :|: TRUE 9.05/3.23 f153_out(x12) -> f86_out(x12) :|: TRUE 9.05/3.23 f86_in(x13) -> f153_in(x13) :|: TRUE 9.05/3.23 f11_in(x15) -> f12_in(x15) :|: TRUE 9.05/3.23 f173_in -> f173_out :|: TRUE 9.05/3.23 f36_in(x17) -> f86_in(x17) :|: TRUE 9.05/3.23 f86_out(x18) -> f87_in(x18) :|: TRUE 9.05/3.23 f23_in(x22) -> f36_in(x22) :|: TRUE 9.05/3.23 f163_in(x23) -> f86_in(x23) :|: TRUE 9.05/3.23 f86_out(x24) -> f163_out(x24) :|: TRUE 9.05/3.23 f153_in(x25) -> f160_in(x25) :|: TRUE 9.05/3.23 f160_out(x26) -> f153_out(x26) :|: TRUE 9.05/3.23 f153_in(x27) -> f158_in(x27) :|: TRUE 9.05/3.23 f158_out(x28) -> f153_out(x28) :|: TRUE 9.05/3.23 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (80) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f158_in(.(T40, T41)) -> f163_in(T41) :|: TRUE 9.05/3.23 f163_out(x1) -> f158_out(.(x2, x1)) :|: TRUE 9.05/3.23 f12_in(T2) -> f23_in(T2) :|: TRUE 9.05/3.23 f160_in(.(T50, T51)) -> f173_in :|: TRUE 9.05/3.23 f173_out -> f160_out(.(x6, x7)) :|: TRUE 9.05/3.23 f87_in(x10) -> f11_in(x10) :|: TRUE 9.05/3.23 f153_out(x12) -> f86_out(x12) :|: TRUE 9.05/3.23 f86_in(x13) -> f153_in(x13) :|: TRUE 9.05/3.23 f11_in(x15) -> f12_in(x15) :|: TRUE 9.05/3.23 f173_in -> f173_out :|: TRUE 9.05/3.23 f36_in(x17) -> f86_in(x17) :|: TRUE 9.05/3.23 f86_out(x18) -> f87_in(x18) :|: TRUE 9.05/3.23 f23_in(x22) -> f36_in(x22) :|: TRUE 9.05/3.23 f163_in(x23) -> f86_in(x23) :|: TRUE 9.05/3.23 f86_out(x24) -> f163_out(x24) :|: TRUE 9.05/3.23 f153_in(x25) -> f160_in(x25) :|: TRUE 9.05/3.23 f160_out(x26) -> f153_out(x26) :|: TRUE 9.05/3.23 f153_in(x27) -> f158_in(x27) :|: TRUE 9.05/3.23 f158_out(x28) -> f153_out(x28) :|: TRUE 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (81) IntTRSCompressionProof (EQUIVALENT) 9.05/3.23 Compressed rules. 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (82) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f86_in(.(T50:0, T51:0)) -> f153_out(.(x6:0, x7:0)) :|: TRUE 9.05/3.23 f86_in(.(T40:0, T41:0)) -> f86_in(T41:0) :|: TRUE 9.05/3.23 f153_out(x12:0) -> f153_out(.(x2:0, x12:0)) :|: TRUE 9.05/3.23 f153_out(x) -> f86_in(x) :|: TRUE 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (83) IRSFormatTransformerProof (EQUIVALENT) 9.05/3.23 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (84) 9.05/3.23 Obligation: 9.05/3.23 Rules: 9.05/3.23 f86_in(.(T50:0, T51:0)) -> f153_out(.(x6:0, x7:0)) :|: TRUE 9.05/3.23 f86_in(.(T40:0, T41:0)) -> f86_in(T41:0) :|: TRUE 9.05/3.23 f153_out(x12:0) -> f153_out(.(x2:0, x12:0)) :|: TRUE 9.05/3.23 f153_out(x) -> f86_in(x) :|: TRUE 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (85) IRSwTTerminationDigraphProof (EQUIVALENT) 9.05/3.23 Constructed termination digraph! 9.05/3.23 Nodes: 9.05/3.23 (1) f86_in(.(T50:0, T51:0)) -> f153_out(.(x6:0, x7:0)) :|: TRUE 9.05/3.23 (2) f86_in(.(T40:0, T41:0)) -> f86_in(T41:0) :|: TRUE 9.05/3.23 (3) f153_out(x12:0) -> f153_out(.(x2:0, x12:0)) :|: TRUE 9.05/3.23 (4) f153_out(x) -> f86_in(x) :|: TRUE 9.05/3.23 9.05/3.23 Arcs: 9.05/3.23 (1) -> (3), (4) 9.05/3.23 (2) -> (1), (2) 9.05/3.23 (3) -> (3), (4) 9.05/3.23 (4) -> (1), (2) 9.05/3.23 9.05/3.23 This digraph is fully evaluated! 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (86) 9.05/3.23 Obligation: 9.05/3.23 9.05/3.23 Termination digraph: 9.05/3.23 Nodes: 9.05/3.23 (1) f86_in(.(T50:0, T51:0)) -> f153_out(.(x6:0, x7:0)) :|: TRUE 9.05/3.23 (2) f86_in(.(T40:0, T41:0)) -> f86_in(T41:0) :|: TRUE 9.05/3.23 (3) f153_out(x) -> f86_in(x) :|: TRUE 9.05/3.23 (4) f153_out(x12:0) -> f153_out(.(x2:0, x12:0)) :|: TRUE 9.05/3.23 9.05/3.23 Arcs: 9.05/3.23 (1) -> (3), (4) 9.05/3.23 (2) -> (1), (2) 9.05/3.23 (3) -> (1), (2) 9.05/3.23 (4) -> (3), (4) 9.05/3.23 9.05/3.23 This digraph is fully evaluated! 9.05/3.23 9.05/3.23 ---------------------------------------- 9.05/3.23 9.05/3.23 (87) PrologToDTProblemTransformerProof (SOUND) 9.05/3.23 Built DT problem from termination graph DT10. 9.05/3.23 9.05/3.23 { 9.05/3.23 "root": 2, 9.05/3.23 "program": { 9.05/3.23 "directives": [], 9.05/3.23 "clauses": [ 9.05/3.23 [ 9.05/3.23 "(member X (. Y Xs))", 9.05/3.23 "(member X Xs)" 9.05/3.23 ], 9.05/3.23 [ 9.05/3.23 "(member X (. X Xs))", 9.05/3.23 null 9.05/3.23 ], 9.05/3.23 [ 9.05/3.23 "(subset (. X Xs) Ys)", 9.05/3.23 "(',' (member X Ys) (subset Xs Ys))" 9.05/3.23 ], 9.05/3.23 [ 9.05/3.23 "(subset ([]) Ys)", 9.05/3.23 null 9.05/3.23 ] 9.05/3.23 ] 9.05/3.23 }, 9.05/3.23 "graph": { 9.05/3.23 "nodes": { 9.05/3.23 "27": { 9.05/3.23 "goal": [ 9.05/3.23 { 9.05/3.23 "clause": -1, 9.05/3.23 "scope": -1, 9.05/3.23 "term": "(',' (member T9 T8) (subset T10 T8))" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "clause": 3, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T8)" 9.05/3.23 } 9.05/3.23 ], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T8"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "28": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 3, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T2)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [[ 9.05/3.23 "(subset T1 T2)", 9.05/3.23 "(subset (. X4 X5) X6)" 9.05/3.23 ]], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T2"], 9.05/3.23 "free": [ 9.05/3.23 "X4", 9.05/3.23 "X5", 9.05/3.23 "X6" 9.05/3.23 ], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "29": { 9.05/3.23 "goal": [ 9.05/3.23 { 9.05/3.23 "clause": 0, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(',' (member T9 T8) (subset T10 T8))" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "clause": 1, 9.05/3.23 "scope": 2, 9.05/3.23 "term": "(',' (member T9 T8) (subset T10 T8))" 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "clause": -1, 9.05/3.23 "scope": 2, 9.05/3.23 "term": null 9.05/3.23 }, 9.05/3.23 { 9.05/3.23 "clause": 3, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T8)" 9.05/3.23 } 9.05/3.23 ], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T8"], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "190": { 9.05/3.23 "goal": [], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": [], 9.05/3.23 "free": [], 9.05/3.23 "exprvars": [] 9.05/3.23 } 9.05/3.23 }, 9.05/3.23 "191": { 9.05/3.23 "goal": [{ 9.05/3.23 "clause": 3, 9.05/3.23 "scope": 1, 9.05/3.23 "term": "(subset T1 T8)" 9.05/3.23 }], 9.05/3.23 "kb": { 9.05/3.23 "nonunifying": [], 9.05/3.23 "intvars": {}, 9.05/3.23 "arithmetic": { 9.05/3.23 "type": "PlainIntegerRelationState", 9.05/3.23 "relations": [] 9.05/3.23 }, 9.05/3.23 "ground": ["T8"], 9.05/3.23 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "192": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": -1, 9.05/3.24 "scope": -1, 9.05/3.24 "term": "(true)" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "193": { 9.05/3.24 "goal": [], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "type": "Nodes", 9.05/3.24 "194": { 9.05/3.24 "goal": [], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "195": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": -1, 9.05/3.24 "scope": -1, 9.05/3.24 "term": "(true)" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "196": { 9.05/3.24 "goal": [], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "197": { 9.05/3.24 "goal": [], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "111": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": -1, 9.05/3.24 "scope": -1, 9.05/3.24 "term": "(member T50 T49)" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T49"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "117": { 9.05/3.24 "goal": [], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "95": { 9.05/3.24 "goal": [ 9.05/3.24 { 9.05/3.24 "clause": 0, 9.05/3.24 "scope": 3, 9.05/3.24 "term": "(member T26 T25)" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "clause": 1, 9.05/3.24 "scope": 3, 9.05/3.24 "term": "(member T26 T25)" 9.05/3.24 } 9.05/3.24 ], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T25"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "30": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": 0, 9.05/3.24 "scope": 2, 9.05/3.24 "term": "(',' (member T9 T8) (subset T10 T8))" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T8"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "96": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": 0, 9.05/3.24 "scope": 3, 9.05/3.24 "term": "(member T26 T25)" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T25"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "31": { 9.05/3.24 "goal": [ 9.05/3.24 { 9.05/3.24 "clause": 1, 9.05/3.24 "scope": 2, 9.05/3.24 "term": "(',' (member T9 T8) (subset T10 T8))" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "clause": -1, 9.05/3.24 "scope": 2, 9.05/3.24 "term": null 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "clause": 3, 9.05/3.24 "scope": 1, 9.05/3.24 "term": "(subset T1 T8)" 9.05/3.24 } 9.05/3.24 ], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T8"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "97": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": 1, 9.05/3.24 "scope": 3, 9.05/3.24 "term": "(member T26 T25)" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T25"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "32": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": -1, 9.05/3.24 "scope": -1, 9.05/3.24 "term": "(',' (member T26 T25) (subset T27 (. T24 T25)))" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [ 9.05/3.24 "T24", 9.05/3.24 "T25" 9.05/3.24 ], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "33": { 9.05/3.24 "goal": [], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "13": { 9.05/3.24 "goal": [ 9.05/3.24 { 9.05/3.24 "clause": 2, 9.05/3.24 "scope": 1, 9.05/3.24 "term": "(subset T1 T2)" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "clause": 3, 9.05/3.24 "scope": 1, 9.05/3.24 "term": "(subset T1 T2)" 9.05/3.24 } 9.05/3.24 ], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T2"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "184": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": -1, 9.05/3.24 "scope": -1, 9.05/3.24 "term": "(true)" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "185": { 9.05/3.24 "goal": [], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "186": { 9.05/3.24 "goal": [], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "187": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": 1, 9.05/3.24 "scope": 2, 9.05/3.24 "term": "(',' (member T9 T8) (subset T10 T8))" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T8"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "188": { 9.05/3.24 "goal": [ 9.05/3.24 { 9.05/3.24 "clause": -1, 9.05/3.24 "scope": 2, 9.05/3.24 "term": null 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "clause": 3, 9.05/3.24 "scope": 1, 9.05/3.24 "term": "(subset T1 T8)" 9.05/3.24 } 9.05/3.24 ], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T8"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "2": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": -1, 9.05/3.24 "scope": -1, 9.05/3.24 "term": "(subset T1 T2)" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T2"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "189": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": -1, 9.05/3.24 "scope": -1, 9.05/3.24 "term": "(subset T74 (. T72 T73))" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [ 9.05/3.24 "T72", 9.05/3.24 "T73" 9.05/3.24 ], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "83": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": -1, 9.05/3.24 "scope": -1, 9.05/3.24 "term": "(member T26 T25)" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": ["T25"], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "85": { 9.05/3.24 "goal": [{ 9.05/3.24 "clause": -1, 9.05/3.24 "scope": -1, 9.05/3.24 "term": "(subset T31 (. T24 T25))" 9.05/3.24 }], 9.05/3.24 "kb": { 9.05/3.24 "nonunifying": [], 9.05/3.24 "intvars": {}, 9.05/3.24 "arithmetic": { 9.05/3.24 "type": "PlainIntegerRelationState", 9.05/3.24 "relations": [] 9.05/3.24 }, 9.05/3.24 "ground": [ 9.05/3.24 "T24", 9.05/3.24 "T25" 9.05/3.24 ], 9.05/3.24 "free": [], 9.05/3.24 "exprvars": [] 9.05/3.24 } 9.05/3.24 } 9.05/3.24 }, 9.05/3.24 "edges": [ 9.05/3.24 { 9.05/3.24 "from": 2, 9.05/3.24 "to": 13, 9.05/3.24 "label": "CASE" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 13, 9.05/3.24 "to": 27, 9.05/3.24 "label": "EVAL with clause\nsubset(.(X4, X5), X6) :- ','(member(X4, X6), subset(X5, X6)).\nand substitutionX4 -> T9,\nX5 -> T10,\nT1 -> .(T9, T10),\nT2 -> T8,\nX6 -> T8,\nT6 -> T9,\nT7 -> T10" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 13, 9.05/3.24 "to": 28, 9.05/3.24 "label": "EVAL-BACKTRACK" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 27, 9.05/3.24 "to": 29, 9.05/3.24 "label": "CASE" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 28, 9.05/3.24 "to": 195, 9.05/3.24 "label": "EVAL with clause\nsubset([], X72).\nand substitutionT1 -> [],\nT2 -> T83,\nX72 -> T83" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 28, 9.05/3.24 "to": 196, 9.05/3.24 "label": "EVAL-BACKTRACK" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 29, 9.05/3.24 "to": 30, 9.05/3.24 "label": "PARALLEL" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 29, 9.05/3.24 "to": 31, 9.05/3.24 "label": "PARALLEL" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 30, 9.05/3.24 "to": 32, 9.05/3.24 "label": "EVAL with clause\nmember(X19, .(X20, X21)) :- member(X19, X21).\nand substitutionT9 -> T26,\nX19 -> T26,\nX20 -> T24,\nX21 -> T25,\nT8 -> .(T24, T25),\nT23 -> T26,\nT10 -> T27" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 30, 9.05/3.24 "to": 33, 9.05/3.24 "label": "EVAL-BACKTRACK" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 31, 9.05/3.24 "to": 187, 9.05/3.24 "label": "PARALLEL" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 31, 9.05/3.24 "to": 188, 9.05/3.24 "label": "PARALLEL" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 32, 9.05/3.24 "to": 83, 9.05/3.24 "label": "SPLIT 1" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 32, 9.05/3.24 "to": 85, 9.05/3.24 "label": "SPLIT 2\nnew knowledge:\nT26 is ground\nT25 is ground\nreplacements:T27 -> T31" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 83, 9.05/3.24 "to": 95, 9.05/3.24 "label": "CASE" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 85, 9.05/3.24 "to": 2, 9.05/3.24 "label": "INSTANCE with matching:\nT1 -> T31\nT2 -> .(T24, T25)" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 95, 9.05/3.24 "to": 96, 9.05/3.24 "label": "PARALLEL" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 95, 9.05/3.24 "to": 97, 9.05/3.24 "label": "PARALLEL" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 96, 9.05/3.24 "to": 111, 9.05/3.24 "label": "EVAL with clause\nmember(X40, .(X41, X42)) :- member(X40, X42).\nand substitutionT26 -> T50,\nX40 -> T50,\nX41 -> T48,\nX42 -> T49,\nT25 -> .(T48, T49),\nT47 -> T50" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 96, 9.05/3.24 "to": 117, 9.05/3.24 "label": "EVAL-BACKTRACK" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 97, 9.05/3.24 "to": 184, 9.05/3.24 "label": "EVAL with clause\nmember(X50, .(X50, X51)).\nand substitutionT26 -> T58,\nX50 -> T58,\nX51 -> T59,\nT25 -> .(T58, T59)" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 97, 9.05/3.24 "to": 185, 9.05/3.24 "label": "EVAL-BACKTRACK" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 111, 9.05/3.24 "to": 83, 9.05/3.24 "label": "INSTANCE with matching:\nT26 -> T50\nT25 -> T49" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 184, 9.05/3.24 "to": 186, 9.05/3.24 "label": "SUCCESS" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 187, 9.05/3.24 "to": 189, 9.05/3.24 "label": "EVAL with clause\nmember(X63, .(X63, X64)).\nand substitutionT9 -> T72,\nX63 -> T72,\nX64 -> T73,\nT8 -> .(T72, T73),\nT10 -> T74" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 187, 9.05/3.24 "to": 190, 9.05/3.24 "label": "EVAL-BACKTRACK" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 188, 9.05/3.24 "to": 191, 9.05/3.24 "label": "FAILURE" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 189, 9.05/3.24 "to": 2, 9.05/3.24 "label": "INSTANCE with matching:\nT1 -> T74\nT2 -> .(T72, T73)" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 191, 9.05/3.24 "to": 192, 9.05/3.24 "label": "EVAL with clause\nsubset([], X70).\nand substitutionT1 -> [],\nT8 -> T81,\nX70 -> T81" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 191, 9.05/3.24 "to": 193, 9.05/3.24 "label": "EVAL-BACKTRACK" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 192, 9.05/3.24 "to": 194, 9.05/3.24 "label": "SUCCESS" 9.05/3.24 }, 9.05/3.24 { 9.05/3.24 "from": 195, 9.05/3.24 "to": 197, 9.05/3.24 "label": "SUCCESS" 9.05/3.24 } 9.05/3.24 ], 9.05/3.24 "type": "Graph" 9.05/3.24 } 9.05/3.24 } 9.05/3.24 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (88) 9.05/3.24 Obligation: 9.05/3.24 Triples: 9.05/3.24 9.05/3.24 memberB(X1, .(X2, X3)) :- memberB(X1, X3). 9.05/3.24 subsetA(.(X1, X2), .(X3, X4)) :- memberB(X1, X4). 9.05/3.24 subsetA(.(X1, X2), .(X3, X4)) :- ','(membercB(X1, X4), subsetA(X2, .(X3, X4))). 9.05/3.24 subsetA(.(X1, X2), .(X1, X3)) :- subsetA(X2, .(X1, X3)). 9.05/3.24 9.05/3.24 Clauses: 9.05/3.24 9.05/3.24 subsetcA(.(X1, X2), .(X3, X4)) :- ','(membercB(X1, X4), subsetcA(X2, .(X3, X4))). 9.05/3.24 subsetcA(.(X1, X2), .(X1, X3)) :- subsetcA(X2, .(X1, X3)). 9.05/3.24 subsetcA([], X1). 9.05/3.24 subsetcA([], X1). 9.05/3.24 membercB(X1, .(X2, X3)) :- membercB(X1, X3). 9.05/3.24 membercB(X1, .(X1, X2)). 9.05/3.24 9.05/3.24 Afs: 9.05/3.24 9.05/3.24 subsetA(x1, x2) = subsetA(x2) 9.05/3.24 9.05/3.24 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (89) TriplesToPiDPProof (SOUND) 9.05/3.24 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 9.05/3.24 9.05/3.24 subsetA_in_2: (f,b) 9.05/3.24 9.05/3.24 memberB_in_2: (f,b) 9.05/3.24 9.05/3.24 membercB_in_2: (f,b) 9.05/3.24 9.05/3.24 Transforming TRIPLES into the following Term Rewriting System: 9.05/3.24 9.05/3.24 Pi DP problem: 9.05/3.24 The TRS P consists of the following rules: 9.05/3.24 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X3, X4)) -> U2_AG(X1, X2, X3, X4, memberB_in_ag(X1, X4)) 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X3, X4)) -> MEMBERB_IN_AG(X1, X4) 9.05/3.24 MEMBERB_IN_AG(X1, .(X2, X3)) -> U1_AG(X1, X2, X3, memberB_in_ag(X1, X3)) 9.05/3.24 MEMBERB_IN_AG(X1, .(X2, X3)) -> MEMBERB_IN_AG(X1, X3) 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X3, X4)) -> U3_AG(X1, X2, X3, X4, membercB_in_ag(X1, X4)) 9.05/3.24 U3_AG(X1, X2, X3, X4, membercB_out_ag(X1, X4)) -> U4_AG(X1, X2, X3, X4, subsetA_in_ag(X2, .(X3, X4))) 9.05/3.24 U3_AG(X1, X2, X3, X4, membercB_out_ag(X1, X4)) -> SUBSETA_IN_AG(X2, .(X3, X4)) 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X1, X3)) -> U5_AG(X1, X2, X3, subsetA_in_ag(X2, .(X1, X3))) 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X1, X3)) -> SUBSETA_IN_AG(X2, .(X1, X3)) 9.05/3.24 9.05/3.24 The TRS R consists of the following rules: 9.05/3.24 9.05/3.24 membercB_in_ag(X1, .(X2, X3)) -> U10_ag(X1, X2, X3, membercB_in_ag(X1, X3)) 9.05/3.24 membercB_in_ag(X1, .(X1, X2)) -> membercB_out_ag(X1, .(X1, X2)) 9.05/3.24 U10_ag(X1, X2, X3, membercB_out_ag(X1, X3)) -> membercB_out_ag(X1, .(X2, X3)) 9.05/3.24 9.05/3.24 The argument filtering Pi contains the following mapping: 9.05/3.24 subsetA_in_ag(x1, x2) = subsetA_in_ag(x2) 9.05/3.24 9.05/3.24 .(x1, x2) = .(x1, x2) 9.05/3.24 9.05/3.24 memberB_in_ag(x1, x2) = memberB_in_ag(x2) 9.05/3.24 9.05/3.24 membercB_in_ag(x1, x2) = membercB_in_ag(x2) 9.05/3.24 9.05/3.24 U10_ag(x1, x2, x3, x4) = U10_ag(x2, x3, x4) 9.05/3.24 9.05/3.24 membercB_out_ag(x1, x2) = membercB_out_ag(x1, x2) 9.05/3.24 9.05/3.24 SUBSETA_IN_AG(x1, x2) = SUBSETA_IN_AG(x2) 9.05/3.24 9.05/3.24 U2_AG(x1, x2, x3, x4, x5) = U2_AG(x3, x4, x5) 9.05/3.24 9.05/3.24 MEMBERB_IN_AG(x1, x2) = MEMBERB_IN_AG(x2) 9.05/3.24 9.05/3.24 U1_AG(x1, x2, x3, x4) = U1_AG(x2, x3, x4) 9.05/3.24 9.05/3.24 U3_AG(x1, x2, x3, x4, x5) = U3_AG(x3, x4, x5) 9.05/3.24 9.05/3.24 U4_AG(x1, x2, x3, x4, x5) = U4_AG(x3, x4, x5) 9.05/3.24 9.05/3.24 U5_AG(x1, x2, x3, x4) = U5_AG(x1, x3, x4) 9.05/3.24 9.05/3.24 9.05/3.24 We have to consider all (P,R,Pi)-chains 9.05/3.24 9.05/3.24 9.05/3.24 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 9.05/3.24 9.05/3.24 9.05/3.24 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (90) 9.05/3.24 Obligation: 9.05/3.24 Pi DP problem: 9.05/3.24 The TRS P consists of the following rules: 9.05/3.24 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X3, X4)) -> U2_AG(X1, X2, X3, X4, memberB_in_ag(X1, X4)) 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X3, X4)) -> MEMBERB_IN_AG(X1, X4) 9.05/3.24 MEMBERB_IN_AG(X1, .(X2, X3)) -> U1_AG(X1, X2, X3, memberB_in_ag(X1, X3)) 9.05/3.24 MEMBERB_IN_AG(X1, .(X2, X3)) -> MEMBERB_IN_AG(X1, X3) 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X3, X4)) -> U3_AG(X1, X2, X3, X4, membercB_in_ag(X1, X4)) 9.05/3.24 U3_AG(X1, X2, X3, X4, membercB_out_ag(X1, X4)) -> U4_AG(X1, X2, X3, X4, subsetA_in_ag(X2, .(X3, X4))) 9.05/3.24 U3_AG(X1, X2, X3, X4, membercB_out_ag(X1, X4)) -> SUBSETA_IN_AG(X2, .(X3, X4)) 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X1, X3)) -> U5_AG(X1, X2, X3, subsetA_in_ag(X2, .(X1, X3))) 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X1, X3)) -> SUBSETA_IN_AG(X2, .(X1, X3)) 9.05/3.24 9.05/3.24 The TRS R consists of the following rules: 9.05/3.24 9.05/3.24 membercB_in_ag(X1, .(X2, X3)) -> U10_ag(X1, X2, X3, membercB_in_ag(X1, X3)) 9.05/3.24 membercB_in_ag(X1, .(X1, X2)) -> membercB_out_ag(X1, .(X1, X2)) 9.05/3.24 U10_ag(X1, X2, X3, membercB_out_ag(X1, X3)) -> membercB_out_ag(X1, .(X2, X3)) 9.05/3.24 9.05/3.24 The argument filtering Pi contains the following mapping: 9.05/3.24 subsetA_in_ag(x1, x2) = subsetA_in_ag(x2) 9.05/3.24 9.05/3.24 .(x1, x2) = .(x1, x2) 9.05/3.24 9.05/3.24 memberB_in_ag(x1, x2) = memberB_in_ag(x2) 9.05/3.24 9.05/3.24 membercB_in_ag(x1, x2) = membercB_in_ag(x2) 9.05/3.24 9.05/3.24 U10_ag(x1, x2, x3, x4) = U10_ag(x2, x3, x4) 9.05/3.24 9.05/3.24 membercB_out_ag(x1, x2) = membercB_out_ag(x1, x2) 9.05/3.24 9.05/3.24 SUBSETA_IN_AG(x1, x2) = SUBSETA_IN_AG(x2) 9.05/3.24 9.05/3.24 U2_AG(x1, x2, x3, x4, x5) = U2_AG(x3, x4, x5) 9.05/3.24 9.05/3.24 MEMBERB_IN_AG(x1, x2) = MEMBERB_IN_AG(x2) 9.05/3.24 9.05/3.24 U1_AG(x1, x2, x3, x4) = U1_AG(x2, x3, x4) 9.05/3.24 9.05/3.24 U3_AG(x1, x2, x3, x4, x5) = U3_AG(x3, x4, x5) 9.05/3.24 9.05/3.24 U4_AG(x1, x2, x3, x4, x5) = U4_AG(x3, x4, x5) 9.05/3.24 9.05/3.24 U5_AG(x1, x2, x3, x4) = U5_AG(x1, x3, x4) 9.05/3.24 9.05/3.24 9.05/3.24 We have to consider all (P,R,Pi)-chains 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (91) DependencyGraphProof (EQUIVALENT) 9.05/3.24 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 5 less nodes. 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (92) 9.05/3.24 Complex Obligation (AND) 9.05/3.24 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (93) 9.05/3.24 Obligation: 9.05/3.24 Pi DP problem: 9.05/3.24 The TRS P consists of the following rules: 9.05/3.24 9.05/3.24 MEMBERB_IN_AG(X1, .(X2, X3)) -> MEMBERB_IN_AG(X1, X3) 9.05/3.24 9.05/3.24 The TRS R consists of the following rules: 9.05/3.24 9.05/3.24 membercB_in_ag(X1, .(X2, X3)) -> U10_ag(X1, X2, X3, membercB_in_ag(X1, X3)) 9.05/3.24 membercB_in_ag(X1, .(X1, X2)) -> membercB_out_ag(X1, .(X1, X2)) 9.05/3.24 U10_ag(X1, X2, X3, membercB_out_ag(X1, X3)) -> membercB_out_ag(X1, .(X2, X3)) 9.05/3.24 9.05/3.24 The argument filtering Pi contains the following mapping: 9.05/3.24 .(x1, x2) = .(x1, x2) 9.05/3.24 9.05/3.24 membercB_in_ag(x1, x2) = membercB_in_ag(x2) 9.05/3.24 9.05/3.24 U10_ag(x1, x2, x3, x4) = U10_ag(x2, x3, x4) 9.05/3.24 9.05/3.24 membercB_out_ag(x1, x2) = membercB_out_ag(x1, x2) 9.05/3.24 9.05/3.24 MEMBERB_IN_AG(x1, x2) = MEMBERB_IN_AG(x2) 9.05/3.24 9.05/3.24 9.05/3.24 We have to consider all (P,R,Pi)-chains 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (94) UsableRulesProof (EQUIVALENT) 9.05/3.24 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (95) 9.05/3.24 Obligation: 9.05/3.24 Pi DP problem: 9.05/3.24 The TRS P consists of the following rules: 9.05/3.24 9.05/3.24 MEMBERB_IN_AG(X1, .(X2, X3)) -> MEMBERB_IN_AG(X1, X3) 9.05/3.24 9.05/3.24 R is empty. 9.05/3.24 The argument filtering Pi contains the following mapping: 9.05/3.24 .(x1, x2) = .(x1, x2) 9.05/3.24 9.05/3.24 MEMBERB_IN_AG(x1, x2) = MEMBERB_IN_AG(x2) 9.05/3.24 9.05/3.24 9.05/3.24 We have to consider all (P,R,Pi)-chains 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (96) PiDPToQDPProof (SOUND) 9.05/3.24 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (97) 9.05/3.24 Obligation: 9.05/3.24 Q DP problem: 9.05/3.24 The TRS P consists of the following rules: 9.05/3.24 9.05/3.24 MEMBERB_IN_AG(.(X2, X3)) -> MEMBERB_IN_AG(X3) 9.05/3.24 9.05/3.24 R is empty. 9.05/3.24 Q is empty. 9.05/3.24 We have to consider all (P,Q,R)-chains. 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (98) QDPSizeChangeProof (EQUIVALENT) 9.05/3.24 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. 9.05/3.24 9.05/3.24 From the DPs we obtained the following set of size-change graphs: 9.05/3.24 *MEMBERB_IN_AG(.(X2, X3)) -> MEMBERB_IN_AG(X3) 9.05/3.24 The graph contains the following edges 1 > 1 9.05/3.24 9.05/3.24 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (99) 9.05/3.24 YES 9.05/3.24 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (100) 9.05/3.24 Obligation: 9.05/3.24 Pi DP problem: 9.05/3.24 The TRS P consists of the following rules: 9.05/3.24 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X3, X4)) -> U3_AG(X1, X2, X3, X4, membercB_in_ag(X1, X4)) 9.05/3.24 U3_AG(X1, X2, X3, X4, membercB_out_ag(X1, X4)) -> SUBSETA_IN_AG(X2, .(X3, X4)) 9.05/3.24 SUBSETA_IN_AG(.(X1, X2), .(X1, X3)) -> SUBSETA_IN_AG(X2, .(X1, X3)) 9.05/3.24 9.05/3.24 The TRS R consists of the following rules: 9.05/3.24 9.05/3.24 membercB_in_ag(X1, .(X2, X3)) -> U10_ag(X1, X2, X3, membercB_in_ag(X1, X3)) 9.05/3.24 membercB_in_ag(X1, .(X1, X2)) -> membercB_out_ag(X1, .(X1, X2)) 9.05/3.24 U10_ag(X1, X2, X3, membercB_out_ag(X1, X3)) -> membercB_out_ag(X1, .(X2, X3)) 9.05/3.24 9.05/3.24 The argument filtering Pi contains the following mapping: 9.05/3.24 .(x1, x2) = .(x1, x2) 9.05/3.24 9.05/3.24 membercB_in_ag(x1, x2) = membercB_in_ag(x2) 9.05/3.24 9.05/3.24 U10_ag(x1, x2, x3, x4) = U10_ag(x2, x3, x4) 9.05/3.24 9.05/3.24 membercB_out_ag(x1, x2) = membercB_out_ag(x1, x2) 9.05/3.24 9.05/3.24 SUBSETA_IN_AG(x1, x2) = SUBSETA_IN_AG(x2) 9.05/3.24 9.05/3.24 U3_AG(x1, x2, x3, x4, x5) = U3_AG(x3, x4, x5) 9.05/3.24 9.05/3.24 9.05/3.24 We have to consider all (P,R,Pi)-chains 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (101) PiDPToQDPProof (SOUND) 9.05/3.24 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (102) 9.05/3.24 Obligation: 9.05/3.24 Q DP problem: 9.05/3.24 The TRS P consists of the following rules: 9.05/3.24 9.05/3.24 SUBSETA_IN_AG(.(X3, X4)) -> U3_AG(X3, X4, membercB_in_ag(X4)) 9.05/3.24 U3_AG(X3, X4, membercB_out_ag(X1, X4)) -> SUBSETA_IN_AG(.(X3, X4)) 9.05/3.24 SUBSETA_IN_AG(.(X1, X3)) -> SUBSETA_IN_AG(.(X1, X3)) 9.05/3.24 9.05/3.24 The TRS R consists of the following rules: 9.05/3.24 9.05/3.24 membercB_in_ag(.(X2, X3)) -> U10_ag(X2, X3, membercB_in_ag(X3)) 9.05/3.24 membercB_in_ag(.(X1, X2)) -> membercB_out_ag(X1, .(X1, X2)) 9.05/3.24 U10_ag(X2, X3, membercB_out_ag(X1, X3)) -> membercB_out_ag(X1, .(X2, X3)) 9.05/3.24 9.05/3.24 The set Q consists of the following terms: 9.05/3.24 9.05/3.24 membercB_in_ag(x0) 9.05/3.24 U10_ag(x0, x1, x2) 9.05/3.24 9.05/3.24 We have to consider all (P,Q,R)-chains. 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (103) TransformationProof (SOUND) 9.05/3.24 By narrowing [LPAR04] the rule SUBSETA_IN_AG(.(X3, X4)) -> U3_AG(X3, X4, membercB_in_ag(X4)) at position [2] we obtained the following new rules [LPAR04]: 9.05/3.24 9.05/3.24 (SUBSETA_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), U10_ag(x0, x1, membercB_in_ag(x1))),SUBSETA_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), U10_ag(x0, x1, membercB_in_ag(x1)))) 9.05/3.24 (SUBSETA_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), membercB_out_ag(x0, .(x0, x1))),SUBSETA_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), membercB_out_ag(x0, .(x0, x1)))) 9.05/3.24 9.05/3.24 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (104) 9.05/3.24 Obligation: 9.05/3.24 Q DP problem: 9.05/3.24 The TRS P consists of the following rules: 9.05/3.24 9.05/3.24 U3_AG(X3, X4, membercB_out_ag(X1, X4)) -> SUBSETA_IN_AG(.(X3, X4)) 9.05/3.24 SUBSETA_IN_AG(.(X1, X3)) -> SUBSETA_IN_AG(.(X1, X3)) 9.05/3.24 SUBSETA_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), U10_ag(x0, x1, membercB_in_ag(x1))) 9.05/3.24 SUBSETA_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), membercB_out_ag(x0, .(x0, x1))) 9.05/3.24 9.05/3.24 The TRS R consists of the following rules: 9.05/3.24 9.05/3.24 membercB_in_ag(.(X2, X3)) -> U10_ag(X2, X3, membercB_in_ag(X3)) 9.05/3.24 membercB_in_ag(.(X1, X2)) -> membercB_out_ag(X1, .(X1, X2)) 9.05/3.24 U10_ag(X2, X3, membercB_out_ag(X1, X3)) -> membercB_out_ag(X1, .(X2, X3)) 9.05/3.24 9.05/3.24 The set Q consists of the following terms: 9.05/3.24 9.05/3.24 membercB_in_ag(x0) 9.05/3.24 U10_ag(x0, x1, x2) 9.05/3.24 9.05/3.24 We have to consider all (P,Q,R)-chains. 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (105) TransformationProof (EQUIVALENT) 9.05/3.24 By instantiating [LPAR04] the rule U3_AG(X3, X4, membercB_out_ag(X1, X4)) -> SUBSETA_IN_AG(.(X3, X4)) we obtained the following new rules [LPAR04]: 9.05/3.24 9.05/3.24 (U3_AG(z0, .(z1, z2), membercB_out_ag(x2, .(z1, z2))) -> SUBSETA_IN_AG(.(z0, .(z1, z2))),U3_AG(z0, .(z1, z2), membercB_out_ag(x2, .(z1, z2))) -> SUBSETA_IN_AG(.(z0, .(z1, z2)))) 9.05/3.24 (U3_AG(z0, .(z1, z2), membercB_out_ag(z1, .(z1, z2))) -> SUBSETA_IN_AG(.(z0, .(z1, z2))),U3_AG(z0, .(z1, z2), membercB_out_ag(z1, .(z1, z2))) -> SUBSETA_IN_AG(.(z0, .(z1, z2)))) 9.05/3.24 9.05/3.24 9.05/3.24 ---------------------------------------- 9.05/3.24 9.05/3.24 (106) 9.05/3.24 Obligation: 9.05/3.24 Q DP problem: 9.05/3.24 The TRS P consists of the following rules: 9.05/3.24 9.05/3.24 SUBSETA_IN_AG(.(X1, X3)) -> SUBSETA_IN_AG(.(X1, X3)) 9.05/3.24 SUBSETA_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), U10_ag(x0, x1, membercB_in_ag(x1))) 9.05/3.24 SUBSETA_IN_AG(.(y0, .(x0, x1))) -> U3_AG(y0, .(x0, x1), membercB_out_ag(x0, .(x0, x1))) 9.05/3.24 U3_AG(z0, .(z1, z2), membercB_out_ag(x2, .(z1, z2))) -> SUBSETA_IN_AG(.(z0, .(z1, z2))) 9.05/3.24 U3_AG(z0, .(z1, z2), membercB_out_ag(z1, .(z1, z2))) -> SUBSETA_IN_AG(.(z0, .(z1, z2))) 9.05/3.24 9.05/3.24 The TRS R consists of the following rules: 9.05/3.24 9.05/3.24 membercB_in_ag(.(X2, X3)) -> U10_ag(X2, X3, membercB_in_ag(X3)) 9.05/3.24 membercB_in_ag(.(X1, X2)) -> membercB_out_ag(X1, .(X1, X2)) 9.05/3.24 U10_ag(X2, X3, membercB_out_ag(X1, X3)) -> membercB_out_ag(X1, .(X2, X3)) 9.05/3.24 9.05/3.24 The set Q consists of the following terms: 9.05/3.24 9.05/3.24 membercB_in_ag(x0) 9.05/3.24 U10_ag(x0, x1, x2) 9.05/3.24 9.05/3.24 We have to consider all (P,Q,R)-chains. 9.18/3.27 EOF