/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 q(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) BuiltinConflictTransformerProof [EQUIVALENT, 0 ms] (2) Prolog (3) PrologToDTProblemTransformerProof [SOUND, 0 ms] (4) TRIPLES (5) TriplesToPiDPProof [SOUND, 0 ms] (6) PiDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) PiDP (9) PiDPToQDPProof [SOUND, 0 ms] (10) QDP (11) QDPSizeChangeProof [EQUIVALENT, 0 ms] (12) YES ---------------------------------------- (0) Obligation: Clauses: m(X, 0, Z) :- ','(!, =(Z, X)). m(0, Y, Z) :- ','(!, =(Z, 0)). m(X, Y, Z) :- ','(p(X, A), ','(p(Y, B), m(A, B, Z))). p(0, 0). p(s(X), X). q(X, Y, Z) :- m(X, Y, Z). q(X, Y, Z). =(X, X). Query: q(g,g,a) ---------------------------------------- (1) BuiltinConflictTransformerProof (EQUIVALENT) Renamed defined predicates conflicting with built-in predicates [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: m(X, 0, Z) :- ','(!, user_defined_=(Z, X)). m(0, Y, Z) :- ','(!, user_defined_=(Z, 0)). m(X, Y, Z) :- ','(p(X, A), ','(p(Y, B), m(A, B, Z))). p(0, 0). p(s(X), X). q(X, Y, Z) :- m(X, Y, Z). q(X, Y, Z). user_defined_=(X, X). Query: q(g,g,a) ---------------------------------------- (3) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(m X (0) Z)", "(',' (!) (user_defined_= Z X))" ], [ "(m (0) Y Z)", "(',' (!) (user_defined_= Z (0)))" ], [ "(m X Y Z)", "(',' (p X A) (',' (p Y B) (m A B Z)))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(q X Y Z)", "(m X Y Z)" ], [ "(q X Y Z)", null ], [ "(user_defined_= X X)", null ] ] }, "graph": { "nodes": { "390": { "goal": [{ "clause": 4, "scope": 10, "term": "(',' (p T102 X115) (',' (p T103 X116) (m X115 X116 T105)))" }], "kb": { "nonunifying": [ [ "(m T102 T103 T62)", "(m X87 (0) X88)" ], [ "(m T102 T103 T62)", "(m (0) X96 X97)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T102", "T103" ], "free": [ "X87", "X88", "X96", "X97", "X115", "X116" ], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "392": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T103 X116) (m T109 X116 T105))" }], "kb": { "nonunifying": [[ "(m (s T109) T103 T62)", "(m X87 (0) X88)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T103", "T109" ], "free": [ "X87", "X88", "X116" ], "exprvars": [] } }, "272": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "273": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "350": { "goal": [{ "clause": 4, "scope": 6, "term": "(',' (p T60 X69) (m T66 X69 T62))" }], "kb": { "nonunifying": [[ "(m (s T66) T60 T10)", "(m X11 (0) X12)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T66" ], "free": [ "X11", "X12", "X69" ], "exprvars": [] } }, "395": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "275": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "352": { "goal": [{ "clause": -1, "scope": -1, "term": "(m T66 T71 T62)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T66", "T71" ], "free": [], "exprvars": [] } }, "396": { "goal": [ { "clause": 3, "scope": 11, "term": "(',' (p T103 X116) (m T109 X116 T105))" }, { "clause": 4, "scope": 11, "term": "(',' (p T103 X116) (m T109 X116 T105))" } ], "kb": { "nonunifying": [[ "(m (s T109) T103 T62)", "(m X87 (0) X88)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T103", "T109" ], "free": [ "X87", "X88", "X116" ], "exprvars": [] } }, "276": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "353": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "397": { "goal": [{ "clause": 4, "scope": 11, "term": "(',' (p T103 X116) (m T109 X116 T105))" }], "kb": { "nonunifying": [[ "(m (s T109) T103 T62)", "(m X87 (0) X88)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T103", "T109" ], "free": [ "X87", "X88", "X116" ], "exprvars": [] } }, "355": { "goal": [ { "clause": 0, "scope": 7, "term": "(m T66 T71 T62)" }, { "clause": 1, "scope": 7, "term": "(m T66 T71 T62)" }, { "clause": 2, "scope": 7, "term": "(m T66 T71 T62)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T66", "T71" ], "free": [], "exprvars": [] } }, "279": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_2) (user_defined_= T33 (0)))" }, { "clause": 2, "scope": 2, "term": "(m (0) T31 T10)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 6, "scope": 1, "term": "(q (0) T31 T3)" } ], "kb": { "nonunifying": [[ "(m (0) T31 T10)", "(m X11 (0) X12)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T31"], "free": [ "X11", "X12" ], "exprvars": [] } }, "359": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_7) (user_defined_= T80 T78))" }, { "clause": 1, "scope": 7, "term": "(m T78 (0) T62)" }, { "clause": 2, "scope": 7, "term": "(m T78 (0) T62)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T78"], "free": [], "exprvars": [] } }, "318": { "goal": [{ "clause": 2, "scope": 2, "term": "(m T7 T8 T10)" }], "kb": { "nonunifying": [ [ "(m T7 T8 T10)", "(m X11 (0) X12)" ], [ "(m T7 T8 T10)", "(m (0) X29 X30)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [ "X11", "X12", "X29", "X30" ], "exprvars": [] } }, "18": { "goal": [ { "clause": 5, "scope": 1, "term": "(q T1 T2 T3)" }, { "clause": 6, "scope": 1, "term": "(q T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "283": { "goal": [ { "clause": 2, "scope": 2, "term": "(m T7 T8 T10)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 6, "scope": 1, "term": "(q T7 T8 T3)" } ], "kb": { "nonunifying": [ [ "(m T7 T8 T10)", "(m X11 (0) X12)" ], [ "(m T7 T8 T10)", "(m (0) X29 X30)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [ "X11", "X12", "X29", "X30" ], "exprvars": [] } }, "284": { "goal": [ { "clause": -1, "scope": -1, "term": "(user_defined_= T33 (0))" }, { "clause": 6, "scope": 1, "term": "(q (0) T31 T3)" } ], "kb": { "nonunifying": [[ "(m (0) T31 T10)", "(m X11 (0) X12)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T31"], "free": [ "X11", "X12" ], "exprvars": [] } }, "361": { "goal": [ { "clause": 1, "scope": 7, "term": "(m T66 T71 T62)" }, { "clause": 2, "scope": 7, "term": "(m T66 T71 T62)" } ], "kb": { "nonunifying": [[ "(m T66 T71 T62)", "(m X87 (0) X88)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T66", "T71" ], "free": [ "X87", "X88" ], "exprvars": [] } }, "362": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= T80 T78)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T78"], "free": [], "exprvars": [] } }, "286": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= T33 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "363": { "goal": [{ "clause": 7, "scope": 8, "term": "(user_defined_= T80 T78)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T78"], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(q T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "289": { "goal": [{ "clause": 6, "scope": 1, "term": "(q (0) T31 T3)" }], "kb": { "nonunifying": [[ "(m (0) T31 T10)", "(m X11 (0) X12)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T31"], "free": [ "X11", "X12" ], "exprvars": [] } }, "366": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "323": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 6, "scope": 1, "term": "(q T7 T8 T3)" } ], "kb": { "nonunifying": [ [ "(m T7 T8 T10)", "(m X11 (0) X12)" ], [ "(m T7 T8 T10)", "(m (0) X29 X30)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [ "X11", "X12", "X29", "X30" ], "exprvars": [] } }, "367": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "368": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "402": { "goal": [{ "clause": -1, "scope": -1, "term": "(m T109 T114 T105)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T109", "T114" ], "free": [], "exprvars": [] } }, "403": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "404": { "goal": [{ "clause": 6, "scope": 1, "term": "(q T7 T8 T3)" }], "kb": { "nonunifying": [ [ "(m T7 T8 T10)", "(m X11 (0) X12)" ], [ "(m T7 T8 T10)", "(m (0) X29 X30)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [ "X11", "X12", "X29", "X30" ], "exprvars": [] } }, "405": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "406": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "290": { "goal": [{ "clause": 7, "scope": 4, "term": "(user_defined_= T33 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "291": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "292": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "293": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "298": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "375": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_7) (user_defined_= T90 (0)))" }, { "clause": 2, "scope": 7, "term": "(m (0) T88 T62)" } ], "kb": { "nonunifying": [[ "(m (0) T88 T62)", "(m X87 (0) X88)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T88"], "free": [ "X87", "X88" ], "exprvars": [] } }, "299": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "376": { "goal": [{ "clause": 2, "scope": 7, "term": "(m T66 T71 T62)" }], "kb": { "nonunifying": [ [ "(m T66 T71 T62)", "(m X87 (0) X88)" ], [ "(m T66 T71 T62)", "(m (0) X96 X97)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T66", "T71" ], "free": [ "X87", "X88", "X96", "X97" ], "exprvars": [] } }, "377": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= T90 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "257": { "goal": [ { "clause": -1, "scope": -1, "term": "(m T7 T8 T10)" }, { "clause": 6, "scope": 1, "term": "(q T7 T8 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "378": { "goal": [{ "clause": 7, "scope": 9, "term": "(user_defined_= T90 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "258": { "goal": [ { "clause": 0, "scope": 2, "term": "(m T7 T8 T10)" }, { "clause": 1, "scope": 2, "term": "(m T7 T8 T10)" }, { "clause": 2, "scope": 2, "term": "(m T7 T8 T10)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 6, "scope": 1, "term": "(q T7 T8 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "379": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "338": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T59 X68) (',' (p T60 X69) (m X68 X69 T62)))" }], "kb": { "nonunifying": [ [ "(m T59 T60 T10)", "(m X11 (0) X12)" ], [ "(m T59 T60 T10)", "(m (0) X29 X30)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T60" ], "free": [ "X11", "X12", "X29", "X30", "X68", "X69" ], "exprvars": [] } }, "339": { "goal": [ { "clause": 3, "scope": 5, "term": "(',' (p T59 X68) (',' (p T60 X69) (m X68 X69 T62)))" }, { "clause": 4, "scope": 5, "term": "(',' (p T59 X68) (',' (p T60 X69) (m X68 X69 T62)))" } ], "kb": { "nonunifying": [ [ "(m T59 T60 T10)", "(m X11 (0) X12)" ], [ "(m T59 T60 T10)", "(m (0) X29 X30)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T60" ], "free": [ "X11", "X12", "X29", "X30", "X68", "X69" ], "exprvars": [] } }, "380": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "260": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_2) (user_defined_= T17 T15))" }, { "clause": 1, "scope": 2, "term": "(m T15 (0) T10)" }, { "clause": 2, "scope": 2, "term": "(m T15 (0) T10)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 6, "scope": 1, "term": "(q T15 (0) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [], "exprvars": [] } }, "261": { "goal": [ { "clause": 1, "scope": 2, "term": "(m T7 T8 T10)" }, { "clause": 2, "scope": 2, "term": "(m T7 T8 T10)" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 6, "scope": 1, "term": "(q T7 T8 T3)" } ], "kb": { "nonunifying": [[ "(m T7 T8 T10)", "(m X11 (0) X12)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [ "X11", "X12" ], "exprvars": [] } }, "382": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "340": { "goal": [{ "clause": 4, "scope": 5, "term": "(',' (p T59 X68) (',' (p T60 X69) (m X68 X69 T62)))" }], "kb": { "nonunifying": [ [ "(m T59 T60 T10)", "(m X11 (0) X12)" ], [ "(m T59 T60 T10)", "(m (0) X29 X30)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T60" ], "free": [ "X11", "X12", "X29", "X30", "X68", "X69" ], "exprvars": [] } }, "264": { "goal": [ { "clause": -1, "scope": -1, "term": "(user_defined_= T17 T15)" }, { "clause": 6, "scope": 1, "term": "(q T15 (0) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [], "exprvars": [] } }, "386": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T102 X115) (',' (p T103 X116) (m X115 X116 T105)))" }], "kb": { "nonunifying": [ [ "(m T102 T103 T62)", "(m X87 (0) X88)" ], [ "(m T102 T103 T62)", "(m (0) X96 X97)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T102", "T103" ], "free": [ "X87", "X88", "X96", "X97", "X115", "X116" ], "exprvars": [] } }, "266": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= T17 T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [], "exprvars": [] } }, "267": { "goal": [{ "clause": 6, "scope": 1, "term": "(q T15 (0) T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [], "exprvars": [] } }, "344": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T60 X69) (m T66 X69 T62))" }], "kb": { "nonunifying": [[ "(m (s T66) T60 T10)", "(m X11 (0) X12)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T66" ], "free": [ "X11", "X12", "X69" ], "exprvars": [] } }, "268": { "goal": [{ "clause": 7, "scope": 3, "term": "(user_defined_= T17 T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [], "exprvars": [] } }, "389": { "goal": [ { "clause": 3, "scope": 10, "term": "(',' (p T102 X115) (',' (p T103 X116) (m X115 X116 T105)))" }, { "clause": 4, "scope": 10, "term": "(',' (p T102 X115) (',' (p T103 X116) (m X115 X116 T105)))" } ], "kb": { "nonunifying": [ [ "(m T102 T103 T62)", "(m X87 (0) X88)" ], [ "(m T102 T103 T62)", "(m (0) X96 X97)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T102", "T103" ], "free": [ "X87", "X88", "X96", "X97", "X115", "X116" ], "exprvars": [] } }, "347": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "348": { "goal": [ { "clause": 3, "scope": 6, "term": "(',' (p T60 X69) (m T66 X69 T62))" }, { "clause": 4, "scope": 6, "term": "(',' (p T60 X69) (m T66 X69 T62))" } ], "kb": { "nonunifying": [[ "(m (s T66) T60 T10)", "(m X11 (0) X12)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T60", "T66" ], "free": [ "X11", "X12", "X69" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 18, "label": "CASE" }, { "from": 18, "to": 257, "label": "ONLY EVAL with clause\nq(X4, X5, X6) :- m(X4, X5, X6).\nand substitutionT1 -> T7,\nX4 -> T7,\nT2 -> T8,\nX5 -> T8,\nT3 -> T10,\nX6 -> T10,\nT9 -> T10" }, { "from": 257, "to": 258, "label": "CASE" }, { "from": 258, "to": 260, "label": "EVAL with clause\nm(X11, 0, X12) :- ','(!_2, user_defined_=(X12, X11)).\nand substitutionT7 -> T15,\nX11 -> T15,\nT8 -> 0,\nT10 -> T17,\nX12 -> T17,\nT16 -> T17" }, { "from": 258, "to": 261, "label": "EVAL-BACKTRACK" }, { "from": 260, "to": 264, "label": "CUT" }, { "from": 261, "to": 279, "label": "EVAL with clause\nm(0, X29, X30) :- ','(!_2, user_defined_=(X30, 0)).\nand substitutionT7 -> 0,\nT8 -> T31,\nX29 -> T31,\nT10 -> T33,\nX30 -> T33,\nT32 -> T33" }, { "from": 261, "to": 283, "label": "EVAL-BACKTRACK" }, { "from": 264, "to": 266, "label": "PARALLEL" }, { "from": 264, "to": 267, "label": "PARALLEL" }, { "from": 266, "to": 268, "label": "CASE" }, { "from": 267, "to": 275, "label": "ONLY EVAL with clause\nq(X22, X23, X24).\nand substitutionT15 -> T25,\nX22 -> T25,\nX23 -> 0,\nT3 -> T26,\nX24 -> T26" }, { "from": 268, "to": 271, "label": "EVAL with clause\nuser_defined_=(X15, X15).\nand substitutionT17 -> T20,\nX15 -> T20,\nT15 -> T20" }, { "from": 268, "to": 272, "label": "EVAL-BACKTRACK" }, { "from": 271, "to": 273, "label": "SUCCESS" }, { "from": 275, "to": 276, "label": "SUCCESS" }, { "from": 279, "to": 284, "label": "CUT" }, { "from": 283, "to": 318, "label": "PARALLEL" }, { "from": 283, "to": 323, "label": "PARALLEL" }, { "from": 284, "to": 286, "label": "PARALLEL" }, { "from": 284, "to": 289, "label": "PARALLEL" }, { "from": 286, "to": 290, "label": "CASE" }, { "from": 289, "to": 298, "label": "ONLY EVAL with clause\nq(X40, X41, X42).\nand substitutionX40 -> 0,\nT31 -> T41,\nX41 -> T41,\nT3 -> T42,\nX42 -> T42" }, { "from": 290, "to": 291, "label": "EVAL with clause\nuser_defined_=(X33, X33).\nand substitutionT33 -> 0,\nX33 -> 0,\nT36 -> 0" }, { "from": 290, "to": 292, "label": "EVAL-BACKTRACK" }, { "from": 291, "to": 293, "label": "SUCCESS" }, { "from": 298, "to": 299, "label": "SUCCESS" }, { "from": 318, "to": 338, "label": "ONLY EVAL with clause\nm(X65, X66, X67) :- ','(p(X65, X68), ','(p(X66, X69), m(X68, X69, X67))).\nand substitutionT7 -> T59,\nX65 -> T59,\nT8 -> T60,\nX66 -> T60,\nT10 -> T62,\nX67 -> T62,\nT61 -> T62" }, { "from": 323, "to": 404, "label": "FAILURE" }, { "from": 338, "to": 339, "label": "CASE" }, { "from": 339, "to": 340, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (m(T59, T60, T10), m(0, X29, X30))" }, { "from": 340, "to": 344, "label": "EVAL with clause\np(s(X75), X75).\nand substitutionX75 -> T66,\nT59 -> s(T66),\nX68 -> T66" }, { "from": 340, "to": 347, "label": "EVAL-BACKTRACK" }, { "from": 344, "to": 348, "label": "CASE" }, { "from": 348, "to": 350, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (m(s(T66), T60, T10), m(X11, 0, X12))" }, { "from": 350, "to": 352, "label": "EVAL with clause\np(s(X80), X80).\nand substitutionX80 -> T71,\nT60 -> s(T71),\nX69 -> T71" }, { "from": 350, "to": 353, "label": "EVAL-BACKTRACK" }, { "from": 352, "to": 355, "label": "CASE" }, { "from": 355, "to": 359, "label": "EVAL with clause\nm(X87, 0, X88) :- ','(!_7, user_defined_=(X88, X87)).\nand substitutionT66 -> T78,\nX87 -> T78,\nT71 -> 0,\nT62 -> T80,\nX88 -> T80,\nT79 -> T80" }, { "from": 355, "to": 361, "label": "EVAL-BACKTRACK" }, { "from": 359, "to": 362, "label": "CUT" }, { "from": 361, "to": 375, "label": "EVAL with clause\nm(0, X96, X97) :- ','(!_7, user_defined_=(X97, 0)).\nand substitutionT66 -> 0,\nT71 -> T88,\nX96 -> T88,\nT62 -> T90,\nX97 -> T90,\nT89 -> T90" }, { "from": 361, "to": 376, "label": "EVAL-BACKTRACK" }, { "from": 362, "to": 363, "label": "CASE" }, { "from": 363, "to": 366, "label": "EVAL with clause\nuser_defined_=(X91, X91).\nand substitutionT80 -> T83,\nX91 -> T83,\nT78 -> T83" }, { "from": 363, "to": 367, "label": "EVAL-BACKTRACK" }, { "from": 366, "to": 368, "label": "SUCCESS" }, { "from": 375, "to": 377, "label": "CUT" }, { "from": 376, "to": 386, "label": "ONLY EVAL with clause\nm(X112, X113, X114) :- ','(p(X112, X115), ','(p(X113, X116), m(X115, X116, X114))).\nand substitutionT66 -> T102,\nX112 -> T102,\nT71 -> T103,\nX113 -> T103,\nT62 -> T105,\nX114 -> T105,\nT104 -> T105" }, { "from": 377, "to": 378, "label": "CASE" }, { "from": 378, "to": 379, "label": "EVAL with clause\nuser_defined_=(X100, X100).\nand substitutionT90 -> 0,\nX100 -> 0,\nT93 -> 0" }, { "from": 378, "to": 380, "label": "EVAL-BACKTRACK" }, { "from": 379, "to": 382, "label": "SUCCESS" }, { "from": 386, "to": 389, "label": "CASE" }, { "from": 389, "to": 390, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (m(T102, T103, T62), m(0, X96, X97))" }, { "from": 390, "to": 392, "label": "EVAL with clause\np(s(X122), X122).\nand substitutionX122 -> T109,\nT102 -> s(T109),\nX115 -> T109" }, { "from": 390, "to": 395, "label": "EVAL-BACKTRACK" }, { "from": 392, "to": 396, "label": "CASE" }, { "from": 396, "to": 397, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (m(s(T109), T103, T62), m(X87, 0, X88))" }, { "from": 397, "to": 402, "label": "EVAL with clause\np(s(X127), X127).\nand substitutionX127 -> T114,\nT103 -> s(T114),\nX116 -> T114" }, { "from": 397, "to": 403, "label": "EVAL-BACKTRACK" }, { "from": 402, "to": 352, "label": "INSTANCE with matching:\nT66 -> T109\nT71 -> T114\nT62 -> T105" }, { "from": 404, "to": 405, "label": "ONLY EVAL with clause\nq(X136, X137, X138).\nand substitutionT7 -> T123,\nX136 -> T123,\nT8 -> T124,\nX137 -> T124,\nT3 -> T125,\nX138 -> T125" }, { "from": 405, "to": 406, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (4) Obligation: Triples: mA(s(X1), s(X2), X3) :- mA(X1, X2, X3). qB(s(X1), s(X2), X3) :- mA(X1, X2, X3). Clauses: mcA(X1, 0, X1). mcA(0, X1, 0). mcA(s(X1), s(X2), X3) :- mcA(X1, X2, X3). Afs: qB(x1, x2, x3) = qB(x1, x2) ---------------------------------------- (5) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: qB_in_3: (b,b,f) mA_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: QB_IN_GGA(s(X1), s(X2), X3) -> U2_GGA(X1, X2, X3, mA_in_gga(X1, X2, X3)) QB_IN_GGA(s(X1), s(X2), X3) -> MA_IN_GGA(X1, X2, X3) MA_IN_GGA(s(X1), s(X2), X3) -> U1_GGA(X1, X2, X3, mA_in_gga(X1, X2, X3)) MA_IN_GGA(s(X1), s(X2), X3) -> MA_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) mA_in_gga(x1, x2, x3) = mA_in_gga(x1, x2) QB_IN_GGA(x1, x2, x3) = QB_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4) = U2_GGA(x1, x2, x4) MA_IN_GGA(x1, x2, x3) = MA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: QB_IN_GGA(s(X1), s(X2), X3) -> U2_GGA(X1, X2, X3, mA_in_gga(X1, X2, X3)) QB_IN_GGA(s(X1), s(X2), X3) -> MA_IN_GGA(X1, X2, X3) MA_IN_GGA(s(X1), s(X2), X3) -> U1_GGA(X1, X2, X3, mA_in_gga(X1, X2, X3)) MA_IN_GGA(s(X1), s(X2), X3) -> MA_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) mA_in_gga(x1, x2, x3) = mA_in_gga(x1, x2) QB_IN_GGA(x1, x2, x3) = QB_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4) = U2_GGA(x1, x2, x4) MA_IN_GGA(x1, x2, x3) = MA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 3 less nodes. ---------------------------------------- (8) Obligation: Pi DP problem: The TRS P consists of the following rules: MA_IN_GGA(s(X1), s(X2), X3) -> MA_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) MA_IN_GGA(x1, x2, x3) = MA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (9) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: MA_IN_GGA(s(X1), s(X2)) -> MA_IN_GGA(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) 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: *MA_IN_GGA(s(X1), s(X2)) -> MA_IN_GGA(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (12) YES