/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 tree_member(g,a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) PrologToPiTRSProof [SOUND, 0 ms] (2) PiTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) PiDP (9) PiDPToQDPProof [SOUND, 0 ms] (10) QDP (11) PrologToPiTRSProof [SOUND, 0 ms] (12) PiTRS (13) DependencyPairsProof [EQUIVALENT, 0 ms] (14) PiDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) PiDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) PiDP (19) PiDPToQDPProof [SOUND, 0 ms] (20) QDP (21) PrologToTRSTransformerProof [SOUND, 0 ms] (22) QTRS (23) DependencyPairsProof [EQUIVALENT, 0 ms] (24) QDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) QDP (27) MNOCProof [EQUIVALENT, 0 ms] (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) PrologToIRSwTTransformerProof [SOUND, 0 ms] (34) IRSwT (35) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (36) IRSwT (37) IntTRSCompressionProof [EQUIVALENT, 0 ms] (38) IRSwT (39) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (40) IRSwT (41) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (42) IRSwT (43) FilterProof [EQUIVALENT, 0 ms] (44) IntTRS (45) IntTRSPeriodicNontermProof [COMPLETE, 7 ms] (46) NO (47) PrologToDTProblemTransformerProof [SOUND, 0 ms] (48) TRIPLES (49) TriplesToPiDPProof [SOUND, 18 ms] (50) PiDP (51) DependencyGraphProof [EQUIVALENT, 0 ms] (52) PiDP (53) PiDPToQDPProof [SOUND, 0 ms] (54) QDP ---------------------------------------- (0) Obligation: Clauses: tree_member(X, tree(X, X1, X2)). tree_member(X, tree(X3, Left, X4)) :- tree_member(X, Left). tree_member(X, tree(X5, X6, Right)) :- tree_member(X, Right). Query: tree_member(g,a) ---------------------------------------- (1) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: tree_member_in_2: (b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(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: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(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: TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> U1_GA(X, X3, Left, X4, tree_member_in_ga(X, Left)) TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> TREE_MEMBER_IN_GA(X, Left) TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> U2_GA(X, X5, X6, Right, tree_member_in_ga(X, Right)) TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> TREE_MEMBER_IN_GA(X, Right) The TRS R consists of the following rules: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x5) TREE_MEMBER_IN_GA(x1, x2) = TREE_MEMBER_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x5) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> U1_GA(X, X3, Left, X4, tree_member_in_ga(X, Left)) TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> TREE_MEMBER_IN_GA(X, Left) TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> U2_GA(X, X5, X6, Right, tree_member_in_ga(X, Right)) TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> TREE_MEMBER_IN_GA(X, Right) The TRS R consists of the following rules: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x5) TREE_MEMBER_IN_GA(x1, x2) = TREE_MEMBER_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x5) U2_GA(x1, x2, x3, x4, x5) = U2_GA(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: TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> TREE_MEMBER_IN_GA(X, Right) TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> TREE_MEMBER_IN_GA(X, Left) The TRS R consists of the following rules: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga U1_ga(x1, x2, x3, x4, x5) = U1_ga(x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x5) TREE_MEMBER_IN_GA(x1, x2) = TREE_MEMBER_IN_GA(x1) 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: TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> TREE_MEMBER_IN_GA(X, Right) TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> TREE_MEMBER_IN_GA(X, Left) R is empty. The argument filtering Pi contains the following mapping: TREE_MEMBER_IN_GA(x1, x2) = TREE_MEMBER_IN_GA(x1) 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: TREE_MEMBER_IN_GA(X) -> TREE_MEMBER_IN_GA(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) PrologToPiTRSProof (SOUND) We use the technique of [TOCL09]. With regard to the inferred argument filtering the predicates were used in the following modes: tree_member_in_2: (b,f) Transforming Prolog into the following Term Rewriting System: Pi-finite rewrite system: The TRS R consists of the following rules: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog ---------------------------------------- (12) Obligation: Pi-finite rewrite system: The TRS R consists of the following rules: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) ---------------------------------------- (13) 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: TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> U1_GA(X, X3, Left, X4, tree_member_in_ga(X, Left)) TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> TREE_MEMBER_IN_GA(X, Left) TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> U2_GA(X, X5, X6, Right, tree_member_in_ga(X, Right)) TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> TREE_MEMBER_IN_GA(X, Right) The TRS R consists of the following rules: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) TREE_MEMBER_IN_GA(x1, x2) = TREE_MEMBER_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> U1_GA(X, X3, Left, X4, tree_member_in_ga(X, Left)) TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> TREE_MEMBER_IN_GA(X, Left) TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> U2_GA(X, X5, X6, Right, tree_member_in_ga(X, Right)) TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> TREE_MEMBER_IN_GA(X, Right) The TRS R consists of the following rules: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) TREE_MEMBER_IN_GA(x1, x2) = TREE_MEMBER_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x5) U2_GA(x1, x2, x3, x4, x5) = U2_GA(x1, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> TREE_MEMBER_IN_GA(X, Right) TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> TREE_MEMBER_IN_GA(X, Left) The TRS R consists of the following rules: tree_member_in_ga(X, tree(X, X1, X2)) -> tree_member_out_ga(X, tree(X, X1, X2)) tree_member_in_ga(X, tree(X3, Left, X4)) -> U1_ga(X, X3, Left, X4, tree_member_in_ga(X, Left)) tree_member_in_ga(X, tree(X5, X6, Right)) -> U2_ga(X, X5, X6, Right, tree_member_in_ga(X, Right)) U2_ga(X, X5, X6, Right, tree_member_out_ga(X, Right)) -> tree_member_out_ga(X, tree(X5, X6, Right)) U1_ga(X, X3, Left, X4, tree_member_out_ga(X, Left)) -> tree_member_out_ga(X, tree(X3, Left, X4)) The argument filtering Pi contains the following mapping: tree_member_in_ga(x1, x2) = tree_member_in_ga(x1) tree_member_out_ga(x1, x2) = tree_member_out_ga(x1) U1_ga(x1, x2, x3, x4, x5) = U1_ga(x1, x5) U2_ga(x1, x2, x3, x4, x5) = U2_ga(x1, x5) TREE_MEMBER_IN_GA(x1, x2) = TREE_MEMBER_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (18) Obligation: Pi DP problem: The TRS P consists of the following rules: TREE_MEMBER_IN_GA(X, tree(X5, X6, Right)) -> TREE_MEMBER_IN_GA(X, Right) TREE_MEMBER_IN_GA(X, tree(X3, Left, X4)) -> TREE_MEMBER_IN_GA(X, Left) R is empty. The argument filtering Pi contains the following mapping: TREE_MEMBER_IN_GA(x1, x2) = TREE_MEMBER_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (19) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: TREE_MEMBER_IN_GA(X) -> TREE_MEMBER_IN_GA(X) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 4, "program": { "directives": [], "clauses": [ [ "(tree_member X (tree X X1 X2))", null ], [ "(tree_member X (tree X3 Left X4))", "(tree_member X Left)" ], [ "(tree_member X (tree X5 X6 Right))", "(tree_member X Right)" ] ] }, "graph": { "nodes": { "type": "Nodes", "130": { "goal": [{ "clause": 2, "scope": 1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "120": { "goal": [ { "clause": 1, "scope": 1, "term": "(tree_member T1 T2)" }, { "clause": 2, "scope": 1, "term": "(tree_member T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "133": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "134": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "145": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T53 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T53"], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "146": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "125": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "126": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "118": { "goal": [ { "clause": 0, "scope": 1, "term": "(tree_member T1 T2)" }, { "clause": 1, "scope": 1, "term": "(tree_member T1 T2)" }, { "clause": 2, "scope": 1, "term": "(tree_member T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "129": { "goal": [{ "clause": 1, "scope": 1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "119": { "goal": [{ "clause": 0, "scope": 1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 4, "to": 118, "label": "CASE" }, { "from": 118, "to": 119, "label": "PARALLEL" }, { "from": 118, "to": 120, "label": "PARALLEL" }, { "from": 119, "to": 124, "label": "EVAL with clause\ntree_member(X19, tree(X19, X20, X21)).\nand substitutionT1 -> T15,\nX19 -> T15,\nX20 -> T16,\nX21 -> T17,\nT2 -> tree(T15, T16, T17)" }, { "from": 119, "to": 125, "label": "EVAL-BACKTRACK" }, { "from": 120, "to": 129, "label": "PARALLEL" }, { "from": 120, "to": 130, "label": "PARALLEL" }, { "from": 124, "to": 126, "label": "SUCCESS" }, { "from": 129, "to": 133, "label": "EVAL with clause\ntree_member(X38, tree(X39, X40, X41)) :- tree_member(X38, X40).\nand substitutionT1 -> T34,\nX38 -> T34,\nX39 -> T35,\nX40 -> T38,\nX41 -> T37,\nT2 -> tree(T35, T38, T37),\nT36 -> T38" }, { "from": 129, "to": 134, "label": "EVAL-BACKTRACK" }, { "from": 130, "to": 145, "label": "EVAL with clause\ntree_member(X56, tree(X57, X58, X59)) :- tree_member(X56, X59).\nand substitutionT1 -> T53,\nX56 -> T53,\nX57 -> T54,\nX58 -> T55,\nX59 -> T57,\nT2 -> tree(T54, T55, T57),\nT56 -> T57" }, { "from": 130, "to": 146, "label": "EVAL-BACKTRACK" }, { "from": 133, "to": 4, "label": "INSTANCE with matching:\nT1 -> T34\nT2 -> T38" }, { "from": 145, "to": 4, "label": "INSTANCE with matching:\nT1 -> T53\nT2 -> T57" } ], "type": "Graph" } } ---------------------------------------- (22) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f4_in(T15) -> f4_out1 f4_in(T34) -> U1(f4_in(T34), T34) U1(f4_out1, T34) -> f4_out1 f4_in(T53) -> U2(f4_in(T53), T53) U2(f4_out1, T53) -> f4_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: F4_IN(T34) -> U1^1(f4_in(T34), T34) F4_IN(T34) -> F4_IN(T34) F4_IN(T53) -> U2^1(f4_in(T53), T53) The TRS R consists of the following rules: f4_in(T15) -> f4_out1 f4_in(T34) -> U1(f4_in(T34), T34) U1(f4_out1, T34) -> f4_out1 f4_in(T53) -> U2(f4_in(T53), T53) U2(f4_out1, T53) -> f4_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: F4_IN(T34) -> F4_IN(T34) The TRS R consists of the following rules: f4_in(T15) -> f4_out1 f4_in(T34) -> U1(f4_in(T34), T34) U1(f4_out1, T34) -> f4_out1 f4_in(T53) -> U2(f4_in(T53), T53) U2(f4_out1, T53) -> f4_out1 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: F4_IN(T34) -> F4_IN(T34) The TRS R consists of the following rules: f4_in(T15) -> f4_out1 f4_in(T34) -> U1(f4_in(T34), T34) U1(f4_out1, T34) -> f4_out1 f4_in(T53) -> U2(f4_in(T53), T53) U2(f4_out1, T53) -> f4_out1 The set Q consists of the following terms: f4_in(x0) U1(f4_out1, x0) U2(f4_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) 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. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: F4_IN(T34) -> F4_IN(T34) R is empty. The set Q consists of the following terms: f4_in(x0) U1(f4_out1, x0) U2(f4_out1, x0) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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]. f4_in(x0) U1(f4_out1, x0) U2(f4_out1, x0) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: F4_IN(T34) -> F4_IN(T34) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 15, "program": { "directives": [], "clauses": [ [ "(tree_member X (tree X X1 X2))", null ], [ "(tree_member X (tree X3 Left X4))", "(tree_member X Left)" ], [ "(tree_member X (tree X5 X6 Right))", "(tree_member X Right)" ] ] }, "graph": { "nodes": { "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "type": "Nodes", "131": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T34 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T34"], "free": [], "exprvars": [] } }, "121": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "132": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "111": { "goal": [ { "clause": 0, "scope": 1, "term": "(tree_member T1 T2)" }, { "clause": 1, "scope": 1, "term": "(tree_member T1 T2)" }, { "clause": 2, "scope": 1, "term": "(tree_member T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "122": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "123": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "147": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T53 T57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T53"], "free": [], "exprvars": [] } }, "148": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "116": { "goal": [{ "clause": 0, "scope": 1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "127": { "goal": [{ "clause": 1, "scope": 1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "117": { "goal": [ { "clause": 1, "scope": 1, "term": "(tree_member T1 T2)" }, { "clause": 2, "scope": 1, "term": "(tree_member T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "128": { "goal": [{ "clause": 2, "scope": 1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 15, "to": 111, "label": "CASE" }, { "from": 111, "to": 116, "label": "PARALLEL" }, { "from": 111, "to": 117, "label": "PARALLEL" }, { "from": 116, "to": 121, "label": "EVAL with clause\ntree_member(X19, tree(X19, X20, X21)).\nand substitutionT1 -> T15,\nX19 -> T15,\nX20 -> T16,\nX21 -> T17,\nT2 -> tree(T15, T16, T17)" }, { "from": 116, "to": 122, "label": "EVAL-BACKTRACK" }, { "from": 117, "to": 127, "label": "PARALLEL" }, { "from": 117, "to": 128, "label": "PARALLEL" }, { "from": 121, "to": 123, "label": "SUCCESS" }, { "from": 127, "to": 131, "label": "EVAL with clause\ntree_member(X38, tree(X39, X40, X41)) :- tree_member(X38, X40).\nand substitutionT1 -> T34,\nX38 -> T34,\nX39 -> T35,\nX40 -> T38,\nX41 -> T37,\nT2 -> tree(T35, T38, T37),\nT36 -> T38" }, { "from": 127, "to": 132, "label": "EVAL-BACKTRACK" }, { "from": 128, "to": 147, "label": "EVAL with clause\ntree_member(X56, tree(X57, X58, X59)) :- tree_member(X56, X59).\nand substitutionT1 -> T53,\nX56 -> T53,\nX57 -> T54,\nX58 -> T55,\nX59 -> T57,\nT2 -> tree(T54, T55, T57),\nT56 -> T57" }, { "from": 128, "to": 148, "label": "EVAL-BACKTRACK" }, { "from": 131, "to": 15, "label": "INSTANCE with matching:\nT1 -> T34\nT2 -> T38" }, { "from": 147, "to": 15, "label": "INSTANCE with matching:\nT1 -> T53\nT2 -> T57" } ], "type": "Graph" } } ---------------------------------------- (34) Obligation: Rules: f111_in(T1) -> f117_in(T1) :|: TRUE f111_in(x) -> f116_in(x) :|: TRUE f117_out(x1) -> f111_out(x1) :|: TRUE f116_out(x2) -> f111_out(x2) :|: TRUE f15_out(T34) -> f131_out(T34) :|: TRUE f131_in(x3) -> f15_in(x3) :|: TRUE f147_out(T53) -> f128_out(T53) :|: TRUE f128_in(x4) -> f147_in(x4) :|: TRUE f148_out -> f128_out(x5) :|: TRUE f128_in(x6) -> f148_in :|: TRUE f127_in(x7) -> f132_in :|: TRUE f131_out(x8) -> f127_out(x8) :|: TRUE f127_in(x9) -> f131_in(x9) :|: TRUE f132_out -> f127_out(x10) :|: TRUE f117_in(x11) -> f127_in(x11) :|: TRUE f117_in(x12) -> f128_in(x12) :|: TRUE f128_out(x13) -> f117_out(x13) :|: TRUE f127_out(x14) -> f117_out(x14) :|: TRUE f15_out(x15) -> f147_out(x15) :|: TRUE f147_in(x16) -> f15_in(x16) :|: TRUE f15_in(x17) -> f111_in(x17) :|: TRUE f111_out(x18) -> f15_out(x18) :|: TRUE Start term: f15_in(T1) ---------------------------------------- (35) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f111_in(T1) -> f117_in(T1) :|: TRUE f131_in(x3) -> f15_in(x3) :|: TRUE f128_in(x4) -> f147_in(x4) :|: TRUE f127_in(x9) -> f131_in(x9) :|: TRUE f117_in(x11) -> f127_in(x11) :|: TRUE f117_in(x12) -> f128_in(x12) :|: TRUE f147_in(x16) -> f15_in(x16) :|: TRUE f15_in(x17) -> f111_in(x17) :|: TRUE ---------------------------------------- (36) Obligation: Rules: f111_in(T1) -> f117_in(T1) :|: TRUE f131_in(x3) -> f15_in(x3) :|: TRUE f128_in(x4) -> f147_in(x4) :|: TRUE f127_in(x9) -> f131_in(x9) :|: TRUE f117_in(x11) -> f127_in(x11) :|: TRUE f117_in(x12) -> f128_in(x12) :|: TRUE f147_in(x16) -> f15_in(x16) :|: TRUE f15_in(x17) -> f111_in(x17) :|: TRUE ---------------------------------------- (37) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (38) Obligation: Rules: f111_in(T1:0) -> f111_in(T1:0) :|: TRUE ---------------------------------------- (39) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (40) Obligation: Rules: f111_in(T1:0) -> f111_in(T1:0) :|: TRUE ---------------------------------------- (41) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f111_in(T1:0) -> f111_in(T1:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (42) Obligation: Termination digraph: Nodes: (1) f111_in(T1:0) -> f111_in(T1:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (43) FilterProof (EQUIVALENT) Used the following sort dictionary for filtering: f111_in(VARIABLE) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (44) Obligation: Rules: f111_in(T1:0) -> f111_in(T1:0) :|: TRUE ---------------------------------------- (45) IntTRSPeriodicNontermProof (COMPLETE) Normalized system to the following form: f(pc, T1:0) -> f(1, T1:0) :|: pc = 1 && TRUE Witness term starting non-terminating reduction: f(1, -8) ---------------------------------------- (46) NO ---------------------------------------- (47) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 3, "program": { "directives": [], "clauses": [ [ "(tree_member X (tree X X1 X2))", null ], [ "(tree_member X (tree X3 Left X4))", "(tree_member X Left)" ], [ "(tree_member X (tree X5 X6 Right))", "(tree_member X Right)" ] ] }, "graph": { "nodes": { "type": "Nodes", "150": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(tree_member T13 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "194": { "goal": [{ "clause": 2, "scope": 1, "term": "(tree_member T180 T2)" }], "kb": { "nonunifying": [[ "(tree_member T180 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T180"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "151": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T76 T80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T76"], "free": [], "exprvars": [] } }, "195": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T262 T266)" }], "kb": { "nonunifying": [[ "(tree_member T262 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T262"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "152": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "196": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "153": { "goal": [{ "clause": 2, "scope": 1, "term": "(tree_member T13 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "197": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T277 T281)" }], "kb": { "nonunifying": [[ "(tree_member T277 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T277"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "154": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T95 T99)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T95"], "free": [], "exprvars": [] } }, "198": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "155": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "199": { "goal": [ { "clause": 0, "scope": 5, "term": "(tree_member T277 T281)" }, { "clause": 1, "scope": 5, "term": "(tree_member T277 T281)" }, { "clause": 2, "scope": 5, "term": "(tree_member T277 T281)" } ], "kb": { "nonunifying": [[ "(tree_member T277 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T277"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "156": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T110 T114)" }], "kb": { "nonunifying": [[ "(tree_member T110 T2)", "(tree_member X17 (tree X18 X19 X20))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T110"], "free": [ "X17", "X18", "X19", "X20" ], "exprvars": [] } }, "157": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "158": { "goal": [ { "clause": 0, "scope": 3, "term": "(tree_member T110 T114)" }, { "clause": 1, "scope": 3, "term": "(tree_member T110 T114)" }, { "clause": 2, "scope": 3, "term": "(tree_member T110 T114)" } ], "kb": { "nonunifying": [[ "(tree_member T110 T2)", "(tree_member X17 (tree X18 X19 X20))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T110"], "free": [ "X17", "X18", "X19", "X20" ], "exprvars": [] } }, "159": { "goal": [{ "clause": 0, "scope": 3, "term": "(tree_member T110 T114)" }], "kb": { "nonunifying": [[ "(tree_member T110 T2)", "(tree_member X17 (tree X18 X19 X20))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T110"], "free": [ "X17", "X18", "X19", "X20" ], "exprvars": [] } }, "56": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(tree_member T6 T2)" }, { "clause": 2, "scope": 1, "term": "(tree_member T6 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "57": { "goal": [ { "clause": 1, "scope": 1, "term": "(tree_member T1 T2)" }, { "clause": 2, "scope": 1, "term": "(tree_member T1 T2)" } ], "kb": { "nonunifying": [[ "(tree_member T1 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "58": { "goal": [ { "clause": 1, "scope": 1, "term": "(tree_member T6 T2)" }, { "clause": 2, "scope": 1, "term": "(tree_member T6 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "16": { "goal": [ { "clause": 0, "scope": 1, "term": "(tree_member T1 T2)" }, { "clause": 1, "scope": 1, "term": "(tree_member T1 T2)" }, { "clause": 2, "scope": 1, "term": "(tree_member T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "160": { "goal": [ { "clause": 1, "scope": 3, "term": "(tree_member T110 T114)" }, { "clause": 2, "scope": 3, "term": "(tree_member T110 T114)" } ], "kb": { "nonunifying": [[ "(tree_member T110 T2)", "(tree_member X17 (tree X18 X19 X20))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T110"], "free": [ "X17", "X18", "X19", "X20" ], "exprvars": [] } }, "161": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "162": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "163": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "164": { "goal": [{ "clause": 1, "scope": 3, "term": "(tree_member T110 T114)" }], "kb": { "nonunifying": [[ "(tree_member T110 T2)", "(tree_member X17 (tree X18 X19 X20))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T110"], "free": [ "X17", "X18", "X19", "X20" ], "exprvars": [] } }, "165": { "goal": [{ "clause": 2, "scope": 3, "term": "(tree_member T110 T114)" }], "kb": { "nonunifying": [[ "(tree_member T110 T2)", "(tree_member X17 (tree X18 X19 X20))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T110"], "free": [ "X17", "X18", "X19", "X20" ], "exprvars": [] } }, "166": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T146 T150)" }], "kb": { "nonunifying": [[ "(tree_member T146 T2)", "(tree_member X17 (tree X18 X19 X20))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T146"], "free": [ "X17", "X18", "X19", "X20" ], "exprvars": [] } }, "167": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "200": { "goal": [{ "clause": 0, "scope": 5, "term": "(tree_member T277 T281)" }], "kb": { "nonunifying": [[ "(tree_member T277 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T277"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "168": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T165 T169)" }], "kb": { "nonunifying": [[ "(tree_member T165 T2)", "(tree_member X17 (tree X18 X19 X20))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T165"], "free": [ "X17", "X18", "X19", "X20" ], "exprvars": [] } }, "201": { "goal": [ { "clause": 1, "scope": 5, "term": "(tree_member T277 T281)" }, { "clause": 2, "scope": 5, "term": "(tree_member T277 T281)" } ], "kb": { "nonunifying": [[ "(tree_member T277 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T277"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "169": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "202": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "203": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "204": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "205": { "goal": [{ "clause": 1, "scope": 5, "term": "(tree_member T277 T281)" }], "kb": { "nonunifying": [[ "(tree_member T277 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T277"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "206": { "goal": [{ "clause": 2, "scope": 5, "term": "(tree_member T277 T281)" }], "kb": { "nonunifying": [[ "(tree_member T277 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T277"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "207": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T313 T317)" }], "kb": { "nonunifying": [[ "(tree_member T313 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T313"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "60": { "goal": [ { "clause": -1, "scope": -1, "term": "(tree_member T13 T17)" }, { "clause": 2, "scope": 1, "term": "(tree_member T13 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "208": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "61": { "goal": [{ "clause": 2, "scope": 1, "term": "(tree_member T6 T2)" }], "kb": { "nonunifying": [[ "(tree_member T6 T2)", "(tree_member X17 (tree X18 X19 X20))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X17", "X18", "X19", "X20" ], "exprvars": [] } }, "209": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T332 T336)" }], "kb": { "nonunifying": [[ "(tree_member T332 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T332"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "170": { "goal": [ { "clause": -1, "scope": -1, "term": "(tree_member T180 T184)" }, { "clause": 2, "scope": 1, "term": "(tree_member T180 T2)" } ], "kb": { "nonunifying": [[ "(tree_member T180 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T180"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "171": { "goal": [{ "clause": 2, "scope": 1, "term": "(tree_member T1 T2)" }], "kb": { "nonunifying": [[ "(tree_member T1 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "172": { "goal": [ { "clause": 0, "scope": 4, "term": "(tree_member T180 T184)" }, { "clause": 1, "scope": 4, "term": "(tree_member T180 T184)" }, { "clause": 2, "scope": 4, "term": "(tree_member T180 T184)" }, { "clause": -1, "scope": 4, "term": null }, { "clause": 2, "scope": 1, "term": "(tree_member T180 T2)" } ], "kb": { "nonunifying": [[ "(tree_member T180 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T180"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "173": { "goal": [{ "clause": 0, "scope": 4, "term": "(tree_member T180 T184)" }], "kb": { "nonunifying": [[ "(tree_member T180 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T180"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "174": { "goal": [ { "clause": 1, "scope": 4, "term": "(tree_member T180 T184)" }, { "clause": 2, "scope": 4, "term": "(tree_member T180 T184)" }, { "clause": -1, "scope": 4, "term": null }, { "clause": 2, "scope": 1, "term": "(tree_member T180 T2)" } ], "kb": { "nonunifying": [[ "(tree_member T180 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T180"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "175": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "176": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "177": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "210": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "178": { "goal": [{ "clause": 1, "scope": 4, "term": "(tree_member T180 T184)" }], "kb": { "nonunifying": [[ "(tree_member T180 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T180"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "135": { "goal": [ { "clause": 0, "scope": 2, "term": "(tree_member T13 T17)" }, { "clause": 1, "scope": 2, "term": "(tree_member T13 T17)" }, { "clause": 2, "scope": 2, "term": "(tree_member T13 T17)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(tree_member T13 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "179": { "goal": [ { "clause": 2, "scope": 4, "term": "(tree_member T180 T184)" }, { "clause": -1, "scope": 4, "term": null }, { "clause": 2, "scope": 1, "term": "(tree_member T180 T2)" } ], "kb": { "nonunifying": [[ "(tree_member T180 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T180"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "136": { "goal": [{ "clause": 0, "scope": 2, "term": "(tree_member T13 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "137": { "goal": [ { "clause": 1, "scope": 2, "term": "(tree_member T13 T17)" }, { "clause": 2, "scope": 2, "term": "(tree_member T13 T17)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(tree_member T13 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "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": [] } }, "180": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T216 T220)" }], "kb": { "nonunifying": [[ "(tree_member T216 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T216"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "181": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "182": { "goal": [{ "clause": 2, "scope": 4, "term": "(tree_member T180 T184)" }], "kb": { "nonunifying": [[ "(tree_member T180 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T180"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "183": { "goal": [ { "clause": -1, "scope": 4, "term": null }, { "clause": 2, "scope": 1, "term": "(tree_member T180 T2)" } ], "kb": { "nonunifying": [[ "(tree_member T180 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T180"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "140": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "184": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T243 T247)" }], "kb": { "nonunifying": [[ "(tree_member T243 T2)", "(tree_member X10 (tree X10 X11 X12))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T243"], "free": [ "X10", "X11", "X12" ], "exprvars": [] } }, "141": { "goal": [{ "clause": 1, "scope": 2, "term": "(tree_member T13 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "185": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "142": { "goal": [ { "clause": 2, "scope": 2, "term": "(tree_member T13 T17)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 2, "scope": 1, "term": "(tree_member T13 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "143": { "goal": [{ "clause": -1, "scope": -1, "term": "(tree_member T49 T53)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T49"], "free": [], "exprvars": [] } }, "144": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "149": { "goal": [{ "clause": 2, "scope": 2, "term": "(tree_member T13 T17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 16, "label": "CASE" }, { "from": 16, "to": 56, "label": "EVAL with clause\ntree_member(X10, tree(X10, X11, X12)).\nand substitutionT1 -> T6,\nX10 -> T6,\nX11 -> T7,\nX12 -> T8,\nT2 -> tree(T6, T7, T8)" }, { "from": 16, "to": 57, "label": "EVAL-BACKTRACK" }, { "from": 56, "to": 58, "label": "SUCCESS" }, { "from": 57, "to": 170, "label": "EVAL with clause\ntree_member(X177, tree(X178, X179, X180)) :- tree_member(X177, X179).\nand substitutionT1 -> T180,\nX177 -> T180,\nX178 -> T181,\nX179 -> T184,\nX180 -> T183,\nT2 -> tree(T181, T184, T183),\nT182 -> T184" }, { "from": 57, "to": 171, "label": "EVAL-BACKTRACK" }, { "from": 58, "to": 60, "label": "EVAL with clause\ntree_member(X17, tree(X18, X19, X20)) :- tree_member(X17, X19).\nand substitutionT6 -> T13,\nX17 -> T13,\nX18 -> T14,\nX19 -> T17,\nX20 -> T16,\nT2 -> tree(T14, T17, T16),\nT15 -> T17" }, { "from": 58, "to": 61, "label": "EVAL-BACKTRACK" }, { "from": 60, "to": 135, "label": "CASE" }, { "from": 61, "to": 156, "label": "EVAL with clause\ntree_member(X110, tree(X111, X112, X113)) :- tree_member(X110, X113).\nand substitutionT6 -> T110,\nX110 -> T110,\nX111 -> T111,\nX112 -> T112,\nX113 -> T114,\nT2 -> tree(T111, T112, T114),\nT113 -> T114" }, { "from": 61, "to": 157, "label": "EVAL-BACKTRACK" }, { "from": 135, "to": 136, "label": "PARALLEL" }, { "from": 135, "to": 137, "label": "PARALLEL" }, { "from": 136, "to": 138, "label": "EVAL with clause\ntree_member(X33, tree(X33, X34, X35)).\nand substitutionT13 -> T30,\nX33 -> T30,\nX34 -> T31,\nX35 -> T32,\nT17 -> tree(T30, T31, T32)" }, { "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\ntree_member(X52, tree(X53, X54, X55)) :- tree_member(X52, X54).\nand substitutionT13 -> T49,\nX52 -> T49,\nX53 -> T50,\nX54 -> T53,\nX55 -> T52,\nT17 -> tree(T50, T53, T52),\nT51 -> T53" }, { "from": 141, "to": 144, "label": "EVAL-BACKTRACK" }, { "from": 142, "to": 149, "label": "PARALLEL" }, { "from": 142, "to": 150, "label": "PARALLEL" }, { "from": 143, "to": 3, "label": "INSTANCE with matching:\nT1 -> T49\nT2 -> T53" }, { "from": 149, "to": 151, "label": "EVAL with clause\ntree_member(X78, tree(X79, X80, X81)) :- tree_member(X78, X81).\nand substitutionT13 -> T76,\nX78 -> T76,\nX79 -> T77,\nX80 -> T78,\nX81 -> T80,\nT17 -> tree(T77, T78, T80),\nT79 -> T80" }, { "from": 149, "to": 152, "label": "EVAL-BACKTRACK" }, { "from": 150, "to": 153, "label": "FAILURE" }, { "from": 151, "to": 3, "label": "INSTANCE with matching:\nT1 -> T76\nT2 -> T80" }, { "from": 153, "to": 154, "label": "EVAL with clause\ntree_member(X96, tree(X97, X98, X99)) :- tree_member(X96, X99).\nand substitutionT13 -> T95,\nX96 -> T95,\nX97 -> T96,\nX98 -> T97,\nX99 -> T99,\nT2 -> tree(T96, T97, T99),\nT98 -> T99" }, { "from": 153, "to": 155, "label": "EVAL-BACKTRACK" }, { "from": 154, "to": 3, "label": "INSTANCE with matching:\nT1 -> T95\nT2 -> T99" }, { "from": 156, "to": 158, "label": "CASE" }, { "from": 158, "to": 159, "label": "PARALLEL" }, { "from": 158, "to": 160, "label": "PARALLEL" }, { "from": 159, "to": 161, "label": "EVAL with clause\ntree_member(X126, tree(X126, X127, X128)).\nand substitutionT110 -> T127,\nX126 -> T127,\nX127 -> T128,\nX128 -> T129,\nT114 -> tree(T127, T128, T129)" }, { "from": 159, "to": 162, "label": "EVAL-BACKTRACK" }, { "from": 160, "to": 164, "label": "PARALLEL" }, { "from": 160, "to": 165, "label": "PARALLEL" }, { "from": 161, "to": 163, "label": "SUCCESS" }, { "from": 164, "to": 166, "label": "EVAL with clause\ntree_member(X145, tree(X146, X147, X148)) :- tree_member(X145, X147).\nand substitutionT110 -> T146,\nX145 -> T146,\nX146 -> T147,\nX147 -> T150,\nX148 -> T149,\nT114 -> tree(T147, T150, T149),\nT148 -> T150" }, { "from": 164, "to": 167, "label": "EVAL-BACKTRACK" }, { "from": 165, "to": 168, "label": "EVAL with clause\ntree_member(X163, tree(X164, X165, X166)) :- tree_member(X163, X166).\nand substitutionT110 -> T165,\nX163 -> T165,\nX164 -> T166,\nX165 -> T167,\nX166 -> T169,\nT114 -> tree(T166, T167, T169),\nT168 -> T169" }, { "from": 165, "to": 169, "label": "EVAL-BACKTRACK" }, { "from": 166, "to": 3, "label": "INSTANCE with matching:\nT1 -> T146\nT2 -> T150" }, { "from": 168, "to": 3, "label": "INSTANCE with matching:\nT1 -> T165\nT2 -> T169" }, { "from": 170, "to": 172, "label": "CASE" }, { "from": 171, "to": 197, "label": "EVAL with clause\ntree_member(X270, tree(X271, X272, X273)) :- tree_member(X270, X273).\nand substitutionT1 -> T277,\nX270 -> T277,\nX271 -> T278,\nX272 -> T279,\nX273 -> T281,\nT2 -> tree(T278, T279, T281),\nT280 -> T281" }, { "from": 171, "to": 198, "label": "EVAL-BACKTRACK" }, { "from": 172, "to": 173, "label": "PARALLEL" }, { "from": 172, "to": 174, "label": "PARALLEL" }, { "from": 173, "to": 175, "label": "EVAL with clause\ntree_member(X193, tree(X193, X194, X195)).\nand substitutionT180 -> T197,\nX193 -> T197,\nX194 -> T198,\nX195 -> T199,\nT184 -> tree(T197, T198, T199)" }, { "from": 173, "to": 176, "label": "EVAL-BACKTRACK" }, { "from": 174, "to": 178, "label": "PARALLEL" }, { "from": 174, "to": 179, "label": "PARALLEL" }, { "from": 175, "to": 177, "label": "SUCCESS" }, { "from": 178, "to": 180, "label": "EVAL with clause\ntree_member(X212, tree(X213, X214, X215)) :- tree_member(X212, X214).\nand substitutionT180 -> T216,\nX212 -> T216,\nX213 -> T217,\nX214 -> T220,\nX215 -> T219,\nT184 -> tree(T217, T220, T219),\nT218 -> T220" }, { "from": 178, "to": 181, "label": "EVAL-BACKTRACK" }, { "from": 179, "to": 182, "label": "PARALLEL" }, { "from": 179, "to": 183, "label": "PARALLEL" }, { "from": 180, "to": 3, "label": "INSTANCE with matching:\nT1 -> T216\nT2 -> T220" }, { "from": 182, "to": 184, "label": "EVAL with clause\ntree_member(X238, tree(X239, X240, X241)) :- tree_member(X238, X241).\nand substitutionT180 -> T243,\nX238 -> T243,\nX239 -> T244,\nX240 -> T245,\nX241 -> T247,\nT184 -> tree(T244, T245, T247),\nT246 -> T247" }, { "from": 182, "to": 185, "label": "EVAL-BACKTRACK" }, { "from": 183, "to": 194, "label": "FAILURE" }, { "from": 184, "to": 3, "label": "INSTANCE with matching:\nT1 -> T243\nT2 -> T247" }, { "from": 194, "to": 195, "label": "EVAL with clause\ntree_member(X256, tree(X257, X258, X259)) :- tree_member(X256, X259).\nand substitutionT180 -> T262,\nX256 -> T262,\nX257 -> T263,\nX258 -> T264,\nX259 -> T266,\nT2 -> tree(T263, T264, T266),\nT265 -> T266" }, { "from": 194, "to": 196, "label": "EVAL-BACKTRACK" }, { "from": 195, "to": 3, "label": "INSTANCE with matching:\nT1 -> T262\nT2 -> T266" }, { "from": 197, "to": 199, "label": "CASE" }, { "from": 199, "to": 200, "label": "PARALLEL" }, { "from": 199, "to": 201, "label": "PARALLEL" }, { "from": 200, "to": 202, "label": "EVAL with clause\ntree_member(X286, tree(X286, X287, X288)).\nand substitutionT277 -> T294,\nX286 -> T294,\nX287 -> T295,\nX288 -> T296,\nT281 -> tree(T294, T295, T296)" }, { "from": 200, "to": 203, "label": "EVAL-BACKTRACK" }, { "from": 201, "to": 205, "label": "PARALLEL" }, { "from": 201, "to": 206, "label": "PARALLEL" }, { "from": 202, "to": 204, "label": "SUCCESS" }, { "from": 205, "to": 207, "label": "EVAL with clause\ntree_member(X305, tree(X306, X307, X308)) :- tree_member(X305, X307).\nand substitutionT277 -> T313,\nX305 -> T313,\nX306 -> T314,\nX307 -> T317,\nX308 -> T316,\nT281 -> tree(T314, T317, T316),\nT315 -> T317" }, { "from": 205, "to": 208, "label": "EVAL-BACKTRACK" }, { "from": 206, "to": 209, "label": "EVAL with clause\ntree_member(X323, tree(X324, X325, X326)) :- tree_member(X323, X326).\nand substitutionT277 -> T332,\nX323 -> T332,\nX324 -> T333,\nX325 -> T334,\nX326 -> T336,\nT281 -> tree(T333, T334, T336),\nT335 -> T336" }, { "from": 206, "to": 210, "label": "EVAL-BACKTRACK" }, { "from": 207, "to": 3, "label": "INSTANCE with matching:\nT1 -> T313\nT2 -> T317" }, { "from": 209, "to": 3, "label": "INSTANCE with matching:\nT1 -> T332\nT2 -> T336" } ], "type": "Graph" } } ---------------------------------------- (48) Obligation: Triples: tree_memberA(X1, tree(X2, tree(X3, X4, X5), X6)) :- tree_memberA(X1, X4). tree_memberA(X1, tree(X2, tree(X3, X4, X5), X6)) :- tree_memberA(X1, X5). tree_memberA(X1, tree(X2, X3, X4)) :- tree_memberA(X1, X4). tree_memberA(X1, tree(X2, X3, tree(X4, X5, X6))) :- tree_memberA(X1, X5). tree_memberA(X1, tree(X2, X3, tree(X4, X5, X6))) :- tree_memberA(X1, X6). tree_memberA(X1, tree(X2, tree(X3, X4, X5), X6)) :- tree_memberA(X1, X4). tree_memberA(X1, tree(X2, tree(X3, X4, X5), X6)) :- tree_memberA(X1, X5). tree_memberA(X1, tree(X2, X3, X4)) :- tree_memberA(X1, X4). tree_memberA(X1, tree(X2, X3, tree(X4, X5, X6))) :- tree_memberA(X1, X5). tree_memberA(X1, tree(X2, X3, tree(X4, X5, X6))) :- tree_memberA(X1, X6). Clauses: tree_membercA(X1, tree(X1, X2, X3)). tree_membercA(X1, tree(X2, tree(X1, X3, X4), X5)). tree_membercA(X1, tree(X2, tree(X3, X4, X5), X6)) :- tree_membercA(X1, X4). tree_membercA(X1, tree(X2, tree(X3, X4, X5), X6)) :- tree_membercA(X1, X5). tree_membercA(X1, tree(X2, X3, X4)) :- tree_membercA(X1, X4). tree_membercA(X1, tree(X2, X3, tree(X1, X4, X5))). tree_membercA(X1, tree(X2, X3, tree(X4, X5, X6))) :- tree_membercA(X1, X5). tree_membercA(X1, tree(X2, X3, tree(X4, X5, X6))) :- tree_membercA(X1, X6). tree_membercA(X1, tree(X2, tree(X1, X3, X4), X5)). tree_membercA(X1, tree(X2, tree(X3, X4, X5), X6)) :- tree_membercA(X1, X4). tree_membercA(X1, tree(X2, tree(X3, X4, X5), X6)) :- tree_membercA(X1, X5). tree_membercA(X1, tree(X2, X3, X4)) :- tree_membercA(X1, X4). tree_membercA(X1, tree(X2, X3, tree(X1, X4, X5))). tree_membercA(X1, tree(X2, X3, tree(X4, X5, X6))) :- tree_membercA(X1, X5). tree_membercA(X1, tree(X2, X3, tree(X4, X5, X6))) :- tree_membercA(X1, X6). Afs: tree_memberA(x1, x2) = tree_memberA(x1) ---------------------------------------- (49) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: tree_memberA_in_2: (b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> U1_GA(X1, X2, X3, X4, X5, X6, tree_memberA_in_ga(X1, X4)) TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> TREE_MEMBERA_IN_GA(X1, X4) TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> U2_GA(X1, X2, X3, X4, X5, X6, tree_memberA_in_ga(X1, X5)) TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> TREE_MEMBERA_IN_GA(X1, X5) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, X4)) -> U3_GA(X1, X2, X3, X4, tree_memberA_in_ga(X1, X4)) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, X4)) -> TREE_MEMBERA_IN_GA(X1, X4) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> U4_GA(X1, X2, X3, X4, X5, X6, tree_memberA_in_ga(X1, X5)) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> TREE_MEMBERA_IN_GA(X1, X5) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> U5_GA(X1, X2, X3, X4, X5, X6, tree_memberA_in_ga(X1, X6)) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> TREE_MEMBERA_IN_GA(X1, X6) R is empty. The argument filtering Pi contains the following mapping: tree_memberA_in_ga(x1, x2) = tree_memberA_in_ga(x1) TREE_MEMBERA_IN_GA(x1, x2) = TREE_MEMBERA_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5, x6, x7) = U1_GA(x1, x7) U2_GA(x1, x2, x3, x4, x5, x6, x7) = U2_GA(x1, x7) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) U4_GA(x1, x2, x3, x4, x5, x6, x7) = U4_GA(x1, x7) U5_GA(x1, x2, x3, x4, x5, x6, x7) = U5_GA(x1, x7) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (50) Obligation: Pi DP problem: The TRS P consists of the following rules: TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> U1_GA(X1, X2, X3, X4, X5, X6, tree_memberA_in_ga(X1, X4)) TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> TREE_MEMBERA_IN_GA(X1, X4) TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> U2_GA(X1, X2, X3, X4, X5, X6, tree_memberA_in_ga(X1, X5)) TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> TREE_MEMBERA_IN_GA(X1, X5) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, X4)) -> U3_GA(X1, X2, X3, X4, tree_memberA_in_ga(X1, X4)) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, X4)) -> TREE_MEMBERA_IN_GA(X1, X4) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> U4_GA(X1, X2, X3, X4, X5, X6, tree_memberA_in_ga(X1, X5)) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> TREE_MEMBERA_IN_GA(X1, X5) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> U5_GA(X1, X2, X3, X4, X5, X6, tree_memberA_in_ga(X1, X6)) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> TREE_MEMBERA_IN_GA(X1, X6) R is empty. The argument filtering Pi contains the following mapping: tree_memberA_in_ga(x1, x2) = tree_memberA_in_ga(x1) TREE_MEMBERA_IN_GA(x1, x2) = TREE_MEMBERA_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5, x6, x7) = U1_GA(x1, x7) U2_GA(x1, x2, x3, x4, x5, x6, x7) = U2_GA(x1, x7) U3_GA(x1, x2, x3, x4, x5) = U3_GA(x1, x5) U4_GA(x1, x2, x3, x4, x5, x6, x7) = U4_GA(x1, x7) U5_GA(x1, x2, x3, x4, x5, x6, x7) = U5_GA(x1, x7) We have to consider all (P,R,Pi)-chains ---------------------------------------- (51) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 5 less nodes. ---------------------------------------- (52) Obligation: Pi DP problem: The TRS P consists of the following rules: TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> TREE_MEMBERA_IN_GA(X1, X5) TREE_MEMBERA_IN_GA(X1, tree(X2, tree(X3, X4, X5), X6)) -> TREE_MEMBERA_IN_GA(X1, X4) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, X4)) -> TREE_MEMBERA_IN_GA(X1, X4) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> TREE_MEMBERA_IN_GA(X1, X5) TREE_MEMBERA_IN_GA(X1, tree(X2, X3, tree(X4, X5, X6))) -> TREE_MEMBERA_IN_GA(X1, X6) R is empty. The argument filtering Pi contains the following mapping: TREE_MEMBERA_IN_GA(x1, x2) = TREE_MEMBERA_IN_GA(x1) 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: TREE_MEMBERA_IN_GA(X1) -> TREE_MEMBERA_IN_GA(X1) R is empty. Q is empty. We have to consider all (P,Q,R)-chains.