7.36/2.85 MAYBE 7.36/2.86 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 7.36/2.86 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.36/2.86 7.36/2.86 7.36/2.86 Left Termination of the query pattern 7.36/2.86 7.36/2.86 subset(g,a) 7.36/2.86 7.36/2.86 w.r.t. the given Prolog program could not be shown: 7.36/2.86 7.36/2.86 (0) Prolog 7.36/2.86 (1) PrologToPiTRSProof [SOUND, 0 ms] 7.36/2.86 (2) PiTRS 7.36/2.86 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 7.36/2.86 (4) PiDP 7.36/2.86 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 7.36/2.86 (6) AND 7.36/2.86 (7) PiDP 7.36/2.86 (8) UsableRulesProof [EQUIVALENT, 0 ms] 7.36/2.86 (9) PiDP 7.36/2.86 (10) PiDPToQDPProof [SOUND, 0 ms] 7.36/2.86 (11) QDP 7.36/2.86 (12) NonTerminationLoopProof [COMPLETE, 5 ms] 7.36/2.86 (13) NO 7.36/2.86 (14) PiDP 7.36/2.86 (15) UsableRulesProof [EQUIVALENT, 0 ms] 7.36/2.86 (16) PiDP 7.36/2.86 (17) PrologToPiTRSProof [SOUND, 0 ms] 7.36/2.86 (18) PiTRS 7.36/2.86 (19) DependencyPairsProof [EQUIVALENT, 0 ms] 7.36/2.86 (20) PiDP 7.36/2.86 (21) DependencyGraphProof [EQUIVALENT, 0 ms] 7.36/2.86 (22) AND 7.36/2.86 (23) PiDP 7.36/2.86 (24) UsableRulesProof [EQUIVALENT, 0 ms] 7.36/2.86 (25) PiDP 7.36/2.86 (26) PiDPToQDPProof [SOUND, 0 ms] 7.36/2.86 (27) QDP 7.36/2.86 (28) NonTerminationLoopProof [COMPLETE, 1 ms] 7.36/2.86 (29) NO 7.36/2.86 (30) PiDP 7.36/2.86 (31) UsableRulesProof [EQUIVALENT, 0 ms] 7.36/2.86 (32) PiDP 7.36/2.86 (33) PrologToTRSTransformerProof [SOUND, 0 ms] 7.36/2.86 (34) QTRS 7.36/2.86 (35) DependencyPairsProof [EQUIVALENT, 0 ms] 7.36/2.86 (36) QDP 7.36/2.86 (37) DependencyGraphProof [EQUIVALENT, 0 ms] 7.36/2.86 (38) AND 7.36/2.86 (39) QDP 7.36/2.86 (40) MNOCProof [EQUIVALENT, 0 ms] 7.36/2.86 (41) QDP 7.36/2.86 (42) UsableRulesProof [EQUIVALENT, 0 ms] 7.36/2.86 (43) QDP 7.36/2.86 (44) QReductionProof [EQUIVALENT, 0 ms] 7.36/2.86 (45) QDP 7.36/2.86 (46) NonTerminationLoopProof [COMPLETE, 1 ms] 7.36/2.86 (47) NO 7.36/2.86 (48) QDP 7.36/2.86 (49) MNOCProof [EQUIVALENT, 0 ms] 7.36/2.86 (50) QDP 7.36/2.86 (51) UsableRulesProof [EQUIVALENT, 0 ms] 7.36/2.86 (52) QDP 7.36/2.86 (53) QReductionProof [EQUIVALENT, 0 ms] 7.36/2.86 (54) QDP 7.36/2.86 (55) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.36/2.87 (56) YES 7.36/2.87 (57) PrologToDTProblemTransformerProof [SOUND, 0 ms] 7.36/2.87 (58) TRIPLES 7.36/2.87 (59) TriplesToPiDPProof [SOUND, 0 ms] 7.36/2.87 (60) PiDP 7.36/2.87 (61) DependencyGraphProof [EQUIVALENT, 0 ms] 7.36/2.87 (62) AND 7.36/2.87 (63) PiDP 7.36/2.87 (64) UsableRulesProof [EQUIVALENT, 0 ms] 7.36/2.87 (65) PiDP 7.36/2.87 (66) PiDPToQDPProof [SOUND, 0 ms] 7.36/2.87 (67) QDP 7.36/2.87 (68) PiDP 7.36/2.87 (69) PrologToIRSwTTransformerProof [SOUND, 0 ms] 7.36/2.87 (70) AND 7.36/2.87 (71) IRSwT 7.36/2.87 (72) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 7.36/2.87 (73) IRSwT 7.36/2.87 (74) IntTRSCompressionProof [EQUIVALENT, 35 ms] 7.36/2.87 (75) IRSwT 7.36/2.87 (76) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 7.36/2.87 (77) IRSwT 7.36/2.87 (78) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] 7.36/2.87 (79) IRSwT 7.36/2.87 (80) FilterProof [EQUIVALENT, 0 ms] 7.36/2.87 (81) IntTRS 7.36/2.87 (82) IntTRSNonPeriodicNontermProof [COMPLETE, 8 ms] 7.36/2.87 (83) NO 7.36/2.87 (84) IRSwT 7.36/2.87 (85) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] 7.36/2.87 (86) IRSwT 7.36/2.87 (87) IntTRSCompressionProof [EQUIVALENT, 11 ms] 7.36/2.87 (88) IRSwT 7.36/2.87 (89) IRSFormatTransformerProof [EQUIVALENT, 0 ms] 7.36/2.87 (90) IRSwT 7.36/2.87 7.36/2.87 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (0) 7.36/2.87 Obligation: 7.36/2.87 Clauses: 7.36/2.87 7.36/2.87 subset([], X1). 7.36/2.87 subset(.(X, Xs), Ys) :- ','(member(X, Ys), subset(Xs, Ys)). 7.36/2.87 member(X, .(X, X2)). 7.36/2.87 member(X, .(X3, Xs)) :- member(X, Xs). 7.36/2.87 7.36/2.87 7.36/2.87 Query: subset(g,a) 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (1) PrologToPiTRSProof (SOUND) 7.36/2.87 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 7.36/2.87 7.36/2.87 subset_in_2: (b,f) 7.36/2.87 7.36/2.87 member_in_2: (b,f) 7.36/2.87 7.36/2.87 Transforming Prolog into the following Term Rewriting System: 7.36/2.87 7.36/2.87 Pi-finite rewrite system: 7.36/2.87 The TRS R consists of the following rules: 7.36/2.87 7.36/2.87 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.36/2.87 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.36/2.87 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.36/2.87 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.36/2.87 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.36/2.87 7.36/2.87 The argument filtering Pi contains the following mapping: 7.36/2.87 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.36/2.87 7.36/2.87 [] = [] 7.36/2.87 7.36/2.87 subset_out_ga(x1, x2) = subset_out_ga(x1) 7.36/2.87 7.36/2.87 .(x1, x2) = .(x1, x2) 7.36/2.87 7.36/2.87 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 member_in_ga(x1, x2) = member_in_ga(x1) 7.36/2.87 7.36/2.87 member_out_ga(x1, x2) = member_out_ga(x1) 7.36/2.87 7.36/2.87 U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) 7.36/2.87 7.36/2.87 U2_ga(x1, x2, x3, x4) = U2_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (2) 7.36/2.87 Obligation: 7.36/2.87 Pi-finite rewrite system: 7.36/2.87 The TRS R consists of the following rules: 7.36/2.87 7.36/2.87 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.36/2.87 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.36/2.87 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.36/2.87 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.36/2.87 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.36/2.87 7.36/2.87 The argument filtering Pi contains the following mapping: 7.36/2.87 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.36/2.87 7.36/2.87 [] = [] 7.36/2.87 7.36/2.87 subset_out_ga(x1, x2) = subset_out_ga(x1) 7.36/2.87 7.36/2.87 .(x1, x2) = .(x1, x2) 7.36/2.87 7.36/2.87 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 member_in_ga(x1, x2) = member_in_ga(x1) 7.36/2.87 7.36/2.87 member_out_ga(x1, x2) = member_out_ga(x1) 7.36/2.87 7.36/2.87 U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) 7.36/2.87 7.36/2.87 U2_ga(x1, x2, x3, x4) = U2_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (3) DependencyPairsProof (EQUIVALENT) 7.36/2.87 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 7.36/2.87 Pi DP problem: 7.36/2.87 The TRS P consists of the following rules: 7.36/2.87 7.36/2.87 SUBSET_IN_GA(.(X, Xs), Ys) -> U1_GA(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 SUBSET_IN_GA(.(X, Xs), Ys) -> MEMBER_IN_GA(X, Ys) 7.36/2.87 MEMBER_IN_GA(X, .(X3, Xs)) -> U3_GA(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 MEMBER_IN_GA(X, .(X3, Xs)) -> MEMBER_IN_GA(X, Xs) 7.36/2.87 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_GA(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.36/2.87 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> SUBSET_IN_GA(Xs, Ys) 7.36/2.87 7.36/2.87 The TRS R consists of the following rules: 7.36/2.87 7.36/2.87 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.36/2.87 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.36/2.87 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.36/2.87 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.36/2.87 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.36/2.87 7.36/2.87 The argument filtering Pi contains the following mapping: 7.36/2.87 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.36/2.87 7.36/2.87 [] = [] 7.36/2.87 7.36/2.87 subset_out_ga(x1, x2) = subset_out_ga(x1) 7.36/2.87 7.36/2.87 .(x1, x2) = .(x1, x2) 7.36/2.87 7.36/2.87 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 member_in_ga(x1, x2) = member_in_ga(x1) 7.36/2.87 7.36/2.87 member_out_ga(x1, x2) = member_out_ga(x1) 7.36/2.87 7.36/2.87 U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) 7.36/2.87 7.36/2.87 U2_ga(x1, x2, x3, x4) = U2_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 SUBSET_IN_GA(x1, x2) = SUBSET_IN_GA(x1) 7.36/2.87 7.36/2.87 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x2, x4) 7.36/2.87 7.36/2.87 MEMBER_IN_GA(x1, x2) = MEMBER_IN_GA(x1) 7.36/2.87 7.36/2.87 U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) 7.36/2.87 7.36/2.87 U2_GA(x1, x2, x3, x4) = U2_GA(x1, x2, x4) 7.36/2.87 7.36/2.87 7.36/2.87 We have to consider all (P,R,Pi)-chains 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (4) 7.36/2.87 Obligation: 7.36/2.87 Pi DP problem: 7.36/2.87 The TRS P consists of the following rules: 7.36/2.87 7.36/2.87 SUBSET_IN_GA(.(X, Xs), Ys) -> U1_GA(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 SUBSET_IN_GA(.(X, Xs), Ys) -> MEMBER_IN_GA(X, Ys) 7.36/2.87 MEMBER_IN_GA(X, .(X3, Xs)) -> U3_GA(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 MEMBER_IN_GA(X, .(X3, Xs)) -> MEMBER_IN_GA(X, Xs) 7.36/2.87 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_GA(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.36/2.87 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> SUBSET_IN_GA(Xs, Ys) 7.36/2.87 7.36/2.87 The TRS R consists of the following rules: 7.36/2.87 7.36/2.87 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.36/2.87 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.36/2.87 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.36/2.87 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.36/2.87 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.36/2.87 7.36/2.87 The argument filtering Pi contains the following mapping: 7.36/2.87 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.36/2.87 7.36/2.87 [] = [] 7.36/2.87 7.36/2.87 subset_out_ga(x1, x2) = subset_out_ga(x1) 7.36/2.87 7.36/2.87 .(x1, x2) = .(x1, x2) 7.36/2.87 7.36/2.87 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 member_in_ga(x1, x2) = member_in_ga(x1) 7.36/2.87 7.36/2.87 member_out_ga(x1, x2) = member_out_ga(x1) 7.36/2.87 7.36/2.87 U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) 7.36/2.87 7.36/2.87 U2_ga(x1, x2, x3, x4) = U2_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 SUBSET_IN_GA(x1, x2) = SUBSET_IN_GA(x1) 7.36/2.87 7.36/2.87 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x2, x4) 7.36/2.87 7.36/2.87 MEMBER_IN_GA(x1, x2) = MEMBER_IN_GA(x1) 7.36/2.87 7.36/2.87 U3_GA(x1, x2, x3, x4) = U3_GA(x1, x4) 7.36/2.87 7.36/2.87 U2_GA(x1, x2, x3, x4) = U2_GA(x1, x2, x4) 7.36/2.87 7.36/2.87 7.36/2.87 We have to consider all (P,R,Pi)-chains 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (5) DependencyGraphProof (EQUIVALENT) 7.36/2.87 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (6) 7.36/2.87 Complex Obligation (AND) 7.36/2.87 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (7) 7.36/2.87 Obligation: 7.36/2.87 Pi DP problem: 7.36/2.87 The TRS P consists of the following rules: 7.36/2.87 7.36/2.87 MEMBER_IN_GA(X, .(X3, Xs)) -> MEMBER_IN_GA(X, Xs) 7.36/2.87 7.36/2.87 The TRS R consists of the following rules: 7.36/2.87 7.36/2.87 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.36/2.87 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.36/2.87 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.36/2.87 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.36/2.87 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.36/2.87 7.36/2.87 The argument filtering Pi contains the following mapping: 7.36/2.87 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.36/2.87 7.36/2.87 [] = [] 7.36/2.87 7.36/2.87 subset_out_ga(x1, x2) = subset_out_ga(x1) 7.36/2.87 7.36/2.87 .(x1, x2) = .(x1, x2) 7.36/2.87 7.36/2.87 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 member_in_ga(x1, x2) = member_in_ga(x1) 7.36/2.87 7.36/2.87 member_out_ga(x1, x2) = member_out_ga(x1) 7.36/2.87 7.36/2.87 U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) 7.36/2.87 7.36/2.87 U2_ga(x1, x2, x3, x4) = U2_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 MEMBER_IN_GA(x1, x2) = MEMBER_IN_GA(x1) 7.36/2.87 7.36/2.87 7.36/2.87 We have to consider all (P,R,Pi)-chains 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (8) UsableRulesProof (EQUIVALENT) 7.36/2.87 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (9) 7.36/2.87 Obligation: 7.36/2.87 Pi DP problem: 7.36/2.87 The TRS P consists of the following rules: 7.36/2.87 7.36/2.87 MEMBER_IN_GA(X, .(X3, Xs)) -> MEMBER_IN_GA(X, Xs) 7.36/2.87 7.36/2.87 R is empty. 7.36/2.87 The argument filtering Pi contains the following mapping: 7.36/2.87 .(x1, x2) = .(x1, x2) 7.36/2.87 7.36/2.87 MEMBER_IN_GA(x1, x2) = MEMBER_IN_GA(x1) 7.36/2.87 7.36/2.87 7.36/2.87 We have to consider all (P,R,Pi)-chains 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (10) PiDPToQDPProof (SOUND) 7.36/2.87 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (11) 7.36/2.87 Obligation: 7.36/2.87 Q DP problem: 7.36/2.87 The TRS P consists of the following rules: 7.36/2.87 7.36/2.87 MEMBER_IN_GA(X) -> MEMBER_IN_GA(X) 7.36/2.87 7.36/2.87 R is empty. 7.36/2.87 Q is empty. 7.36/2.87 We have to consider all (P,Q,R)-chains. 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (12) NonTerminationLoopProof (COMPLETE) 7.36/2.87 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 7.36/2.87 Found a loop by semiunifying a rule from P directly. 7.36/2.87 7.36/2.87 s = MEMBER_IN_GA(X) evaluates to t =MEMBER_IN_GA(X) 7.36/2.87 7.36/2.87 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 7.36/2.87 * Matcher: [ ] 7.36/2.87 * Semiunifier: [ ] 7.36/2.87 7.36/2.87 -------------------------------------------------------------------------------- 7.36/2.87 Rewriting sequence 7.36/2.87 7.36/2.87 The DP semiunifies directly so there is only one rewrite step from MEMBER_IN_GA(X) to MEMBER_IN_GA(X). 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (13) 7.36/2.87 NO 7.36/2.87 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (14) 7.36/2.87 Obligation: 7.36/2.87 Pi DP problem: 7.36/2.87 The TRS P consists of the following rules: 7.36/2.87 7.36/2.87 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> SUBSET_IN_GA(Xs, Ys) 7.36/2.87 SUBSET_IN_GA(.(X, Xs), Ys) -> U1_GA(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 7.36/2.87 The TRS R consists of the following rules: 7.36/2.87 7.36/2.87 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.36/2.87 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.36/2.87 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.36/2.87 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.36/2.87 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.36/2.87 7.36/2.87 The argument filtering Pi contains the following mapping: 7.36/2.87 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.36/2.87 7.36/2.87 [] = [] 7.36/2.87 7.36/2.87 subset_out_ga(x1, x2) = subset_out_ga(x1) 7.36/2.87 7.36/2.87 .(x1, x2) = .(x1, x2) 7.36/2.87 7.36/2.87 U1_ga(x1, x2, x3, x4) = U1_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 member_in_ga(x1, x2) = member_in_ga(x1) 7.36/2.87 7.36/2.87 member_out_ga(x1, x2) = member_out_ga(x1) 7.36/2.87 7.36/2.87 U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) 7.36/2.87 7.36/2.87 U2_ga(x1, x2, x3, x4) = U2_ga(x1, x2, x4) 7.36/2.87 7.36/2.87 SUBSET_IN_GA(x1, x2) = SUBSET_IN_GA(x1) 7.36/2.87 7.36/2.87 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x2, x4) 7.36/2.87 7.36/2.87 7.36/2.87 We have to consider all (P,R,Pi)-chains 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (15) UsableRulesProof (EQUIVALENT) 7.36/2.87 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (16) 7.36/2.87 Obligation: 7.36/2.87 Pi DP problem: 7.36/2.87 The TRS P consists of the following rules: 7.36/2.87 7.36/2.87 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> SUBSET_IN_GA(Xs, Ys) 7.36/2.87 SUBSET_IN_GA(.(X, Xs), Ys) -> U1_GA(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 7.36/2.87 The TRS R consists of the following rules: 7.36/2.87 7.36/2.87 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.36/2.87 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.36/2.87 7.36/2.87 The argument filtering Pi contains the following mapping: 7.36/2.87 .(x1, x2) = .(x1, x2) 7.36/2.87 7.36/2.87 member_in_ga(x1, x2) = member_in_ga(x1) 7.36/2.87 7.36/2.87 member_out_ga(x1, x2) = member_out_ga(x1) 7.36/2.87 7.36/2.87 U3_ga(x1, x2, x3, x4) = U3_ga(x1, x4) 7.36/2.87 7.36/2.87 SUBSET_IN_GA(x1, x2) = SUBSET_IN_GA(x1) 7.36/2.87 7.36/2.87 U1_GA(x1, x2, x3, x4) = U1_GA(x1, x2, x4) 7.36/2.87 7.36/2.87 7.36/2.87 We have to consider all (P,R,Pi)-chains 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (17) PrologToPiTRSProof (SOUND) 7.36/2.87 We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: 7.36/2.87 7.36/2.87 subset_in_2: (b,f) 7.36/2.87 7.36/2.87 member_in_2: (b,f) 7.36/2.87 7.36/2.87 Transforming Prolog into the following Term Rewriting System: 7.36/2.87 7.36/2.87 Pi-finite rewrite system: 7.36/2.87 The TRS R consists of the following rules: 7.36/2.87 7.36/2.87 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.36/2.87 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.36/2.87 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.36/2.87 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.36/2.87 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.36/2.87 7.36/2.87 The argument filtering Pi contains the following mapping: 7.36/2.87 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.36/2.87 7.36/2.87 [] = [] 7.36/2.87 7.36/2.87 subset_out_ga(x1, x2) = subset_out_ga 7.36/2.87 7.36/2.87 .(x1, x2) = .(x1, x2) 7.36/2.87 7.36/2.87 U1_ga(x1, x2, x3, x4) = U1_ga(x2, x4) 7.36/2.87 7.36/2.87 member_in_ga(x1, x2) = member_in_ga(x1) 7.36/2.87 7.36/2.87 member_out_ga(x1, x2) = member_out_ga 7.36/2.87 7.36/2.87 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 7.36/2.87 7.36/2.87 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog 7.36/2.87 7.36/2.87 7.36/2.87 7.36/2.87 ---------------------------------------- 7.36/2.87 7.36/2.87 (18) 7.36/2.87 Obligation: 7.36/2.87 Pi-finite rewrite system: 7.36/2.87 The TRS R consists of the following rules: 7.36/2.87 7.36/2.87 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.36/2.87 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.36/2.87 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.36/2.87 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.36/2.87 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.60/2.88 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.60/2.88 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.60/2.88 7.60/2.88 The argument filtering Pi contains the following mapping: 7.60/2.88 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.60/2.88 7.60/2.88 [] = [] 7.60/2.88 7.60/2.88 subset_out_ga(x1, x2) = subset_out_ga 7.60/2.88 7.60/2.88 .(x1, x2) = .(x1, x2) 7.60/2.88 7.60/2.88 U1_ga(x1, x2, x3, x4) = U1_ga(x2, x4) 7.60/2.88 7.60/2.88 member_in_ga(x1, x2) = member_in_ga(x1) 7.60/2.88 7.60/2.88 member_out_ga(x1, x2) = member_out_ga 7.60/2.88 7.60/2.88 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 7.60/2.88 7.60/2.88 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 7.60/2.88 7.60/2.88 7.60/2.88 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (19) DependencyPairsProof (EQUIVALENT) 7.60/2.88 Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: 7.60/2.88 Pi DP problem: 7.60/2.88 The TRS P consists of the following rules: 7.60/2.88 7.60/2.88 SUBSET_IN_GA(.(X, Xs), Ys) -> U1_GA(X, Xs, Ys, member_in_ga(X, Ys)) 7.60/2.88 SUBSET_IN_GA(.(X, Xs), Ys) -> MEMBER_IN_GA(X, Ys) 7.60/2.88 MEMBER_IN_GA(X, .(X3, Xs)) -> U3_GA(X, X3, Xs, member_in_ga(X, Xs)) 7.60/2.88 MEMBER_IN_GA(X, .(X3, Xs)) -> MEMBER_IN_GA(X, Xs) 7.60/2.88 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_GA(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.60/2.88 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> SUBSET_IN_GA(Xs, Ys) 7.60/2.88 7.60/2.88 The TRS R consists of the following rules: 7.60/2.88 7.60/2.88 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.60/2.88 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.60/2.88 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.60/2.88 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.60/2.88 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.60/2.88 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.60/2.88 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.60/2.88 7.60/2.88 The argument filtering Pi contains the following mapping: 7.60/2.88 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.60/2.88 7.60/2.88 [] = [] 7.60/2.88 7.60/2.88 subset_out_ga(x1, x2) = subset_out_ga 7.60/2.88 7.60/2.88 .(x1, x2) = .(x1, x2) 7.60/2.88 7.60/2.88 U1_ga(x1, x2, x3, x4) = U1_ga(x2, x4) 7.60/2.88 7.60/2.88 member_in_ga(x1, x2) = member_in_ga(x1) 7.60/2.88 7.60/2.88 member_out_ga(x1, x2) = member_out_ga 7.60/2.88 7.60/2.88 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 7.60/2.88 7.60/2.88 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 7.60/2.88 7.60/2.88 SUBSET_IN_GA(x1, x2) = SUBSET_IN_GA(x1) 7.60/2.88 7.60/2.88 U1_GA(x1, x2, x3, x4) = U1_GA(x2, x4) 7.60/2.88 7.60/2.88 MEMBER_IN_GA(x1, x2) = MEMBER_IN_GA(x1) 7.60/2.88 7.60/2.88 U3_GA(x1, x2, x3, x4) = U3_GA(x4) 7.60/2.88 7.60/2.88 U2_GA(x1, x2, x3, x4) = U2_GA(x4) 7.60/2.88 7.60/2.88 7.60/2.88 We have to consider all (P,R,Pi)-chains 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (20) 7.60/2.88 Obligation: 7.60/2.88 Pi DP problem: 7.60/2.88 The TRS P consists of the following rules: 7.60/2.88 7.60/2.88 SUBSET_IN_GA(.(X, Xs), Ys) -> U1_GA(X, Xs, Ys, member_in_ga(X, Ys)) 7.60/2.88 SUBSET_IN_GA(.(X, Xs), Ys) -> MEMBER_IN_GA(X, Ys) 7.60/2.88 MEMBER_IN_GA(X, .(X3, Xs)) -> U3_GA(X, X3, Xs, member_in_ga(X, Xs)) 7.60/2.88 MEMBER_IN_GA(X, .(X3, Xs)) -> MEMBER_IN_GA(X, Xs) 7.60/2.88 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_GA(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.60/2.88 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> SUBSET_IN_GA(Xs, Ys) 7.60/2.88 7.60/2.88 The TRS R consists of the following rules: 7.60/2.88 7.60/2.88 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.60/2.88 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.60/2.88 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.60/2.88 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.60/2.88 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.60/2.88 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.60/2.88 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.60/2.88 7.60/2.88 The argument filtering Pi contains the following mapping: 7.60/2.88 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.60/2.88 7.60/2.88 [] = [] 7.60/2.88 7.60/2.88 subset_out_ga(x1, x2) = subset_out_ga 7.60/2.88 7.60/2.88 .(x1, x2) = .(x1, x2) 7.60/2.88 7.60/2.88 U1_ga(x1, x2, x3, x4) = U1_ga(x2, x4) 7.60/2.88 7.60/2.88 member_in_ga(x1, x2) = member_in_ga(x1) 7.60/2.88 7.60/2.88 member_out_ga(x1, x2) = member_out_ga 7.60/2.88 7.60/2.88 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 7.60/2.88 7.60/2.88 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 7.60/2.88 7.60/2.88 SUBSET_IN_GA(x1, x2) = SUBSET_IN_GA(x1) 7.60/2.88 7.60/2.88 U1_GA(x1, x2, x3, x4) = U1_GA(x2, x4) 7.60/2.88 7.60/2.88 MEMBER_IN_GA(x1, x2) = MEMBER_IN_GA(x1) 7.60/2.88 7.60/2.88 U3_GA(x1, x2, x3, x4) = U3_GA(x4) 7.60/2.88 7.60/2.88 U2_GA(x1, x2, x3, x4) = U2_GA(x4) 7.60/2.88 7.60/2.88 7.60/2.88 We have to consider all (P,R,Pi)-chains 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (21) DependencyGraphProof (EQUIVALENT) 7.60/2.88 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (22) 7.60/2.88 Complex Obligation (AND) 7.60/2.88 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (23) 7.60/2.88 Obligation: 7.60/2.88 Pi DP problem: 7.60/2.88 The TRS P consists of the following rules: 7.60/2.88 7.60/2.88 MEMBER_IN_GA(X, .(X3, Xs)) -> MEMBER_IN_GA(X, Xs) 7.60/2.88 7.60/2.88 The TRS R consists of the following rules: 7.60/2.88 7.60/2.88 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.60/2.88 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.60/2.88 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.60/2.88 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.60/2.88 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.60/2.88 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.60/2.88 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.60/2.88 7.60/2.88 The argument filtering Pi contains the following mapping: 7.60/2.88 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.60/2.88 7.60/2.88 [] = [] 7.60/2.88 7.60/2.88 subset_out_ga(x1, x2) = subset_out_ga 7.60/2.88 7.60/2.88 .(x1, x2) = .(x1, x2) 7.60/2.88 7.60/2.88 U1_ga(x1, x2, x3, x4) = U1_ga(x2, x4) 7.60/2.88 7.60/2.88 member_in_ga(x1, x2) = member_in_ga(x1) 7.60/2.88 7.60/2.88 member_out_ga(x1, x2) = member_out_ga 7.60/2.88 7.60/2.88 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 7.60/2.88 7.60/2.88 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 7.60/2.88 7.60/2.88 MEMBER_IN_GA(x1, x2) = MEMBER_IN_GA(x1) 7.60/2.88 7.60/2.88 7.60/2.88 We have to consider all (P,R,Pi)-chains 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (24) UsableRulesProof (EQUIVALENT) 7.60/2.88 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (25) 7.60/2.88 Obligation: 7.60/2.88 Pi DP problem: 7.60/2.88 The TRS P consists of the following rules: 7.60/2.88 7.60/2.88 MEMBER_IN_GA(X, .(X3, Xs)) -> MEMBER_IN_GA(X, Xs) 7.60/2.88 7.60/2.88 R is empty. 7.60/2.88 The argument filtering Pi contains the following mapping: 7.60/2.88 .(x1, x2) = .(x1, x2) 7.60/2.88 7.60/2.88 MEMBER_IN_GA(x1, x2) = MEMBER_IN_GA(x1) 7.60/2.88 7.60/2.88 7.60/2.88 We have to consider all (P,R,Pi)-chains 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (26) PiDPToQDPProof (SOUND) 7.60/2.88 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (27) 7.60/2.88 Obligation: 7.60/2.88 Q DP problem: 7.60/2.88 The TRS P consists of the following rules: 7.60/2.88 7.60/2.88 MEMBER_IN_GA(X) -> MEMBER_IN_GA(X) 7.60/2.88 7.60/2.88 R is empty. 7.60/2.88 Q is empty. 7.60/2.88 We have to consider all (P,Q,R)-chains. 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (28) NonTerminationLoopProof (COMPLETE) 7.60/2.88 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 7.60/2.88 Found a loop by semiunifying a rule from P directly. 7.60/2.88 7.60/2.88 s = MEMBER_IN_GA(X) evaluates to t =MEMBER_IN_GA(X) 7.60/2.88 7.60/2.88 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 7.60/2.88 * Matcher: [ ] 7.60/2.88 * Semiunifier: [ ] 7.60/2.88 7.60/2.88 -------------------------------------------------------------------------------- 7.60/2.88 Rewriting sequence 7.60/2.88 7.60/2.88 The DP semiunifies directly so there is only one rewrite step from MEMBER_IN_GA(X) to MEMBER_IN_GA(X). 7.60/2.88 7.60/2.88 7.60/2.88 7.60/2.88 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (29) 7.60/2.88 NO 7.60/2.88 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (30) 7.60/2.88 Obligation: 7.60/2.88 Pi DP problem: 7.60/2.88 The TRS P consists of the following rules: 7.60/2.88 7.60/2.88 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> SUBSET_IN_GA(Xs, Ys) 7.60/2.88 SUBSET_IN_GA(.(X, Xs), Ys) -> U1_GA(X, Xs, Ys, member_in_ga(X, Ys)) 7.60/2.88 7.60/2.88 The TRS R consists of the following rules: 7.60/2.88 7.60/2.88 subset_in_ga([], X1) -> subset_out_ga([], X1) 7.60/2.88 subset_in_ga(.(X, Xs), Ys) -> U1_ga(X, Xs, Ys, member_in_ga(X, Ys)) 7.60/2.88 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.60/2.88 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.60/2.88 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.60/2.88 U1_ga(X, Xs, Ys, member_out_ga(X, Ys)) -> U2_ga(X, Xs, Ys, subset_in_ga(Xs, Ys)) 7.60/2.88 U2_ga(X, Xs, Ys, subset_out_ga(Xs, Ys)) -> subset_out_ga(.(X, Xs), Ys) 7.60/2.88 7.60/2.88 The argument filtering Pi contains the following mapping: 7.60/2.88 subset_in_ga(x1, x2) = subset_in_ga(x1) 7.60/2.88 7.60/2.88 [] = [] 7.60/2.88 7.60/2.88 subset_out_ga(x1, x2) = subset_out_ga 7.60/2.88 7.60/2.88 .(x1, x2) = .(x1, x2) 7.60/2.88 7.60/2.88 U1_ga(x1, x2, x3, x4) = U1_ga(x2, x4) 7.60/2.88 7.60/2.88 member_in_ga(x1, x2) = member_in_ga(x1) 7.60/2.88 7.60/2.88 member_out_ga(x1, x2) = member_out_ga 7.60/2.88 7.60/2.88 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 7.60/2.88 7.60/2.88 U2_ga(x1, x2, x3, x4) = U2_ga(x4) 7.60/2.88 7.60/2.88 SUBSET_IN_GA(x1, x2) = SUBSET_IN_GA(x1) 7.60/2.88 7.60/2.88 U1_GA(x1, x2, x3, x4) = U1_GA(x2, x4) 7.60/2.88 7.60/2.88 7.60/2.88 We have to consider all (P,R,Pi)-chains 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (31) UsableRulesProof (EQUIVALENT) 7.60/2.88 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 7.60/2.88 ---------------------------------------- 7.60/2.88 7.60/2.88 (32) 7.60/2.88 Obligation: 7.60/2.88 Pi DP problem: 7.60/2.88 The TRS P consists of the following rules: 7.60/2.88 7.60/2.88 U1_GA(X, Xs, Ys, member_out_ga(X, Ys)) -> SUBSET_IN_GA(Xs, Ys) 7.60/2.88 SUBSET_IN_GA(.(X, Xs), Ys) -> U1_GA(X, Xs, Ys, member_in_ga(X, Ys)) 7.60/2.88 7.60/2.88 The TRS R consists of the following rules: 7.60/2.88 7.60/2.88 member_in_ga(X, .(X, X2)) -> member_out_ga(X, .(X, X2)) 7.60/2.88 member_in_ga(X, .(X3, Xs)) -> U3_ga(X, X3, Xs, member_in_ga(X, Xs)) 7.60/2.88 U3_ga(X, X3, Xs, member_out_ga(X, Xs)) -> member_out_ga(X, .(X3, Xs)) 7.60/2.88 7.60/2.88 The argument filtering Pi contains the following mapping: 7.60/2.88 .(x1, x2) = .(x1, x2) 7.60/2.88 7.60/2.88 member_in_ga(x1, x2) = member_in_ga(x1) 7.60/2.88 7.60/2.88 member_out_ga(x1, x2) = member_out_ga 7.60/2.88 7.60/2.88 U3_ga(x1, x2, x3, x4) = U3_ga(x4) 7.60/2.88 7.60/2.88 SUBSET_IN_GA(x1, x2) = SUBSET_IN_GA(x1) 7.60/2.89 7.60/2.89 U1_GA(x1, x2, x3, x4) = U1_GA(x2, x4) 7.60/2.89 7.60/2.89 7.60/2.89 We have to consider all (P,R,Pi)-chains 7.60/2.89 ---------------------------------------- 7.60/2.89 7.60/2.89 (33) PrologToTRSTransformerProof (SOUND) 7.60/2.89 Transformed Prolog program to TRS. 7.60/2.89 7.60/2.89 { 7.60/2.89 "root": 2, 7.60/2.89 "program": { 7.60/2.89 "directives": [], 7.60/2.89 "clauses": [ 7.60/2.89 [ 7.60/2.89 "(subset ([]) X1)", 7.60/2.89 null 7.60/2.89 ], 7.60/2.89 [ 7.60/2.89 "(subset (. X Xs) Ys)", 7.60/2.89 "(',' (member X Ys) (subset Xs Ys))" 7.60/2.89 ], 7.60/2.89 [ 7.60/2.89 "(member X (. X X2))", 7.60/2.89 null 7.60/2.89 ], 7.60/2.89 [ 7.60/2.89 "(member X (. X3 Xs))", 7.60/2.89 "(member X Xs)" 7.60/2.89 ] 7.60/2.89 ] 7.60/2.89 }, 7.60/2.89 "graph": { 7.60/2.89 "nodes": { 7.60/2.89 "180": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": -1, 7.60/2.89 "scope": -1, 7.60/2.89 "term": "(member T43 T46)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T43"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "181": { 7.60/2.89 "goal": [], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": [], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "type": "Nodes", 7.60/2.89 "174": { 7.60/2.89 "goal": [ 7.60/2.89 { 7.60/2.89 "clause": 2, 7.60/2.89 "scope": 2, 7.60/2.89 "term": "(member T14 T17)" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "clause": 3, 7.60/2.89 "scope": 2, 7.60/2.89 "term": "(member T14 T17)" 7.60/2.89 } 7.60/2.89 ], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T14"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "175": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": 2, 7.60/2.89 "scope": 2, 7.60/2.89 "term": "(member T14 T17)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T14"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "121": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": -1, 7.60/2.89 "scope": -1, 7.60/2.89 "term": "(',' (member T14 T17) (subset T15 T17))" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": [ 7.60/2.89 "T14", 7.60/2.89 "T15" 7.60/2.89 ], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "176": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": 3, 7.60/2.89 "scope": 2, 7.60/2.89 "term": "(member T14 T17)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T14"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "166": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": -1, 7.60/2.89 "scope": -1, 7.60/2.89 "term": "(member T14 T17)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T14"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "177": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": -1, 7.60/2.89 "scope": -1, 7.60/2.89 "term": "(true)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": [], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "2": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": -1, 7.60/2.89 "scope": -1, 7.60/2.89 "term": "(subset T1 T2)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T1"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "167": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": -1, 7.60/2.89 "scope": -1, 7.60/2.89 "term": "(subset T15 T22)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T15"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "178": { 7.60/2.89 "goal": [], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": [], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "179": { 7.60/2.89 "goal": [], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": [], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "90": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": -1, 7.60/2.89 "scope": -1, 7.60/2.89 "term": "(true)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": [], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "128": { 7.60/2.89 "goal": [], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": [], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "91": { 7.60/2.89 "goal": [], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": [], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "92": { 7.60/2.89 "goal": [], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": [], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "86": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": 0, 7.60/2.89 "scope": 1, 7.60/2.89 "term": "(subset T1 T2)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T1"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "10": { 7.60/2.89 "goal": [ 7.60/2.89 { 7.60/2.89 "clause": 0, 7.60/2.89 "scope": 1, 7.60/2.89 "term": "(subset T1 T2)" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "clause": 1, 7.60/2.89 "scope": 1, 7.60/2.89 "term": "(subset T1 T2)" 7.60/2.89 } 7.60/2.89 ], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T1"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "87": { 7.60/2.89 "goal": [{ 7.60/2.89 "clause": 1, 7.60/2.89 "scope": 1, 7.60/2.89 "term": "(subset T1 T2)" 7.60/2.89 }], 7.60/2.89 "kb": { 7.60/2.89 "nonunifying": [], 7.60/2.89 "intvars": {}, 7.60/2.89 "arithmetic": { 7.60/2.89 "type": "PlainIntegerRelationState", 7.60/2.89 "relations": [] 7.60/2.89 }, 7.60/2.89 "ground": ["T1"], 7.60/2.89 "free": [], 7.60/2.89 "exprvars": [] 7.60/2.89 } 7.60/2.89 } 7.60/2.89 }, 7.60/2.89 "edges": [ 7.60/2.89 { 7.60/2.89 "from": 2, 7.60/2.89 "to": 10, 7.60/2.89 "label": "CASE" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 10, 7.60/2.89 "to": 86, 7.60/2.89 "label": "PARALLEL" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 10, 7.60/2.89 "to": 87, 7.60/2.89 "label": "PARALLEL" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 86, 7.60/2.89 "to": 90, 7.60/2.89 "label": "EVAL with clause\nsubset([], X8).\nand substitutionT1 -> [],\nT2 -> T7,\nX8 -> T7" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 86, 7.60/2.89 "to": 91, 7.60/2.89 "label": "EVAL-BACKTRACK" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 87, 7.60/2.89 "to": 121, 7.60/2.89 "label": "EVAL with clause\nsubset(.(X15, X16), X17) :- ','(member(X15, X17), subset(X16, X17)).\nand substitutionX15 -> T14,\nX16 -> T15,\nT1 -> .(T14, T15),\nT2 -> T17,\nX17 -> T17,\nT16 -> T17" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 87, 7.60/2.89 "to": 128, 7.60/2.89 "label": "EVAL-BACKTRACK" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 90, 7.60/2.89 "to": 92, 7.60/2.89 "label": "SUCCESS" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 121, 7.60/2.89 "to": 166, 7.60/2.89 "label": "SPLIT 1" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 121, 7.60/2.89 "to": 167, 7.60/2.89 "label": "SPLIT 2\nnew knowledge:\nT14 is ground\nreplacements:T17 -> T22" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 166, 7.60/2.89 "to": 174, 7.60/2.89 "label": "CASE" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 167, 7.60/2.89 "to": 2, 7.60/2.89 "label": "INSTANCE with matching:\nT1 -> T15\nT2 -> T22" 7.60/2.89 }, 7.60/2.89 { 7.60/2.89 "from": 174, 7.60/2.89 "to": 175, 7.60/2.89 "label": "PARALLEL" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 174, 7.65/2.89 "to": 176, 7.65/2.89 "label": "PARALLEL" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 175, 7.65/2.89 "to": 177, 7.65/2.89 "label": "EVAL with clause\nmember(X34, .(X34, X35)).\nand substitutionT14 -> T35,\nX34 -> T35,\nX35 -> T36,\nT17 -> .(T35, T36)" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 175, 7.65/2.89 "to": 178, 7.65/2.89 "label": "EVAL-BACKTRACK" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 176, 7.65/2.89 "to": 180, 7.65/2.89 "label": "EVAL with clause\nmember(X42, .(X43, X44)) :- member(X42, X44).\nand substitutionT14 -> T43,\nX42 -> T43,\nX43 -> T44,\nX44 -> T46,\nT17 -> .(T44, T46),\nT45 -> T46" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 176, 7.65/2.89 "to": 181, 7.65/2.89 "label": "EVAL-BACKTRACK" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 177, 7.65/2.89 "to": 179, 7.65/2.89 "label": "SUCCESS" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 180, 7.65/2.89 "to": 166, 7.65/2.89 "label": "INSTANCE with matching:\nT14 -> T43\nT17 -> T46" 7.65/2.89 } 7.65/2.89 ], 7.65/2.89 "type": "Graph" 7.65/2.89 } 7.65/2.89 } 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (34) 7.65/2.89 Obligation: 7.65/2.89 Q restricted rewrite system: 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 f2_in([]) -> f2_out1 7.65/2.89 f2_in(.(T14, T15)) -> U1(f121_in(T14, T15), .(T14, T15)) 7.65/2.89 U1(f121_out1, .(T14, T15)) -> f2_out1 7.65/2.89 f166_in(T35) -> f166_out1 7.65/2.89 f166_in(T43) -> U2(f166_in(T43), T43) 7.65/2.89 U2(f166_out1, T43) -> f166_out1 7.65/2.89 f121_in(T14, T15) -> U3(f166_in(T14), T14, T15) 7.65/2.89 U3(f166_out1, T14, T15) -> U4(f2_in(T15), T14, T15) 7.65/2.89 U4(f2_out1, T14, T15) -> f121_out1 7.65/2.89 7.65/2.89 Q is empty. 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (35) DependencyPairsProof (EQUIVALENT) 7.65/2.89 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (36) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 F2_IN(.(T14, T15)) -> U1^1(f121_in(T14, T15), .(T14, T15)) 7.65/2.89 F2_IN(.(T14, T15)) -> F121_IN(T14, T15) 7.65/2.89 F166_IN(T43) -> U2^1(f166_in(T43), T43) 7.65/2.89 F166_IN(T43) -> F166_IN(T43) 7.65/2.89 F121_IN(T14, T15) -> U3^1(f166_in(T14), T14, T15) 7.65/2.89 F121_IN(T14, T15) -> F166_IN(T14) 7.65/2.89 U3^1(f166_out1, T14, T15) -> U4^1(f2_in(T15), T14, T15) 7.65/2.89 U3^1(f166_out1, T14, T15) -> F2_IN(T15) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 f2_in([]) -> f2_out1 7.65/2.89 f2_in(.(T14, T15)) -> U1(f121_in(T14, T15), .(T14, T15)) 7.65/2.89 U1(f121_out1, .(T14, T15)) -> f2_out1 7.65/2.89 f166_in(T35) -> f166_out1 7.65/2.89 f166_in(T43) -> U2(f166_in(T43), T43) 7.65/2.89 U2(f166_out1, T43) -> f166_out1 7.65/2.89 f121_in(T14, T15) -> U3(f166_in(T14), T14, T15) 7.65/2.89 U3(f166_out1, T14, T15) -> U4(f2_in(T15), T14, T15) 7.65/2.89 U4(f2_out1, T14, T15) -> f121_out1 7.65/2.89 7.65/2.89 Q is empty. 7.65/2.89 We have to consider all minimal (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (37) DependencyGraphProof (EQUIVALENT) 7.65/2.89 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (38) 7.65/2.89 Complex Obligation (AND) 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (39) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 F166_IN(T43) -> F166_IN(T43) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 f2_in([]) -> f2_out1 7.65/2.89 f2_in(.(T14, T15)) -> U1(f121_in(T14, T15), .(T14, T15)) 7.65/2.89 U1(f121_out1, .(T14, T15)) -> f2_out1 7.65/2.89 f166_in(T35) -> f166_out1 7.65/2.89 f166_in(T43) -> U2(f166_in(T43), T43) 7.65/2.89 U2(f166_out1, T43) -> f166_out1 7.65/2.89 f121_in(T14, T15) -> U3(f166_in(T14), T14, T15) 7.65/2.89 U3(f166_out1, T14, T15) -> U4(f2_in(T15), T14, T15) 7.65/2.89 U4(f2_out1, T14, T15) -> f121_out1 7.65/2.89 7.65/2.89 Q is empty. 7.65/2.89 We have to consider all minimal (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (40) MNOCProof (EQUIVALENT) 7.65/2.89 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (41) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 F166_IN(T43) -> F166_IN(T43) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 f2_in([]) -> f2_out1 7.65/2.89 f2_in(.(T14, T15)) -> U1(f121_in(T14, T15), .(T14, T15)) 7.65/2.89 U1(f121_out1, .(T14, T15)) -> f2_out1 7.65/2.89 f166_in(T35) -> f166_out1 7.65/2.89 f166_in(T43) -> U2(f166_in(T43), T43) 7.65/2.89 U2(f166_out1, T43) -> f166_out1 7.65/2.89 f121_in(T14, T15) -> U3(f166_in(T14), T14, T15) 7.65/2.89 U3(f166_out1, T14, T15) -> U4(f2_in(T15), T14, T15) 7.65/2.89 U4(f2_out1, T14, T15) -> f121_out1 7.65/2.89 7.65/2.89 The set Q consists of the following terms: 7.65/2.89 7.65/2.89 f2_in([]) 7.65/2.89 f2_in(.(x0, x1)) 7.65/2.89 U1(f121_out1, .(x0, x1)) 7.65/2.89 f166_in(x0) 7.65/2.89 U2(f166_out1, x0) 7.65/2.89 f121_in(x0, x1) 7.65/2.89 U3(f166_out1, x0, x1) 7.65/2.89 U4(f2_out1, x0, x1) 7.65/2.89 7.65/2.89 We have to consider all minimal (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (42) UsableRulesProof (EQUIVALENT) 7.65/2.89 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (43) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 F166_IN(T43) -> F166_IN(T43) 7.65/2.89 7.65/2.89 R is empty. 7.65/2.89 The set Q consists of the following terms: 7.65/2.89 7.65/2.89 f2_in([]) 7.65/2.89 f2_in(.(x0, x1)) 7.65/2.89 U1(f121_out1, .(x0, x1)) 7.65/2.89 f166_in(x0) 7.65/2.89 U2(f166_out1, x0) 7.65/2.89 f121_in(x0, x1) 7.65/2.89 U3(f166_out1, x0, x1) 7.65/2.89 U4(f2_out1, x0, x1) 7.65/2.89 7.65/2.89 We have to consider all minimal (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (44) QReductionProof (EQUIVALENT) 7.65/2.89 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.65/2.89 7.65/2.89 f2_in([]) 7.65/2.89 f2_in(.(x0, x1)) 7.65/2.89 U1(f121_out1, .(x0, x1)) 7.65/2.89 f166_in(x0) 7.65/2.89 U2(f166_out1, x0) 7.65/2.89 f121_in(x0, x1) 7.65/2.89 U3(f166_out1, x0, x1) 7.65/2.89 U4(f2_out1, x0, x1) 7.65/2.89 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (45) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 F166_IN(T43) -> F166_IN(T43) 7.65/2.89 7.65/2.89 R is empty. 7.65/2.89 Q is empty. 7.65/2.89 We have to consider all minimal (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (46) NonTerminationLoopProof (COMPLETE) 7.65/2.89 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 7.65/2.89 Found a loop by semiunifying a rule from P directly. 7.65/2.89 7.65/2.89 s = F166_IN(T43) evaluates to t =F166_IN(T43) 7.65/2.89 7.65/2.89 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 7.65/2.89 * Matcher: [ ] 7.65/2.89 * Semiunifier: [ ] 7.65/2.89 7.65/2.89 -------------------------------------------------------------------------------- 7.65/2.89 Rewriting sequence 7.65/2.89 7.65/2.89 The DP semiunifies directly so there is only one rewrite step from F166_IN(T43) to F166_IN(T43). 7.65/2.89 7.65/2.89 7.65/2.89 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (47) 7.65/2.89 NO 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (48) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 F2_IN(.(T14, T15)) -> F121_IN(T14, T15) 7.65/2.89 F121_IN(T14, T15) -> U3^1(f166_in(T14), T14, T15) 7.65/2.89 U3^1(f166_out1, T14, T15) -> F2_IN(T15) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 f2_in([]) -> f2_out1 7.65/2.89 f2_in(.(T14, T15)) -> U1(f121_in(T14, T15), .(T14, T15)) 7.65/2.89 U1(f121_out1, .(T14, T15)) -> f2_out1 7.65/2.89 f166_in(T35) -> f166_out1 7.65/2.89 f166_in(T43) -> U2(f166_in(T43), T43) 7.65/2.89 U2(f166_out1, T43) -> f166_out1 7.65/2.89 f121_in(T14, T15) -> U3(f166_in(T14), T14, T15) 7.65/2.89 U3(f166_out1, T14, T15) -> U4(f2_in(T15), T14, T15) 7.65/2.89 U4(f2_out1, T14, T15) -> f121_out1 7.65/2.89 7.65/2.89 Q is empty. 7.65/2.89 We have to consider all minimal (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (49) MNOCProof (EQUIVALENT) 7.65/2.89 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (50) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 F2_IN(.(T14, T15)) -> F121_IN(T14, T15) 7.65/2.89 F121_IN(T14, T15) -> U3^1(f166_in(T14), T14, T15) 7.65/2.89 U3^1(f166_out1, T14, T15) -> F2_IN(T15) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 f2_in([]) -> f2_out1 7.65/2.89 f2_in(.(T14, T15)) -> U1(f121_in(T14, T15), .(T14, T15)) 7.65/2.89 U1(f121_out1, .(T14, T15)) -> f2_out1 7.65/2.89 f166_in(T35) -> f166_out1 7.65/2.89 f166_in(T43) -> U2(f166_in(T43), T43) 7.65/2.89 U2(f166_out1, T43) -> f166_out1 7.65/2.89 f121_in(T14, T15) -> U3(f166_in(T14), T14, T15) 7.65/2.89 U3(f166_out1, T14, T15) -> U4(f2_in(T15), T14, T15) 7.65/2.89 U4(f2_out1, T14, T15) -> f121_out1 7.65/2.89 7.65/2.89 The set Q consists of the following terms: 7.65/2.89 7.65/2.89 f2_in([]) 7.65/2.89 f2_in(.(x0, x1)) 7.65/2.89 U1(f121_out1, .(x0, x1)) 7.65/2.89 f166_in(x0) 7.65/2.89 U2(f166_out1, x0) 7.65/2.89 f121_in(x0, x1) 7.65/2.89 U3(f166_out1, x0, x1) 7.65/2.89 U4(f2_out1, x0, x1) 7.65/2.89 7.65/2.89 We have to consider all minimal (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (51) UsableRulesProof (EQUIVALENT) 7.65/2.89 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (52) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 F2_IN(.(T14, T15)) -> F121_IN(T14, T15) 7.65/2.89 F121_IN(T14, T15) -> U3^1(f166_in(T14), T14, T15) 7.65/2.89 U3^1(f166_out1, T14, T15) -> F2_IN(T15) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 f166_in(T35) -> f166_out1 7.65/2.89 f166_in(T43) -> U2(f166_in(T43), T43) 7.65/2.89 U2(f166_out1, T43) -> f166_out1 7.65/2.89 7.65/2.89 The set Q consists of the following terms: 7.65/2.89 7.65/2.89 f2_in([]) 7.65/2.89 f2_in(.(x0, x1)) 7.65/2.89 U1(f121_out1, .(x0, x1)) 7.65/2.89 f166_in(x0) 7.65/2.89 U2(f166_out1, x0) 7.65/2.89 f121_in(x0, x1) 7.65/2.89 U3(f166_out1, x0, x1) 7.65/2.89 U4(f2_out1, x0, x1) 7.65/2.89 7.65/2.89 We have to consider all minimal (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (53) QReductionProof (EQUIVALENT) 7.65/2.89 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.65/2.89 7.65/2.89 f2_in([]) 7.65/2.89 f2_in(.(x0, x1)) 7.65/2.89 U1(f121_out1, .(x0, x1)) 7.65/2.89 f121_in(x0, x1) 7.65/2.89 U3(f166_out1, x0, x1) 7.65/2.89 U4(f2_out1, x0, x1) 7.65/2.89 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (54) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 F2_IN(.(T14, T15)) -> F121_IN(T14, T15) 7.65/2.89 F121_IN(T14, T15) -> U3^1(f166_in(T14), T14, T15) 7.65/2.89 U3^1(f166_out1, T14, T15) -> F2_IN(T15) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 f166_in(T35) -> f166_out1 7.65/2.89 f166_in(T43) -> U2(f166_in(T43), T43) 7.65/2.89 U2(f166_out1, T43) -> f166_out1 7.65/2.89 7.65/2.89 The set Q consists of the following terms: 7.65/2.89 7.65/2.89 f166_in(x0) 7.65/2.89 U2(f166_out1, x0) 7.65/2.89 7.65/2.89 We have to consider all minimal (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (55) QDPSizeChangeProof (EQUIVALENT) 7.65/2.89 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 7.65/2.89 7.65/2.89 From the DPs we obtained the following set of size-change graphs: 7.65/2.89 *F121_IN(T14, T15) -> U3^1(f166_in(T14), T14, T15) 7.65/2.89 The graph contains the following edges 1 >= 2, 2 >= 3 7.65/2.89 7.65/2.89 7.65/2.89 *U3^1(f166_out1, T14, T15) -> F2_IN(T15) 7.65/2.89 The graph contains the following edges 3 >= 1 7.65/2.89 7.65/2.89 7.65/2.89 *F2_IN(.(T14, T15)) -> F121_IN(T14, T15) 7.65/2.89 The graph contains the following edges 1 > 1, 1 > 2 7.65/2.89 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (56) 7.65/2.89 YES 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (57) PrologToDTProblemTransformerProof (SOUND) 7.65/2.89 Built DT problem from termination graph DT10. 7.65/2.89 7.65/2.89 { 7.65/2.89 "root": 1, 7.65/2.89 "program": { 7.65/2.89 "directives": [], 7.65/2.89 "clauses": [ 7.65/2.89 [ 7.65/2.89 "(subset ([]) X1)", 7.65/2.89 null 7.65/2.89 ], 7.65/2.89 [ 7.65/2.89 "(subset (. X Xs) Ys)", 7.65/2.89 "(',' (member X Ys) (subset Xs Ys))" 7.65/2.89 ], 7.65/2.89 [ 7.65/2.89 "(member X (. X X2))", 7.65/2.89 null 7.65/2.89 ], 7.65/2.89 [ 7.65/2.89 "(member X (. X3 Xs))", 7.65/2.89 "(member X Xs)" 7.65/2.89 ] 7.65/2.89 ] 7.65/2.89 }, 7.65/2.89 "graph": { 7.65/2.89 "nodes": { 7.65/2.89 "192": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(member T33 T36)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T33"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "193": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(subset T9 (. T42 T43))" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T9"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "type": "Nodes", 7.65/2.89 "195": { 7.65/2.89 "goal": [ 7.65/2.89 { 7.65/2.89 "clause": 2, 7.65/2.89 "scope": 3, 7.65/2.89 "term": "(member T33 T36)" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "clause": 3, 7.65/2.89 "scope": 3, 7.65/2.89 "term": "(member T33 T36)" 7.65/2.89 } 7.65/2.89 ], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T33"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "198": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 2, 7.65/2.89 "scope": 3, 7.65/2.89 "term": "(member T33 T36)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T33"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "199": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 3, 7.65/2.89 "scope": 3, 7.65/2.89 "term": "(member T33 T36)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T33"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "71": { 7.65/2.89 "goal": [ 7.65/2.89 { 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(true)" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "clause": 1, 7.65/2.89 "scope": 1, 7.65/2.89 "term": "(subset ([]) T2)" 7.65/2.89 } 7.65/2.89 ], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "72": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 1, 7.65/2.89 "scope": 1, 7.65/2.89 "term": "(subset T1 T2)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [[ 7.65/2.89 "(subset T1 T2)", 7.65/2.89 "(subset ([]) X5)" 7.65/2.89 ]], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T1"], 7.65/2.89 "free": ["X5"], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "73": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 1, 7.65/2.89 "scope": 1, 7.65/2.89 "term": "(subset ([]) T2)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "74": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "75": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(',' (member T8 T11) (subset T9 T11))" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [ 7.65/2.89 "T8", 7.65/2.89 "T9" 7.65/2.89 ], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "76": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "77": { 7.65/2.89 "goal": [ 7.65/2.89 { 7.65/2.89 "clause": 2, 7.65/2.89 "scope": 2, 7.65/2.89 "term": "(',' (member T8 T11) (subset T9 T11))" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "clause": 3, 7.65/2.89 "scope": 2, 7.65/2.89 "term": "(',' (member T8 T11) (subset T9 T11))" 7.65/2.89 } 7.65/2.89 ], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [ 7.65/2.89 "T8", 7.65/2.89 "T9" 7.65/2.89 ], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "78": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 2, 7.65/2.89 "scope": 2, 7.65/2.89 "term": "(',' (member T8 T11) (subset T9 T11))" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [ 7.65/2.89 "T8", 7.65/2.89 "T9" 7.65/2.89 ], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "79": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 3, 7.65/2.89 "scope": 2, 7.65/2.89 "term": "(',' (member T8 T11) (subset T9 T11))" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [ 7.65/2.89 "T8", 7.65/2.89 "T9" 7.65/2.89 ], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "182": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(',' (member T33 T36) (subset T9 (. T37 T36)))" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [ 7.65/2.89 "T9", 7.65/2.89 "T33" 7.65/2.89 ], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "183": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "164": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(subset T9 (. T20 T22))" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [ 7.65/2.89 "T9", 7.65/2.89 "T20" 7.65/2.89 ], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "165": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "1": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(subset T1 T2)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T1"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "200": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(true)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "3": { 7.65/2.89 "goal": [ 7.65/2.89 { 7.65/2.89 "clause": 0, 7.65/2.89 "scope": 1, 7.65/2.89 "term": "(subset T1 T2)" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "clause": 1, 7.65/2.89 "scope": 1, 7.65/2.89 "term": "(subset T1 T2)" 7.65/2.89 } 7.65/2.89 ], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T1"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "201": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "202": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "203": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(member T64 T67)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T64"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "204": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "edges": [ 7.65/2.89 { 7.65/2.89 "from": 1, 7.65/2.89 "to": 3, 7.65/2.89 "label": "CASE" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 3, 7.65/2.89 "to": 71, 7.65/2.89 "label": "EVAL with clause\nsubset([], X5).\nand substitutionT1 -> [],\nT2 -> T4,\nX5 -> T4" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 3, 7.65/2.89 "to": 72, 7.65/2.89 "label": "EVAL-BACKTRACK" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 71, 7.65/2.89 "to": 73, 7.65/2.89 "label": "SUCCESS" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 72, 7.65/2.89 "to": 75, 7.65/2.89 "label": "EVAL with clause\nsubset(.(X12, X13), X14) :- ','(member(X12, X14), subset(X13, X14)).\nand substitutionX12 -> T8,\nX13 -> T9,\nT1 -> .(T8, T9),\nT2 -> T11,\nX14 -> T11,\nT10 -> T11" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 72, 7.65/2.89 "to": 76, 7.65/2.89 "label": "EVAL-BACKTRACK" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 73, 7.65/2.89 "to": 74, 7.65/2.89 "label": "BACKTRACK\nfor clause: subset(.(X, Xs), Ys) :- ','(member(X, Ys), subset(Xs, Ys))because of non-unification" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 75, 7.65/2.89 "to": 77, 7.65/2.89 "label": "CASE" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 77, 7.65/2.89 "to": 78, 7.65/2.89 "label": "PARALLEL" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 77, 7.65/2.89 "to": 79, 7.65/2.89 "label": "PARALLEL" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 78, 7.65/2.89 "to": 164, 7.65/2.89 "label": "EVAL with clause\nmember(X23, .(X23, X24)).\nand substitutionT8 -> T20,\nX23 -> T20,\nX24 -> T22,\nT11 -> .(T20, T22),\nT21 -> T22" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 78, 7.65/2.89 "to": 165, 7.65/2.89 "label": "EVAL-BACKTRACK" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 79, 7.65/2.89 "to": 182, 7.65/2.89 "label": "EVAL with clause\nmember(X33, .(X34, X35)) :- member(X33, X35).\nand substitutionT8 -> T33,\nX33 -> T33,\nX34 -> T37,\nX35 -> T36,\nT11 -> .(T37, T36),\nT35 -> T36,\nT34 -> T37" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 79, 7.65/2.89 "to": 183, 7.65/2.89 "label": "EVAL-BACKTRACK" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 164, 7.65/2.89 "to": 1, 7.65/2.89 "label": "INSTANCE with matching:\nT1 -> T9\nT2 -> .(T20, T22)" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 182, 7.65/2.89 "to": 192, 7.65/2.89 "label": "SPLIT 1" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 182, 7.65/2.89 "to": 193, 7.65/2.89 "label": "SPLIT 2\nnew knowledge:\nT33 is ground\nreplacements:T37 -> T42,\nT36 -> T43" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 192, 7.65/2.89 "to": 195, 7.65/2.89 "label": "CASE" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 193, 7.65/2.89 "to": 1, 7.65/2.89 "label": "INSTANCE with matching:\nT1 -> T9\nT2 -> .(T42, T43)" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 195, 7.65/2.89 "to": 198, 7.65/2.89 "label": "PARALLEL" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 195, 7.65/2.89 "to": 199, 7.65/2.89 "label": "PARALLEL" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 198, 7.65/2.89 "to": 200, 7.65/2.89 "label": "EVAL with clause\nmember(X52, .(X52, X53)).\nand substitutionT33 -> T56,\nX52 -> T56,\nX53 -> T57,\nT36 -> .(T56, T57)" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 198, 7.65/2.89 "to": 201, 7.65/2.89 "label": "EVAL-BACKTRACK" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 199, 7.65/2.89 "to": 203, 7.65/2.89 "label": "EVAL with clause\nmember(X60, .(X61, X62)) :- member(X60, X62).\nand substitutionT33 -> T64,\nX60 -> T64,\nX61 -> T65,\nX62 -> T67,\nT36 -> .(T65, T67),\nT66 -> T67" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 199, 7.65/2.89 "to": 204, 7.65/2.89 "label": "EVAL-BACKTRACK" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 200, 7.65/2.89 "to": 202, 7.65/2.89 "label": "SUCCESS" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "from": 203, 7.65/2.89 "to": 192, 7.65/2.89 "label": "INSTANCE with matching:\nT33 -> T64\nT36 -> T67" 7.65/2.89 } 7.65/2.89 ], 7.65/2.89 "type": "Graph" 7.65/2.89 } 7.65/2.89 } 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (58) 7.65/2.89 Obligation: 7.65/2.89 Triples: 7.65/2.89 7.65/2.89 memberB(X1, .(X2, X3)) :- memberB(X1, X3). 7.65/2.89 subsetA(.(X1, X2), .(X1, X3)) :- subsetA(X2, .(X1, X3)). 7.65/2.89 subsetA(.(X1, X2), .(X3, X4)) :- memberB(X1, X4). 7.65/2.89 subsetA(.(X1, X2), .(X3, X4)) :- ','(membercB(X1, X4), subsetA(X2, .(X3, X4))). 7.65/2.89 7.65/2.89 Clauses: 7.65/2.89 7.65/2.89 subsetcA([], X1). 7.65/2.89 subsetcA(.(X1, X2), .(X1, X3)) :- subsetcA(X2, .(X1, X3)). 7.65/2.89 subsetcA(.(X1, X2), .(X3, X4)) :- ','(membercB(X1, X4), subsetcA(X2, .(X3, X4))). 7.65/2.89 membercB(X1, .(X1, X2)). 7.65/2.89 membercB(X1, .(X2, X3)) :- membercB(X1, X3). 7.65/2.89 7.65/2.89 Afs: 7.65/2.89 7.65/2.89 subsetA(x1, x2) = subsetA(x1) 7.65/2.89 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (59) TriplesToPiDPProof (SOUND) 7.65/2.89 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 7.65/2.89 7.65/2.89 subsetA_in_2: (b,f) 7.65/2.89 7.65/2.89 memberB_in_2: (f,f) 7.65/2.89 7.65/2.89 membercB_in_2: (f,f) 7.65/2.89 7.65/2.89 Transforming TRIPLES into the following Term Rewriting System: 7.65/2.89 7.65/2.89 Pi DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X1, X3)) -> U2_GA(X1, X2, X3, subsetA_in_ga(X2, .(X1, X3))) 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X1, X3)) -> SUBSETA_IN_GA(X2, .(X1, X3)) 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X3, X4)) -> U3_GA(X1, X2, X3, X4, memberB_in_aa(X1, X4)) 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X3, X4)) -> MEMBERB_IN_AA(X1, X4) 7.65/2.89 MEMBERB_IN_AA(X1, .(X2, X3)) -> U1_AA(X1, X2, X3, memberB_in_aa(X1, X3)) 7.65/2.89 MEMBERB_IN_AA(X1, .(X2, X3)) -> MEMBERB_IN_AA(X1, X3) 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X3, X4)) -> U4_GA(X1, X2, X3, X4, membercB_in_aa(X1, X4)) 7.65/2.89 U4_GA(X1, X2, X3, X4, membercB_out_aa(X1, X4)) -> U5_GA(X1, X2, X3, X4, subsetA_in_ga(X2, .(X3, X4))) 7.65/2.89 U4_GA(X1, X2, X3, X4, membercB_out_aa(X1, X4)) -> SUBSETA_IN_GA(X2, .(X3, X4)) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 membercB_in_aa(X1, .(X1, X2)) -> membercB_out_aa(X1, .(X1, X2)) 7.65/2.89 membercB_in_aa(X1, .(X2, X3)) -> U10_aa(X1, X2, X3, membercB_in_aa(X1, X3)) 7.65/2.89 U10_aa(X1, X2, X3, membercB_out_aa(X1, X3)) -> membercB_out_aa(X1, .(X2, X3)) 7.65/2.89 7.65/2.89 The argument filtering Pi contains the following mapping: 7.65/2.89 subsetA_in_ga(x1, x2) = subsetA_in_ga(x1) 7.65/2.89 7.65/2.89 .(x1, x2) = .(x2) 7.65/2.89 7.65/2.89 memberB_in_aa(x1, x2) = memberB_in_aa 7.65/2.89 7.65/2.89 membercB_in_aa(x1, x2) = membercB_in_aa 7.65/2.89 7.65/2.89 membercB_out_aa(x1, x2) = membercB_out_aa 7.65/2.89 7.65/2.89 U10_aa(x1, x2, x3, x4) = U10_aa(x4) 7.65/2.89 7.65/2.89 SUBSETA_IN_GA(x1, x2) = SUBSETA_IN_GA(x1) 7.65/2.89 7.65/2.89 U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) 7.65/2.89 7.65/2.89 U3_GA(x1, x2, x3, x4, x5) = U3_GA(x2, x5) 7.65/2.89 7.65/2.89 MEMBERB_IN_AA(x1, x2) = MEMBERB_IN_AA 7.65/2.89 7.65/2.89 U1_AA(x1, x2, x3, x4) = U1_AA(x4) 7.65/2.89 7.65/2.89 U4_GA(x1, x2, x3, x4, x5) = U4_GA(x2, x5) 7.65/2.89 7.65/2.89 U5_GA(x1, x2, x3, x4, x5) = U5_GA(x2, x5) 7.65/2.89 7.65/2.89 7.65/2.89 We have to consider all (P,R,Pi)-chains 7.65/2.89 7.65/2.89 7.65/2.89 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 7.65/2.89 7.65/2.89 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (60) 7.65/2.89 Obligation: 7.65/2.89 Pi DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X1, X3)) -> U2_GA(X1, X2, X3, subsetA_in_ga(X2, .(X1, X3))) 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X1, X3)) -> SUBSETA_IN_GA(X2, .(X1, X3)) 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X3, X4)) -> U3_GA(X1, X2, X3, X4, memberB_in_aa(X1, X4)) 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X3, X4)) -> MEMBERB_IN_AA(X1, X4) 7.65/2.89 MEMBERB_IN_AA(X1, .(X2, X3)) -> U1_AA(X1, X2, X3, memberB_in_aa(X1, X3)) 7.65/2.89 MEMBERB_IN_AA(X1, .(X2, X3)) -> MEMBERB_IN_AA(X1, X3) 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X3, X4)) -> U4_GA(X1, X2, X3, X4, membercB_in_aa(X1, X4)) 7.65/2.89 U4_GA(X1, X2, X3, X4, membercB_out_aa(X1, X4)) -> U5_GA(X1, X2, X3, X4, subsetA_in_ga(X2, .(X3, X4))) 7.65/2.89 U4_GA(X1, X2, X3, X4, membercB_out_aa(X1, X4)) -> SUBSETA_IN_GA(X2, .(X3, X4)) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 membercB_in_aa(X1, .(X1, X2)) -> membercB_out_aa(X1, .(X1, X2)) 7.65/2.89 membercB_in_aa(X1, .(X2, X3)) -> U10_aa(X1, X2, X3, membercB_in_aa(X1, X3)) 7.65/2.89 U10_aa(X1, X2, X3, membercB_out_aa(X1, X3)) -> membercB_out_aa(X1, .(X2, X3)) 7.65/2.89 7.65/2.89 The argument filtering Pi contains the following mapping: 7.65/2.89 subsetA_in_ga(x1, x2) = subsetA_in_ga(x1) 7.65/2.89 7.65/2.89 .(x1, x2) = .(x2) 7.65/2.89 7.65/2.89 memberB_in_aa(x1, x2) = memberB_in_aa 7.65/2.89 7.65/2.89 membercB_in_aa(x1, x2) = membercB_in_aa 7.65/2.89 7.65/2.89 membercB_out_aa(x1, x2) = membercB_out_aa 7.65/2.89 7.65/2.89 U10_aa(x1, x2, x3, x4) = U10_aa(x4) 7.65/2.89 7.65/2.89 SUBSETA_IN_GA(x1, x2) = SUBSETA_IN_GA(x1) 7.65/2.89 7.65/2.89 U2_GA(x1, x2, x3, x4) = U2_GA(x2, x4) 7.65/2.89 7.65/2.89 U3_GA(x1, x2, x3, x4, x5) = U3_GA(x2, x5) 7.65/2.89 7.65/2.89 MEMBERB_IN_AA(x1, x2) = MEMBERB_IN_AA 7.65/2.89 7.65/2.89 U1_AA(x1, x2, x3, x4) = U1_AA(x4) 7.65/2.89 7.65/2.89 U4_GA(x1, x2, x3, x4, x5) = U4_GA(x2, x5) 7.65/2.89 7.65/2.89 U5_GA(x1, x2, x3, x4, x5) = U5_GA(x2, x5) 7.65/2.89 7.65/2.89 7.65/2.89 We have to consider all (P,R,Pi)-chains 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (61) DependencyGraphProof (EQUIVALENT) 7.65/2.89 The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 5 less nodes. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (62) 7.65/2.89 Complex Obligation (AND) 7.65/2.89 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (63) 7.65/2.89 Obligation: 7.65/2.89 Pi DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 MEMBERB_IN_AA(X1, .(X2, X3)) -> MEMBERB_IN_AA(X1, X3) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 membercB_in_aa(X1, .(X1, X2)) -> membercB_out_aa(X1, .(X1, X2)) 7.65/2.89 membercB_in_aa(X1, .(X2, X3)) -> U10_aa(X1, X2, X3, membercB_in_aa(X1, X3)) 7.65/2.89 U10_aa(X1, X2, X3, membercB_out_aa(X1, X3)) -> membercB_out_aa(X1, .(X2, X3)) 7.65/2.89 7.65/2.89 The argument filtering Pi contains the following mapping: 7.65/2.89 .(x1, x2) = .(x2) 7.65/2.89 7.65/2.89 membercB_in_aa(x1, x2) = membercB_in_aa 7.65/2.89 7.65/2.89 membercB_out_aa(x1, x2) = membercB_out_aa 7.65/2.89 7.65/2.89 U10_aa(x1, x2, x3, x4) = U10_aa(x4) 7.65/2.89 7.65/2.89 MEMBERB_IN_AA(x1, x2) = MEMBERB_IN_AA 7.65/2.89 7.65/2.89 7.65/2.89 We have to consider all (P,R,Pi)-chains 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (64) UsableRulesProof (EQUIVALENT) 7.65/2.89 For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (65) 7.65/2.89 Obligation: 7.65/2.89 Pi DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 MEMBERB_IN_AA(X1, .(X2, X3)) -> MEMBERB_IN_AA(X1, X3) 7.65/2.89 7.65/2.89 R is empty. 7.65/2.89 The argument filtering Pi contains the following mapping: 7.65/2.89 .(x1, x2) = .(x2) 7.65/2.89 7.65/2.89 MEMBERB_IN_AA(x1, x2) = MEMBERB_IN_AA 7.65/2.89 7.65/2.89 7.65/2.89 We have to consider all (P,R,Pi)-chains 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (66) PiDPToQDPProof (SOUND) 7.65/2.89 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (67) 7.65/2.89 Obligation: 7.65/2.89 Q DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 MEMBERB_IN_AA -> MEMBERB_IN_AA 7.65/2.89 7.65/2.89 R is empty. 7.65/2.89 Q is empty. 7.65/2.89 We have to consider all (P,Q,R)-chains. 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (68) 7.65/2.89 Obligation: 7.65/2.89 Pi DP problem: 7.65/2.89 The TRS P consists of the following rules: 7.65/2.89 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X3, X4)) -> U4_GA(X1, X2, X3, X4, membercB_in_aa(X1, X4)) 7.65/2.89 U4_GA(X1, X2, X3, X4, membercB_out_aa(X1, X4)) -> SUBSETA_IN_GA(X2, .(X3, X4)) 7.65/2.89 SUBSETA_IN_GA(.(X1, X2), .(X1, X3)) -> SUBSETA_IN_GA(X2, .(X1, X3)) 7.65/2.89 7.65/2.89 The TRS R consists of the following rules: 7.65/2.89 7.65/2.89 membercB_in_aa(X1, .(X1, X2)) -> membercB_out_aa(X1, .(X1, X2)) 7.65/2.89 membercB_in_aa(X1, .(X2, X3)) -> U10_aa(X1, X2, X3, membercB_in_aa(X1, X3)) 7.65/2.89 U10_aa(X1, X2, X3, membercB_out_aa(X1, X3)) -> membercB_out_aa(X1, .(X2, X3)) 7.65/2.89 7.65/2.89 The argument filtering Pi contains the following mapping: 7.65/2.89 .(x1, x2) = .(x2) 7.65/2.89 7.65/2.89 membercB_in_aa(x1, x2) = membercB_in_aa 7.65/2.89 7.65/2.89 membercB_out_aa(x1, x2) = membercB_out_aa 7.65/2.89 7.65/2.89 U10_aa(x1, x2, x3, x4) = U10_aa(x4) 7.65/2.89 7.65/2.89 SUBSETA_IN_GA(x1, x2) = SUBSETA_IN_GA(x1) 7.65/2.89 7.65/2.89 U4_GA(x1, x2, x3, x4, x5) = U4_GA(x2, x5) 7.65/2.89 7.65/2.89 7.65/2.89 We have to consider all (P,R,Pi)-chains 7.65/2.89 ---------------------------------------- 7.65/2.89 7.65/2.89 (69) PrologToIRSwTTransformerProof (SOUND) 7.65/2.89 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 7.65/2.89 7.65/2.89 { 7.65/2.89 "root": 4, 7.65/2.89 "program": { 7.65/2.89 "directives": [], 7.65/2.89 "clauses": [ 7.65/2.89 [ 7.65/2.89 "(subset ([]) X1)", 7.65/2.89 null 7.65/2.89 ], 7.65/2.89 [ 7.65/2.89 "(subset (. X Xs) Ys)", 7.65/2.89 "(',' (member X Ys) (subset Xs Ys))" 7.65/2.89 ], 7.65/2.89 [ 7.65/2.89 "(member X (. X X2))", 7.65/2.89 null 7.65/2.89 ], 7.65/2.89 [ 7.65/2.89 "(member X (. X3 Xs))", 7.65/2.89 "(member X Xs)" 7.65/2.89 ] 7.65/2.89 ] 7.65/2.89 }, 7.65/2.89 "graph": { 7.65/2.89 "nodes": { 7.65/2.89 "88": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(',' (member T14 T17) (subset T15 T17))" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [ 7.65/2.89 "T14", 7.65/2.89 "T15" 7.65/2.89 ], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "23": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 0, 7.65/2.89 "scope": 1, 7.65/2.89 "term": "(subset T1 T2)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T1"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "89": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "24": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 1, 7.65/2.89 "scope": 1, 7.65/2.89 "term": "(subset T1 T2)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T1"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "190": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(true)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "191": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "type": "Nodes", 7.65/2.89 "161": { 7.65/2.89 "goal": [ 7.65/2.89 { 7.65/2.89 "clause": 2, 7.65/2.89 "scope": 2, 7.65/2.89 "term": "(member T14 T17)" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "clause": 3, 7.65/2.89 "scope": 2, 7.65/2.89 "term": "(member T14 T17)" 7.65/2.89 } 7.65/2.89 ], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T14"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "194": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "151": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(subset T15 T22)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T15"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "162": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 2, 7.65/2.89 "scope": 2, 7.65/2.89 "term": "(member T14 T17)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T14"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "163": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": 3, 7.65/2.89 "scope": 2, 7.65/2.89 "term": "(member T14 T17)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T14"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "196": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(member T43 T46)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T43"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "197": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "4": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(subset T1 T2)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T1"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "5": { 7.65/2.89 "goal": [ 7.65/2.89 { 7.65/2.89 "clause": 0, 7.65/2.89 "scope": 1, 7.65/2.89 "term": "(subset T1 T2)" 7.65/2.89 }, 7.65/2.89 { 7.65/2.89 "clause": 1, 7.65/2.89 "scope": 1, 7.65/2.89 "term": "(subset T1 T2)" 7.65/2.89 } 7.65/2.89 ], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T1"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "149": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(member T14 T17)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": ["T14"], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "80": { 7.65/2.89 "goal": [{ 7.65/2.89 "clause": -1, 7.65/2.89 "scope": -1, 7.65/2.89 "term": "(true)" 7.65/2.89 }], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.89 }, 7.65/2.89 "ground": [], 7.65/2.89 "free": [], 7.65/2.89 "exprvars": [] 7.65/2.89 } 7.65/2.89 }, 7.65/2.89 "81": { 7.65/2.89 "goal": [], 7.65/2.89 "kb": { 7.65/2.89 "nonunifying": [], 7.65/2.89 "intvars": {}, 7.65/2.89 "arithmetic": { 7.65/2.89 "type": "PlainIntegerRelationState", 7.65/2.89 "relations": [] 7.65/2.90 }, 7.65/2.90 "ground": [], 7.65/2.90 "free": [], 7.65/2.90 "exprvars": [] 7.65/2.90 } 7.65/2.90 }, 7.65/2.90 "82": { 7.65/2.90 "goal": [], 7.65/2.90 "kb": { 7.65/2.90 "nonunifying": [], 7.65/2.90 "intvars": {}, 7.65/2.90 "arithmetic": { 7.65/2.90 "type": "PlainIntegerRelationState", 7.65/2.90 "relations": [] 7.65/2.90 }, 7.65/2.90 "ground": [], 7.65/2.90 "free": [], 7.65/2.90 "exprvars": [] 7.65/2.90 } 7.65/2.90 } 7.65/2.90 }, 7.65/2.90 "edges": [ 7.65/2.90 { 7.65/2.90 "from": 4, 7.65/2.90 "to": 5, 7.65/2.90 "label": "CASE" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 5, 7.65/2.90 "to": 23, 7.65/2.90 "label": "PARALLEL" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 5, 7.65/2.90 "to": 24, 7.65/2.90 "label": "PARALLEL" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 23, 7.65/2.90 "to": 80, 7.65/2.90 "label": "EVAL with clause\nsubset([], X8).\nand substitutionT1 -> [],\nT2 -> T7,\nX8 -> T7" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 23, 7.65/2.90 "to": 81, 7.65/2.90 "label": "EVAL-BACKTRACK" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 24, 7.65/2.90 "to": 88, 7.65/2.90 "label": "EVAL with clause\nsubset(.(X15, X16), X17) :- ','(member(X15, X17), subset(X16, X17)).\nand substitutionX15 -> T14,\nX16 -> T15,\nT1 -> .(T14, T15),\nT2 -> T17,\nX17 -> T17,\nT16 -> T17" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 24, 7.65/2.90 "to": 89, 7.65/2.90 "label": "EVAL-BACKTRACK" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 80, 7.65/2.90 "to": 82, 7.65/2.90 "label": "SUCCESS" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 88, 7.65/2.90 "to": 149, 7.65/2.90 "label": "SPLIT 1" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 88, 7.65/2.90 "to": 151, 7.65/2.90 "label": "SPLIT 2\nnew knowledge:\nT14 is ground\nreplacements:T17 -> T22" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 149, 7.65/2.90 "to": 161, 7.65/2.90 "label": "CASE" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 151, 7.65/2.90 "to": 4, 7.65/2.90 "label": "INSTANCE with matching:\nT1 -> T15\nT2 -> T22" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 161, 7.65/2.90 "to": 162, 7.65/2.90 "label": "PARALLEL" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 161, 7.65/2.90 "to": 163, 7.65/2.90 "label": "PARALLEL" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 162, 7.65/2.90 "to": 190, 7.65/2.90 "label": "EVAL with clause\nmember(X34, .(X34, X35)).\nand substitutionT14 -> T35,\nX34 -> T35,\nX35 -> T36,\nT17 -> .(T35, T36)" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 162, 7.65/2.90 "to": 191, 7.65/2.90 "label": "EVAL-BACKTRACK" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 163, 7.65/2.90 "to": 196, 7.65/2.90 "label": "EVAL with clause\nmember(X42, .(X43, X44)) :- member(X42, X44).\nand substitutionT14 -> T43,\nX42 -> T43,\nX43 -> T44,\nX44 -> T46,\nT17 -> .(T44, T46),\nT45 -> T46" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 163, 7.65/2.90 "to": 197, 7.65/2.90 "label": "EVAL-BACKTRACK" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 190, 7.65/2.90 "to": 194, 7.65/2.90 "label": "SUCCESS" 7.65/2.90 }, 7.65/2.90 { 7.65/2.90 "from": 196, 7.65/2.90 "to": 149, 7.65/2.90 "label": "INSTANCE with matching:\nT14 -> T43\nT17 -> T46" 7.65/2.90 } 7.65/2.90 ], 7.65/2.90 "type": "Graph" 7.65/2.90 } 7.65/2.90 } 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (70) 7.65/2.90 Complex Obligation (AND) 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (71) 7.65/2.90 Obligation: 7.65/2.90 Rules: 7.65/2.90 f196_in(T43) -> f149_in(T43) :|: TRUE 7.65/2.90 f149_out(x) -> f196_out(x) :|: TRUE 7.65/2.90 f161_out(T14) -> f149_out(T14) :|: TRUE 7.65/2.90 f149_in(x1) -> f161_in(x1) :|: TRUE 7.65/2.90 f162_out(x2) -> f161_out(x2) :|: TRUE 7.65/2.90 f163_out(x3) -> f161_out(x3) :|: TRUE 7.65/2.90 f161_in(x4) -> f163_in(x4) :|: TRUE 7.65/2.90 f161_in(x5) -> f162_in(x5) :|: TRUE 7.65/2.90 f196_out(x6) -> f163_out(x6) :|: TRUE 7.65/2.90 f197_out -> f163_out(x7) :|: TRUE 7.65/2.90 f163_in(x8) -> f197_in :|: TRUE 7.65/2.90 f163_in(x9) -> f196_in(x9) :|: TRUE 7.65/2.90 f5_out(T1) -> f4_out(T1) :|: TRUE 7.65/2.90 f4_in(x10) -> f5_in(x10) :|: TRUE 7.65/2.90 f5_in(x11) -> f24_in(x11) :|: TRUE 7.65/2.90 f24_out(x12) -> f5_out(x12) :|: TRUE 7.65/2.90 f5_in(x13) -> f23_in(x13) :|: TRUE 7.65/2.90 f23_out(x14) -> f5_out(x14) :|: TRUE 7.65/2.90 f24_in(x15) -> f89_in :|: TRUE 7.65/2.90 f89_out -> f24_out(x16) :|: TRUE 7.65/2.90 f88_out(x17, x18) -> f24_out(.(x17, x18)) :|: TRUE 7.65/2.90 f24_in(.(x19, x20)) -> f88_in(x19, x20) :|: TRUE 7.65/2.90 f88_in(x21, x22) -> f149_in(x21) :|: TRUE 7.65/2.90 f151_out(x23) -> f88_out(x24, x23) :|: TRUE 7.65/2.90 f149_out(x25) -> f151_in(x26) :|: TRUE 7.65/2.90 Start term: f4_in(T1) 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (72) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 7.65/2.90 Constructed simple dependency graph. 7.65/2.90 7.65/2.90 Simplified to the following IRSwTs: 7.65/2.90 7.65/2.90 intTRSProblem: 7.65/2.90 f196_in(T43) -> f149_in(T43) :|: TRUE 7.65/2.90 f149_in(x1) -> f161_in(x1) :|: TRUE 7.65/2.90 f161_in(x4) -> f163_in(x4) :|: TRUE 7.65/2.90 f163_in(x9) -> f196_in(x9) :|: TRUE 7.65/2.90 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (73) 7.65/2.90 Obligation: 7.65/2.90 Rules: 7.65/2.90 f196_in(T43) -> f149_in(T43) :|: TRUE 7.65/2.90 f149_in(x1) -> f161_in(x1) :|: TRUE 7.65/2.90 f161_in(x4) -> f163_in(x4) :|: TRUE 7.65/2.90 f163_in(x9) -> f196_in(x9) :|: TRUE 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (74) IntTRSCompressionProof (EQUIVALENT) 7.65/2.90 Compressed rules. 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (75) 7.65/2.90 Obligation: 7.65/2.90 Rules: 7.65/2.90 f196_in(T43:0) -> f196_in(T43:0) :|: TRUE 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (76) IRSFormatTransformerProof (EQUIVALENT) 7.65/2.90 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (77) 7.65/2.90 Obligation: 7.65/2.90 Rules: 7.65/2.90 f196_in(T43:0) -> f196_in(T43:0) :|: TRUE 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (78) IRSwTTerminationDigraphProof (EQUIVALENT) 7.65/2.90 Constructed termination digraph! 7.65/2.90 Nodes: 7.65/2.90 (1) f196_in(T43:0) -> f196_in(T43:0) :|: TRUE 7.65/2.90 7.65/2.90 Arcs: 7.65/2.90 (1) -> (1) 7.65/2.90 7.65/2.90 This digraph is fully evaluated! 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (79) 7.65/2.90 Obligation: 7.65/2.90 7.65/2.90 Termination digraph: 7.65/2.90 Nodes: 7.65/2.90 (1) f196_in(T43:0) -> f196_in(T43:0) :|: TRUE 7.65/2.90 7.65/2.90 Arcs: 7.65/2.90 (1) -> (1) 7.65/2.90 7.65/2.90 This digraph is fully evaluated! 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (80) FilterProof (EQUIVALENT) 7.65/2.90 Used the following sort dictionary for filtering: 7.65/2.90 f196_in(VARIABLE) 7.65/2.90 Replaced non-predefined constructor symbols by 0. 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (81) 7.65/2.90 Obligation: 7.65/2.90 Rules: 7.65/2.90 f196_in(T43:0) -> f196_in(T43:0) :|: TRUE 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (82) IntTRSNonPeriodicNontermProof (COMPLETE) 7.65/2.90 Normalized system to the following form: 7.65/2.90 f(pc, T43:0) -> f(1, T43:0) :|: pc = 1 && TRUE 7.65/2.90 Proved unsatisfiability of the following formula, indicating that the system is never left after entering: 7.65/2.90 (((run2_0 = ((1 * 1)) and run2_1 = ((run1_1 * 1))) and (((run1_0 * 1)) = ((1 * 1)) and T)) and !(((run2_0 * 1)) = ((1 * 1)) and T)) 7.65/2.90 Proved satisfiability of the following formula, indicating that the system is entered at least once: 7.65/2.90 ((run2_0 = ((1 * 1)) and run2_1 = ((run1_1 * 1))) and (((run1_0 * 1)) = ((1 * 1)) and T)) 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (83) 7.65/2.90 NO 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (84) 7.65/2.90 Obligation: 7.65/2.90 Rules: 7.65/2.90 f5_in(T1) -> f24_in(T1) :|: TRUE 7.65/2.90 f24_out(x) -> f5_out(x) :|: TRUE 7.65/2.90 f5_in(x1) -> f23_in(x1) :|: TRUE 7.65/2.90 f23_out(x2) -> f5_out(x2) :|: TRUE 7.65/2.90 f24_in(x3) -> f89_in :|: TRUE 7.65/2.90 f89_out -> f24_out(x4) :|: TRUE 7.65/2.90 f88_out(T14, T15) -> f24_out(.(T14, T15)) :|: TRUE 7.65/2.90 f24_in(.(x5, x6)) -> f88_in(x5, x6) :|: TRUE 7.65/2.90 f162_out(x7) -> f161_out(x7) :|: TRUE 7.65/2.90 f163_out(x8) -> f161_out(x8) :|: TRUE 7.65/2.90 f161_in(x9) -> f163_in(x9) :|: TRUE 7.65/2.90 f161_in(x10) -> f162_in(x10) :|: TRUE 7.65/2.90 f196_in(T43) -> f149_in(T43) :|: TRUE 7.65/2.90 f149_out(x11) -> f196_out(x11) :|: TRUE 7.65/2.90 f190_in -> f190_out :|: TRUE 7.65/2.90 f162_in(x12) -> f191_in :|: TRUE 7.65/2.90 f162_in(T35) -> f190_in :|: TRUE 7.65/2.90 f191_out -> f162_out(x13) :|: TRUE 7.65/2.90 f190_out -> f162_out(x14) :|: TRUE 7.65/2.90 f88_in(x15, x16) -> f149_in(x15) :|: TRUE 7.65/2.90 f151_out(x17) -> f88_out(x18, x17) :|: TRUE 7.65/2.90 f149_out(x19) -> f151_in(x20) :|: TRUE 7.65/2.90 f5_out(x21) -> f4_out(x21) :|: TRUE 7.65/2.90 f4_in(x22) -> f5_in(x22) :|: TRUE 7.65/2.90 f161_out(x23) -> f149_out(x23) :|: TRUE 7.65/2.90 f149_in(x24) -> f161_in(x24) :|: TRUE 7.65/2.90 f196_out(x25) -> f163_out(x25) :|: TRUE 7.65/2.90 f197_out -> f163_out(x26) :|: TRUE 7.65/2.90 f163_in(x27) -> f197_in :|: TRUE 7.65/2.90 f163_in(x28) -> f196_in(x28) :|: TRUE 7.65/2.90 f151_in(x29) -> f4_in(x29) :|: TRUE 7.65/2.90 f4_out(x30) -> f151_out(x30) :|: TRUE 7.65/2.90 Start term: f4_in(T1) 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (85) IRSwTSimpleDependencyGraphProof (EQUIVALENT) 7.65/2.90 Constructed simple dependency graph. 7.65/2.90 7.65/2.90 Simplified to the following IRSwTs: 7.65/2.90 7.65/2.90 intTRSProblem: 7.65/2.90 f5_in(T1) -> f24_in(T1) :|: TRUE 7.65/2.90 f24_in(.(x5, x6)) -> f88_in(x5, x6) :|: TRUE 7.65/2.90 f162_out(x7) -> f161_out(x7) :|: TRUE 7.65/2.90 f163_out(x8) -> f161_out(x8) :|: TRUE 7.65/2.90 f161_in(x9) -> f163_in(x9) :|: TRUE 7.65/2.90 f161_in(x10) -> f162_in(x10) :|: TRUE 7.65/2.90 f196_in(T43) -> f149_in(T43) :|: TRUE 7.65/2.90 f149_out(x11) -> f196_out(x11) :|: TRUE 7.65/2.90 f190_in -> f190_out :|: TRUE 7.65/2.90 f162_in(T35) -> f190_in :|: TRUE 7.65/2.90 f190_out -> f162_out(x14) :|: TRUE 7.65/2.90 f88_in(x15, x16) -> f149_in(x15) :|: TRUE 7.65/2.90 f149_out(x19) -> f151_in(x20) :|: TRUE 7.65/2.90 f4_in(x22) -> f5_in(x22) :|: TRUE 7.65/2.90 f161_out(x23) -> f149_out(x23) :|: TRUE 7.65/2.90 f149_in(x24) -> f161_in(x24) :|: TRUE 7.65/2.90 f196_out(x25) -> f163_out(x25) :|: TRUE 7.65/2.90 f163_in(x28) -> f196_in(x28) :|: TRUE 7.65/2.90 f151_in(x29) -> f4_in(x29) :|: TRUE 7.65/2.90 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (86) 7.65/2.90 Obligation: 7.65/2.90 Rules: 7.65/2.90 f5_in(T1) -> f24_in(T1) :|: TRUE 7.65/2.90 f24_in(.(x5, x6)) -> f88_in(x5, x6) :|: TRUE 7.65/2.90 f162_out(x7) -> f161_out(x7) :|: TRUE 7.65/2.90 f163_out(x8) -> f161_out(x8) :|: TRUE 7.65/2.90 f161_in(x9) -> f163_in(x9) :|: TRUE 7.65/2.90 f161_in(x10) -> f162_in(x10) :|: TRUE 7.65/2.90 f196_in(T43) -> f149_in(T43) :|: TRUE 7.65/2.90 f149_out(x11) -> f196_out(x11) :|: TRUE 7.65/2.90 f190_in -> f190_out :|: TRUE 7.65/2.90 f162_in(T35) -> f190_in :|: TRUE 7.65/2.90 f190_out -> f162_out(x14) :|: TRUE 7.65/2.90 f88_in(x15, x16) -> f149_in(x15) :|: TRUE 7.65/2.90 f149_out(x19) -> f151_in(x20) :|: TRUE 7.65/2.90 f4_in(x22) -> f5_in(x22) :|: TRUE 7.65/2.90 f161_out(x23) -> f149_out(x23) :|: TRUE 7.65/2.90 f149_in(x24) -> f161_in(x24) :|: TRUE 7.65/2.90 f196_out(x25) -> f163_out(x25) :|: TRUE 7.65/2.90 f163_in(x28) -> f196_in(x28) :|: TRUE 7.65/2.90 f151_in(x29) -> f4_in(x29) :|: TRUE 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (87) IntTRSCompressionProof (EQUIVALENT) 7.65/2.90 Compressed rules. 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (88) 7.65/2.90 Obligation: 7.65/2.90 Rules: 7.65/2.90 f161_in(x9:0) -> f161_in(x9:0) :|: TRUE 7.65/2.90 f149_out(x19:0) -> f161_in(x5:0) :|: TRUE 7.65/2.90 f149_out(x11:0) -> f149_out(x11:0) :|: TRUE 7.65/2.90 f161_in(x10:0) -> f149_out(x14:0) :|: TRUE 7.65/2.90 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (89) IRSFormatTransformerProof (EQUIVALENT) 7.65/2.90 Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). 7.65/2.90 ---------------------------------------- 7.65/2.90 7.65/2.90 (90) 7.65/2.90 Obligation: 7.65/2.90 Rules: 7.65/2.90 f161_in(x9:0) -> f161_in(x9:0) :|: TRUE 7.65/2.90 f149_out(x19:0) -> f161_in(x5:0) :|: TRUE 7.65/2.90 f149_out(x11:0) -> f149_out(x11:0) :|: TRUE 7.65/2.90 f161_in(x10:0) -> f149_out(x14:0) :|: TRUE 7.70/2.93 EOF