/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern 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, 11 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, 7 ms] (12) QDP (13) DependencyGraphProof [EQUIVALENT, 0 ms] (14) QDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) QDP (17) QReductionProof [EQUIVALENT, 0 ms] (18) QDP (19) NonTerminationLoopProof [COMPLETE, 0 ms] (20) NO (21) PrologToTRSTransformerProof [SOUND, 0 ms] (22) QTRS (23) DependencyPairsProof [EQUIVALENT, 0 ms] (24) QDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) QDP (27) UsableRulesProof [EQUIVALENT, 0 ms] (28) QDP (29) UsableRulesReductionPairsProof [EQUIVALENT, 2 ms] (30) QDP (31) NonTerminationLoopProof [COMPLETE, 0 ms] (32) NO (33) PrologToIRSwTTransformerProof [SOUND, 0 ms] (34) IRSwT (35) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (36) IRSwT (37) IntTRSCompressionProof [EQUIVALENT, 45 ms] (38) IRSwT (39) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (40) IRSwT (41) IRSwTTerminationDigraphProof [EQUIVALENT, 11 ms] (42) IRSwT (43) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 29 ms] (44) IRSwT (45) PrologToPiTRSProof [SOUND, 0 ms] (46) PiTRS (47) DependencyPairsProof [EQUIVALENT, 0 ms] (48) PiDP (49) DependencyGraphProof [EQUIVALENT, 0 ms] (50) PiDP (51) UsableRulesProof [EQUIVALENT, 0 ms] (52) PiDP (53) PiDPToQDPProof [SOUND, 0 ms] (54) QDP (55) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (56) QDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) QDP (59) UsableRulesProof [EQUIVALENT, 0 ms] (60) QDP (61) QReductionProof [EQUIVALENT, 0 ms] (62) QDP (63) NonTerminationLoopProof [COMPLETE, 0 ms] (64) NO (65) PrologToDTProblemTransformerProof [SOUND, 0 ms] (66) TRIPLES (67) TriplesToPiDPProof [SOUND, 0 ms] (68) PiDP (69) DependencyGraphProof [EQUIVALENT, 0 ms] (70) PiDP (71) PiDPToQDPProof [SOUND, 0 ms] (72) QDP (73) MRRProof [EQUIVALENT, 6 ms] (74) QDP (75) NonTerminationLoopProof [COMPLETE, 0 ms] (76) NO ---------------------------------------- (0) Obligation: Clauses: right(tree(X, XS1, XS2), XS2). flat(niltree, nil). flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS)). flat(tree(X, tree(Y, YS1, YS2), XS), ZS) :- flat(tree(Y, YS1, tree(X, YS2, XS)), ZS). 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(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) 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(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) ---------------------------------------- (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(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> RIGHT_IN_AA(tree(X, niltree, XS), ZS) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_AG(X, XS, YS, flat_in_ag(ZS, YS)) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_AG(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x1, x3, x4) RIGHT_IN_AA(x1, x2) = RIGHT_IN_AA U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) U3_AG(x1, x2, x3, x4, x5, x6, x7) = U3_AG(x6, x7) 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(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> RIGHT_IN_AA(tree(X, niltree, XS), ZS) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_AG(X, XS, YS, flat_in_ag(ZS, YS)) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_AG(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x1, x3, x4) RIGHT_IN_AA(x1, x2) = RIGHT_IN_AA U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) U3_AG(x1, x2, x3, x4, x5, x6, x7) = U3_AG(x6, x7) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag(x2) cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x1, x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x1, x3, x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x6, x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x1, x3, x4) 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: U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) The argument filtering Pi contains the following mapping: cons(x1, x2) = cons(x1, x2) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x1, x3, x4) 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: U1_AG(X, YS, right_out_aa) -> FLAT_IN_AG(YS) FLAT_IN_AG(cons(X, YS)) -> U1_AG(X, YS, right_in_aa) FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa 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(cons(X, YS)) -> U1_AG(X, YS, right_in_aa) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(FLAT_IN_AG(x_1)) = x_1 POL(U1_AG(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(right_in_aa) = 0 POL(right_out_aa) = 0 ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(X, YS, right_out_aa) -> FLAT_IN_AG(YS) FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (13) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) R is empty. The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (17) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. right_in_aa ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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(ZS) evaluates to t =FLAT_IN_AG(ZS) 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(ZS) to FLAT_IN_AG(ZS). ---------------------------------------- (20) NO ---------------------------------------- (21) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 21, "program": { "directives": [], "clauses": [ [ "(right (tree X XS1 XS2) XS2)", null ], [ "(flat (niltree) (nil))", null ], [ "(flat (tree X (niltree) XS) (cons X YS))", "(',' (right (tree X (niltree) XS) ZS) (flat ZS YS))" ], [ "(flat (tree X (tree Y YS1 YS2) XS) ZS)", "(flat (tree Y YS1 (tree X YS2 XS)) ZS)" ] ] }, "graph": { "nodes": { "22": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "type": "Nodes", "151": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T45 T46 (tree T47 T48 T49)) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "152": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "132": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "133": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "134": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (right (tree T15 (niltree) T18) X18) (flat X18 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T17" ], "free": ["X18"], "exprvars": [] } }, "135": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "136": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (right (tree T15 (niltree) T18) X18) (flat X18 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T17" ], "free": ["X18"], "exprvars": [] } }, "127": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "128": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "139": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T26 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "129": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "21": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "32": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 21, "to": 22, "label": "CASE" }, { "from": 22, "to": 31, "label": "PARALLEL" }, { "from": 22, "to": 32, "label": "PARALLEL" }, { "from": 31, "to": 127, "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" }, { "from": 31, "to": 128, "label": "EVAL-BACKTRACK" }, { "from": 32, "to": 132, "label": "PARALLEL" }, { "from": 32, "to": 133, "label": "PARALLEL" }, { "from": 127, "to": 129, "label": "SUCCESS" }, { "from": 132, "to": 134, "label": "EVAL with clause\nflat(tree(X15, niltree, X16), cons(X15, X17)) :- ','(right(tree(X15, niltree, X16), X18), flat(X18, X17)).\nand substitutionX15 -> T15,\nX16 -> T18,\nT1 -> tree(T15, niltree, T18),\nX17 -> T17,\nT2 -> cons(T15, T17),\nT16 -> T18" }, { "from": 132, "to": 135, "label": "EVAL-BACKTRACK" }, { "from": 133, "to": 151, "label": "EVAL with clause\nflat(tree(X40, tree(X41, X42, X43), X44), X45) :- flat(tree(X41, X42, tree(X40, X43, X44)), X45).\nand substitutionX40 -> T47,\nX41 -> T45,\nX42 -> T46,\nX43 -> T48,\nX44 -> T49,\nT1 -> tree(T47, tree(T45, T46, T48), T49),\nT2 -> T44,\nX45 -> T44,\nT40 -> T45,\nT41 -> T46,\nT39 -> T47,\nT42 -> T48,\nT43 -> T49" }, { "from": 133, "to": 152, "label": "EVAL-BACKTRACK" }, { "from": 134, "to": 136, "label": "CASE" }, { "from": 136, "to": 139, "label": "ONLY EVAL with clause\nright(tree(X25, X26, X27), X27).\nand substitutionT15 -> T24,\nX25 -> T24,\nX26 -> niltree,\nT18 -> T26,\nX27 -> T26,\nX18 -> T26,\nT25 -> T26" }, { "from": 139, "to": 21, "label": "INSTANCE with matching:\nT1 -> T26\nT2 -> T17" }, { "from": 151, "to": 21, "label": "INSTANCE with matching:\nT1 -> tree(T45, T46, tree(T47, T48, T49))\nT2 -> T44" } ], "type": "Graph" } } ---------------------------------------- (22) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f21_in(nil) -> f21_out1 f21_in(cons(T24, T17)) -> U1(f21_in(T17), cons(T24, T17)) U1(f21_out1, cons(T24, T17)) -> f21_out1 f21_in(T44) -> U2(f21_in(T44), T44) U2(f21_out1, T44) -> f21_out1 Q is empty. ---------------------------------------- (23) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: F21_IN(cons(T24, T17)) -> U1^1(f21_in(T17), cons(T24, T17)) F21_IN(cons(T24, T17)) -> F21_IN(T17) F21_IN(T44) -> U2^1(f21_in(T44), T44) F21_IN(T44) -> F21_IN(T44) The TRS R consists of the following rules: f21_in(nil) -> f21_out1 f21_in(cons(T24, T17)) -> U1(f21_in(T17), cons(T24, T17)) U1(f21_out1, cons(T24, T17)) -> f21_out1 f21_in(T44) -> U2(f21_in(T44), T44) U2(f21_out1, T44) -> f21_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: F21_IN(T44) -> F21_IN(T44) F21_IN(cons(T24, T17)) -> F21_IN(T17) The TRS R consists of the following rules: f21_in(nil) -> f21_out1 f21_in(cons(T24, T17)) -> U1(f21_in(T17), cons(T24, T17)) U1(f21_out1, cons(T24, T17)) -> f21_out1 f21_in(T44) -> U2(f21_in(T44), T44) U2(f21_out1, T44) -> f21_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) 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. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: F21_IN(T44) -> F21_IN(T44) F21_IN(cons(T24, T17)) -> F21_IN(T17) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) 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: F21_IN(cons(T24, T17)) -> F21_IN(T17) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(F21_IN(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: F21_IN(T44) -> F21_IN(T44) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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 = F21_IN(T44) evaluates to t =F21_IN(T44) 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 F21_IN(T44) to F21_IN(T44). ---------------------------------------- (32) NO ---------------------------------------- (33) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 11, "program": { "directives": [], "clauses": [ [ "(right (tree X XS1 XS2) XS2)", null ], [ "(flat (niltree) (nil))", null ], [ "(flat (tree X (niltree) XS) (cons X YS))", "(',' (right (tree X (niltree) XS) ZS) (flat ZS YS))" ], [ "(flat (tree X (tree Y YS1 YS2) XS) ZS)", "(flat (tree Y YS1 (tree X YS2 XS)) ZS)" ] ] }, "graph": { "nodes": { "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "12": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "type": "Nodes", "140": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "141": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "142": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "153": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T45 T46 (tree T47 T48 T49)) T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "143": { "goal": [{ "clause": 2, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "144": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "155": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "145": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (right (tree T15 (niltree) T18) X18) (flat X18 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T17" ], "free": ["X18"], "exprvars": [] } }, "146": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "147": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (right (tree T15 (niltree) T18) X18) (flat X18 T17))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T17" ], "free": ["X18"], "exprvars": [] } }, "137": { "goal": [{ "clause": 1, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "148": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T26 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [], "exprvars": [] } }, "138": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 11, "to": 12, "label": "CASE" }, { "from": 12, "to": 137, "label": "PARALLEL" }, { "from": 12, "to": 138, "label": "PARALLEL" }, { "from": 137, "to": 140, "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" }, { "from": 137, "to": 141, "label": "EVAL-BACKTRACK" }, { "from": 138, "to": 143, "label": "PARALLEL" }, { "from": 138, "to": 144, "label": "PARALLEL" }, { "from": 140, "to": 142, "label": "SUCCESS" }, { "from": 143, "to": 145, "label": "EVAL with clause\nflat(tree(X15, niltree, X16), cons(X15, X17)) :- ','(right(tree(X15, niltree, X16), X18), flat(X18, X17)).\nand substitutionX15 -> T15,\nX16 -> T18,\nT1 -> tree(T15, niltree, T18),\nX17 -> T17,\nT2 -> cons(T15, T17),\nT16 -> T18" }, { "from": 143, "to": 146, "label": "EVAL-BACKTRACK" }, { "from": 144, "to": 153, "label": "EVAL with clause\nflat(tree(X40, tree(X41, X42, X43), X44), X45) :- flat(tree(X41, X42, tree(X40, X43, X44)), X45).\nand substitutionX40 -> T47,\nX41 -> T45,\nX42 -> T46,\nX43 -> T48,\nX44 -> T49,\nT1 -> tree(T47, tree(T45, T46, T48), T49),\nT2 -> T44,\nX45 -> T44,\nT40 -> T45,\nT41 -> T46,\nT39 -> T47,\nT42 -> T48,\nT43 -> T49" }, { "from": 144, "to": 155, "label": "EVAL-BACKTRACK" }, { "from": 145, "to": 147, "label": "CASE" }, { "from": 147, "to": 148, "label": "ONLY EVAL with clause\nright(tree(X25, X26, X27), X27).\nand substitutionT15 -> T24,\nX25 -> T24,\nX26 -> niltree,\nT18 -> T26,\nX27 -> T26,\nX18 -> T26,\nT25 -> T26" }, { "from": 148, "to": 11, "label": "INSTANCE with matching:\nT1 -> T26\nT2 -> T17" }, { "from": 153, "to": 11, "label": "INSTANCE with matching:\nT1 -> tree(T45, T46, tree(T47, T48, T49))\nT2 -> T44" } ], "type": "Graph" } } ---------------------------------------- (34) Obligation: Rules: f138_in(T2) -> f143_in(T2) :|: TRUE f143_out(x) -> f138_out(x) :|: TRUE f144_out(x1) -> f138_out(x1) :|: TRUE f138_in(x2) -> f144_in(x2) :|: TRUE f146_out -> f143_out(x3) :|: TRUE f143_in(x4) -> f146_in :|: TRUE f143_in(cons(T15, T17)) -> f145_in(T15, T17) :|: TRUE f145_out(x5, x6) -> f143_out(cons(x5, x6)) :|: TRUE f147_in(x7, x8) -> f148_in(x8) :|: TRUE f148_out(x9) -> f147_out(x10, x9) :|: TRUE f148_in(x11) -> f11_in(x11) :|: TRUE f11_out(x12) -> f148_out(x12) :|: TRUE f12_in(x13) -> f137_in(x13) :|: TRUE f137_out(x14) -> f12_out(x14) :|: TRUE f12_in(x15) -> f138_in(x15) :|: TRUE f138_out(x16) -> f12_out(x16) :|: TRUE f144_in(x17) -> f155_in :|: TRUE f155_out -> f144_out(x18) :|: TRUE f153_out(T44) -> f144_out(T44) :|: TRUE f144_in(x19) -> f153_in(x19) :|: TRUE f147_out(x20, x21) -> f145_out(x20, x21) :|: TRUE f145_in(x22, x23) -> f147_in(x22, x23) :|: TRUE f12_out(x24) -> f11_out(x24) :|: TRUE f11_in(x25) -> f12_in(x25) :|: TRUE f11_out(x26) -> f153_out(x26) :|: TRUE f153_in(x27) -> f11_in(x27) :|: TRUE Start term: f11_in(T2) ---------------------------------------- (35) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f138_in(T2) -> f143_in(T2) :|: TRUE f138_in(x2) -> f144_in(x2) :|: TRUE f143_in(cons(T15, T17)) -> f145_in(T15, T17) :|: TRUE f147_in(x7, x8) -> f148_in(x8) :|: TRUE f148_in(x11) -> f11_in(x11) :|: TRUE f12_in(x15) -> f138_in(x15) :|: TRUE f144_in(x19) -> f153_in(x19) :|: TRUE f145_in(x22, x23) -> f147_in(x22, x23) :|: TRUE f11_in(x25) -> f12_in(x25) :|: TRUE f153_in(x27) -> f11_in(x27) :|: TRUE ---------------------------------------- (36) Obligation: Rules: f138_in(T2) -> f143_in(T2) :|: TRUE f138_in(x2) -> f144_in(x2) :|: TRUE f143_in(cons(T15, T17)) -> f145_in(T15, T17) :|: TRUE f147_in(x7, x8) -> f148_in(x8) :|: TRUE f148_in(x11) -> f11_in(x11) :|: TRUE f12_in(x15) -> f138_in(x15) :|: TRUE f144_in(x19) -> f153_in(x19) :|: TRUE f145_in(x22, x23) -> f147_in(x22, x23) :|: TRUE f11_in(x25) -> f12_in(x25) :|: TRUE f153_in(x27) -> f11_in(x27) :|: TRUE ---------------------------------------- (37) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (38) Obligation: Rules: f12_in(cons(T15:0, T17:0)) -> f12_in(T17:0) :|: TRUE f12_in(x15:0) -> f12_in(x15:0) :|: TRUE ---------------------------------------- (39) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (40) Obligation: Rules: f12_in(cons(T15:0, T17:0)) -> f12_in(T17:0) :|: TRUE f12_in(x15:0) -> f12_in(x15:0) :|: TRUE ---------------------------------------- (41) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f12_in(cons(T15:0, T17:0)) -> f12_in(T17:0) :|: TRUE (2) f12_in(x15:0) -> f12_in(x15:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (42) Obligation: Termination digraph: Nodes: (1) f12_in(cons(T15:0, T17:0)) -> f12_in(T17:0) :|: TRUE (2) f12_in(x15:0) -> f12_in(x15:0) :|: TRUE Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (43) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: cons(x1, x2) -> cons(x2) ---------------------------------------- (44) Obligation: Rules: f12_in(cons(T17:0)) -> f12_in(T17:0) :|: TRUE f12_in(x15:0) -> f12_in(x15:0) :|: TRUE ---------------------------------------- (45) 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(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (46) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) ---------------------------------------- (47) 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(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> RIGHT_IN_AA(tree(X, niltree, XS), ZS) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_AG(X, XS, YS, flat_in_ag(ZS, YS)) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_AG(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) RIGHT_IN_AA(x1, x2) = RIGHT_IN_AA U2_AG(x1, x2, x3, x4) = U2_AG(x4) U3_AG(x1, x2, x3, x4, x5, x6, x7) = U3_AG(x7) We have to consider all (P,R,Pi)-chains ---------------------------------------- (48) Obligation: Pi DP problem: The TRS P consists of the following rules: FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> RIGHT_IN_AA(tree(X, niltree, XS), ZS) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_AG(X, XS, YS, flat_in_ag(ZS, YS)) U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_AG(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) RIGHT_IN_AA(x1, x2) = RIGHT_IN_AA U2_AG(x1, x2, x3, x4) = U2_AG(x4) U3_AG(x1, x2, x3, x4, x5, x6, x7) = U3_AG(x7) We have to consider all (P,R,Pi)-chains ---------------------------------------- (49) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (50) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: flat_in_ag(niltree, nil) -> flat_out_ag(niltree, nil) flat_in_ag(tree(X, niltree, XS), cons(X, YS)) -> U1_ag(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) U1_ag(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> U2_ag(X, XS, YS, flat_in_ag(ZS, YS)) flat_in_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) -> U3_ag(X, Y, YS1, YS2, XS, ZS, flat_in_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) U3_ag(X, Y, YS1, YS2, XS, ZS, flat_out_ag(tree(Y, YS1, tree(X, YS2, XS)), ZS)) -> flat_out_ag(tree(X, tree(Y, YS1, YS2), XS), ZS) U2_ag(X, XS, YS, flat_out_ag(ZS, YS)) -> flat_out_ag(tree(X, niltree, XS), cons(X, YS)) The argument filtering Pi contains the following mapping: flat_in_ag(x1, x2) = flat_in_ag(x2) nil = nil flat_out_ag(x1, x2) = flat_out_ag cons(x1, x2) = cons(x1, x2) U1_ag(x1, x2, x3, x4) = U1_ag(x3, x4) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) U2_ag(x1, x2, x3, x4) = U2_ag(x4) U3_ag(x1, x2, x3, x4, x5, x6, x7) = U3_ag(x7) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (51) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (52) Obligation: Pi DP problem: The TRS P consists of the following rules: U1_AG(X, XS, YS, right_out_aa(tree(X, niltree, XS), ZS)) -> FLAT_IN_AG(ZS, YS) FLAT_IN_AG(tree(X, niltree, XS), cons(X, YS)) -> U1_AG(X, XS, YS, right_in_aa(tree(X, niltree, XS), ZS)) FLAT_IN_AG(tree(X, tree(Y, YS1, YS2), XS), ZS) -> FLAT_IN_AG(tree(Y, YS1, tree(X, YS2, XS)), ZS) The TRS R consists of the following rules: right_in_aa(tree(X, XS1, XS2), XS2) -> right_out_aa(tree(X, XS1, XS2), XS2) The argument filtering Pi contains the following mapping: cons(x1, x2) = cons(x1, x2) right_in_aa(x1, x2) = right_in_aa right_out_aa(x1, x2) = right_out_aa tree(x1, x2, x3) = tree(x2, x3) FLAT_IN_AG(x1, x2) = FLAT_IN_AG(x2) U1_AG(x1, x2, x3, x4) = U1_AG(x3, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (53) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(YS, right_out_aa) -> FLAT_IN_AG(YS) FLAT_IN_AG(cons(X, YS)) -> U1_AG(YS, right_in_aa) FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (55) 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(cons(X, YS)) -> U1_AG(YS, right_in_aa) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(FLAT_IN_AG(x_1)) = x_1 POL(U1_AG(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(right_in_aa) = 0 POL(right_out_aa) = 0 ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: U1_AG(YS, right_out_aa) -> FLAT_IN_AG(YS) FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) The TRS R consists of the following rules: right_in_aa -> right_out_aa The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (59) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) R is empty. The set Q consists of the following terms: right_in_aa We have to consider all (P,Q,R)-chains. ---------------------------------------- (61) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. right_in_aa ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: FLAT_IN_AG(ZS) -> FLAT_IN_AG(ZS) 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 = FLAT_IN_AG(ZS) evaluates to t =FLAT_IN_AG(ZS) 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(ZS) to FLAT_IN_AG(ZS). ---------------------------------------- (64) NO ---------------------------------------- (65) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 4, "program": { "directives": [], "clauses": [ [ "(right (tree X XS1 XS2) XS2)", null ], [ "(flat (niltree) (nil))", null ], [ "(flat (tree X (niltree) XS) (cons X YS))", "(',' (right (tree X (niltree) XS) ZS) (flat ZS YS))" ], [ "(flat (tree X (tree Y YS1 YS2) XS) ZS)", "(flat (tree Y YS1 (tree X YS2 XS)) ZS)" ] ] }, "graph": { "nodes": { "type": "Nodes", "130": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T45 T46 (tree T47 T48 (tree T49 T50 T51))) (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "131": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "230": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "231": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "232": { "goal": [ { "clause": 1, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }, { "clause": 2, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }, { "clause": 3, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" } ], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "233": { "goal": [ { "clause": 2, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }, { "clause": 3, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" } ], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "234": { "goal": [{ "clause": 2, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "235": { "goal": [{ "clause": 3, "scope": 4, "term": "(flat (tree T110 T111 (tree T112 T113 T114)) T109)" }], "kb": { "nonunifying": [ [ "(flat T1 T109)", "(flat (niltree) (nil))" ], [ "(flat T1 T109)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T109"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "236": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (right (tree T135 (niltree) (tree T140 T141 T142)) X106) (flat X106 T139))" }], "kb": { "nonunifying": [[ "(flat T1 (cons T135 T139))", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T135", "T139" ], "free": [ "X40", "X41", "X42", "X106" ], "exprvars": [] } }, "237": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "238": { "goal": [{ "clause": 0, "scope": 5, "term": "(',' (right (tree T135 (niltree) (tree T140 T141 T142)) X106) (flat X106 T139))" }], "kb": { "nonunifying": [[ "(flat T1 (cons T135 T139))", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T135", "T139" ], "free": [ "X40", "X41", "X42", "X106" ], "exprvars": [] } }, "239": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T158 T159 T160) T139)" }], "kb": { "nonunifying": [[ "(flat T1 (cons T154 T139))", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T139", "T154" ], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "72": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 2, "scope": 1, "term": "(flat T1 (nil))" }, { "clause": 3, "scope": 1, "term": "(flat T1 (nil))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [ { "clause": 1, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "240": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T185 T186 (tree T187 T188 (tree T189 T190 T191))) T184)" }], "kb": { "nonunifying": [ [ "(flat T1 T184)", "(flat (niltree) (nil))" ], [ "(flat T1 T184)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T184"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "120": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 (nil))" }, { "clause": 3, "scope": 1, "term": "(flat T1 (nil))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "241": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "121": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "122": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "221": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (right (tree T55 (niltree) T58) X43) (flat X43 T57))" }, { "clause": 3, "scope": 1, "term": "(flat T1 (cons T55 T57))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": ["X43"], "exprvars": [] } }, "123": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "222": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [ [ "(flat T1 T2)", "(flat (niltree) (nil))" ], [ "(flat T1 T2)", "(flat (tree X40 (niltree) X41) (cons X40 X42))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [ "X40", "X41", "X42" ], "exprvars": [] } }, "124": { "goal": [ { "clause": 1, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }, { "clause": 2, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }, { "clause": 3, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "223": { "goal": [ { "clause": 0, "scope": 3, "term": "(',' (right (tree T55 (niltree) T58) X43) (flat X43 T57))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 3, "scope": 1, "term": "(flat T1 (cons T55 T57))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": ["X43"], "exprvars": [] } }, "4": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "125": { "goal": [ { "clause": 2, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }, { "clause": 3, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "224": { "goal": [{ "clause": 0, "scope": 3, "term": "(',' (right (tree T55 (niltree) T58) X43) (flat X43 T57))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": ["X43"], "exprvars": [] } }, "126": { "goal": [{ "clause": 3, "scope": 2, "term": "(flat (tree T15 T16 (tree T17 T18 T19)) (nil))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "225": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 3, "scope": 1, "term": "(flat T1 (cons T55 T57))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": [], "exprvars": [] } }, "226": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat T71 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T57"], "free": [], "exprvars": [] } }, "227": { "goal": [{ "clause": 3, "scope": 1, "term": "(flat T1 (cons T55 T57))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T57" ], "free": [], "exprvars": [] } }, "228": { "goal": [{ "clause": -1, "scope": -1, "term": "(flat (tree T93 T94 (tree T95 T96 T97)) (cons T91 T92))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T91", "T92" ], "free": [], "exprvars": [] } }, "229": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "84": { "goal": [ { "clause": 2, "scope": 1, "term": "(flat T1 T2)" }, { "clause": 3, "scope": 1, "term": "(flat T1 T2)" } ], "kb": { "nonunifying": [[ "(flat T1 T2)", "(flat (niltree) (nil))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 4, "to": 10, "label": "CASE" }, { "from": 10, "to": 72, "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" }, { "from": 10, "to": 84, "label": "EVAL-BACKTRACK" }, { "from": 72, "to": 120, "label": "SUCCESS" }, { "from": 84, "to": 221, "label": "EVAL with clause\nflat(tree(X40, niltree, X41), cons(X40, X42)) :- ','(right(tree(X40, niltree, X41), X43), flat(X43, X42)).\nand substitutionX40 -> T55,\nX41 -> T58,\nT1 -> tree(T55, niltree, T58),\nX42 -> T57,\nT2 -> cons(T55, T57),\nT56 -> T58" }, { "from": 84, "to": 222, "label": "EVAL-BACKTRACK" }, { "from": 120, "to": 121, "label": "BACKTRACK\nfor clause: flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS))because of non-unification" }, { "from": 121, "to": 122, "label": "EVAL with clause\nflat(tree(X10, tree(X11, X12, X13), X14), X15) :- flat(tree(X11, X12, tree(X10, X13, X14)), X15).\nand substitutionX10 -> T17,\nX11 -> T15,\nX12 -> T16,\nX13 -> T18,\nX14 -> T19,\nT1 -> tree(T17, tree(T15, T16, T18), T19),\nX15 -> nil,\nT11 -> T15,\nT12 -> T16,\nT10 -> T17,\nT13 -> T18,\nT14 -> T19" }, { "from": 121, "to": 123, "label": "EVAL-BACKTRACK" }, { "from": 122, "to": 124, "label": "CASE" }, { "from": 124, "to": 125, "label": "BACKTRACK\nfor clause: flat(niltree, nil)because of non-unification" }, { "from": 125, "to": 126, "label": "BACKTRACK\nfor clause: flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS))because of non-unification" }, { "from": 126, "to": 130, "label": "EVAL with clause\nflat(tree(X31, tree(X32, X33, X34), X35), X36) :- flat(tree(X32, X33, tree(X31, X34, X35)), X36).\nand substitutionT15 -> T47,\nX31 -> T47,\nX32 -> T45,\nX33 -> T46,\nX34 -> T48,\nT16 -> tree(T45, T46, T48),\nT17 -> T49,\nT18 -> T50,\nT19 -> T51,\nX35 -> tree(T49, T50, T51),\nX36 -> nil,\nT39 -> T45,\nT40 -> T46,\nT38 -> T47,\nT41 -> T48,\nT42 -> T49,\nT43 -> T50,\nT44 -> T51" }, { "from": 126, "to": 131, "label": "EVAL-BACKTRACK" }, { "from": 130, "to": 4, "label": "INSTANCE with matching:\nT1 -> tree(T45, T46, tree(T47, T48, tree(T49, T50, T51)))\nT2 -> nil" }, { "from": 221, "to": 223, "label": "CASE" }, { "from": 222, "to": 230, "label": "EVAL with clause\nflat(tree(X83, tree(X84, X85, X86), X87), X88) :- flat(tree(X84, X85, tree(X83, X86, X87)), X88).\nand substitutionX83 -> T112,\nX84 -> T110,\nX85 -> T111,\nX86 -> T113,\nX87 -> T114,\nT1 -> tree(T112, tree(T110, T111, T113), T114),\nT2 -> T109,\nX88 -> T109,\nT105 -> T110,\nT106 -> T111,\nT104 -> T112,\nT107 -> T113,\nT108 -> T114" }, { "from": 222, "to": 231, "label": "EVAL-BACKTRACK" }, { "from": 223, "to": 224, "label": "PARALLEL" }, { "from": 223, "to": 225, "label": "PARALLEL" }, { "from": 224, "to": 226, "label": "ONLY EVAL with clause\nright(tree(X56, X57, X58), X58).\nand substitutionT55 -> T69,\nX56 -> T69,\nX57 -> niltree,\nT58 -> T71,\nX58 -> T71,\nX43 -> T71,\nT70 -> T71" }, { "from": 225, "to": 227, "label": "FAILURE" }, { "from": 226, "to": 4, "label": "INSTANCE with matching:\nT1 -> T71\nT2 -> T57" }, { "from": 227, "to": 228, "label": "EVAL with clause\nflat(tree(X71, tree(X72, X73, X74), X75), X76) :- flat(tree(X72, X73, tree(X71, X74, X75)), X76).\nand substitutionX71 -> T95,\nX72 -> T93,\nX73 -> T94,\nX74 -> T96,\nX75 -> T97,\nT1 -> tree(T95, tree(T93, T94, T96), T97),\nT55 -> T91,\nT57 -> T92,\nX76 -> cons(T91, T92),\nT87 -> T93,\nT88 -> T94,\nT86 -> T95,\nT89 -> T96,\nT90 -> T97" }, { "from": 227, "to": 229, "label": "EVAL-BACKTRACK" }, { "from": 228, "to": 4, "label": "INSTANCE with matching:\nT1 -> tree(T93, T94, tree(T95, T96, T97))\nT2 -> cons(T91, T92)" }, { "from": 230, "to": 232, "label": "CASE" }, { "from": 232, "to": 233, "label": "BACKTRACK\nfor clause: flat(niltree, nil)because of non-unification" }, { "from": 233, "to": 234, "label": "PARALLEL" }, { "from": 233, "to": 235, "label": "PARALLEL" }, { "from": 234, "to": 236, "label": "EVAL with clause\nflat(tree(X103, niltree, X104), cons(X103, X105)) :- ','(right(tree(X103, niltree, X104), X106), flat(X106, X105)).\nand substitutionT110 -> T135,\nX103 -> T135,\nT111 -> niltree,\nT112 -> T140,\nT113 -> T141,\nT114 -> T142,\nX104 -> tree(T140, T141, T142),\nX105 -> T139,\nT109 -> cons(T135, T139),\nT136 -> T140,\nT137 -> T141,\nT138 -> T142" }, { "from": 234, "to": 237, "label": "EVAL-BACKTRACK" }, { "from": 235, "to": 240, "label": "EVAL with clause\nflat(tree(X128, tree(X129, X130, X131), X132), X133) :- flat(tree(X129, X130, tree(X128, X131, X132)), X133).\nand substitutionT110 -> T187,\nX128 -> T187,\nX129 -> T185,\nX130 -> T186,\nX131 -> T188,\nT111 -> tree(T185, T186, T188),\nT112 -> T189,\nT113 -> T190,\nT114 -> T191,\nX132 -> tree(T189, T190, T191),\nT109 -> T184,\nX133 -> T184,\nT178 -> T185,\nT179 -> T186,\nT177 -> T187,\nT180 -> T188,\nT181 -> T189,\nT182 -> T190,\nT183 -> T191" }, { "from": 235, "to": 241, "label": "EVAL-BACKTRACK" }, { "from": 236, "to": 238, "label": "CASE" }, { "from": 238, "to": 239, "label": "ONLY EVAL with clause\nright(tree(X113, X114, X115), X115).\nand substitutionT135 -> T154,\nX113 -> T154,\nX114 -> niltree,\nT140 -> T158,\nT141 -> T159,\nT142 -> T160,\nX115 -> tree(T158, T159, T160),\nX106 -> tree(T158, T159, T160),\nT155 -> T158,\nT156 -> T159,\nT157 -> T160" }, { "from": 239, "to": 4, "label": "INSTANCE with matching:\nT1 -> tree(T158, T159, T160)\nT2 -> T139" }, { "from": 240, "to": 4, "label": "INSTANCE with matching:\nT1 -> tree(T185, T186, tree(T187, T188, tree(T189, T190, T191)))\nT2 -> T184" } ], "type": "Graph" } } ---------------------------------------- (66) Obligation: Triples: flatA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) :- flatA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil). flatA(tree(X1, niltree, X2), cons(X1, X3)) :- flatA(X2, X3). flatA(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) :- flatA(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)). flatA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) :- flatA(tree(X1, X3, X4), X5). flatA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) :- flatA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8). Clauses: flatcA(niltree, nil). flatcA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) :- flatcA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil). flatcA(tree(X1, niltree, X2), cons(X1, X3)) :- flatcA(X2, X3). flatcA(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) :- flatcA(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)). flatcA(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) :- flatcA(tree(X1, X3, X4), X5). flatcA(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) :- flatcA(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8). Afs: flatA(x1, x2) = flatA(x2) ---------------------------------------- (67) 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(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> U1_AG(X1, X2, X3, X4, X5, X6, X7, flatA_in_ag(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil)) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> U2_AG(X1, X2, X3, flatA_in_ag(X2, X3)) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> FLATA_IN_AG(X2, X3) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> U3_AG(X1, X2, X3, X4, X5, X6, X7, flatA_in_ag(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7))) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> FLATA_IN_AG(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> U4_AG(X1, X2, X3, X4, X5, flatA_in_ag(tree(X1, X3, X4), X5)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> FLATA_IN_AG(tree(X1, X3, X4), X5) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> U5_AG(X1, X2, X3, X4, X5, X6, X7, X8, flatA_in_ag(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8)) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ag(x1, x2) = flatA_in_ag(x2) nil = nil tree(x1, x2, x3) = tree(x2, x3) cons(x1, x2) = cons(x1, x2) niltree = niltree FLATA_IN_AG(x1, x2) = FLATA_IN_AG(x2) U1_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U1_AG(x8) U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) U3_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U3_AG(x6, x7, x8) U4_AG(x1, x2, x3, x4, x5, x6) = U4_AG(x2, x5, x6) U5_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U5_AG(x8, x9) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (68) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> U1_AG(X1, X2, X3, X4, X5, X6, X7, flatA_in_ag(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil)) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> U2_AG(X1, X2, X3, flatA_in_ag(X2, X3)) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> FLATA_IN_AG(X2, X3) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> U3_AG(X1, X2, X3, X4, X5, X6, X7, flatA_in_ag(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7))) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> FLATA_IN_AG(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> U4_AG(X1, X2, X3, X4, X5, flatA_in_ag(tree(X1, X3, X4), X5)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> FLATA_IN_AG(tree(X1, X3, X4), X5) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> U5_AG(X1, X2, X3, X4, X5, X6, X7, X8, flatA_in_ag(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8)) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8) R is empty. The argument filtering Pi contains the following mapping: flatA_in_ag(x1, x2) = flatA_in_ag(x2) nil = nil tree(x1, x2, x3) = tree(x2, x3) cons(x1, x2) = cons(x1, x2) niltree = niltree FLATA_IN_AG(x1, x2) = FLATA_IN_AG(x2) U1_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U1_AG(x8) U2_AG(x1, x2, x3, x4) = U2_AG(x1, x3, x4) U3_AG(x1, x2, x3, x4, x5, x6, x7, x8) = U3_AG(x6, x7, x8) U4_AG(x1, x2, x3, x4, x5, x6) = U4_AG(x2, x5, x6) U5_AG(x1, x2, x3, x4, x5, x6, x7, x8, x9) = U5_AG(x8, x9) We have to consider all (P,R,Pi)-chains ---------------------------------------- (69) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 5 less nodes. ---------------------------------------- (70) Obligation: Pi DP problem: The TRS P consists of the following rules: FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), X8) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), X8) FLATA_IN_AG(tree(X1, tree(X2, tree(X3, X4, X5), X6), X7), nil) -> FLATA_IN_AG(tree(X3, X4, tree(X2, X5, tree(X1, X6, X7))), nil) FLATA_IN_AG(tree(X1, niltree, X2), cons(X1, X3)) -> FLATA_IN_AG(X2, X3) FLATA_IN_AG(tree(X1, tree(X2, X3, X4), X5), cons(X6, X7)) -> FLATA_IN_AG(tree(X2, X3, tree(X1, X4, X5)), cons(X6, X7)) FLATA_IN_AG(tree(X1, tree(X2, niltree, X3), X4), cons(X2, X5)) -> FLATA_IN_AG(tree(X1, X3, X4), X5) R is empty. The argument filtering Pi contains the following mapping: nil = nil tree(x1, x2, x3) = tree(x2, x3) cons(x1, x2) = cons(x1, x2) niltree = niltree FLATA_IN_AG(x1, x2) = FLATA_IN_AG(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (71) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: FLATA_IN_AG(X8) -> FLATA_IN_AG(X8) FLATA_IN_AG(nil) -> FLATA_IN_AG(nil) FLATA_IN_AG(cons(X1, X3)) -> FLATA_IN_AG(X3) FLATA_IN_AG(cons(X6, X7)) -> FLATA_IN_AG(cons(X6, X7)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (73) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: FLATA_IN_AG(cons(X1, X3)) -> FLATA_IN_AG(X3) Used ordering: Polynomial interpretation [POLO]: POL(FLATA_IN_AG(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(nil) = 0 ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: FLATA_IN_AG(X8) -> FLATA_IN_AG(X8) FLATA_IN_AG(nil) -> FLATA_IN_AG(nil) FLATA_IN_AG(cons(X6, X7)) -> FLATA_IN_AG(cons(X6, X7)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (75) 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(X8) evaluates to t =FLATA_IN_AG(X8) 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(X8) to FLATA_IN_AG(X8). ---------------------------------------- (76) NO