MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern sublist(g,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 13 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) PrologToPiTRSProof [SOUND, 0 ms] (20) PiTRS (21) DependencyPairsProof [EQUIVALENT, 6 ms] (22) PiDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) AND (25) PiDP (26) UsableRulesProof [EQUIVALENT, 0 ms] (27) PiDP (28) PiDPToQDPProof [SOUND, 0 ms] (29) QDP (30) QDPSizeChangeProof [EQUIVALENT, 0 ms] (31) YES (32) PiDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) PiDP (35) PiDPToQDPProof [SOUND, 0 ms] (36) QDP (37) PrologToDTProblemTransformerProof [SOUND, 0 ms] (38) TRIPLES (39) TriplesToPiDPProof [SOUND, 0 ms] (40) PiDP (41) DependencyGraphProof [EQUIVALENT, 0 ms] (42) AND (43) PiDP (44) PiDPToQDPProof [SOUND, 0 ms] (45) QDP (46) QDPSizeChangeProof [EQUIVALENT, 0 ms] (47) YES (48) PiDP (49) PiDPToQDPProof [SOUND, 0 ms] (50) QDP (51) PrologToTRSTransformerProof [SOUND, 22 ms] (52) QTRS (53) QTRSRRRProof [EQUIVALENT, 49 ms] (54) QTRS (55) QTRSRRRProof [EQUIVALENT, 3 ms] (56) QTRS (57) Overlay + Local Confluence [EQUIVALENT, 0 ms] (58) QTRS (59) DependencyPairsProof [EQUIVALENT, 0 ms] (60) QDP (61) UsableRulesProof [EQUIVALENT, 0 ms] (62) QDP (63) QReductionProof [EQUIVALENT, 0 ms] (64) QDP (65) PrologToIRSwTTransformerProof [SOUND, 36 ms] (66) AND (67) IRSwT (68) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (69) TRUE (70) IRSwT (71) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (72) IRSwT (73) IntTRSCompressionProof [EQUIVALENT, 20 ms] (74) IRSwT (75) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (76) IRSwT (77) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (78) IRSwT (79) FilterProof [EQUIVALENT, 0 ms] (80) IntTRS (81) IntTRSPeriodicNontermProof [COMPLETE, 0 ms] (82) NO ---------------------------------------- (0) Obligation: Clauses: sublist(Xs, Ys) :- ','(app(X1, Zs, Ys), app(Xs, X2, Zs)). app([], X, X). app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). Query: sublist(g,a) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: sublist_in_2: (b,f) app_in_3: (f,f,f) (b,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) sublist_out_ga(x1, x2) = sublist_out_ga Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) sublist_out_ga(x1, x2) = sublist_out_ga ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: SUBLIST_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, app_in_aaa(X1, Zs, Ys)) SUBLIST_IN_GA(Xs, Ys) -> APP_IN_AAA(X1, Zs, Ys) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_GA(Xs, Ys, app_in_gaa(Xs, X2, Zs)) U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> APP_IN_GAA(Xs, X2, Zs) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) sublist_out_ga(x1, x2) = sublist_out_ga SUBLIST_IN_GA(x1, x2) = SUBLIST_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) U2_GA(x1, x2, x3) = U2_GA(x3) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: SUBLIST_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, app_in_aaa(X1, Zs, Ys)) SUBLIST_IN_GA(Xs, Ys) -> APP_IN_AAA(X1, Zs, Ys) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_GA(Xs, Ys, app_in_gaa(Xs, X2, Zs)) U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> APP_IN_GAA(Xs, X2, Zs) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) sublist_out_ga(x1, x2) = sublist_out_ga SUBLIST_IN_GA(x1, x2) = SUBLIST_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) U2_GA(x1, x2, x3) = U2_GA(x3) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) sublist_out_ga(x1, x2) = sublist_out_ga APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x5) sublist_out_ga(x1, x2) = sublist_out_ga APP_IN_AAA(x1, x2, x3) = APP_IN_AAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_AAA -> APP_IN_AAA R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: sublist_in_2: (b,f) app_in_3: (f,f,f) (b,f,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x1, x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) sublist_out_ga(x1, x2) = sublist_out_ga(x1) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (20) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x1, x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) sublist_out_ga(x1, x2) = sublist_out_ga(x1) ---------------------------------------- (21) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LOPSTR] we result in the following initial DP problem: Pi DP problem: The TRS P consists of the following rules: SUBLIST_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, app_in_aaa(X1, Zs, Ys)) SUBLIST_IN_GA(Xs, Ys) -> APP_IN_AAA(X1, Zs, Ys) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_GA(Xs, Ys, app_in_gaa(Xs, X2, Zs)) U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> APP_IN_GAA(Xs, X2, Zs) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x1, x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) sublist_out_ga(x1, x2) = sublist_out_ga(x1) SUBLIST_IN_GA(x1, x2) = SUBLIST_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) U2_GA(x1, x2, x3) = U2_GA(x1, x3) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x2, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) Obligation: Pi DP problem: The TRS P consists of the following rules: SUBLIST_IN_GA(Xs, Ys) -> U1_GA(Xs, Ys, app_in_aaa(X1, Zs, Ys)) SUBLIST_IN_GA(Xs, Ys) -> APP_IN_AAA(X1, Zs, Ys) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> U3_AAA(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_GA(Xs, Ys, app_in_gaa(Xs, X2, Zs)) U1_GA(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> APP_IN_GAA(Xs, X2, Zs) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> U3_GAA(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x1, x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) sublist_out_ga(x1, x2) = sublist_out_ga(x1) SUBLIST_IN_GA(x1, x2) = SUBLIST_IN_GA(x1) U1_GA(x1, x2, x3) = U1_GA(x1, x3) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA U3_AAA(x1, x2, x3, x4, x5) = U3_AAA(x5) U2_GA(x1, x2, x3) = U2_GA(x1, x3) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) U3_GAA(x1, x2, x3, x4, x5) = U3_GAA(x2, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (23) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (24) Complex Obligation (AND) ---------------------------------------- (25) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x1, x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) sublist_out_ga(x1, x2) = sublist_out_ga(x1) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (26) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (27) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GAA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GAA(x1, x2, x3) = APP_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (28) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (30) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *APP_IN_GAA(.(Xs)) -> APP_IN_GAA(Xs) The graph contains the following edges 1 > 1 ---------------------------------------- (31) YES ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) The TRS R consists of the following rules: sublist_in_ga(Xs, Ys) -> U1_ga(Xs, Ys, app_in_aaa(X1, Zs, Ys)) app_in_aaa([], X, X) -> app_out_aaa([], X, X) app_in_aaa(.(X, Xs), Ys, .(X, Zs)) -> U3_aaa(X, Xs, Ys, Zs, app_in_aaa(Xs, Ys, Zs)) U3_aaa(X, Xs, Ys, Zs, app_out_aaa(Xs, Ys, Zs)) -> app_out_aaa(.(X, Xs), Ys, .(X, Zs)) U1_ga(Xs, Ys, app_out_aaa(X1, Zs, Ys)) -> U2_ga(Xs, Ys, app_in_gaa(Xs, X2, Zs)) app_in_gaa([], X, X) -> app_out_gaa([], X, X) app_in_gaa(.(X, Xs), Ys, .(X, Zs)) -> U3_gaa(X, Xs, Ys, Zs, app_in_gaa(Xs, Ys, Zs)) U3_gaa(X, Xs, Ys, Zs, app_out_gaa(Xs, Ys, Zs)) -> app_out_gaa(.(X, Xs), Ys, .(X, Zs)) U2_ga(Xs, Ys, app_out_gaa(Xs, X2, Zs)) -> sublist_out_ga(Xs, Ys) The argument filtering Pi contains the following mapping: sublist_in_ga(x1, x2) = sublist_in_ga(x1) U1_ga(x1, x2, x3) = U1_ga(x1, x3) app_in_aaa(x1, x2, x3) = app_in_aaa app_out_aaa(x1, x2, x3) = app_out_aaa(x1) U3_aaa(x1, x2, x3, x4, x5) = U3_aaa(x5) .(x1, x2) = .(x2) U2_ga(x1, x2, x3) = U2_ga(x1, x3) app_in_gaa(x1, x2, x3) = app_in_gaa(x1) [] = [] app_out_gaa(x1, x2, x3) = app_out_gaa(x1) U3_gaa(x1, x2, x3, x4, x5) = U3_gaa(x2, x5) sublist_out_ga(x1, x2) = sublist_out_ga(x1) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_AAA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_AAA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_AAA(x1, x2, x3) = APP_IN_AAA We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_AAA -> APP_IN_AAA R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(sublist Xs Ys)", "(',' (app X1 Zs Ys) (app Xs X2 Zs))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "182": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app X80 X81 T45) (app T5 X9 X81))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X9", "X80", "X81" ], "exprvars": [] } }, "type": "Nodes", "183": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "130": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T5 X9 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X9"], "exprvars": [] } }, "121": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "132": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "176": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(sublist T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "122": { "goal": [ { "clause": 1, "scope": 2, "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" }, { "clause": 2, "scope": 2, "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "133": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "177": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T34 X56 T36)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": ["X56"], "exprvars": [] } }, "123": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "178": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (app X7 X8 T7) (app T5 X9 X8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X8", "X9" ], "exprvars": [] } }, "127": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T5 X9 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X9"], "exprvars": [] } }, "128": { "goal": [ { "clause": 1, "scope": 3, "term": "(app T5 X9 T19)" }, { "clause": 2, "scope": 3, "term": "(app T5 X9 T19)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X9"], "exprvars": [] } }, "129": { "goal": [{ "clause": 1, "scope": 3, "term": "(app T5 X9 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": ["X9"], "exprvars": [] } }, "20": { "goal": [{ "clause": 0, "scope": 1, "term": "(sublist T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 20, "label": "CASE" }, { "from": 20, "to": 121, "label": "ONLY EVAL with clause\nsublist(X5, X6) :- ','(app(X7, X8, X6), app(X5, X9, X8)).\nand substitutionT1 -> T5,\nX5 -> T5,\nT2 -> T7,\nX6 -> T7,\nT6 -> T7" }, { "from": 121, "to": 122, "label": "CASE" }, { "from": 122, "to": 123, "label": "PARALLEL" }, { "from": 122, "to": 124, "label": "PARALLEL" }, { "from": 123, "to": 127, "label": "ONLY EVAL with clause\napp([], X26, X26).\nand substitutionX7 -> [],\nX8 -> T19,\nX26 -> T19,\nT7 -> T19,\nX27 -> T19,\nT18 -> T19" }, { "from": 124, "to": 182, "label": "EVAL with clause\napp(.(X75, X76), X77, .(X75, X78)) :- app(X76, X77, X78).\nand substitutionX75 -> T43,\nX76 -> X80,\nX7 -> .(T43, X80),\nX8 -> X81,\nX77 -> X81,\nX79 -> T43,\nX78 -> T45,\nT7 -> .(T43, T45),\nT44 -> T45" }, { "from": 124, "to": 183, "label": "EVAL-BACKTRACK" }, { "from": 127, "to": 128, "label": "CASE" }, { "from": 128, "to": 129, "label": "PARALLEL" }, { "from": 128, "to": 130, "label": "PARALLEL" }, { "from": 129, "to": 132, "label": "EVAL with clause\napp([], X40, X40).\nand substitutionT5 -> [],\nX9 -> T26,\nX40 -> T26,\nT19 -> T26,\nX41 -> T26" }, { "from": 129, "to": 133, "label": "EVAL-BACKTRACK" }, { "from": 130, "to": 177, "label": "EVAL with clause\napp(.(X52, X53), X54, .(X52, X55)) :- app(X53, X54, X55).\nand substitutionX52 -> T33,\nX53 -> T34,\nT5 -> .(T33, T34),\nX9 -> X56,\nX54 -> X56,\nX55 -> T36,\nT19 -> .(T33, T36),\nT35 -> T36" }, { "from": 130, "to": 178, "label": "EVAL-BACKTRACK" }, { "from": 132, "to": 176, "label": "SUCCESS" }, { "from": 177, "to": 127, "label": "INSTANCE with matching:\nT5 -> T34\nX9 -> X56\nT19 -> T36" }, { "from": 182, "to": 121, "label": "INSTANCE with matching:\nX7 -> X80\nX8 -> X81\nT7 -> T45" } ], "type": "Graph" } } ---------------------------------------- (38) Obligation: Triples: appA(.(X1, X2), X3, .(X1, X4)) :- appA(X2, X3, X4). pB([], X1, X1, X2, X3) :- appA(X2, X3, X1). pB(.(X1, X2), X3, .(X1, X4), X5, X6) :- pB(X2, X3, X4, X5, X6). sublistC(X1, X2) :- pB(X3, X4, X2, X1, X5). Clauses: appcA([], X1, X1). appcA(.(X1, X2), X3, .(X1, X4)) :- appcA(X2, X3, X4). qcB([], X1, X1, X2, X3) :- appcA(X2, X3, X1). qcB(.(X1, X2), X3, .(X1, X4), X5, X6) :- qcB(X2, X3, X4, X5, X6). Afs: sublistC(x1, x2) = sublistC(x1) ---------------------------------------- (39) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: sublistC_in_2: (b,f) pB_in_5: (f,f,f,b,f) appA_in_3: (b,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: SUBLISTC_IN_GA(X1, X2) -> U4_GA(X1, X2, pB_in_aaaga(X3, X4, X2, X1, X5)) SUBLISTC_IN_GA(X1, X2) -> PB_IN_AAAGA(X3, X4, X2, X1, X5) PB_IN_AAAGA([], X1, X1, X2, X3) -> U2_AAAGA(X1, X2, X3, appA_in_gaa(X2, X3, X1)) PB_IN_AAAGA([], X1, X1, X2, X3) -> APPA_IN_GAA(X2, X3, X1) APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U1_GAA(X1, X2, X3, X4, appA_in_gaa(X2, X3, X4)) APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GAA(X2, X3, X4) PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> U3_AAAGA(X1, X2, X3, X4, X5, X6, pB_in_aaaga(X2, X3, X4, X5, X6)) PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_AAAGA(X2, X3, X4, X5, X6) R is empty. The argument filtering Pi contains the following mapping: pB_in_aaaga(x1, x2, x3, x4, x5) = pB_in_aaaga(x4) appA_in_gaa(x1, x2, x3) = appA_in_gaa(x1) .(x1, x2) = .(x2) [] = [] SUBLISTC_IN_GA(x1, x2) = SUBLISTC_IN_GA(x1) U4_GA(x1, x2, x3) = U4_GA(x1, x3) PB_IN_AAAGA(x1, x2, x3, x4, x5) = PB_IN_AAAGA(x4) U2_AAAGA(x1, x2, x3, x4) = U2_AAAGA(x2, x4) APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x2, x5) U3_AAAGA(x1, x2, x3, x4, x5, x6, x7) = U3_AAAGA(x5, x7) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (40) Obligation: Pi DP problem: The TRS P consists of the following rules: SUBLISTC_IN_GA(X1, X2) -> U4_GA(X1, X2, pB_in_aaaga(X3, X4, X2, X1, X5)) SUBLISTC_IN_GA(X1, X2) -> PB_IN_AAAGA(X3, X4, X2, X1, X5) PB_IN_AAAGA([], X1, X1, X2, X3) -> U2_AAAGA(X1, X2, X3, appA_in_gaa(X2, X3, X1)) PB_IN_AAAGA([], X1, X1, X2, X3) -> APPA_IN_GAA(X2, X3, X1) APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U1_GAA(X1, X2, X3, X4, appA_in_gaa(X2, X3, X4)) APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GAA(X2, X3, X4) PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> U3_AAAGA(X1, X2, X3, X4, X5, X6, pB_in_aaaga(X2, X3, X4, X5, X6)) PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_AAAGA(X2, X3, X4, X5, X6) R is empty. The argument filtering Pi contains the following mapping: pB_in_aaaga(x1, x2, x3, x4, x5) = pB_in_aaaga(x4) appA_in_gaa(x1, x2, x3) = appA_in_gaa(x1) .(x1, x2) = .(x2) [] = [] SUBLISTC_IN_GA(x1, x2) = SUBLISTC_IN_GA(x1) U4_GA(x1, x2, x3) = U4_GA(x1, x3) PB_IN_AAAGA(x1, x2, x3, x4, x5) = PB_IN_AAAGA(x4) U2_AAAGA(x1, x2, x3, x4) = U2_AAAGA(x2, x4) APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5) = U1_GAA(x2, x5) U3_AAAGA(x1, x2, x3, x4, x5, x6, x7) = U3_AAAGA(x5, x7) We have to consider all (P,R,Pi)-chains ---------------------------------------- (41) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (42) Complex Obligation (AND) ---------------------------------------- (43) Obligation: Pi DP problem: The TRS P consists of the following rules: APPA_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GAA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APPA_IN_GAA(x1, x2, x3) = APPA_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (44) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: APPA_IN_GAA(.(X2)) -> APPA_IN_GAA(X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (46) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *APPA_IN_GAA(.(X2)) -> APPA_IN_GAA(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (47) YES ---------------------------------------- (48) Obligation: Pi DP problem: The TRS P consists of the following rules: PB_IN_AAAGA(.(X1, X2), X3, .(X1, X4), X5, X6) -> PB_IN_AAAGA(X2, X3, X4, X5, X6) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) PB_IN_AAAGA(x1, x2, x3, x4, x5) = PB_IN_AAAGA(x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (49) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: PB_IN_AAAGA(X5) -> PB_IN_AAAGA(X5) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (51) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 5, "program": { "directives": [], "clauses": [ [ "(sublist Xs Ys)", "(',' (app X1 Zs Ys) (app Xs X2 Zs))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "180": { "goal": [{ "clause": 1, "scope": 3, "term": "(app T9 X20 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X20"], "exprvars": [] } }, "181": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T9 X20 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X20"], "exprvars": [] } }, "192": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "193": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "194": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "140": { "goal": [ { "clause": 1, "scope": 2, "term": "(app X18 X19 T11)" }, { "clause": 2, "scope": 2, "term": "(app X18 X19 T11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X18", "X19" ], "exprvars": [] } }, "151": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X58 X59 T27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X58", "X59" ], "exprvars": [] } }, "141": { "goal": [{ "clause": 1, "scope": 2, "term": "(app X18 X19 T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X18", "X19" ], "exprvars": [] } }, "152": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "142": { "goal": [{ "clause": 2, "scope": 2, "term": "(app X18 X19 T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X18", "X19" ], "exprvars": [] } }, "145": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "146": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "179": { "goal": [ { "clause": 1, "scope": 3, "term": "(app T9 X20 T14)" }, { "clause": 2, "scope": 3, "term": "(app T9 X20 T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X20"], "exprvars": [] } }, "5": { "goal": [{ "clause": -1, "scope": -1, "term": "(sublist T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "203": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T43 X90 T45)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X90"], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(sublist T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "138": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X18 X19 T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X18", "X19" ], "exprvars": [] } }, "204": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "139": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T9 X20 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X20"], "exprvars": [] } }, "119": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app X18 X19 T11) (app T9 X20 X19))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X18", "X19", "X20" ], "exprvars": [] } } }, "edges": [ { "from": 5, "to": 6, "label": "CASE" }, { "from": 6, "to": 119, "label": "ONLY EVAL with clause\nsublist(X16, X17) :- ','(app(X18, X19, X17), app(X16, X20, X19)).\nand substitutionT1 -> T9,\nX16 -> T9,\nT2 -> T11,\nX17 -> T11,\nT10 -> T11" }, { "from": 119, "to": 138, "label": "SPLIT 1" }, { "from": 119, "to": 139, "label": "SPLIT 2\nreplacements:X18 -> T13,\nX19 -> T14" }, { "from": 138, "to": 140, "label": "CASE" }, { "from": 139, "to": 179, "label": "CASE" }, { "from": 140, "to": 141, "label": "PARALLEL" }, { "from": 140, "to": 142, "label": "PARALLEL" }, { "from": 141, "to": 145, "label": "ONLY EVAL with clause\napp([], X37, X37).\nand substitutionX18 -> [],\nX19 -> T20,\nX37 -> T20,\nT11 -> T20,\nX38 -> T20" }, { "from": 142, "to": 151, "label": "EVAL with clause\napp(.(X53, X54), X55, .(X53, X56)) :- app(X54, X55, X56).\nand substitutionX53 -> T25,\nX54 -> X58,\nX18 -> .(T25, X58),\nX19 -> X59,\nX55 -> X59,\nX57 -> T25,\nX56 -> T27,\nT11 -> .(T25, T27),\nT26 -> T27" }, { "from": 142, "to": 152, "label": "EVAL-BACKTRACK" }, { "from": 145, "to": 146, "label": "SUCCESS" }, { "from": 151, "to": 138, "label": "INSTANCE with matching:\nX18 -> X58\nX19 -> X59\nT11 -> T27" }, { "from": 179, "to": 180, "label": "PARALLEL" }, { "from": 179, "to": 181, "label": "PARALLEL" }, { "from": 180, "to": 192, "label": "EVAL with clause\napp([], X74, X74).\nand substitutionT9 -> [],\nX20 -> T35,\nX74 -> T35,\nT14 -> T35,\nX75 -> T35" }, { "from": 180, "to": 193, "label": "EVAL-BACKTRACK" }, { "from": 181, "to": 203, "label": "EVAL with clause\napp(.(X86, X87), X88, .(X86, X89)) :- app(X87, X88, X89).\nand substitutionX86 -> T42,\nX87 -> T43,\nT9 -> .(T42, T43),\nX20 -> X90,\nX88 -> X90,\nX89 -> T45,\nT14 -> .(T42, T45),\nT44 -> T45" }, { "from": 181, "to": 204, "label": "EVAL-BACKTRACK" }, { "from": 192, "to": 194, "label": "SUCCESS" }, { "from": 203, "to": 139, "label": "INSTANCE with matching:\nT9 -> T43\nX20 -> X90\nT14 -> T45" } ], "type": "Graph" } } ---------------------------------------- (52) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f5_in(T9) -> U1(f119_in(T9), T9) U1(f119_out1, T9) -> f5_out1 f138_in -> f138_out1 f138_in -> U2(f138_in) U2(f138_out1) -> f138_out1 f139_in([]) -> f139_out1 f139_in(.(T42, T43)) -> U3(f139_in(T43), .(T42, T43)) U3(f139_out1, .(T42, T43)) -> f139_out1 f119_in(T9) -> U4(f138_in, T9) U4(f138_out1, T9) -> U5(f139_in(T9), T9) U5(f139_out1, T9) -> f119_out1 Q is empty. ---------------------------------------- (53) QTRSRRRProof (EQUIVALENT) Used ordering: f5_in/1(YES) U1/2(YES,YES) f119_in/1(YES) f119_out1/0) f5_out1/0) f138_in/0) f138_out1/0) U2/1)YES( f139_in/1(YES) []/0) f139_out1/0) ./2(YES,YES) U3/2(YES,YES) U4/2(YES,YES) U5/2(YES,YES) Quasi precedence: f5_in_1 > U1_2 > f5_out1 f5_in_1 > [f119_in_1, f138_in] > U4_2 > [f119_out1, f138_out1, f139_in_1, [], f139_out1, ._2] > U3_2 f5_in_1 > [f119_in_1, f138_in] > U4_2 > [f119_out1, f138_out1, f139_in_1, [], f139_out1, ._2] > U5_2 Status: f5_in_1: multiset status U1_2: [1,2] f119_in_1: [1] f119_out1: multiset status f5_out1: multiset status f138_in: multiset status f138_out1: multiset status f139_in_1: multiset status []: multiset status f139_out1: multiset status ._2: multiset status U3_2: multiset status U4_2: multiset status U5_2: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f5_in(T9) -> U1(f119_in(T9), T9) U1(f119_out1, T9) -> f5_out1 f138_in -> f138_out1 f139_in([]) -> f139_out1 f139_in(.(T42, T43)) -> U3(f139_in(T43), .(T42, T43)) U3(f139_out1, .(T42, T43)) -> f139_out1 f119_in(T9) -> U4(f138_in, T9) U4(f138_out1, T9) -> U5(f139_in(T9), T9) U5(f139_out1, T9) -> f119_out1 ---------------------------------------- (54) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f138_in -> U2(f138_in) U2(f138_out1) -> f138_out1 Q is empty. ---------------------------------------- (55) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U2(x_1)) = 2*x_1 POL(f138_in) = 0 POL(f138_out1) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U2(f138_out1) -> f138_out1 ---------------------------------------- (56) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f138_in -> U2(f138_in) Q is empty. ---------------------------------------- (57) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (58) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f138_in -> U2(f138_in) The set Q consists of the following terms: f138_in ---------------------------------------- (59) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: F138_IN -> F138_IN The TRS R consists of the following rules: f138_in -> U2(f138_in) The set Q consists of the following terms: f138_in We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: F138_IN -> F138_IN R is empty. The set Q consists of the following terms: f138_in We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f138_in ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: F138_IN -> F138_IN R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(sublist Xs Ys)", "(',' (app X1 Zs Ys) (app Xs X2 Zs))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "190": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T43 X90 T45)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X90"], "exprvars": [] } }, "191": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "184": { "goal": [ { "clause": 1, "scope": 3, "term": "(app T9 X20 T14)" }, { "clause": 2, "scope": 3, "term": "(app T9 X20 T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X20"], "exprvars": [] } }, "185": { "goal": [{ "clause": 1, "scope": 3, "term": "(app T9 X20 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X20"], "exprvars": [] } }, "120": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app X18 X19 T11) (app T9 X20 X19))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X18", "X19", "X20" ], "exprvars": [] } }, "131": { "goal": [ { "clause": 1, "scope": 2, "term": "(app X18 X19 T11)" }, { "clause": 2, "scope": 2, "term": "(app X18 X19 T11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X18", "X19" ], "exprvars": [] } }, "186": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T9 X20 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X20"], "exprvars": [] } }, "143": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X58 X59 T27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X58", "X59" ], "exprvars": [] } }, "187": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "144": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "188": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(sublist T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "134": { "goal": [{ "clause": 1, "scope": 2, "term": "(app X18 X19 T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X18", "X19" ], "exprvars": [] } }, "189": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": 0, "scope": 1, "term": "(sublist T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "135": { "goal": [{ "clause": 2, "scope": 2, "term": "(app X18 X19 T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X18", "X19" ], "exprvars": [] } }, "125": { "goal": [{ "clause": -1, "scope": -1, "term": "(app X18 X19 T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X18", "X19" ], "exprvars": [] } }, "136": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "126": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T9 X20 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X20"], "exprvars": [] } }, "137": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 3, "label": "CASE" }, { "from": 3, "to": 120, "label": "ONLY EVAL with clause\nsublist(X16, X17) :- ','(app(X18, X19, X17), app(X16, X20, X19)).\nand substitutionT1 -> T9,\nX16 -> T9,\nT2 -> T11,\nX17 -> T11,\nT10 -> T11" }, { "from": 120, "to": 125, "label": "SPLIT 1" }, { "from": 120, "to": 126, "label": "SPLIT 2\nreplacements:X18 -> T13,\nX19 -> T14" }, { "from": 125, "to": 131, "label": "CASE" }, { "from": 126, "to": 184, "label": "CASE" }, { "from": 131, "to": 134, "label": "PARALLEL" }, { "from": 131, "to": 135, "label": "PARALLEL" }, { "from": 134, "to": 136, "label": "ONLY EVAL with clause\napp([], X37, X37).\nand substitutionX18 -> [],\nX19 -> T20,\nX37 -> T20,\nT11 -> T20,\nX38 -> T20" }, { "from": 135, "to": 143, "label": "EVAL with clause\napp(.(X53, X54), X55, .(X53, X56)) :- app(X54, X55, X56).\nand substitutionX53 -> T25,\nX54 -> X58,\nX18 -> .(T25, X58),\nX19 -> X59,\nX55 -> X59,\nX57 -> T25,\nX56 -> T27,\nT11 -> .(T25, T27),\nT26 -> T27" }, { "from": 135, "to": 144, "label": "EVAL-BACKTRACK" }, { "from": 136, "to": 137, "label": "SUCCESS" }, { "from": 143, "to": 125, "label": "INSTANCE with matching:\nX18 -> X58\nX19 -> X59\nT11 -> T27" }, { "from": 184, "to": 185, "label": "PARALLEL" }, { "from": 184, "to": 186, "label": "PARALLEL" }, { "from": 185, "to": 187, "label": "EVAL with clause\napp([], X74, X74).\nand substitutionT9 -> [],\nX20 -> T35,\nX74 -> T35,\nT14 -> T35,\nX75 -> T35" }, { "from": 185, "to": 188, "label": "EVAL-BACKTRACK" }, { "from": 186, "to": 190, "label": "EVAL with clause\napp(.(X86, X87), X88, .(X86, X89)) :- app(X87, X88, X89).\nand substitutionX86 -> T42,\nX87 -> T43,\nT9 -> .(T42, T43),\nX20 -> X90,\nX88 -> X90,\nX89 -> T45,\nT14 -> .(T42, T45),\nT44 -> T45" }, { "from": 186, "to": 191, "label": "EVAL-BACKTRACK" }, { "from": 187, "to": 189, "label": "SUCCESS" }, { "from": 190, "to": 126, "label": "INSTANCE with matching:\nT9 -> T43\nX20 -> X90\nT14 -> T45" } ], "type": "Graph" } } ---------------------------------------- (66) Complex Obligation (AND) ---------------------------------------- (67) Obligation: Rules: f186_in(T9) -> f191_in :|: TRUE f186_in(.(T42, T43)) -> f190_in(T43) :|: TRUE f191_out -> f186_out(x) :|: TRUE f190_out(x1) -> f186_out(.(x2, x1)) :|: TRUE f184_out(x3) -> f126_out(x3) :|: TRUE f126_in(x4) -> f184_in(x4) :|: TRUE f185_out(x5) -> f184_out(x5) :|: TRUE f184_in(x6) -> f186_in(x6) :|: TRUE f184_in(x7) -> f185_in(x7) :|: TRUE f186_out(x8) -> f184_out(x8) :|: TRUE f126_out(x9) -> f190_out(x9) :|: TRUE f190_in(x10) -> f126_in(x10) :|: TRUE f2_in(T1) -> f3_in(T1) :|: TRUE f3_out(x11) -> f2_out(x11) :|: TRUE f120_out(x12) -> f3_out(x12) :|: TRUE f3_in(x13) -> f120_in(x13) :|: TRUE f120_in(x14) -> f125_in :|: TRUE f126_out(x15) -> f120_out(x15) :|: TRUE f125_out -> f126_in(x16) :|: TRUE Start term: f2_in(T1) ---------------------------------------- (68) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (69) TRUE ---------------------------------------- (70) Obligation: Rules: f125_in -> f131_in :|: TRUE f131_out -> f125_out :|: TRUE f144_out -> f135_out :|: TRUE f143_out -> f135_out :|: TRUE f135_in -> f144_in :|: TRUE f135_in -> f143_in :|: TRUE f131_in -> f134_in :|: TRUE f131_in -> f135_in :|: TRUE f134_out -> f131_out :|: TRUE f135_out -> f131_out :|: TRUE f125_out -> f143_out :|: TRUE f143_in -> f125_in :|: TRUE f2_in(T1) -> f3_in(T1) :|: TRUE f3_out(x) -> f2_out(x) :|: TRUE f120_out(T9) -> f3_out(T9) :|: TRUE f3_in(x1) -> f120_in(x1) :|: TRUE f120_in(x2) -> f125_in :|: TRUE f126_out(x3) -> f120_out(x3) :|: TRUE f125_out -> f126_in(x4) :|: TRUE Start term: f2_in(T1) ---------------------------------------- (71) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f125_in -> f131_in :|: TRUE f135_in -> f143_in :|: TRUE f131_in -> f135_in :|: TRUE f143_in -> f125_in :|: TRUE ---------------------------------------- (72) Obligation: Rules: f125_in -> f131_in :|: TRUE f135_in -> f143_in :|: TRUE f131_in -> f135_in :|: TRUE f143_in -> f125_in :|: TRUE ---------------------------------------- (73) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (74) Obligation: Rules: f125_in -> f125_in :|: TRUE ---------------------------------------- (75) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (76) Obligation: Rules: f125_in -> f125_in :|: TRUE ---------------------------------------- (77) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f125_in -> f125_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (78) Obligation: Termination digraph: Nodes: (1) f125_in -> f125_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (79) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f125_in() Replaced non-predefined constructor symbols by 0. ---------------------------------------- (80) Obligation: Rules: f125_in -> f125_in :|: TRUE ---------------------------------------- (81) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc) -> f(1) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1) ---------------------------------------- (82) NO