/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern rev(a,g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 6 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) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) PrologToPiTRSProof [SOUND, 0 ms] (27) PiTRS (28) DependencyPairsProof [EQUIVALENT, 19 ms] (29) PiDP (30) DependencyGraphProof [EQUIVALENT, 0 ms] (31) AND (32) PiDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) PiDP (35) PiDPToQDPProof [SOUND, 0 ms] (36) QDP (37) QDPSizeChangeProof [EQUIVALENT, 0 ms] (38) YES (39) PiDP (40) UsableRulesProof [EQUIVALENT, 0 ms] (41) PiDP (42) PiDPToQDPProof [SOUND, 0 ms] (43) QDP (44) QDPSizeChangeProof [EQUIVALENT, 0 ms] (45) YES (46) PiDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) PiDP (49) PiDPToQDPProof [SOUND, 0 ms] (50) QDP (51) PrologToTRSTransformerProof [SOUND, 27 ms] (52) QTRS (53) QTRSRRRProof [EQUIVALENT, 121 ms] (54) QTRS (55) QTRSRRRProof [EQUIVALENT, 12 ms] (56) QTRS (57) QTRSRRRProof [EQUIVALENT, 6 ms] (58) QTRS (59) QTRSRRRProof [EQUIVALENT, 0 ms] (60) QTRS (61) PrologToIRSwTTransformerProof [SOUND, 40 ms] (62) AND (63) IRSwT (64) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (65) TRUE (66) IRSwT (67) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (68) TRUE (69) IRSwT (70) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (71) IRSwT (72) IntTRSCompressionProof [EQUIVALENT, 19 ms] (73) IRSwT (74) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (75) IRSwT (76) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (77) IRSwT (78) FilterProof [EQUIVALENT, 0 ms] (79) IntTRS (80) IntTRSPeriodicNontermProof [COMPLETE, 0 ms] (81) NO (82) PrologToDTProblemTransformerProof [SOUND, 42 ms] (83) TRIPLES (84) TriplesToPiDPProof [SOUND, 0 ms] (85) PiDP (86) DependencyGraphProof [EQUIVALENT, 0 ms] (87) AND (88) PiDP (89) UsableRulesProof [EQUIVALENT, 0 ms] (90) PiDP (91) PiDPToQDPProof [SOUND, 0 ms] (92) QDP (93) QDPSizeChangeProof [EQUIVALENT, 0 ms] (94) YES (95) PiDP (96) UsableRulesProof [EQUIVALENT, 0 ms] (97) PiDP (98) PiDPToQDPProof [SOUND, 0 ms] (99) QDP (100) QDPSizeChangeProof [EQUIVALENT, 0 ms] (101) YES (102) PiDP (103) UsableRulesProof [EQUIVALENT, 0 ms] (104) PiDP (105) PiDPToQDPProof [SOUND, 0 ms] (106) QDP ---------------------------------------- (0) Obligation: Clauses: rev([], []). rev(.(X, Xs), Ys) :- ','(rev(Xs, Zs), app(Zs, .(X, []), Ys)). app([], X, X). app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). Query: rev(a,g) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: rev_in_2: (f,b) (f,f) app_in_3: (b,b,f) (b,b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x3, x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x2, x3, x4, x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x3, x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x2, x3, x4, x5) ---------------------------------------- (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: REV_IN_AG(.(X, Xs), Ys) -> U1_AG(X, Xs, Ys, rev_in_aa(Xs, Zs)) REV_IN_AG(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) REV_IN_AA(.(X, Xs), Ys) -> U1_AA(X, Xs, Ys, rev_in_aa(Xs, Zs)) REV_IN_AA(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) U1_AA(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_AA(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) U1_AA(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> APP_IN_GGA(Zs, .(X, []), Ys) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U3_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U1_AG(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_AG(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) U1_AG(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> APP_IN_GGG(Zs, .(X, []), Ys) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U3_GGG(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x3, x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x2, x3, x4, x5) REV_IN_AG(x1, x2) = REV_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) REV_IN_AA(x1, x2) = REV_IN_AA U1_AA(x1, x2, x3, x4) = U1_AA(x4) U2_AA(x1, x2, x3, x4) = U2_AA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x2, x3, x5) U2_AG(x1, x2, x3, x4) = U2_AG(x2, x3, x4) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U3_GGG(x1, x2, x3, x4, x5) = U3_GGG(x2, x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: REV_IN_AG(.(X, Xs), Ys) -> U1_AG(X, Xs, Ys, rev_in_aa(Xs, Zs)) REV_IN_AG(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) REV_IN_AA(.(X, Xs), Ys) -> U1_AA(X, Xs, Ys, rev_in_aa(Xs, Zs)) REV_IN_AA(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) U1_AA(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_AA(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) U1_AA(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> APP_IN_GGA(Zs, .(X, []), Ys) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U3_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U1_AG(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_AG(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) U1_AG(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> APP_IN_GGG(Zs, .(X, []), Ys) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U3_GGG(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x3, x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x2, x3, x4, x5) REV_IN_AG(x1, x2) = REV_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) REV_IN_AA(x1, x2) = REV_IN_AA U1_AA(x1, x2, x3, x4) = U1_AA(x4) U2_AA(x1, x2, x3, x4) = U2_AA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x2, x3, x5) U2_AG(x1, x2, x3, x4) = U2_AG(x2, x3, x4) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U3_GGG(x1, x2, x3, x4, x5) = U3_GGG(x2, x3, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 9 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x3, x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x2, x3, x4, x5) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) 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_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) 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_GGG(.(Xs), Ys, .(Zs)) -> APP_IN_GGG(Xs, Ys, Zs) 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_GGG(.(Xs), Ys, .(Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The graph contains the following edges 1 > 1, 2 >= 2, 3 > 3 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x3, x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x2, x3, x4, x5) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) 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_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) 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_GGA(.(Xs), Ys) -> APP_IN_GGA(Xs, Ys) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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_GGA(.(Xs), Ys) -> APP_IN_GGA(Xs, Ys) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: REV_IN_AA(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x2, x3, x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x2, x3, x4, x5) REV_IN_AA(x1, x2) = REV_IN_AA We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: REV_IN_AA(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) REV_IN_AA(x1, x2) = REV_IN_AA We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: REV_IN_AA -> REV_IN_AA R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: rev_in_2: (f,b) (f,f) app_in_3: (b,b,f) (b,b,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (27) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x5) ---------------------------------------- (28) 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: REV_IN_AG(.(X, Xs), Ys) -> U1_AG(X, Xs, Ys, rev_in_aa(Xs, Zs)) REV_IN_AG(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) REV_IN_AA(.(X, Xs), Ys) -> U1_AA(X, Xs, Ys, rev_in_aa(Xs, Zs)) REV_IN_AA(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) U1_AA(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_AA(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) U1_AA(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> APP_IN_GGA(Zs, .(X, []), Ys) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U3_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U1_AG(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_AG(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) U1_AG(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> APP_IN_GGG(Zs, .(X, []), Ys) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U3_GGG(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x5) REV_IN_AG(x1, x2) = REV_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) REV_IN_AA(x1, x2) = REV_IN_AA U1_AA(x1, x2, x3, x4) = U1_AA(x4) U2_AA(x1, x2, x3, x4) = U2_AA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x5) U2_AG(x1, x2, x3, x4) = U2_AG(x2, x4) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U3_GGG(x1, x2, x3, x4, x5) = U3_GGG(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) Obligation: Pi DP problem: The TRS P consists of the following rules: REV_IN_AG(.(X, Xs), Ys) -> U1_AG(X, Xs, Ys, rev_in_aa(Xs, Zs)) REV_IN_AG(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) REV_IN_AA(.(X, Xs), Ys) -> U1_AA(X, Xs, Ys, rev_in_aa(Xs, Zs)) REV_IN_AA(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) U1_AA(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_AA(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) U1_AA(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> APP_IN_GGA(Zs, .(X, []), Ys) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U3_GGA(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) U1_AG(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_AG(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) U1_AG(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> APP_IN_GGG(Zs, .(X, []), Ys) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U3_GGG(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x5) REV_IN_AG(x1, x2) = REV_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) REV_IN_AA(x1, x2) = REV_IN_AA U1_AA(x1, x2, x3, x4) = U1_AA(x4) U2_AA(x1, x2, x3, x4) = U2_AA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4, x5) = U3_GGA(x5) U2_AG(x1, x2, x3, x4) = U2_AG(x2, x4) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U3_GGG(x1, x2, x3, x4, x5) = U3_GGG(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (30) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 9 less nodes. ---------------------------------------- (31) Complex Obligation (AND) ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x5) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) 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_GGG(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGG(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) 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_GGG(.(Xs), Ys, .(Zs)) -> APP_IN_GGG(Xs, Ys, Zs) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) 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_GGG(.(Xs), Ys, .(Zs)) -> APP_IN_GGG(Xs, Ys, Zs) The graph contains the following edges 1 > 1, 2 >= 2, 3 > 3 ---------------------------------------- (38) YES ---------------------------------------- (39) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x5) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (40) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (41) Obligation: Pi DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> APP_IN_GGA(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (42) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: APP_IN_GGA(.(Xs), Ys) -> APP_IN_GGA(Xs, Ys) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (44) 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_GGA(.(Xs), Ys) -> APP_IN_GGA(Xs, Ys) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (45) YES ---------------------------------------- (46) Obligation: Pi DP problem: The TRS P consists of the following rules: REV_IN_AA(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) The TRS R consists of the following rules: rev_in_ag([], []) -> rev_out_ag([], []) rev_in_ag(.(X, Xs), Ys) -> U1_ag(X, Xs, Ys, rev_in_aa(Xs, Zs)) rev_in_aa([], []) -> rev_out_aa([], []) rev_in_aa(.(X, Xs), Ys) -> U1_aa(X, Xs, Ys, rev_in_aa(Xs, Zs)) U1_aa(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga([], X, X) -> app_out_gga([], X, X) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U3_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) U3_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U2_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> rev_out_aa(.(X, Xs), Ys) U1_ag(X, Xs, Ys, rev_out_aa(Xs, Zs)) -> U2_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg([], X, X) -> app_out_ggg([], X, X) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U3_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) U3_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U2_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> rev_out_ag(.(X, Xs), Ys) The argument filtering Pi contains the following mapping: rev_in_ag(x1, x2) = rev_in_ag(x2) [] = [] rev_out_ag(x1, x2) = rev_out_ag(x1) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) rev_in_aa(x1, x2) = rev_in_aa rev_out_aa(x1, x2) = rev_out_aa(x1, x2) U1_aa(x1, x2, x3, x4) = U1_aa(x4) U2_aa(x1, x2, x3, x4) = U2_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_gga(x1, x2, x3, x4, x5) = U3_gga(x5) U2_ag(x1, x2, x3, x4) = U2_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) app_out_ggg(x1, x2, x3) = app_out_ggg U3_ggg(x1, x2, x3, x4, x5) = U3_ggg(x5) REV_IN_AA(x1, x2) = REV_IN_AA We have to consider all (P,R,Pi)-chains ---------------------------------------- (47) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (48) Obligation: Pi DP problem: The TRS P consists of the following rules: REV_IN_AA(.(X, Xs), Ys) -> REV_IN_AA(Xs, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) REV_IN_AA(x1, x2) = REV_IN_AA 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: REV_IN_AA -> REV_IN_AA R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (51) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 131, "program": { "directives": [], "clauses": [ [ "(rev ([]) ([]))", null ], [ "(rev (. X Xs) Ys)", "(',' (rev Xs Zs) (app Zs (. X ([])) Ys))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "type": "Nodes", "250": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "251": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "131": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "153": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (rev T12 X11) (app X11 (. T13 ([])) T11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": ["X11"], "exprvars": [] } }, "132": { "goal": [ { "clause": 0, "scope": 1, "term": "(rev T1 T2)" }, { "clause": 1, "scope": 1, "term": "(rev T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "155": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "210": { "goal": [{ "clause": 1, "scope": 2, "term": "(rev T12 X11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "254": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "135": { "goal": [{ "clause": 0, "scope": 1, "term": "(rev T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "234": { "goal": [ { "clause": 2, "scope": 3, "term": "(app T24 (. T25 ([])) X25)" }, { "clause": 3, "scope": 3, "term": "(app T24 (. T25 ([])) X25)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X25"], "exprvars": [] } }, "136": { "goal": [{ "clause": 1, "scope": 1, "term": "(rev T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "213": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "235": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T24 (. T25 ([])) X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X25"], "exprvars": [] } }, "214": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "236": { "goal": [{ "clause": 3, "scope": 3, "term": "(app T24 (. T25 ([])) X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X25"], "exprvars": [] } }, "258": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T65 (. T66 ([])) T64)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T64"], "free": [], "exprvars": [] } }, "138": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "215": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "237": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "139": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "216": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (rev T22 X24) (app X24 (. T23 ([])) X25))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X25", "X24" ], "exprvars": [] } }, "238": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "217": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "239": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "218": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T22 X24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X24"], "exprvars": [] } }, "219": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T24 (. T25 ([])) X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X25"], "exprvars": [] } }, "140": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "242": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T42 (. T43 ([])) X47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X47"], "exprvars": [] } }, "243": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "246": { "goal": [ { "clause": 2, "scope": 4, "term": "(app T14 (. T15 ([])) T11)" }, { "clause": 3, "scope": 4, "term": "(app T14 (. T15 ([])) T11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "247": { "goal": [{ "clause": 2, "scope": 4, "term": "(app T14 (. T15 ([])) T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "248": { "goal": [{ "clause": 3, "scope": 4, "term": "(app T14 (. T15 ([])) T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "206": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T12 X11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "305": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "207": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T14 (. T15 ([])) T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "208": { "goal": [ { "clause": 0, "scope": 2, "term": "(rev T12 X11)" }, { "clause": 1, "scope": 2, "term": "(rev T12 X11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "209": { "goal": [{ "clause": 0, "scope": 2, "term": "(rev T12 X11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } } }, "edges": [ { "from": 131, "to": 132, "label": "CASE" }, { "from": 132, "to": 135, "label": "PARALLEL" }, { "from": 132, "to": 136, "label": "PARALLEL" }, { "from": 135, "to": 138, "label": "EVAL with clause\nrev([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 135, "to": 139, "label": "EVAL-BACKTRACK" }, { "from": 136, "to": 153, "label": "EVAL with clause\nrev(.(X8, X9), X10) :- ','(rev(X9, X11), app(X11, .(X8, []), X10)).\nand substitutionX8 -> T13,\nX9 -> T12,\nT1 -> .(T13, T12),\nT2 -> T11,\nX10 -> T11,\nT10 -> T12,\nT9 -> T13" }, { "from": 136, "to": 155, "label": "EVAL-BACKTRACK" }, { "from": 138, "to": 140, "label": "SUCCESS" }, { "from": 153, "to": 206, "label": "SPLIT 1" }, { "from": 153, "to": 207, "label": "SPLIT 2\nreplacements:X11 -> T14,\nT13 -> T15" }, { "from": 206, "to": 208, "label": "CASE" }, { "from": 207, "to": 246, "label": "CASE" }, { "from": 208, "to": 209, "label": "PARALLEL" }, { "from": 208, "to": 210, "label": "PARALLEL" }, { "from": 209, "to": 213, "label": "EVAL with clause\nrev([], []).\nand substitutionT12 -> [],\nX11 -> []" }, { "from": 209, "to": 214, "label": "EVAL-BACKTRACK" }, { "from": 210, "to": 216, "label": "EVAL with clause\nrev(.(X21, X22), X23) :- ','(rev(X22, X24), app(X24, .(X21, []), X23)).\nand substitutionX21 -> T23,\nX22 -> T22,\nT12 -> .(T23, T22),\nX11 -> X25,\nX23 -> X25,\nT21 -> T22,\nT20 -> T23" }, { "from": 210, "to": 217, "label": "EVAL-BACKTRACK" }, { "from": 213, "to": 215, "label": "SUCCESS" }, { "from": 216, "to": 218, "label": "SPLIT 1" }, { "from": 216, "to": 219, "label": "SPLIT 2\nreplacements:X24 -> T24,\nT23 -> T25" }, { "from": 218, "to": 206, "label": "INSTANCE with matching:\nT12 -> T22\nX11 -> X24" }, { "from": 219, "to": 234, "label": "CASE" }, { "from": 234, "to": 235, "label": "PARALLEL" }, { "from": 234, "to": 236, "label": "PARALLEL" }, { "from": 235, "to": 237, "label": "EVAL with clause\napp([], X32, X32).\nand substitutionT24 -> [],\nT25 -> T32,\nX32 -> .(T32, []),\nX25 -> .(T32, [])" }, { "from": 235, "to": 238, "label": "EVAL-BACKTRACK" }, { "from": 236, "to": 242, "label": "EVAL with clause\napp(.(X43, X44), X45, .(X43, X46)) :- app(X44, X45, X46).\nand substitutionX43 -> T39,\nX44 -> T42,\nT24 -> .(T39, T42),\nT25 -> T43,\nX45 -> .(T43, []),\nX46 -> X47,\nX25 -> .(T39, X47),\nT40 -> T42,\nT41 -> T43" }, { "from": 236, "to": 243, "label": "EVAL-BACKTRACK" }, { "from": 237, "to": 239, "label": "SUCCESS" }, { "from": 242, "to": 219, "label": "INSTANCE with matching:\nT24 -> T42\nT25 -> T43\nX25 -> X47" }, { "from": 246, "to": 247, "label": "PARALLEL" }, { "from": 246, "to": 248, "label": "PARALLEL" }, { "from": 247, "to": 250, "label": "EVAL with clause\napp([], X56, X56).\nand substitutionT14 -> [],\nT15 -> T52,\nX56 -> .(T52, []),\nT11 -> .(T52, [])" }, { "from": 247, "to": 251, "label": "EVAL-BACKTRACK" }, { "from": 248, "to": 258, "label": "EVAL with clause\napp(.(X65, X66), X67, .(X65, X68)) :- app(X66, X67, X68).\nand substitutionX65 -> T61,\nX66 -> T65,\nT14 -> .(T61, T65),\nT15 -> T66,\nX67 -> .(T66, []),\nX68 -> T64,\nT11 -> .(T61, T64),\nT62 -> T65,\nT63 -> T66" }, { "from": 248, "to": 305, "label": "EVAL-BACKTRACK" }, { "from": 250, "to": 254, "label": "SUCCESS" }, { "from": 258, "to": 207, "label": "INSTANCE with matching:\nT14 -> T65\nT15 -> T66\nT11 -> T64" } ], "type": "Graph" } } ---------------------------------------- (52) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f131_in([]) -> f131_out1 f131_in(T11) -> U1(f153_in(T11), T11) U1(f153_out1(X11, T13), T11) -> f131_out1 f206_in -> f206_out1 f206_in -> U2(f216_in) U2(f216_out1) -> f206_out1 f219_in -> f219_out1 f219_in -> U3(f219_in) U3(f219_out1) -> f219_out1 f207_in(.(T52, [])) -> f207_out1([], T52) f207_in(.(T61, T64)) -> U4(f207_in(T64), .(T61, T64)) U4(f207_out1(T65, T66), .(T61, T64)) -> f207_out1(.(T61, T65), T66) f153_in(T11) -> U5(f206_in, T11) U5(f206_out1, T11) -> U6(f207_in(T11), T11) U6(f207_out1(T14, T15), T11) -> f153_out1(T14, T15) f216_in -> U7(f206_in) U7(f206_out1) -> U8(f219_in) U8(f219_out1) -> f216_out1 Q is empty. ---------------------------------------- (53) QTRSRRRProof (EQUIVALENT) Used ordering: f131_in/1(YES) []/0) f131_out1/0) U1/2(YES,YES) f153_in/1(YES) f153_out1/2(YES,YES) f206_in/0) f206_out1/0) U2/1)YES( f216_in/0) f216_out1/0) f219_in/0) f219_out1/0) U3/1)YES( f207_in/1(YES) ./2(YES,YES) f207_out1/2(YES,YES) U4/2(YES,YES) U5/2(YES,YES) U6/2(YES,YES) U7/1)YES( U8/1)YES( Quasi precedence: f131_in_1 > U1_2 > [] f131_in_1 > [f153_in_1, f206_in, f216_in] > [f206_out1, f216_out1, f219_in, f219_out1] > U6_2 > [] f131_in_1 > [f153_in_1, f206_in, f216_in] > [f207_in_1, U5_2] > U4_2 > f207_out1_2 > [f131_out1, f153_out1_2] > [] f131_in_1 > [f153_in_1, f206_in, f216_in] > [f207_in_1, U5_2] > U4_2 > f207_out1_2 > ._2 > [] f131_in_1 > [f153_in_1, f206_in, f216_in] > [f207_in_1, U5_2] > U6_2 > [] Status: f131_in_1: multiset status []: multiset status f131_out1: multiset status U1_2: multiset status f153_in_1: [1] f153_out1_2: multiset status f206_in: multiset status f206_out1: multiset status f216_in: multiset status f216_out1: multiset status f219_in: multiset status f219_out1: multiset status f207_in_1: multiset status ._2: [1,2] f207_out1_2: multiset status U4_2: multiset status U5_2: multiset status U6_2: multiset status With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f131_in([]) -> f131_out1 f131_in(T11) -> U1(f153_in(T11), T11) U1(f153_out1(X11, T13), T11) -> f131_out1 f206_in -> f206_out1 f207_in(.(T52, [])) -> f207_out1([], T52) f207_in(.(T61, T64)) -> U4(f207_in(T64), .(T61, T64)) U4(f207_out1(T65, T66), .(T61, T64)) -> f207_out1(.(T61, T65), T66) f153_in(T11) -> U5(f206_in, T11) U5(f206_out1, T11) -> U6(f207_in(T11), T11) U6(f207_out1(T14, T15), T11) -> f153_out1(T14, T15) ---------------------------------------- (54) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f206_in -> U2(f216_in) U2(f216_out1) -> f206_out1 f219_in -> f219_out1 f219_in -> U3(f219_in) U3(f219_out1) -> f219_out1 f216_in -> U7(f206_in) U7(f206_out1) -> U8(f219_in) U8(f219_out1) -> f216_out1 Q is empty. ---------------------------------------- (55) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U2(x_1)) = 2*x_1 POL(U3(x_1)) = x_1 POL(U7(x_1)) = 2*x_1 POL(U8(x_1)) = 2 + x_1 POL(f206_in) = 0 POL(f206_out1) = 2 POL(f216_in) = 0 POL(f216_out1) = 1 POL(f219_in) = 1 POL(f219_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f219_in -> f219_out1 U7(f206_out1) -> U8(f219_in) U8(f219_out1) -> f216_out1 ---------------------------------------- (56) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f206_in -> U2(f216_in) U2(f216_out1) -> f206_out1 f219_in -> U3(f219_in) U3(f219_out1) -> f219_out1 f216_in -> U7(f206_in) Q is empty. ---------------------------------------- (57) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U2(x_1)) = x_1 POL(U3(x_1)) = 2*x_1 POL(U7(x_1)) = 2*x_1 POL(f206_in) = 0 POL(f206_out1) = 0 POL(f216_in) = 0 POL(f216_out1) = 1 POL(f219_in) = 0 POL(f219_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U2(f216_out1) -> f206_out1 ---------------------------------------- (58) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f206_in -> U2(f216_in) f219_in -> U3(f219_in) U3(f219_out1) -> f219_out1 f216_in -> U7(f206_in) Q is empty. ---------------------------------------- (59) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U2(x_1)) = 2*x_1 POL(U3(x_1)) = 2*x_1 POL(U7(x_1)) = 2*x_1 POL(f206_in) = 0 POL(f216_in) = 0 POL(f219_in) = 0 POL(f219_out1) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U3(f219_out1) -> f219_out1 ---------------------------------------- (60) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f206_in -> U2(f216_in) f219_in -> U3(f219_in) f216_in -> U7(f206_in) Q is empty. ---------------------------------------- (61) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 125, "program": { "directives": [], "clauses": [ [ "(rev ([]) ([]))", null ], [ "(rev (. X Xs) Ys)", "(',' (rev Xs Zs) (app Zs (. X ([])) Ys))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "type": "Nodes", "194": { "goal": [ { "clause": 0, "scope": 2, "term": "(rev T12 X11)" }, { "clause": 1, "scope": 2, "term": "(rev T12 X11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "174": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (rev T12 X11) (app X11 (. T13 ([])) T11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": ["X11"], "exprvars": [] } }, "196": { "goal": [{ "clause": 0, "scope": 2, "term": "(rev T12 X11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "197": { "goal": [{ "clause": 1, "scope": 2, "term": "(rev T12 X11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "230": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "252": { "goal": [{ "clause": 2, "scope": 4, "term": "(app T14 (. T15 ([])) T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "253": { "goal": [{ "clause": 3, "scope": 4, "term": "(app T14 (. T15 ([])) T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "177": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "211": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T22 X24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X24"], "exprvars": [] } }, "255": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "212": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T24 (. T25 ([])) X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X25"], "exprvars": [] } }, "256": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "257": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "259": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T65 (. T66 ([])) T64)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T64"], "free": [], "exprvars": [] } }, "260": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "240": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "186": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T12 X11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "241": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "187": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T14 (. T15 ([])) T11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "166": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "167": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "200": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "222": { "goal": [ { "clause": 2, "scope": 3, "term": "(app T24 (. T25 ([])) X25)" }, { "clause": 3, "scope": 3, "term": "(app T24 (. T25 ([])) X25)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X25"], "exprvars": [] } }, "244": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T42 (. T43 ([])) X47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X47"], "exprvars": [] } }, "168": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "201": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "245": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "125": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "202": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "126": { "goal": [ { "clause": 0, "scope": 1, "term": "(rev T1 T2)" }, { "clause": 1, "scope": 1, "term": "(rev T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "225": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T24 (. T25 ([])) X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X25"], "exprvars": [] } }, "127": { "goal": [{ "clause": 0, "scope": 1, "term": "(rev T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "204": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (rev T22 X24) (app X24 (. T23 ([])) X25))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X25", "X24" ], "exprvars": [] } }, "226": { "goal": [{ "clause": 3, "scope": 3, "term": "(app T24 (. T25 ([])) X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X25"], "exprvars": [] } }, "128": { "goal": [{ "clause": 1, "scope": 1, "term": "(rev T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "205": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "249": { "goal": [ { "clause": 2, "scope": 4, "term": "(app T14 (. T15 ([])) T11)" }, { "clause": 3, "scope": 4, "term": "(app T14 (. T15 ([])) T11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 125, "to": 126, "label": "CASE" }, { "from": 126, "to": 127, "label": "PARALLEL" }, { "from": 126, "to": 128, "label": "PARALLEL" }, { "from": 127, "to": 166, "label": "EVAL with clause\nrev([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 127, "to": 167, "label": "EVAL-BACKTRACK" }, { "from": 128, "to": 174, "label": "EVAL with clause\nrev(.(X8, X9), X10) :- ','(rev(X9, X11), app(X11, .(X8, []), X10)).\nand substitutionX8 -> T13,\nX9 -> T12,\nT1 -> .(T13, T12),\nT2 -> T11,\nX10 -> T11,\nT10 -> T12,\nT9 -> T13" }, { "from": 128, "to": 177, "label": "EVAL-BACKTRACK" }, { "from": 166, "to": 168, "label": "SUCCESS" }, { "from": 174, "to": 186, "label": "SPLIT 1" }, { "from": 174, "to": 187, "label": "SPLIT 2\nreplacements:X11 -> T14,\nT13 -> T15" }, { "from": 186, "to": 194, "label": "CASE" }, { "from": 187, "to": 249, "label": "CASE" }, { "from": 194, "to": 196, "label": "PARALLEL" }, { "from": 194, "to": 197, "label": "PARALLEL" }, { "from": 196, "to": 200, "label": "EVAL with clause\nrev([], []).\nand substitutionT12 -> [],\nX11 -> []" }, { "from": 196, "to": 201, "label": "EVAL-BACKTRACK" }, { "from": 197, "to": 204, "label": "EVAL with clause\nrev(.(X21, X22), X23) :- ','(rev(X22, X24), app(X24, .(X21, []), X23)).\nand substitutionX21 -> T23,\nX22 -> T22,\nT12 -> .(T23, T22),\nX11 -> X25,\nX23 -> X25,\nT21 -> T22,\nT20 -> T23" }, { "from": 197, "to": 205, "label": "EVAL-BACKTRACK" }, { "from": 200, "to": 202, "label": "SUCCESS" }, { "from": 204, "to": 211, "label": "SPLIT 1" }, { "from": 204, "to": 212, "label": "SPLIT 2\nreplacements:X24 -> T24,\nT23 -> T25" }, { "from": 211, "to": 186, "label": "INSTANCE with matching:\nT12 -> T22\nX11 -> X24" }, { "from": 212, "to": 222, "label": "CASE" }, { "from": 222, "to": 225, "label": "PARALLEL" }, { "from": 222, "to": 226, "label": "PARALLEL" }, { "from": 225, "to": 230, "label": "EVAL with clause\napp([], X32, X32).\nand substitutionT24 -> [],\nT25 -> T32,\nX32 -> .(T32, []),\nX25 -> .(T32, [])" }, { "from": 225, "to": 240, "label": "EVAL-BACKTRACK" }, { "from": 226, "to": 244, "label": "EVAL with clause\napp(.(X43, X44), X45, .(X43, X46)) :- app(X44, X45, X46).\nand substitutionX43 -> T39,\nX44 -> T42,\nT24 -> .(T39, T42),\nT25 -> T43,\nX45 -> .(T43, []),\nX46 -> X47,\nX25 -> .(T39, X47),\nT40 -> T42,\nT41 -> T43" }, { "from": 226, "to": 245, "label": "EVAL-BACKTRACK" }, { "from": 230, "to": 241, "label": "SUCCESS" }, { "from": 244, "to": 212, "label": "INSTANCE with matching:\nT24 -> T42\nT25 -> T43\nX25 -> X47" }, { "from": 249, "to": 252, "label": "PARALLEL" }, { "from": 249, "to": 253, "label": "PARALLEL" }, { "from": 252, "to": 255, "label": "EVAL with clause\napp([], X56, X56).\nand substitutionT14 -> [],\nT15 -> T52,\nX56 -> .(T52, []),\nT11 -> .(T52, [])" }, { "from": 252, "to": 256, "label": "EVAL-BACKTRACK" }, { "from": 253, "to": 259, "label": "EVAL with clause\napp(.(X65, X66), X67, .(X65, X68)) :- app(X66, X67, X68).\nand substitutionX65 -> T61,\nX66 -> T65,\nT14 -> .(T61, T65),\nT15 -> T66,\nX67 -> .(T66, []),\nX68 -> T64,\nT11 -> .(T61, T64),\nT62 -> T65,\nT63 -> T66" }, { "from": 253, "to": 260, "label": "EVAL-BACKTRACK" }, { "from": 255, "to": 257, "label": "SUCCESS" }, { "from": 259, "to": 187, "label": "INSTANCE with matching:\nT14 -> T65\nT15 -> T66\nT11 -> T64" } ], "type": "Graph" } } ---------------------------------------- (62) Complex Obligation (AND) ---------------------------------------- (63) Obligation: Rules: f222_out -> f212_out :|: TRUE f212_in -> f222_in :|: TRUE f212_out -> f244_out :|: TRUE f244_in -> f212_in :|: TRUE f244_out -> f226_out :|: TRUE f226_in -> f245_in :|: TRUE f245_out -> f226_out :|: TRUE f226_in -> f244_in :|: TRUE f222_in -> f226_in :|: TRUE f226_out -> f222_out :|: TRUE f222_in -> f225_in :|: TRUE f225_out -> f222_out :|: TRUE f126_out(T2) -> f125_out(T2) :|: TRUE f125_in(x) -> f126_in(x) :|: TRUE f126_in(x1) -> f127_in(x1) :|: TRUE f128_out(x2) -> f126_out(x2) :|: TRUE f127_out(x3) -> f126_out(x3) :|: TRUE f126_in(x4) -> f128_in(x4) :|: TRUE f174_out(T11) -> f128_out(T11) :|: TRUE f128_in(x5) -> f177_in :|: TRUE f128_in(x6) -> f174_in(x6) :|: TRUE f177_out -> f128_out(x7) :|: TRUE f187_out(x8) -> f174_out(x8) :|: TRUE f186_out -> f187_in(x9) :|: TRUE f174_in(x10) -> f186_in :|: TRUE f194_out -> f186_out :|: TRUE f186_in -> f194_in :|: TRUE f194_in -> f197_in :|: TRUE f196_out -> f194_out :|: TRUE f194_in -> f196_in :|: TRUE f197_out -> f194_out :|: TRUE f197_in -> f204_in :|: TRUE f204_out -> f197_out :|: TRUE f205_out -> f197_out :|: TRUE f197_in -> f205_in :|: TRUE f204_in -> f211_in :|: TRUE f211_out -> f212_in :|: TRUE f212_out -> f204_out :|: TRUE Start term: f125_in(T2) ---------------------------------------- (64) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (65) TRUE ---------------------------------------- (66) Obligation: Rules: f253_out(T11) -> f249_out(T11) :|: TRUE f249_in(x) -> f253_in(x) :|: TRUE f249_in(x1) -> f252_in(x1) :|: TRUE f252_out(x2) -> f249_out(x2) :|: TRUE f187_out(T64) -> f259_out(T64) :|: TRUE f259_in(x3) -> f187_in(x3) :|: TRUE f253_in(x4) -> f260_in :|: TRUE f259_out(x5) -> f253_out(.(x6, x5)) :|: TRUE f253_in(.(x7, x8)) -> f259_in(x8) :|: TRUE f260_out -> f253_out(x9) :|: TRUE f249_out(x10) -> f187_out(x10) :|: TRUE f187_in(x11) -> f249_in(x11) :|: TRUE f126_out(T2) -> f125_out(T2) :|: TRUE f125_in(x12) -> f126_in(x12) :|: TRUE f126_in(x13) -> f127_in(x13) :|: TRUE f128_out(x14) -> f126_out(x14) :|: TRUE f127_out(x15) -> f126_out(x15) :|: TRUE f126_in(x16) -> f128_in(x16) :|: TRUE f174_out(x17) -> f128_out(x17) :|: TRUE f128_in(x18) -> f177_in :|: TRUE f128_in(x19) -> f174_in(x19) :|: TRUE f177_out -> f128_out(x20) :|: TRUE f187_out(x21) -> f174_out(x21) :|: TRUE f186_out -> f187_in(x22) :|: TRUE f174_in(x23) -> f186_in :|: TRUE Start term: f125_in(T2) ---------------------------------------- (67) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (68) TRUE ---------------------------------------- (69) Obligation: Rules: f197_in -> f204_in :|: TRUE f204_out -> f197_out :|: TRUE f205_out -> f197_out :|: TRUE f197_in -> f205_in :|: TRUE f186_out -> f211_out :|: TRUE f211_in -> f186_in :|: TRUE f212_out -> f244_out :|: TRUE f244_in -> f212_in :|: TRUE f204_in -> f211_in :|: TRUE f211_out -> f212_in :|: TRUE f212_out -> f204_out :|: TRUE f194_in -> f197_in :|: TRUE f196_out -> f194_out :|: TRUE f194_in -> f196_in :|: TRUE f197_out -> f194_out :|: TRUE f194_out -> f186_out :|: TRUE f186_in -> f194_in :|: TRUE f222_out -> f212_out :|: TRUE f212_in -> f222_in :|: TRUE f225_in -> f240_in :|: TRUE f240_out -> f225_out :|: TRUE f230_out -> f225_out :|: TRUE f225_in -> f230_in :|: TRUE f230_in -> f230_out :|: TRUE f244_out -> f226_out :|: TRUE f226_in -> f245_in :|: TRUE f245_out -> f226_out :|: TRUE f226_in -> f244_in :|: TRUE f222_in -> f226_in :|: TRUE f226_out -> f222_out :|: TRUE f222_in -> f225_in :|: TRUE f225_out -> f222_out :|: TRUE f126_out(T2) -> f125_out(T2) :|: TRUE f125_in(x) -> f126_in(x) :|: TRUE f126_in(x1) -> f127_in(x1) :|: TRUE f128_out(x2) -> f126_out(x2) :|: TRUE f127_out(x3) -> f126_out(x3) :|: TRUE f126_in(x4) -> f128_in(x4) :|: TRUE f174_out(T11) -> f128_out(T11) :|: TRUE f128_in(x5) -> f177_in :|: TRUE f128_in(x6) -> f174_in(x6) :|: TRUE f177_out -> f128_out(x7) :|: TRUE f187_out(x8) -> f174_out(x8) :|: TRUE f186_out -> f187_in(x9) :|: TRUE f174_in(x10) -> f186_in :|: TRUE Start term: f125_in(T2) ---------------------------------------- (70) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f197_in -> f204_in :|: TRUE f211_in -> f186_in :|: TRUE f204_in -> f211_in :|: TRUE f194_in -> f197_in :|: TRUE f186_in -> f194_in :|: TRUE ---------------------------------------- (71) Obligation: Rules: f197_in -> f204_in :|: TRUE f211_in -> f186_in :|: TRUE f204_in -> f211_in :|: TRUE f194_in -> f197_in :|: TRUE f186_in -> f194_in :|: TRUE ---------------------------------------- (72) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (73) Obligation: Rules: f194_in -> f194_in :|: TRUE ---------------------------------------- (74) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (75) Obligation: Rules: f194_in -> f194_in :|: TRUE ---------------------------------------- (76) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f194_in -> f194_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (77) Obligation: Termination digraph: Nodes: (1) f194_in -> f194_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (78) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f194_in() Replaced non-predefined constructor symbols by 0. ---------------------------------------- (79) Obligation: Rules: f194_in -> f194_in :|: TRUE ---------------------------------------- (80) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc) -> f(1) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1) ---------------------------------------- (81) NO ---------------------------------------- (82) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 17, "program": { "directives": [], "clauses": [ [ "(rev ([]) ([]))", null ], [ "(rev (. X Xs) Ys)", "(',' (rev Xs Zs) (app Zs (. X ([])) Ys))" ], [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "190": { "goal": [ { "clause": 0, "scope": 2, "term": "(',' (rev T7 X7) (app X7 (. T8 ([])) ([])))" }, { "clause": 1, "scope": 2, "term": "(',' (rev T7 X7) (app X7 (. T8 ([])) ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X7"], "exprvars": [] } }, "191": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (rev T7 X7) (app X7 (. T8 ([])) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X7"], "exprvars": [] } }, "192": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (rev T7 X7) (app X7 (. T8 ([])) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X7"], "exprvars": [] } }, "193": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) (. T9 ([])) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "270": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "195": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "198": { "goal": [ { "clause": 2, "scope": 3, "term": "(app ([]) (. T9 ([])) ([]))" }, { "clause": 3, "scope": 3, "term": "(app ([]) (. T9 ([])) ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "199": { "goal": [{ "clause": 3, "scope": 3, "term": "(app ([]) (. T9 ([])) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "232": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "233": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "310": { "goal": [ { "clause": 2, "scope": 8, "term": "(app ([]) (. T75 ([])) T72)" }, { "clause": 3, "scope": 8, "term": "(app ([]) (. T75 ([])) T72)" } ], "kb": { "nonunifying": [[ "(rev T1 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": [], "exprvars": [] } }, "311": { "goal": [{ "clause": 2, "scope": 8, "term": "(app ([]) (. T75 ([])) T72)" }], "kb": { "nonunifying": [[ "(rev T1 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": [], "exprvars": [] } }, "114": { "goal": [{ "clause": 1, "scope": 1, "term": "(rev T1 T2)" }], "kb": { "nonunifying": [[ "(rev T1 T2)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "312": { "goal": [{ "clause": 3, "scope": 8, "term": "(app ([]) (. T75 ([])) T72)" }], "kb": { "nonunifying": [[ "(rev T1 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": [], "exprvars": [] } }, "313": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "314": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "315": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "316": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "317": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (rev T89 X108) (app X108 (. T90 ([])) X109)) (app X109 (. T91 ([])) T72))" }], "kb": { "nonunifying": [[ "(rev T1 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": [ "X109", "X108" ], "exprvars": [] } }, "318": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "319": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T89 X108)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X108"], "exprvars": [] } }, "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "18": { "goal": [ { "clause": 0, "scope": 1, "term": "(rev T1 T2)" }, { "clause": 1, "scope": 1, "term": "(rev T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "320": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T92 (. T93 ([])) X109) (app X109 (. T94 ([])) T72))" }], "kb": { "nonunifying": [[ "(rev T95 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": ["X109"], "exprvars": [] } }, "321": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T92 (. T93 ([])) X109)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X109"], "exprvars": [] } }, "322": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T98 (. T99 ([])) T72)" }], "kb": { "nonunifying": [[ "(rev T100 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": [], "exprvars": [] } }, "323": { "goal": [ { "clause": 2, "scope": 9, "term": "(app T98 (. T99 ([])) T72)" }, { "clause": 3, "scope": 9, "term": "(app T98 (. T99 ([])) T72)" } ], "kb": { "nonunifying": [[ "(rev T100 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": [], "exprvars": [] } }, "203": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "324": { "goal": [{ "clause": 2, "scope": 9, "term": "(app T98 (. T99 ([])) T72)" }], "kb": { "nonunifying": [[ "(rev T100 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": [], "exprvars": [] } }, "325": { "goal": [{ "clause": 3, "scope": 9, "term": "(app T98 (. T99 ([])) T72)" }], "kb": { "nonunifying": [[ "(rev T100 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": [], "exprvars": [] } }, "326": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "327": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "328": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "329": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T122 (. T123 ([])) T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T121"], "free": [], "exprvars": [] } }, "295": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T51 (. T52 ([])) X64)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X64"], "exprvars": [] } }, "296": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "297": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T22 (. T23 ([])) X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X28"], "exprvars": [] } }, "330": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "298": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T57 (. T58 ([])) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "331": { "goal": [ { "clause": 2, "scope": 10, "term": "(app T122 (. T123 ([])) T121)" }, { "clause": 3, "scope": 10, "term": "(app T122 (. T123 ([])) T121)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T121"], "free": [], "exprvars": [] } }, "299": { "goal": [ { "clause": 2, "scope": 6, "term": "(app T57 (. T58 ([])) ([]))" }, { "clause": 3, "scope": 6, "term": "(app T57 (. T58 ([])) ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "332": { "goal": [{ "clause": 2, "scope": 10, "term": "(app T122 (. T123 ([])) T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T121"], "free": [], "exprvars": [] } }, "333": { "goal": [{ "clause": 3, "scope": 10, "term": "(app T122 (. T123 ([])) T121)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T121"], "free": [], "exprvars": [] } }, "334": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "335": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "336": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "337": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T143 (. T144 ([])) T142)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T142"], "free": [], "exprvars": [] } }, "338": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "261": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (rev T31 X41) (app X41 (. T32 ([])) X42))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X42", "X41" ], "exprvars": [] } }, "185": { "goal": [{ "clause": 1, "scope": 1, "term": "(rev T1 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "262": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "263": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T31 X41)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X41"], "exprvars": [] } }, "220": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (rev T19 X27) (app X27 (. T20 ([])) X28)) (app X28 (. T21 ([])) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X28", "X27" ], "exprvars": [] } }, "264": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T33 (. T34 ([])) X42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X42"], "exprvars": [] } }, "188": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (rev T7 X7) (app X7 (. T8 ([])) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X7"], "exprvars": [] } }, "221": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "265": { "goal": [ { "clause": 2, "scope": 5, "term": "(app T33 (. T34 ([])) X42)" }, { "clause": 3, "scope": 5, "term": "(app T33 (. T34 ([])) X42)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X42"], "exprvars": [] } }, "189": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "266": { "goal": [{ "clause": 2, "scope": 5, "term": "(app T33 (. T34 ([])) X42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X42"], "exprvars": [] } }, "223": { "goal": [{ "clause": -1, "scope": -1, "term": "(rev T19 X27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X27"], "exprvars": [] } }, "267": { "goal": [{ "clause": 3, "scope": 5, "term": "(app T33 (. T34 ([])) X42)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X42"], "exprvars": [] } }, "300": { "goal": [{ "clause": 3, "scope": 6, "term": "(app T57 (. T58 ([])) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "224": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T22 (. T23 ([])) X28) (app X28 (. T24 ([])) ([])))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X28"], "exprvars": [] } }, "268": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "301": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "269": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "302": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (rev T73 X84) (app X84 (. T74 ([])) T72))" }], "kb": { "nonunifying": [[ "(rev T1 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": ["X84"], "exprvars": [] } }, "303": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "227": { "goal": [ { "clause": 0, "scope": 4, "term": "(rev T19 X27)" }, { "clause": 1, "scope": 4, "term": "(rev T19 X27)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X27"], "exprvars": [] } }, "304": { "goal": [ { "clause": 0, "scope": 7, "term": "(',' (rev T73 X84) (app X84 (. T74 ([])) T72))" }, { "clause": 1, "scope": 7, "term": "(',' (rev T73 X84) (app X84 (. T74 ([])) T72))" } ], "kb": { "nonunifying": [[ "(rev T1 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": ["X84"], "exprvars": [] } }, "228": { "goal": [{ "clause": 0, "scope": 4, "term": "(rev T19 X27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X27"], "exprvars": [] } }, "108": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(rev T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "229": { "goal": [{ "clause": 1, "scope": 4, "term": "(rev T19 X27)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X27"], "exprvars": [] } }, "306": { "goal": [{ "clause": 0, "scope": 7, "term": "(',' (rev T73 X84) (app X84 (. T74 ([])) T72))" }], "kb": { "nonunifying": [[ "(rev T1 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": ["X84"], "exprvars": [] } }, "307": { "goal": [{ "clause": 1, "scope": 7, "term": "(',' (rev T73 X84) (app X84 (. T74 ([])) T72))" }], "kb": { "nonunifying": [[ "(rev T1 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": ["X84"], "exprvars": [] } }, "308": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) (. T75 ([])) T72)" }], "kb": { "nonunifying": [[ "(rev T1 T72)", "(rev ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": [], "exprvars": [] } }, "309": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 17, "to": 18, "label": "CASE" }, { "from": 18, "to": 108, "label": "EVAL with clause\nrev([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 18, "to": 114, "label": "EVAL-BACKTRACK" }, { "from": 108, "to": 185, "label": "SUCCESS" }, { "from": 114, "to": 302, "label": "EVAL with clause\nrev(.(X81, X82), X83) :- ','(rev(X82, X84), app(X84, .(X81, []), X83)).\nand substitutionX81 -> T74,\nX82 -> T73,\nT1 -> .(T74, T73),\nT2 -> T72,\nX83 -> T72,\nT71 -> T73,\nT70 -> T74" }, { "from": 114, "to": 303, "label": "EVAL-BACKTRACK" }, { "from": 185, "to": 188, "label": "EVAL with clause\nrev(.(X4, X5), X6) :- ','(rev(X5, X7), app(X7, .(X4, []), X6)).\nand substitutionX4 -> T8,\nX5 -> T7,\nT1 -> .(T8, T7),\nX6 -> [],\nT6 -> T7,\nT5 -> T8" }, { "from": 185, "to": 189, "label": "EVAL-BACKTRACK" }, { "from": 188, "to": 190, "label": "CASE" }, { "from": 190, "to": 191, "label": "PARALLEL" }, { "from": 190, "to": 192, "label": "PARALLEL" }, { "from": 191, "to": 193, "label": "EVAL with clause\nrev([], []).\nand substitutionT7 -> [],\nX7 -> [],\nT8 -> T9" }, { "from": 191, "to": 195, "label": "EVAL-BACKTRACK" }, { "from": 192, "to": 220, "label": "EVAL with clause\nrev(.(X24, X25), X26) :- ','(rev(X25, X27), app(X27, .(X24, []), X26)).\nand substitutionX24 -> T20,\nX25 -> T19,\nT7 -> .(T20, T19),\nX7 -> X28,\nX26 -> X28,\nT18 -> T19,\nT17 -> T20,\nT8 -> T21" }, { "from": 192, "to": 221, "label": "EVAL-BACKTRACK" }, { "from": 193, "to": 198, "label": "CASE" }, { "from": 198, "to": 199, "label": "BACKTRACK\nfor clause: app([], X, X)because of non-unification" }, { "from": 199, "to": 203, "label": "BACKTRACK\nfor clause: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs)because of non-unification" }, { "from": 220, "to": 223, "label": "SPLIT 1" }, { "from": 220, "to": 224, "label": "SPLIT 2\nreplacements:X27 -> T22,\nT20 -> T23,\nT21 -> T24" }, { "from": 223, "to": 227, "label": "CASE" }, { "from": 224, "to": 297, "label": "SPLIT 1" }, { "from": 224, "to": 298, "label": "SPLIT 2\nreplacements:X28 -> T57,\nT24 -> T58" }, { "from": 227, "to": 228, "label": "PARALLEL" }, { "from": 227, "to": 229, "label": "PARALLEL" }, { "from": 228, "to": 231, "label": "EVAL with clause\nrev([], []).\nand substitutionT19 -> [],\nX27 -> []" }, { "from": 228, "to": 232, "label": "EVAL-BACKTRACK" }, { "from": 229, "to": 261, "label": "EVAL with clause\nrev(.(X38, X39), X40) :- ','(rev(X39, X41), app(X41, .(X38, []), X40)).\nand substitutionX38 -> T32,\nX39 -> T31,\nT19 -> .(T32, T31),\nX27 -> X42,\nX40 -> X42,\nT30 -> T31,\nT29 -> T32" }, { "from": 229, "to": 262, "label": "EVAL-BACKTRACK" }, { "from": 231, "to": 233, "label": "SUCCESS" }, { "from": 261, "to": 263, "label": "SPLIT 1" }, { "from": 261, "to": 264, "label": "SPLIT 2\nreplacements:X41 -> T33,\nT32 -> T34" }, { "from": 263, "to": 223, "label": "INSTANCE with matching:\nT19 -> T31\nX27 -> X41" }, { "from": 264, "to": 265, "label": "CASE" }, { "from": 265, "to": 266, "label": "PARALLEL" }, { "from": 265, "to": 267, "label": "PARALLEL" }, { "from": 266, "to": 268, "label": "EVAL with clause\napp([], X49, X49).\nand substitutionT33 -> [],\nT34 -> T41,\nX49 -> .(T41, []),\nX42 -> .(T41, [])" }, { "from": 266, "to": 269, "label": "EVAL-BACKTRACK" }, { "from": 267, "to": 295, "label": "EVAL with clause\napp(.(X60, X61), X62, .(X60, X63)) :- app(X61, X62, X63).\nand substitutionX60 -> T48,\nX61 -> T51,\nT33 -> .(T48, T51),\nT34 -> T52,\nX62 -> .(T52, []),\nX63 -> X64,\nX42 -> .(T48, X64),\nT49 -> T51,\nT50 -> T52" }, { "from": 267, "to": 296, "label": "EVAL-BACKTRACK" }, { "from": 268, "to": 270, "label": "SUCCESS" }, { "from": 295, "to": 264, "label": "INSTANCE with matching:\nT33 -> T51\nT34 -> T52\nX42 -> X64" }, { "from": 297, "to": 264, "label": "INSTANCE with matching:\nT33 -> T22\nT34 -> T23\nX42 -> X28" }, { "from": 298, "to": 299, "label": "CASE" }, { "from": 299, "to": 300, "label": "BACKTRACK\nfor clause: app([], X, X)because of non-unification" }, { "from": 300, "to": 301, "label": "BACKTRACK\nfor clause: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs)because of non-unification" }, { "from": 302, "to": 304, "label": "CASE" }, { "from": 304, "to": 306, "label": "PARALLEL" }, { "from": 304, "to": 307, "label": "PARALLEL" }, { "from": 306, "to": 308, "label": "EVAL with clause\nrev([], []).\nand substitutionT73 -> [],\nX84 -> [],\nT74 -> T75" }, { "from": 306, "to": 309, "label": "EVAL-BACKTRACK" }, { "from": 307, "to": 317, "label": "EVAL with clause\nrev(.(X105, X106), X107) :- ','(rev(X106, X108), app(X108, .(X105, []), X107)).\nand substitutionX105 -> T90,\nX106 -> T89,\nT73 -> .(T90, T89),\nX84 -> X109,\nX107 -> X109,\nT88 -> T89,\nT87 -> T90,\nT74 -> T91" }, { "from": 307, "to": 318, "label": "EVAL-BACKTRACK" }, { "from": 308, "to": 310, "label": "CASE" }, { "from": 310, "to": 311, "label": "PARALLEL" }, { "from": 310, "to": 312, "label": "PARALLEL" }, { "from": 311, "to": 313, "label": "EVAL with clause\napp([], X91, X91).\nand substitutionT75 -> T82,\nX91 -> .(T82, []),\nT72 -> .(T82, [])" }, { "from": 311, "to": 314, "label": "EVAL-BACKTRACK" }, { "from": 312, "to": 316, "label": "BACKTRACK\nfor clause: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs)because of non-unification" }, { "from": 313, "to": 315, "label": "SUCCESS" }, { "from": 317, "to": 319, "label": "SPLIT 1" }, { "from": 317, "to": 320, "label": "SPLIT 2\nreplacements:X108 -> T92,\nT90 -> T93,\nT91 -> T94,\nT1 -> T95" }, { "from": 319, "to": 223, "label": "INSTANCE with matching:\nT19 -> T89\nX27 -> X108" }, { "from": 320, "to": 321, "label": "SPLIT 1" }, { "from": 320, "to": 322, "label": "SPLIT 2\nreplacements:X109 -> T98,\nT94 -> T99,\nT95 -> T100" }, { "from": 321, "to": 264, "label": "INSTANCE with matching:\nT33 -> T92\nT34 -> T93\nX42 -> X109" }, { "from": 322, "to": 323, "label": "CASE" }, { "from": 323, "to": 324, "label": "PARALLEL" }, { "from": 323, "to": 325, "label": "PARALLEL" }, { "from": 324, "to": 326, "label": "EVAL with clause\napp([], X120, X120).\nand substitutionT98 -> [],\nT99 -> T109,\nX120 -> .(T109, []),\nT72 -> .(T109, [])" }, { "from": 324, "to": 327, "label": "EVAL-BACKTRACK" }, { "from": 325, "to": 329, "label": "EVAL with clause\napp(.(X129, X130), X131, .(X129, X132)) :- app(X130, X131, X132).\nand substitutionX129 -> T118,\nX130 -> T122,\nT98 -> .(T118, T122),\nT99 -> T123,\nX131 -> .(T123, []),\nX132 -> T121,\nT72 -> .(T118, T121),\nT119 -> T122,\nT120 -> T123" }, { "from": 325, "to": 330, "label": "EVAL-BACKTRACK" }, { "from": 326, "to": 328, "label": "SUCCESS" }, { "from": 329, "to": 331, "label": "CASE" }, { "from": 331, "to": 332, "label": "PARALLEL" }, { "from": 331, "to": 333, "label": "PARALLEL" }, { "from": 332, "to": 334, "label": "EVAL with clause\napp([], X139, X139).\nand substitutionT122 -> [],\nT123 -> T130,\nX139 -> .(T130, []),\nT121 -> .(T130, [])" }, { "from": 332, "to": 335, "label": "EVAL-BACKTRACK" }, { "from": 333, "to": 337, "label": "EVAL with clause\napp(.(X148, X149), X150, .(X148, X151)) :- app(X149, X150, X151).\nand substitutionX148 -> T139,\nX149 -> T143,\nT122 -> .(T139, T143),\nT123 -> T144,\nX150 -> .(T144, []),\nX151 -> T142,\nT121 -> .(T139, T142),\nT140 -> T143,\nT141 -> T144" }, { "from": 333, "to": 338, "label": "EVAL-BACKTRACK" }, { "from": 334, "to": 336, "label": "SUCCESS" }, { "from": 337, "to": 329, "label": "INSTANCE with matching:\nT122 -> T143\nT123 -> T144\nT121 -> T142" } ], "type": "Graph" } } ---------------------------------------- (83) Obligation: Triples: revA(.(X1, X2), X3) :- revA(X2, X4). revA(.(X1, X2), X3) :- ','(revcA(X2, X4), appB(X4, X1, X3)). appB(.(X1, X2), X3, .(X1, X4)) :- appB(X2, X3, X4). appC(.(X1, X2), X3, .(X1, X4)) :- appC(X2, X3, X4). revD(.(X1, .(X2, X3)), []) :- revA(X3, X4). revD(.(X1, .(X2, X3)), []) :- ','(revcA(X3, X4), appB(X4, X2, X5)). revD(.(X1, .(X2, X3)), X4) :- revA(X3, X5). revD(.(X1, .(X2, X3)), X4) :- ','(revcA(X3, X5), appB(X5, X2, X6)). revD(.(X1, .(X2, X3)), .(X4, X5)) :- ','(revcA(X3, X6), ','(appcB(X6, X2, .(X4, X7)), appC(X7, X1, X5))). Clauses: revcA([], []). revcA(.(X1, X2), X3) :- ','(revcA(X2, X4), appcB(X4, X1, X3)). appcB([], X1, .(X1, [])). appcB(.(X1, X2), X3, .(X1, X4)) :- appcB(X2, X3, X4). appcC([], X1, .(X1, [])). appcC(.(X1, X2), X3, .(X1, X4)) :- appcC(X2, X3, X4). Afs: revD(x1, x2) = revD(x2) ---------------------------------------- (84) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: revD_in_2: (f,b) revA_in_2: (f,f) revcA_in_2: (f,f) appcB_in_3: (b,f,f) appB_in_3: (b,f,f) appC_in_3: (b,f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: REVD_IN_AG(.(X1, .(X2, X3)), []) -> U6_AG(X1, X2, X3, revA_in_aa(X3, X4)) REVD_IN_AG(.(X1, .(X2, X3)), []) -> REVA_IN_AA(X3, X4) REVA_IN_AA(.(X1, X2), X3) -> U1_AA(X1, X2, X3, revA_in_aa(X2, X4)) REVA_IN_AA(.(X1, X2), X3) -> REVA_IN_AA(X2, X4) REVA_IN_AA(.(X1, X2), X3) -> U2_AA(X1, X2, X3, revcA_in_aa(X2, X4)) U2_AA(X1, X2, X3, revcA_out_aa(X2, X4)) -> U3_AA(X1, X2, X3, appB_in_gaa(X4, X1, X3)) U2_AA(X1, X2, X3, revcA_out_aa(X2, X4)) -> APPB_IN_GAA(X4, X1, X3) APPB_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U4_GAA(X1, X2, X3, X4, appB_in_gaa(X2, X3, X4)) APPB_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GAA(X2, X3, X4) REVD_IN_AG(.(X1, .(X2, X3)), []) -> U7_AG(X1, X2, X3, revcA_in_aa(X3, X4)) U7_AG(X1, X2, X3, revcA_out_aa(X3, X4)) -> U8_AG(X1, X2, X3, appB_in_gaa(X4, X2, X5)) U7_AG(X1, X2, X3, revcA_out_aa(X3, X4)) -> APPB_IN_GAA(X4, X2, X5) REVD_IN_AG(.(X1, .(X2, X3)), X4) -> U9_AG(X1, X2, X3, X4, revA_in_aa(X3, X5)) REVD_IN_AG(.(X1, .(X2, X3)), X4) -> REVA_IN_AA(X3, X5) REVD_IN_AG(.(X1, .(X2, X3)), X4) -> U10_AG(X1, X2, X3, X4, revcA_in_aa(X3, X5)) U10_AG(X1, X2, X3, X4, revcA_out_aa(X3, X5)) -> U11_AG(X1, X2, X3, X4, appB_in_gaa(X5, X2, X6)) U10_AG(X1, X2, X3, X4, revcA_out_aa(X3, X5)) -> APPB_IN_GAA(X5, X2, X6) REVD_IN_AG(.(X1, .(X2, X3)), .(X4, X5)) -> U12_AG(X1, X2, X3, X4, X5, revcA_in_aa(X3, X6)) U12_AG(X1, X2, X3, X4, X5, revcA_out_aa(X3, X6)) -> U13_AG(X1, X2, X3, X4, X5, appcB_in_gaa(X6, X2, .(X4, X7))) U13_AG(X1, X2, X3, X4, X5, appcB_out_gaa(X6, X2, .(X4, X7))) -> U14_AG(X1, X2, X3, X4, X5, appC_in_gag(X7, X1, X5)) U13_AG(X1, X2, X3, X4, X5, appcB_out_gaa(X6, X2, .(X4, X7))) -> APPC_IN_GAG(X7, X1, X5) APPC_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> U5_GAG(X1, X2, X3, X4, appC_in_gag(X2, X3, X4)) APPC_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> APPC_IN_GAG(X2, X3, X4) The TRS R consists of the following rules: revcA_in_aa([], []) -> revcA_out_aa([], []) revcA_in_aa(.(X1, X2), X3) -> U16_aa(X1, X2, X3, revcA_in_aa(X2, X4)) U16_aa(X1, X2, X3, revcA_out_aa(X2, X4)) -> U17_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U18_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) U18_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U17_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> revcA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: [] = [] revA_in_aa(x1, x2) = revA_in_aa revcA_in_aa(x1, x2) = revcA_in_aa revcA_out_aa(x1, x2) = revcA_out_aa(x1, x2) U16_aa(x1, x2, x3, x4) = U16_aa(x4) U17_aa(x1, x2, x3, x4) = U17_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) .(x1, x2) = .(x2) U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x2, x5) appB_in_gaa(x1, x2, x3) = appB_in_gaa(x1) appC_in_gag(x1, x2, x3) = appC_in_gag(x1, x3) REVD_IN_AG(x1, x2) = REVD_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x4) REVA_IN_AA(x1, x2) = REVA_IN_AA U1_AA(x1, x2, x3, x4) = U1_AA(x4) U2_AA(x1, x2, x3, x4) = U2_AA(x4) U3_AA(x1, x2, x3, x4) = U3_AA(x2, x4) APPB_IN_GAA(x1, x2, x3) = APPB_IN_GAA(x1) U4_GAA(x1, x2, x3, x4, x5) = U4_GAA(x2, x5) U7_AG(x1, x2, x3, x4) = U7_AG(x4) U8_AG(x1, x2, x3, x4) = U8_AG(x3, x4) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x4, x5) U10_AG(x1, x2, x3, x4, x5) = U10_AG(x4, x5) U11_AG(x1, x2, x3, x4, x5) = U11_AG(x3, x4, x5) U12_AG(x1, x2, x3, x4, x5, x6) = U12_AG(x5, x6) U13_AG(x1, x2, x3, x4, x5, x6) = U13_AG(x3, x5, x6) U14_AG(x1, x2, x3, x4, x5, x6) = U14_AG(x3, x5, x6) APPC_IN_GAG(x1, x2, x3) = APPC_IN_GAG(x1, x3) U5_GAG(x1, x2, x3, x4, x5) = U5_GAG(x2, x4, x5) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (85) Obligation: Pi DP problem: The TRS P consists of the following rules: REVD_IN_AG(.(X1, .(X2, X3)), []) -> U6_AG(X1, X2, X3, revA_in_aa(X3, X4)) REVD_IN_AG(.(X1, .(X2, X3)), []) -> REVA_IN_AA(X3, X4) REVA_IN_AA(.(X1, X2), X3) -> U1_AA(X1, X2, X3, revA_in_aa(X2, X4)) REVA_IN_AA(.(X1, X2), X3) -> REVA_IN_AA(X2, X4) REVA_IN_AA(.(X1, X2), X3) -> U2_AA(X1, X2, X3, revcA_in_aa(X2, X4)) U2_AA(X1, X2, X3, revcA_out_aa(X2, X4)) -> U3_AA(X1, X2, X3, appB_in_gaa(X4, X1, X3)) U2_AA(X1, X2, X3, revcA_out_aa(X2, X4)) -> APPB_IN_GAA(X4, X1, X3) APPB_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U4_GAA(X1, X2, X3, X4, appB_in_gaa(X2, X3, X4)) APPB_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GAA(X2, X3, X4) REVD_IN_AG(.(X1, .(X2, X3)), []) -> U7_AG(X1, X2, X3, revcA_in_aa(X3, X4)) U7_AG(X1, X2, X3, revcA_out_aa(X3, X4)) -> U8_AG(X1, X2, X3, appB_in_gaa(X4, X2, X5)) U7_AG(X1, X2, X3, revcA_out_aa(X3, X4)) -> APPB_IN_GAA(X4, X2, X5) REVD_IN_AG(.(X1, .(X2, X3)), X4) -> U9_AG(X1, X2, X3, X4, revA_in_aa(X3, X5)) REVD_IN_AG(.(X1, .(X2, X3)), X4) -> REVA_IN_AA(X3, X5) REVD_IN_AG(.(X1, .(X2, X3)), X4) -> U10_AG(X1, X2, X3, X4, revcA_in_aa(X3, X5)) U10_AG(X1, X2, X3, X4, revcA_out_aa(X3, X5)) -> U11_AG(X1, X2, X3, X4, appB_in_gaa(X5, X2, X6)) U10_AG(X1, X2, X3, X4, revcA_out_aa(X3, X5)) -> APPB_IN_GAA(X5, X2, X6) REVD_IN_AG(.(X1, .(X2, X3)), .(X4, X5)) -> U12_AG(X1, X2, X3, X4, X5, revcA_in_aa(X3, X6)) U12_AG(X1, X2, X3, X4, X5, revcA_out_aa(X3, X6)) -> U13_AG(X1, X2, X3, X4, X5, appcB_in_gaa(X6, X2, .(X4, X7))) U13_AG(X1, X2, X3, X4, X5, appcB_out_gaa(X6, X2, .(X4, X7))) -> U14_AG(X1, X2, X3, X4, X5, appC_in_gag(X7, X1, X5)) U13_AG(X1, X2, X3, X4, X5, appcB_out_gaa(X6, X2, .(X4, X7))) -> APPC_IN_GAG(X7, X1, X5) APPC_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> U5_GAG(X1, X2, X3, X4, appC_in_gag(X2, X3, X4)) APPC_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> APPC_IN_GAG(X2, X3, X4) The TRS R consists of the following rules: revcA_in_aa([], []) -> revcA_out_aa([], []) revcA_in_aa(.(X1, X2), X3) -> U16_aa(X1, X2, X3, revcA_in_aa(X2, X4)) U16_aa(X1, X2, X3, revcA_out_aa(X2, X4)) -> U17_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U18_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) U18_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U17_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> revcA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: [] = [] revA_in_aa(x1, x2) = revA_in_aa revcA_in_aa(x1, x2) = revcA_in_aa revcA_out_aa(x1, x2) = revcA_out_aa(x1, x2) U16_aa(x1, x2, x3, x4) = U16_aa(x4) U17_aa(x1, x2, x3, x4) = U17_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) .(x1, x2) = .(x2) U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x2, x5) appB_in_gaa(x1, x2, x3) = appB_in_gaa(x1) appC_in_gag(x1, x2, x3) = appC_in_gag(x1, x3) REVD_IN_AG(x1, x2) = REVD_IN_AG(x2) U6_AG(x1, x2, x3, x4) = U6_AG(x4) REVA_IN_AA(x1, x2) = REVA_IN_AA U1_AA(x1, x2, x3, x4) = U1_AA(x4) U2_AA(x1, x2, x3, x4) = U2_AA(x4) U3_AA(x1, x2, x3, x4) = U3_AA(x2, x4) APPB_IN_GAA(x1, x2, x3) = APPB_IN_GAA(x1) U4_GAA(x1, x2, x3, x4, x5) = U4_GAA(x2, x5) U7_AG(x1, x2, x3, x4) = U7_AG(x4) U8_AG(x1, x2, x3, x4) = U8_AG(x3, x4) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x4, x5) U10_AG(x1, x2, x3, x4, x5) = U10_AG(x4, x5) U11_AG(x1, x2, x3, x4, x5) = U11_AG(x3, x4, x5) U12_AG(x1, x2, x3, x4, x5, x6) = U12_AG(x5, x6) U13_AG(x1, x2, x3, x4, x5, x6) = U13_AG(x3, x5, x6) U14_AG(x1, x2, x3, x4, x5, x6) = U14_AG(x3, x5, x6) APPC_IN_GAG(x1, x2, x3) = APPC_IN_GAG(x1, x3) U5_GAG(x1, x2, x3, x4, x5) = U5_GAG(x2, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (86) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 20 less nodes. ---------------------------------------- (87) Complex Obligation (AND) ---------------------------------------- (88) Obligation: Pi DP problem: The TRS P consists of the following rules: APPC_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> APPC_IN_GAG(X2, X3, X4) The TRS R consists of the following rules: revcA_in_aa([], []) -> revcA_out_aa([], []) revcA_in_aa(.(X1, X2), X3) -> U16_aa(X1, X2, X3, revcA_in_aa(X2, X4)) U16_aa(X1, X2, X3, revcA_out_aa(X2, X4)) -> U17_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U18_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) U18_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U17_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> revcA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: [] = [] revcA_in_aa(x1, x2) = revcA_in_aa revcA_out_aa(x1, x2) = revcA_out_aa(x1, x2) U16_aa(x1, x2, x3, x4) = U16_aa(x4) U17_aa(x1, x2, x3, x4) = U17_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) .(x1, x2) = .(x2) U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x2, x5) APPC_IN_GAG(x1, x2, x3) = APPC_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (89) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (90) Obligation: Pi DP problem: The TRS P consists of the following rules: APPC_IN_GAG(.(X1, X2), X3, .(X1, X4)) -> APPC_IN_GAG(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APPC_IN_GAG(x1, x2, x3) = APPC_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (91) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: APPC_IN_GAG(.(X2), .(X4)) -> APPC_IN_GAG(X2, X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (93) 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: *APPC_IN_GAG(.(X2), .(X4)) -> APPC_IN_GAG(X2, X4) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (94) YES ---------------------------------------- (95) Obligation: Pi DP problem: The TRS P consists of the following rules: APPB_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GAA(X2, X3, X4) The TRS R consists of the following rules: revcA_in_aa([], []) -> revcA_out_aa([], []) revcA_in_aa(.(X1, X2), X3) -> U16_aa(X1, X2, X3, revcA_in_aa(X2, X4)) U16_aa(X1, X2, X3, revcA_out_aa(X2, X4)) -> U17_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U18_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) U18_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U17_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> revcA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: [] = [] revcA_in_aa(x1, x2) = revcA_in_aa revcA_out_aa(x1, x2) = revcA_out_aa(x1, x2) U16_aa(x1, x2, x3, x4) = U16_aa(x4) U17_aa(x1, x2, x3, x4) = U17_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) .(x1, x2) = .(x2) U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x2, x5) APPB_IN_GAA(x1, x2, x3) = APPB_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (96) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (97) Obligation: Pi DP problem: The TRS P consists of the following rules: APPB_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPB_IN_GAA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APPB_IN_GAA(x1, x2, x3) = APPB_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (98) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (99) Obligation: Q DP problem: The TRS P consists of the following rules: APPB_IN_GAA(.(X2)) -> APPB_IN_GAA(X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (100) 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: *APPB_IN_GAA(.(X2)) -> APPB_IN_GAA(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (101) YES ---------------------------------------- (102) Obligation: Pi DP problem: The TRS P consists of the following rules: REVA_IN_AA(.(X1, X2), X3) -> REVA_IN_AA(X2, X4) The TRS R consists of the following rules: revcA_in_aa([], []) -> revcA_out_aa([], []) revcA_in_aa(.(X1, X2), X3) -> U16_aa(X1, X2, X3, revcA_in_aa(X2, X4)) U16_aa(X1, X2, X3, revcA_out_aa(X2, X4)) -> U17_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U18_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) U18_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U17_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> revcA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: [] = [] revcA_in_aa(x1, x2) = revcA_in_aa revcA_out_aa(x1, x2) = revcA_out_aa(x1, x2) U16_aa(x1, x2, x3, x4) = U16_aa(x4) U17_aa(x1, x2, x3, x4) = U17_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) .(x1, x2) = .(x2) U18_gaa(x1, x2, x3, x4, x5) = U18_gaa(x2, x5) REVA_IN_AA(x1, x2) = REVA_IN_AA We have to consider all (P,R,Pi)-chains ---------------------------------------- (103) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (104) Obligation: Pi DP problem: The TRS P consists of the following rules: REVA_IN_AA(.(X1, X2), X3) -> REVA_IN_AA(X2, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) REVA_IN_AA(x1, x2) = REVA_IN_AA We have to consider all (P,R,Pi)-chains ---------------------------------------- (105) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (106) Obligation: Q DP problem: The TRS P consists of the following rules: REVA_IN_AA -> REVA_IN_AA R is empty. Q is empty. We have to consider all (P,Q,R)-chains.