/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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, 12 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) PrologToPiTRSProof [SOUND, 0 ms] (27) PiTRS (28) DependencyPairsProof [EQUIVALENT, 3 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, 0 ms] (52) QTRS (53) QTRSRRRProof [EQUIVALENT, 102 ms] (54) QTRS (55) QTRSRRRProof [EQUIVALENT, 12 ms] (56) QTRS (57) QTRSRRRProof [EQUIVALENT, 0 ms] (58) QTRS (59) QTRSRRRProof [EQUIVALENT, 1 ms] (60) QTRS (61) Overlay + Local Confluence [EQUIVALENT, 0 ms] (62) QTRS (63) DependencyPairsProof [EQUIVALENT, 0 ms] (64) QDP (65) DependencyGraphProof [EQUIVALENT, 0 ms] (66) AND (67) QDP (68) UsableRulesProof [EQUIVALENT, 0 ms] (69) QDP (70) QReductionProof [EQUIVALENT, 0 ms] (71) QDP (72) QDP (73) UsableRulesProof [EQUIVALENT, 0 ms] (74) QDP (75) QReductionProof [EQUIVALENT, 0 ms] (76) QDP (77) PrologToDTProblemTransformerProof [SOUND, 0 ms] (78) TRIPLES (79) TriplesToPiDPProof [SOUND, 0 ms] (80) PiDP (81) DependencyGraphProof [EQUIVALENT, 0 ms] (82) AND (83) PiDP (84) UsableRulesProof [EQUIVALENT, 0 ms] (85) PiDP (86) PiDPToQDPProof [SOUND, 0 ms] (87) QDP (88) QDPSizeChangeProof [EQUIVALENT, 0 ms] (89) YES (90) PiDP (91) UsableRulesProof [EQUIVALENT, 0 ms] (92) PiDP (93) PiDPToQDPProof [SOUND, 0 ms] (94) QDP (95) QDPSizeChangeProof [EQUIVALENT, 0 ms] (96) YES (97) PiDP (98) UsableRulesProof [EQUIVALENT, 0 ms] (99) PiDP (100) PiDPToQDPProof [SOUND, 0 ms] (101) QDP (102) PrologToIRSwTTransformerProof [SOUND, 29 ms] (103) AND (104) IRSwT (105) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (106) TRUE (107) IRSwT (108) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (109) TRUE (110) IRSwT (111) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (112) IRSwT (113) IntTRSCompressionProof [EQUIVALENT, 19 ms] (114) IRSwT (115) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (116) IRSwT (117) IRSwTTerminationDigraphProof [EQUIVALENT, 2 ms] (118) IRSwT (119) FilterProof [EQUIVALENT, 0 ms] (120) IntTRS (121) IntTRSPeriodicNontermProof [COMPLETE, 0 ms] (122) 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(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 ---------------------------------------- (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(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) ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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) ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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(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 ---------------------------------------- (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": 3, "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": { "193": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "196": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "197": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "230": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "198": { "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": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "199": { "goal": [{ "clause": 2, "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": [] } }, "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": [] } }, "237": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T94 (. T95 ([])) T93)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T93"], "free": [], "exprvars": [] } }, "216": { "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": [] } }, "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": [] } }, "15": { "goal": [{ "clause": 2, "scope": 1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "16": { "goal": [{ "clause": 3, "scope": 1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "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": [] } }, "242": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "221": { "goal": [{ "clause": 0, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "243": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "200": { "goal": [{ "clause": 3, "scope": 2, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "222": { "goal": [{ "clause": 1, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "244": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "124": { "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": [] } }, "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": [] } }, "203": { "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": [] } }, "204": { "goal": [], "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": [] } }, "205": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T36 X50)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X50"], "exprvars": [] } }, "227": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "206": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "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": 3, "to": 5, "label": "CASE" }, { "from": 5, "to": 15, "label": "PARALLEL" }, { "from": 5, "to": 16, "label": "PARALLEL" }, { "from": 15, "to": 124, "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": 15, "to": 193, "label": "EVAL-BACKTRACK" }, { "from": 16, "to": 242, "label": "EVAL with clause\nreverse([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 16, "to": 243, "label": "EVAL-BACKTRACK" }, { "from": 124, "to": 196, "label": "SPLIT 1" }, { "from": 124, "to": 197, "label": "SPLIT 2\nreplacements:X18 -> T22,\nT19 -> T23" }, { "from": 196, "to": 198, "label": "CASE" }, { "from": 197, "to": 234, "label": "CASE" }, { "from": 198, "to": 199, "label": "PARALLEL" }, { "from": 198, "to": 200, "label": "PARALLEL" }, { "from": 199, "to": 203, "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": 199, "to": 204, "label": "EVAL-BACKTRACK" }, { "from": 200, "to": 231, "label": "EVAL with clause\nreverse([], []).\nand substitutionT18 -> [],\nX18 -> []" }, { "from": 200, "to": 232, "label": "EVAL-BACKTRACK" }, { "from": 203, "to": 205, "label": "SPLIT 1" }, { "from": 203, "to": 206, "label": "SPLIT 2\nreplacements:X50 -> T40,\nT37 -> T41" }, { "from": 205, "to": 196, "label": "INSTANCE with matching:\nT18 -> T36\nX18 -> X50" }, { "from": 206, "to": 216, "label": "CASE" }, { "from": 216, "to": 221, "label": "PARALLEL" }, { "from": 216, "to": 222, "label": "PARALLEL" }, { "from": 221, "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": 221, "to": 227, "label": "EVAL-BACKTRACK" }, { "from": 222, "to": 228, "label": "EVAL with clause\napp([], X99, X99).\nand substitutionT40 -> [],\nT41 -> T69,\nX99 -> .(T69, []),\nX51 -> .(T69, [])" }, { "from": 222, "to": 229, "label": "EVAL-BACKTRACK" }, { "from": 226, "to": 206, "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": 237, "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": 238, "label": "EVAL-BACKTRACK" }, { "from": 236, "to": 239, "label": "EVAL with clause\napp([], X130, X130).\nand substitutionT22 -> [],\nT23 -> T102,\nX130 -> .(T102, []),\nT17 -> .(T102, [])" }, { "from": 236, "to": 240, "label": "EVAL-BACKTRACK" }, { "from": 237, "to": 197, "label": "INSTANCE with matching:\nT22 -> T94\nT23 -> T95\nT17 -> T93" }, { "from": 239, "to": 241, "label": "SUCCESS" }, { "from": 242, "to": 244, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (52) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f3_in(T17) -> U1(f124_in(T17), T17) U1(f124_out1(X18, T19), T17) -> f3_out1 f3_in([]) -> f3_out1 f196_in -> U2(f203_in) U2(f203_out1) -> f196_out1 f196_in -> f196_out1 f206_in -> U3(f206_in) U3(f206_out1) -> f206_out1 f206_in -> f206_out1 f197_in(.(T90, T93)) -> U4(f197_in(T93), .(T90, T93)) U4(f197_out1(T94, T95), .(T90, T93)) -> f197_out1(.(T90, T94), T95) f197_in(.(T102, [])) -> f197_out1([], T102) f124_in(T17) -> U5(f196_in, T17) U5(f196_out1, T17) -> U6(f197_in(T17), T17) U6(f197_out1(T22, T23), T17) -> f124_out1(T22, T23) f203_in -> U7(f196_in) U7(f196_out1) -> U8(f206_in) U8(f206_out1) -> f203_out1 Q is empty. ---------------------------------------- (53) QTRSRRRProof (EQUIVALENT) Used ordering: f3_in/1(YES) U1/2(YES,YES) f124_in/1(YES) f124_out1/2(YES,YES) f3_out1/0) []/0) f196_in/0) U2/1)YES( f203_in/0) f203_out1/0) f196_out1/0) f206_in/0) U3/1)YES( f206_out1/0) f197_in/1(YES) ./2(YES,YES) U4/2(YES,YES) f197_out1/2(YES,YES) U5/2(YES,YES) U6/2(YES,YES) U7/1)YES( U8/1)YES( Quasi precedence: f3_in_1 > U1_2 > [f3_out1, []] > f197_out1_2 > f124_out1_2 f3_in_1 > U1_2 > [f3_out1, []] > f197_out1_2 > ._2 f3_in_1 > f124_in_1 > [f196_in, f203_in] > [f203_out1, f196_out1, f206_in, f206_out1] > [f197_in_1, U5_2] > [f3_out1, []] > f197_out1_2 > f124_out1_2 f3_in_1 > f124_in_1 > [f196_in, f203_in] > [f203_out1, f196_out1, f206_in, f206_out1] > [f197_in_1, U5_2] > [f3_out1, []] > f197_out1_2 > ._2 f3_in_1 > f124_in_1 > [f196_in, f203_in] > [f203_out1, f196_out1, f206_in, f206_out1] > [f197_in_1, U5_2] > U4_2 > f197_out1_2 > f124_out1_2 f3_in_1 > f124_in_1 > [f196_in, f203_in] > [f203_out1, f196_out1, f206_in, f206_out1] > [f197_in_1, U5_2] > U4_2 > f197_out1_2 > ._2 f3_in_1 > f124_in_1 > [f196_in, f203_in] > [f203_out1, f196_out1, f206_in, f206_out1] > [f197_in_1, U5_2] > U6_2 > f124_out1_2 Status: f3_in_1: multiset status U1_2: multiset status f124_in_1: [1] f124_out1_2: multiset status f3_out1: multiset status []: multiset status f196_in: multiset status f203_in: multiset status f203_out1: multiset status f196_out1: multiset status f206_in: multiset status f206_out1: multiset status f197_in_1: multiset status ._2: multiset status U4_2: multiset status f197_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: f3_in(T17) -> U1(f124_in(T17), T17) U1(f124_out1(X18, T19), T17) -> f3_out1 f3_in([]) -> f3_out1 f196_in -> f196_out1 f197_in(.(T90, T93)) -> U4(f197_in(T93), .(T90, T93)) U4(f197_out1(T94, T95), .(T90, T93)) -> f197_out1(.(T90, T94), T95) f197_in(.(T102, [])) -> f197_out1([], T102) f124_in(T17) -> U5(f196_in, T17) U5(f196_out1, T17) -> U6(f197_in(T17), T17) U6(f197_out1(T22, T23), T17) -> f124_out1(T22, T23) ---------------------------------------- (54) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f196_in -> U2(f203_in) U2(f203_out1) -> f196_out1 f206_in -> U3(f206_in) U3(f206_out1) -> f206_out1 f206_in -> f206_out1 f203_in -> U7(f196_in) U7(f196_out1) -> U8(f206_in) U8(f206_out1) -> f203_out1 Q is empty. ---------------------------------------- (55) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U2(x_1)) = 2*x_1 POL(U3(x_1)) = x_1 POL(U7(x_1)) = 2*x_1 POL(U8(x_1)) = 2 + x_1 POL(f196_in) = 0 POL(f196_out1) = 2 POL(f203_in) = 0 POL(f203_out1) = 1 POL(f206_in) = 1 POL(f206_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: f206_in -> f206_out1 U7(f196_out1) -> U8(f206_in) U8(f206_out1) -> f203_out1 ---------------------------------------- (56) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f196_in -> U2(f203_in) U2(f203_out1) -> f196_out1 f206_in -> U3(f206_in) U3(f206_out1) -> f206_out1 f203_in -> U7(f196_in) Q is empty. ---------------------------------------- (57) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U2(x_1)) = x_1 POL(U3(x_1)) = 2*x_1 POL(U7(x_1)) = 2*x_1 POL(f196_in) = 0 POL(f196_out1) = 0 POL(f203_in) = 0 POL(f203_out1) = 1 POL(f206_in) = 0 POL(f206_out1) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U2(f203_out1) -> f196_out1 ---------------------------------------- (58) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f196_in -> U2(f203_in) f206_in -> U3(f206_in) U3(f206_out1) -> f206_out1 f203_in -> U7(f196_in) Q is empty. ---------------------------------------- (59) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U2(x_1)) = 2*x_1 POL(U3(x_1)) = 2*x_1 POL(U7(x_1)) = 2*x_1 POL(f196_in) = 0 POL(f203_in) = 0 POL(f206_in) = 0 POL(f206_out1) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U3(f206_out1) -> f206_out1 ---------------------------------------- (60) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f196_in -> U2(f203_in) f206_in -> U3(f206_in) f203_in -> U7(f196_in) Q is empty. ---------------------------------------- (61) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (62) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f196_in -> U2(f203_in) f206_in -> U3(f206_in) f203_in -> U7(f196_in) The set Q consists of the following terms: f196_in f206_in f203_in ---------------------------------------- (63) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: F196_IN -> F203_IN F206_IN -> F206_IN F203_IN -> F196_IN The TRS R consists of the following rules: f196_in -> U2(f203_in) f206_in -> U3(f206_in) f203_in -> U7(f196_in) The set Q consists of the following terms: f196_in f206_in f203_in We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (66) Complex Obligation (AND) ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: F206_IN -> F206_IN The TRS R consists of the following rules: f196_in -> U2(f203_in) f206_in -> U3(f206_in) f203_in -> U7(f196_in) The set Q consists of the following terms: f196_in f206_in f203_in We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (68) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: F206_IN -> F206_IN R is empty. The set Q consists of the following terms: f196_in f206_in f203_in We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f196_in f206_in f203_in ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: F206_IN -> F206_IN R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: F203_IN -> F196_IN F196_IN -> F203_IN The TRS R consists of the following rules: f196_in -> U2(f203_in) f206_in -> U3(f206_in) f203_in -> U7(f196_in) The set Q consists of the following terms: f196_in f206_in f203_in We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: F203_IN -> F196_IN F196_IN -> F203_IN R is empty. The set Q consists of the following terms: f196_in f206_in f203_in We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f196_in f206_in f203_in ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: F203_IN -> F196_IN F196_IN -> F203_IN R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "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": { "192": { "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": [] } }, "type": "Nodes", "194": { "goal": [{ "clause": 0, "scope": 4, "term": "(app T45 (. T46 ([])) X63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X63"], "exprvars": [] } }, "195": { "goal": [{ "clause": 1, "scope": 4, "term": "(app T45 (. T46 ([])) X63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X63"], "exprvars": [] } }, "272": { "goal": [{ "clause": 3, "scope": 1, "term": "(reverse T1 T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "273": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "274": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "275": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "278": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "97": { "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": [] } }, "99": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "164": { "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": [] } }, "285": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "165": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "286": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "122": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T21 X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "123": { "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": [] } }, "201": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T67 (. T68 ([])) X103)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X103"], "exprvars": [] } }, "245": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T26 (. T27 ([])) X30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X30"], "exprvars": [] } }, "202": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "246": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T78 (. T79 ([])) T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "6": { "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": [] } }, "127": { "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": [] } }, "248": { "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": [] } }, "171": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T41 X62)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X62"], "exprvars": [] } }, "173": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T45 (. T46 ([])) X63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X63"], "exprvars": [] } }, "250": { "goal": [{ "clause": 0, "scope": 5, "term": "(app T78 (. T79 ([])) T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "251": { "goal": [{ "clause": 1, "scope": 5, "term": "(app T78 (. T79 ([])) T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "254": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T107 (. T108 ([])) T106)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T106"], "free": [], "exprvars": [] } }, "255": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "135": { "goal": [{ "clause": 2, "scope": 3, "term": "(reverse T21 X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "218": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "219": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "79": { "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": [] } }, "140": { "goal": [{ "clause": 3, "scope": 3, "term": "(reverse T21 X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X29"], "exprvars": [] } }, "262": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "263": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "220": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "264": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "265": { "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": [] } }, "266": { "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": [] } }, "223": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "224": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "268": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) (. T116 ([])) T8)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "225": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "269": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "80": { "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": [] } }, "82": { "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": [] } }, "86": { "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": [] } }, "87": { "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": [] } } }, "edges": [ { "from": 1, "to": 6, "label": "CASE" }, { "from": 6, "to": 79, "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": 6, "to": 80, "label": "EVAL-BACKTRACK" }, { "from": 79, "to": 82, "label": "CASE" }, { "from": 80, "to": 278, "label": "EVAL with clause\nreverse([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 80, "to": 285, "label": "EVAL-BACKTRACK" }, { "from": 82, "to": 86, "label": "PARALLEL" }, { "from": 82, "to": 87, "label": "PARALLEL" }, { "from": 86, "to": 97, "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": 86, "to": 99, "label": "EVAL-BACKTRACK" }, { "from": 87, "to": 265, "label": "PARALLEL" }, { "from": 87, "to": 266, "label": "PARALLEL" }, { "from": 97, "to": 122, "label": "SPLIT 1" }, { "from": 97, "to": 123, "label": "SPLIT 2\nreplacements:X29 -> T26,\nT22 -> T27,\nT23 -> T28" }, { "from": 122, "to": 127, "label": "CASE" }, { "from": 123, "to": 245, "label": "SPLIT 1" }, { "from": 123, "to": 246, "label": "SPLIT 2\nreplacements:X30 -> T78,\nT28 -> T79" }, { "from": 127, "to": 135, "label": "PARALLEL" }, { "from": 127, "to": 140, "label": "PARALLEL" }, { "from": 135, "to": 164, "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": 135, "to": 165, "label": "EVAL-BACKTRACK" }, { "from": 140, "to": 223, "label": "EVAL with clause\nreverse([], []).\nand substitutionT21 -> [],\nX29 -> []" }, { "from": 140, "to": 224, "label": "EVAL-BACKTRACK" }, { "from": 164, "to": 171, "label": "SPLIT 1" }, { "from": 164, "to": 173, "label": "SPLIT 2\nreplacements:X62 -> T45,\nT42 -> T46" }, { "from": 171, "to": 122, "label": "INSTANCE with matching:\nT21 -> T41\nX29 -> X62" }, { "from": 173, "to": 192, "label": "CASE" }, { "from": 192, "to": 194, "label": "PARALLEL" }, { "from": 192, "to": 195, "label": "PARALLEL" }, { "from": 194, "to": 201, "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": 194, "to": 202, "label": "EVAL-BACKTRACK" }, { "from": 195, "to": 218, "label": "EVAL with clause\napp([], X111, X111).\nand substitutionT45 -> [],\nT46 -> T74,\nX111 -> .(T74, []),\nX63 -> .(T74, [])" }, { "from": 195, "to": 219, "label": "EVAL-BACKTRACK" }, { "from": 201, "to": 173, "label": "INSTANCE with matching:\nT45 -> T67\nT46 -> T68\nX63 -> X103" }, { "from": 218, "to": 220, "label": "SUCCESS" }, { "from": 223, "to": 225, "label": "SUCCESS" }, { "from": 245, "to": 173, "label": "INSTANCE with matching:\nT45 -> T26\nT46 -> T27\nX63 -> X30" }, { "from": 246, "to": 248, "label": "CASE" }, { "from": 248, "to": 250, "label": "PARALLEL" }, { "from": 248, "to": 251, "label": "PARALLEL" }, { "from": 250, "to": 254, "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": 250, "to": 255, "label": "EVAL-BACKTRACK" }, { "from": 251, "to": 262, "label": "EVAL with clause\napp([], X152, X152).\nand substitutionT78 -> [],\nT79 -> T115,\nX152 -> .(T115, []),\nT8 -> .(T115, [])" }, { "from": 251, "to": 263, "label": "EVAL-BACKTRACK" }, { "from": 254, "to": 246, "label": "INSTANCE with matching:\nT78 -> T107\nT79 -> T108\nT8 -> T106" }, { "from": 262, "to": 264, "label": "SUCCESS" }, { "from": 265, "to": 268, "label": "EVAL with clause\nreverse([], []).\nand substitutionT9 -> [],\nX7 -> [],\nT10 -> T116" }, { "from": 265, "to": 269, "label": "EVAL-BACKTRACK" }, { "from": 266, "to": 272, "label": "FAILURE" }, { "from": 268, "to": 246, "label": "INSTANCE with matching:\nT78 -> []\nT79 -> T116" }, { "from": 272, "to": 273, "label": "EVAL with clause\nreverse([], []).\nand substitutionT1 -> [],\nT8 -> []" }, { "from": 272, "to": 274, "label": "EVAL-BACKTRACK" }, { "from": 273, "to": 275, "label": "SUCCESS" }, { "from": 278, "to": 286, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (78) 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) ---------------------------------------- (79) 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 ---------------------------------------- (80) 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 ---------------------------------------- (81) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 16 less nodes. ---------------------------------------- (82) Complex Obligation (AND) ---------------------------------------- (83) 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 ---------------------------------------- (84) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (85) 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 ---------------------------------------- (86) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (87) 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. ---------------------------------------- (88) 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 ---------------------------------------- (89) YES ---------------------------------------- (90) 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 ---------------------------------------- (91) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (92) 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 ---------------------------------------- (93) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (94) 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. ---------------------------------------- (95) 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 ---------------------------------------- (96) YES ---------------------------------------- (97) 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 ---------------------------------------- (98) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (99) 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 ---------------------------------------- (100) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (101) 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. ---------------------------------------- (102) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "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": { "190": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T36 X50)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X50"], "exprvars": [] } }, "191": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "270": { "goal": [{ "clause": 0, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [{ "clause": 1, "scope": 4, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "252": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T62 (. T63 ([])) X91)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X91"], "exprvars": [] } }, "253": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "276": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T94 (. T95 ([])) T93)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T93"], "free": [], "exprvars": [] } }, "277": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "256": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "257": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "279": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "258": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "259": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "217": { "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": [] } }, "14": { "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": [] } }, "17": { "goal": [{ "clause": 2, "scope": 1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "18": { "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": [] } }, "260": { "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": [] } }, "261": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "283": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "185": { "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": [] } }, "284": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "120": { "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": [] } }, "186": { "goal": [{ "clause": 2, "scope": 2, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "121": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "187": { "goal": [{ "clause": 3, "scope": 2, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "188": { "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": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "189": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "267": { "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": [] } }, "125": { "goal": [{ "clause": -1, "scope": -1, "term": "(reverse T18 X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "126": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T22 (. T23 ([])) T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "247": { "goal": [{ "clause": 0, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } }, "249": { "goal": [{ "clause": 1, "scope": 3, "term": "(app T40 (. T41 ([])) X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X51"], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 14, "label": "CASE" }, { "from": 14, "to": 17, "label": "PARALLEL" }, { "from": 14, "to": 18, "label": "PARALLEL" }, { "from": 17, "to": 120, "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": 17, "to": 121, "label": "EVAL-BACKTRACK" }, { "from": 18, "to": 282, "label": "EVAL with clause\nreverse([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 18, "to": 283, "label": "EVAL-BACKTRACK" }, { "from": 120, "to": 125, "label": "SPLIT 1" }, { "from": 120, "to": 126, "label": "SPLIT 2\nreplacements:X18 -> T22,\nT19 -> T23" }, { "from": 125, "to": 185, "label": "CASE" }, { "from": 126, "to": 267, "label": "CASE" }, { "from": 185, "to": 186, "label": "PARALLEL" }, { "from": 185, "to": 187, "label": "PARALLEL" }, { "from": 186, "to": 188, "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": 186, "to": 189, "label": "EVAL-BACKTRACK" }, { "from": 187, "to": 259, "label": "EVAL with clause\nreverse([], []).\nand substitutionT18 -> [],\nX18 -> []" }, { "from": 187, "to": 260, "label": "EVAL-BACKTRACK" }, { "from": 188, "to": 190, "label": "SPLIT 1" }, { "from": 188, "to": 191, "label": "SPLIT 2\nreplacements:X50 -> T40,\nT37 -> T41" }, { "from": 190, "to": 125, "label": "INSTANCE with matching:\nT18 -> T36\nX18 -> X50" }, { "from": 191, "to": 217, "label": "CASE" }, { "from": 217, "to": 247, "label": "PARALLEL" }, { "from": 217, "to": 249, "label": "PARALLEL" }, { "from": 247, "to": 252, "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": 247, "to": 253, "label": "EVAL-BACKTRACK" }, { "from": 249, "to": 256, "label": "EVAL with clause\napp([], X99, X99).\nand substitutionT40 -> [],\nT41 -> T69,\nX99 -> .(T69, []),\nX51 -> .(T69, [])" }, { "from": 249, "to": 257, "label": "EVAL-BACKTRACK" }, { "from": 252, "to": 191, "label": "INSTANCE with matching:\nT40 -> T62\nT41 -> T63\nX51 -> X91" }, { "from": 256, "to": 258, "label": "SUCCESS" }, { "from": 259, "to": 261, "label": "SUCCESS" }, { "from": 267, "to": 270, "label": "PARALLEL" }, { "from": 267, "to": 271, "label": "PARALLEL" }, { "from": 270, "to": 276, "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": 270, "to": 277, "label": "EVAL-BACKTRACK" }, { "from": 271, "to": 279, "label": "EVAL with clause\napp([], X130, X130).\nand substitutionT22 -> [],\nT23 -> T102,\nX130 -> .(T102, []),\nT17 -> .(T102, [])" }, { "from": 271, "to": 280, "label": "EVAL-BACKTRACK" }, { "from": 276, "to": 126, "label": "INSTANCE with matching:\nT22 -> T94\nT23 -> T95\nT17 -> T93" }, { "from": 279, "to": 281, "label": "SUCCESS" }, { "from": 282, "to": 284, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (103) Complex Obligation (AND) ---------------------------------------- (104) Obligation: Rules: f249_out -> f217_out :|: TRUE f217_in -> f247_in :|: TRUE f247_out -> f217_out :|: TRUE f217_in -> f249_in :|: TRUE f247_in -> f252_in :|: TRUE f253_out -> f247_out :|: TRUE f252_out -> f247_out :|: TRUE f247_in -> f253_in :|: TRUE f191_out -> f252_out :|: TRUE f252_in -> f191_in :|: TRUE f217_out -> f191_out :|: TRUE f191_in -> f217_in :|: TRUE f14_out(T2) -> f2_out(T2) :|: TRUE f2_in(x) -> f14_in(x) :|: TRUE f14_in(x1) -> f18_in(x1) :|: TRUE f14_in(x2) -> f17_in(x2) :|: TRUE f18_out(x3) -> f14_out(x3) :|: TRUE f17_out(x4) -> f14_out(x4) :|: TRUE f120_out(T17) -> f17_out(T17) :|: TRUE f17_in(x5) -> f121_in :|: TRUE f121_out -> f17_out(x6) :|: TRUE f17_in(x7) -> f120_in(x7) :|: TRUE f120_in(x8) -> f125_in :|: TRUE f126_out(x9) -> f120_out(x9) :|: TRUE f125_out -> f126_in(x10) :|: TRUE f185_out -> f125_out :|: TRUE f125_in -> f185_in :|: TRUE f187_out -> f185_out :|: TRUE f185_in -> f187_in :|: TRUE f185_in -> f186_in :|: TRUE f186_out -> f185_out :|: TRUE f189_out -> f186_out :|: TRUE f186_in -> f189_in :|: TRUE f188_out -> f186_out :|: TRUE f186_in -> f188_in :|: TRUE f191_out -> f188_out :|: TRUE f190_out -> f191_in :|: TRUE f188_in -> f190_in :|: TRUE Start term: f2_in(T2) ---------------------------------------- (105) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (106) TRUE ---------------------------------------- (107) Obligation: Rules: f277_out -> f270_out(T17) :|: TRUE f276_out(T93) -> f270_out(.(T90, T93)) :|: TRUE f270_in(.(x, x1)) -> f276_in(x1) :|: TRUE f270_in(x2) -> f277_in :|: TRUE f267_out(x3) -> f126_out(x3) :|: TRUE f126_in(x4) -> f267_in(x4) :|: TRUE f271_out(x5) -> f267_out(x5) :|: TRUE f270_out(x6) -> f267_out(x6) :|: TRUE f267_in(x7) -> f270_in(x7) :|: TRUE f267_in(x8) -> f271_in(x8) :|: TRUE f126_out(x9) -> f276_out(x9) :|: TRUE f276_in(x10) -> f126_in(x10) :|: TRUE f14_out(T2) -> f2_out(T2) :|: TRUE f2_in(x11) -> f14_in(x11) :|: TRUE f14_in(x12) -> f18_in(x12) :|: TRUE f14_in(x13) -> f17_in(x13) :|: TRUE f18_out(x14) -> f14_out(x14) :|: TRUE f17_out(x15) -> f14_out(x15) :|: TRUE f120_out(x16) -> f17_out(x16) :|: TRUE f17_in(x17) -> f121_in :|: TRUE f121_out -> f17_out(x18) :|: TRUE f17_in(x19) -> f120_in(x19) :|: TRUE f120_in(x20) -> f125_in :|: TRUE f126_out(x21) -> f120_out(x21) :|: TRUE f125_out -> f126_in(x22) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (108) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (109) TRUE ---------------------------------------- (110) Obligation: Rules: f256_in -> f256_out :|: TRUE f247_in -> f252_in :|: TRUE f253_out -> f247_out :|: TRUE f252_out -> f247_out :|: TRUE f247_in -> f253_in :|: TRUE f217_out -> f191_out :|: TRUE f191_in -> f217_in :|: TRUE f191_out -> f188_out :|: TRUE f190_out -> f191_in :|: TRUE f188_in -> f190_in :|: TRUE f249_in -> f257_in :|: TRUE f257_out -> f249_out :|: TRUE f249_in -> f256_in :|: TRUE f256_out -> f249_out :|: TRUE f125_out -> f190_out :|: TRUE f190_in -> f125_in :|: TRUE f249_out -> f217_out :|: TRUE f217_in -> f247_in :|: TRUE f247_out -> f217_out :|: TRUE f217_in -> f249_in :|: TRUE f191_out -> f252_out :|: TRUE f252_in -> f191_in :|: TRUE f189_out -> f186_out :|: TRUE f186_in -> f189_in :|: TRUE f188_out -> f186_out :|: TRUE f186_in -> f188_in :|: TRUE f185_out -> f125_out :|: TRUE f125_in -> f185_in :|: TRUE f187_out -> f185_out :|: TRUE f185_in -> f187_in :|: TRUE f185_in -> f186_in :|: TRUE f186_out -> f185_out :|: TRUE f14_out(T2) -> f2_out(T2) :|: TRUE f2_in(x) -> f14_in(x) :|: TRUE f14_in(x1) -> f18_in(x1) :|: TRUE f14_in(x2) -> f17_in(x2) :|: TRUE f18_out(x3) -> f14_out(x3) :|: TRUE f17_out(x4) -> f14_out(x4) :|: TRUE f120_out(T17) -> f17_out(T17) :|: TRUE f17_in(x5) -> f121_in :|: TRUE f121_out -> f17_out(x6) :|: TRUE f17_in(x7) -> f120_in(x7) :|: TRUE f120_in(x8) -> f125_in :|: TRUE f126_out(x9) -> f120_out(x9) :|: TRUE f125_out -> f126_in(x10) :|: TRUE Start term: f2_in(T2) ---------------------------------------- (111) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f188_in -> f190_in :|: TRUE f190_in -> f125_in :|: TRUE f186_in -> f188_in :|: TRUE f125_in -> f185_in :|: TRUE f185_in -> f186_in :|: TRUE ---------------------------------------- (112) Obligation: Rules: f188_in -> f190_in :|: TRUE f190_in -> f125_in :|: TRUE f186_in -> f188_in :|: TRUE f125_in -> f185_in :|: TRUE f185_in -> f186_in :|: TRUE ---------------------------------------- (113) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (114) Obligation: Rules: f186_in -> f186_in :|: TRUE ---------------------------------------- (115) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (116) Obligation: Rules: f186_in -> f186_in :|: TRUE ---------------------------------------- (117) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f186_in -> f186_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (118) Obligation: Termination digraph: Nodes: (1) f186_in -> f186_in :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (119) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f186_in() Replaced non-predefined constructor symbols by 0. ---------------------------------------- (120) Obligation: Rules: f186_in -> f186_in :|: TRUE ---------------------------------------- (121) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc) -> f(1) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1) ---------------------------------------- (122) NO