/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern fl(a,g,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 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) MRRProof [EQUIVALENT, 0 ms] (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) QReductionProof [EQUIVALENT, 0 ms] (24) QDP (25) TransformationProof [EQUIVALENT, 0 ms] (26) QDP (27) UsableRulesProof [EQUIVALENT, 0 ms] (28) QDP (29) QReductionProof [EQUIVALENT, 0 ms] (30) QDP (31) TransformationProof [EQUIVALENT, 0 ms] (32) QDP (33) PrologToPiTRSProof [SOUND, 0 ms] (34) PiTRS (35) DependencyPairsProof [EQUIVALENT, 0 ms] (36) PiDP (37) DependencyGraphProof [EQUIVALENT, 0 ms] (38) AND (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) QDPQMonotonicMRRProof [EQUIVALENT, 14 ms] (52) QDP (53) UsableRulesProof [EQUIVALENT, 0 ms] (54) QDP (55) QReductionProof [EQUIVALENT, 0 ms] (56) QDP (57) TransformationProof [EQUIVALENT, 0 ms] (58) QDP (59) UsableRulesProof [EQUIVALENT, 0 ms] (60) QDP (61) QReductionProof [EQUIVALENT, 0 ms] (62) QDP (63) TransformationProof [EQUIVALENT, 0 ms] (64) QDP (65) PrologToTRSTransformerProof [SOUND, 0 ms] (66) QTRS (67) DependencyPairsProof [EQUIVALENT, 3 ms] (68) QDP (69) DependencyGraphProof [EQUIVALENT, 0 ms] (70) AND (71) QDP (72) UsableRulesProof [EQUIVALENT, 0 ms] (73) QDP (74) QDPSizeChangeProof [EQUIVALENT, 0 ms] (75) YES (76) QDP (77) NonTerminationLoopProof [COMPLETE, 0 ms] (78) NO (79) PrologToDTProblemTransformerProof [SOUND, 0 ms] (80) TRIPLES (81) TriplesToPiDPProof [SOUND, 0 ms] (82) PiDP (83) DependencyGraphProof [EQUIVALENT, 0 ms] (84) AND (85) PiDP (86) UsableRulesProof [EQUIVALENT, 0 ms] (87) PiDP (88) PiDPToQDPProof [SOUND, 0 ms] (89) QDP (90) QDPSizeChangeProof [EQUIVALENT, 0 ms] (91) YES (92) PiDP (93) PiDPToQDPProof [SOUND, 0 ms] (94) QDP (95) QDPQMonotonicMRRProof [EQUIVALENT, 13 ms] (96) QDP (97) UsableRulesProof [EQUIVALENT, 0 ms] (98) QDP (99) QReductionProof [EQUIVALENT, 0 ms] (100) QDP (101) PrologToIRSwTTransformerProof [SOUND, 0 ms] (102) AND (103) IRSwT (104) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (105) IRSwT (106) IntTRSCompressionProof [EQUIVALENT, 0 ms] (107) IRSwT (108) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (109) IRSwT (110) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (111) IRSwT (112) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 5 ms] (113) IRSwT (114) TempFilterProof [SOUND, 2 ms] (115) IRSwT (116) IRSwTToQDPProof [SOUND, 0 ms] (117) QDP (118) QDPSizeChangeProof [EQUIVALENT, 0 ms] (119) YES (120) IRSwT (121) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (122) IRSwT (123) IntTRSCompressionProof [EQUIVALENT, 10 ms] (124) IRSwT (125) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (126) IRSwT (127) IRSwTTerminationDigraphProof [EQUIVALENT, 4 ms] (128) IRSwT ---------------------------------------- (0) Obligation: Clauses: fl([], [], 0). fl(.(E, X), R, s(Z)) :- ','(append(E, Y, R), fl(X, Y, Z)). append([], X, X). append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs). Query: fl(a,g,a) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: fl_in_3: (f,b,f) append_in_3: (f,f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) s(x1) = s(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: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) s(x1) = s(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: FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) FL_IN_AGA(.(E, X), R, s(Z)) -> APPEND_IN_AAG(E, Y, R) APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z)) U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) s(x1) = s(x1) FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x5) APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG'(x3) U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x1, x5) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) FL_IN_AGA(.(E, X), R, s(Z)) -> APPEND_IN_AAG(E, Y, R) APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z)) U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) s(x1) = s(x1) FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x5) APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x1, x5) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) s(x1) = s(x1) APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(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: APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(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: APPEND_IN_AAG(.(X, Zs)) -> APPEND_IN_AAG(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: *APPEND_IN_AAG(.(X, Zs)) -> APPEND_IN_AAG(Zs) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x5) s(x1) = s(x1) FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x5) 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: U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) The TRS R consists of the following rules: append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) The argument filtering Pi contains the following mapping: [] = [] append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x5) s(x1) = s(x1) FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x5) 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: U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X) append_in_aag(.(X, Zs)) -> U3_aag(X, append_in_aag(Zs)) U3_aag(X, append_out_aag(Xs, Ys)) -> append_out_aag(.(X, Xs), Ys) The set Q consists of the following terms: append_in_aag(x0) U3_aag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: append_in_aag(.(X, Zs)) -> U3_aag(X, append_in_aag(Zs)) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(FL_IN_AGA(x_1)) = 2*x_1 POL(U1_AGA(x_1)) = x_1 POL(U3_aag(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL([]) = 0 POL(append_in_aag(x_1)) = 2*x_1 POL(append_out_aag(x_1, x_2)) = x_1 + 2*x_2 ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X) U3_aag(X, append_out_aag(Xs, Ys)) -> append_out_aag(.(X, Xs), Ys) The set Q consists of the following terms: append_in_aag(x0) U3_aag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) 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. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X) The set Q consists of the following terms: append_in_aag(x0) U3_aag(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (23) 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]. U3_aag(x0, x1) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X) The set Q consists of the following terms: append_in_aag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (25) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule FL_IN_AGA(R) -> U1_AGA(append_in_aag(R)) at position [0] we obtained the following new rules [LPAR04]: (FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)),FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R))) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X) The set Q consists of the following terms: append_in_aag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (27) 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. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)) R is empty. The set Q consists of the following terms: append_in_aag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (29) 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]. append_in_aag(x0) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (31) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U1_AGA(append_out_aag(E, Y)) -> FL_IN_AGA(Y) we obtained the following new rules [LPAR04]: (U1_AGA(append_out_aag([], z0)) -> FL_IN_AGA(z0),U1_AGA(append_out_aag([], z0)) -> FL_IN_AGA(z0)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: FL_IN_AGA(R) -> U1_AGA(append_out_aag([], R)) U1_AGA(append_out_aag([], z0)) -> FL_IN_AGA(z0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: fl_in_3: (f,b,f) append_in_3: (f,f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) s(x1) = s(x1) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (34) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) s(x1) = s(x1) ---------------------------------------- (35) 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: FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) FL_IN_AGA(.(E, X), R, s(Z)) -> APPEND_IN_AAG(E, Y, R) APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z)) U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) s(x1) = s(x1) FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x3, x5) APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x1, x4, x5) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x1, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (36) Obligation: Pi DP problem: The TRS P consists of the following rules: FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) FL_IN_AGA(.(E, X), R, s(Z)) -> APPEND_IN_AAG(E, Y, R) APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> U3_AAG(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_AGA(E, X, R, Z, fl_in_aga(X, Y, Z)) U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) s(x1) = s(x1) FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x3, x5) APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) U3_AAG(x1, x2, x3, x4, x5) = U3_AAG(x1, x4, x5) U2_AGA(x1, x2, x3, x4, x5) = U2_AGA(x1, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (37) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (38) Complex Obligation (AND) ---------------------------------------- (39) Obligation: Pi DP problem: The TRS P consists of the following rules: APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) s(x1) = s(x1) APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 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: APPEND_IN_AAG(.(X, Xs), Ys, .(X, Zs)) -> APPEND_IN_AAG(Xs, Ys, Zs) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPEND_IN_AAG(x1, x2, x3) = APPEND_IN_AAG(x3) 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: APPEND_IN_AAG(.(X, Zs)) -> APPEND_IN_AAG(Zs) 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: *APPEND_IN_AAG(.(X, Zs)) -> APPEND_IN_AAG(Zs) The graph contains the following edges 1 > 1 ---------------------------------------- (45) YES ---------------------------------------- (46) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) The TRS R consists of the following rules: fl_in_aga([], [], 0) -> fl_out_aga([], [], 0) fl_in_aga(.(E, X), R, s(Z)) -> U1_aga(E, X, R, Z, append_in_aag(E, Y, R)) append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) U1_aga(E, X, R, Z, append_out_aag(E, Y, R)) -> U2_aga(E, X, R, Z, fl_in_aga(X, Y, Z)) U2_aga(E, X, R, Z, fl_out_aga(X, Y, Z)) -> fl_out_aga(.(E, X), R, s(Z)) The argument filtering Pi contains the following mapping: fl_in_aga(x1, x2, x3) = fl_in_aga(x2) [] = [] fl_out_aga(x1, x2, x3) = fl_out_aga(x1, x2, x3) U1_aga(x1, x2, x3, x4, x5) = U1_aga(x3, x5) append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) U2_aga(x1, x2, x3, x4, x5) = U2_aga(x1, x3, x5) s(x1) = s(x1) FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x3, x5) 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: U1_AGA(E, X, R, Z, append_out_aag(E, Y, R)) -> FL_IN_AGA(X, Y, Z) FL_IN_AGA(.(E, X), R, s(Z)) -> U1_AGA(E, X, R, Z, append_in_aag(E, Y, R)) The TRS R consists of the following rules: append_in_aag([], X, X) -> append_out_aag([], X, X) append_in_aag(.(X, Xs), Ys, .(X, Zs)) -> U3_aag(X, Xs, Ys, Zs, append_in_aag(Xs, Ys, Zs)) U3_aag(X, Xs, Ys, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) The argument filtering Pi contains the following mapping: [] = [] append_in_aag(x1, x2, x3) = append_in_aag(x3) append_out_aag(x1, x2, x3) = append_out_aag(x1, x2, x3) .(x1, x2) = .(x1, x2) U3_aag(x1, x2, x3, x4, x5) = U3_aag(x1, x4, x5) s(x1) = s(x1) FL_IN_AGA(x1, x2, x3) = FL_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x3, x5) 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: U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X, X) append_in_aag(.(X, Zs)) -> U3_aag(X, Zs, append_in_aag(Zs)) U3_aag(X, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) The set Q consists of the following terms: append_in_aag(x0) U3_aag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (51) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented rules of the TRS R: append_in_aag(.(X, Zs)) -> U3_aag(X, Zs, append_in_aag(Zs)) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 1 + 2*x_2 POL(FL_IN_AGA(x_1)) = 2*x_1 POL(U1_AGA(x_1, x_2)) = x_2 POL(U3_aag(x_1, x_2, x_3)) = x_3 POL([]) = 2 POL(append_in_aag(x_1)) = 2*x_1 POL(append_out_aag(x_1, x_2, x_3)) = 2*x_2 ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X, X) U3_aag(X, Zs, append_out_aag(Xs, Ys, Zs)) -> append_out_aag(.(X, Xs), Ys, .(X, Zs)) The set Q consists of the following terms: append_in_aag(x0) U3_aag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (53) 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. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X, X) The set Q consists of the following terms: append_in_aag(x0) U3_aag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (55) 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]. U3_aag(x0, x1, x2) ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X, X) The set Q consists of the following terms: append_in_aag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (57) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule FL_IN_AGA(R) -> U1_AGA(R, append_in_aag(R)) at position [1] we obtained the following new rules [LPAR04]: (FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)),FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R))) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)) The TRS R consists of the following rules: append_in_aag(X) -> append_out_aag([], X, X) The set Q consists of the following terms: append_in_aag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (59) 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. ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)) R is empty. The set Q consists of the following terms: append_in_aag(x0) We have to consider all (P,Q,R)-chains. ---------------------------------------- (61) 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]. append_in_aag(x0) ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (63) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule U1_AGA(R, append_out_aag(E, Y, R)) -> FL_IN_AGA(Y) we obtained the following new rules [LPAR04]: (U1_AGA(z0, append_out_aag([], z0, z0)) -> FL_IN_AGA(z0),U1_AGA(z0, append_out_aag([], z0, z0)) -> FL_IN_AGA(z0)) ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)) U1_AGA(z0, append_out_aag([], z0, z0)) -> FL_IN_AGA(z0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (65) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 2, "program": { "directives": [], "clauses": [ [ "(fl ([]) ([]) (0))", null ], [ "(fl (. E X) R (s Z))", "(',' (append E Y R) (fl X Y Z))" ], [ "(append ([]) X X)", null ], [ "(append (. X Xs) Ys (. X Zs))", "(append Xs Ys Zs)" ] ] }, "graph": { "nodes": { "190": { "goal": [{ "clause": 2, "scope": 2, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "191": { "goal": [{ "clause": 3, "scope": 2, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "type": "Nodes", "195": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "185": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "196": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "186": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T22 T21 T23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [], "exprvars": [] } }, "197": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "189": { "goal": [ { "clause": 2, "scope": 2, "term": "(append T16 X14 T14)" }, { "clause": 3, "scope": 2, "term": "(append T16 X14 T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "114": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "224": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T40 X47 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T39"], "free": ["X47"], "exprvars": [] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(fl T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(fl T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "225": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "106": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T16 X14 T14) (fl T17 X14 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "91": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "93": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [{ "clause": 0, "scope": 1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "21": { "goal": [{ "clause": 1, "scope": 1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "98": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 20, "label": "PARALLEL" }, { "from": 5, "to": 21, "label": "PARALLEL" }, { "from": 20, "to": 91, "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" }, { "from": 20, "to": 93, "label": "EVAL-BACKTRACK" }, { "from": 21, "to": 106, "label": "EVAL with clause\nfl(.(X10, X11), X12, s(X13)) :- ','(append(X10, X14, X12), fl(X11, X14, X13)).\nand substitutionX10 -> T16,\nX11 -> T17,\nT1 -> .(T16, T17),\nT2 -> T14,\nX12 -> T14,\nX13 -> T18,\nT3 -> s(T18),\nT12 -> T16,\nT13 -> T17,\nT15 -> T18" }, { "from": 21, "to": 114, "label": "EVAL-BACKTRACK" }, { "from": 91, "to": 98, "label": "SUCCESS" }, { "from": 106, "to": 185, "label": "SPLIT 1" }, { "from": 106, "to": 186, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT21 is ground\nT14 is ground\nreplacements:X14 -> T21,\nT17 -> T22,\nT18 -> T23" }, { "from": 185, "to": 189, "label": "CASE" }, { "from": 186, "to": 2, "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T21\nT3 -> T23" }, { "from": 189, "to": 190, "label": "PARALLEL" }, { "from": 189, "to": 191, "label": "PARALLEL" }, { "from": 190, "to": 195, "label": "EVAL with clause\nappend([], X31, X31).\nand substitutionT16 -> [],\nX14 -> T30,\nX31 -> T30,\nT14 -> T30,\nX32 -> T30" }, { "from": 190, "to": 196, "label": "EVAL-BACKTRACK" }, { "from": 191, "to": 224, "label": "EVAL with clause\nappend(.(X43, X44), X45, .(X43, X46)) :- append(X44, X45, X46).\nand substitutionX43 -> T37,\nX44 -> T40,\nT16 -> .(T37, T40),\nX14 -> X47,\nX45 -> X47,\nX46 -> T39,\nT14 -> .(T37, T39),\nT38 -> T40" }, { "from": 191, "to": 225, "label": "EVAL-BACKTRACK" }, { "from": 195, "to": 197, "label": "SUCCESS" }, { "from": 224, "to": 185, "label": "INSTANCE with matching:\nT16 -> T40\nX14 -> X47\nT14 -> T39" } ], "type": "Graph" } } ---------------------------------------- (66) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f2_in([]) -> f2_out1([], 0) f2_in(T14) -> U1(f106_in(T14), T14) U1(f106_out1(T16, X14, T17, T18), T14) -> f2_out1(.(T16, T17), s(T18)) f185_in(T30) -> f185_out1([], T30) f185_in(.(T37, T39)) -> U2(f185_in(T39), .(T37, T39)) U2(f185_out1(T40, X47), .(T37, T39)) -> f185_out1(.(T37, T40), X47) f106_in(T14) -> U3(f185_in(T14), T14) U3(f185_out1(T16, T21), T14) -> U4(f2_in(T21), T14, T16, T21) U4(f2_out1(T22, T23), T14, T16, T21) -> f106_out1(T16, T21, T22, T23) Q is empty. ---------------------------------------- (67) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(T14) -> U1^1(f106_in(T14), T14) F2_IN(T14) -> F106_IN(T14) F185_IN(.(T37, T39)) -> U2^1(f185_in(T39), .(T37, T39)) F185_IN(.(T37, T39)) -> F185_IN(T39) F106_IN(T14) -> U3^1(f185_in(T14), T14) F106_IN(T14) -> F185_IN(T14) U3^1(f185_out1(T16, T21), T14) -> U4^1(f2_in(T21), T14, T16, T21) U3^1(f185_out1(T16, T21), T14) -> F2_IN(T21) The TRS R consists of the following rules: f2_in([]) -> f2_out1([], 0) f2_in(T14) -> U1(f106_in(T14), T14) U1(f106_out1(T16, X14, T17, T18), T14) -> f2_out1(.(T16, T17), s(T18)) f185_in(T30) -> f185_out1([], T30) f185_in(.(T37, T39)) -> U2(f185_in(T39), .(T37, T39)) U2(f185_out1(T40, X47), .(T37, T39)) -> f185_out1(.(T37, T40), X47) f106_in(T14) -> U3(f185_in(T14), T14) U3(f185_out1(T16, T21), T14) -> U4(f2_in(T21), T14, T16, T21) U4(f2_out1(T22, T23), T14, T16, T21) -> f106_out1(T16, T21, T22, T23) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (70) Complex Obligation (AND) ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: F185_IN(.(T37, T39)) -> F185_IN(T39) The TRS R consists of the following rules: f2_in([]) -> f2_out1([], 0) f2_in(T14) -> U1(f106_in(T14), T14) U1(f106_out1(T16, X14, T17, T18), T14) -> f2_out1(.(T16, T17), s(T18)) f185_in(T30) -> f185_out1([], T30) f185_in(.(T37, T39)) -> U2(f185_in(T39), .(T37, T39)) U2(f185_out1(T40, X47), .(T37, T39)) -> f185_out1(.(T37, T40), X47) f106_in(T14) -> U3(f185_in(T14), T14) U3(f185_out1(T16, T21), T14) -> U4(f2_in(T21), T14, T16, T21) U4(f2_out1(T22, T23), T14, T16, T21) -> f106_out1(T16, T21, T22, T23) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: F185_IN(.(T37, T39)) -> F185_IN(T39) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (74) 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: *F185_IN(.(T37, T39)) -> F185_IN(T39) The graph contains the following edges 1 > 1 ---------------------------------------- (75) YES ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: F2_IN(T14) -> F106_IN(T14) F106_IN(T14) -> U3^1(f185_in(T14), T14) U3^1(f185_out1(T16, T21), T14) -> F2_IN(T21) The TRS R consists of the following rules: f2_in([]) -> f2_out1([], 0) f2_in(T14) -> U1(f106_in(T14), T14) U1(f106_out1(T16, X14, T17, T18), T14) -> f2_out1(.(T16, T17), s(T18)) f185_in(T30) -> f185_out1([], T30) f185_in(.(T37, T39)) -> U2(f185_in(T39), .(T37, T39)) U2(f185_out1(T40, X47), .(T37, T39)) -> f185_out1(.(T37, T40), X47) f106_in(T14) -> U3(f185_in(T14), T14) U3(f185_out1(T16, T21), T14) -> U4(f2_in(T21), T14, T16, T21) U4(f2_out1(T22, T23), T14, T16, T21) -> f106_out1(T16, T21, T22, T23) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by narrowing to the left: s = F106_IN(T14) evaluates to t =F106_IN(T14) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F106_IN(T14) -> U3^1(f185_in(T14), T14) with rule F106_IN(T14') -> U3^1(f185_in(T14'), T14') at position [] and matcher [T14' / T14] U3^1(f185_in(T14), T14) -> U3^1(f185_out1([], T14), T14) with rule f185_in(T30) -> f185_out1([], T30) at position [0] and matcher [T30 / T14] U3^1(f185_out1([], T14), T14) -> F2_IN(T14) with rule U3^1(f185_out1(T16, T21), T14') -> F2_IN(T21) at position [] and matcher [T16 / [], T21 / T14, T14' / T14] F2_IN(T14) -> F106_IN(T14) with rule F2_IN(T14) -> F106_IN(T14) Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence All these steps are and every following step will be a correct step w.r.t to Q. ---------------------------------------- (78) NO ---------------------------------------- (79) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(fl ([]) ([]) (0))", null ], [ "(fl (. E X) R (s Z))", "(',' (append E Y R) (fl X Y Z))" ], [ "(append ([]) X X)", null ], [ "(append (. X Xs) Ys (. X Zs))", "(append Xs Ys Zs)" ] ] }, "graph": { "nodes": { "type": "Nodes", "234": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T44 X58 T43)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X58"], "exprvars": [] } }, "235": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T50 T49 T51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T49"], "free": [], "exprvars": [] } }, "214": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "236": { "goal": [ { "clause": 2, "scope": 4, "term": "(append T44 X58 T43)" }, { "clause": 3, "scope": 4, "term": "(append T44 X58 T43)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X58"], "exprvars": [] } }, "215": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" }], "kb": { "nonunifying": [[ "(fl T1 T23 T3)", "(fl ([]) ([]) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T23"], "free": ["X33"], "exprvars": [] } }, "237": { "goal": [{ "clause": 2, "scope": 4, "term": "(append T44 X58 T43)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X58"], "exprvars": [] } }, "216": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "238": { "goal": [{ "clause": 3, "scope": 4, "term": "(append T44 X58 T43)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X58"], "exprvars": [] } }, "217": { "goal": [ { "clause": 2, "scope": 3, "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" }, { "clause": 3, "scope": 3, "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" } ], "kb": { "nonunifying": [[ "(fl T1 T23 T3)", "(fl ([]) ([]) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T23"], "free": ["X33"], "exprvars": [] } }, "239": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "218": { "goal": [{ "clause": 2, "scope": 3, "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" }], "kb": { "nonunifying": [[ "(fl T1 T23 T3)", "(fl ([]) ([]) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T23"], "free": ["X33"], "exprvars": [] } }, "219": { "goal": [{ "clause": 3, "scope": 3, "term": "(',' (append T25 X33 T23) (fl T26 X33 T27))" }], "kb": { "nonunifying": [[ "(fl T1 T23 T3)", "(fl ([]) ([]) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T23"], "free": ["X33"], "exprvars": [] } }, "74": { "goal": [ { "clause": 0, "scope": 1, "term": "(fl T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(fl T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "182": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(fl T1 ([]) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "183": { "goal": [{ "clause": 1, "scope": 1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [[ "(fl T1 T2 T3)", "(fl ([]) ([]) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "184": { "goal": [{ "clause": 1, "scope": 1, "term": "(fl T1 ([]) T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "240": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "241": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T33 T32 T34)" }], "kb": { "nonunifying": [[ "(fl T1 T32 T3)", "(fl ([]) ([]) (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T32"], "free": [], "exprvars": [] } }, "242": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T68 X91 T67)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T67"], "free": ["X91"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "221": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "243": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "222": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T44 X58 T43) (fl T45 X58 T46))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X58"], "exprvars": [] } }, "201": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X9"], "exprvars": [] } }, "223": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "202": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "203": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" }, { "clause": 3, "scope": 2, "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X9"], "exprvars": [] } }, "204": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X9"], "exprvars": [] } }, "205": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X9"], "exprvars": [] } }, "206": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T13 ([]) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "207": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 74, "label": "CASE" }, { "from": 74, "to": 182, "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" }, { "from": 74, "to": 183, "label": "EVAL-BACKTRACK" }, { "from": 182, "to": 184, "label": "SUCCESS" }, { "from": 183, "to": 215, "label": "EVAL with clause\nfl(.(X29, X30), X31, s(X32)) :- ','(append(X29, X33, X31), fl(X30, X33, X32)).\nand substitutionX29 -> T25,\nX30 -> T26,\nT1 -> .(T25, T26),\nT2 -> T23,\nX31 -> T23,\nX32 -> T27,\nT3 -> s(T27),\nT21 -> T25,\nT22 -> T26,\nT24 -> T27" }, { "from": 183, "to": 216, "label": "EVAL-BACKTRACK" }, { "from": 184, "to": 201, "label": "EVAL with clause\nfl(.(X5, X6), X7, s(X8)) :- ','(append(X5, X9, X7), fl(X6, X9, X8)).\nand substitutionX5 -> T10,\nX6 -> T11,\nT1 -> .(T10, T11),\nX7 -> [],\nX8 -> T12,\nT3 -> s(T12),\nT7 -> T10,\nT8 -> T11,\nT9 -> T12" }, { "from": 184, "to": 202, "label": "EVAL-BACKTRACK" }, { "from": 201, "to": 203, "label": "CASE" }, { "from": 203, "to": 204, "label": "PARALLEL" }, { "from": 203, "to": 205, "label": "PARALLEL" }, { "from": 204, "to": 206, "label": "EVAL with clause\nappend([], X18, X18).\nand substitutionT10 -> [],\nX9 -> [],\nX18 -> [],\nX19 -> [],\nT11 -> T13,\nT12 -> T14" }, { "from": 204, "to": 207, "label": "EVAL-BACKTRACK" }, { "from": 205, "to": 214, "label": "BACKTRACK\nfor clause: append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs)because of non-unification" }, { "from": 206, "to": 1, "label": "INSTANCE with matching:\nT1 -> T13\nT2 -> []\nT3 -> T14" }, { "from": 215, "to": 217, "label": "CASE" }, { "from": 217, "to": 218, "label": "PARALLEL" }, { "from": 217, "to": 219, "label": "PARALLEL" }, { "from": 218, "to": 220, "label": "EVAL with clause\nappend([], X42, X42).\nand substitutionT25 -> [],\nX33 -> T32,\nX42 -> T32,\nT23 -> T32,\nX43 -> T32,\nT26 -> T33,\nT27 -> T34" }, { "from": 218, "to": 221, "label": "EVAL-BACKTRACK" }, { "from": 219, "to": 222, "label": "EVAL with clause\nappend(.(X54, X55), X56, .(X54, X57)) :- append(X55, X56, X57).\nand substitutionX54 -> T41,\nX55 -> T44,\nT25 -> .(T41, T44),\nX33 -> X58,\nX56 -> X58,\nX57 -> T43,\nT23 -> .(T41, T43),\nT42 -> T44,\nT26 -> T45,\nT27 -> T46" }, { "from": 219, "to": 223, "label": "EVAL-BACKTRACK" }, { "from": 220, "to": 1, "label": "INSTANCE with matching:\nT1 -> T33\nT2 -> T32\nT3 -> T34" }, { "from": 222, "to": 234, "label": "SPLIT 1" }, { "from": 222, "to": 235, "label": "SPLIT 2\nnew knowledge:\nT44 is ground\nT49 is ground\nT43 is ground\nreplacements:X58 -> T49,\nT45 -> T50,\nT46 -> T51" }, { "from": 234, "to": 236, "label": "CASE" }, { "from": 235, "to": 1, "label": "INSTANCE with matching:\nT1 -> T50\nT2 -> T49\nT3 -> T51" }, { "from": 236, "to": 237, "label": "PARALLEL" }, { "from": 236, "to": 238, "label": "PARALLEL" }, { "from": 237, "to": 239, "label": "EVAL with clause\nappend([], X75, X75).\nand substitutionT44 -> [],\nX58 -> T58,\nX75 -> T58,\nT43 -> T58,\nX76 -> T58" }, { "from": 237, "to": 240, "label": "EVAL-BACKTRACK" }, { "from": 238, "to": 242, "label": "EVAL with clause\nappend(.(X87, X88), X89, .(X87, X90)) :- append(X88, X89, X90).\nand substitutionX87 -> T65,\nX88 -> T68,\nT44 -> .(T65, T68),\nX58 -> X91,\nX89 -> X91,\nX90 -> T67,\nT43 -> .(T65, T67),\nT66 -> T68" }, { "from": 238, "to": 243, "label": "EVAL-BACKTRACK" }, { "from": 239, "to": 241, "label": "SUCCESS" }, { "from": 242, "to": 234, "label": "INSTANCE with matching:\nT44 -> T68\nX58 -> X91\nT43 -> T67" } ], "type": "Graph" } } ---------------------------------------- (80) Obligation: Triples: appendB(.(X1, X2), X3, .(X1, X4)) :- appendB(X2, X3, X4). flA(.([], X1), [], s(X2)) :- flA(X1, [], X2). flA(.([], X1), X2, s(X3)) :- flA(X1, X2, X3). flA(.(.(X1, X2), X3), .(X1, X4), s(X5)) :- appendB(X2, X6, X4). flA(.(.(X1, X2), X3), .(X1, X4), s(X5)) :- ','(appendcB(X2, X6, X4), flA(X3, X6, X5)). Clauses: flcA([], [], 0). flcA(.([], X1), [], s(X2)) :- flcA(X1, [], X2). flcA(.([], X1), X2, s(X3)) :- flcA(X1, X2, X3). flcA(.(.(X1, X2), X3), .(X1, X4), s(X5)) :- ','(appendcB(X2, X6, X4), flcA(X3, X6, X5)). appendcB([], X1, X1). appendcB(.(X1, X2), X3, .(X1, X4)) :- appendcB(X2, X3, X4). Afs: flA(x1, x2, x3) = flA(x2) ---------------------------------------- (81) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: flA_in_3: (f,b,f) appendB_in_3: (f,f,b) appendcB_in_3: (f,f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: FLA_IN_AGA(.([], X1), [], s(X2)) -> U2_AGA(X1, X2, flA_in_aga(X1, [], X2)) FLA_IN_AGA(.([], X1), [], s(X2)) -> FLA_IN_AGA(X1, [], X2) FLA_IN_AGA(.([], X1), X2, s(X3)) -> U3_AGA(X1, X2, X3, flA_in_aga(X1, X2, X3)) FLA_IN_AGA(.([], X1), X2, s(X3)) -> FLA_IN_AGA(X1, X2, X3) FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U4_AGA(X1, X2, X3, X4, X5, appendB_in_aag(X2, X6, X4)) FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> APPENDB_IN_AAG(X2, X6, X4) APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendB_in_aag(X2, X3, X4)) APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAG(X2, X3, X4) FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U5_AGA(X1, X2, X3, X4, X5, appendcB_in_aag(X2, X6, X4)) U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> U6_AGA(X1, X2, X3, X4, X5, flA_in_aga(X3, X6, X5)) U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X3, X6, X5) The TRS R consists of the following rules: appendcB_in_aag([], X1, X1) -> appendcB_out_aag([], X1, X1) appendcB_in_aag(.(X1, X2), X3, .(X1, X4)) -> U12_aag(X1, X2, X3, X4, appendcB_in_aag(X2, X3, X4)) U12_aag(X1, X2, X3, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: flA_in_aga(x1, x2, x3) = flA_in_aga(x2) [] = [] .(x1, x2) = .(x1, x2) appendB_in_aag(x1, x2, x3) = appendB_in_aag(x3) appendcB_in_aag(x1, x2, x3) = appendcB_in_aag(x3) appendcB_out_aag(x1, x2, x3) = appendcB_out_aag(x1, x2, x3) U12_aag(x1, x2, x3, x4, x5) = U12_aag(x1, x4, x5) FLA_IN_AGA(x1, x2, x3) = FLA_IN_AGA(x2) U2_AGA(x1, x2, x3) = U2_AGA(x3) U3_AGA(x1, x2, x3, x4) = U3_AGA(x2, x4) U4_AGA(x1, x2, x3, x4, x5, x6) = U4_AGA(x1, x4, x6) APPENDB_IN_AAG(x1, x2, x3) = APPENDB_IN_AAG(x3) U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x1, x4, x5) U5_AGA(x1, x2, x3, x4, x5, x6) = U5_AGA(x1, x4, x6) U6_AGA(x1, x2, x3, x4, x5, x6) = U6_AGA(x1, x4, x6) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (82) Obligation: Pi DP problem: The TRS P consists of the following rules: FLA_IN_AGA(.([], X1), [], s(X2)) -> U2_AGA(X1, X2, flA_in_aga(X1, [], X2)) FLA_IN_AGA(.([], X1), [], s(X2)) -> FLA_IN_AGA(X1, [], X2) FLA_IN_AGA(.([], X1), X2, s(X3)) -> U3_AGA(X1, X2, X3, flA_in_aga(X1, X2, X3)) FLA_IN_AGA(.([], X1), X2, s(X3)) -> FLA_IN_AGA(X1, X2, X3) FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U4_AGA(X1, X2, X3, X4, X5, appendB_in_aag(X2, X6, X4)) FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> APPENDB_IN_AAG(X2, X6, X4) APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> U1_AAG(X1, X2, X3, X4, appendB_in_aag(X2, X3, X4)) APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAG(X2, X3, X4) FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U5_AGA(X1, X2, X3, X4, X5, appendcB_in_aag(X2, X6, X4)) U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> U6_AGA(X1, X2, X3, X4, X5, flA_in_aga(X3, X6, X5)) U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X3, X6, X5) The TRS R consists of the following rules: appendcB_in_aag([], X1, X1) -> appendcB_out_aag([], X1, X1) appendcB_in_aag(.(X1, X2), X3, .(X1, X4)) -> U12_aag(X1, X2, X3, X4, appendcB_in_aag(X2, X3, X4)) U12_aag(X1, X2, X3, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: flA_in_aga(x1, x2, x3) = flA_in_aga(x2) [] = [] .(x1, x2) = .(x1, x2) appendB_in_aag(x1, x2, x3) = appendB_in_aag(x3) appendcB_in_aag(x1, x2, x3) = appendcB_in_aag(x3) appendcB_out_aag(x1, x2, x3) = appendcB_out_aag(x1, x2, x3) U12_aag(x1, x2, x3, x4, x5) = U12_aag(x1, x4, x5) FLA_IN_AGA(x1, x2, x3) = FLA_IN_AGA(x2) U2_AGA(x1, x2, x3) = U2_AGA(x3) U3_AGA(x1, x2, x3, x4) = U3_AGA(x2, x4) U4_AGA(x1, x2, x3, x4, x5, x6) = U4_AGA(x1, x4, x6) APPENDB_IN_AAG(x1, x2, x3) = APPENDB_IN_AAG(x3) U1_AAG(x1, x2, x3, x4, x5) = U1_AAG(x1, x4, x5) U5_AGA(x1, x2, x3, x4, x5, x6) = U5_AGA(x1, x4, x6) U6_AGA(x1, x2, x3, x4, x5, x6) = U6_AGA(x1, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (83) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (84) Complex Obligation (AND) ---------------------------------------- (85) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAG(X2, X3, X4) The TRS R consists of the following rules: appendcB_in_aag([], X1, X1) -> appendcB_out_aag([], X1, X1) appendcB_in_aag(.(X1, X2), X3, .(X1, X4)) -> U12_aag(X1, X2, X3, X4, appendcB_in_aag(X2, X3, X4)) U12_aag(X1, X2, X3, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) appendcB_in_aag(x1, x2, x3) = appendcB_in_aag(x3) appendcB_out_aag(x1, x2, x3) = appendcB_out_aag(x1, x2, x3) U12_aag(x1, x2, x3, x4, x5) = U12_aag(x1, x4, x5) APPENDB_IN_AAG(x1, x2, x3) = APPENDB_IN_AAG(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (86) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (87) Obligation: Pi DP problem: The TRS P consists of the following rules: APPENDB_IN_AAG(.(X1, X2), X3, .(X1, X4)) -> APPENDB_IN_AAG(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPENDB_IN_AAG(x1, x2, x3) = APPENDB_IN_AAG(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (88) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (89) Obligation: Q DP problem: The TRS P consists of the following rules: APPENDB_IN_AAG(.(X1, X4)) -> APPENDB_IN_AAG(X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (90) 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: *APPENDB_IN_AAG(.(X1, X4)) -> APPENDB_IN_AAG(X4) The graph contains the following edges 1 > 1 ---------------------------------------- (91) YES ---------------------------------------- (92) Obligation: Pi DP problem: The TRS P consists of the following rules: FLA_IN_AGA(.([], X1), X2, s(X3)) -> FLA_IN_AGA(X1, X2, X3) FLA_IN_AGA(.([], X1), [], s(X2)) -> FLA_IN_AGA(X1, [], X2) FLA_IN_AGA(.(.(X1, X2), X3), .(X1, X4), s(X5)) -> U5_AGA(X1, X2, X3, X4, X5, appendcB_in_aag(X2, X6, X4)) U5_AGA(X1, X2, X3, X4, X5, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X3, X6, X5) The TRS R consists of the following rules: appendcB_in_aag([], X1, X1) -> appendcB_out_aag([], X1, X1) appendcB_in_aag(.(X1, X2), X3, .(X1, X4)) -> U12_aag(X1, X2, X3, X4, appendcB_in_aag(X2, X3, X4)) U12_aag(X1, X2, X3, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) appendcB_in_aag(x1, x2, x3) = appendcB_in_aag(x3) appendcB_out_aag(x1, x2, x3) = appendcB_out_aag(x1, x2, x3) U12_aag(x1, x2, x3, x4, x5) = U12_aag(x1, x4, x5) FLA_IN_AGA(x1, x2, x3) = FLA_IN_AGA(x2) U5_AGA(x1, x2, x3, x4, x5, x6) = U5_AGA(x1, x4, x6) 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: FLA_IN_AGA(X2) -> FLA_IN_AGA(X2) FLA_IN_AGA([]) -> FLA_IN_AGA([]) FLA_IN_AGA(.(X1, X4)) -> U5_AGA(X1, X4, appendcB_in_aag(X4)) U5_AGA(X1, X4, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X6) The TRS R consists of the following rules: appendcB_in_aag(X1) -> appendcB_out_aag([], X1, X1) appendcB_in_aag(.(X1, X4)) -> U12_aag(X1, X4, appendcB_in_aag(X4)) U12_aag(X1, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) The set Q consists of the following terms: appendcB_in_aag(x0) U12_aag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (95) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: FLA_IN_AGA(.(X1, X4)) -> U5_AGA(X1, X4, appendcB_in_aag(X4)) U5_AGA(X1, X4, appendcB_out_aag(X2, X6, X4)) -> FLA_IN_AGA(X6) Strictly oriented rules of the TRS R: appendcB_in_aag(.(X1, X4)) -> U12_aag(X1, X4, appendcB_in_aag(X4)) U12_aag(X1, X4, appendcB_out_aag(X2, X3, X4)) -> appendcB_out_aag(.(X1, X2), X3, .(X1, X4)) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2 + 2*x_2 POL(FLA_IN_AGA(x_1)) = 2 + 2*x_1 POL(U12_aag(x_1, x_2, x_3)) = 2*x_3 POL(U5_AGA(x_1, x_2, x_3)) = 2*x_3 POL([]) = 2 POL(appendcB_in_aag(x_1)) = 2 + 2*x_1 POL(appendcB_out_aag(x_1, x_2, x_3)) = 2 + 2*x_2 ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: FLA_IN_AGA(X2) -> FLA_IN_AGA(X2) FLA_IN_AGA([]) -> FLA_IN_AGA([]) The TRS R consists of the following rules: appendcB_in_aag(X1) -> appendcB_out_aag([], X1, X1) The set Q consists of the following terms: appendcB_in_aag(x0) U12_aag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (97) 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. ---------------------------------------- (98) Obligation: Q DP problem: The TRS P consists of the following rules: FLA_IN_AGA(X2) -> FLA_IN_AGA(X2) FLA_IN_AGA([]) -> FLA_IN_AGA([]) R is empty. The set Q consists of the following terms: appendcB_in_aag(x0) U12_aag(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (99) 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]. appendcB_in_aag(x0) U12_aag(x0, x1, x2) ---------------------------------------- (100) Obligation: Q DP problem: The TRS P consists of the following rules: FLA_IN_AGA(X2) -> FLA_IN_AGA(X2) FLA_IN_AGA([]) -> FLA_IN_AGA([]) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (101) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 22, "program": { "directives": [], "clauses": [ [ "(fl ([]) ([]) (0))", null ], [ "(fl (. E X) R (s Z))", "(',' (append E Y R) (fl X Y Z))" ], [ "(append ([]) X X)", null ], [ "(append (. X Xs) Ys (. X Zs))", "(append Xs Ys Zs)" ] ] }, "graph": { "nodes": { "22": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "37": { "goal": [{ "clause": 0, "scope": 1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "180": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T16 X14 T14) (fl T17 X14 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "181": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "192": { "goal": [ { "clause": 2, "scope": 2, "term": "(append T16 X14 T14)" }, { "clause": 3, "scope": 2, "term": "(append T16 X14 T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "193": { "goal": [{ "clause": 2, "scope": 2, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "type": "Nodes", "194": { "goal": [{ "clause": 3, "scope": 2, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "187": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "198": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "177": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "188": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T22 T21 T23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [], "exprvars": [] } }, "199": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "178": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "200": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "179": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "226": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T40 X47 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T39"], "free": ["X47"], "exprvars": [] } }, "227": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": 1, "scope": 1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "32": { "goal": [ { "clause": 0, "scope": 1, "term": "(fl T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(fl T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 22, "to": 32, "label": "CASE" }, { "from": 32, "to": 37, "label": "PARALLEL" }, { "from": 32, "to": 40, "label": "PARALLEL" }, { "from": 37, "to": 177, "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" }, { "from": 37, "to": 178, "label": "EVAL-BACKTRACK" }, { "from": 40, "to": 180, "label": "EVAL with clause\nfl(.(X10, X11), X12, s(X13)) :- ','(append(X10, X14, X12), fl(X11, X14, X13)).\nand substitutionX10 -> T16,\nX11 -> T17,\nT1 -> .(T16, T17),\nT2 -> T14,\nX12 -> T14,\nX13 -> T18,\nT3 -> s(T18),\nT12 -> T16,\nT13 -> T17,\nT15 -> T18" }, { "from": 40, "to": 181, "label": "EVAL-BACKTRACK" }, { "from": 177, "to": 179, "label": "SUCCESS" }, { "from": 180, "to": 187, "label": "SPLIT 1" }, { "from": 180, "to": 188, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT21 is ground\nT14 is ground\nreplacements:X14 -> T21,\nT17 -> T22,\nT18 -> T23" }, { "from": 187, "to": 192, "label": "CASE" }, { "from": 188, "to": 22, "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T21\nT3 -> T23" }, { "from": 192, "to": 193, "label": "PARALLEL" }, { "from": 192, "to": 194, "label": "PARALLEL" }, { "from": 193, "to": 198, "label": "EVAL with clause\nappend([], X31, X31).\nand substitutionT16 -> [],\nX14 -> T30,\nX31 -> T30,\nT14 -> T30,\nX32 -> T30" }, { "from": 193, "to": 199, "label": "EVAL-BACKTRACK" }, { "from": 194, "to": 226, "label": "EVAL with clause\nappend(.(X43, X44), X45, .(X43, X46)) :- append(X44, X45, X46).\nand substitutionX43 -> T37,\nX44 -> T40,\nT16 -> .(T37, T40),\nX14 -> X47,\nX45 -> X47,\nX46 -> T39,\nT14 -> .(T37, T39),\nT38 -> T40" }, { "from": 194, "to": 227, "label": "EVAL-BACKTRACK" }, { "from": 198, "to": 200, "label": "SUCCESS" }, { "from": 226, "to": 187, "label": "INSTANCE with matching:\nT16 -> T40\nX14 -> X47\nT14 -> T39" } ], "type": "Graph" } } ---------------------------------------- (102) Complex Obligation (AND) ---------------------------------------- (103) Obligation: Rules: f226_out(T39) -> f194_out(.(T37, T39)) :|: TRUE f227_out -> f194_out(T14) :|: TRUE f194_in(.(x, x1)) -> f226_in(x1) :|: TRUE f194_in(x2) -> f227_in :|: TRUE f187_out(x3) -> f226_out(x3) :|: TRUE f226_in(x4) -> f187_in(x4) :|: TRUE f192_in(x5) -> f194_in(x5) :|: TRUE f192_in(x6) -> f193_in(x6) :|: TRUE f193_out(x7) -> f192_out(x7) :|: TRUE f194_out(x8) -> f192_out(x8) :|: TRUE f187_in(x9) -> f192_in(x9) :|: TRUE f192_out(x10) -> f187_out(x10) :|: TRUE f22_in(T2) -> f32_in(T2) :|: TRUE f32_out(x11) -> f22_out(x11) :|: TRUE f40_out(x12) -> f32_out(x12) :|: TRUE f37_out(x13) -> f32_out(x13) :|: TRUE f32_in(x14) -> f40_in(x14) :|: TRUE f32_in(x15) -> f37_in(x15) :|: TRUE f180_out(x16) -> f40_out(x16) :|: TRUE f40_in(x17) -> f181_in :|: TRUE f40_in(x18) -> f180_in(x18) :|: TRUE f181_out -> f40_out(x19) :|: TRUE f180_in(x20) -> f187_in(x20) :|: TRUE f187_out(x21) -> f188_in(x22) :|: TRUE f188_out(x23) -> f180_out(x24) :|: TRUE Start term: f22_in(T2) ---------------------------------------- (104) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f194_in(.(x, x1)) -> f226_in(x1) :|: TRUE f226_in(x4) -> f187_in(x4) :|: TRUE f192_in(x5) -> f194_in(x5) :|: TRUE f187_in(x9) -> f192_in(x9) :|: TRUE ---------------------------------------- (105) Obligation: Rules: f194_in(.(x, x1)) -> f226_in(x1) :|: TRUE f226_in(x4) -> f187_in(x4) :|: TRUE f192_in(x5) -> f194_in(x5) :|: TRUE f187_in(x9) -> f192_in(x9) :|: TRUE ---------------------------------------- (106) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (107) Obligation: Rules: f192_in(.(x:0, x1:0)) -> f192_in(x1:0) :|: TRUE ---------------------------------------- (108) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (109) Obligation: Rules: f192_in(.(x:0, x1:0)) -> f192_in(x1:0) :|: TRUE ---------------------------------------- (110) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f192_in(.(x:0, x1:0)) -> f192_in(x1:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (111) Obligation: Termination digraph: Nodes: (1) f192_in(.(x:0, x1:0)) -> f192_in(x1:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (112) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: .(x1, x2) -> .(x2) ---------------------------------------- (113) Obligation: Rules: f192_in(.(x1:0)) -> f192_in(x1:0) :|: TRUE ---------------------------------------- (114) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f192_in(VARIABLE) .(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (115) Obligation: Rules: f192_in(.(x1:0)) -> f192_in(x1:0) ---------------------------------------- (116) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (117) Obligation: Q DP problem: The TRS P consists of the following rules: f192_in(.(x1:0)) -> f192_in(x1:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (118) 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: *f192_in(.(x1:0)) -> f192_in(x1:0) The graph contains the following edges 1 > 1 ---------------------------------------- (119) YES ---------------------------------------- (120) Obligation: Rules: f180_out(T14) -> f40_out(T14) :|: TRUE f40_in(T2) -> f181_in :|: TRUE f40_in(x) -> f180_in(x) :|: TRUE f181_out -> f40_out(x1) :|: TRUE f198_in -> f198_out :|: TRUE f40_out(x2) -> f32_out(x2) :|: TRUE f37_out(x3) -> f32_out(x3) :|: TRUE f32_in(x4) -> f40_in(x4) :|: TRUE f32_in(x5) -> f37_in(x5) :|: TRUE f180_in(x6) -> f187_in(x6) :|: TRUE f187_out(x7) -> f188_in(x8) :|: TRUE f188_out(x9) -> f180_out(x10) :|: TRUE f226_out(T39) -> f194_out(.(T37, T39)) :|: TRUE f227_out -> f194_out(x11) :|: TRUE f194_in(.(x12, x13)) -> f226_in(x13) :|: TRUE f194_in(x14) -> f227_in :|: TRUE f187_out(x15) -> f226_out(x15) :|: TRUE f226_in(x16) -> f187_in(x16) :|: TRUE f199_out -> f193_out(x17) :|: TRUE f193_in(x18) -> f199_in :|: TRUE f193_in(T30) -> f198_in :|: TRUE f198_out -> f193_out(x19) :|: TRUE f192_in(x20) -> f194_in(x20) :|: TRUE f192_in(x21) -> f193_in(x21) :|: TRUE f193_out(x22) -> f192_out(x22) :|: TRUE f194_out(x23) -> f192_out(x23) :|: TRUE f22_in(x24) -> f32_in(x24) :|: TRUE f32_out(x25) -> f22_out(x25) :|: TRUE f188_in(T21) -> f22_in(T21) :|: TRUE f22_out(x26) -> f188_out(x26) :|: TRUE f187_in(x27) -> f192_in(x27) :|: TRUE f192_out(x28) -> f187_out(x28) :|: TRUE Start term: f22_in(T2) ---------------------------------------- (121) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f40_in(x) -> f180_in(x) :|: TRUE f198_in -> f198_out :|: TRUE f32_in(x4) -> f40_in(x4) :|: TRUE f180_in(x6) -> f187_in(x6) :|: TRUE f187_out(x7) -> f188_in(x8) :|: TRUE f226_out(T39) -> f194_out(.(T37, T39)) :|: TRUE f194_in(.(x12, x13)) -> f226_in(x13) :|: TRUE f187_out(x15) -> f226_out(x15) :|: TRUE f226_in(x16) -> f187_in(x16) :|: TRUE f193_in(T30) -> f198_in :|: TRUE f198_out -> f193_out(x19) :|: TRUE f192_in(x20) -> f194_in(x20) :|: TRUE f192_in(x21) -> f193_in(x21) :|: TRUE f193_out(x22) -> f192_out(x22) :|: TRUE f194_out(x23) -> f192_out(x23) :|: TRUE f22_in(x24) -> f32_in(x24) :|: TRUE f188_in(T21) -> f22_in(T21) :|: TRUE f187_in(x27) -> f192_in(x27) :|: TRUE f192_out(x28) -> f187_out(x28) :|: TRUE ---------------------------------------- (122) Obligation: Rules: f40_in(x) -> f180_in(x) :|: TRUE f198_in -> f198_out :|: TRUE f32_in(x4) -> f40_in(x4) :|: TRUE f180_in(x6) -> f187_in(x6) :|: TRUE f187_out(x7) -> f188_in(x8) :|: TRUE f226_out(T39) -> f194_out(.(T37, T39)) :|: TRUE f194_in(.(x12, x13)) -> f226_in(x13) :|: TRUE f187_out(x15) -> f226_out(x15) :|: TRUE f226_in(x16) -> f187_in(x16) :|: TRUE f193_in(T30) -> f198_in :|: TRUE f198_out -> f193_out(x19) :|: TRUE f192_in(x20) -> f194_in(x20) :|: TRUE f192_in(x21) -> f193_in(x21) :|: TRUE f193_out(x22) -> f192_out(x22) :|: TRUE f194_out(x23) -> f192_out(x23) :|: TRUE f22_in(x24) -> f32_in(x24) :|: TRUE f188_in(T21) -> f22_in(T21) :|: TRUE f187_in(x27) -> f192_in(x27) :|: TRUE f192_out(x28) -> f187_out(x28) :|: TRUE ---------------------------------------- (123) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (124) Obligation: Rules: f192_in(.(x12:0, x13:0)) -> f192_in(x13:0) :|: TRUE f192_in(x21:0) -> f187_out(x19:0) :|: TRUE f187_out(x15:0) -> f187_out(.(T37:0, x15:0)) :|: TRUE f187_out(x7:0) -> f192_in(x8:0) :|: TRUE ---------------------------------------- (125) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (126) Obligation: Rules: f192_in(.(x12:0, x13:0)) -> f192_in(x13:0) :|: TRUE f192_in(x21:0) -> f187_out(x19:0) :|: TRUE f187_out(x15:0) -> f187_out(.(T37:0, x15:0)) :|: TRUE f187_out(x7:0) -> f192_in(x8:0) :|: TRUE ---------------------------------------- (127) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f192_in(.(x12:0, x13:0)) -> f192_in(x13:0) :|: TRUE (2) f192_in(x21:0) -> f187_out(x19:0) :|: TRUE (3) f187_out(x15:0) -> f187_out(.(T37:0, x15:0)) :|: TRUE (4) f187_out(x7:0) -> f192_in(x8:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (3), (4) (3) -> (3), (4) (4) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (128) Obligation: Termination digraph: Nodes: (1) f192_in(.(x12:0, x13:0)) -> f192_in(x13:0) :|: TRUE (2) f187_out(x7:0) -> f192_in(x8:0) :|: TRUE (3) f187_out(x15:0) -> f187_out(.(T37:0, x15:0)) :|: TRUE (4) f192_in(x21:0) -> f187_out(x19:0) :|: TRUE Arcs: (1) -> (1), (4) (2) -> (1), (4) (3) -> (2), (3) (4) -> (2), (3) This digraph is fully evaluated!