MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern flat(a,g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToTRSTransformerProof [SOUND, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) QDP (9) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (10) QDP (11) NonTerminationLoopProof [COMPLETE, 0 ms] (12) NO (13) PrologToPiTRSProof [SOUND, 0 ms] (14) PiTRS (15) DependencyPairsProof [EQUIVALENT, 0 ms] (16) PiDP (17) DependencyGraphProof [EQUIVALENT, 0 ms] (18) PiDP (19) UsableRulesProof [EQUIVALENT, 0 ms] (20) PiDP (21) PiDPToQDPProof [SOUND, 0 ms] (22) QDP (23) UsableRulesReductionPairsProof [EQUIVALENT, 1 ms] (24) QDP (25) NonTerminationLoopProof [COMPLETE, 0 ms] (26) NO (27) PrologToPiTRSProof [SOUND, 0 ms] (28) PiTRS (29) DependencyPairsProof [EQUIVALENT, 0 ms] (30) PiDP (31) DependencyGraphProof [EQUIVALENT, 0 ms] (32) PiDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) PiDP (35) PiDPToQDPProof [SOUND, 0 ms] (36) QDP (37) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (38) QDP (39) NonTerminationLoopProof [COMPLETE, 0 ms] (40) NO (41) PrologToIRSwTTransformerProof [SOUND, 0 ms] (42) IRSwT (43) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (44) IRSwT (45) IntTRSCompressionProof [EQUIVALENT, 32 ms] (46) IRSwT (47) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (48) IRSwT (49) IRSwTTerminationDigraphProof [EQUIVALENT, 8 ms] (50) IRSwT (51) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 11 ms] (52) IRSwT (53) PrologToDTProblemTransformerProof [SOUND, 32 ms] (54) TRIPLES (55) TriplesToPiDPProof [SOUND, 0 ms] (56) PiDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) PiDP (59) PiDPToQDPProof [SOUND, 1 ms] (60) QDP (61) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (62) QDP (63) NonTerminationLoopProof [COMPLETE, 0 ms] (64) NO ---------------------------------------- (0) Obligation: Clauses: flat([], []). flat(.([], T), R) :- flat(T, R). flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R). Query: flat(a,g) ---------------------------------------- (1) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 10, "program": { "directives": [], "clauses": [ [ "(flat ([]) ([]))", null ], [ "(flat (. ([]) T) R)", "(flat T R)" ], [ "(flat (. (. H T) TT) (. H R))", "(flat (. T TT) R)" ] ] }, "graph": { "nodes": { "11": { "goal": [ { "clause": 0, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "56": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": 0, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "19": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "type": "Nodes", "120": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T13 T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [], "exprvars": [] } }, "122": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "127": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T26 T27) T25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "129": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "60": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "72": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "73": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "53": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 10, "to": 11, "label": "CASE" }, { "from": 11, "to": 18, "label": "PARALLEL" }, { "from": 11, "to": 19, "label": "PARALLEL" }, { "from": 18, "to": 53, "label": "EVAL with clause\nflat([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 18, "to": 56, "label": "EVAL-BACKTRACK" }, { "from": 19, "to": 72, "label": "PARALLEL" }, { "from": 19, "to": 73, "label": "PARALLEL" }, { "from": 53, "to": 60, "label": "SUCCESS" }, { "from": 72, "to": 120, "label": "EVAL with clause\nflat(.([], X9), X10) :- flat(X9, X10).\nand substitutionX9 -> T13,\nT1 -> .([], T13),\nT2 -> T12,\nX10 -> T12,\nT11 -> T13" }, { "from": 72, "to": 122, "label": "EVAL-BACKTRACK" }, { "from": 73, "to": 127, "label": "EVAL with clause\nflat(.(.(X19, X20), X21), .(X19, X22)) :- flat(.(X20, X21), X22).\nand substitutionX19 -> T22,\nX20 -> T26,\nX21 -> T27,\nT1 -> .(.(T22, T26), T27),\nX22 -> T25,\nT2 -> .(T22, T25),\nT23 -> T26,\nT24 -> T27" }, { "from": 73, "to": 129, "label": "EVAL-BACKTRACK" }, { "from": 120, "to": 10, "label": "INSTANCE with matching:\nT1 -> T13\nT2 -> T12" }, { "from": 127, "to": 10, "label": "INSTANCE with matching:\nT1 -> .(T26, T27)\nT2 -> T25" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f10_in([]) -> f10_out1([]) f10_in(T12) -> U1(f10_in(T12), T12) U1(f10_out1(T13), T12) -> f10_out1(.([], T13)) f10_in(.(T22, T25)) -> U2(f10_in(T25), .(T22, T25)) U2(f10_out1(.(T26, T27)), .(T22, T25)) -> f10_out1(.(.(T22, T26), T27)) Q is empty. ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: F10_IN(T12) -> U1^1(f10_in(T12), T12) F10_IN(T12) -> F10_IN(T12) F10_IN(.(T22, T25)) -> U2^1(f10_in(T25), .(T22, T25)) F10_IN(.(T22, T25)) -> F10_IN(T25) The TRS R consists of the following rules: f10_in([]) -> f10_out1([]) f10_in(T12) -> U1(f10_in(T12), T12) U1(f10_out1(T13), T12) -> f10_out1(.([], T13)) f10_in(.(T22, T25)) -> U2(f10_in(T25), .(T22, T25)) U2(f10_out1(.(T26, T27)), .(T22, T25)) -> f10_out1(.(.(T22, T26), T27)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: F10_IN(.(T22, T25)) -> F10_IN(T25) F10_IN(T12) -> F10_IN(T12) The TRS R consists of the following rules: f10_in([]) -> f10_out1([]) f10_in(T12) -> U1(f10_in(T12), T12) U1(f10_out1(T13), T12) -> f10_out1(.([], T13)) f10_in(.(T22, T25)) -> U2(f10_in(T25), .(T22, T25)) U2(f10_out1(.(T26, T27)), .(T22, T25)) -> f10_out1(.(.(T22, T26), T27)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) 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. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: F10_IN(.(T22, T25)) -> F10_IN(T25) F10_IN(T12) -> F10_IN(T12) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: F10_IN(.(T22, T25)) -> F10_IN(T25) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + x_2 POL(F10_IN(x_1)) = 2*x_1 ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: F10_IN(T12) -> F10_IN(T12) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) 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 = F10_IN(T12) evaluates to t =F10_IN(T12) 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 F10_IN(T12) to F10_IN(T12). ---------------------------------------- (12) NO ---------------------------------------- (13) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: flat_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1) U1_ag(x1, x2, x3) = U1_ag(x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (14) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1) U1_ag(x1, x2, x3) = U1_ag(x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x5) ---------------------------------------- (15) 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: FLAT_IN_AG(.([], T), R) -> U1_AG(T, R, flat_in_ag(T, R)) FLAT_IN_AG(.([], T), R) -> FLAT_IN_AG(T, R) FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> U2_AG(H, T, TT, R, flat_in_ag(.(T, TT), R)) FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> FLAT_IN_AG(.(T, TT), R) The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1) U1_ag(x1, x2, x3) = U1_ag(x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x5) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x3) U2_AG(x1, x2, x3, x4, x5) = U2_AG(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: FLAT_IN_AG(.([], T), R) -> U1_AG(T, R, flat_in_ag(T, R)) FLAT_IN_AG(.([], T), R) -> FLAT_IN_AG(T, R) FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> U2_AG(H, T, TT, R, flat_in_ag(.(T, TT), R)) FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> FLAT_IN_AG(.(T, TT), R) The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1) U1_ag(x1, x2, x3) = U1_ag(x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x5) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x3) U2_AG(x1, x2, x3, x4, x5) = U2_AG(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (18) Obligation: Pi DP problem: The TRS P consists of the following rules: FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> FLAT_IN_AG(.(T, TT), R) FLAT_IN_AG(.([], T), R) -> FLAT_IN_AG(T, R) The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1) U1_ag(x1, x2, x3) = U1_ag(x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x5) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (19) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (20) Obligation: Pi DP problem: The TRS P consists of the following rules: FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> FLAT_IN_AG(.(T, TT), R) FLAT_IN_AG(.([], T), R) -> FLAT_IN_AG(T, R) R is empty. The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (21) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(.(H, R)) -> FLAT_IN_AG(R) FLAT_IN_AG(R) -> FLAT_IN_AG(R) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (23) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: FLAT_IN_AG(.(H, R)) -> FLAT_IN_AG(R) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + x_2 POL(FLAT_IN_AG(x_1)) = 2*x_1 ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(R) -> FLAT_IN_AG(R) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (25) 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 = FLAT_IN_AG(R) evaluates to t =FLAT_IN_AG(R) 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 FLAT_IN_AG(R) to FLAT_IN_AG(R). ---------------------------------------- (26) NO ---------------------------------------- (27) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: flat_in_2: (f,b) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1, x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x4, x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (28) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1, x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x4, x5) ---------------------------------------- (29) 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: FLAT_IN_AG(.([], T), R) -> U1_AG(T, R, flat_in_ag(T, R)) FLAT_IN_AG(.([], T), R) -> FLAT_IN_AG(T, R) FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> U2_AG(H, T, TT, R, flat_in_ag(.(T, TT), R)) FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> FLAT_IN_AG(.(T, TT), R) The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1, x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x4, x5) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) U2_AG(x1, x2, x3, x4, x5) = U2_AG(x1, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: FLAT_IN_AG(.([], T), R) -> U1_AG(T, R, flat_in_ag(T, R)) FLAT_IN_AG(.([], T), R) -> FLAT_IN_AG(T, R) FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> U2_AG(H, T, TT, R, flat_in_ag(.(T, TT), R)) FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> FLAT_IN_AG(.(T, TT), R) The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1, x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x4, x5) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3) = U1_AG(x2, x3) U2_AG(x1, x2, x3, x4, x5) = U2_AG(x1, x4, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (32) Obligation: Pi DP problem: The TRS P consists of the following rules: FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> FLAT_IN_AG(.(T, TT), R) FLAT_IN_AG(.([], T), R) -> FLAT_IN_AG(T, R) The TRS R consists of the following rules: flat_in_ag([], []) -> flat_out_ag([], []) flat_in_ag(.([], T), R) -> U1_ag(T, R, flat_in_ag(T, R)) flat_in_ag(.(.(H, T), TT), .(H, R)) -> U2_ag(H, T, TT, R, flat_in_ag(.(T, TT), R)) U2_ag(H, T, TT, R, flat_out_ag(.(T, TT), R)) -> flat_out_ag(.(.(H, T), TT), .(H, R)) U1_ag(T, R, flat_out_ag(T, R)) -> flat_out_ag(.([], T), R) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) [] = [] flat_out_ag(x1, x2) = flat_out_ag(x1, x2) U1_ag(x1, x2, x3) = U1_ag(x2, x3) .(x1, x2) = .(x1, x2) U2_ag(x1, x2, x3, x4, x5) = U2_ag(x1, x4, x5) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (33) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (34) Obligation: Pi DP problem: The TRS P consists of the following rules: FLAT_IN_AG(.(.(H, T), TT), .(H, R)) -> FLAT_IN_AG(.(T, TT), R) FLAT_IN_AG(.([], T), R) -> FLAT_IN_AG(T, R) R is empty. The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (35) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(.(H, R)) -> FLAT_IN_AG(R) FLAT_IN_AG(R) -> FLAT_IN_AG(R) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (37) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: FLAT_IN_AG(.(H, R)) -> FLAT_IN_AG(R) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + x_2 POL(FLAT_IN_AG(x_1)) = 2*x_1 ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(R) -> FLAT_IN_AG(R) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (39) 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 = FLAT_IN_AG(R) evaluates to t =FLAT_IN_AG(R) 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 FLAT_IN_AG(R) to FLAT_IN_AG(R). ---------------------------------------- (40) NO ---------------------------------------- (41) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 17, "program": { "directives": [], "clauses": [ [ "(flat ([]) ([]))", null ], [ "(flat (. ([]) T) R)", "(flat T R)" ], [ "(flat (. (. H T) TT) (. H R))", "(flat (. T TT) R)" ] ] }, "graph": { "nodes": { "22": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "55": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "59": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "type": "Nodes", "130": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "121": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "128": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T26 T27) T25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "119": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T13 T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [], "exprvars": [] } }, "62": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "63": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "20": { "goal": [ { "clause": 0, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "21": { "goal": [{ "clause": 0, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "54": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 17, "to": 20, "label": "CASE" }, { "from": 20, "to": 21, "label": "PARALLEL" }, { "from": 20, "to": 22, "label": "PARALLEL" }, { "from": 21, "to": 54, "label": "EVAL with clause\nflat([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 21, "to": 55, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 62, "label": "PARALLEL" }, { "from": 22, "to": 63, "label": "PARALLEL" }, { "from": 54, "to": 59, "label": "SUCCESS" }, { "from": 62, "to": 119, "label": "EVAL with clause\nflat(.([], X9), X10) :- flat(X9, X10).\nand substitutionX9 -> T13,\nT1 -> .([], T13),\nT2 -> T12,\nX10 -> T12,\nT11 -> T13" }, { "from": 62, "to": 121, "label": "EVAL-BACKTRACK" }, { "from": 63, "to": 128, "label": "EVAL with clause\nflat(.(.(X19, X20), X21), .(X19, X22)) :- flat(.(X20, X21), X22).\nand substitutionX19 -> T22,\nX20 -> T26,\nX21 -> T27,\nT1 -> .(.(T22, T26), T27),\nX22 -> T25,\nT2 -> .(T22, T25),\nT23 -> T26,\nT24 -> T27" }, { "from": 63, "to": 130, "label": "EVAL-BACKTRACK" }, { "from": 119, "to": 17, "label": "INSTANCE with matching:\nT1 -> T13\nT2 -> T12" }, { "from": 128, "to": 17, "label": "INSTANCE with matching:\nT1 -> .(T26, T27)\nT2 -> T25" } ], "type": "Graph" } } ---------------------------------------- (42) Obligation: Rules: f119_out(T12) -> f62_out(T12) :|: TRUE f121_out -> f62_out(T2) :|: TRUE f62_in(x) -> f119_in(x) :|: TRUE f62_in(x1) -> f121_in :|: TRUE f119_in(x2) -> f17_in(x2) :|: TRUE f17_out(x3) -> f119_out(x3) :|: TRUE f128_in(T25) -> f17_in(T25) :|: TRUE f17_out(x4) -> f128_out(x4) :|: TRUE f63_in(.(x5, x6)) -> f128_in(x6) :|: TRUE f128_out(x7) -> f63_out(.(x8, x7)) :|: TRUE f63_in(x9) -> f130_in :|: TRUE f130_out -> f63_out(x10) :|: TRUE f20_in(x11) -> f21_in(x11) :|: TRUE f22_out(x12) -> f20_out(x12) :|: TRUE f20_in(x13) -> f22_in(x13) :|: TRUE f21_out(x14) -> f20_out(x14) :|: TRUE f62_out(x15) -> f22_out(x15) :|: TRUE f63_out(x16) -> f22_out(x16) :|: TRUE f22_in(x17) -> f63_in(x17) :|: TRUE f22_in(x18) -> f62_in(x18) :|: TRUE f20_out(x19) -> f17_out(x19) :|: TRUE f17_in(x20) -> f20_in(x20) :|: TRUE Start term: f17_in(T2) ---------------------------------------- (43) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f62_in(x) -> f119_in(x) :|: TRUE f119_in(x2) -> f17_in(x2) :|: TRUE f128_in(T25) -> f17_in(T25) :|: TRUE f63_in(.(x5, x6)) -> f128_in(x6) :|: TRUE f20_in(x13) -> f22_in(x13) :|: TRUE f22_in(x17) -> f63_in(x17) :|: TRUE f22_in(x18) -> f62_in(x18) :|: TRUE f17_in(x20) -> f20_in(x20) :|: TRUE ---------------------------------------- (44) Obligation: Rules: f62_in(x) -> f119_in(x) :|: TRUE f119_in(x2) -> f17_in(x2) :|: TRUE f128_in(T25) -> f17_in(T25) :|: TRUE f63_in(.(x5, x6)) -> f128_in(x6) :|: TRUE f20_in(x13) -> f22_in(x13) :|: TRUE f22_in(x17) -> f63_in(x17) :|: TRUE f22_in(x18) -> f62_in(x18) :|: TRUE f17_in(x20) -> f20_in(x20) :|: TRUE ---------------------------------------- (45) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (46) Obligation: Rules: f20_in(.(x5:0, x6:0)) -> f20_in(x6:0) :|: TRUE f20_in(x13:0) -> f20_in(x13:0) :|: TRUE ---------------------------------------- (47) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (48) Obligation: Rules: f20_in(.(x5:0, x6:0)) -> f20_in(x6:0) :|: TRUE f20_in(x13:0) -> f20_in(x13:0) :|: TRUE ---------------------------------------- (49) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f20_in(.(x5:0, x6:0)) -> f20_in(x6:0) :|: TRUE (2) f20_in(x13:0) -> f20_in(x13:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (50) Obligation: Termination digraph: Nodes: (1) f20_in(.(x5:0, x6:0)) -> f20_in(x6:0) :|: TRUE (2) f20_in(x13:0) -> f20_in(x13:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (51) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: .(x1, x2) -> .(x2) ---------------------------------------- (52) Obligation: Rules: f20_in(.(x6:0)) -> f20_in(x6:0) :|: TRUE f20_in(x13:0) -> f20_in(x13:0) :|: TRUE ---------------------------------------- (53) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 9, "program": { "directives": [], "clauses": [ [ "(flat ([]) ([]))", null ], [ "(flat (. ([]) T) R)", "(flat T R)" ], [ "(flat (. (. H T) TT) (. H R))", "(flat (. T TT) R)" ] ] }, "graph": { "nodes": { "type": "Nodes", "12": { "goal": [ { "clause": 0, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "57": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(flat T1 ([]))" }, { "clause": 2, "scope": 1, "term": "(flat T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "58": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [[ "(flat T1 T2)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "164": { "goal": [{ "clause": 1, "scope": 3, "term": "(flat T25 T24)" }], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "165": { "goal": [ { "clause": 2, "scope": 3, "term": "(flat T25 T24)" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flat T1 T24)" } ], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "166": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T36 T35)" }], "kb": { "nonunifying": [[ "(flat T1 T35)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": [], "exprvars": [] } }, "123": { "goal": [{ "clause": 1, "scope": 2, "term": "(flat T5 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "167": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "124": { "goal": [ { "clause": 2, "scope": 2, "term": "(flat T5 ([]))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(flat T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "168": { "goal": [{ "clause": 2, "scope": 3, "term": "(flat T25 T24)" }], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "125": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T11 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "169": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flat T1 T24)" } ], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "126": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "61": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 ([]))" }, { "clause": 2, "scope": 1, "term": "(flat T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "64": { "goal": [ { "clause": -1, "scope": -1, "term": "(flat T5 ([]))" }, { "clause": 2, "scope": 1, "term": "(flat T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "65": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 ([]))" }], "kb": { "nonunifying": [[ "(flat T1 ([]))", "(flat (. ([]) X3) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X3", "X4" ], "exprvars": [] } }, "66": { "goal": [ { "clause": 0, "scope": 2, "term": "(flat T5 ([]))" }, { "clause": 1, "scope": 2, "term": "(flat T5 ([]))" }, { "clause": 2, "scope": 2, "term": "(flat T5 ([]))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(flat T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "67": { "goal": [{ "clause": 0, "scope": 2, "term": "(flat T5 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "68": { "goal": [ { "clause": 1, "scope": 2, "term": "(flat T5 ([]))" }, { "clause": 2, "scope": 2, "term": "(flat T5 ([]))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(flat T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "69": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "170": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T57 T58) T56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T56"], "free": [], "exprvars": [] } }, "171": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "172": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T24)" }], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "131": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(flat T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "132": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "133": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "177": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T71 T72) T70)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T70"], "free": [], "exprvars": [] } }, "134": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "178": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "135": { "goal": [ { "clause": -1, "scope": -1, "term": "(flat T25 T24)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T24)" } ], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "179": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T81 T82) T80)" }], "kb": { "nonunifying": [[ "(flat T1 (. T77 T80))", "(flat (. ([]) X29) X30)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T80" ], "free": [ "X29", "X30" ], "exprvars": [] } }, "136": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [ [ "(flat T1 T2)", "(flat ([]) ([]))" ], [ "(flat T1 T2)", "(flat (. ([]) X29) X30)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [ "X29", "X30" ], "exprvars": [] } }, "137": { "goal": [ { "clause": 0, "scope": 3, "term": "(flat T25 T24)" }, { "clause": 1, "scope": 3, "term": "(flat T25 T24)" }, { "clause": 2, "scope": 3, "term": "(flat T25 T24)" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flat T1 T24)" } ], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "138": { "goal": [{ "clause": 0, "scope": 3, "term": "(flat T25 T24)" }], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "139": { "goal": [ { "clause": 1, "scope": 3, "term": "(flat T25 T24)" }, { "clause": 2, "scope": 3, "term": "(flat T25 T24)" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 2, "scope": 1, "term": "(flat T1 T24)" } ], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "70": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "71": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "180": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "181": { "goal": [ { "clause": 0, "scope": 4, "term": "(flat (. T81 T82) T80)" }, { "clause": 1, "scope": 4, "term": "(flat (. T81 T82) T80)" }, { "clause": 2, "scope": 4, "term": "(flat (. T81 T82) T80)" } ], "kb": { "nonunifying": [[ "(flat T1 (. T77 T80))", "(flat (. ([]) X29) X30)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T80" ], "free": [ "X29", "X30" ], "exprvars": [] } }, "182": { "goal": [ { "clause": 1, "scope": 4, "term": "(flat (. T81 T82) T80)" }, { "clause": 2, "scope": 4, "term": "(flat (. T81 T82) T80)" } ], "kb": { "nonunifying": [[ "(flat T1 (. T77 T80))", "(flat (. ([]) X29) X30)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T80" ], "free": [ "X29", "X30" ], "exprvars": [] } }, "183": { "goal": [{ "clause": 1, "scope": 4, "term": "(flat (. T81 T82) T80)" }], "kb": { "nonunifying": [[ "(flat T1 (. T77 T80))", "(flat (. ([]) X29) X30)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T80" ], "free": [ "X29", "X30" ], "exprvars": [] } }, "140": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "184": { "goal": [{ "clause": 2, "scope": 4, "term": "(flat (. T81 T82) T80)" }], "kb": { "nonunifying": [[ "(flat T1 (. T77 T80))", "(flat (. ([]) X29) X30)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T80" ], "free": [ "X29", "X30" ], "exprvars": [] } }, "141": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "185": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T93 T92)" }], "kb": { "nonunifying": [[ "(flat T1 (. T77 T92))", "(flat (. ([]) X29) X30)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T92" ], "free": [ "X29", "X30" ], "exprvars": [] } }, "142": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "186": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "187": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T106 T107) T105)" }], "kb": { "nonunifying": [[ "(flat T1 (. T77 (. T102 T105)))", "(flat (. ([]) X29) X30)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T102", "T105" ], "free": [ "X29", "X30" ], "exprvars": [] } }, "188": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 9, "to": 12, "label": "CASE" }, { "from": 12, "to": 57, "label": "EVAL with clause\nflat([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 12, "to": 58, "label": "EVAL-BACKTRACK" }, { "from": 57, "to": 61, "label": "SUCCESS" }, { "from": 58, "to": 135, "label": "EVAL with clause\nflat(.([], X29), X30) :- flat(X29, X30).\nand substitutionX29 -> T25,\nT1 -> .([], T25),\nT2 -> T24,\nX30 -> T24,\nT23 -> T25" }, { "from": 58, "to": 136, "label": "EVAL-BACKTRACK" }, { "from": 61, "to": 64, "label": "EVAL with clause\nflat(.([], X3), X4) :- flat(X3, X4).\nand substitutionX3 -> T5,\nT1 -> .([], T5),\nX4 -> [],\nT4 -> T5" }, { "from": 61, "to": 65, "label": "EVAL-BACKTRACK" }, { "from": 64, "to": 66, "label": "CASE" }, { "from": 65, "to": 134, "label": "BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification" }, { "from": 66, "to": 67, "label": "PARALLEL" }, { "from": 66, "to": 68, "label": "PARALLEL" }, { "from": 67, "to": 69, "label": "EVAL with clause\nflat([], []).\nand substitutionT5 -> []" }, { "from": 67, "to": 70, "label": "EVAL-BACKTRACK" }, { "from": 68, "to": 123, "label": "PARALLEL" }, { "from": 68, "to": 124, "label": "PARALLEL" }, { "from": 69, "to": 71, "label": "SUCCESS" }, { "from": 123, "to": 125, "label": "EVAL with clause\nflat(.([], X13), X14) :- flat(X13, X14).\nand substitutionX13 -> T11,\nT5 -> .([], T11),\nX14 -> [],\nT10 -> T11" }, { "from": 123, "to": 126, "label": "EVAL-BACKTRACK" }, { "from": 124, "to": 131, "label": "BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification" }, { "from": 125, "to": 9, "label": "INSTANCE with matching:\nT1 -> T11\nT2 -> []" }, { "from": 131, "to": 132, "label": "FAILURE" }, { "from": 132, "to": 133, "label": "BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification" }, { "from": 135, "to": 137, "label": "CASE" }, { "from": 136, "to": 179, "label": "EVAL with clause\nflat(.(.(X77, X78), X79), .(X77, X80)) :- flat(.(X78, X79), X80).\nand substitutionX77 -> T77,\nX78 -> T81,\nX79 -> T82,\nT1 -> .(.(T77, T81), T82),\nX80 -> T80,\nT2 -> .(T77, T80),\nT78 -> T81,\nT79 -> T82" }, { "from": 136, "to": 180, "label": "EVAL-BACKTRACK" }, { "from": 137, "to": 138, "label": "PARALLEL" }, { "from": 137, "to": 139, "label": "PARALLEL" }, { "from": 138, "to": 140, "label": "EVAL with clause\nflat([], []).\nand substitutionT25 -> [],\nT24 -> []" }, { "from": 138, "to": 141, "label": "EVAL-BACKTRACK" }, { "from": 139, "to": 164, "label": "PARALLEL" }, { "from": 139, "to": 165, "label": "PARALLEL" }, { "from": 140, "to": 142, "label": "SUCCESS" }, { "from": 164, "to": 166, "label": "EVAL with clause\nflat(.([], X39), X40) :- flat(X39, X40).\nand substitutionX39 -> T36,\nT25 -> .([], T36),\nT24 -> T35,\nX40 -> T35,\nT34 -> T36" }, { "from": 164, "to": 167, "label": "EVAL-BACKTRACK" }, { "from": 165, "to": 168, "label": "PARALLEL" }, { "from": 165, "to": 169, "label": "PARALLEL" }, { "from": 166, "to": 9, "label": "INSTANCE with matching:\nT1 -> T36\nT2 -> T35" }, { "from": 168, "to": 170, "label": "EVAL with clause\nflat(.(.(X57, X58), X59), .(X57, X60)) :- flat(.(X58, X59), X60).\nand substitutionX57 -> T53,\nX58 -> T57,\nX59 -> T58,\nT25 -> .(.(T53, T57), T58),\nX60 -> T56,\nT24 -> .(T53, T56),\nT54 -> T57,\nT55 -> T58" }, { "from": 168, "to": 171, "label": "EVAL-BACKTRACK" }, { "from": 169, "to": 172, "label": "FAILURE" }, { "from": 170, "to": 9, "label": "INSTANCE with matching:\nT1 -> .(T57, T58)\nT2 -> T56" }, { "from": 172, "to": 177, "label": "EVAL with clause\nflat(.(.(X69, X70), X71), .(X69, X72)) :- flat(.(X70, X71), X72).\nand substitutionX69 -> T67,\nX70 -> T71,\nX71 -> T72,\nT1 -> .(.(T67, T71), T72),\nX72 -> T70,\nT24 -> .(T67, T70),\nT68 -> T71,\nT69 -> T72" }, { "from": 172, "to": 178, "label": "EVAL-BACKTRACK" }, { "from": 177, "to": 9, "label": "INSTANCE with matching:\nT1 -> .(T71, T72)\nT2 -> T70" }, { "from": 179, "to": 181, "label": "CASE" }, { "from": 181, "to": 182, "label": "BACKTRACK\nfor clause: flat([], [])because of non-unification" }, { "from": 182, "to": 183, "label": "PARALLEL" }, { "from": 182, "to": 184, "label": "PARALLEL" }, { "from": 183, "to": 185, "label": "EVAL with clause\nflat(.([], X89), X90) :- flat(X89, X90).\nand substitutionT81 -> [],\nT82 -> T93,\nX89 -> T93,\nT80 -> T92,\nX90 -> T92,\nT91 -> T93" }, { "from": 183, "to": 186, "label": "EVAL-BACKTRACK" }, { "from": 184, "to": 187, "label": "EVAL with clause\nflat(.(.(X99, X100), X101), .(X99, X102)) :- flat(.(X100, X101), X102).\nand substitutionX99 -> T102,\nX100 -> T106,\nT81 -> .(T102, T106),\nT82 -> T107,\nX101 -> T107,\nX102 -> T105,\nT80 -> .(T102, T105),\nT103 -> T106,\nT104 -> T107" }, { "from": 184, "to": 188, "label": "EVAL-BACKTRACK" }, { "from": 185, "to": 9, "label": "INSTANCE with matching:\nT1 -> T93\nT2 -> T92" }, { "from": 187, "to": 9, "label": "INSTANCE with matching:\nT1 -> .(T106, T107)\nT2 -> T105" } ], "type": "Graph" } } ---------------------------------------- (54) Obligation: Triples: flatA(.([], .([], X1)), []) :- flatA(X1, []). flatA(.([], .([], X1)), X2) :- flatA(X1, X2). flatA(.([], .(.(X1, X2), X3)), .(X1, X4)) :- flatA(.(X2, X3), X4). flatA(.(.(X1, X2), X3), .(X1, X4)) :- flatA(.(X2, X3), X4). flatA(.(.(X1, []), X2), .(X1, X3)) :- flatA(X2, X3). flatA(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) :- flatA(.(X3, X4), X5). Clauses: flatcA([], []). flatcA(.([], []), []). flatcA(.([], .([], X1)), []) :- flatcA(X1, []). flatcA(.([], []), []). flatcA(.([], .([], X1)), X2) :- flatcA(X1, X2). flatcA(.([], .(.(X1, X2), X3)), .(X1, X4)) :- flatcA(.(X2, X3), X4). flatcA(.(.(X1, X2), X3), .(X1, X4)) :- flatcA(.(X2, X3), X4). flatcA(.(.(X1, []), X2), .(X1, X3)) :- flatcA(X2, X3). flatcA(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) :- flatcA(.(X3, X4), X5). Afs: flatA(x1, x2) = flatA(x2) ---------------------------------------- (55) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: flatA_in_2: (f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_AG(.([], .([], X1)), []) -> U1_AG(X1, flatA_in_ag(X1, [])) FLATA_IN_AG(.([], .([], X1)), []) -> FLATA_IN_AG(X1, []) FLATA_IN_AG(.([], .([], X1)), X2) -> U2_AG(X1, X2, flatA_in_ag(X1, X2)) FLATA_IN_AG(.([], .([], X1)), X2) -> FLATA_IN_AG(X1, X2) FLATA_IN_AG(.([], .(.(X1, X2), X3)), .(X1, X4)) -> U3_AG(X1, X2, X3, X4, flatA_in_ag(.(X2, X3), X4)) FLATA_IN_AG(.([], .(.(X1, X2), X3)), .(X1, X4)) -> FLATA_IN_AG(.(X2, X3), X4) FLATA_IN_AG(.(.(X1, X2), X3), .(X1, X4)) -> U4_AG(X1, X2, X3, X4, flatA_in_ag(.(X2, X3), X4)) FLATA_IN_AG(.(.(X1, X2), X3), .(X1, X4)) -> FLATA_IN_AG(.(X2, X3), X4) FLATA_IN_AG(.(.(X1, []), X2), .(X1, X3)) -> U5_AG(X1, X2, X3, flatA_in_ag(X2, X3)) FLATA_IN_AG(.(.(X1, []), X2), .(X1, X3)) -> FLATA_IN_AG(X2, X3) FLATA_IN_AG(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> U6_AG(X1, X2, X3, X4, X5, flatA_in_ag(.(X3, X4), X5)) FLATA_IN_AG(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> FLATA_IN_AG(.(X3, X4), X5) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ag(x1, x2) = flatA_in_ag(x2) [] = [] .(x1, x2) = .(x1, x2) FLATA_IN_AG(x1, x2) = FLATA_IN_AG(x2) U1_AG(x1, x2) = U1_AG(x2) U2_AG(x1, x2, x3) = U2_AG(x2, x3) U3_AG(x1, x2, x3, x4, x5) = U3_AG(x1, x4, x5) U4_AG(x1, x2, x3, x4, x5) = U4_AG(x1, x4, x5) U5_AG(x1, x2, x3, x4) = U5_AG(x1, x3, x4) U6_AG(x1, x2, x3, x4, x5, x6) = U6_AG(x1, x2, x5, x6) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (56) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_AG(.([], .([], X1)), []) -> U1_AG(X1, flatA_in_ag(X1, [])) FLATA_IN_AG(.([], .([], X1)), []) -> FLATA_IN_AG(X1, []) FLATA_IN_AG(.([], .([], X1)), X2) -> U2_AG(X1, X2, flatA_in_ag(X1, X2)) FLATA_IN_AG(.([], .([], X1)), X2) -> FLATA_IN_AG(X1, X2) FLATA_IN_AG(.([], .(.(X1, X2), X3)), .(X1, X4)) -> U3_AG(X1, X2, X3, X4, flatA_in_ag(.(X2, X3), X4)) FLATA_IN_AG(.([], .(.(X1, X2), X3)), .(X1, X4)) -> FLATA_IN_AG(.(X2, X3), X4) FLATA_IN_AG(.(.(X1, X2), X3), .(X1, X4)) -> U4_AG(X1, X2, X3, X4, flatA_in_ag(.(X2, X3), X4)) FLATA_IN_AG(.(.(X1, X2), X3), .(X1, X4)) -> FLATA_IN_AG(.(X2, X3), X4) FLATA_IN_AG(.(.(X1, []), X2), .(X1, X3)) -> U5_AG(X1, X2, X3, flatA_in_ag(X2, X3)) FLATA_IN_AG(.(.(X1, []), X2), .(X1, X3)) -> FLATA_IN_AG(X2, X3) FLATA_IN_AG(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> U6_AG(X1, X2, X3, X4, X5, flatA_in_ag(.(X3, X4), X5)) FLATA_IN_AG(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> FLATA_IN_AG(.(X3, X4), X5) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ag(x1, x2) = flatA_in_ag(x2) [] = [] .(x1, x2) = .(x1, x2) FLATA_IN_AG(x1, x2) = FLATA_IN_AG(x2) U1_AG(x1, x2) = U1_AG(x2) U2_AG(x1, x2, x3) = U2_AG(x2, x3) U3_AG(x1, x2, x3, x4, x5) = U3_AG(x1, x4, x5) U4_AG(x1, x2, x3, x4, x5) = U4_AG(x1, x4, x5) U5_AG(x1, x2, x3, x4) = U5_AG(x1, x3, x4) U6_AG(x1, x2, x3, x4, x5, x6) = U6_AG(x1, x2, x5, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 6 less nodes. ---------------------------------------- (58) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_AG(.([], .([], X1)), X2) -> FLATA_IN_AG(X1, X2) FLATA_IN_AG(.([], .([], X1)), []) -> FLATA_IN_AG(X1, []) FLATA_IN_AG(.([], .(.(X1, X2), X3)), .(X1, X4)) -> FLATA_IN_AG(.(X2, X3), X4) FLATA_IN_AG(.(.(X1, X2), X3), .(X1, X4)) -> FLATA_IN_AG(.(X2, X3), X4) FLATA_IN_AG(.(.(X1, []), X2), .(X1, X3)) -> FLATA_IN_AG(X2, X3) FLATA_IN_AG(.(.(X1, .(X2, X3)), X4), .(X1, .(X2, X5))) -> FLATA_IN_AG(.(X3, X4), X5) R is empty. The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) FLATA_IN_AG(x1, x2) = FLATA_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (59) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: FLATA_IN_AG(X2) -> FLATA_IN_AG(X2) FLATA_IN_AG([]) -> FLATA_IN_AG([]) FLATA_IN_AG(.(X1, X4)) -> FLATA_IN_AG(X4) FLATA_IN_AG(.(X1, .(X2, X5))) -> FLATA_IN_AG(X5) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (61) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: FLATA_IN_AG(.(X1, X4)) -> FLATA_IN_AG(X4) FLATA_IN_AG(.(X1, .(X2, X5))) -> FLATA_IN_AG(X5) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + x_2 POL(FLATA_IN_AG(x_1)) = 2*x_1 POL([]) = 0 ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: FLATA_IN_AG(X2) -> FLATA_IN_AG(X2) FLATA_IN_AG([]) -> FLATA_IN_AG([]) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (63) 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 = FLATA_IN_AG(X2) evaluates to t =FLATA_IN_AG(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 FLATA_IN_AG(X2) to FLATA_IN_AG(X2). ---------------------------------------- (64) NO