/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern flat(a,g) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) PiDP (9) PiDPToQDPProof [SOUND, 0 ms] (10) QDP (11) UsableRulesReductionPairsProof [EQUIVALENT, 3 ms] (12) QDP (13) NonTerminationLoopProof [COMPLETE, 0 ms] (14) NO (15) PrologToPiTRSProof [SOUND, 0 ms] (16) PiTRS (17) DependencyPairsProof [EQUIVALENT, 0 ms] (18) PiDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) PiDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) PiDP (23) PiDPToQDPProof [SOUND, 0 ms] (24) QDP (25) UsableRulesReductionPairsProof [EQUIVALENT, 5 ms] (26) QDP (27) NonTerminationLoopProof [COMPLETE, 0 ms] (28) NO (29) PrologToIRSwTTransformerProof [SOUND, 0 ms] (30) IRSwT (31) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (32) IRSwT (33) IntTRSCompressionProof [EQUIVALENT, 44 ms] (34) IRSwT (35) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (36) IRSwT (37) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (38) IRSwT (39) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (40) IRSwT (41) PrologToDTProblemTransformerProof [SOUND, 0 ms] (42) TRIPLES (43) TriplesToPiDPProof [SOUND, 0 ms] (44) PiDP (45) DependencyGraphProof [EQUIVALENT, 0 ms] (46) PiDP (47) PiDPToQDPProof [SOUND, 0 ms] (48) QDP (49) UsableRulesReductionPairsProof [EQUIVALENT, 5 ms] (50) QDP (51) PrologToTRSTransformerProof [SOUND, 0 ms] (52) QTRS (53) DependencyPairsProof [EQUIVALENT, 0 ms] (54) QDP (55) DependencyGraphProof [EQUIVALENT, 0 ms] (56) QDP (57) UsableRulesProof [EQUIVALENT, 0 ms] (58) QDP (59) UsableRulesReductionPairsProof [EQUIVALENT, 4 ms] (60) QDP (61) NonTerminationLoopProof [COMPLETE, 0 ms] (62) 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) 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 ---------------------------------------- (2) 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) ---------------------------------------- (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: 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 ---------------------------------------- (4) 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 ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (6) 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 ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (8) 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 ---------------------------------------- (9) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (10) 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. ---------------------------------------- (11) 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 ---------------------------------------- (12) 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. ---------------------------------------- (13) 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). ---------------------------------------- (14) NO ---------------------------------------- (15) 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 ---------------------------------------- (16) 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) ---------------------------------------- (17) 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 ---------------------------------------- (18) 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 ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (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) 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 ---------------------------------------- (21) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (22) 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 ---------------------------------------- (23) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (24) 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. ---------------------------------------- (25) 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 ---------------------------------------- (26) 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. ---------------------------------------- (27) 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). ---------------------------------------- (28) NO ---------------------------------------- (29) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 6, "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", "121": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "122": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "133": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T26 T27) T25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "135": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "125": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "127": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T13 T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [], "exprvars": [] } }, "129": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "71": { "goal": [{ "clause": 0, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "72": { "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": [] } }, "73": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "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": [] } } }, "edges": [ { "from": 6, "to": 10, "label": "CASE" }, { "from": 10, "to": 71, "label": "PARALLEL" }, { "from": 10, "to": 72, "label": "PARALLEL" }, { "from": 71, "to": 73, "label": "EVAL with clause\nflat([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 71, "to": 121, "label": "EVAL-BACKTRACK" }, { "from": 72, "to": 124, "label": "PARALLEL" }, { "from": 72, "to": 125, "label": "PARALLEL" }, { "from": 73, "to": 122, "label": "SUCCESS" }, { "from": 124, "to": 127, "label": "EVAL with clause\nflat(.([], X9), X10) :- flat(X9, X10).\nand substitutionX9 -> T13,\nT1 -> .([], T13),\nT2 -> T12,\nX10 -> T12,\nT11 -> T13" }, { "from": 124, "to": 129, "label": "EVAL-BACKTRACK" }, { "from": 125, "to": 133, "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": 125, "to": 135, "label": "EVAL-BACKTRACK" }, { "from": 127, "to": 6, "label": "INSTANCE with matching:\nT1 -> T13\nT2 -> T12" }, { "from": 133, "to": 6, "label": "INSTANCE with matching:\nT1 -> .(T26, T27)\nT2 -> T25" } ], "type": "Graph" } } ---------------------------------------- (30) Obligation: Rules: f124_out(T2) -> f72_out(T2) :|: TRUE f72_in(x) -> f125_in(x) :|: TRUE f72_in(x1) -> f124_in(x1) :|: TRUE f125_out(x2) -> f72_out(x2) :|: TRUE f124_in(T12) -> f127_in(T12) :|: TRUE f129_out -> f124_out(x3) :|: TRUE f124_in(x4) -> f129_in :|: TRUE f127_out(x5) -> f124_out(x5) :|: TRUE f10_in(x6) -> f72_in(x6) :|: TRUE f72_out(x7) -> f10_out(x7) :|: TRUE f10_in(x8) -> f71_in(x8) :|: TRUE f71_out(x9) -> f10_out(x9) :|: TRUE f6_out(T25) -> f133_out(T25) :|: TRUE f133_in(x10) -> f6_in(x10) :|: TRUE f135_out -> f125_out(x11) :|: TRUE f133_out(x12) -> f125_out(.(x13, x12)) :|: TRUE f125_in(.(x14, x15)) -> f133_in(x15) :|: TRUE f125_in(x16) -> f135_in :|: TRUE f6_out(x17) -> f127_out(x17) :|: TRUE f127_in(x18) -> f6_in(x18) :|: TRUE f6_in(x19) -> f10_in(x19) :|: TRUE f10_out(x20) -> f6_out(x20) :|: TRUE Start term: f6_in(T2) ---------------------------------------- (31) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f72_in(x) -> f125_in(x) :|: TRUE f72_in(x1) -> f124_in(x1) :|: TRUE f124_in(T12) -> f127_in(T12) :|: TRUE f10_in(x6) -> f72_in(x6) :|: TRUE f133_in(x10) -> f6_in(x10) :|: TRUE f125_in(.(x14, x15)) -> f133_in(x15) :|: TRUE f127_in(x18) -> f6_in(x18) :|: TRUE f6_in(x19) -> f10_in(x19) :|: TRUE ---------------------------------------- (32) Obligation: Rules: f72_in(x) -> f125_in(x) :|: TRUE f72_in(x1) -> f124_in(x1) :|: TRUE f124_in(T12) -> f127_in(T12) :|: TRUE f10_in(x6) -> f72_in(x6) :|: TRUE f133_in(x10) -> f6_in(x10) :|: TRUE f125_in(.(x14, x15)) -> f133_in(x15) :|: TRUE f127_in(x18) -> f6_in(x18) :|: TRUE f6_in(x19) -> f10_in(x19) :|: TRUE ---------------------------------------- (33) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (34) Obligation: Rules: f10_in(x6:0) -> f10_in(x6:0) :|: TRUE f10_in(.(x14:0, x15:0)) -> f10_in(x15:0) :|: TRUE ---------------------------------------- (35) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (36) Obligation: Rules: f10_in(x6:0) -> f10_in(x6:0) :|: TRUE f10_in(.(x14:0, x15:0)) -> f10_in(x15:0) :|: TRUE ---------------------------------------- (37) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f10_in(x6:0) -> f10_in(x6:0) :|: TRUE (2) f10_in(.(x14:0, x15:0)) -> f10_in(x15:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (38) Obligation: Termination digraph: Nodes: (1) f10_in(x6:0) -> f10_in(x6:0) :|: TRUE (2) f10_in(.(x14:0, x15:0)) -> f10_in(x15:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (39) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: .(x1, x2) -> .(x2) ---------------------------------------- (40) Obligation: Rules: f10_in(x6:0) -> f10_in(x6:0) :|: TRUE f10_in(.(x15:0)) -> f10_in(x15:0) :|: TRUE ---------------------------------------- (41) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 5, "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", "150": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T71 T72) T70)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T70"], "free": [], "exprvars": [] } }, "151": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "152": { "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": [] } }, "153": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "154": { "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": [] } }, "155": { "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": [] } }, "156": { "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": [] } }, "157": { "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": [] } }, "158": { "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": [] } }, "159": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "52": { "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": [] } }, "54": { "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": [] } }, "55": { "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": [] } }, "56": { "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": [] } }, "57": { "goal": [{ "clause": 0, "scope": 2, "term": "(flat T5 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "58": { "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": [] } }, "59": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "160": { "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": [] } }, "161": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "123": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(flat T1 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "126": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "128": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "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": [] } }, "60": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "61": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "63": { "goal": [{ "clause": 1, "scope": 2, "term": "(flat T5 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "65": { "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": [] } }, "67": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T11 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "68": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "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": [] } }, "130": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "131": { "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": [] } }, "132": { "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": [] } }, "134": { "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": [] } }, "136": { "goal": [{ "clause": 0, "scope": 3, "term": "(flat T25 T24)" }], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "137": { "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": [] } }, "138": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "139": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "34": { "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": [] } }, "140": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "141": { "goal": [{ "clause": 1, "scope": 3, "term": "(flat T25 T24)" }], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "142": { "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": [] } }, "143": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T36 T35)" }], "kb": { "nonunifying": [[ "(flat T1 T35)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T35"], "free": [], "exprvars": [] } }, "144": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "145": { "goal": [{ "clause": 2, "scope": 3, "term": "(flat T25 T24)" }], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "146": { "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": [] } }, "147": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T57 T58) T56)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T56"], "free": [], "exprvars": [] } }, "148": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "149": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T24)" }], "kb": { "nonunifying": [[ "(flat T1 T24)", "(flat ([]) ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 5, "to": 8, "label": "CASE" }, { "from": 8, "to": 28, "label": "EVAL with clause\nflat([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 8, "to": 34, "label": "EVAL-BACKTRACK" }, { "from": 28, "to": 52, "label": "SUCCESS" }, { "from": 34, "to": 131, "label": "EVAL with clause\nflat(.([], X29), X30) :- flat(X29, X30).\nand substitutionX29 -> T25,\nT1 -> .([], T25),\nT2 -> T24,\nX30 -> T24,\nT23 -> T25" }, { "from": 34, "to": 132, "label": "EVAL-BACKTRACK" }, { "from": 52, "to": 54, "label": "EVAL with clause\nflat(.([], X3), X4) :- flat(X3, X4).\nand substitutionX3 -> T5,\nT1 -> .([], T5),\nX4 -> [],\nT4 -> T5" }, { "from": 52, "to": 55, "label": "EVAL-BACKTRACK" }, { "from": 54, "to": 56, "label": "CASE" }, { "from": 55, "to": 130, "label": "BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification" }, { "from": 56, "to": 57, "label": "PARALLEL" }, { "from": 56, "to": 58, "label": "PARALLEL" }, { "from": 57, "to": 59, "label": "EVAL with clause\nflat([], []).\nand substitutionT5 -> []" }, { "from": 57, "to": 60, "label": "EVAL-BACKTRACK" }, { "from": 58, "to": 63, "label": "PARALLEL" }, { "from": 58, "to": 65, "label": "PARALLEL" }, { "from": 59, "to": 61, "label": "SUCCESS" }, { "from": 63, "to": 67, "label": "EVAL with clause\nflat(.([], X13), X14) :- flat(X13, X14).\nand substitutionX13 -> T11,\nT5 -> .([], T11),\nX14 -> [],\nT10 -> T11" }, { "from": 63, "to": 68, "label": "EVAL-BACKTRACK" }, { "from": 65, "to": 123, "label": "BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification" }, { "from": 67, "to": 5, "label": "INSTANCE with matching:\nT1 -> T11\nT2 -> []" }, { "from": 123, "to": 126, "label": "FAILURE" }, { "from": 126, "to": 128, "label": "BACKTRACK\nfor clause: flat(.(.(H, T), TT), .(H, R)) :- flat(.(T, TT), R)because of non-unification" }, { "from": 131, "to": 134, "label": "CASE" }, { "from": 132, "to": 152, "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": 132, "to": 153, "label": "EVAL-BACKTRACK" }, { "from": 134, "to": 136, "label": "PARALLEL" }, { "from": 134, "to": 137, "label": "PARALLEL" }, { "from": 136, "to": 138, "label": "EVAL with clause\nflat([], []).\nand substitutionT25 -> [],\nT24 -> []" }, { "from": 136, "to": 139, "label": "EVAL-BACKTRACK" }, { "from": 137, "to": 141, "label": "PARALLEL" }, { "from": 137, "to": 142, "label": "PARALLEL" }, { "from": 138, "to": 140, "label": "SUCCESS" }, { "from": 141, "to": 143, "label": "EVAL with clause\nflat(.([], X39), X40) :- flat(X39, X40).\nand substitutionX39 -> T36,\nT25 -> .([], T36),\nT24 -> T35,\nX40 -> T35,\nT34 -> T36" }, { "from": 141, "to": 144, "label": "EVAL-BACKTRACK" }, { "from": 142, "to": 145, "label": "PARALLEL" }, { "from": 142, "to": 146, "label": "PARALLEL" }, { "from": 143, "to": 5, "label": "INSTANCE with matching:\nT1 -> T36\nT2 -> T35" }, { "from": 145, "to": 147, "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": 145, "to": 148, "label": "EVAL-BACKTRACK" }, { "from": 146, "to": 149, "label": "FAILURE" }, { "from": 147, "to": 5, "label": "INSTANCE with matching:\nT1 -> .(T57, T58)\nT2 -> T56" }, { "from": 149, "to": 150, "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": 149, "to": 151, "label": "EVAL-BACKTRACK" }, { "from": 150, "to": 5, "label": "INSTANCE with matching:\nT1 -> .(T71, T72)\nT2 -> T70" }, { "from": 152, "to": 154, "label": "CASE" }, { "from": 154, "to": 155, "label": "BACKTRACK\nfor clause: flat([], [])because of non-unification" }, { "from": 155, "to": 156, "label": "PARALLEL" }, { "from": 155, "to": 157, "label": "PARALLEL" }, { "from": 156, "to": 158, "label": "EVAL with clause\nflat(.([], X89), X90) :- flat(X89, X90).\nand substitutionT81 -> [],\nT82 -> T93,\nX89 -> T93,\nT80 -> T92,\nX90 -> T92,\nT91 -> T93" }, { "from": 156, "to": 159, "label": "EVAL-BACKTRACK" }, { "from": 157, "to": 160, "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": 157, "to": 161, "label": "EVAL-BACKTRACK" }, { "from": 158, "to": 5, "label": "INSTANCE with matching:\nT1 -> T93\nT2 -> T92" }, { "from": 160, "to": 5, "label": "INSTANCE with matching:\nT1 -> .(T106, T107)\nT2 -> T105" } ], "type": "Graph" } } ---------------------------------------- (42) 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) ---------------------------------------- (43) 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 ---------------------------------------- (44) 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 ---------------------------------------- (45) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 6 less nodes. ---------------------------------------- (46) 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 ---------------------------------------- (47) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (48) 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. ---------------------------------------- (49) 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 ---------------------------------------- (50) 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. ---------------------------------------- (51) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 7, "program": { "directives": [], "clauses": [ [ "(flat ([]) ([]))", null ], [ "(flat (. ([]) T) R)", "(flat T R)" ], [ "(flat (. (. H T) TT) (. H R))", "(flat (. T TT) R)" ] ] }, "graph": { "nodes": { "14": { "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": [] } }, "19": { "goal": [{ "clause": 0, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "type": "Nodes", "162": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (. T26 T27) T25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "163": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "120": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "113": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "114": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "107": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "108": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "119": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T13 T12)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [], "exprvars": [] } }, "109": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "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": [] } } }, "edges": [ { "from": 7, "to": 14, "label": "CASE" }, { "from": 14, "to": 19, "label": "PARALLEL" }, { "from": 14, "to": 20, "label": "PARALLEL" }, { "from": 19, "to": 107, "label": "EVAL with clause\nflat([], []).\nand substitutionT1 -> [],\nT2 -> []" }, { "from": 19, "to": 108, "label": "EVAL-BACKTRACK" }, { "from": 20, "to": 113, "label": "PARALLEL" }, { "from": 20, "to": 114, "label": "PARALLEL" }, { "from": 107, "to": 109, "label": "SUCCESS" }, { "from": 113, "to": 119, "label": "EVAL with clause\nflat(.([], X9), X10) :- flat(X9, X10).\nand substitutionX9 -> T13,\nT1 -> .([], T13),\nT2 -> T12,\nX10 -> T12,\nT11 -> T13" }, { "from": 113, "to": 120, "label": "EVAL-BACKTRACK" }, { "from": 114, "to": 162, "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": 114, "to": 163, "label": "EVAL-BACKTRACK" }, { "from": 119, "to": 7, "label": "INSTANCE with matching:\nT1 -> T13\nT2 -> T12" }, { "from": 162, "to": 7, "label": "INSTANCE with matching:\nT1 -> .(T26, T27)\nT2 -> T25" } ], "type": "Graph" } } ---------------------------------------- (52) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f7_in([]) -> f7_out1([]) f7_in(T12) -> U1(f7_in(T12), T12) U1(f7_out1(T13), T12) -> f7_out1(.([], T13)) f7_in(.(T22, T25)) -> U2(f7_in(T25), .(T22, T25)) U2(f7_out1(.(T26, T27)), .(T22, T25)) -> f7_out1(.(.(T22, T26), T27)) Q is empty. ---------------------------------------- (53) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: F7_IN(T12) -> U1^1(f7_in(T12), T12) F7_IN(T12) -> F7_IN(T12) F7_IN(.(T22, T25)) -> U2^1(f7_in(T25), .(T22, T25)) F7_IN(.(T22, T25)) -> F7_IN(T25) The TRS R consists of the following rules: f7_in([]) -> f7_out1([]) f7_in(T12) -> U1(f7_in(T12), T12) U1(f7_out1(T13), T12) -> f7_out1(.([], T13)) f7_in(.(T22, T25)) -> U2(f7_in(T25), .(T22, T25)) U2(f7_out1(.(T26, T27)), .(T22, T25)) -> f7_out1(.(.(T22, T26), T27)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: F7_IN(.(T22, T25)) -> F7_IN(T25) F7_IN(T12) -> F7_IN(T12) The TRS R consists of the following rules: f7_in([]) -> f7_out1([]) f7_in(T12) -> U1(f7_in(T12), T12) U1(f7_out1(T13), T12) -> f7_out1(.([], T13)) f7_in(.(T22, T25)) -> U2(f7_in(T25), .(T22, T25)) U2(f7_out1(.(T26, T27)), .(T22, T25)) -> f7_out1(.(.(T22, T26), T27)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) 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. ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: F7_IN(.(T22, T25)) -> F7_IN(T25) F7_IN(T12) -> F7_IN(T12) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) 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: F7_IN(.(T22, T25)) -> F7_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(F7_IN(x_1)) = 2*x_1 ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: F7_IN(T12) -> F7_IN(T12) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) 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 = F7_IN(T12) evaluates to t =F7_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 F7_IN(T12) to F7_IN(T12). ---------------------------------------- (62) NO