/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) BuiltinConflictTransformerProof [EQUIVALENT, 0 ms] (2) Prolog (3) PrologToDTProblemTransformerProof [SOUND, 46 ms] (4) TRIPLES (5) TriplesToPiDPProof [SOUND, 0 ms] (6) PiDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) PiDP (10) UsableRulesProof [EQUIVALENT, 0 ms] (11) PiDP (12) PiDPToQDPProof [SOUND, 4 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] (15) YES (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPQMonotonicMRRProof [EQUIVALENT, 32 ms] (20) QDP (21) PisEmptyProof [EQUIVALENT, 0 ms] (22) YES ---------------------------------------- (0) Obligation: Clauses: minus(X, Y, Z) :- ','(=(X, 0), ','(!, =(Z, 0))). minus(X, Y, Z) :- ','(=(Y, 0), ','(!, =(Z, X))). minus(X, Y, Z) :- ','(=(X, s(A)), ','(=(Y, s(B)), minus(A, B, Z))). div(X, Y, Z) :- ','(=(Y, 0), ','(!, fail)). div(X, Y, Z) :- ','(=(X, 0), ','(!, =(Z, 0))). div(X, Y, Z) :- ','(minus(X, Y, U), ','(div(U, Y, V), =(Z, s(V)))). =(X, X). Query: div(g,g,a) ---------------------------------------- (1) BuiltinConflictTransformerProof (EQUIVALENT) Renamed defined predicates conflicting with built-in predicates [PROLOG]. ---------------------------------------- (2) Obligation: Clauses: minus(X, Y, Z) :- ','(user_defined_=(X, 0), ','(!, user_defined_=(Z, 0))). minus(X, Y, Z) :- ','(user_defined_=(Y, 0), ','(!, user_defined_=(Z, X))). minus(X, Y, Z) :- ','(user_defined_=(X, s(A)), ','(user_defined_=(Y, s(B)), minus(A, B, Z))). div(X, Y, Z) :- ','(user_defined_=(Y, 0), ','(!, fail)). div(X, Y, Z) :- ','(user_defined_=(X, 0), ','(!, user_defined_=(Z, 0))). div(X, Y, Z) :- ','(minus(X, Y, U), ','(div(U, Y, V), user_defined_=(Z, s(V)))). user_defined_=(X, X). Query: div(g,g,a) ---------------------------------------- (3) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(minus X Y Z)", "(',' (user_defined_= X (0)) (',' (!) (user_defined_= Z (0))))" ], [ "(minus X Y Z)", "(',' (user_defined_= Y (0)) (',' (!) (user_defined_= Z X)))" ], [ "(minus X Y Z)", "(',' (user_defined_= X (s A)) (',' (user_defined_= Y (s B)) (minus A B Z)))" ], [ "(div X Y Z)", "(',' (user_defined_= Y (0)) (',' (!) (fail)))" ], [ "(div X Y Z)", "(',' (user_defined_= X (0)) (',' (!) (user_defined_= Z (0))))" ], [ "(div X Y Z)", "(',' (minus X Y U) (',' (div U Y V) (user_defined_= Z (s V))))" ], [ "(user_defined_= X X)", null ] ] }, "graph": { "nodes": { "type": "Nodes", "476": { "goal": [ { "clause": 6, "scope": 6, "term": "(',' (user_defined_= T52 (0)) (',' (!_5) (user_defined_= X61 (0))))" }, { "clause": -1, "scope": 6, "term": null }, { "clause": 1, "scope": 5, "term": "(minus T52 T53 X40)" }, { "clause": 2, "scope": 5, "term": "(minus T52 T53 X40)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T53 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T52 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T52", "T53" ], "free": [ "X9", "X21", "X40", "X61" ], "exprvars": [] } }, "513": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (user_defined_= T66 (s X95)) (',' (user_defined_= T67 (s X96)) (minus X95 X96 X97)))" }], "kb": { "nonunifying": [ [ "(user_defined_= T67 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T66 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T66", "T67" ], "free": [ "X9", "X21", "X97", "X95", "X96" ], "exprvars": [] } }, "557": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= T97 (0)) (',' (!_10) (user_defined_= X151 T96)))" }, { "clause": 2, "scope": 10, "term": "(minus T96 T97 X97)" } ], "kb": { "nonunifying": [[ "(user_defined_= T96 (0))", "(user_defined_= X133 X133)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T97" ], "free": [ "X97", "X133", "X151" ], "exprvars": [] } }, "92": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "515": { "goal": [{ "clause": 6, "scope": 8, "term": "(',' (user_defined_= T66 (s X95)) (',' (user_defined_= T67 (s X96)) (minus X95 X96 X97)))" }], "kb": { "nonunifying": [ [ "(user_defined_= T67 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T66 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T66", "T67" ], "free": [ "X9", "X21", "X97", "X95", "X96" ], "exprvars": [] } }, "93": { "goal": [ { "clause": 4, "scope": 1, "term": "(div T7 T8 T3)" }, { "clause": 5, "scope": 1, "term": "(div T7 T8 T3)" } ], "kb": { "nonunifying": [[ "(user_defined_= T8 (0))", "(user_defined_= X9 X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": ["X9"], "exprvars": [] } }, "98": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= T20 (0)) (',' (!_1) (user_defined_= T23 (0))))" }, { "clause": 5, "scope": 1, "term": "(div T20 T21 T3)" } ], "kb": { "nonunifying": [[ "(user_defined_= T21 (0))", "(user_defined_= X9 X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X9"], "exprvars": [] } }, "11": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (fail))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 4, "scope": 1, "term": "(div T7 (0) T3)" }, { "clause": 5, "scope": 1, "term": "(div T7 (0) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "99": { "goal": [ { "clause": 6, "scope": 3, "term": "(',' (user_defined_= T20 (0)) (',' (!_1) (user_defined_= T23 (0))))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 5, "scope": 1, "term": "(div T20 T21 T3)" } ], "kb": { "nonunifying": [[ "(user_defined_= T21 (0))", "(user_defined_= X9 X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X9"], "exprvars": [] } }, "14": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 4, "scope": 1, "term": "(div T7 T8 T3)" }, { "clause": 5, "scope": 1, "term": "(div T7 T8 T3)" } ], "kb": { "nonunifying": [[ "(user_defined_= T8 (0))", "(user_defined_= X9 X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": ["X9"], "exprvars": [] } }, "16": { "goal": [{ "clause": -1, "scope": -1, "term": "(fail)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "484": { "goal": [ { "clause": -1, "scope": 6, "term": null }, { "clause": 1, "scope": 5, "term": "(minus T52 T53 X40)" }, { "clause": 2, "scope": 5, "term": "(minus T52 T53 X40)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T53 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T52 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T52", "T53" ], "free": [ "X9", "X21", "X40" ], "exprvars": [] } }, "561": { "goal": [ { "clause": 6, "scope": 13, "term": "(',' (user_defined_= T97 (0)) (',' (!_10) (user_defined_= X151 T96)))" }, { "clause": -1, "scope": 13, "term": null }, { "clause": 2, "scope": 10, "term": "(minus T96 T97 X97)" } ], "kb": { "nonunifying": [[ "(user_defined_= T96 (0))", "(user_defined_= X133 X133)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T97" ], "free": [ "X97", "X133", "X151" ], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(div T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "488": { "goal": [ { "clause": 1, "scope": 5, "term": "(minus T52 T53 X40)" }, { "clause": 2, "scope": 5, "term": "(minus T52 T53 X40)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T53 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T52 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T52", "T53" ], "free": [ "X9", "X21", "X40" ], "exprvars": [] } }, "521": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (user_defined_= T67 (s X96)) (minus T73 X96 X97))" }], "kb": { "nonunifying": [[ "(user_defined_= T67 (0))", "(user_defined_= X9 X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T67", "T73" ], "free": [ "X9", "X97", "X96" ], "exprvars": [] } }, "5": { "goal": [ { "clause": 3, "scope": 1, "term": "(div T1 T2 T3)" }, { "clause": 4, "scope": 1, "term": "(div T1 T2 T3)" }, { "clause": 5, "scope": 1, "term": "(div T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "522": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= T8 (0)) (',' (!_1) (fail)))" }, { "clause": 4, "scope": 1, "term": "(div T7 T8 T3)" }, { "clause": 5, "scope": 1, "term": "(div T7 T8 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "523": { "goal": [{ "clause": 6, "scope": 9, "term": "(',' (user_defined_= T67 (s X96)) (minus T73 X96 X97))" }], "kb": { "nonunifying": [[ "(user_defined_= T67 (0))", "(user_defined_= X9 X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T67", "T73" ], "free": [ "X9", "X97", "X96" ], "exprvars": [] } }, "524": { "goal": [{ "clause": -1, "scope": -1, "term": "(minus T73 T80 X97)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T73", "T80" ], "free": ["X97"], "exprvars": [] } }, "568": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_10) (user_defined_= X151 T96))" }, { "clause": -1, "scope": 13, "term": null }, { "clause": 2, "scope": 10, "term": "(minus T96 (0) X97)" } ], "kb": { "nonunifying": [[ "(user_defined_= T96 (0))", "(user_defined_= X133 X133)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T96"], "free": [ "X97", "X133", "X151" ], "exprvars": [] } }, "8": { "goal": [ { "clause": 6, "scope": 2, "term": "(',' (user_defined_= T8 (0)) (',' (!_1) (fail)))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 4, "scope": 1, "term": "(div T7 T8 T3)" }, { "clause": 5, "scope": 1, "term": "(div T7 T8 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T7", "T8" ], "free": [], "exprvars": [] } }, "525": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "607": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (user_defined_= T108 (s X180)) (',' (user_defined_= T109 (s X181)) (minus X180 X181 X182)))" }], "kb": { "nonunifying": [ [ "(user_defined_= T108 (0))", "(user_defined_= X133 X133)" ], [ "(user_defined_= T109 (0))", "(user_defined_= X154 X154)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T108", "T109" ], "free": [ "X133", "X154", "X182", "X180", "X181" ], "exprvars": [] } }, "609": { "goal": [{ "clause": 6, "scope": 15, "term": "(',' (user_defined_= T108 (s X180)) (',' (user_defined_= T109 (s X181)) (minus X180 X181 X182)))" }], "kb": { "nonunifying": [ [ "(user_defined_= T108 (0))", "(user_defined_= X133 X133)" ], [ "(user_defined_= T109 (0))", "(user_defined_= X154 X154)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T108", "T109" ], "free": [ "X133", "X154", "X182", "X180", "X181" ], "exprvars": [] } }, "571": { "goal": [ { "clause": -1, "scope": 13, "term": null }, { "clause": 2, "scope": 10, "term": "(minus T96 T97 X97)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T96 (0))", "(user_defined_= X133 X133)" ], [ "(user_defined_= T97 (0))", "(user_defined_= X154 X154)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T97" ], "free": [ "X97", "X133", "X154" ], "exprvars": [] } }, "574": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= X151 T96)" }], "kb": { "nonunifying": [[ "(user_defined_= T96 (0))", "(user_defined_= X133 X133)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T96"], "free": [ "X133", "X151" ], "exprvars": [] } }, "531": { "goal": [ { "clause": 0, "scope": 10, "term": "(minus T73 T80 X97)" }, { "clause": 1, "scope": 10, "term": "(minus T73 T80 X97)" }, { "clause": 2, "scope": 10, "term": "(minus T73 T80 X97)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T73", "T80" ], "free": ["X97"], "exprvars": [] } }, "576": { "goal": [{ "clause": 6, "scope": 14, "term": "(user_defined_= X151 T96)" }], "kb": { "nonunifying": [[ "(user_defined_= T96 (0))", "(user_defined_= X133 X133)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T96"], "free": [ "X133", "X151" ], "exprvars": [] } }, "335": { "goal": [{ "clause": -1, "scope": -1, "term": "(minus T39 T40 X40)" }], "kb": { "nonunifying": [ [ "(user_defined_= T40 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T39 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T39", "T40" ], "free": [ "X9", "X21", "X40" ], "exprvars": [] } }, "611": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (user_defined_= T109 (s X181)) (minus T115 X181 X182))" }], "kb": { "nonunifying": [[ "(user_defined_= T109 (0))", "(user_defined_= X154 X154)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T109", "T115" ], "free": [ "X154", "X182", "X181" ], "exprvars": [] } }, "535": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= T87 (0)) (',' (!_10) (user_defined_= X130 (0))))" }, { "clause": 1, "scope": 10, "term": "(minus T87 T88 X97)" }, { "clause": 2, "scope": 10, "term": "(minus T87 T88 X97)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T87", "T88" ], "free": [ "X97", "X130" ], "exprvars": [] } }, "612": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "536": { "goal": [ { "clause": 6, "scope": 11, "term": "(',' (user_defined_= T87 (0)) (',' (!_10) (user_defined_= X130 (0))))" }, { "clause": -1, "scope": 11, "term": null }, { "clause": 1, "scope": 10, "term": "(minus T87 T88 X97)" }, { "clause": 2, "scope": 10, "term": "(minus T87 T88 X97)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T87", "T88" ], "free": [ "X97", "X130" ], "exprvars": [] } }, "537": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_10) (user_defined_= X130 (0)))" }, { "clause": -1, "scope": 11, "term": null }, { "clause": 1, "scope": 10, "term": "(minus (0) T88 X97)" }, { "clause": 2, "scope": 10, "term": "(minus (0) T88 X97)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T88"], "free": [ "X97", "X130" ], "exprvars": [] } }, "538": { "goal": [ { "clause": -1, "scope": 11, "term": null }, { "clause": 1, "scope": 10, "term": "(minus T87 T88 X97)" }, { "clause": 2, "scope": 10, "term": "(minus T87 T88 X97)" } ], "kb": { "nonunifying": [[ "(user_defined_= T87 (0))", "(user_defined_= X133 X133)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T87", "T88" ], "free": [ "X97", "X133" ], "exprvars": [] } }, "539": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= X130 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X130"], "exprvars": [] } }, "583": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "100": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (user_defined_= T23 (0)))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 5, "scope": 1, "term": "(div (0) T21 T3)" } ], "kb": { "nonunifying": [[ "(user_defined_= T21 (0))", "(user_defined_= X9 X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X9"], "exprvars": [] } }, "463": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= T52 (0)) (',' (!_5) (user_defined_= X61 (0))))" }, { "clause": 1, "scope": 5, "term": "(minus T52 T53 X40)" }, { "clause": 2, "scope": 5, "term": "(minus T52 T53 X40)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T53 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T52 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T52", "T53" ], "free": [ "X9", "X21", "X40", "X61" ], "exprvars": [] } }, "540": { "goal": [{ "clause": 6, "scope": 12, "term": "(user_defined_= X130 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X130"], "exprvars": [] } }, "584": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "101": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 5, "scope": 1, "term": "(div T20 T21 T3)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T21 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T20 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": [ "X9", "X21" ], "exprvars": [] } }, "387": { "goal": [ { "clause": 0, "scope": 5, "term": "(minus T39 T40 X40)" }, { "clause": 1, "scope": 5, "term": "(minus T39 T40 X40)" }, { "clause": 2, "scope": 5, "term": "(minus T39 T40 X40)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T40 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T39 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T39", "T40" ], "free": [ "X9", "X21", "X40" ], "exprvars": [] } }, "344": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (div T45 T40 X41) (user_defined_= T42 (s X41)))" }], "kb": { "nonunifying": [[ "(user_defined_= T40 (0))", "(user_defined_= X9 X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T45" ], "free": [ "X9", "X41" ], "exprvars": [] } }, "103": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= T23 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "543": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "587": { "goal": [{ "clause": 2, "scope": 10, "term": "(minus T96 T97 X97)" }], "kb": { "nonunifying": [ [ "(user_defined_= T96 (0))", "(user_defined_= X133 X133)" ], [ "(user_defined_= T97 (0))", "(user_defined_= X154 X154)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T96", "T97" ], "free": [ "X97", "X133", "X154" ], "exprvars": [] } }, "620": { "goal": [{ "clause": 6, "scope": 16, "term": "(',' (user_defined_= T109 (s X181)) (minus T115 X181 X182))" }], "kb": { "nonunifying": [[ "(user_defined_= T109 (0))", "(user_defined_= X154 X154)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T109", "T115" ], "free": [ "X154", "X182", "X181" ], "exprvars": [] } }, "104": { "goal": [{ "clause": 6, "scope": 4, "term": "(user_defined_= T23 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "302": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (minus T39 T40 X40) (',' (div X40 T40 X41) (user_defined_= T42 (s X41))))" }], "kb": { "nonunifying": [ [ "(user_defined_= T40 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T39 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T39", "T40" ], "free": [ "X9", "X21", "X40", "X41" ], "exprvars": [] } }, "544": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "621": { "goal": [{ "clause": -1, "scope": -1, "term": "(minus T115 T122 X182)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T115", "T122" ], "free": ["X182"], "exprvars": [] } }, "105": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "622": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "106": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "502": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (user_defined_= T60 (0)) (',' (!_5) (user_defined_= X74 T59)))" }, { "clause": 2, "scope": 5, "term": "(minus T59 T60 X40)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T60 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T59 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T60" ], "free": [ "X9", "X21", "X40", "X74" ], "exprvars": [] } }, "546": { "goal": [ { "clause": 1, "scope": 10, "term": "(minus T87 T88 X97)" }, { "clause": 2, "scope": 10, "term": "(minus T87 T88 X97)" } ], "kb": { "nonunifying": [[ "(user_defined_= T87 (0))", "(user_defined_= X133 X133)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T87", "T88" ], "free": [ "X97", "X133" ], "exprvars": [] } }, "623": { "goal": [{ "clause": -1, "scope": -1, "term": "(div T45 T40 X41)" }], "kb": { "nonunifying": [[ "(user_defined_= T40 (0))", "(user_defined_= X9 X9)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T40", "T45" ], "free": [ "X9", "X41" ], "exprvars": [] } }, "107": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "503": { "goal": [ { "clause": 6, "scope": 7, "term": "(',' (user_defined_= T60 (0)) (',' (!_5) (user_defined_= X74 T59)))" }, { "clause": -1, "scope": 7, "term": null }, { "clause": 2, "scope": 5, "term": "(minus T59 T60 X40)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T60 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T59 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T60" ], "free": [ "X9", "X21", "X40", "X74" ], "exprvars": [] } }, "108": { "goal": [{ "clause": 5, "scope": 1, "term": "(div T20 T21 T3)" }], "kb": { "nonunifying": [ [ "(user_defined_= T21 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T20 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": [ "X9", "X21" ], "exprvars": [] } }, "504": { "goal": [ { "clause": -1, "scope": 7, "term": null }, { "clause": 2, "scope": 5, "term": "(minus T59 T60 X40)" } ], "kb": { "nonunifying": [ [ "(user_defined_= T60 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T59 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T60" ], "free": [ "X9", "X21", "X40" ], "exprvars": [] } }, "625": { "goal": [{ "clause": -1, "scope": -1, "term": "(user_defined_= T42 (s T127))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "626": { "goal": [{ "clause": 6, "scope": 17, "term": "(user_defined_= T42 (s T127))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "506": { "goal": [{ "clause": 2, "scope": 5, "term": "(minus T59 T60 X40)" }], "kb": { "nonunifying": [ [ "(user_defined_= T60 (0))", "(user_defined_= X9 X9)" ], [ "(user_defined_= T59 (0))", "(user_defined_= X21 X21)" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T59", "T60" ], "free": [ "X9", "X21", "X40" ], "exprvars": [] } }, "627": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "628": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "629": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 5, "label": "CASE" }, { "from": 5, "to": 6, "label": "ONLY EVAL with clause\ndiv(X4, X5, X6) :- ','(user_defined_=(X5, 0), ','(!_1, fail)).\nand substitutionT1 -> T7,\nX4 -> T7,\nT2 -> T8,\nX5 -> T8,\nT3 -> T9,\nX6 -> T9" }, { "from": 6, "to": 8, "label": "CASE" }, { "from": 8, "to": 11, "label": "EVAL with clause\nuser_defined_=(X9, X9).\nand substitutionT8 -> 0,\nX9 -> 0,\nT12 -> 0" }, { "from": 8, "to": 14, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 16, "label": "CUT" }, { "from": 14, "to": 93, "label": "FAILURE" }, { "from": 16, "to": 92, "label": "FAILURE" }, { "from": 93, "to": 98, "label": "ONLY EVAL with clause\ndiv(X16, X17, X18) :- ','(user_defined_=(X16, 0), ','(!_1, user_defined_=(X18, 0))).\nand substitutionT7 -> T20,\nX16 -> T20,\nT8 -> T21,\nX17 -> T21,\nT3 -> T23,\nX18 -> T23,\nT22 -> T23" }, { "from": 98, "to": 99, "label": "CASE" }, { "from": 99, "to": 100, "label": "EVAL with clause\nuser_defined_=(X21, X21).\nand substitutionT20 -> 0,\nX21 -> 0,\nT26 -> 0" }, { "from": 99, "to": 101, "label": "EVAL-BACKTRACK" }, { "from": 100, "to": 103, "label": "CUT" }, { "from": 101, "to": 108, "label": "FAILURE" }, { "from": 103, "to": 104, "label": "CASE" }, { "from": 104, "to": 105, "label": "EVAL with clause\nuser_defined_=(X24, X24).\nand substitutionT23 -> 0,\nX24 -> 0,\nT29 -> 0" }, { "from": 104, "to": 106, "label": "EVAL-BACKTRACK" }, { "from": 105, "to": 107, "label": "SUCCESS" }, { "from": 108, "to": 302, "label": "ONLY EVAL with clause\ndiv(X37, X38, X39) :- ','(minus(X37, X38, X40), ','(div(X40, X38, X41), user_defined_=(X39, s(X41)))).\nand substitutionT20 -> T39,\nX37 -> T39,\nT21 -> T40,\nX38 -> T40,\nT3 -> T42,\nX39 -> T42,\nT41 -> T42" }, { "from": 302, "to": 335, "label": "SPLIT 1" }, { "from": 302, "to": 344, "label": "SPLIT 2\nnew knowledge:\nT39 is ground\nT40 is ground\nT45 is ground\nreplacements:X40 -> T45" }, { "from": 335, "to": 387, "label": "CASE" }, { "from": 344, "to": 623, "label": "SPLIT 1" }, { "from": 344, "to": 625, "label": "SPLIT 2\nnew knowledge:\nT45 is ground\nT40 is ground\nreplacements:X41 -> T127" }, { "from": 387, "to": 463, "label": "ONLY EVAL with clause\nminus(X58, X59, X60) :- ','(user_defined_=(X58, 0), ','(!_5, user_defined_=(X60, 0))).\nand substitutionT39 -> T52,\nX58 -> T52,\nT40 -> T53,\nX59 -> T53,\nX40 -> X61,\nX60 -> X61" }, { "from": 463, "to": 476, "label": "CASE" }, { "from": 476, "to": 484, "label": "BACKTRACK\nfor clause: user_defined_=(X, X)\nwith clash: (user_defined_=(T52, 0), user_defined_=(X21, X21))" }, { "from": 484, "to": 488, "label": "FAILURE" }, { "from": 488, "to": 502, "label": "ONLY EVAL with clause\nminus(X71, X72, X73) :- ','(user_defined_=(X72, 0), ','(!_5, user_defined_=(X73, X71))).\nand substitutionT52 -> T59,\nX71 -> T59,\nT53 -> T60,\nX72 -> T60,\nX40 -> X74,\nX73 -> X74" }, { "from": 502, "to": 503, "label": "CASE" }, { "from": 503, "to": 504, "label": "BACKTRACK\nfor clause: user_defined_=(X, X)\nwith clash: (user_defined_=(T60, 0), user_defined_=(X9, X9))" }, { "from": 504, "to": 506, "label": "FAILURE" }, { "from": 506, "to": 513, "label": "ONLY EVAL with clause\nminus(X92, X93, X94) :- ','(user_defined_=(X92, s(X95)), ','(user_defined_=(X93, s(X96)), minus(X95, X96, X94))).\nand substitutionT59 -> T66,\nX92 -> T66,\nT60 -> T67,\nX93 -> T67,\nX40 -> X97,\nX94 -> X97" }, { "from": 513, "to": 515, "label": "CASE" }, { "from": 515, "to": 521, "label": "EVAL with clause\nuser_defined_=(X106, X106).\nand substitutionT66 -> s(T73),\nX106 -> s(T73),\nX95 -> T73,\nT72 -> s(T73)" }, { "from": 515, "to": 522, "label": "EVAL-BACKTRACK" }, { "from": 521, "to": 523, "label": "CASE" }, { "from": 523, "to": 524, "label": "EVAL with clause\nuser_defined_=(X114, X114).\nand substitutionT67 -> s(T80),\nX114 -> s(T80),\nX96 -> T80,\nT79 -> s(T80)" }, { "from": 523, "to": 525, "label": "EVAL-BACKTRACK" }, { "from": 524, "to": 531, "label": "CASE" }, { "from": 531, "to": 535, "label": "ONLY EVAL with clause\nminus(X127, X128, X129) :- ','(user_defined_=(X127, 0), ','(!_10, user_defined_=(X129, 0))).\nand substitutionT73 -> T87,\nX127 -> T87,\nT80 -> T88,\nX128 -> T88,\nX97 -> X130,\nX129 -> X130" }, { "from": 535, "to": 536, "label": "CASE" }, { "from": 536, "to": 537, "label": "EVAL with clause\nuser_defined_=(X133, X133).\nand substitutionT87 -> 0,\nX133 -> 0,\nT91 -> 0" }, { "from": 536, "to": 538, "label": "EVAL-BACKTRACK" }, { "from": 537, "to": 539, "label": "CUT" }, { "from": 538, "to": 546, "label": "FAILURE" }, { "from": 539, "to": 540, "label": "CASE" }, { "from": 540, "to": 543, "label": "ONLY EVAL with clause\nuser_defined_=(X138, X138).\nand substitutionX130 -> 0,\nX138 -> 0,\nX139 -> 0" }, { "from": 543, "to": 544, "label": "SUCCESS" }, { "from": 546, "to": 557, "label": "ONLY EVAL with clause\nminus(X148, X149, X150) :- ','(user_defined_=(X149, 0), ','(!_10, user_defined_=(X150, X148))).\nand substitutionT87 -> T96,\nX148 -> T96,\nT88 -> T97,\nX149 -> T97,\nX97 -> X151,\nX150 -> X151" }, { "from": 557, "to": 561, "label": "CASE" }, { "from": 561, "to": 568, "label": "EVAL with clause\nuser_defined_=(X154, X154).\nand substitutionT97 -> 0,\nX154 -> 0,\nT100 -> 0" }, { "from": 561, "to": 571, "label": "EVAL-BACKTRACK" }, { "from": 568, "to": 574, "label": "CUT" }, { "from": 571, "to": 587, "label": "FAILURE" }, { "from": 574, "to": 576, "label": "CASE" }, { "from": 576, "to": 583, "label": "ONLY EVAL with clause\nuser_defined_=(X159, X159).\nand substitutionX151 -> T103,\nX159 -> T103,\nT96 -> T103,\nX160 -> T103" }, { "from": 583, "to": 584, "label": "SUCCESS" }, { "from": 587, "to": 607, "label": "ONLY EVAL with clause\nminus(X177, X178, X179) :- ','(user_defined_=(X177, s(X180)), ','(user_defined_=(X178, s(X181)), minus(X180, X181, X179))).\nand substitutionT96 -> T108,\nX177 -> T108,\nT97 -> T109,\nX178 -> T109,\nX97 -> X182,\nX179 -> X182" }, { "from": 607, "to": 609, "label": "CASE" }, { "from": 609, "to": 611, "label": "EVAL with clause\nuser_defined_=(X191, X191).\nand substitutionT108 -> s(T115),\nX191 -> s(T115),\nX180 -> T115,\nT114 -> s(T115)" }, { "from": 609, "to": 612, "label": "EVAL-BACKTRACK" }, { "from": 611, "to": 620, "label": "CASE" }, { "from": 620, "to": 621, "label": "EVAL with clause\nuser_defined_=(X199, X199).\nand substitutionT109 -> s(T122),\nX199 -> s(T122),\nX181 -> T122,\nT121 -> s(T122)" }, { "from": 620, "to": 622, "label": "EVAL-BACKTRACK" }, { "from": 621, "to": 524, "label": "INSTANCE with matching:\nT73 -> T115\nT80 -> T122\nX97 -> X182" }, { "from": 623, "to": 1, "label": "INSTANCE with matching:\nT1 -> T45\nT2 -> T40\nT3 -> X41" }, { "from": 625, "to": 626, "label": "CASE" }, { "from": 626, "to": 627, "label": "EVAL with clause\nuser_defined_=(X214, X214).\nand substitutionT42 -> s(T135),\nX214 -> s(T135),\nT127 -> T135,\nT134 -> s(T135)" }, { "from": 626, "to": 628, "label": "EVAL-BACKTRACK" }, { "from": 627, "to": 629, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (4) Obligation: Triples: minusA(s(X1), s(X2), X3) :- minusA(X1, X2, X3). divB(s(X1), s(X2), X3) :- minusA(X1, X2, X4). divB(X1, X2, X3) :- ','(minuscC(X1, X2, X4), divB(X4, X2, X5)). Clauses: minuscA(0, X1, 0). minuscA(X1, 0, X1). minuscA(s(X1), s(X2), X3) :- minuscA(X1, X2, X3). divcB(0, X1, 0). divcB(X1, X2, s(X3)) :- ','(minuscC(X1, X2, X4), divcB(X4, X2, X3)). minuscC(s(X1), s(X2), X3) :- minuscA(X1, X2, X3). Afs: divB(x1, x2, x3) = divB(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: divB_in_3: (b,b,f) minusA_in_3: (b,b,f) minuscC_in_3: (b,b,f) minuscA_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: DIVB_IN_GGA(s(X1), s(X2), X3) -> U2_GGA(X1, X2, X3, minusA_in_gga(X1, X2, X4)) DIVB_IN_GGA(s(X1), s(X2), X3) -> MINUSA_IN_GGA(X1, X2, X4) MINUSA_IN_GGA(s(X1), s(X2), X3) -> U1_GGA(X1, X2, X3, minusA_in_gga(X1, X2, X3)) MINUSA_IN_GGA(s(X1), s(X2), X3) -> MINUSA_IN_GGA(X1, X2, X3) DIVB_IN_GGA(X1, X2, X3) -> U3_GGA(X1, X2, X3, minuscC_in_gga(X1, X2, X4)) U3_GGA(X1, X2, X3, minuscC_out_gga(X1, X2, X4)) -> U4_GGA(X1, X2, X3, divB_in_gga(X4, X2, X5)) U3_GGA(X1, X2, X3, minuscC_out_gga(X1, X2, X4)) -> DIVB_IN_GGA(X4, X2, X5) The TRS R consists of the following rules: minuscC_in_gga(s(X1), s(X2), X3) -> U9_gga(X1, X2, X3, minuscA_in_gga(X1, X2, X3)) minuscA_in_gga(0, X1, 0) -> minuscA_out_gga(0, X1, 0) minuscA_in_gga(X1, 0, X1) -> minuscA_out_gga(X1, 0, X1) minuscA_in_gga(s(X1), s(X2), X3) -> U6_gga(X1, X2, X3, minuscA_in_gga(X1, X2, X3)) U6_gga(X1, X2, X3, minuscA_out_gga(X1, X2, X3)) -> minuscA_out_gga(s(X1), s(X2), X3) U9_gga(X1, X2, X3, minuscA_out_gga(X1, X2, X3)) -> minuscC_out_gga(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: divB_in_gga(x1, x2, x3) = divB_in_gga(x1, x2) s(x1) = s(x1) minusA_in_gga(x1, x2, x3) = minusA_in_gga(x1, x2) minuscC_in_gga(x1, x2, x3) = minuscC_in_gga(x1, x2) U9_gga(x1, x2, x3, x4) = U9_gga(x1, x2, x4) minuscA_in_gga(x1, x2, x3) = minuscA_in_gga(x1, x2) 0 = 0 minuscA_out_gga(x1, x2, x3) = minuscA_out_gga(x1, x2, x3) U6_gga(x1, x2, x3, x4) = U6_gga(x1, x2, x4) minuscC_out_gga(x1, x2, x3) = minuscC_out_gga(x1, x2, x3) DIVB_IN_GGA(x1, x2, x3) = DIVB_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4) = U2_GGA(x1, x2, x4) MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) U4_GGA(x1, x2, x3, x4) = U4_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: DIVB_IN_GGA(s(X1), s(X2), X3) -> U2_GGA(X1, X2, X3, minusA_in_gga(X1, X2, X4)) DIVB_IN_GGA(s(X1), s(X2), X3) -> MINUSA_IN_GGA(X1, X2, X4) MINUSA_IN_GGA(s(X1), s(X2), X3) -> U1_GGA(X1, X2, X3, minusA_in_gga(X1, X2, X3)) MINUSA_IN_GGA(s(X1), s(X2), X3) -> MINUSA_IN_GGA(X1, X2, X3) DIVB_IN_GGA(X1, X2, X3) -> U3_GGA(X1, X2, X3, minuscC_in_gga(X1, X2, X4)) U3_GGA(X1, X2, X3, minuscC_out_gga(X1, X2, X4)) -> U4_GGA(X1, X2, X3, divB_in_gga(X4, X2, X5)) U3_GGA(X1, X2, X3, minuscC_out_gga(X1, X2, X4)) -> DIVB_IN_GGA(X4, X2, X5) The TRS R consists of the following rules: minuscC_in_gga(s(X1), s(X2), X3) -> U9_gga(X1, X2, X3, minuscA_in_gga(X1, X2, X3)) minuscA_in_gga(0, X1, 0) -> minuscA_out_gga(0, X1, 0) minuscA_in_gga(X1, 0, X1) -> minuscA_out_gga(X1, 0, X1) minuscA_in_gga(s(X1), s(X2), X3) -> U6_gga(X1, X2, X3, minuscA_in_gga(X1, X2, X3)) U6_gga(X1, X2, X3, minuscA_out_gga(X1, X2, X3)) -> minuscA_out_gga(s(X1), s(X2), X3) U9_gga(X1, X2, X3, minuscA_out_gga(X1, X2, X3)) -> minuscC_out_gga(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: divB_in_gga(x1, x2, x3) = divB_in_gga(x1, x2) s(x1) = s(x1) minusA_in_gga(x1, x2, x3) = minusA_in_gga(x1, x2) minuscC_in_gga(x1, x2, x3) = minuscC_in_gga(x1, x2) U9_gga(x1, x2, x3, x4) = U9_gga(x1, x2, x4) minuscA_in_gga(x1, x2, x3) = minuscA_in_gga(x1, x2) 0 = 0 minuscA_out_gga(x1, x2, x3) = minuscA_out_gga(x1, x2, x3) U6_gga(x1, x2, x3, x4) = U6_gga(x1, x2, x4) minuscC_out_gga(x1, x2, x3) = minuscC_out_gga(x1, x2, x3) DIVB_IN_GGA(x1, x2, x3) = DIVB_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4) = U2_GGA(x1, x2, x4) MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 4 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: MINUSA_IN_GGA(s(X1), s(X2), X3) -> MINUSA_IN_GGA(X1, X2, X3) The TRS R consists of the following rules: minuscC_in_gga(s(X1), s(X2), X3) -> U9_gga(X1, X2, X3, minuscA_in_gga(X1, X2, X3)) minuscA_in_gga(0, X1, 0) -> minuscA_out_gga(0, X1, 0) minuscA_in_gga(X1, 0, X1) -> minuscA_out_gga(X1, 0, X1) minuscA_in_gga(s(X1), s(X2), X3) -> U6_gga(X1, X2, X3, minuscA_in_gga(X1, X2, X3)) U6_gga(X1, X2, X3, minuscA_out_gga(X1, X2, X3)) -> minuscA_out_gga(s(X1), s(X2), X3) U9_gga(X1, X2, X3, minuscA_out_gga(X1, X2, X3)) -> minuscC_out_gga(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) minuscC_in_gga(x1, x2, x3) = minuscC_in_gga(x1, x2) U9_gga(x1, x2, x3, x4) = U9_gga(x1, x2, x4) minuscA_in_gga(x1, x2, x3) = minuscA_in_gga(x1, x2) 0 = 0 minuscA_out_gga(x1, x2, x3) = minuscA_out_gga(x1, x2, x3) U6_gga(x1, x2, x3, x4) = U6_gga(x1, x2, x4) minuscC_out_gga(x1, x2, x3) = minuscC_out_gga(x1, x2, x3) MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (11) Obligation: Pi DP problem: The TRS P consists of the following rules: MINUSA_IN_GGA(s(X1), s(X2), X3) -> MINUSA_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (12) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: MINUSA_IN_GGA(s(X1), s(X2)) -> MINUSA_IN_GGA(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (14) 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: *MINUSA_IN_GGA(s(X1), s(X2)) -> MINUSA_IN_GGA(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: DIVB_IN_GGA(X1, X2, X3) -> U3_GGA(X1, X2, X3, minuscC_in_gga(X1, X2, X4)) U3_GGA(X1, X2, X3, minuscC_out_gga(X1, X2, X4)) -> DIVB_IN_GGA(X4, X2, X5) The TRS R consists of the following rules: minuscC_in_gga(s(X1), s(X2), X3) -> U9_gga(X1, X2, X3, minuscA_in_gga(X1, X2, X3)) minuscA_in_gga(0, X1, 0) -> minuscA_out_gga(0, X1, 0) minuscA_in_gga(X1, 0, X1) -> minuscA_out_gga(X1, 0, X1) minuscA_in_gga(s(X1), s(X2), X3) -> U6_gga(X1, X2, X3, minuscA_in_gga(X1, X2, X3)) U6_gga(X1, X2, X3, minuscA_out_gga(X1, X2, X3)) -> minuscA_out_gga(s(X1), s(X2), X3) U9_gga(X1, X2, X3, minuscA_out_gga(X1, X2, X3)) -> minuscC_out_gga(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) minuscC_in_gga(x1, x2, x3) = minuscC_in_gga(x1, x2) U9_gga(x1, x2, x3, x4) = U9_gga(x1, x2, x4) minuscA_in_gga(x1, x2, x3) = minuscA_in_gga(x1, x2) 0 = 0 minuscA_out_gga(x1, x2, x3) = minuscA_out_gga(x1, x2, x3) U6_gga(x1, x2, x3, x4) = U6_gga(x1, x2, x4) minuscC_out_gga(x1, x2, x3) = minuscC_out_gga(x1, x2, x3) DIVB_IN_GGA(x1, x2, x3) = DIVB_IN_GGA(x1, x2) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) 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: DIVB_IN_GGA(X1, X2) -> U3_GGA(X1, X2, minuscC_in_gga(X1, X2)) U3_GGA(X1, X2, minuscC_out_gga(X1, X2, X4)) -> DIVB_IN_GGA(X4, X2) The TRS R consists of the following rules: minuscC_in_gga(s(X1), s(X2)) -> U9_gga(X1, X2, minuscA_in_gga(X1, X2)) minuscA_in_gga(0, X1) -> minuscA_out_gga(0, X1, 0) minuscA_in_gga(X1, 0) -> minuscA_out_gga(X1, 0, X1) minuscA_in_gga(s(X1), s(X2)) -> U6_gga(X1, X2, minuscA_in_gga(X1, X2)) U6_gga(X1, X2, minuscA_out_gga(X1, X2, X3)) -> minuscA_out_gga(s(X1), s(X2), X3) U9_gga(X1, X2, minuscA_out_gga(X1, X2, X3)) -> minuscC_out_gga(s(X1), s(X2), X3) The set Q consists of the following terms: minuscC_in_gga(x0, x1) minuscA_in_gga(x0, x1) U6_gga(x0, x1, x2) U9_gga(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) QDPQMonotonicMRRProof (EQUIVALENT) By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. Strictly oriented dependency pairs: DIVB_IN_GGA(X1, X2) -> U3_GGA(X1, X2, minuscC_in_gga(X1, X2)) U3_GGA(X1, X2, minuscC_out_gga(X1, X2, X4)) -> DIVB_IN_GGA(X4, X2) Strictly oriented rules of the TRS R: U6_gga(X1, X2, minuscA_out_gga(X1, X2, X3)) -> minuscA_out_gga(s(X1), s(X2), X3) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(DIVB_IN_GGA(x_1, x_2)) = 2 + 2*x_1 POL(U3_GGA(x_1, x_2, x_3)) = 2*x_3 POL(U6_gga(x_1, x_2, x_3)) = 2 + x_3 POL(U9_gga(x_1, x_2, x_3)) = 2 + 2*x_3 POL(minuscA_in_gga(x_1, x_2)) = x_1 POL(minuscA_out_gga(x_1, x_2, x_3)) = x_3 POL(minuscC_in_gga(x_1, x_2)) = x_1 POL(minuscC_out_gga(x_1, x_2, x_3)) = 2 + 2*x_3 POL(s(x_1)) = 2 + 2*x_1 ---------------------------------------- (20) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: minuscC_in_gga(s(X1), s(X2)) -> U9_gga(X1, X2, minuscA_in_gga(X1, X2)) minuscA_in_gga(0, X1) -> minuscA_out_gga(0, X1, 0) minuscA_in_gga(X1, 0) -> minuscA_out_gga(X1, 0, X1) minuscA_in_gga(s(X1), s(X2)) -> U6_gga(X1, X2, minuscA_in_gga(X1, X2)) U9_gga(X1, X2, minuscA_out_gga(X1, X2, X3)) -> minuscC_out_gga(s(X1), s(X2), X3) The set Q consists of the following terms: minuscC_in_gga(x0, x1) minuscA_in_gga(x0, x1) U6_gga(x0, x1, x2) U9_gga(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (22) YES