/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern div(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToTRSTransformerProof [SOUND, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) QDP (13) QDPOrderProof [EQUIVALENT, 31 ms] (14) QDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) TRUE ---------------------------------------- (0) Obligation: Clauses: div(0, Y, 0) :- no(zero(Y)). div(X, Y, s(Z)) :- ','(no(zero(X)), ','(no(zero(Y)), ','(minus(X, Y, U), div(U, Y, Z)))). minus(0, Y, 0). minus(X, 0, X). minus(s(X), s(Y), Z) :- minus(X, Y, Z). zero(0). no(X) :- ','(X, ','(!, failure(a))). no(X1). failure(b). Query: div(g,g,a) ---------------------------------------- (1) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 1, "program": { "directives": [], "clauses": [ [ "(div (0) Y (0))", "(no (zero Y))" ], [ "(div X Y (s Z))", "(',' (no (zero X)) (',' (no (zero Y)) (',' (minus X Y U) (div U Y Z))))" ], [ "(minus (0) Y (0))", null ], [ "(minus X (0) X)", null ], [ "(minus (s X) (s Y) Z)", "(minus X Y Z)" ], [ "(zero (0))", null ], [ "(no X)", "(',' X (',' (!) (failure (a))))" ], [ "(no X1)", null ], [ "(failure (b))", null ] ] }, "graph": { "nodes": { "44": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "45": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (zero T21)) (',' (no (zero T22)) (',' (minus T21 T22 X23) (div X23 T22 T24))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T21", "T22" ], "free": ["X23"], "exprvars": [] } }, "49": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "112": { "goal": [{ "clause": -1, "scope": -1, "term": "(div T62 T55 T24)" }], "kb": { "nonunifying": [[ "(zero T55)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T55", "T62" ], "free": [], "exprvars": [] } }, "91": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (zero T45) (',' (',' (!_10) (failure (a))) (',' (minus T38 T45 X23) (div X23 T45 T24))))" }, { "clause": -1, "scope": 11, "term": null }, { "clause": 7, "scope": 10, "term": "(',' (no (zero T45)) (',' (minus T38 T45 X23) (div X23 T45 T24)))" } ], "kb": { "nonunifying": [[ "(zero T38)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T45" ], "free": ["X23"], "exprvars": [] } }, "118": { "goal": [ { "clause": 2, "scope": 14, "term": "(minus T38 T55 X23)" }, { "clause": 3, "scope": 14, "term": "(minus T38 T55 X23)" }, { "clause": 4, "scope": 14, "term": "(minus T38 T55 X23)" } ], "kb": { "nonunifying": [ [ "(zero T38)", "(zero (0))" ], [ "(zero T55)", "(zero (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T55" ], "free": ["X23"], "exprvars": [] } }, "119": { "goal": [ { "clause": 3, "scope": 14, "term": "(minus T38 T55 X23)" }, { "clause": 4, "scope": 14, "term": "(minus T38 T55 X23)" } ], "kb": { "nonunifying": [ [ "(zero T38)", "(zero (0))" ], [ "(zero T55)", "(zero (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T55" ], "free": ["X23"], "exprvars": [] } }, "94": { "goal": [ { "clause": 5, "scope": 12, "term": "(',' (zero T45) (',' (',' (!_10) (failure (a))) (',' (minus T38 T45 X23) (div X23 T45 T24))))" }, { "clause": -1, "scope": 12, "term": null }, { "clause": -1, "scope": 11, "term": null }, { "clause": 7, "scope": 10, "term": "(',' (no (zero T45)) (',' (minus T38 T45 X23) (div X23 T45 T24)))" } ], "kb": { "nonunifying": [[ "(zero T38)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T45" ], "free": ["X23"], "exprvars": [] } }, "51": { "goal": [ { "clause": 6, "scope": 6, "term": "(',' (no (zero T21)) (',' (no (zero T22)) (',' (minus T21 T22 X23) (div X23 T22 T24))))" }, { "clause": 7, "scope": 6, "term": "(',' (no (zero T21)) (',' (no (zero T22)) (',' (minus T21 T22 X23) (div X23 T22 T24))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T21", "T22" ], "free": ["X23"], "exprvars": [] } }, "95": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_10) (failure (a))) (',' (minus T38 (0) X23) (div X23 (0) T24)))" }, { "clause": -1, "scope": 12, "term": null }, { "clause": -1, "scope": 11, "term": null }, { "clause": 7, "scope": 10, "term": "(',' (no (zero (0))) (',' (minus T38 (0) X23) (div X23 (0) T24)))" } ], "kb": { "nonunifying": [[ "(zero T38)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": ["X23"], "exprvars": [] } }, "96": { "goal": [ { "clause": -1, "scope": 12, "term": null }, { "clause": -1, "scope": 11, "term": null }, { "clause": 7, "scope": 10, "term": "(',' (no (zero T45)) (',' (minus T38 T45 X23) (div X23 T45 T24)))" } ], "kb": { "nonunifying": [ [ "(zero T38)", "(zero (0))" ], [ "(zero T45)", "(zero (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T45" ], "free": ["X23"], "exprvars": [] } }, "53": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (zero T29)) (',' (!_6) (failure (a)))) (',' (no (zero T22)) (',' (minus T29 T22 X23) (div X23 T22 T24))))" }, { "clause": 7, "scope": 6, "term": "(',' (no (zero T29)) (',' (no (zero T22)) (',' (minus T29 T22 X23) (div X23 T22 T24))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T29" ], "free": ["X23"], "exprvars": [] } }, "97": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (minus T38 (0) X23) (div X23 (0) T24)))" }], "kb": { "nonunifying": [[ "(zero T38)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": ["X23"], "exprvars": [] } }, "98": { "goal": [{ "clause": 8, "scope": 13, "term": "(',' (failure (a)) (',' (minus T38 (0) X23) (div X23 (0) T24)))" }], "kb": { "nonunifying": [[ "(zero T38)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T38"], "free": ["X23"], "exprvars": [] } }, "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(no (zero T8))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "55": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (zero T29) (',' (',' (!_6) (failure (a))) (',' (no (zero T22)) (',' (minus T29 T22 X23) (div X23 T22 T24)))))" }, { "clause": -1, "scope": 7, "term": null }, { "clause": 7, "scope": 6, "term": "(',' (no (zero T29)) (',' (no (zero T22)) (',' (minus T29 T22 X23) (div X23 T22 T24))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T29" ], "free": ["X23"], "exprvars": [] } }, "99": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "57": { "goal": [ { "clause": 5, "scope": 8, "term": "(',' (zero T29) (',' (',' (!_6) (failure (a))) (',' (no (zero T22)) (',' (minus T29 T22 X23) (div X23 T22 T24)))))" }, { "clause": -1, "scope": 8, "term": null }, { "clause": -1, "scope": 7, "term": null }, { "clause": 7, "scope": 6, "term": "(',' (no (zero T29)) (',' (no (zero T22)) (',' (minus T29 T22 X23) (div X23 T22 T24))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T29" ], "free": ["X23"], "exprvars": [] } }, "59": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_6) (failure (a))) (',' (no (zero T22)) (',' (minus (0) T22 X23) (div X23 T22 T24))))" }, { "clause": -1, "scope": 8, "term": null }, { "clause": -1, "scope": 7, "term": null }, { "clause": 7, "scope": 6, "term": "(',' (no (zero (0))) (',' (no (zero T22)) (',' (minus (0) T22 X23) (div X23 T22 T24))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X23"], "exprvars": [] } }, "16": { "goal": [ { "clause": 6, "scope": 2, "term": "(no (zero T8))" }, { "clause": 7, "scope": 2, "term": "(no (zero T8))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "121": { "goal": [{ "clause": 4, "scope": 14, "term": "(minus T38 T55 X23)" }], "kb": { "nonunifying": [ [ "(zero T38)", "(zero (0))" ], [ "(zero T55)", "(zero (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T55" ], "free": ["X23"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(div T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "3": { "goal": [ { "clause": 0, "scope": 1, "term": "(div T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(div T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": -1, "scope": -1, "term": "(minus T75 T76 X89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T76" ], "free": ["X89"], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(div T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "125": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": 1, "scope": 1, "term": "(div T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "128": { "goal": [ { "clause": 2, "scope": 15, "term": "(minus T75 T76 X89)" }, { "clause": 3, "scope": 15, "term": "(minus T75 T76 X89)" }, { "clause": 4, "scope": 15, "term": "(minus T75 T76 X89)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T76" ], "free": ["X89"], "exprvars": [] } }, "129": { "goal": [{ "clause": 2, "scope": 15, "term": "(minus T75 T76 X89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T76" ], "free": ["X89"], "exprvars": [] } }, "61": { "goal": [ { "clause": -1, "scope": 8, "term": null }, { "clause": -1, "scope": 7, "term": null }, { "clause": 7, "scope": 6, "term": "(',' (no (zero T29)) (',' (no (zero T22)) (',' (minus T29 T22 X23) (div X23 T22 T24))))" } ], "kb": { "nonunifying": [[ "(zero T29)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T29" ], "free": ["X23"], "exprvars": [] } }, "63": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (no (zero T22)) (',' (minus (0) T22 X23) (div X23 T22 T24))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X23"], "exprvars": [] } }, "65": { "goal": [{ "clause": 8, "scope": 9, "term": "(',' (failure (a)) (',' (no (zero T22)) (',' (minus (0) T22 X23) (div X23 T22 T24))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X23"], "exprvars": [] } }, "67": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "69": { "goal": [ { "clause": -1, "scope": 7, "term": null }, { "clause": 7, "scope": 6, "term": "(',' (no (zero T29)) (',' (no (zero T22)) (',' (minus T29 T22 X23) (div X23 T22 T24))))" } ], "kb": { "nonunifying": [[ "(zero T29)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T29" ], "free": ["X23"], "exprvars": [] } }, "130": { "goal": [ { "clause": 3, "scope": 15, "term": "(minus T75 T76 X89)" }, { "clause": 4, "scope": 15, "term": "(minus T75 T76 X89)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T76" ], "free": ["X89"], "exprvars": [] } }, "131": { "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": [] } }, "133": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "134": { "goal": [{ "clause": 3, "scope": 15, "term": "(minus T75 T76 X89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T76" ], "free": ["X89"], "exprvars": [] } }, "135": { "goal": [{ "clause": 4, "scope": 15, "term": "(minus T75 T76 X89)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T75", "T76" ], "free": ["X89"], "exprvars": [] } }, "136": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "137": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "138": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "139": { "goal": [{ "clause": -1, "scope": -1, "term": "(minus T93 T94 X113)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T93", "T94" ], "free": ["X113"], "exprvars": [] } }, "71": { "goal": [{ "clause": 7, "scope": 6, "term": "(',' (no (zero T29)) (',' (no (zero T22)) (',' (minus T29 T22 X23) (div X23 T22 T24))))" }], "kb": { "nonunifying": [[ "(zero T29)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T29" ], "free": ["X23"], "exprvars": [] } }, "73": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (zero T22)) (',' (minus T38 T22 X23) (div X23 T22 T24)))" }], "kb": { "nonunifying": [[ "(zero T38)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T38" ], "free": ["X23"], "exprvars": [] } }, "30": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (call (zero T11)) (',' (!_2) (failure (a))))" }, { "clause": 7, "scope": 2, "term": "(no (zero T11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "31": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (zero T11) (',' (!_2) (failure (a))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 7, "scope": 2, "term": "(no (zero T11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "75": { "goal": [ { "clause": 6, "scope": 10, "term": "(',' (no (zero T22)) (',' (minus T38 T22 X23) (div X23 T22 T24)))" }, { "clause": 7, "scope": 10, "term": "(',' (no (zero T22)) (',' (minus T38 T22 X23) (div X23 T22 T24)))" } ], "kb": { "nonunifying": [[ "(zero T38)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T38" ], "free": ["X23"], "exprvars": [] } }, "32": { "goal": [ { "clause": 5, "scope": 4, "term": "(',' (zero T11) (',' (!_2) (failure (a))))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 7, "scope": 2, "term": "(no (zero T11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "76": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (zero T45)) (',' (!_10) (failure (a)))) (',' (minus T38 T45 X23) (div X23 T45 T24)))" }, { "clause": 7, "scope": 10, "term": "(',' (no (zero T45)) (',' (minus T38 T45 X23) (div X23 T45 T24)))" } ], "kb": { "nonunifying": [[ "(zero T38)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T45" ], "free": ["X23"], "exprvars": [] } }, "34": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_2) (failure (a)))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 7, "scope": 2, "term": "(no (zero (0)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "35": { "goal": [ { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 7, "scope": 2, "term": "(no (zero T11))" } ], "kb": { "nonunifying": [[ "(zero T11)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "37": { "goal": [{ "clause": -1, "scope": -1, "term": "(failure (a))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "38": { "goal": [{ "clause": 8, "scope": 5, "term": "(failure (a))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "140": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "100": { "goal": [ { "clause": -1, "scope": 11, "term": null }, { "clause": 7, "scope": 10, "term": "(',' (no (zero T45)) (',' (minus T38 T45 X23) (div X23 T45 T24)))" } ], "kb": { "nonunifying": [ [ "(zero T38)", "(zero (0))" ], [ "(zero T45)", "(zero (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T45" ], "free": ["X23"], "exprvars": [] } }, "102": { "goal": [{ "clause": 7, "scope": 10, "term": "(',' (no (zero T45)) (',' (minus T38 T45 X23) (div X23 T45 T24)))" }], "kb": { "nonunifying": [ [ "(zero T38)", "(zero (0))" ], [ "(zero T45)", "(zero (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T45" ], "free": ["X23"], "exprvars": [] } }, "105": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (minus T38 T55 X23) (div X23 T55 T24))" }], "kb": { "nonunifying": [ [ "(zero T38)", "(zero (0))" ], [ "(zero T55)", "(zero (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T55" ], "free": ["X23"], "exprvars": [] } }, "109": { "goal": [{ "clause": -1, "scope": -1, "term": "(minus T38 T55 X23)" }], "kb": { "nonunifying": [ [ "(zero T38)", "(zero (0))" ], [ "(zero T55)", "(zero (0))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T38", "T55" ], "free": ["X23"], "exprvars": [] } }, "40": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 7, "scope": 2, "term": "(no (zero T11))" } ], "kb": { "nonunifying": [[ "(zero T11)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } }, "41": { "goal": [{ "clause": 7, "scope": 2, "term": "(no (zero T11))" }], "kb": { "nonunifying": [[ "(zero T11)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T11"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 4, "label": "PARALLEL" }, { "from": 3, "to": 5, "label": "PARALLEL" }, { "from": 4, "to": 11, "label": "EVAL with clause\ndiv(0, X6, 0) :- no(zero(X6)).\nand substitutionT1 -> 0,\nT2 -> T8,\nX6 -> T8,\nT3 -> 0" }, { "from": 4, "to": 12, "label": "EVAL-BACKTRACK" }, { "from": 5, "to": 47, "label": "EVAL with clause\ndiv(X20, X21, s(X22)) :- ','(no(zero(X20)), ','(no(zero(X21)), ','(minus(X20, X21, X23), div(X23, X21, X22)))).\nand substitutionT1 -> T21,\nX20 -> T21,\nT2 -> T22,\nX21 -> T22,\nX22 -> T24,\nT3 -> s(T24),\nT23 -> T24" }, { "from": 5, "to": 49, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 16, "label": "CASE" }, { "from": 16, "to": 30, "label": "ONLY EVAL with clause\nno(X9) :- ','(call(X9), ','(!_2, failure(a))).\nand substitutionT8 -> T11,\nX9 -> zero(T11)" }, { "from": 30, "to": 31, "label": "CALL" }, { "from": 31, "to": 32, "label": "CASE" }, { "from": 32, "to": 34, "label": "EVAL with clause\nzero(0).\nand substitutionT11 -> 0" }, { "from": 32, "to": 35, "label": "EVAL-BACKTRACK" }, { "from": 34, "to": 37, "label": "CUT" }, { "from": 35, "to": 40, "label": "FAILURE" }, { "from": 37, "to": 38, "label": "CASE" }, { "from": 38, "to": 39, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 40, "to": 41, "label": "FAILURE" }, { "from": 41, "to": 44, "label": "ONLY EVAL with clause\nno(X12).\nand substitutionT11 -> T14,\nX12 -> zero(T14)" }, { "from": 44, "to": 45, "label": "SUCCESS" }, { "from": 47, "to": 51, "label": "CASE" }, { "from": 51, "to": 53, "label": "ONLY EVAL with clause\nno(X28) :- ','(call(X28), ','(!_6, failure(a))).\nand substitutionT21 -> T29,\nX28 -> zero(T29)" }, { "from": 53, "to": 55, "label": "CALL" }, { "from": 55, "to": 57, "label": "CASE" }, { "from": 57, "to": 59, "label": "EVAL with clause\nzero(0).\nand substitutionT29 -> 0" }, { "from": 57, "to": 61, "label": "EVAL-BACKTRACK" }, { "from": 59, "to": 63, "label": "CUT" }, { "from": 61, "to": 69, "label": "FAILURE" }, { "from": 63, "to": 65, "label": "CASE" }, { "from": 65, "to": 67, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 69, "to": 71, "label": "FAILURE" }, { "from": 71, "to": 73, "label": "ONLY EVAL with clause\nno(X37).\nand substitutionT29 -> T38,\nX37 -> zero(T38)" }, { "from": 73, "to": 75, "label": "CASE" }, { "from": 75, "to": 76, "label": "ONLY EVAL with clause\nno(X44) :- ','(call(X44), ','(!_10, failure(a))).\nand substitutionT22 -> T45,\nX44 -> zero(T45)" }, { "from": 76, "to": 91, "label": "CALL" }, { "from": 91, "to": 94, "label": "CASE" }, { "from": 94, "to": 95, "label": "EVAL with clause\nzero(0).\nand substitutionT45 -> 0" }, { "from": 94, "to": 96, "label": "EVAL-BACKTRACK" }, { "from": 95, "to": 97, "label": "CUT" }, { "from": 96, "to": 100, "label": "FAILURE" }, { "from": 97, "to": 98, "label": "CASE" }, { "from": 98, "to": 99, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 100, "to": 102, "label": "FAILURE" }, { "from": 102, "to": 105, "label": "ONLY EVAL with clause\nno(X59).\nand substitutionT45 -> T55,\nX59 -> zero(T55)" }, { "from": 105, "to": 109, "label": "SPLIT 1" }, { "from": 105, "to": 112, "label": "SPLIT 2\nnew knowledge:\nT38 is ground\nT55 is ground\nT62 is ground\nreplacements:X23 -> T62" }, { "from": 109, "to": 118, "label": "CASE" }, { "from": 112, "to": 1, "label": "INSTANCE with matching:\nT1 -> T62\nT2 -> T55\nT3 -> T24" }, { "from": 118, "to": 119, "label": "BACKTRACK\nfor clause: minus(0, Y, 0)\nwith clash: (zero(T38), zero(0))" }, { "from": 119, "to": 121, "label": "BACKTRACK\nfor clause: minus(X, 0, X)\nwith clash: (zero(T55), zero(0))" }, { "from": 121, "to": 124, "label": "EVAL with clause\nminus(s(X86), s(X87), X88) :- minus(X86, X87, X88).\nand substitutionX86 -> T75,\nT38 -> s(T75),\nX87 -> T76,\nT55 -> s(T76),\nX23 -> X89,\nX88 -> X89" }, { "from": 121, "to": 125, "label": "EVAL-BACKTRACK" }, { "from": 124, "to": 128, "label": "CASE" }, { "from": 128, "to": 129, "label": "PARALLEL" }, { "from": 128, "to": 130, "label": "PARALLEL" }, { "from": 129, "to": 131, "label": "EVAL with clause\nminus(0, X96, 0).\nand substitutionT75 -> 0,\nT76 -> T83,\nX96 -> T83,\nX89 -> 0" }, { "from": 129, "to": 132, "label": "EVAL-BACKTRACK" }, { "from": 130, "to": 134, "label": "PARALLEL" }, { "from": 130, "to": 135, "label": "PARALLEL" }, { "from": 131, "to": 133, "label": "SUCCESS" }, { "from": 134, "to": 136, "label": "EVAL with clause\nminus(X101, 0, X101).\nand substitutionT75 -> T88,\nX101 -> T88,\nT76 -> 0,\nX89 -> T88" }, { "from": 134, "to": 137, "label": "EVAL-BACKTRACK" }, { "from": 135, "to": 139, "label": "EVAL with clause\nminus(s(X110), s(X111), X112) :- minus(X110, X111, X112).\nand substitutionX110 -> T93,\nT75 -> s(T93),\nX111 -> T94,\nT76 -> s(T94),\nX89 -> X113,\nX112 -> X113" }, { "from": 135, "to": 140, "label": "EVAL-BACKTRACK" }, { "from": 136, "to": 138, "label": "SUCCESS" }, { "from": 139, "to": 124, "label": "INSTANCE with matching:\nT75 -> T93\nT76 -> T94\nX89 -> X113" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f1_in(0, T14) -> f1_out1(0) f1_in(T38, T55) -> U1(f105_in(T38, T55), T38, T55) U1(f105_out1(X23, T24), T38, T55) -> f1_out1(s(T24)) f124_in(0, T83) -> f124_out1(0) f124_in(T88, 0) -> f124_out1(T88) f124_in(s(T93), s(T94)) -> U2(f124_in(T93, T94), s(T93), s(T94)) U2(f124_out1(X113), s(T93), s(T94)) -> f124_out1(X113) f109_in(s(T75), s(T76)) -> U3(f124_in(T75, T76), s(T75), s(T76)) U3(f124_out1(X89), s(T75), s(T76)) -> f109_out1(X89) f105_in(T38, T55) -> U4(f109_in(T38, T55), T38, T55) U4(f109_out1(T62), T38, T55) -> U5(f1_in(T62, T55), T38, T55, T62) U5(f1_out1(T24), T38, T55, T62) -> f105_out1(T62, T24) Q is empty. ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T38, T55) -> U1^1(f105_in(T38, T55), T38, T55) F1_IN(T38, T55) -> F105_IN(T38, T55) F124_IN(s(T93), s(T94)) -> U2^1(f124_in(T93, T94), s(T93), s(T94)) F124_IN(s(T93), s(T94)) -> F124_IN(T93, T94) F109_IN(s(T75), s(T76)) -> U3^1(f124_in(T75, T76), s(T75), s(T76)) F109_IN(s(T75), s(T76)) -> F124_IN(T75, T76) F105_IN(T38, T55) -> U4^1(f109_in(T38, T55), T38, T55) F105_IN(T38, T55) -> F109_IN(T38, T55) U4^1(f109_out1(T62), T38, T55) -> U5^1(f1_in(T62, T55), T38, T55, T62) U4^1(f109_out1(T62), T38, T55) -> F1_IN(T62, T55) The TRS R consists of the following rules: f1_in(0, T14) -> f1_out1(0) f1_in(T38, T55) -> U1(f105_in(T38, T55), T38, T55) U1(f105_out1(X23, T24), T38, T55) -> f1_out1(s(T24)) f124_in(0, T83) -> f124_out1(0) f124_in(T88, 0) -> f124_out1(T88) f124_in(s(T93), s(T94)) -> U2(f124_in(T93, T94), s(T93), s(T94)) U2(f124_out1(X113), s(T93), s(T94)) -> f124_out1(X113) f109_in(s(T75), s(T76)) -> U3(f124_in(T75, T76), s(T75), s(T76)) U3(f124_out1(X89), s(T75), s(T76)) -> f109_out1(X89) f105_in(T38, T55) -> U4(f109_in(T38, T55), T38, T55) U4(f109_out1(T62), T38, T55) -> U5(f1_in(T62, T55), T38, T55, T62) U5(f1_out1(T24), T38, T55, T62) -> f105_out1(T62, T24) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 6 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: F124_IN(s(T93), s(T94)) -> F124_IN(T93, T94) The TRS R consists of the following rules: f1_in(0, T14) -> f1_out1(0) f1_in(T38, T55) -> U1(f105_in(T38, T55), T38, T55) U1(f105_out1(X23, T24), T38, T55) -> f1_out1(s(T24)) f124_in(0, T83) -> f124_out1(0) f124_in(T88, 0) -> f124_out1(T88) f124_in(s(T93), s(T94)) -> U2(f124_in(T93, T94), s(T93), s(T94)) U2(f124_out1(X113), s(T93), s(T94)) -> f124_out1(X113) f109_in(s(T75), s(T76)) -> U3(f124_in(T75, T76), s(T75), s(T76)) U3(f124_out1(X89), s(T75), s(T76)) -> f109_out1(X89) f105_in(T38, T55) -> U4(f109_in(T38, T55), T38, T55) U4(f109_out1(T62), T38, T55) -> U5(f1_in(T62, T55), T38, T55, T62) U5(f1_out1(T24), T38, T55, T62) -> f105_out1(T62, T24) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: F124_IN(s(T93), s(T94)) -> F124_IN(T93, T94) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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: *F124_IN(s(T93), s(T94)) -> F124_IN(T93, T94) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: F1_IN(T38, T55) -> F105_IN(T38, T55) F105_IN(T38, T55) -> U4^1(f109_in(T38, T55), T38, T55) U4^1(f109_out1(T62), T38, T55) -> F1_IN(T62, T55) The TRS R consists of the following rules: f1_in(0, T14) -> f1_out1(0) f1_in(T38, T55) -> U1(f105_in(T38, T55), T38, T55) U1(f105_out1(X23, T24), T38, T55) -> f1_out1(s(T24)) f124_in(0, T83) -> f124_out1(0) f124_in(T88, 0) -> f124_out1(T88) f124_in(s(T93), s(T94)) -> U2(f124_in(T93, T94), s(T93), s(T94)) U2(f124_out1(X113), s(T93), s(T94)) -> f124_out1(X113) f109_in(s(T75), s(T76)) -> U3(f124_in(T75, T76), s(T75), s(T76)) U3(f124_out1(X89), s(T75), s(T76)) -> f109_out1(X89) f105_in(T38, T55) -> U4(f109_in(T38, T55), T38, T55) U4(f109_out1(T62), T38, T55) -> U5(f1_in(T62, T55), T38, T55, T62) U5(f1_out1(T24), T38, T55, T62) -> f105_out1(T62, T24) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. F1_IN(T38, T55) -> F105_IN(T38, T55) U4^1(f109_out1(T62), T38, T55) -> F1_IN(T62, T55) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U4^1_3(x_1, ..., x_3) ) = max{0, 2x_1 - 2} POL( f109_in_2(x_1, x_2) ) = x_1 + 1 POL( s_1(x_1) ) = 2x_1 + 1 POL( U3_3(x_1, ..., x_3) ) = max{0, 2x_1 - 2} POL( f124_in_2(x_1, x_2) ) = x_1 + 2 POL( 0 ) = 0 POL( f124_out1_1(x_1) ) = x_1 + 2 POL( U2_3(x_1, ..., x_3) ) = max{0, 2x_1 - 1} POL( f109_out1_1(x_1) ) = 2x_1 + 2 POL( F1_IN_2(x_1, x_2) ) = 2x_1 + 1 POL( F105_IN_2(x_1, x_2) ) = 2x_1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: f109_in(s(T75), s(T76)) -> U3(f124_in(T75, T76), s(T75), s(T76)) f124_in(0, T83) -> f124_out1(0) f124_in(T88, 0) -> f124_out1(T88) f124_in(s(T93), s(T94)) -> U2(f124_in(T93, T94), s(T93), s(T94)) U3(f124_out1(X89), s(T75), s(T76)) -> f109_out1(X89) U2(f124_out1(X113), s(T93), s(T94)) -> f124_out1(X113) ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: F105_IN(T38, T55) -> U4^1(f109_in(T38, T55), T38, T55) The TRS R consists of the following rules: f1_in(0, T14) -> f1_out1(0) f1_in(T38, T55) -> U1(f105_in(T38, T55), T38, T55) U1(f105_out1(X23, T24), T38, T55) -> f1_out1(s(T24)) f124_in(0, T83) -> f124_out1(0) f124_in(T88, 0) -> f124_out1(T88) f124_in(s(T93), s(T94)) -> U2(f124_in(T93, T94), s(T93), s(T94)) U2(f124_out1(X113), s(T93), s(T94)) -> f124_out1(X113) f109_in(s(T75), s(T76)) -> U3(f124_in(T75, T76), s(T75), s(T76)) U3(f124_out1(X89), s(T75), s(T76)) -> f109_out1(X89) f105_in(T38, T55) -> U4(f109_in(T38, T55), T38, T55) U4(f109_out1(T62), T38, T55) -> U5(f1_in(T62, T55), T38, T55, T62) U5(f1_out1(T24), T38, T55, T62) -> f105_out1(T62, T24) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (16) TRUE