/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern p(a,a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) BuiltinConflictTransformerProof [EQUIVALENT, 0 ms] (2) Prolog (3) PrologToIRSwTTransformerProof [SOUND, 0 ms] (4) TRUE ---------------------------------------- (0) Obligation: Clauses: p(X, Y, Z) :- ','(=(X, Y), ','(=(Z, 1), !)). p(X, Y, Z) :- ','(=(Z, 1), ','(=(Y, X), p(X, Y, Z))). =(X, X). Query: p(a,a,a) ---------------------------------------- (1) BuiltinConflictTransformerProof (EQUIVALENT) Renamed defined predicates conflicting with built-in predicates [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: p(X, Y, Z) :- ','(user_defined_=(X, Y), ','(user_defined_=(Z, 1), !)). p(X, Y, Z) :- ','(user_defined_=(Z, 1), ','(user_defined_=(Y, X), p(X, Y, Z))). user_defined_=(X, X). Query: p(a,a,a) ---------------------------------------- (3) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 10, "program": { "directives": [], "clauses": [ [ "(p X Y Z)", "(',' (user_defined_= X Y) (',' (user_defined_= Z (1)) (!)))" ], [ "(p X Y Z)", "(',' (user_defined_= Z (1)) (',' (user_defined_= Y X) (p X Y Z)))" ], [ "(user_defined_= X X)", null ] ] }, "graph": { "nodes": { "type": "Nodes", "131": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= T16 T17) (',' (user_defined_= T18 (1)) (!_1)))" }, { "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "155": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": -1, "scope": 3, "term": null }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "310": { "goal": [ { "clause": 2, "scope": 7, "term": "(',' (user_defined_= T63 T63) (',' (user_defined_= (1) (1)) (!_6)))" }, { "clause": -1, "scope": 7, "term": null }, { "clause": 1, "scope": 6, "term": "(p T57 T57 (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "157": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "311": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= (1) (1)) (!_6))" }, { "clause": -1, "scope": 7, "term": null }, { "clause": 1, "scope": 6, "term": "(p T57 T57 (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "158": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "312": { "goal": [ { "clause": 2, "scope": 8, "term": "(',' (user_defined_= (1) (1)) (!_6))" }, { "clause": -1, "scope": 8, "term": null }, { "clause": -1, "scope": 7, "term": null }, { "clause": 1, "scope": 6, "term": "(p T57 T57 (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "159": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "313": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_6)" }, { "clause": -1, "scope": 8, "term": null }, { "clause": -1, "scope": 7, "term": null }, { "clause": 1, "scope": 6, "term": "(p T57 T57 (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "259": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (user_defined_= T41 (1)) (',' (user_defined_= T42 T43) (p T43 T42 T41)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "314": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "315": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "316": { "goal": [{ "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "317": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (user_defined_= T82 (1)) (',' (user_defined_= T83 T84) (p T84 T83 T82)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "318": { "goal": [{ "clause": 2, "scope": 9, "term": "(',' (user_defined_= T82 (1)) (',' (user_defined_= T83 T84) (p T84 T83 T82)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "319": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (user_defined_= T91 T92) (p T92 T91 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [ { "clause": 0, "scope": 1, "term": "(p T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "160": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "161": { "goal": [{ "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "140": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (user_defined_= T16 T17) (',' (user_defined_= T18 (1)) (!_1)))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "262": { "goal": [{ "clause": 2, "scope": 4, "term": "(',' (user_defined_= T41 (1)) (',' (user_defined_= T42 T43) (p T43 T42 T41)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "263": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (user_defined_= T50 T51) (p T51 T50 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "264": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "265": { "goal": [{ "clause": 2, "scope": 5, "term": "(',' (user_defined_= T50 T51) (p T51 T50 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "320": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "321": { "goal": [{ "clause": 2, "scope": 10, "term": "(',' (user_defined_= T91 T92) (p T92 T91 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "146": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= T22 (1)) (!_1))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "322": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T98 T98 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "147": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "323": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "148": { "goal": [ { "clause": 2, "scope": 3, "term": "(',' (user_defined_= T22 (1)) (!_1))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(p T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "306": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T57 T57 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "307": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "308": { "goal": [ { "clause": 0, "scope": 6, "term": "(p T57 T57 (1))" }, { "clause": 1, "scope": 6, "term": "(p T57 T57 (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "309": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= T63 T63) (',' (user_defined_= (1) (1)) (!_6)))" }, { "clause": 1, "scope": 6, "term": "(p T57 T57 (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 10, "to": 12, "label": "CASE" }, { "from": 12, "to": 131, "label": "ONLY EVAL with clause\np(X7, X8, X9) :- ','(user_defined_=(X7, X8), ','(user_defined_=(X9, 1), !_1)).\nand substitutionT1 -> T16,\nX7 -> T16,\nT2 -> T17,\nX8 -> T17,\nT3 -> T18,\nX9 -> T18,\nT13 -> T16,\nT14 -> T17,\nT15 -> T18" }, { "from": 131, "to": 140, "label": "CASE" }, { "from": 140, "to": 146, "label": "EVAL with clause\nuser_defined_=(X12, X12).\nand substitutionT16 -> T21,\nX12 -> T21,\nT17 -> T21,\nT18 -> T22" }, { "from": 140, "to": 147, "label": "EVAL-BACKTRACK" }, { "from": 146, "to": 148, "label": "CASE" }, { "from": 147, "to": 316, "label": "FAILURE" }, { "from": 148, "to": 155, "label": "EVAL with clause\nuser_defined_=(X15, X15).\nand substitutionT22 -> 1,\nX15 -> 1,\nT25 -> 1" }, { "from": 148, "to": 157, "label": "EVAL-BACKTRACK" }, { "from": 155, "to": 158, "label": "CUT" }, { "from": 157, "to": 160, "label": "FAILURE" }, { "from": 158, "to": 159, "label": "SUCCESS" }, { "from": 160, "to": 161, "label": "FAILURE" }, { "from": 161, "to": 259, "label": "ONLY EVAL with clause\np(X25, X26, X27) :- ','(user_defined_=(X27, 1), ','(user_defined_=(X26, X25), p(X25, X26, X27))).\nand substitutionT1 -> T43,\nX25 -> T43,\nT2 -> T42,\nX26 -> T42,\nT3 -> T41,\nX27 -> T41,\nT40 -> T41,\nT39 -> T42,\nT38 -> T43" }, { "from": 259, "to": 262, "label": "CASE" }, { "from": 262, "to": 263, "label": "EVAL with clause\nuser_defined_=(X33, X33).\nand substitutionT41 -> 1,\nX33 -> 1,\nT49 -> 1,\nT42 -> T50,\nT43 -> T51" }, { "from": 262, "to": 264, "label": "EVAL-BACKTRACK" }, { "from": 263, "to": 265, "label": "CASE" }, { "from": 265, "to": 306, "label": "EVAL with clause\nuser_defined_=(X39, X39).\nand substitutionT50 -> T57,\nX39 -> T57,\nT51 -> T57,\nT56 -> T57" }, { "from": 265, "to": 307, "label": "EVAL-BACKTRACK" }, { "from": 306, "to": 308, "label": "CASE" }, { "from": 308, "to": 309, "label": "ONLY EVAL with clause\np(X49, X50, X51) :- ','(user_defined_=(X49, X50), ','(user_defined_=(X51, 1), !_6)).\nand substitutionT57 -> T63,\nX49 -> T63,\nX50 -> T63,\nX51 -> 1,\nT62 -> T63" }, { "from": 309, "to": 310, "label": "CASE" }, { "from": 310, "to": 311, "label": "ONLY EVAL with clause\nuser_defined_=(X54, X54).\nand substitutionT63 -> T66,\nX54 -> T66" }, { "from": 311, "to": 312, "label": "CASE" }, { "from": 312, "to": 313, "label": "ONLY EVAL with clause\nuser_defined_=(X57, X57).\nand substitutionX57 -> 1" }, { "from": 313, "to": 314, "label": "CUT" }, { "from": 314, "to": 315, "label": "SUCCESS" }, { "from": 316, "to": 317, "label": "ONLY EVAL with clause\np(X67, X68, X69) :- ','(user_defined_=(X69, 1), ','(user_defined_=(X68, X67), p(X67, X68, X69))).\nand substitutionT1 -> T84,\nX67 -> T84,\nT2 -> T83,\nX68 -> T83,\nT3 -> T82,\nX69 -> T82,\nT81 -> T82,\nT80 -> T83,\nT79 -> T84" }, { "from": 317, "to": 318, "label": "CASE" }, { "from": 318, "to": 319, "label": "EVAL with clause\nuser_defined_=(X75, X75).\nand substitutionT82 -> 1,\nX75 -> 1,\nT90 -> 1,\nT83 -> T91,\nT84 -> T92" }, { "from": 318, "to": 320, "label": "EVAL-BACKTRACK" }, { "from": 319, "to": 321, "label": "CASE" }, { "from": 321, "to": 322, "label": "EVAL with clause\nuser_defined_=(X81, X81).\nand substitutionT91 -> T98,\nX81 -> T98,\nT92 -> T98,\nT97 -> T98" }, { "from": 321, "to": 323, "label": "EVAL-BACKTRACK" }, { "from": 322, "to": 306, "label": "INSTANCE with matching:\nT57 -> T98" } ], "type": "Graph" } } ---------------------------------------- (4) TRUE