/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern 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, 0 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) NonTerminationLoopProof [COMPLETE, 0 ms] (66) NO (67) PrologToTRSTransformerProof [SOUND, 0 ms] (68) QTRS (69) DependencyPairsProof [EQUIVALENT, 0 ms] (70) QDP (71) DependencyGraphProof [EQUIVALENT, 0 ms] (72) AND (73) QDP (74) UsableRulesProof [EQUIVALENT, 0 ms] (75) QDP (76) QDPSizeChangeProof [EQUIVALENT, 0 ms] (77) YES (78) QDP (79) NonTerminationLoopProof [COMPLETE, 0 ms] (80) NO (81) PrologToDTProblemTransformerProof [SOUND, 0 ms] (82) TRIPLES (83) TriplesToPiDPProof [SOUND, 0 ms] (84) PiDP (85) DependencyGraphProof [EQUIVALENT, 0 ms] (86) AND (87) PiDP (88) UsableRulesProof [EQUIVALENT, 0 ms] (89) PiDP (90) PiDPToQDPProof [SOUND, 0 ms] (91) QDP (92) QDPSizeChangeProof [EQUIVALENT, 0 ms] (93) YES (94) PiDP (95) PiDPToQDPProof [SOUND, 0 ms] (96) QDP (97) QDPQMonotonicMRRProof [EQUIVALENT, 0 ms] (98) QDP (99) UsableRulesProof [EQUIVALENT, 0 ms] (100) QDP (101) QReductionProof [EQUIVALENT, 0 ms] (102) QDP (103) NonTerminationLoopProof [COMPLETE, 0 ms] (104) NO (105) PrologToIRSwTTransformerProof [SOUND, 37 ms] (106) AND (107) IRSwT (108) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (109) IRSwT (110) IntTRSCompressionProof [EQUIVALENT, 23 ms] (111) IRSwT (112) IRSFormatTransformerProof [EQUIVALENT, 1 ms] (113) IRSwT (114) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (115) IRSwT (116) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 2 ms] (117) IRSwT (118) TempFilterProof [SOUND, 4 ms] (119) IRSwT (120) IRSwTToQDPProof [SOUND, 0 ms] (121) QDP (122) QDPSizeChangeProof [EQUIVALENT, 0 ms] (123) YES (124) IRSwT (125) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (126) IRSwT (127) IntTRSCompressionProof [EQUIVALENT, 9 ms] (128) IRSwT (129) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (130) IRSwT (131) IRSwTTerminationDigraphProof [EQUIVALENT, 12 ms] (132) 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) 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 = U1_AGA(z0, append_out_aag([], z0, z0)) evaluates to t =U1_AGA(z0, append_out_aag([], z0, z0)) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence U1_AGA(z0, append_out_aag([], z0, z0)) -> FL_IN_AGA(z0) with rule U1_AGA(z0', append_out_aag([], z0', z0')) -> FL_IN_AGA(z0') at position [] and matcher [z0' / z0] FL_IN_AGA(z0) -> U1_AGA(z0, append_out_aag([], z0, z0)) with rule FL_IN_AGA(R) -> U1_AGA(R, append_out_aag([], R, R)) 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. ---------------------------------------- (66) NO ---------------------------------------- (67) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 17, "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": { "25": { "goal": [{ "clause": 0, "scope": 1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "26": { "goal": [{ "clause": 1, "scope": 1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "190": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "191": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T22 T21 T23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [], "exprvars": [] } }, "type": "Nodes", "185": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "186": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "187": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "188": { "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": [] } }, "199": { "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": [] } }, "189": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "201": { "goal": [{ "clause": 2, "scope": 2, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "202": { "goal": [{ "clause": 3, "scope": 2, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "203": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "204": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "205": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "208": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T40 X47 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T39"], "free": ["X47"], "exprvars": [] } }, "209": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "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": 17, "to": 21, "label": "CASE" }, { "from": 21, "to": 25, "label": "PARALLEL" }, { "from": 21, "to": 26, "label": "PARALLEL" }, { "from": 25, "to": 185, "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" }, { "from": 25, "to": 186, "label": "EVAL-BACKTRACK" }, { "from": 26, "to": 188, "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": 26, "to": 189, "label": "EVAL-BACKTRACK" }, { "from": 185, "to": 187, "label": "SUCCESS" }, { "from": 188, "to": 190, "label": "SPLIT 1" }, { "from": 188, "to": 191, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT21 is ground\nT14 is ground\nreplacements:X14 -> T21,\nT17 -> T22,\nT18 -> T23" }, { "from": 190, "to": 199, "label": "CASE" }, { "from": 191, "to": 17, "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T21\nT3 -> T23" }, { "from": 199, "to": 201, "label": "PARALLEL" }, { "from": 199, "to": 202, "label": "PARALLEL" }, { "from": 201, "to": 203, "label": "EVAL with clause\nappend([], X31, X31).\nand substitutionT16 -> [],\nX14 -> T30,\nX31 -> T30,\nT14 -> T30,\nX32 -> T30" }, { "from": 201, "to": 204, "label": "EVAL-BACKTRACK" }, { "from": 202, "to": 208, "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": 202, "to": 209, "label": "EVAL-BACKTRACK" }, { "from": 203, "to": 205, "label": "SUCCESS" }, { "from": 208, "to": 190, "label": "INSTANCE with matching:\nT16 -> T40\nX14 -> X47\nT14 -> T39" } ], "type": "Graph" } } ---------------------------------------- (68) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f17_in([]) -> f17_out1([], 0) f17_in(T14) -> U1(f188_in(T14), T14) U1(f188_out1(T16, X14, T17, T18), T14) -> f17_out1(.(T16, T17), s(T18)) f190_in(T30) -> f190_out1([], T30) f190_in(.(T37, T39)) -> U2(f190_in(T39), .(T37, T39)) U2(f190_out1(T40, X47), .(T37, T39)) -> f190_out1(.(T37, T40), X47) f188_in(T14) -> U3(f190_in(T14), T14) U3(f190_out1(T16, T21), T14) -> U4(f17_in(T21), T14, T16, T21) U4(f17_out1(T22, T23), T14, T16, T21) -> f188_out1(T16, T21, T22, T23) Q is empty. ---------------------------------------- (69) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: F17_IN(T14) -> U1^1(f188_in(T14), T14) F17_IN(T14) -> F188_IN(T14) F190_IN(.(T37, T39)) -> U2^1(f190_in(T39), .(T37, T39)) F190_IN(.(T37, T39)) -> F190_IN(T39) F188_IN(T14) -> U3^1(f190_in(T14), T14) F188_IN(T14) -> F190_IN(T14) U3^1(f190_out1(T16, T21), T14) -> U4^1(f17_in(T21), T14, T16, T21) U3^1(f190_out1(T16, T21), T14) -> F17_IN(T21) The TRS R consists of the following rules: f17_in([]) -> f17_out1([], 0) f17_in(T14) -> U1(f188_in(T14), T14) U1(f188_out1(T16, X14, T17, T18), T14) -> f17_out1(.(T16, T17), s(T18)) f190_in(T30) -> f190_out1([], T30) f190_in(.(T37, T39)) -> U2(f190_in(T39), .(T37, T39)) U2(f190_out1(T40, X47), .(T37, T39)) -> f190_out1(.(T37, T40), X47) f188_in(T14) -> U3(f190_in(T14), T14) U3(f190_out1(T16, T21), T14) -> U4(f17_in(T21), T14, T16, T21) U4(f17_out1(T22, T23), T14, T16, T21) -> f188_out1(T16, T21, T22, T23) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (71) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (72) Complex Obligation (AND) ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: F190_IN(.(T37, T39)) -> F190_IN(T39) The TRS R consists of the following rules: f17_in([]) -> f17_out1([], 0) f17_in(T14) -> U1(f188_in(T14), T14) U1(f188_out1(T16, X14, T17, T18), T14) -> f17_out1(.(T16, T17), s(T18)) f190_in(T30) -> f190_out1([], T30) f190_in(.(T37, T39)) -> U2(f190_in(T39), .(T37, T39)) U2(f190_out1(T40, X47), .(T37, T39)) -> f190_out1(.(T37, T40), X47) f188_in(T14) -> U3(f190_in(T14), T14) U3(f190_out1(T16, T21), T14) -> U4(f17_in(T21), T14, T16, T21) U4(f17_out1(T22, T23), T14, T16, T21) -> f188_out1(T16, T21, T22, T23) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (74) 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. ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: F190_IN(.(T37, T39)) -> F190_IN(T39) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (76) 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: *F190_IN(.(T37, T39)) -> F190_IN(T39) The graph contains the following edges 1 > 1 ---------------------------------------- (77) YES ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: F17_IN(T14) -> F188_IN(T14) F188_IN(T14) -> U3^1(f190_in(T14), T14) U3^1(f190_out1(T16, T21), T14) -> F17_IN(T21) The TRS R consists of the following rules: f17_in([]) -> f17_out1([], 0) f17_in(T14) -> U1(f188_in(T14), T14) U1(f188_out1(T16, X14, T17, T18), T14) -> f17_out1(.(T16, T17), s(T18)) f190_in(T30) -> f190_out1([], T30) f190_in(.(T37, T39)) -> U2(f190_in(T39), .(T37, T39)) U2(f190_out1(T40, X47), .(T37, T39)) -> f190_out1(.(T37, T40), X47) f188_in(T14) -> U3(f190_in(T14), T14) U3(f190_out1(T16, T21), T14) -> U4(f17_in(T21), T14, T16, T21) U4(f17_out1(T22, T23), T14, T16, T21) -> f188_out1(T16, T21, T22, T23) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (79) 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 = F188_IN(T14) evaluates to t =F188_IN(T14) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence F188_IN(T14) -> U3^1(f190_in(T14), T14) with rule F188_IN(T14') -> U3^1(f190_in(T14'), T14') at position [] and matcher [T14' / T14] U3^1(f190_in(T14), T14) -> U3^1(f190_out1([], T14), T14) with rule f190_in(T30) -> f190_out1([], T30) at position [0] and matcher [T30 / T14] U3^1(f190_out1([], T14), T14) -> F17_IN(T14) with rule U3^1(f190_out1(T16, T21), T14') -> F17_IN(T21) at position [] and matcher [T16 / [], T21 / T14, T14' / T14] F17_IN(T14) -> F188_IN(T14) with rule F17_IN(T14) -> F188_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. ---------------------------------------- (80) NO ---------------------------------------- (81) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 19, "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": 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": [] } }, "170": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X9"], "exprvars": [] } }, "192": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "193": { "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": [] } }, "type": "Nodes", "194": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "195": { "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": [] } }, "196": { "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": [] } }, "197": { "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": [] } }, "230": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T68 X91 T67)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T67"], "free": ["X91"], "exprvars": [] } }, "176": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T13 ([]) T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "198": { "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": [] } }, "231": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "177": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "156": { "goal": [{ "clause": 1, "scope": 1, "term": "(fl T1 ([]) T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "137": { "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": [] } }, "139": { "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": [] } }, "219": { "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": [] } }, "19": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "161": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X9"], "exprvars": [] } }, "163": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "165": { "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": [] } }, "221": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "200": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "222": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T44 X58 T43)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X58"], "exprvars": [] } }, "223": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T50 T49 T51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T49"], "free": [], "exprvars": [] } }, "169": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (append T10 X9 ([])) (fl T11 X9 T12))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X9"], "exprvars": [] } }, "224": { "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": [] } }, "225": { "goal": [{ "clause": 2, "scope": 4, "term": "(append T44 X58 T43)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X58"], "exprvars": [] } }, "226": { "goal": [{ "clause": 3, "scope": 4, "term": "(append T44 X58 T43)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X58"], "exprvars": [] } }, "227": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "228": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "229": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 19, "to": 22, "label": "CASE" }, { "from": 22, "to": 137, "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" }, { "from": 22, "to": 139, "label": "EVAL-BACKTRACK" }, { "from": 137, "to": 156, "label": "SUCCESS" }, { "from": 139, "to": 193, "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": 139, "to": 194, "label": "EVAL-BACKTRACK" }, { "from": 156, "to": 161, "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": 156, "to": 163, "label": "EVAL-BACKTRACK" }, { "from": 161, "to": 165, "label": "CASE" }, { "from": 165, "to": 169, "label": "PARALLEL" }, { "from": 165, "to": 170, "label": "PARALLEL" }, { "from": 169, "to": 176, "label": "EVAL with clause\nappend([], X18, X18).\nand substitutionT10 -> [],\nX9 -> [],\nX18 -> [],\nX19 -> [],\nT11 -> T13,\nT12 -> T14" }, { "from": 169, "to": 177, "label": "EVAL-BACKTRACK" }, { "from": 170, "to": 192, "label": "BACKTRACK\nfor clause: append(.(X, Xs), Ys, .(X, Zs)) :- append(Xs, Ys, Zs)because of non-unification" }, { "from": 176, "to": 19, "label": "INSTANCE with matching:\nT1 -> T13\nT2 -> []\nT3 -> T14" }, { "from": 193, "to": 195, "label": "CASE" }, { "from": 195, "to": 196, "label": "PARALLEL" }, { "from": 195, "to": 197, "label": "PARALLEL" }, { "from": 196, "to": 198, "label": "EVAL with clause\nappend([], X42, X42).\nand substitutionT25 -> [],\nX33 -> T32,\nX42 -> T32,\nT23 -> T32,\nX43 -> T32,\nT26 -> T33,\nT27 -> T34" }, { "from": 196, "to": 200, "label": "EVAL-BACKTRACK" }, { "from": 197, "to": 219, "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": 197, "to": 221, "label": "EVAL-BACKTRACK" }, { "from": 198, "to": 19, "label": "INSTANCE with matching:\nT1 -> T33\nT2 -> T32\nT3 -> T34" }, { "from": 219, "to": 222, "label": "SPLIT 1" }, { "from": 219, "to": 223, "label": "SPLIT 2\nnew knowledge:\nT44 is ground\nT49 is ground\nT43 is ground\nreplacements:X58 -> T49,\nT45 -> T50,\nT46 -> T51" }, { "from": 222, "to": 224, "label": "CASE" }, { "from": 223, "to": 19, "label": "INSTANCE with matching:\nT1 -> T50\nT2 -> T49\nT3 -> T51" }, { "from": 224, "to": 225, "label": "PARALLEL" }, { "from": 224, "to": 226, "label": "PARALLEL" }, { "from": 225, "to": 227, "label": "EVAL with clause\nappend([], X75, X75).\nand substitutionT44 -> [],\nX58 -> T58,\nX75 -> T58,\nT43 -> T58,\nX76 -> T58" }, { "from": 225, "to": 228, "label": "EVAL-BACKTRACK" }, { "from": 226, "to": 230, "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": 226, "to": 231, "label": "EVAL-BACKTRACK" }, { "from": 227, "to": 229, "label": "SUCCESS" }, { "from": 230, "to": 222, "label": "INSTANCE with matching:\nT44 -> T68\nX58 -> X91\nT43 -> T67" } ], "type": "Graph" } } ---------------------------------------- (82) 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) ---------------------------------------- (83) 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 ---------------------------------------- (84) 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 ---------------------------------------- (85) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (86) Complex Obligation (AND) ---------------------------------------- (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) 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 ---------------------------------------- (88) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (89) 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 ---------------------------------------- (90) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (91) 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. ---------------------------------------- (92) 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 ---------------------------------------- (93) YES ---------------------------------------- (94) 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 ---------------------------------------- (95) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (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([]) 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. ---------------------------------------- (97) 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 ---------------------------------------- (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([]) 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. ---------------------------------------- (99) 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. ---------------------------------------- (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. 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. ---------------------------------------- (101) 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) ---------------------------------------- (102) 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. ---------------------------------------- (103) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = FLA_IN_AGA(X2) evaluates to t =FLA_IN_AGA(X2) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from FLA_IN_AGA(X2) to FLA_IN_AGA(X2). ---------------------------------------- (104) NO ---------------------------------------- (105) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 18, "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": { "23": { "goal": [{ "clause": 0, "scope": 1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "24": { "goal": [{ "clause": 1, "scope": 1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "type": "Nodes", "220": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "210": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "145": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "211": { "goal": [{ "clause": -1, "scope": -1, "term": "(fl T22 T21 T23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": [], "exprvars": [] } }, "212": { "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": [] } }, "136": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "213": { "goal": [{ "clause": 2, "scope": 2, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "214": { "goal": [{ "clause": 3, "scope": 2, "term": "(append T16 X14 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T14"], "free": ["X14"], "exprvars": [] } }, "138": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "215": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "216": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "206": { "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": [] } }, "217": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "207": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "218": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T40 X47 T39)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T39"], "free": ["X47"], "exprvars": [] } }, "20": { "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": 18, "to": 20, "label": "CASE" }, { "from": 20, "to": 23, "label": "PARALLEL" }, { "from": 20, "to": 24, "label": "PARALLEL" }, { "from": 23, "to": 136, "label": "EVAL with clause\nfl([], [], 0).\nand substitutionT1 -> [],\nT2 -> [],\nT3 -> 0" }, { "from": 23, "to": 138, "label": "EVAL-BACKTRACK" }, { "from": 24, "to": 206, "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": 24, "to": 207, "label": "EVAL-BACKTRACK" }, { "from": 136, "to": 145, "label": "SUCCESS" }, { "from": 206, "to": 210, "label": "SPLIT 1" }, { "from": 206, "to": 211, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT21 is ground\nT14 is ground\nreplacements:X14 -> T21,\nT17 -> T22,\nT18 -> T23" }, { "from": 210, "to": 212, "label": "CASE" }, { "from": 211, "to": 18, "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T21\nT3 -> T23" }, { "from": 212, "to": 213, "label": "PARALLEL" }, { "from": 212, "to": 214, "label": "PARALLEL" }, { "from": 213, "to": 215, "label": "EVAL with clause\nappend([], X31, X31).\nand substitutionT16 -> [],\nX14 -> T30,\nX31 -> T30,\nT14 -> T30,\nX32 -> T30" }, { "from": 213, "to": 216, "label": "EVAL-BACKTRACK" }, { "from": 214, "to": 218, "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": 214, "to": 220, "label": "EVAL-BACKTRACK" }, { "from": 215, "to": 217, "label": "SUCCESS" }, { "from": 218, "to": 210, "label": "INSTANCE with matching:\nT16 -> T40\nX14 -> X47\nT14 -> T39" } ], "type": "Graph" } } ---------------------------------------- (106) Complex Obligation (AND) ---------------------------------------- (107) Obligation: Rules: f214_in(T14) -> f220_in :|: TRUE f214_in(.(T37, T39)) -> f218_in(T39) :|: TRUE f218_out(x) -> f214_out(.(x1, x)) :|: TRUE f220_out -> f214_out(x2) :|: TRUE f218_in(x3) -> f210_in(x3) :|: TRUE f210_out(x4) -> f218_out(x4) :|: TRUE f212_out(x5) -> f210_out(x5) :|: TRUE f210_in(x6) -> f212_in(x6) :|: TRUE f214_out(x7) -> f212_out(x7) :|: TRUE f213_out(x8) -> f212_out(x8) :|: TRUE f212_in(x9) -> f214_in(x9) :|: TRUE f212_in(x10) -> f213_in(x10) :|: TRUE f20_out(T2) -> f18_out(T2) :|: TRUE f18_in(x11) -> f20_in(x11) :|: TRUE f24_out(x12) -> f20_out(x12) :|: TRUE f23_out(x13) -> f20_out(x13) :|: TRUE f20_in(x14) -> f23_in(x14) :|: TRUE f20_in(x15) -> f24_in(x15) :|: TRUE f24_in(x16) -> f207_in :|: TRUE f24_in(x17) -> f206_in(x17) :|: TRUE f207_out -> f24_out(x18) :|: TRUE f206_out(x19) -> f24_out(x19) :|: TRUE f210_out(x20) -> f211_in(x21) :|: TRUE f206_in(x22) -> f210_in(x22) :|: TRUE f211_out(x23) -> f206_out(x24) :|: TRUE Start term: f18_in(T2) ---------------------------------------- (108) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f214_in(.(T37, T39)) -> f218_in(T39) :|: TRUE f218_in(x3) -> f210_in(x3) :|: TRUE f210_in(x6) -> f212_in(x6) :|: TRUE f212_in(x9) -> f214_in(x9) :|: TRUE ---------------------------------------- (109) Obligation: Rules: f214_in(.(T37, T39)) -> f218_in(T39) :|: TRUE f218_in(x3) -> f210_in(x3) :|: TRUE f210_in(x6) -> f212_in(x6) :|: TRUE f212_in(x9) -> f214_in(x9) :|: TRUE ---------------------------------------- (110) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (111) Obligation: Rules: f214_in(.(T37:0, T39:0)) -> f214_in(T39:0) :|: TRUE ---------------------------------------- (112) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (113) Obligation: Rules: f214_in(.(T37:0, T39:0)) -> f214_in(T39:0) :|: TRUE ---------------------------------------- (114) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f214_in(.(T37:0, T39:0)) -> f214_in(T39:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (115) Obligation: Termination digraph: Nodes: (1) f214_in(.(T37:0, T39:0)) -> f214_in(T39:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (116) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: .(x1, x2) -> .(x2) ---------------------------------------- (117) Obligation: Rules: f214_in(.(T39:0)) -> f214_in(T39:0) :|: TRUE ---------------------------------------- (118) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f214_in(VARIABLE) .(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (119) Obligation: Rules: f214_in(.(T39:0)) -> f214_in(T39:0) ---------------------------------------- (120) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (121) Obligation: Q DP problem: The TRS P consists of the following rules: f214_in(.(T39:0)) -> f214_in(T39:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (122) 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: *f214_in(.(T39:0)) -> f214_in(T39:0) The graph contains the following edges 1 > 1 ---------------------------------------- (123) YES ---------------------------------------- (124) Obligation: Rules: f18_out(T21) -> f211_out(T21) :|: TRUE f211_in(x) -> f18_in(x) :|: TRUE f214_in(T14) -> f220_in :|: TRUE f214_in(.(T37, T39)) -> f218_in(T39) :|: TRUE f218_out(x1) -> f214_out(.(x2, x1)) :|: TRUE f220_out -> f214_out(x3) :|: TRUE f210_out(x4) -> f211_in(x5) :|: TRUE f206_in(x6) -> f210_in(x6) :|: TRUE f211_out(x7) -> f206_out(x8) :|: TRUE f20_out(T2) -> f18_out(T2) :|: TRUE f18_in(x9) -> f20_in(x9) :|: TRUE f24_in(x10) -> f207_in :|: TRUE f24_in(x11) -> f206_in(x11) :|: TRUE f207_out -> f24_out(x12) :|: TRUE f206_out(x13) -> f24_out(x13) :|: TRUE f215_in -> f215_out :|: TRUE f214_out(x14) -> f212_out(x14) :|: TRUE f213_out(x15) -> f212_out(x15) :|: TRUE f212_in(x16) -> f214_in(x16) :|: TRUE f212_in(x17) -> f213_in(x17) :|: TRUE f218_in(x18) -> f210_in(x18) :|: TRUE f210_out(x19) -> f218_out(x19) :|: TRUE f212_out(x20) -> f210_out(x20) :|: TRUE f210_in(x21) -> f212_in(x21) :|: TRUE f213_in(x22) -> f216_in :|: TRUE f216_out -> f213_out(x23) :|: TRUE f213_in(T30) -> f215_in :|: TRUE f215_out -> f213_out(x24) :|: TRUE f24_out(x25) -> f20_out(x25) :|: TRUE f23_out(x26) -> f20_out(x26) :|: TRUE f20_in(x27) -> f23_in(x27) :|: TRUE f20_in(x28) -> f24_in(x28) :|: TRUE Start term: f18_in(T2) ---------------------------------------- (125) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f211_in(x) -> f18_in(x) :|: TRUE f214_in(.(T37, T39)) -> f218_in(T39) :|: TRUE f218_out(x1) -> f214_out(.(x2, x1)) :|: TRUE f210_out(x4) -> f211_in(x5) :|: TRUE f206_in(x6) -> f210_in(x6) :|: TRUE f18_in(x9) -> f20_in(x9) :|: TRUE f24_in(x11) -> f206_in(x11) :|: TRUE f215_in -> f215_out :|: TRUE f214_out(x14) -> f212_out(x14) :|: TRUE f213_out(x15) -> f212_out(x15) :|: TRUE f212_in(x16) -> f214_in(x16) :|: TRUE f212_in(x17) -> f213_in(x17) :|: TRUE f218_in(x18) -> f210_in(x18) :|: TRUE f210_out(x19) -> f218_out(x19) :|: TRUE f212_out(x20) -> f210_out(x20) :|: TRUE f210_in(x21) -> f212_in(x21) :|: TRUE f213_in(T30) -> f215_in :|: TRUE f215_out -> f213_out(x24) :|: TRUE f20_in(x28) -> f24_in(x28) :|: TRUE ---------------------------------------- (126) Obligation: Rules: f211_in(x) -> f18_in(x) :|: TRUE f214_in(.(T37, T39)) -> f218_in(T39) :|: TRUE f218_out(x1) -> f214_out(.(x2, x1)) :|: TRUE f210_out(x4) -> f211_in(x5) :|: TRUE f206_in(x6) -> f210_in(x6) :|: TRUE f18_in(x9) -> f20_in(x9) :|: TRUE f24_in(x11) -> f206_in(x11) :|: TRUE f215_in -> f215_out :|: TRUE f214_out(x14) -> f212_out(x14) :|: TRUE f213_out(x15) -> f212_out(x15) :|: TRUE f212_in(x16) -> f214_in(x16) :|: TRUE f212_in(x17) -> f213_in(x17) :|: TRUE f218_in(x18) -> f210_in(x18) :|: TRUE f210_out(x19) -> f218_out(x19) :|: TRUE f212_out(x20) -> f210_out(x20) :|: TRUE f210_in(x21) -> f212_in(x21) :|: TRUE f213_in(T30) -> f215_in :|: TRUE f215_out -> f213_out(x24) :|: TRUE f20_in(x28) -> f24_in(x28) :|: TRUE ---------------------------------------- (127) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (128) Obligation: Rules: f210_out(x19:0) -> f210_out(.(x2:0, x19:0)) :|: TRUE f212_in(.(T37:0, T39:0)) -> f212_in(T39:0) :|: TRUE f212_in(x17:0) -> f210_out(x24:0) :|: TRUE f210_out(x4:0) -> f212_in(x5:0) :|: TRUE ---------------------------------------- (129) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (130) Obligation: Rules: f210_out(x19:0) -> f210_out(.(x2:0, x19:0)) :|: TRUE f212_in(.(T37:0, T39:0)) -> f212_in(T39:0) :|: TRUE f212_in(x17:0) -> f210_out(x24:0) :|: TRUE f210_out(x4:0) -> f212_in(x5:0) :|: TRUE ---------------------------------------- (131) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f210_out(x19:0) -> f210_out(.(x2:0, x19:0)) :|: TRUE (2) f212_in(.(T37:0, T39:0)) -> f212_in(T39:0) :|: TRUE (3) f212_in(x17:0) -> f210_out(x24:0) :|: TRUE (4) f210_out(x4:0) -> f212_in(x5:0) :|: TRUE Arcs: (1) -> (1), (4) (2) -> (2), (3) (3) -> (1), (4) (4) -> (2), (3) This digraph is fully evaluated! ---------------------------------------- (132) Obligation: Termination digraph: Nodes: (1) f210_out(x19:0) -> f210_out(.(x2:0, x19:0)) :|: TRUE (2) f212_in(x17:0) -> f210_out(x24:0) :|: TRUE (3) f212_in(.(T37:0, T39:0)) -> f212_in(T39:0) :|: TRUE (4) f210_out(x4:0) -> f212_in(x5:0) :|: TRUE Arcs: (1) -> (1), (4) (2) -> (1), (4) (3) -> (2), (3) (4) -> (2), (3) This digraph is fully evaluated!