/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern reverse(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, 11 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 6 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, 9 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, 28 ms] (52) QTRS (53) QTRSRRRProof [EQUIVALENT, 109 ms] (54) QTRS (55) QTRSRRRProof [EQUIVALENT, 7 ms] (56) QTRS (57) QTRSRRRProof [EQUIVALENT, 4 ms] (58) QTRS (59) QTRSRRRProof [EQUIVALENT, 2 ms] (60) QTRS (61) PrologToDTProblemTransformerProof [SOUND, 39 ms] (62) TRIPLES (63) TriplesToPiDPProof [SOUND, 0 ms] (64) PiDP (65) DependencyGraphProof [EQUIVALENT, 0 ms] (66) AND (67) PiDP (68) UsableRulesProof [EQUIVALENT, 0 ms] (69) PiDP (70) PiDPToQDPProof [SOUND, 0 ms] (71) QDP (72) QDPSizeChangeProof [EQUIVALENT, 0 ms] (73) YES (74) PiDP (75) UsableRulesProof [EQUIVALENT, 0 ms] (76) PiDP (77) PiDPToQDPProof [SOUND, 0 ms] (78) QDP (79) QDPSizeChangeProof [EQUIVALENT, 0 ms] (80) YES (81) PiDP (82) UsableRulesProof [EQUIVALENT, 0 ms] (83) PiDP (84) PiDPToQDPProof [SOUND, 0 ms] (85) QDP (86) PrologToIRSwTTransformerProof [SOUND, 27 ms] (87) AND (88) IRSwT (89) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (90) TRUE (91) IRSwT (92) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (93) TRUE (94) IRSwT (95) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (96) IRSwT (97) IntTRSCompressionProof [EQUIVALENT, 1 ms] (98) IRSwT (99) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (100) IRSwT (101) IRSwTTerminationDigraphProof [EQUIVALENT, 5 ms] (102) IRSwT (103) FilterProof [EQUIVALENT, 3 ms] (104) IntTRS (105) IntTRSPeriodicNontermProof [COMPLETE, 6 ms] (106) NO ---------------------------------------- (0) Obligation: Clauses: app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). app([], Ys, Ys). reverse(.(X, Xs), Ys) :- ','(reverse(Xs, Zs), app(Zs, .(X, []), Ys)). reverse([], []). Query: reverse(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: reverse_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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x2, x3, x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x2, x3, x4, x5) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) reverse_out_ag(x1, x2) = reverse_out_ag(x1, x2) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (2) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x2, x3, x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x2, x3, x4, x5) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) reverse_out_ag(x1, x2) = reverse_out_ag(x1, x2) ---------------------------------------- (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: REVERSE_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, reverse_in_aa(Xs, Zs)) REVERSE_IN_AG(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) REVERSE_IN_AA(.(X, Xs), Ys) -> U2_AA(X, Xs, Ys, reverse_in_aa(Xs, Zs)) REVERSE_IN_AA(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) U2_AA(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_AA(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) U2_AA(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> APP_IN_GGA(Zs, .(X, []), Ys) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U1_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) U2_AG(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_AG(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) U2_AG(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> APP_IN_GGG(Zs, .(X, []), Ys) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U1_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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x2, x3, x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x2, x3, x4, x5) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) reverse_out_ag(x1, x2) = reverse_out_ag(x1, x2) REVERSE_IN_AG(x1, x2) = REVERSE_IN_AG(x2) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) REVERSE_IN_AA(x1, x2) = REVERSE_IN_AA U2_AA(x1, x2, x3, x4) = U2_AA(x4) U3_AA(x1, x2, x3, x4) = U3_AA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x2, x3, x5) U3_AG(x1, x2, x3, x4) = U3_AG(x2, x3, x4) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4, x5) = U1_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: REVERSE_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, reverse_in_aa(Xs, Zs)) REVERSE_IN_AG(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) REVERSE_IN_AA(.(X, Xs), Ys) -> U2_AA(X, Xs, Ys, reverse_in_aa(Xs, Zs)) REVERSE_IN_AA(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) U2_AA(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_AA(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) U2_AA(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> APP_IN_GGA(Zs, .(X, []), Ys) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U1_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) U2_AG(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_AG(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) U2_AG(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> APP_IN_GGG(Zs, .(X, []), Ys) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U1_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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x2, x3, x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x2, x3, x4, x5) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) reverse_out_ag(x1, x2) = reverse_out_ag(x1, x2) REVERSE_IN_AG(x1, x2) = REVERSE_IN_AG(x2) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) REVERSE_IN_AA(x1, x2) = REVERSE_IN_AA U2_AA(x1, x2, x3, x4) = U2_AA(x4) U3_AA(x1, x2, x3, x4) = U3_AA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x2, x3, x5) U3_AG(x1, x2, x3, x4) = U3_AG(x2, x3, x4) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4, x5) = U1_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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x2, x3, x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x2, x3, x4, x5) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) reverse_out_ag(x1, x2) = reverse_out_ag(x1, x2) 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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x2, x3, x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x2, x3, x4, x5) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) reverse_out_ag(x1, x2) = reverse_out_ag(x1, x2) 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: REVERSE_IN_AA(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) The TRS R consists of the following rules: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x2, x3, x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x1, x2, x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x3, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x2, x3, x4, x5) app_out_ggg(x1, x2, x3) = app_out_ggg(x1, x2, x3) reverse_out_ag(x1, x2) = reverse_out_ag(x1, x2) REVERSE_IN_AA(x1, x2) = REVERSE_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: REVERSE_IN_AA(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) REVERSE_IN_AA(x1, x2) = REVERSE_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: REVERSE_IN_AA -> REVERSE_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: reverse_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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x5) app_out_ggg(x1, x2, x3) = app_out_ggg reverse_out_ag(x1, x2) = reverse_out_ag(x1) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (27) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x5) app_out_ggg(x1, x2, x3) = app_out_ggg reverse_out_ag(x1, x2) = reverse_out_ag(x1) ---------------------------------------- (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: REVERSE_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, reverse_in_aa(Xs, Zs)) REVERSE_IN_AG(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) REVERSE_IN_AA(.(X, Xs), Ys) -> U2_AA(X, Xs, Ys, reverse_in_aa(Xs, Zs)) REVERSE_IN_AA(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) U2_AA(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_AA(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) U2_AA(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> APP_IN_GGA(Zs, .(X, []), Ys) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U1_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) U2_AG(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_AG(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) U2_AG(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> APP_IN_GGG(Zs, .(X, []), Ys) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U1_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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x5) app_out_ggg(x1, x2, x3) = app_out_ggg reverse_out_ag(x1, x2) = reverse_out_ag(x1) REVERSE_IN_AG(x1, x2) = REVERSE_IN_AG(x2) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) REVERSE_IN_AA(x1, x2) = REVERSE_IN_AA U2_AA(x1, x2, x3, x4) = U2_AA(x4) U3_AA(x1, x2, x3, x4) = U3_AA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x5) U3_AG(x1, x2, x3, x4) = U3_AG(x2, x4) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4, x5) = U1_GGG(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) Obligation: Pi DP problem: The TRS P consists of the following rules: REVERSE_IN_AG(.(X, Xs), Ys) -> U2_AG(X, Xs, Ys, reverse_in_aa(Xs, Zs)) REVERSE_IN_AG(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) REVERSE_IN_AA(.(X, Xs), Ys) -> U2_AA(X, Xs, Ys, reverse_in_aa(Xs, Zs)) REVERSE_IN_AA(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) U2_AA(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_AA(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) U2_AA(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> APP_IN_GGA(Zs, .(X, []), Ys) APP_IN_GGA(.(X, Xs), Ys, .(X, Zs)) -> U1_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) U2_AG(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_AG(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) U2_AG(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> APP_IN_GGG(Zs, .(X, []), Ys) APP_IN_GGG(.(X, Xs), Ys, .(X, Zs)) -> U1_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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x5) app_out_ggg(x1, x2, x3) = app_out_ggg reverse_out_ag(x1, x2) = reverse_out_ag(x1) REVERSE_IN_AG(x1, x2) = REVERSE_IN_AG(x2) U2_AG(x1, x2, x3, x4) = U2_AG(x3, x4) REVERSE_IN_AA(x1, x2) = REVERSE_IN_AA U2_AA(x1, x2, x3, x4) = U2_AA(x4) U3_AA(x1, x2, x3, x4) = U3_AA(x2, x4) APP_IN_GGA(x1, x2, x3) = APP_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x5) U3_AG(x1, x2, x3, x4) = U3_AG(x2, x4) APP_IN_GGG(x1, x2, x3) = APP_IN_GGG(x1, x2, x3) U1_GGG(x1, x2, x3, x4, x5) = U1_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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x5) app_out_ggg(x1, x2, x3) = app_out_ggg reverse_out_ag(x1, x2) = reverse_out_ag(x1) 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: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x5) app_out_ggg(x1, x2, x3) = app_out_ggg reverse_out_ag(x1, x2) = reverse_out_ag(x1) 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: REVERSE_IN_AA(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) The TRS R consists of the following rules: reverse_in_ag(.(X, Xs), Ys) -> U2_ag(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa(.(X, Xs), Ys) -> U2_aa(X, Xs, Ys, reverse_in_aa(Xs, Zs)) reverse_in_aa([], []) -> reverse_out_aa([], []) U2_aa(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_aa(X, Xs, Ys, app_in_gga(Zs, .(X, []), Ys)) app_in_gga(.(X, Xs), Ys, .(X, Zs)) -> U1_gga(X, Xs, Ys, Zs, app_in_gga(Xs, Ys, Zs)) app_in_gga([], Ys, Ys) -> app_out_gga([], Ys, Ys) U1_gga(X, Xs, Ys, Zs, app_out_gga(Xs, Ys, Zs)) -> app_out_gga(.(X, Xs), Ys, .(X, Zs)) U3_aa(X, Xs, Ys, app_out_gga(Zs, .(X, []), Ys)) -> reverse_out_aa(.(X, Xs), Ys) U2_ag(X, Xs, Ys, reverse_out_aa(Xs, Zs)) -> U3_ag(X, Xs, Ys, app_in_ggg(Zs, .(X, []), Ys)) app_in_ggg(.(X, Xs), Ys, .(X, Zs)) -> U1_ggg(X, Xs, Ys, Zs, app_in_ggg(Xs, Ys, Zs)) app_in_ggg([], Ys, Ys) -> app_out_ggg([], Ys, Ys) U1_ggg(X, Xs, Ys, Zs, app_out_ggg(Xs, Ys, Zs)) -> app_out_ggg(.(X, Xs), Ys, .(X, Zs)) U3_ag(X, Xs, Ys, app_out_ggg(Zs, .(X, []), Ys)) -> reverse_out_ag(.(X, Xs), Ys) reverse_in_ag([], []) -> reverse_out_ag([], []) The argument filtering Pi contains the following mapping: reverse_in_ag(x1, x2) = reverse_in_ag(x2) U2_ag(x1, x2, x3, x4) = U2_ag(x3, x4) reverse_in_aa(x1, x2) = reverse_in_aa U2_aa(x1, x2, x3, x4) = U2_aa(x4) reverse_out_aa(x1, x2) = reverse_out_aa(x1, x2) U3_aa(x1, x2, x3, x4) = U3_aa(x2, x4) app_in_gga(x1, x2, x3) = app_in_gga(x1, x2) .(x1, x2) = .(x2) U1_gga(x1, x2, x3, x4, x5) = U1_gga(x5) [] = [] app_out_gga(x1, x2, x3) = app_out_gga(x3) U3_ag(x1, x2, x3, x4) = U3_ag(x2, x4) app_in_ggg(x1, x2, x3) = app_in_ggg(x1, x2, x3) U1_ggg(x1, x2, x3, x4, x5) = U1_ggg(x5) app_out_ggg(x1, x2, x3) = app_out_ggg reverse_out_ag(x1, x2) = reverse_out_ag(x1) REVERSE_IN_AA(x1, x2) = REVERSE_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: REVERSE_IN_AA(.(X, Xs), Ys) -> REVERSE_IN_AA(Xs, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) REVERSE_IN_AA(x1, x2) = REVERSE_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: REVERSE_IN_AA -> REVERSE_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": 6, "program": { "directives": [], "clauses": [ [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ], [ "(app ([]) Ys Ys)", null ], [ "(reverse (. X Xs) Ys)", "(',' (reverse Xs Zs) (app Zs (. X ([])) Ys))" ], [ "(reverse ([]) ([]))", null ] ] }, "graph": { "nodes": { "190": { "goal": [{ "clause": 3, "scope": 2, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "191": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (reverse T36 X50) (app X50 (. T37 ([])) X51))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X51", "X50" ], "exprvars": [] } }, "192": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "193": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T36 X50)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X50"], "exprvars": [] } }, "type": "Nodes", "194": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "250": { "goal": [{ "clause": 0, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "251": { "goal": [{ "clause": 1, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "211": { "goal": [ { "clause": 0, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }, { "clause": 1, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "213": { "goal": [{ "clause": 0, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "279": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "214": { "goal": [{ "clause": 1, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "217": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T62 (. T63 ([])) X91)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X91"], "exprvars": [] } }, "218": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "33": { "goal": [{ "clause": 2, "scope": 1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "79": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (reverse T18 X18) (app X18 (. T19 ([])) T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": ["X18"], "exprvars": [] } }, "36": { "goal": [{ "clause": 3, "scope": 1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "280": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "281": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "282": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "284": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "186": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "187": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "286": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "188": { "goal": [ { "clause": 2, "scope": 2, "term": "(reverse T18 X18)" }, { "clause": 3, "scope": 2, "term": "(reverse T18 X18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "243": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "265": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T94 (. T95 ([])) T93)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T93"], "free": [], "exprvars": [] } }, "189": { "goal": [{ "clause": 2, "scope": 2, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "222": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "266": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "223": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "245": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "224": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "246": { "goal": [ { "clause": 0, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" }, { "clause": 1, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "225": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "7": { "goal": [ { "clause": 2, "scope": 1, "term": "(reverse T1 T2)" }, { "clause": 3, "scope": 1, "term": "(reverse T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "80": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 6, "to": 7, "label": "CASE" }, { "from": 7, "to": 33, "label": "PARALLEL" }, { "from": 7, "to": 36, "label": "PARALLEL" }, { "from": 33, "to": 79, "label": "EVAL with clause\nreverse(.(X15, X16), X17) :- ','(reverse(X16, X18), app(X18, .(X15, []), X17)).\nand substitutionX15 -> T19,\nX16 -> T18,\nT1 -> .(T19, T18),\nT2 -> T17,\nX17 -> T17,\nT16 -> T18,\nT15 -> T19" }, { "from": 33, "to": 80, "label": "EVAL-BACKTRACK" }, { "from": 36, "to": 282, "label": "EVAL with clause\nreverse([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 36, "to": 284, "label": "EVAL-BACKTRACK" }, { "from": 79, "to": 186, "label": "SPLIT 1" }, { "from": 79, "to": 187, "label": "SPLIT 2\nreplacements:X18 -> T22,\nT19 -> T23" }, { "from": 186, "to": 188, "label": "CASE" }, { "from": 187, "to": 246, "label": "CASE" }, { "from": 188, "to": 189, "label": "PARALLEL" }, { "from": 188, "to": 190, "label": "PARALLEL" }, { "from": 189, "to": 191, "label": "EVAL with clause\nreverse(.(X47, X48), X49) :- ','(reverse(X48, X50), app(X50, .(X47, []), X49)).\nand substitutionX47 -> T37,\nX48 -> T36,\nT18 -> .(T37, T36),\nX18 -> X51,\nX49 -> X51,\nT35 -> T36,\nT34 -> T37" }, { "from": 189, "to": 192, "label": "EVAL-BACKTRACK" }, { "from": 190, "to": 225, "label": "EVAL with clause\nreverse([], []).\nand substitutionT18 -> [],\nX18 -> []" }, { "from": 190, "to": 243, "label": "EVAL-BACKTRACK" }, { "from": 191, "to": 193, "label": "SPLIT 1" }, { "from": 191, "to": 194, "label": "SPLIT 2\nreplacements:X50 -> T40,\nT37 -> T41" }, { "from": 193, "to": 186, "label": "INSTANCE with matching:\nT18 -> T36\nX18 -> X50" }, { "from": 194, "to": 211, "label": "CASE" }, { "from": 211, "to": 213, "label": "PARALLEL" }, { "from": 211, "to": 214, "label": "PARALLEL" }, { "from": 213, "to": 217, "label": "EVAL with clause\napp(.(X87, X88), X89, .(X87, X90)) :- app(X88, X89, X90).\nand substitutionX87 -> T59,\nX88 -> T62,\nT40 -> .(T59, T62),\nT41 -> T63,\nX89 -> .(T63, []),\nX90 -> X91,\nX51 -> .(T59, X91),\nT60 -> T62,\nT61 -> T63" }, { "from": 213, "to": 218, "label": "EVAL-BACKTRACK" }, { "from": 214, "to": 222, "label": "EVAL with clause\napp([], X99, X99).\nand substitutionT40 -> [],\nT41 -> T69,\nX99 -> .(T69, []),\nX51 -> .(T69, [])" }, { "from": 214, "to": 223, "label": "EVAL-BACKTRACK" }, { "from": 217, "to": 194, "label": "INSTANCE with matching:\nT40 -> T62\nT41 -> T63\nX51 -> X91" }, { "from": 222, "to": 224, "label": "SUCCESS" }, { "from": 225, "to": 245, "label": "SUCCESS" }, { "from": 246, "to": 250, "label": "PARALLEL" }, { "from": 246, "to": 251, "label": "PARALLEL" }, { "from": 250, "to": 265, "label": "EVAL with clause\napp(.(X120, X121), X122, .(X120, X123)) :- app(X121, X122, X123).\nand substitutionX120 -> T90,\nX121 -> T94,\nT22 -> .(T90, T94),\nT23 -> T95,\nX122 -> .(T95, []),\nX123 -> T93,\nT17 -> .(T90, T93),\nT91 -> T94,\nT92 -> T95" }, { "from": 250, "to": 266, "label": "EVAL-BACKTRACK" }, { "from": 251, "to": 279, "label": "EVAL with clause\napp([], X130, X130).\nand substitutionT22 -> [],\nT23 -> T102,\nX130 -> .(T102, []),\nT17 -> .(T102, [])" }, { "from": 251, "to": 280, "label": "EVAL-BACKTRACK" }, { "from": 265, "to": 187, "label": "INSTANCE with matching:\nT22 -> T94\nT23 -> T95\nT17 -> T93" }, { "from": 279, "to": 281, "label": "SUCCESS" }, { "from": 282, "to": 286, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (52) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f6_in(T17) -> U1(f79_in(T17), T17) U1(f79_out1(X18, T19), T17) -> f6_out1 f6_in([]) -> f6_out1 f186_in -> U2(f191_in) U2(f191_out1) -> f186_out1 f186_in -> f186_out1 f194_in -> U3(f194_in) U3(f194_out1) -> f194_out1 f194_in -> f194_out1 f187_in(.(T90, T93)) -> U4(f187_in(T93), .(T90, T93)) U4(f187_out1(T94, T95), .(T90, T93)) -> f187_out1(.(T90, T94), T95) f187_in(.(T102, [])) -> f187_out1([], T102) f79_in(T17) -> U5(f186_in, T17) U5(f186_out1, T17) -> U6(f187_in(T17), T17) U6(f187_out1(T22, T23), T17) -> f79_out1(T22, T23) f191_in -> U7(f186_in) U7(f186_out1) -> U8(f194_in) U8(f194_out1) -> f191_out1 Q is empty. ---------------------------------------- (53) QTRSRRRProof (EQUIVALENT) Used ordering: f6_in/1(YES) U1/2(YES,YES) f79_in/1(YES) f79_out1/2(YES,YES) f6_out1/0) []/0) f186_in/0) U2/1)YES( f191_in/0) f191_out1/0) f186_out1/0) f194_in/0) U3/1)YES( f194_out1/0) f187_in/1(YES) ./2(YES,YES) U4/2(YES,YES) f187_out1/2(YES,YES) U5/2(YES,YES) U6/2(YES,YES) U7/1)YES( U8/1)YES( Quasi precedence: f6_in_1 > [U1_2, f6_out1] > ._2 f6_in_1 > [f79_in_1, f186_in, f191_in, f191_out1, f186_out1, f194_in, f194_out1] > U5_2 > [[], f187_in_1] > [U4_2, f187_out1_2] > f79_out1_2 > ._2 f6_in_1 > [f79_in_1, f186_in, f191_in, f191_out1, f186_out1, f194_in, f194_out1] > U5_2 > U6_2 > f79_out1_2 > ._2 Status: f6_in_1: multiset status U1_2: multiset status f79_in_1: multiset status f79_out1_2: multiset status f6_out1: multiset status []: multiset status f186_in: multiset status f191_in: multiset status f191_out1: multiset status f186_out1: multiset status f194_in: multiset status f194_out1: multiset status f187_in_1: [1] ._2: [1,2] U4_2: [1,2] f187_out1_2: [2,1] 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: f6_in(T17) -> U1(f79_in(T17), T17) U1(f79_out1(X18, T19), T17) -> f6_out1 f6_in([]) -> f6_out1 f187_in(.(T90, T93)) -> U4(f187_in(T93), .(T90, T93)) U4(f187_out1(T94, T95), .(T90, T93)) -> f187_out1(.(T90, T94), T95) f187_in(.(T102, [])) -> f187_out1([], T102) f79_in(T17) -> U5(f186_in, T17) U5(f186_out1, T17) -> U6(f187_in(T17), T17) U6(f187_out1(T22, T23), T17) -> f79_out1(T22, T23) ---------------------------------------- (54) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f186_in -> U2(f191_in) U2(f191_out1) -> f186_out1 f186_in -> f186_out1 f194_in -> U3(f194_in) U3(f194_out1) -> f194_out1 f194_in -> f194_out1 f191_in -> U7(f186_in) U7(f186_out1) -> U8(f194_in) U8(f194_out1) -> f191_out1 Q is empty. ---------------------------------------- (55) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U2(x_1)) = x_1 POL(U3(x_1)) = x_1 POL(U7(x_1)) = x_1 POL(U8(x_1)) = 2*x_1 POL(f186_in) = 1 POL(f186_out1) = 0 POL(f191_in) = 1 POL(f191_out1) = 0 POL(f194_in) = 0 POL(f194_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f186_in -> f186_out1 ---------------------------------------- (56) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f186_in -> U2(f191_in) U2(f191_out1) -> f186_out1 f194_in -> U3(f194_in) U3(f194_out1) -> f194_out1 f194_in -> f194_out1 f191_in -> U7(f186_in) U7(f186_out1) -> U8(f194_in) U8(f194_out1) -> f191_out1 Q is empty. ---------------------------------------- (57) 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(f186_in) = 0 POL(f186_out1) = 2 POL(f191_in) = 0 POL(f191_out1) = 1 POL(f194_in) = 1 POL(f194_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f194_in -> f194_out1 U7(f186_out1) -> U8(f194_in) U8(f194_out1) -> f191_out1 ---------------------------------------- (58) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f186_in -> U2(f191_in) U2(f191_out1) -> f186_out1 f194_in -> U3(f194_in) U3(f194_out1) -> f194_out1 f191_in -> U7(f186_in) Q is empty. ---------------------------------------- (59) 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(f186_in) = 0 POL(f186_out1) = 0 POL(f191_in) = 0 POL(f191_out1) = 1 POL(f194_in) = 0 POL(f194_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U2(f191_out1) -> f186_out1 ---------------------------------------- (60) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f186_in -> U2(f191_in) f194_in -> U3(f194_in) U3(f194_out1) -> f194_out1 f191_in -> U7(f186_in) Q is empty. ---------------------------------------- (61) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ], [ "(app ([]) Ys Ys)", null ], [ "(reverse (. X Xs) Ys)", "(',' (reverse Xs Zs) (app Zs (. X ([])) Ys))" ], [ "(reverse ([]) ([]))", null ] ] }, "graph": { "nodes": { "48": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (reverse T9 X7) (app X7 (. T10 ([])) T8))" }, { "clause": 3, "scope": 1, "term": "(reverse T1 T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": ["X7"], "exprvars": [] } }, "type": "Nodes", "310": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "237": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T67 (. T68 ([])) X103)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X103"], "exprvars": [] } }, "238": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "239": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "54": { "goal": [{ "clause": 3, "scope": 1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [[ "(reverse T1 T2)", "(reverse (. X4 X5) X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [ "X4", "X5", "X6" ], "exprvars": [] } }, "283": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "240": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "241": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "285": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "165": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (reverse T9 X7) (app X7 (. T10 ([])) T8))" }, { "clause": 3, "scope": 2, "term": "(',' (reverse T9 X7) (app X7 (. T10 ([])) T8))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(reverse T1 T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": ["X7"], "exprvars": [] } }, "166": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (reverse T9 X7) (app X7 (. T10 ([])) T8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": ["X7"], "exprvars": [] } }, "287": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "167": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (reverse T9 X7) (app X7 (. T10 ([])) T8))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(reverse T1 T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": ["X7"], "exprvars": [] } }, "288": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T26 (. T27 ([])) X30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X30"], "exprvars": [] } }, "168": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (reverse T21 X29) (app X29 (. T22 ([])) X30)) (app X30 (. T23 ([])) T8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [ "X30", "X29" ], "exprvars": [] } }, "289": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T78 (. T79 ([])) T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "169": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": 2, "scope": 1, "term": "(reverse T1 T2)" }, { "clause": 3, "scope": 1, "term": "(reverse T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "204": { "goal": [ { "clause": 2, "scope": 3, "term": "(reverse T21 X29)" }, { "clause": 3, "scope": 3, "term": "(reverse T21 X29)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "205": { "goal": [{ "clause": 2, "scope": 3, "term": "(reverse T21 X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "206": { "goal": [{ "clause": 3, "scope": 3, "term": "(reverse T21 X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "207": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (reverse T41 X62) (app X62 (. T42 ([])) X63))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X63", "X62" ], "exprvars": [] } }, "208": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "209": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T41 X62)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X62"], "exprvars": [] } }, "290": { "goal": [ { "clause": 0, "scope": 5, "term": "(app T78 (. T79 ([])) T8)" }, { "clause": 1, "scope": 5, "term": "(app T78 (. T79 ([])) T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "293": { "goal": [{ "clause": 0, "scope": 5, "term": "(app T78 (. T79 ([])) T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "294": { "goal": [{ "clause": 1, "scope": 5, "term": "(app T78 (. T79 ([])) T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "295": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T107 (. T108 ([])) T106)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T106"], "free": [], "exprvars": [] } }, "296": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "297": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "210": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T45 (. T46 ([])) X63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X63"], "exprvars": [] } }, "298": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "299": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "212": { "goal": [ { "clause": 0, "scope": 4, "term": "(app T45 (. T46 ([])) X63)" }, { "clause": 1, "scope": 4, "term": "(app T45 (. T46 ([])) X63)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X63"], "exprvars": [] } }, "215": { "goal": [{ "clause": 0, "scope": 4, "term": "(app T45 (. T46 ([])) X63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X63"], "exprvars": [] } }, "216": { "goal": [{ "clause": 1, "scope": 4, "term": "(app T45 (. T46 ([])) X63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X63"], "exprvars": [] } }, "184": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T21 X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "185": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T26 (. T27 ([])) X30) (app X30 (. T28 ([])) T8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": ["X30"], "exprvars": [] } }, "300": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (reverse T9 X7) (app X7 (. T10 ([])) T8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": ["X7"], "exprvars": [] } }, "301": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 3, "scope": 1, "term": "(reverse T1 T8)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "302": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) (. T116 ([])) T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "303": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "304": { "goal": [{ "clause": 3, "scope": 1, "term": "(reverse T1 T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "305": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "306": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "307": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "308": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "309": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 48, "label": "EVAL with clause\nreverse(.(X4, X5), X6) :- ','(reverse(X5, X7), app(X7, .(X4, []), X6)).\nand substitutionX4 -> T10,\nX5 -> T9,\nT1 -> .(T10, T9),\nT2 -> T8,\nX6 -> T8,\nT7 -> T9,\nT6 -> T10" }, { "from": 5, "to": 54, "label": "EVAL-BACKTRACK" }, { "from": 48, "to": 165, "label": "CASE" }, { "from": 54, "to": 308, "label": "EVAL with clause\nreverse([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 54, "to": 309, "label": "EVAL-BACKTRACK" }, { "from": 165, "to": 166, "label": "PARALLEL" }, { "from": 165, "to": 167, "label": "PARALLEL" }, { "from": 166, "to": 168, "label": "EVAL with clause\nreverse(.(X26, X27), X28) :- ','(reverse(X27, X29), app(X29, .(X26, []), X28)).\nand substitutionX26 -> T22,\nX27 -> T21,\nT9 -> .(T22, T21),\nX7 -> X30,\nX28 -> X30,\nT20 -> T21,\nT19 -> T22,\nT10 -> T23" }, { "from": 166, "to": 169, "label": "EVAL-BACKTRACK" }, { "from": 167, "to": 300, "label": "PARALLEL" }, { "from": 167, "to": 301, "label": "PARALLEL" }, { "from": 168, "to": 184, "label": "SPLIT 1" }, { "from": 168, "to": 185, "label": "SPLIT 2\nreplacements:X29 -> T26,\nT22 -> T27,\nT23 -> T28" }, { "from": 184, "to": 204, "label": "CASE" }, { "from": 185, "to": 288, "label": "SPLIT 1" }, { "from": 185, "to": 289, "label": "SPLIT 2\nreplacements:X30 -> T78,\nT28 -> T79" }, { "from": 204, "to": 205, "label": "PARALLEL" }, { "from": 204, "to": 206, "label": "PARALLEL" }, { "from": 205, "to": 207, "label": "EVAL with clause\nreverse(.(X59, X60), X61) :- ','(reverse(X60, X62), app(X62, .(X59, []), X61)).\nand substitutionX59 -> T42,\nX60 -> T41,\nT21 -> .(T42, T41),\nX29 -> X63,\nX61 -> X63,\nT40 -> T41,\nT39 -> T42" }, { "from": 205, "to": 208, "label": "EVAL-BACKTRACK" }, { "from": 206, "to": 283, "label": "EVAL with clause\nreverse([], []).\nand substitutionT21 -> [],\nX29 -> []" }, { "from": 206, "to": 285, "label": "EVAL-BACKTRACK" }, { "from": 207, "to": 209, "label": "SPLIT 1" }, { "from": 207, "to": 210, "label": "SPLIT 2\nreplacements:X62 -> T45,\nT42 -> T46" }, { "from": 209, "to": 184, "label": "INSTANCE with matching:\nT21 -> T41\nX29 -> X62" }, { "from": 210, "to": 212, "label": "CASE" }, { "from": 212, "to": 215, "label": "PARALLEL" }, { "from": 212, "to": 216, "label": "PARALLEL" }, { "from": 215, "to": 237, "label": "EVAL with clause\napp(.(X99, X100), X101, .(X99, X102)) :- app(X100, X101, X102).\nand substitutionX99 -> T64,\nX100 -> T67,\nT45 -> .(T64, T67),\nT46 -> T68,\nX101 -> .(T68, []),\nX102 -> X103,\nX63 -> .(T64, X103),\nT65 -> T67,\nT66 -> T68" }, { "from": 215, "to": 238, "label": "EVAL-BACKTRACK" }, { "from": 216, "to": 239, "label": "EVAL with clause\napp([], X111, X111).\nand substitutionT45 -> [],\nT46 -> T74,\nX111 -> .(T74, []),\nX63 -> .(T74, [])" }, { "from": 216, "to": 240, "label": "EVAL-BACKTRACK" }, { "from": 237, "to": 210, "label": "INSTANCE with matching:\nT45 -> T67\nT46 -> T68\nX63 -> X103" }, { "from": 239, "to": 241, "label": "SUCCESS" }, { "from": 283, "to": 287, "label": "SUCCESS" }, { "from": 288, "to": 210, "label": "INSTANCE with matching:\nT45 -> T26\nT46 -> T27\nX63 -> X30" }, { "from": 289, "to": 290, "label": "CASE" }, { "from": 290, "to": 293, "label": "PARALLEL" }, { "from": 290, "to": 294, "label": "PARALLEL" }, { "from": 293, "to": 295, "label": "EVAL with clause\napp(.(X142, X143), X144, .(X142, X145)) :- app(X143, X144, X145).\nand substitutionX142 -> T103,\nX143 -> T107,\nT78 -> .(T103, T107),\nT79 -> T108,\nX144 -> .(T108, []),\nX145 -> T106,\nT8 -> .(T103, T106),\nT104 -> T107,\nT105 -> T108" }, { "from": 293, "to": 296, "label": "EVAL-BACKTRACK" }, { "from": 294, "to": 297, "label": "EVAL with clause\napp([], X152, X152).\nand substitutionT78 -> [],\nT79 -> T115,\nX152 -> .(T115, []),\nT8 -> .(T115, [])" }, { "from": 294, "to": 298, "label": "EVAL-BACKTRACK" }, { "from": 295, "to": 289, "label": "INSTANCE with matching:\nT78 -> T107\nT79 -> T108\nT8 -> T106" }, { "from": 297, "to": 299, "label": "SUCCESS" }, { "from": 300, "to": 302, "label": "EVAL with clause\nreverse([], []).\nand substitutionT9 -> [],\nX7 -> [],\nT10 -> T116" }, { "from": 300, "to": 303, "label": "EVAL-BACKTRACK" }, { "from": 301, "to": 304, "label": "FAILURE" }, { "from": 302, "to": 289, "label": "INSTANCE with matching:\nT78 -> []\nT79 -> T116" }, { "from": 304, "to": 305, "label": "EVAL with clause\nreverse([], []).\nand substitutionT1 -> [],\nT8 -> []" }, { "from": 304, "to": 306, "label": "EVAL-BACKTRACK" }, { "from": 305, "to": 307, "label": "SUCCESS" }, { "from": 308, "to": 310, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (62) Obligation: Triples: reverseA(.(X1, X2), X3) :- reverseA(X2, X4). reverseA(.(X1, X2), X3) :- ','(reversecA(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). reverseD(.(X1, .(X2, X3)), X4) :- reverseA(X3, X5). reverseD(.(X1, .(X2, X3)), X4) :- ','(reversecA(X3, X5), appB(X5, X2, X6)). reverseD(.(X1, .(X2, X3)), X4) :- ','(reversecA(X3, X5), ','(appcB(X5, X2, X6), appC(X6, X1, X4))). reverseD(.(X1, []), X2) :- appC([], X1, X2). Clauses: reversecA(.(X1, X2), X3) :- ','(reversecA(X2, X4), appcB(X4, X1, X3)). reversecA([], []). appcB(.(X1, X2), X3, .(X1, X4)) :- appcB(X2, X3, X4). appcB([], X1, .(X1, [])). appcC(.(X1, X2), X3, .(X1, X4)) :- appcC(X2, X3, X4). appcC([], X1, .(X1, [])). Afs: reverseD(x1, x2) = reverseD(x2) ---------------------------------------- (63) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: reverseD_in_2: (f,b) reverseA_in_2: (f,f) reversecA_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: REVERSED_IN_AG(.(X1, .(X2, X3)), X4) -> U6_AG(X1, X2, X3, X4, reverseA_in_aa(X3, X5)) REVERSED_IN_AG(.(X1, .(X2, X3)), X4) -> REVERSEA_IN_AA(X3, X5) REVERSEA_IN_AA(.(X1, X2), X3) -> U1_AA(X1, X2, X3, reverseA_in_aa(X2, X4)) REVERSEA_IN_AA(.(X1, X2), X3) -> REVERSEA_IN_AA(X2, X4) REVERSEA_IN_AA(.(X1, X2), X3) -> U2_AA(X1, X2, X3, reversecA_in_aa(X2, X4)) U2_AA(X1, X2, X3, reversecA_out_aa(X2, X4)) -> U3_AA(X1, X2, X3, appB_in_gaa(X4, X1, X3)) U2_AA(X1, X2, X3, reversecA_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) REVERSED_IN_AG(.(X1, .(X2, X3)), X4) -> U7_AG(X1, X2, X3, X4, reversecA_in_aa(X3, X5)) U7_AG(X1, X2, X3, X4, reversecA_out_aa(X3, X5)) -> U8_AG(X1, X2, X3, X4, appB_in_gaa(X5, X2, X6)) U7_AG(X1, X2, X3, X4, reversecA_out_aa(X3, X5)) -> APPB_IN_GAA(X5, X2, X6) U7_AG(X1, X2, X3, X4, reversecA_out_aa(X3, X5)) -> U9_AG(X1, X2, X3, X4, appcB_in_gaa(X5, X2, X6)) U9_AG(X1, X2, X3, X4, appcB_out_gaa(X5, X2, X6)) -> U10_AG(X1, X2, X3, X4, appC_in_gag(X6, X1, X4)) U9_AG(X1, X2, X3, X4, appcB_out_gaa(X5, X2, X6)) -> APPC_IN_GAG(X6, X1, X4) 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) REVERSED_IN_AG(.(X1, []), X2) -> U11_AG(X1, X2, appC_in_gag([], X1, X2)) REVERSED_IN_AG(.(X1, []), X2) -> APPC_IN_GAG([], X1, X2) The TRS R consists of the following rules: reversecA_in_aa(.(X1, X2), X3) -> U13_aa(X1, X2, X3, reversecA_in_aa(X2, X4)) reversecA_in_aa([], []) -> reversecA_out_aa([], []) U13_aa(X1, X2, X3, reversecA_out_aa(X2, X4)) -> U14_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U15_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) U15_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U14_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> reversecA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: reverseA_in_aa(x1, x2) = reverseA_in_aa reversecA_in_aa(x1, x2) = reversecA_in_aa U13_aa(x1, x2, x3, x4) = U13_aa(x4) reversecA_out_aa(x1, x2) = reversecA_out_aa(x1, x2) U14_aa(x1, x2, x3, x4) = U14_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) .(x1, x2) = .(x2) U15_gaa(x1, x2, x3, x4, x5) = U15_gaa(x2, x5) [] = [] appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) appB_in_gaa(x1, x2, x3) = appB_in_gaa(x1) appC_in_gag(x1, x2, x3) = appC_in_gag(x1, x3) REVERSED_IN_AG(x1, x2) = REVERSED_IN_AG(x2) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x4, x5) REVERSEA_IN_AA(x1, x2) = REVERSEA_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, x5) = U7_AG(x4, x5) U8_AG(x1, x2, x3, x4, x5) = U8_AG(x3, x4, x5) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x3, x4, x5) U10_AG(x1, x2, x3, x4, x5) = U10_AG(x3, x4, x5) APPC_IN_GAG(x1, x2, x3) = APPC_IN_GAG(x1, x3) U5_GAG(x1, x2, x3, x4, x5) = U5_GAG(x2, x4, x5) U11_AG(x1, x2, x3) = U11_AG(x2, x3) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (64) Obligation: Pi DP problem: The TRS P consists of the following rules: REVERSED_IN_AG(.(X1, .(X2, X3)), X4) -> U6_AG(X1, X2, X3, X4, reverseA_in_aa(X3, X5)) REVERSED_IN_AG(.(X1, .(X2, X3)), X4) -> REVERSEA_IN_AA(X3, X5) REVERSEA_IN_AA(.(X1, X2), X3) -> U1_AA(X1, X2, X3, reverseA_in_aa(X2, X4)) REVERSEA_IN_AA(.(X1, X2), X3) -> REVERSEA_IN_AA(X2, X4) REVERSEA_IN_AA(.(X1, X2), X3) -> U2_AA(X1, X2, X3, reversecA_in_aa(X2, X4)) U2_AA(X1, X2, X3, reversecA_out_aa(X2, X4)) -> U3_AA(X1, X2, X3, appB_in_gaa(X4, X1, X3)) U2_AA(X1, X2, X3, reversecA_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) REVERSED_IN_AG(.(X1, .(X2, X3)), X4) -> U7_AG(X1, X2, X3, X4, reversecA_in_aa(X3, X5)) U7_AG(X1, X2, X3, X4, reversecA_out_aa(X3, X5)) -> U8_AG(X1, X2, X3, X4, appB_in_gaa(X5, X2, X6)) U7_AG(X1, X2, X3, X4, reversecA_out_aa(X3, X5)) -> APPB_IN_GAA(X5, X2, X6) U7_AG(X1, X2, X3, X4, reversecA_out_aa(X3, X5)) -> U9_AG(X1, X2, X3, X4, appcB_in_gaa(X5, X2, X6)) U9_AG(X1, X2, X3, X4, appcB_out_gaa(X5, X2, X6)) -> U10_AG(X1, X2, X3, X4, appC_in_gag(X6, X1, X4)) U9_AG(X1, X2, X3, X4, appcB_out_gaa(X5, X2, X6)) -> APPC_IN_GAG(X6, X1, X4) 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) REVERSED_IN_AG(.(X1, []), X2) -> U11_AG(X1, X2, appC_in_gag([], X1, X2)) REVERSED_IN_AG(.(X1, []), X2) -> APPC_IN_GAG([], X1, X2) The TRS R consists of the following rules: reversecA_in_aa(.(X1, X2), X3) -> U13_aa(X1, X2, X3, reversecA_in_aa(X2, X4)) reversecA_in_aa([], []) -> reversecA_out_aa([], []) U13_aa(X1, X2, X3, reversecA_out_aa(X2, X4)) -> U14_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U15_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) U15_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U14_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> reversecA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: reverseA_in_aa(x1, x2) = reverseA_in_aa reversecA_in_aa(x1, x2) = reversecA_in_aa U13_aa(x1, x2, x3, x4) = U13_aa(x4) reversecA_out_aa(x1, x2) = reversecA_out_aa(x1, x2) U14_aa(x1, x2, x3, x4) = U14_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) .(x1, x2) = .(x2) U15_gaa(x1, x2, x3, x4, x5) = U15_gaa(x2, x5) [] = [] appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) appB_in_gaa(x1, x2, x3) = appB_in_gaa(x1) appC_in_gag(x1, x2, x3) = appC_in_gag(x1, x3) REVERSED_IN_AG(x1, x2) = REVERSED_IN_AG(x2) U6_AG(x1, x2, x3, x4, x5) = U6_AG(x4, x5) REVERSEA_IN_AA(x1, x2) = REVERSEA_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, x5) = U7_AG(x4, x5) U8_AG(x1, x2, x3, x4, x5) = U8_AG(x3, x4, x5) U9_AG(x1, x2, x3, x4, x5) = U9_AG(x3, x4, x5) U10_AG(x1, x2, x3, x4, x5) = U10_AG(x3, x4, x5) APPC_IN_GAG(x1, x2, x3) = APPC_IN_GAG(x1, x3) U5_GAG(x1, x2, x3, x4, x5) = U5_GAG(x2, x4, x5) U11_AG(x1, x2, x3) = U11_AG(x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (65) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 16 less nodes. ---------------------------------------- (66) Complex Obligation (AND) ---------------------------------------- (67) 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: reversecA_in_aa(.(X1, X2), X3) -> U13_aa(X1, X2, X3, reversecA_in_aa(X2, X4)) reversecA_in_aa([], []) -> reversecA_out_aa([], []) U13_aa(X1, X2, X3, reversecA_out_aa(X2, X4)) -> U14_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U15_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) U15_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U14_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> reversecA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: reversecA_in_aa(x1, x2) = reversecA_in_aa U13_aa(x1, x2, x3, x4) = U13_aa(x4) reversecA_out_aa(x1, x2) = reversecA_out_aa(x1, x2) U14_aa(x1, x2, x3, x4) = U14_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) .(x1, x2) = .(x2) U15_gaa(x1, x2, x3, x4, x5) = U15_gaa(x2, x5) [] = [] appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) APPC_IN_GAG(x1, x2, x3) = APPC_IN_GAG(x1, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (68) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (69) 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 ---------------------------------------- (70) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (71) 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. ---------------------------------------- (72) 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 ---------------------------------------- (73) YES ---------------------------------------- (74) 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: reversecA_in_aa(.(X1, X2), X3) -> U13_aa(X1, X2, X3, reversecA_in_aa(X2, X4)) reversecA_in_aa([], []) -> reversecA_out_aa([], []) U13_aa(X1, X2, X3, reversecA_out_aa(X2, X4)) -> U14_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U15_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) U15_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U14_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> reversecA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: reversecA_in_aa(x1, x2) = reversecA_in_aa U13_aa(x1, x2, x3, x4) = U13_aa(x4) reversecA_out_aa(x1, x2) = reversecA_out_aa(x1, x2) U14_aa(x1, x2, x3, x4) = U14_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) .(x1, x2) = .(x2) U15_gaa(x1, x2, x3, x4, x5) = U15_gaa(x2, x5) [] = [] appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) APPB_IN_GAA(x1, x2, x3) = APPB_IN_GAA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (75) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (76) 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 ---------------------------------------- (77) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (78) 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. ---------------------------------------- (79) 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 ---------------------------------------- (80) YES ---------------------------------------- (81) Obligation: Pi DP problem: The TRS P consists of the following rules: REVERSEA_IN_AA(.(X1, X2), X3) -> REVERSEA_IN_AA(X2, X4) The TRS R consists of the following rules: reversecA_in_aa(.(X1, X2), X3) -> U13_aa(X1, X2, X3, reversecA_in_aa(X2, X4)) reversecA_in_aa([], []) -> reversecA_out_aa([], []) U13_aa(X1, X2, X3, reversecA_out_aa(X2, X4)) -> U14_aa(X1, X2, X3, appcB_in_gaa(X4, X1, X3)) appcB_in_gaa(.(X1, X2), X3, .(X1, X4)) -> U15_gaa(X1, X2, X3, X4, appcB_in_gaa(X2, X3, X4)) appcB_in_gaa([], X1, .(X1, [])) -> appcB_out_gaa([], X1, .(X1, [])) U15_gaa(X1, X2, X3, X4, appcB_out_gaa(X2, X3, X4)) -> appcB_out_gaa(.(X1, X2), X3, .(X1, X4)) U14_aa(X1, X2, X3, appcB_out_gaa(X4, X1, X3)) -> reversecA_out_aa(.(X1, X2), X3) The argument filtering Pi contains the following mapping: reversecA_in_aa(x1, x2) = reversecA_in_aa U13_aa(x1, x2, x3, x4) = U13_aa(x4) reversecA_out_aa(x1, x2) = reversecA_out_aa(x1, x2) U14_aa(x1, x2, x3, x4) = U14_aa(x2, x4) appcB_in_gaa(x1, x2, x3) = appcB_in_gaa(x1) .(x1, x2) = .(x2) U15_gaa(x1, x2, x3, x4, x5) = U15_gaa(x2, x5) [] = [] appcB_out_gaa(x1, x2, x3) = appcB_out_gaa(x1, x3) REVERSEA_IN_AA(x1, x2) = REVERSEA_IN_AA We have to consider all (P,R,Pi)-chains ---------------------------------------- (82) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (83) Obligation: Pi DP problem: The TRS P consists of the following rules: REVERSEA_IN_AA(.(X1, X2), X3) -> REVERSEA_IN_AA(X2, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) REVERSEA_IN_AA(x1, x2) = REVERSEA_IN_AA We have to consider all (P,R,Pi)-chains ---------------------------------------- (84) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: REVERSEA_IN_AA -> REVERSEA_IN_AA R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (86) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ], [ "(app ([]) Ys Ys)", null ], [ "(reverse (. X Xs) Ys)", "(',' (reverse Xs Zs) (app Zs (. X ([])) Ys))" ], [ "(reverse ([]) ([]))", null ] ] }, "graph": { "nodes": { "22": { "goal": [ { "clause": 2, "scope": 1, "term": "(reverse T1 T2)" }, { "clause": 3, "scope": 1, "term": "(reverse T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "291": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "292": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "195": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "196": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "197": { "goal": [ { "clause": 2, "scope": 2, "term": "(reverse T18 X18)" }, { "clause": 3, "scope": 2, "term": "(reverse T18 X18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "230": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "252": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "198": { "goal": [{ "clause": 2, "scope": 2, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "133": { "goal": [{ "clause": 2, "scope": 1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "199": { "goal": [{ "clause": 3, "scope": 2, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "232": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "134": { "goal": [{ "clause": 3, "scope": 1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "233": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "234": { "goal": [ { "clause": 0, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" }, { "clause": 1, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "235": { "goal": [{ "clause": 0, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "236": { "goal": [{ "clause": 1, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "139": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (reverse T18 X18) (app X18 (. T19 ([])) T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": ["X18"], "exprvars": [] } }, "219": { "goal": [ { "clause": 0, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }, { "clause": 1, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "140": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": 0, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "242": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T94 (. T95 ([])) T93)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T93"], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "221": { "goal": [{ "clause": 1, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "200": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (reverse T36 X50) (app X50 (. T37 ([])) X51))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X51", "X50" ], "exprvars": [] } }, "244": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "201": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "202": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T36 X50)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X50"], "exprvars": [] } }, "203": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "247": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "226": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T62 (. T63 ([])) X91)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X91"], "exprvars": [] } }, "248": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "227": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "249": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "228": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "229": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 22, "label": "CASE" }, { "from": 22, "to": 133, "label": "PARALLEL" }, { "from": 22, "to": 134, "label": "PARALLEL" }, { "from": 133, "to": 139, "label": "EVAL with clause\nreverse(.(X15, X16), X17) :- ','(reverse(X16, X18), app(X18, .(X15, []), X17)).\nand substitutionX15 -> T19,\nX16 -> T18,\nT1 -> .(T19, T18),\nT2 -> T17,\nX17 -> T17,\nT16 -> T18,\nT15 -> T19" }, { "from": 133, "to": 140, "label": "EVAL-BACKTRACK" }, { "from": 134, "to": 252, "label": "EVAL with clause\nreverse([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 134, "to": 291, "label": "EVAL-BACKTRACK" }, { "from": 139, "to": 195, "label": "SPLIT 1" }, { "from": 139, "to": 196, "label": "SPLIT 2\nreplacements:X18 -> T22,\nT19 -> T23" }, { "from": 195, "to": 197, "label": "CASE" }, { "from": 196, "to": 234, "label": "CASE" }, { "from": 197, "to": 198, "label": "PARALLEL" }, { "from": 197, "to": 199, "label": "PARALLEL" }, { "from": 198, "to": 200, "label": "EVAL with clause\nreverse(.(X47, X48), X49) :- ','(reverse(X48, X50), app(X50, .(X47, []), X49)).\nand substitutionX47 -> T37,\nX48 -> T36,\nT18 -> .(T37, T36),\nX18 -> X51,\nX49 -> X51,\nT35 -> T36,\nT34 -> T37" }, { "from": 198, "to": 201, "label": "EVAL-BACKTRACK" }, { "from": 199, "to": 231, "label": "EVAL with clause\nreverse([], []).\nand substitutionT18 -> [],\nX18 -> []" }, { "from": 199, "to": 232, "label": "EVAL-BACKTRACK" }, { "from": 200, "to": 202, "label": "SPLIT 1" }, { "from": 200, "to": 203, "label": "SPLIT 2\nreplacements:X50 -> T40,\nT37 -> T41" }, { "from": 202, "to": 195, "label": "INSTANCE with matching:\nT18 -> T36\nX18 -> X50" }, { "from": 203, "to": 219, "label": "CASE" }, { "from": 219, "to": 220, "label": "PARALLEL" }, { "from": 219, "to": 221, "label": "PARALLEL" }, { "from": 220, "to": 226, "label": "EVAL with clause\napp(.(X87, X88), X89, .(X87, X90)) :- app(X88, X89, X90).\nand substitutionX87 -> T59,\nX88 -> T62,\nT40 -> .(T59, T62),\nT41 -> T63,\nX89 -> .(T63, []),\nX90 -> X91,\nX51 -> .(T59, X91),\nT60 -> T62,\nT61 -> T63" }, { "from": 220, "to": 227, "label": "EVAL-BACKTRACK" }, { "from": 221, "to": 228, "label": "EVAL with clause\napp([], X99, X99).\nand substitutionT40 -> [],\nT41 -> T69,\nX99 -> .(T69, []),\nX51 -> .(T69, [])" }, { "from": 221, "to": 229, "label": "EVAL-BACKTRACK" }, { "from": 226, "to": 203, "label": "INSTANCE with matching:\nT40 -> T62\nT41 -> T63\nX51 -> X91" }, { "from": 228, "to": 230, "label": "SUCCESS" }, { "from": 231, "to": 233, "label": "SUCCESS" }, { "from": 234, "to": 235, "label": "PARALLEL" }, { "from": 234, "to": 236, "label": "PARALLEL" }, { "from": 235, "to": 242, "label": "EVAL with clause\napp(.(X120, X121), X122, .(X120, X123)) :- app(X121, X122, X123).\nand substitutionX120 -> T90,\nX121 -> T94,\nT22 -> .(T90, T94),\nT23 -> T95,\nX122 -> .(T95, []),\nX123 -> T93,\nT17 -> .(T90, T93),\nT91 -> T94,\nT92 -> T95" }, { "from": 235, "to": 244, "label": "EVAL-BACKTRACK" }, { "from": 236, "to": 247, "label": "EVAL with clause\napp([], X130, X130).\nand substitutionT22 -> [],\nT23 -> T102,\nX130 -> .(T102, []),\nT17 -> .(T102, [])" }, { "from": 236, "to": 248, "label": "EVAL-BACKTRACK" }, { "from": 242, "to": 196, "label": "INSTANCE with matching:\nT22 -> T94\nT23 -> T95\nT17 -> T93" }, { "from": 247, "to": 249, "label": "SUCCESS" }, { "from": 252, "to": 292, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (87) Complex Obligation (AND) ---------------------------------------- (88) Obligation: Rules: f203_in -> f219_in :|: TRUE f219_out -> f203_out :|: TRUE f227_out -> f220_out :|: TRUE f226_out -> f220_out :|: TRUE f220_in -> f226_in :|: TRUE f220_in -> f227_in :|: TRUE f203_out -> f226_out :|: TRUE f226_in -> f203_in :|: TRUE f220_out -> f219_out :|: TRUE f221_out -> f219_out :|: TRUE f219_in -> f221_in :|: TRUE f219_in -> f220_in :|: TRUE f1_in(T2) -> f22_in(T2) :|: TRUE f22_out(x) -> f1_out(x) :|: TRUE f22_in(x1) -> f133_in(x1) :|: TRUE f133_out(x2) -> f22_out(x2) :|: TRUE f22_in(x3) -> f134_in(x3) :|: TRUE f134_out(x4) -> f22_out(x4) :|: TRUE f139_out(T17) -> f133_out(T17) :|: TRUE f133_in(x5) -> f140_in :|: TRUE f140_out -> f133_out(x6) :|: TRUE f133_in(x7) -> f139_in(x7) :|: TRUE f139_in(x8) -> f195_in :|: TRUE f196_out(x9) -> f139_out(x9) :|: TRUE f195_out -> f196_in(x10) :|: TRUE f197_out -> f195_out :|: TRUE f195_in -> f197_in :|: TRUE f198_out -> f197_out :|: TRUE f197_in -> f198_in :|: TRUE f197_in -> f199_in :|: TRUE f199_out -> f197_out :|: TRUE f200_out -> f198_out :|: TRUE f201_out -> f198_out :|: TRUE f198_in -> f200_in :|: TRUE f198_in -> f201_in :|: TRUE f200_in -> f202_in :|: TRUE f202_out -> f203_in :|: TRUE f203_out -> f200_out :|: TRUE Start term: f1_in(T2) ---------------------------------------- (89) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (90) TRUE ---------------------------------------- (91) Obligation: Rules: f196_out(T93) -> f242_out(T93) :|: TRUE f242_in(x) -> f196_in(x) :|: TRUE f244_out -> f235_out(T17) :|: TRUE f235_in(x1) -> f244_in :|: TRUE f235_in(.(x2, x3)) -> f242_in(x3) :|: TRUE f242_out(x4) -> f235_out(.(x5, x4)) :|: TRUE f234_in(x6) -> f236_in(x6) :|: TRUE f236_out(x7) -> f234_out(x7) :|: TRUE f234_in(x8) -> f235_in(x8) :|: TRUE f235_out(x9) -> f234_out(x9) :|: TRUE f196_in(x10) -> f234_in(x10) :|: TRUE f234_out(x11) -> f196_out(x11) :|: TRUE f1_in(T2) -> f22_in(T2) :|: TRUE f22_out(x12) -> f1_out(x12) :|: TRUE f22_in(x13) -> f133_in(x13) :|: TRUE f133_out(x14) -> f22_out(x14) :|: TRUE f22_in(x15) -> f134_in(x15) :|: TRUE f134_out(x16) -> f22_out(x16) :|: TRUE f139_out(x17) -> f133_out(x17) :|: TRUE f133_in(x18) -> f140_in :|: TRUE f140_out -> f133_out(x19) :|: TRUE f133_in(x20) -> f139_in(x20) :|: TRUE f139_in(x21) -> f195_in :|: TRUE f196_out(x22) -> f139_out(x22) :|: TRUE f195_out -> f196_in(x23) :|: TRUE Start term: f1_in(T2) ---------------------------------------- (92) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (93) TRUE ---------------------------------------- (94) Obligation: Rules: f200_out -> f198_out :|: TRUE f201_out -> f198_out :|: TRUE f198_in -> f200_in :|: TRUE f198_in -> f201_in :|: TRUE f228_in -> f228_out :|: TRUE f200_in -> f202_in :|: TRUE f202_out -> f203_in :|: TRUE f203_out -> f200_out :|: TRUE f227_out -> f220_out :|: TRUE f226_out -> f220_out :|: TRUE f220_in -> f226_in :|: TRUE f220_in -> f227_in :|: TRUE f202_in -> f195_in :|: TRUE f195_out -> f202_out :|: TRUE f197_out -> f195_out :|: TRUE f195_in -> f197_in :|: TRUE f198_out -> f197_out :|: TRUE f197_in -> f198_in :|: TRUE f197_in -> f199_in :|: TRUE f199_out -> f197_out :|: TRUE f203_in -> f219_in :|: TRUE f219_out -> f203_out :|: TRUE f221_in -> f228_in :|: TRUE f228_out -> f221_out :|: TRUE f221_in -> f229_in :|: TRUE f229_out -> f221_out :|: TRUE f203_out -> f226_out :|: TRUE f226_in -> f203_in :|: TRUE f220_out -> f219_out :|: TRUE f221_out -> f219_out :|: TRUE f219_in -> f221_in :|: TRUE f219_in -> f220_in :|: TRUE f1_in(T2) -> f22_in(T2) :|: TRUE f22_out(x) -> f1_out(x) :|: TRUE f22_in(x1) -> f133_in(x1) :|: TRUE f133_out(x2) -> f22_out(x2) :|: TRUE f22_in(x3) -> f134_in(x3) :|: TRUE f134_out(x4) -> f22_out(x4) :|: TRUE f139_out(T17) -> f133_out(T17) :|: TRUE f133_in(x5) -> f140_in :|: TRUE f140_out -> f133_out(x6) :|: TRUE f133_in(x7) -> f139_in(x7) :|: TRUE f139_in(x8) -> f195_in :|: TRUE f196_out(x9) -> f139_out(x9) :|: TRUE f195_out -> f196_in(x10) :|: TRUE Start term: f1_in(T2) ---------------------------------------- (95) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f198_in -> f200_in :|: TRUE f200_in -> f202_in :|: TRUE f202_in -> f195_in :|: TRUE f195_in -> f197_in :|: TRUE f197_in -> f198_in :|: TRUE ---------------------------------------- (96) Obligation: Rules: f198_in -> f200_in :|: TRUE f200_in -> f202_in :|: TRUE f202_in -> f195_in :|: TRUE f195_in -> f197_in :|: TRUE f197_in -> f198_in :|: TRUE ---------------------------------------- (97) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (98) Obligation: Rules: f198_in -> f198_in :|: TRUE ---------------------------------------- (99) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (100) Obligation: Rules: f198_in -> f198_in :|: TRUE ---------------------------------------- (101) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f198_in -> f198_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (102) Obligation: Termination digraph: Nodes: (1) f198_in -> f198_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (103) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f198_in() Replaced non-predefined constructor symbols by 0. ---------------------------------------- (104) Obligation: Rules: f198_in -> f198_in :|: TRUE ---------------------------------------- (105) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc) -> f(1) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1) ---------------------------------------- (106) NO