YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern perm1(g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 23 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [EQUIVALENT, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES ---------------------------------------- (0) Obligation: Clauses: perm1(L, M) :- ','(eq_len1(L, M), same_sets(L, M)). eq_len1([], []). eq_len1(.(X1, Xs), .(X2, Ys)) :- eq_len1(Xs, Ys). member(X, .(X, X3)). member(X, .(X4, T)) :- member(X, T). same_sets([], X5). same_sets(.(X, Xs), L) :- ','(member(X, L), same_sets(Xs, L)). Query: perm1(g,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 7, "program": { "directives": [], "clauses": [ [ "(perm1 L M)", "(',' (eq_len1 L M) (same_sets L M))" ], [ "(eq_len1 ([]) ([]))", null ], [ "(eq_len1 (. X1 Xs) (. X2 Ys))", "(eq_len1 Xs Ys)" ], [ "(member X (. X X3))", null ], [ "(member X (. X4 T))", "(member X T)" ], [ "(same_sets ([]) X5)", null ], [ "(same_sets (. X Xs) L)", "(',' (member X L) (same_sets Xs L))" ] ] }, "graph": { "nodes": { "type": "Nodes", "350": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "351": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "352": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "353": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T75 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77" ], "free": [], "exprvars": [] } }, "354": { "goal": [ { "clause": 3, "scope": 7, "term": "(member T75 T77)" }, { "clause": 4, "scope": 7, "term": "(member T75 T77)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77" ], "free": [], "exprvars": [] } }, "355": { "goal": [{ "clause": 3, "scope": 7, "term": "(member T75 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77" ], "free": [], "exprvars": [] } }, "356": { "goal": [{ "clause": 4, "scope": 7, "term": "(member T75 T77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T77" ], "free": [], "exprvars": [] } }, "357": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "358": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "359": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "360": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T98 T100)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T98", "T100" ], "free": [], "exprvars": [] } }, "361": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "362": { "goal": [ { "clause": 5, "scope": 8, "term": "(same_sets T44 (. T45 T46))" }, { "clause": 6, "scope": 8, "term": "(same_sets T44 (. T45 T46))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45", "T46" ], "free": [], "exprvars": [] } }, "363": { "goal": [{ "clause": 5, "scope": 8, "term": "(same_sets T44 (. T45 T46))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45", "T46" ], "free": [], "exprvars": [] } }, "364": { "goal": [{ "clause": 6, "scope": 8, "term": "(same_sets T44 (. T45 T46))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45", "T46" ], "free": [], "exprvars": [] } }, "365": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "366": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "367": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "368": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member T127 (. T129 T130)) (same_sets T128 (. T129 T130)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T127", "T128", "T129", "T130" ], "free": [], "exprvars": [] } }, "369": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(perm1 T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": 0, "scope": 1, "term": "(perm1 T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "295": { "goal": [{ "clause": -1, "scope": -1, "term": "(same_sets ([]) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "296": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "297": { "goal": [ { "clause": 5, "scope": 3, "term": "(same_sets ([]) ([]))" }, { "clause": 6, "scope": 3, "term": "(same_sets ([]) ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "298": { "goal": [{ "clause": 5, "scope": 3, "term": "(same_sets ([]) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "299": { "goal": [{ "clause": 6, "scope": 3, "term": "(same_sets ([]) ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "332": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq_len1 T16 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T18" ], "free": [], "exprvars": [] } }, "256": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (eq_len1 T5 T6) (same_sets T5 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [], "exprvars": [] } }, "333": { "goal": [{ "clause": -1, "scope": -1, "term": "(same_sets (. T15 T16) (. T17 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16", "T17", "T18" ], "free": [], "exprvars": [] } }, "257": { "goal": [ { "clause": 1, "scope": 2, "term": "(',' (eq_len1 T5 T6) (same_sets T5 T6))" }, { "clause": 2, "scope": 2, "term": "(',' (eq_len1 T5 T6) (same_sets T5 T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [], "exprvars": [] } }, "334": { "goal": [ { "clause": 1, "scope": 4, "term": "(eq_len1 T16 T18)" }, { "clause": 2, "scope": 4, "term": "(eq_len1 T16 T18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T18" ], "free": [], "exprvars": [] } }, "258": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (eq_len1 T5 T6) (same_sets T5 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [], "exprvars": [] } }, "335": { "goal": [{ "clause": 1, "scope": 4, "term": "(eq_len1 T16 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T18" ], "free": [], "exprvars": [] } }, "259": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (eq_len1 T5 T6) (same_sets T5 T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T5", "T6" ], "free": [], "exprvars": [] } }, "336": { "goal": [{ "clause": 2, "scope": 4, "term": "(eq_len1 T16 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T18" ], "free": [], "exprvars": [] } }, "337": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "338": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "339": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "340": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq_len1 T28 T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T30" ], "free": [], "exprvars": [] } }, "341": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "342": { "goal": [ { "clause": 5, "scope": 5, "term": "(same_sets (. T15 T16) (. T17 T18))" }, { "clause": 6, "scope": 5, "term": "(same_sets (. T15 T16) (. T17 T18))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16", "T17", "T18" ], "free": [], "exprvars": [] } }, "343": { "goal": [{ "clause": 6, "scope": 5, "term": "(same_sets (. T15 T16) (. T17 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16", "T17", "T18" ], "free": [], "exprvars": [] } }, "344": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (member T43 (. T45 T46)) (same_sets T44 (. T45 T46)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T44", "T45", "T46" ], "free": [], "exprvars": [] } }, "301": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "345": { "goal": [{ "clause": -1, "scope": -1, "term": "(member T43 (. T45 T46))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T45", "T46" ], "free": [], "exprvars": [] } }, "302": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "346": { "goal": [{ "clause": -1, "scope": -1, "term": "(same_sets T44 (. T45 T46))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45", "T46" ], "free": [], "exprvars": [] } }, "303": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "347": { "goal": [ { "clause": 3, "scope": 6, "term": "(member T43 (. T45 T46))" }, { "clause": 4, "scope": 6, "term": "(member T43 (. T45 T46))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T45", "T46" ], "free": [], "exprvars": [] } }, "348": { "goal": [{ "clause": 3, "scope": 6, "term": "(member T43 (. T45 T46))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T45", "T46" ], "free": [], "exprvars": [] } }, "349": { "goal": [{ "clause": 4, "scope": 6, "term": "(member T43 (. T45 T46))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T43", "T45", "T46" ], "free": [], "exprvars": [] } }, "306": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (eq_len1 T16 T18) (same_sets (. T15 T16) (. T17 T18)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16", "T17", "T18" ], "free": [], "exprvars": [] } }, "307": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 7, "to": 8, "label": "CASE" }, { "from": 8, "to": 256, "label": "ONLY EVAL with clause\nperm1(X8, X9) :- ','(eq_len1(X8, X9), same_sets(X8, X9)).\nand substitutionT1 -> T5,\nX8 -> T5,\nT2 -> T6,\nX9 -> T6" }, { "from": 256, "to": 257, "label": "CASE" }, { "from": 257, "to": 258, "label": "PARALLEL" }, { "from": 257, "to": 259, "label": "PARALLEL" }, { "from": 258, "to": 295, "label": "EVAL with clause\neq_len1([], []).\nand substitutionT5 -> [],\nT6 -> []" }, { "from": 258, "to": 296, "label": "EVAL-BACKTRACK" }, { "from": 259, "to": 306, "label": "EVAL with clause\neq_len1(.(X27, X28), .(X29, X30)) :- eq_len1(X28, X30).\nand substitutionX27 -> T15,\nX28 -> T16,\nT5 -> .(T15, T16),\nX29 -> T17,\nX30 -> T18,\nT6 -> .(T17, T18)" }, { "from": 259, "to": 307, "label": "EVAL-BACKTRACK" }, { "from": 295, "to": 297, "label": "CASE" }, { "from": 297, "to": 298, "label": "PARALLEL" }, { "from": 297, "to": 299, "label": "PARALLEL" }, { "from": 298, "to": 301, "label": "ONLY EVAL with clause\nsame_sets([], X15).\nand substitutionX15 -> []" }, { "from": 299, "to": 303, "label": "BACKTRACK\nfor clause: same_sets(.(X, Xs), L) :- ','(member(X, L), same_sets(Xs, L))because of non-unification" }, { "from": 301, "to": 302, "label": "SUCCESS" }, { "from": 306, "to": 332, "label": "SPLIT 1" }, { "from": 306, "to": 333, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT18 is ground" }, { "from": 332, "to": 334, "label": "CASE" }, { "from": 333, "to": 342, "label": "CASE" }, { "from": 334, "to": 335, "label": "PARALLEL" }, { "from": 334, "to": 336, "label": "PARALLEL" }, { "from": 335, "to": 337, "label": "EVAL with clause\neq_len1([], []).\nand substitutionT16 -> [],\nT18 -> []" }, { "from": 335, "to": 338, "label": "EVAL-BACKTRACK" }, { "from": 336, "to": 340, "label": "EVAL with clause\neq_len1(.(X39, X40), .(X41, X42)) :- eq_len1(X40, X42).\nand substitutionX39 -> T27,\nX40 -> T28,\nT16 -> .(T27, T28),\nX41 -> T29,\nX42 -> T30,\nT18 -> .(T29, T30)" }, { "from": 336, "to": 341, "label": "EVAL-BACKTRACK" }, { "from": 337, "to": 339, "label": "SUCCESS" }, { "from": 340, "to": 332, "label": "INSTANCE with matching:\nT16 -> T28\nT18 -> T30" }, { "from": 342, "to": 343, "label": "BACKTRACK\nfor clause: same_sets([], X5)because of non-unification" }, { "from": 343, "to": 344, "label": "ONLY EVAL with clause\nsame_sets(.(X56, X57), X58) :- ','(member(X56, X58), same_sets(X57, X58)).\nand substitutionT15 -> T43,\nX56 -> T43,\nT16 -> T44,\nX57 -> T44,\nT17 -> T45,\nT18 -> T46,\nX58 -> .(T45, T46)" }, { "from": 344, "to": 345, "label": "SPLIT 1" }, { "from": 344, "to": 346, "label": "SPLIT 2\nnew knowledge:\nT43 is ground\nT45 is ground\nT46 is ground" }, { "from": 345, "to": 347, "label": "CASE" }, { "from": 346, "to": 362, "label": "CASE" }, { "from": 347, "to": 348, "label": "PARALLEL" }, { "from": 347, "to": 349, "label": "PARALLEL" }, { "from": 348, "to": 350, "label": "EVAL with clause\nmember(X75, .(X75, X76)).\nand substitutionT43 -> T63,\nX75 -> T63,\nT45 -> T63,\nT46 -> T64,\nX76 -> T64" }, { "from": 348, "to": 351, "label": "EVAL-BACKTRACK" }, { "from": 349, "to": 353, "label": "ONLY EVAL with clause\nmember(X87, .(X88, X89)) :- member(X87, X89).\nand substitutionT43 -> T75,\nX87 -> T75,\nT45 -> T76,\nX88 -> T76,\nT46 -> T77,\nX89 -> T77" }, { "from": 350, "to": 352, "label": "SUCCESS" }, { "from": 353, "to": 354, "label": "CASE" }, { "from": 354, "to": 355, "label": "PARALLEL" }, { "from": 354, "to": 356, "label": "PARALLEL" }, { "from": 355, "to": 357, "label": "EVAL with clause\nmember(X102, .(X102, X103)).\nand substitutionT75 -> T90,\nX102 -> T90,\nX103 -> T91,\nT77 -> .(T90, T91)" }, { "from": 355, "to": 358, "label": "EVAL-BACKTRACK" }, { "from": 356, "to": 360, "label": "EVAL with clause\nmember(X110, .(X111, X112)) :- member(X110, X112).\nand substitutionT75 -> T98,\nX110 -> T98,\nX111 -> T99,\nX112 -> T100,\nT77 -> .(T99, T100)" }, { "from": 356, "to": 361, "label": "EVAL-BACKTRACK" }, { "from": 357, "to": 359, "label": "SUCCESS" }, { "from": 360, "to": 353, "label": "INSTANCE with matching:\nT75 -> T98\nT77 -> T100" }, { "from": 362, "to": 363, "label": "PARALLEL" }, { "from": 362, "to": 364, "label": "PARALLEL" }, { "from": 363, "to": 365, "label": "EVAL with clause\nsame_sets([], X123).\nand substitutionT44 -> [],\nT45 -> T117,\nT46 -> T118,\nX123 -> .(T117, T118)" }, { "from": 363, "to": 366, "label": "EVAL-BACKTRACK" }, { "from": 364, "to": 368, "label": "EVAL with clause\nsame_sets(.(X130, X131), X132) :- ','(member(X130, X132), same_sets(X131, X132)).\nand substitutionX130 -> T127,\nX131 -> T128,\nT44 -> .(T127, T128),\nT45 -> T129,\nT46 -> T130,\nX132 -> .(T129, T130)" }, { "from": 364, "to": 369, "label": "EVAL-BACKTRACK" }, { "from": 365, "to": 367, "label": "SUCCESS" }, { "from": 368, "to": 344, "label": "INSTANCE with matching:\nT43 -> T127\nT45 -> T129\nT46 -> T130\nT44 -> T128" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: eq_len1A(.(X1, X2), .(X3, X4)) :- eq_len1A(X2, X4). memberB(X1, .(X2, X3)) :- memberB(X1, X3). pC(X1, X2, X3, X4) :- memberB(X1, X3). pC(X1, X2, X3, .(X4, X5)) :- ','(membercD(X1, X2, X3), pC(X4, X2, X3, X5)). perm1E(.(X1, X2), .(X3, X4)) :- eq_len1A(X2, X4). perm1E(.(X1, X2), .(X3, X4)) :- ','(eq_len1cA(X2, X4), pC(X1, X3, X4, X2)). Clauses: eq_len1cA([], []). eq_len1cA(.(X1, X2), .(X3, X4)) :- eq_len1cA(X2, X4). membercB(X1, .(X1, X2)). membercB(X1, .(X2, X3)) :- membercB(X1, X3). qcC(X1, X2, X3, []) :- membercD(X1, X2, X3). qcC(X1, X2, X3, .(X4, X5)) :- ','(membercD(X1, X2, X3), qcC(X4, X2, X3, X5)). membercD(X1, X1, X2). membercD(X1, X2, X3) :- membercB(X1, X3). Afs: perm1E(x1, x2) = perm1E(x1, x2) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: perm1E_in_2: (b,b) eq_len1A_in_2: (b,b) eq_len1cA_in_2: (b,b) pC_in_4: (b,b,b,b) memberB_in_2: (b,b) membercD_in_3: (b,b,b) membercB_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: PERM1E_IN_GG(.(X1, X2), .(X3, X4)) -> U6_GG(X1, X2, X3, X4, eq_len1A_in_gg(X2, X4)) PERM1E_IN_GG(.(X1, X2), .(X3, X4)) -> EQ_LEN1A_IN_GG(X2, X4) EQ_LEN1A_IN_GG(.(X1, X2), .(X3, X4)) -> U1_GG(X1, X2, X3, X4, eq_len1A_in_gg(X2, X4)) EQ_LEN1A_IN_GG(.(X1, X2), .(X3, X4)) -> EQ_LEN1A_IN_GG(X2, X4) PERM1E_IN_GG(.(X1, X2), .(X3, X4)) -> U7_GG(X1, X2, X3, X4, eq_len1cA_in_gg(X2, X4)) U7_GG(X1, X2, X3, X4, eq_len1cA_out_gg(X2, X4)) -> U8_GG(X1, X2, X3, X4, pC_in_gggg(X1, X3, X4, X2)) U7_GG(X1, X2, X3, X4, eq_len1cA_out_gg(X2, X4)) -> PC_IN_GGGG(X1, X3, X4, X2) PC_IN_GGGG(X1, X2, X3, X4) -> U3_GGGG(X1, X2, X3, X4, memberB_in_gg(X1, X3)) PC_IN_GGGG(X1, X2, X3, X4) -> MEMBERB_IN_GG(X1, X3) MEMBERB_IN_GG(X1, .(X2, X3)) -> U2_GG(X1, X2, X3, memberB_in_gg(X1, X3)) MEMBERB_IN_GG(X1, .(X2, X3)) -> MEMBERB_IN_GG(X1, X3) PC_IN_GGGG(X1, X2, X3, .(X4, X5)) -> U4_GGGG(X1, X2, X3, X4, X5, membercD_in_ggg(X1, X2, X3)) U4_GGGG(X1, X2, X3, X4, X5, membercD_out_ggg(X1, X2, X3)) -> U5_GGGG(X1, X2, X3, X4, X5, pC_in_gggg(X4, X2, X3, X5)) U4_GGGG(X1, X2, X3, X4, X5, membercD_out_ggg(X1, X2, X3)) -> PC_IN_GGGG(X4, X2, X3, X5) The TRS R consists of the following rules: eq_len1cA_in_gg([], []) -> eq_len1cA_out_gg([], []) eq_len1cA_in_gg(.(X1, X2), .(X3, X4)) -> U10_gg(X1, X2, X3, X4, eq_len1cA_in_gg(X2, X4)) U10_gg(X1, X2, X3, X4, eq_len1cA_out_gg(X2, X4)) -> eq_len1cA_out_gg(.(X1, X2), .(X3, X4)) membercD_in_ggg(X1, X1, X2) -> membercD_out_ggg(X1, X1, X2) membercD_in_ggg(X1, X2, X3) -> U15_ggg(X1, X2, X3, membercB_in_gg(X1, X3)) membercB_in_gg(X1, .(X1, X2)) -> membercB_out_gg(X1, .(X1, X2)) membercB_in_gg(X1, .(X2, X3)) -> U11_gg(X1, X2, X3, membercB_in_gg(X1, X3)) U11_gg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercB_out_gg(X1, .(X2, X3)) U15_ggg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercD_out_ggg(X1, X2, X3) Pi is empty. We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: PERM1E_IN_GG(.(X1, X2), .(X3, X4)) -> U6_GG(X1, X2, X3, X4, eq_len1A_in_gg(X2, X4)) PERM1E_IN_GG(.(X1, X2), .(X3, X4)) -> EQ_LEN1A_IN_GG(X2, X4) EQ_LEN1A_IN_GG(.(X1, X2), .(X3, X4)) -> U1_GG(X1, X2, X3, X4, eq_len1A_in_gg(X2, X4)) EQ_LEN1A_IN_GG(.(X1, X2), .(X3, X4)) -> EQ_LEN1A_IN_GG(X2, X4) PERM1E_IN_GG(.(X1, X2), .(X3, X4)) -> U7_GG(X1, X2, X3, X4, eq_len1cA_in_gg(X2, X4)) U7_GG(X1, X2, X3, X4, eq_len1cA_out_gg(X2, X4)) -> U8_GG(X1, X2, X3, X4, pC_in_gggg(X1, X3, X4, X2)) U7_GG(X1, X2, X3, X4, eq_len1cA_out_gg(X2, X4)) -> PC_IN_GGGG(X1, X3, X4, X2) PC_IN_GGGG(X1, X2, X3, X4) -> U3_GGGG(X1, X2, X3, X4, memberB_in_gg(X1, X3)) PC_IN_GGGG(X1, X2, X3, X4) -> MEMBERB_IN_GG(X1, X3) MEMBERB_IN_GG(X1, .(X2, X3)) -> U2_GG(X1, X2, X3, memberB_in_gg(X1, X3)) MEMBERB_IN_GG(X1, .(X2, X3)) -> MEMBERB_IN_GG(X1, X3) PC_IN_GGGG(X1, X2, X3, .(X4, X5)) -> U4_GGGG(X1, X2, X3, X4, X5, membercD_in_ggg(X1, X2, X3)) U4_GGGG(X1, X2, X3, X4, X5, membercD_out_ggg(X1, X2, X3)) -> U5_GGGG(X1, X2, X3, X4, X5, pC_in_gggg(X4, X2, X3, X5)) U4_GGGG(X1, X2, X3, X4, X5, membercD_out_ggg(X1, X2, X3)) -> PC_IN_GGGG(X4, X2, X3, X5) The TRS R consists of the following rules: eq_len1cA_in_gg([], []) -> eq_len1cA_out_gg([], []) eq_len1cA_in_gg(.(X1, X2), .(X3, X4)) -> U10_gg(X1, X2, X3, X4, eq_len1cA_in_gg(X2, X4)) U10_gg(X1, X2, X3, X4, eq_len1cA_out_gg(X2, X4)) -> eq_len1cA_out_gg(.(X1, X2), .(X3, X4)) membercD_in_ggg(X1, X1, X2) -> membercD_out_ggg(X1, X1, X2) membercD_in_ggg(X1, X2, X3) -> U15_ggg(X1, X2, X3, membercB_in_gg(X1, X3)) membercB_in_gg(X1, .(X1, X2)) -> membercB_out_gg(X1, .(X1, X2)) membercB_in_gg(X1, .(X2, X3)) -> U11_gg(X1, X2, X3, membercB_in_gg(X1, X3)) U11_gg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercB_out_gg(X1, .(X2, X3)) U15_ggg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercD_out_ggg(X1, X2, X3) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 10 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERB_IN_GG(X1, .(X2, X3)) -> MEMBERB_IN_GG(X1, X3) The TRS R consists of the following rules: eq_len1cA_in_gg([], []) -> eq_len1cA_out_gg([], []) eq_len1cA_in_gg(.(X1, X2), .(X3, X4)) -> U10_gg(X1, X2, X3, X4, eq_len1cA_in_gg(X2, X4)) U10_gg(X1, X2, X3, X4, eq_len1cA_out_gg(X2, X4)) -> eq_len1cA_out_gg(.(X1, X2), .(X3, X4)) membercD_in_ggg(X1, X1, X2) -> membercD_out_ggg(X1, X1, X2) membercD_in_ggg(X1, X2, X3) -> U15_ggg(X1, X2, X3, membercB_in_gg(X1, X3)) membercB_in_gg(X1, .(X1, X2)) -> membercB_out_gg(X1, .(X1, X2)) membercB_in_gg(X1, .(X2, X3)) -> U11_gg(X1, X2, X3, membercB_in_gg(X1, X3)) U11_gg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercB_out_gg(X1, .(X2, X3)) U15_ggg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercD_out_ggg(X1, X2, X3) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: MEMBERB_IN_GG(X1, .(X2, X3)) -> MEMBERB_IN_GG(X1, X3) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: MEMBERB_IN_GG(X1, .(X2, X3)) -> MEMBERB_IN_GG(X1, X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MEMBERB_IN_GG(X1, .(X2, X3)) -> MEMBERB_IN_GG(X1, X3) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: PC_IN_GGGG(X1, X2, X3, .(X4, X5)) -> U4_GGGG(X1, X2, X3, X4, X5, membercD_in_ggg(X1, X2, X3)) U4_GGGG(X1, X2, X3, X4, X5, membercD_out_ggg(X1, X2, X3)) -> PC_IN_GGGG(X4, X2, X3, X5) The TRS R consists of the following rules: eq_len1cA_in_gg([], []) -> eq_len1cA_out_gg([], []) eq_len1cA_in_gg(.(X1, X2), .(X3, X4)) -> U10_gg(X1, X2, X3, X4, eq_len1cA_in_gg(X2, X4)) U10_gg(X1, X2, X3, X4, eq_len1cA_out_gg(X2, X4)) -> eq_len1cA_out_gg(.(X1, X2), .(X3, X4)) membercD_in_ggg(X1, X1, X2) -> membercD_out_ggg(X1, X1, X2) membercD_in_ggg(X1, X2, X3) -> U15_ggg(X1, X2, X3, membercB_in_gg(X1, X3)) membercB_in_gg(X1, .(X1, X2)) -> membercB_out_gg(X1, .(X1, X2)) membercB_in_gg(X1, .(X2, X3)) -> U11_gg(X1, X2, X3, membercB_in_gg(X1, X3)) U11_gg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercB_out_gg(X1, .(X2, X3)) U15_ggg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercD_out_ggg(X1, X2, X3) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: PC_IN_GGGG(X1, X2, X3, .(X4, X5)) -> U4_GGGG(X1, X2, X3, X4, X5, membercD_in_ggg(X1, X2, X3)) U4_GGGG(X1, X2, X3, X4, X5, membercD_out_ggg(X1, X2, X3)) -> PC_IN_GGGG(X4, X2, X3, X5) The TRS R consists of the following rules: membercD_in_ggg(X1, X1, X2) -> membercD_out_ggg(X1, X1, X2) membercD_in_ggg(X1, X2, X3) -> U15_ggg(X1, X2, X3, membercB_in_gg(X1, X3)) U15_ggg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercD_out_ggg(X1, X2, X3) membercB_in_gg(X1, .(X1, X2)) -> membercB_out_gg(X1, .(X1, X2)) membercB_in_gg(X1, .(X2, X3)) -> U11_gg(X1, X2, X3, membercB_in_gg(X1, X3)) U11_gg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercB_out_gg(X1, .(X2, X3)) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: PC_IN_GGGG(X1, X2, X3, .(X4, X5)) -> U4_GGGG(X1, X2, X3, X4, X5, membercD_in_ggg(X1, X2, X3)) U4_GGGG(X1, X2, X3, X4, X5, membercD_out_ggg(X1, X2, X3)) -> PC_IN_GGGG(X4, X2, X3, X5) The TRS R consists of the following rules: membercD_in_ggg(X1, X1, X2) -> membercD_out_ggg(X1, X1, X2) membercD_in_ggg(X1, X2, X3) -> U15_ggg(X1, X2, X3, membercB_in_gg(X1, X3)) U15_ggg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercD_out_ggg(X1, X2, X3) membercB_in_gg(X1, .(X1, X2)) -> membercB_out_gg(X1, .(X1, X2)) membercB_in_gg(X1, .(X2, X3)) -> U11_gg(X1, X2, X3, membercB_in_gg(X1, X3)) U11_gg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercB_out_gg(X1, .(X2, X3)) The set Q consists of the following terms: membercD_in_ggg(x0, x1, x2) U15_ggg(x0, x1, x2, x3) membercB_in_gg(x0, x1) U11_gg(x0, x1, x2, x3) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *U4_GGGG(X1, X2, X3, X4, X5, membercD_out_ggg(X1, X2, X3)) -> PC_IN_GGGG(X4, X2, X3, X5) The graph contains the following edges 4 >= 1, 2 >= 2, 6 > 2, 3 >= 3, 6 > 3, 5 >= 4 *PC_IN_GGGG(X1, X2, X3, .(X4, X5)) -> U4_GGGG(X1, X2, X3, X4, X5, membercD_in_ggg(X1, X2, X3)) The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 > 4, 4 > 5 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: EQ_LEN1A_IN_GG(.(X1, X2), .(X3, X4)) -> EQ_LEN1A_IN_GG(X2, X4) The TRS R consists of the following rules: eq_len1cA_in_gg([], []) -> eq_len1cA_out_gg([], []) eq_len1cA_in_gg(.(X1, X2), .(X3, X4)) -> U10_gg(X1, X2, X3, X4, eq_len1cA_in_gg(X2, X4)) U10_gg(X1, X2, X3, X4, eq_len1cA_out_gg(X2, X4)) -> eq_len1cA_out_gg(.(X1, X2), .(X3, X4)) membercD_in_ggg(X1, X1, X2) -> membercD_out_ggg(X1, X1, X2) membercD_in_ggg(X1, X2, X3) -> U15_ggg(X1, X2, X3, membercB_in_gg(X1, X3)) membercB_in_gg(X1, .(X1, X2)) -> membercB_out_gg(X1, .(X1, X2)) membercB_in_gg(X1, .(X2, X3)) -> U11_gg(X1, X2, X3, membercB_in_gg(X1, X3)) U11_gg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercB_out_gg(X1, .(X2, X3)) U15_ggg(X1, X2, X3, membercB_out_gg(X1, X3)) -> membercD_out_ggg(X1, X2, X3) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: EQ_LEN1A_IN_GG(.(X1, X2), .(X3, X4)) -> EQ_LEN1A_IN_GG(X2, X4) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: EQ_LEN1A_IN_GG(.(X1, X2), .(X3, X4)) -> EQ_LEN1A_IN_GG(X2, X4) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *EQ_LEN1A_IN_GG(.(X1, X2), .(X3, X4)) -> EQ_LEN1A_IN_GG(X2, X4) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (27) YES