/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 goal(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 69 ms] (2) TRIPLES (3) UndefinedPredicateInTriplesTransformerProof [SOUND, 0 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, 0 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] (15) YES (16) PiDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) PiDP (19) PiDPToQDPProof [SOUND, 0 ms] (20) QDP (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] (22) YES ---------------------------------------- (0) Obligation: Clauses: goal(X) :- ','(s2l(X, Xs), list(Xs)). list([]). list(X) :- ','(no(empty(X)), ','(tail(X, T), list(T))). s2l(0, []). s2l(X, .(X1, Xs)) :- ','(no(zero(X)), ','(p(X, P), s2l(P, Xs))). tail([], []). tail(.(X2, Xs), Xs). p(0, 0). p(s(X), X). empty([]). zero(0). no(X) :- ','(X, ','(!, failure(a))). no(X3). failure(b). Query: goal(g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(goal X)", "(',' (s2l X Xs) (list Xs))" ], [ "(list ([]))", null ], [ "(list X)", "(',' (no (empty X)) (',' (tail X T) (list T)))" ], [ "(s2l (0) ([]))", null ], [ "(s2l X (. X1 Xs))", "(',' (no (zero X)) (',' (p X P) (s2l P Xs)))" ], [ "(tail ([]) ([]))", null ], [ "(tail (. X2 Xs) Xs)", null ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(empty ([]))", null ], [ "(zero (0))", null ], [ "(no X)", "(',' X (',' (!) (failure (a))))" ], [ "(no X3)", null ], [ "(failure (b))", null ] ] }, "graph": { "nodes": { "88": { "goal": [ { "clause": 11, "scope": 14, "term": "(',' (no (zero T19)) (',' (p T19 X55) (s2l X55 X57)))" }, { "clause": 12, "scope": 14, "term": "(',' (no (zero T19)) (',' (p T19 X55) (s2l X55 X57)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [ "X57", "X55" ], "exprvars": [] } }, "89": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (zero T22)) (',' (!_14) (failure (a)))) (',' (p T22 X55) (s2l X55 X57)))" }, { "clause": 12, "scope": 14, "term": "(',' (no (zero T22)) (',' (p T22 X55) (s2l X55 X57)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [ "X57", "X55" ], "exprvars": [] } }, "type": "Nodes", "230": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "231": { "goal": [ { "clause": -1, "scope": 26, "term": null }, { "clause": 12, "scope": 25, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "232": { "goal": [{ "clause": 12, "scope": 25, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "233": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail T63 X100) (list X100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "234": { "goal": [ { "clause": 5, "scope": 29, "term": "(',' (tail T63 X100) (list X100))" }, { "clause": 6, "scope": 29, "term": "(',' (tail T63 X100) (list X100))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "114": { "goal": [{ "clause": -1, "scope": -1, "term": "(s2l T28 X57)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T28"], "free": ["X57"], "exprvars": [] } }, "235": { "goal": [{ "clause": 5, "scope": 29, "term": "(',' (tail T63 X100) (list X100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "115": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "236": { "goal": [{ "clause": 6, "scope": 29, "term": "(',' (tail T63 X100) (list X100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "237": { "goal": [{ "clause": -1, "scope": -1, "term": "(list ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "90": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (zero T22) (',' (',' (!_14) (failure (a))) (',' (p T22 X55) (s2l X55 X57))))" }, { "clause": -1, "scope": 15, "term": null }, { "clause": 12, "scope": 14, "term": "(',' (no (zero T22)) (',' (p T22 X55) (s2l X55 X57)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [ "X57", "X55" ], "exprvars": [] } }, "238": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "91": { "goal": [ { "clause": 10, "scope": 16, "term": "(',' (zero T22) (',' (',' (!_14) (failure (a))) (',' (p T22 X55) (s2l X55 X57))))" }, { "clause": -1, "scope": 16, "term": null }, { "clause": -1, "scope": 15, "term": null }, { "clause": 12, "scope": 14, "term": "(',' (no (zero T22)) (',' (p T22 X55) (s2l X55 X57)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [ "X57", "X55" ], "exprvars": [] } }, "239": { "goal": [{ "clause": -1, "scope": -1, "term": "(list T70)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "92": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_14) (failure (a))) (',' (p (0) X55) (s2l X55 X57)))" }, { "clause": -1, "scope": 16, "term": null }, { "clause": -1, "scope": 15, "term": null }, { "clause": 12, "scope": 14, "term": "(',' (no (zero (0))) (',' (p (0) X55) (s2l X55 X57)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X57", "X55" ], "exprvars": [] } }, "94": { "goal": [ { "clause": -1, "scope": 16, "term": null }, { "clause": -1, "scope": 15, "term": null }, { "clause": 12, "scope": 14, "term": "(',' (no (zero T22)) (',' (p T22 X55) (s2l X55 X57)))" } ], "kb": { "nonunifying": [[ "(zero T22)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [ "X57", "X55" ], "exprvars": [] } }, "95": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (p (0) X55) (s2l X55 X57)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X57", "X55" ], "exprvars": [] } }, "97": { "goal": [{ "clause": 13, "scope": 17, "term": "(',' (failure (a)) (',' (p (0) X55) (s2l X55 X57)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X57", "X55" ], "exprvars": [] } }, "10": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (s2l T3 X6) (list X6))" }, { "clause": 4, "scope": 2, "term": "(',' (s2l T3 X6) (list X6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": ["X6"], "exprvars": [] } }, "98": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "11": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (s2l T3 X6) (list X6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": ["X6"], "exprvars": [] } }, "99": { "goal": [ { "clause": -1, "scope": 15, "term": null }, { "clause": 12, "scope": 14, "term": "(',' (no (zero T22)) (',' (p T22 X55) (s2l X55 X57)))" } ], "kb": { "nonunifying": [[ "(zero T22)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [ "X57", "X55" ], "exprvars": [] } }, "12": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (s2l T3 X6) (list X6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": ["X6"], "exprvars": [] } }, "13": { "goal": [{ "clause": -1, "scope": -1, "term": "(list ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "15": { "goal": [ { "clause": 1, "scope": 3, "term": "(list ([]))" }, { "clause": 2, "scope": 3, "term": "(list ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 1, "scope": 3, "term": "(list ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": 2, "scope": 3, "term": "(list ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "240": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(goal T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(goal T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (s2l T3 X6) (list X6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": ["X6"], "exprvars": [] } }, "20": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (empty ([]))) (',' (tail ([]) X11) (list X11)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "26": { "goal": [ { "clause": 11, "scope": 4, "term": "(',' (no (empty ([]))) (',' (tail ([]) X11) (list X11)))" }, { "clause": 12, "scope": 4, "term": "(',' (no (empty ([]))) (',' (tail ([]) X11) (list X11)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "130": { "goal": [ { "clause": 1, "scope": 19, "term": "(list (. X30 T16))" }, { "clause": 2, "scope": 19, "term": "(list (. X30 T16))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X30"], "exprvars": [] } }, "132": { "goal": [{ "clause": 2, "scope": 19, "term": "(list (. X30 T16))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X30"], "exprvars": [] } }, "136": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (empty (. X74 T33))) (',' (tail (. X74 T33) X73) (list X73)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X74", "X73" ], "exprvars": [] } }, "138": { "goal": [ { "clause": 11, "scope": 20, "term": "(',' (no (empty (. X74 T33))) (',' (tail (. X74 T33) X73) (list X73)))" }, { "clause": 12, "scope": 20, "term": "(',' (no (empty (. X74 T33))) (',' (tail (. X74 T33) X73) (list X73)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X74", "X73" ], "exprvars": [] } }, "30": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (empty ([]))) (',' (!_4) (failure (a)))) (',' (tail ([]) X11) (list X11)))" }, { "clause": 12, "scope": 4, "term": "(',' (no (empty ([]))) (',' (tail ([]) X11) (list X11)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "31": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (empty ([])) (',' (',' (!_4) (failure (a))) (',' (tail ([]) X11) (list X11))))" }, { "clause": -1, "scope": 5, "term": null }, { "clause": 12, "scope": 4, "term": "(',' (no (empty ([]))) (',' (tail ([]) X11) (list X11)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "32": { "goal": [ { "clause": 9, "scope": 6, "term": "(',' (empty ([])) (',' (',' (!_4) (failure (a))) (',' (tail ([]) X11) (list X11))))" }, { "clause": -1, "scope": 6, "term": null }, { "clause": -1, "scope": 5, "term": null }, { "clause": 12, "scope": 4, "term": "(',' (no (empty ([]))) (',' (tail ([]) X11) (list X11)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "34": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_4) (failure (a))) (',' (tail ([]) X11) (list X11)))" }, { "clause": -1, "scope": 6, "term": null }, { "clause": -1, "scope": 5, "term": null }, { "clause": 12, "scope": 4, "term": "(',' (no (empty ([]))) (',' (tail ([]) X11) (list X11)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "35": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (tail ([]) X11) (list X11)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "37": { "goal": [{ "clause": 13, "scope": 7, "term": "(',' (failure (a)) (',' (tail ([]) X11) (list X11)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X11"], "exprvars": [] } }, "38": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "146": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (empty (. X80 T38))) (',' (!_20) (failure (a)))) (',' (tail (. X80 T38) X73) (list X73)))" }, { "clause": 12, "scope": 20, "term": "(',' (no (empty (. X74 T33))) (',' (tail (. X74 T33) X73) (list X73)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X74", "X73", "X80" ], "exprvars": [] } }, "147": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (empty (. X80 T38)) (',' (',' (!_20) (failure (a))) (',' (tail (. X80 T38) X73) (list X73))))" }, { "clause": -1, "scope": 21, "term": null }, { "clause": 12, "scope": 20, "term": "(',' (no (empty (. X74 T33))) (',' (tail (. X74 T33) X73) (list X73)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X74", "X73", "X80" ], "exprvars": [] } }, "148": { "goal": [ { "clause": 9, "scope": 22, "term": "(',' (empty (. X80 T38)) (',' (',' (!_20) (failure (a))) (',' (tail (. X80 T38) X73) (list X73))))" }, { "clause": -1, "scope": 22, "term": null }, { "clause": -1, "scope": 21, "term": null }, { "clause": 12, "scope": 20, "term": "(',' (no (empty (. X74 T33))) (',' (tail (. X74 T33) X73) (list X73)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X74", "X73", "X80" ], "exprvars": [] } }, "48": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (no (zero T6)) (',' (p T6 X29) (s2l X29 X31))) (list (. X30 X31)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "50": { "goal": [ { "clause": 11, "scope": 8, "term": "(',' (',' (no (zero T6)) (',' (p T6 X29) (s2l X29 X31))) (list (. X30 X31)))" }, { "clause": 12, "scope": 8, "term": "(',' (',' (no (zero T6)) (',' (p T6 X29) (s2l X29 X31))) (list (. X30 X31)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "52": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (zero T9)) (',' (!_8) (failure (a)))) (',' (',' (p T9 X29) (s2l X29 X31)) (list (. X30 X31))))" }, { "clause": 12, "scope": 8, "term": "(',' (',' (no (zero T9)) (',' (p T9 X29) (s2l X29 X31))) (list (. X30 X31)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "54": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (zero T9) (',' (',' (!_8) (failure (a))) (',' (',' (p T9 X29) (s2l X29 X31)) (list (. X30 X31)))))" }, { "clause": -1, "scope": 9, "term": null }, { "clause": 12, "scope": 8, "term": "(',' (',' (no (zero T9)) (',' (p T9 X29) (s2l X29 X31))) (list (. X30 X31)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "56": { "goal": [ { "clause": 10, "scope": 10, "term": "(',' (zero T9) (',' (',' (!_8) (failure (a))) (',' (',' (p T9 X29) (s2l X29 X31)) (list (. X30 X31)))))" }, { "clause": -1, "scope": 10, "term": null }, { "clause": -1, "scope": 9, "term": null }, { "clause": 12, "scope": 8, "term": "(',' (',' (no (zero T9)) (',' (p T9 X29) (s2l X29 X31))) (list (. X30 X31)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "58": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_8) (failure (a))) (',' (',' (p (0) X29) (s2l X29 X31)) (list (. X30 X31))))" }, { "clause": -1, "scope": 10, "term": null }, { "clause": -1, "scope": 9, "term": null }, { "clause": 12, "scope": 8, "term": "(',' (',' (no (zero (0))) (',' (p (0) X29) (s2l X29 X31))) (list (. X30 X31)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "60": { "goal": [ { "clause": -1, "scope": 10, "term": null }, { "clause": -1, "scope": 9, "term": null }, { "clause": 12, "scope": 8, "term": "(',' (',' (no (zero T9)) (',' (p T9 X29) (s2l X29 X31))) (list (. X30 X31)))" } ], "kb": { "nonunifying": [[ "(zero T9)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "208": { "goal": [ { "clause": -1, "scope": 22, "term": null }, { "clause": -1, "scope": 21, "term": null }, { "clause": 12, "scope": 20, "term": "(',' (no (empty (. X74 T33))) (',' (tail (. X74 T33) X73) (list X73)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X74", "X73" ], "exprvars": [] } }, "61": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (',' (p (0) X29) (s2l X29 X31)) (list (. X30 X31))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "209": { "goal": [ { "clause": -1, "scope": 21, "term": null }, { "clause": 12, "scope": 20, "term": "(',' (no (empty (. X74 T33))) (',' (tail (. X74 T33) X73) (list X73)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X74", "X73" ], "exprvars": [] } }, "62": { "goal": [{ "clause": 13, "scope": 11, "term": "(',' (failure (a)) (',' (',' (p (0) X29) (s2l X29 X31)) (list (. X30 X31))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "63": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "64": { "goal": [ { "clause": -1, "scope": 9, "term": null }, { "clause": 12, "scope": 8, "term": "(',' (',' (no (zero T9)) (',' (p T9 X29) (s2l X29 X31))) (list (. X30 X31)))" } ], "kb": { "nonunifying": [[ "(zero T9)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "65": { "goal": [{ "clause": 12, "scope": 8, "term": "(',' (',' (no (zero T9)) (',' (p T9 X29) (s2l X29 X31))) (list (. X30 X31)))" }], "kb": { "nonunifying": [[ "(zero T9)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "66": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (p T12 X29) (s2l X29 X31)) (list (. X30 X31)))" }], "kb": { "nonunifying": [[ "(zero T12)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "67": { "goal": [ { "clause": 7, "scope": 12, "term": "(',' (',' (p T12 X29) (s2l X29 X31)) (list (. X30 X31)))" }, { "clause": 8, "scope": 12, "term": "(',' (',' (p T12 X29) (s2l X29 X31)) (list (. X30 X31)))" } ], "kb": { "nonunifying": [[ "(zero T12)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "68": { "goal": [{ "clause": 8, "scope": 12, "term": "(',' (',' (p T12 X29) (s2l X29 X31)) (list (. X30 X31)))" }], "kb": { "nonunifying": [[ "(zero T12)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [ "X30", "X31", "X29" ], "exprvars": [] } }, "69": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (s2l T15 X31) (list (. X30 X31)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X30", "X31" ], "exprvars": [] } }, "210": { "goal": [{ "clause": 12, "scope": 20, "term": "(',' (no (empty (. X74 T33))) (',' (tail (. X74 T33) X73) (list X73)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X74", "X73" ], "exprvars": [] } }, "211": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. X86 T43) X73) (list X73))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X73", "X86" ], "exprvars": [] } }, "212": { "goal": [ { "clause": 5, "scope": 23, "term": "(',' (tail (. X86 T43) X73) (list X73))" }, { "clause": 6, "scope": 23, "term": "(',' (tail (. X86 T43) X73) (list X73))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X73", "X86" ], "exprvars": [] } }, "213": { "goal": [{ "clause": 6, "scope": 23, "term": "(',' (tail (. X86 T43) X73) (list X73))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X73", "X86" ], "exprvars": [] } }, "214": { "goal": [{ "clause": -1, "scope": -1, "term": "(list T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "215": { "goal": [ { "clause": 1, "scope": 24, "term": "(list T48)" }, { "clause": 2, "scope": 24, "term": "(list T48)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "216": { "goal": [{ "clause": 1, "scope": 24, "term": "(list T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "217": { "goal": [{ "clause": 2, "scope": 24, "term": "(list T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "70": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "218": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "71": { "goal": [{ "clause": -1, "scope": -1, "term": "(s2l T15 X31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X31"], "exprvars": [] } }, "219": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "72": { "goal": [{ "clause": -1, "scope": -1, "term": "(list (. X30 T16))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X30"], "exprvars": [] } }, "73": { "goal": [ { "clause": 3, "scope": 13, "term": "(s2l T15 X31)" }, { "clause": 4, "scope": 13, "term": "(s2l T15 X31)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X31"], "exprvars": [] } }, "74": { "goal": [{ "clause": 3, "scope": 13, "term": "(s2l T15 X31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X31"], "exprvars": [] } }, "75": { "goal": [{ "clause": 4, "scope": 13, "term": "(s2l T15 X31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": ["X31"], "exprvars": [] } }, "76": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "77": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "78": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "220": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "100": { "goal": [{ "clause": 12, "scope": 14, "term": "(',' (no (zero T22)) (',' (p T22 X55) (s2l X55 X57)))" }], "kb": { "nonunifying": [[ "(zero T22)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [ "X57", "X55" ], "exprvars": [] } }, "221": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "222": { "goal": [ { "clause": 11, "scope": 25, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" }, { "clause": 12, "scope": 25, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "223": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (empty T58)) (',' (!_25) (failure (a)))) (',' (tail T58 X100) (list X100)))" }, { "clause": 12, "scope": 25, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "224": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (empty T58) (',' (',' (!_25) (failure (a))) (',' (tail T58 X100) (list X100))))" }, { "clause": -1, "scope": 26, "term": null }, { "clause": 12, "scope": 25, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "104": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T25 X55) (s2l X55 X57))" }], "kb": { "nonunifying": [[ "(zero T25)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [ "X57", "X55" ], "exprvars": [] } }, "225": { "goal": [ { "clause": 9, "scope": 27, "term": "(',' (empty T58) (',' (',' (!_25) (failure (a))) (',' (tail T58 X100) (list X100))))" }, { "clause": -1, "scope": 27, "term": null }, { "clause": -1, "scope": 26, "term": null }, { "clause": 12, "scope": 25, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "226": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_25) (failure (a))) (',' (tail ([]) X100) (list X100)))" }, { "clause": -1, "scope": 27, "term": null }, { "clause": -1, "scope": 26, "term": null }, { "clause": 12, "scope": 25, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "227": { "goal": [ { "clause": -1, "scope": 27, "term": null }, { "clause": -1, "scope": 26, "term": null }, { "clause": 12, "scope": 25, "term": "(',' (no (empty T53)) (',' (tail T53 X100) (list X100)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "228": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (',' (tail ([]) X100) (list X100)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "108": { "goal": [ { "clause": 7, "scope": 18, "term": "(',' (p T25 X55) (s2l X55 X57))" }, { "clause": 8, "scope": 18, "term": "(',' (p T25 X55) (s2l X55 X57))" } ], "kb": { "nonunifying": [[ "(zero T25)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [ "X57", "X55" ], "exprvars": [] } }, "229": { "goal": [{ "clause": 13, "scope": 28, "term": "(',' (failure (a)) (',' (tail ([]) X100) (list X100)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X100"], "exprvars": [] } }, "109": { "goal": [{ "clause": 8, "scope": 18, "term": "(',' (p T25 X55) (s2l X55 X57))" }], "kb": { "nonunifying": [[ "(zero T25)", "(zero (0))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [ "X57", "X55" ], "exprvars": [] } }, "85": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (zero T19)) (',' (p T19 X55) (s2l X55 X57)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [ "X57", "X55" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 9, "label": "ONLY EVAL with clause\ngoal(X5) :- ','(s2l(X5, X6), list(X6)).\nand substitutionT1 -> T3,\nX5 -> T3" }, { "from": 9, "to": 10, "label": "CASE" }, { "from": 10, "to": 11, "label": "PARALLEL" }, { "from": 10, "to": 12, "label": "PARALLEL" }, { "from": 11, "to": 13, "label": "EVAL with clause\ns2l(0, []).\nand substitutionT3 -> 0,\nX6 -> []" }, { "from": 11, "to": 14, "label": "EVAL-BACKTRACK" }, { "from": 12, "to": 48, "label": "ONLY EVAL with clause\ns2l(X26, .(X27, X28)) :- ','(no(zero(X26)), ','(p(X26, X29), s2l(X29, X28))).\nand substitutionT3 -> T6,\nX26 -> T6,\nX27 -> X30,\nX28 -> X31,\nX6 -> .(X30, X31)" }, { "from": 13, "to": 15, "label": "CASE" }, { "from": 15, "to": 17, "label": "PARALLEL" }, { "from": 15, "to": 19, "label": "PARALLEL" }, { "from": 17, "to": 20, "label": "ONLY EVAL with clause\nlist([]).\nand substitution" }, { "from": 19, "to": 23, "label": "ONLY EVAL with clause\nlist(X10) :- ','(no(empty(X10)), ','(tail(X10, X11), list(X11))).\nand substitutionX10 -> []" }, { "from": 20, "to": 21, "label": "SUCCESS" }, { "from": 23, "to": 26, "label": "CASE" }, { "from": 26, "to": 30, "label": "ONLY EVAL with clause\nno(X14) :- ','(call(X14), ','(!_4, failure(a))).\nand substitutionX14 -> empty([])" }, { "from": 30, "to": 31, "label": "CALL" }, { "from": 31, "to": 32, "label": "CASE" }, { "from": 32, "to": 34, "label": "ONLY EVAL with clause\nempty([]).\nand substitution" }, { "from": 34, "to": 35, "label": "CUT" }, { "from": 35, "to": 37, "label": "CASE" }, { "from": 37, "to": 38, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 48, "to": 50, "label": "CASE" }, { "from": 50, "to": 52, "label": "ONLY EVAL with clause\nno(X34) :- ','(call(X34), ','(!_8, failure(a))).\nand substitutionT6 -> T9,\nX34 -> zero(T9)" }, { "from": 52, "to": 54, "label": "CALL" }, { "from": 54, "to": 56, "label": "CASE" }, { "from": 56, "to": 58, "label": "EVAL with clause\nzero(0).\nand substitutionT9 -> 0" }, { "from": 56, "to": 60, "label": "EVAL-BACKTRACK" }, { "from": 58, "to": 61, "label": "CUT" }, { "from": 60, "to": 64, "label": "FAILURE" }, { "from": 61, "to": 62, "label": "CASE" }, { "from": 62, "to": 63, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 64, "to": 65, "label": "FAILURE" }, { "from": 65, "to": 66, "label": "ONLY EVAL with clause\nno(X37).\nand substitutionT9 -> T12,\nX37 -> zero(T12)" }, { "from": 66, "to": 67, "label": "CASE" }, { "from": 67, "to": 68, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (zero(T12), zero(0))" }, { "from": 68, "to": 69, "label": "EVAL with clause\np(s(X40), X40).\nand substitutionX40 -> T15,\nT12 -> s(T15),\nX29 -> T15" }, { "from": 68, "to": 70, "label": "EVAL-BACKTRACK" }, { "from": 69, "to": 71, "label": "SPLIT 1" }, { "from": 69, "to": 72, "label": "SPLIT 2\nnew knowledge:\nT15 is ground\nreplacements:X31 -> T16" }, { "from": 71, "to": 73, "label": "CASE" }, { "from": 72, "to": 130, "label": "CASE" }, { "from": 73, "to": 74, "label": "PARALLEL" }, { "from": 73, "to": 75, "label": "PARALLEL" }, { "from": 74, "to": 76, "label": "EVAL with clause\ns2l(0, []).\nand substitutionT15 -> 0,\nX31 -> []" }, { "from": 74, "to": 77, "label": "EVAL-BACKTRACK" }, { "from": 75, "to": 85, "label": "ONLY EVAL with clause\ns2l(X52, .(X53, X54)) :- ','(no(zero(X52)), ','(p(X52, X55), s2l(X55, X54))).\nand substitutionT15 -> T19,\nX52 -> T19,\nX53 -> X56,\nX54 -> X57,\nX31 -> .(X56, X57)" }, { "from": 76, "to": 78, "label": "SUCCESS" }, { "from": 85, "to": 88, "label": "CASE" }, { "from": 88, "to": 89, "label": "ONLY EVAL with clause\nno(X60) :- ','(call(X60), ','(!_14, failure(a))).\nand substitutionT19 -> T22,\nX60 -> zero(T22)" }, { "from": 89, "to": 90, "label": "CALL" }, { "from": 90, "to": 91, "label": "CASE" }, { "from": 91, "to": 92, "label": "EVAL with clause\nzero(0).\nand substitutionT22 -> 0" }, { "from": 91, "to": 94, "label": "EVAL-BACKTRACK" }, { "from": 92, "to": 95, "label": "CUT" }, { "from": 94, "to": 99, "label": "FAILURE" }, { "from": 95, "to": 97, "label": "CASE" }, { "from": 97, "to": 98, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 99, "to": 100, "label": "FAILURE" }, { "from": 100, "to": 104, "label": "ONLY EVAL with clause\nno(X63).\nand substitutionT22 -> T25,\nX63 -> zero(T25)" }, { "from": 104, "to": 108, "label": "CASE" }, { "from": 108, "to": 109, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (zero(T25), zero(0))" }, { "from": 109, "to": 114, "label": "EVAL with clause\np(s(X66), X66).\nand substitutionX66 -> T28,\nT25 -> s(T28),\nX55 -> T28" }, { "from": 109, "to": 115, "label": "EVAL-BACKTRACK" }, { "from": 114, "to": 71, "label": "INSTANCE with matching:\nT15 -> T28\nX31 -> X57" }, { "from": 130, "to": 132, "label": "BACKTRACK\nfor clause: list([])because of non-unification" }, { "from": 132, "to": 136, "label": "ONLY EVAL with clause\nlist(X72) :- ','(no(empty(X72)), ','(tail(X72, X73), list(X73))).\nand substitutionX30 -> X74,\nT16 -> T33,\nX72 -> .(X74, T33),\nT32 -> T33" }, { "from": 136, "to": 138, "label": "CASE" }, { "from": 138, "to": 146, "label": "ONLY EVAL with clause\nno(X79) :- ','(call(X79), ','(!_20, failure(a))).\nand substitutionX74 -> X80,\nT33 -> T38,\nX79 -> empty(.(X80, T38)),\nT37 -> T38" }, { "from": 146, "to": 147, "label": "CALL" }, { "from": 147, "to": 148, "label": "CASE" }, { "from": 148, "to": 208, "label": "BACKTRACK\nfor clause: empty([])because of non-unification" }, { "from": 208, "to": 209, "label": "FAILURE" }, { "from": 209, "to": 210, "label": "FAILURE" }, { "from": 210, "to": 211, "label": "ONLY EVAL with clause\nno(X85).\nand substitutionX74 -> X86,\nT33 -> T43,\nX85 -> empty(.(X86, T43)),\nT42 -> T43" }, { "from": 211, "to": 212, "label": "CASE" }, { "from": 212, "to": 213, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 213, "to": 214, "label": "ONLY EVAL with clause\ntail(.(X93, X94), X94).\nand substitutionX86 -> X95,\nX93 -> X95,\nT43 -> T48,\nX94 -> T48,\nX73 -> T48,\nT47 -> T48" }, { "from": 214, "to": 215, "label": "CASE" }, { "from": 215, "to": 216, "label": "PARALLEL" }, { "from": 215, "to": 217, "label": "PARALLEL" }, { "from": 216, "to": 218, "label": "EVAL with clause\nlist([]).\nand substitutionT48 -> []" }, { "from": 216, "to": 219, "label": "EVAL-BACKTRACK" }, { "from": 217, "to": 221, "label": "ONLY EVAL with clause\nlist(X99) :- ','(no(empty(X99)), ','(tail(X99, X100), list(X100))).\nand substitutionT48 -> T53,\nX99 -> T53,\nT52 -> T53" }, { "from": 218, "to": 220, "label": "SUCCESS" }, { "from": 221, "to": 222, "label": "CASE" }, { "from": 222, "to": 223, "label": "ONLY EVAL with clause\nno(X103) :- ','(call(X103), ','(!_25, failure(a))).\nand substitutionT53 -> T58,\nX103 -> empty(T58),\nT57 -> T58" }, { "from": 223, "to": 224, "label": "CALL" }, { "from": 224, "to": 225, "label": "CASE" }, { "from": 225, "to": 226, "label": "EVAL with clause\nempty([]).\nand substitutionT58 -> []" }, { "from": 225, "to": 227, "label": "EVAL-BACKTRACK" }, { "from": 226, "to": 228, "label": "CUT" }, { "from": 227, "to": 231, "label": "FAILURE" }, { "from": 228, "to": 229, "label": "CASE" }, { "from": 229, "to": 230, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 231, "to": 232, "label": "FAILURE" }, { "from": 232, "to": 233, "label": "ONLY EVAL with clause\nno(X106).\nand substitutionT53 -> T63,\nX106 -> empty(T63),\nT62 -> T63" }, { "from": 233, "to": 234, "label": "CASE" }, { "from": 234, "to": 235, "label": "PARALLEL" }, { "from": 234, "to": 236, "label": "PARALLEL" }, { "from": 235, "to": 237, "label": "EVAL with clause\ntail([], []).\nand substitutionT63 -> [],\nX100 -> []" }, { "from": 235, "to": 238, "label": "EVAL-BACKTRACK" }, { "from": 236, "to": 239, "label": "EVAL with clause\ntail(.(X111, X112), X112).\nand substitutionX111 -> T68,\nX112 -> T70,\nT63 -> .(T68, T70),\nX100 -> T70,\nT69 -> T70" }, { "from": 236, "to": 240, "label": "EVAL-BACKTRACK" }, { "from": 237, "to": 13, "label": "INSTANCE" }, { "from": 239, "to": 214, "label": "INSTANCE with matching:\nT48 -> T70" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: s2lA(s(X1), .(X2, X3)) :- s2lA(X1, X3). listC([]) :- listB. listC(.(X1, X2)) :- listC(X2). goalD(0) :- listB. goalD(s(X1)) :- s2lA(X1, X2). goalD(s(X1)) :- ','(s2lcA(X1, X2), listC(X2)). Clauses: s2lcA(0, []). s2lcA(s(X1), .(X2, X3)) :- s2lcA(X1, X3). listcB. listcC([]). listcC([]) :- listcB. listcC(.(X1, X2)) :- listcC(X2). Afs: goalD(x1) = goalD(x1) ---------------------------------------- (3) UndefinedPredicateInTriplesTransformerProof (SOUND) Deleted triples and predicates having undefined goals [DT09]. ---------------------------------------- (4) Obligation: Triples: s2lA(s(X1), .(X2, X3)) :- s2lA(X1, X3). listC(.(X1, X2)) :- listC(X2). goalD(s(X1)) :- s2lA(X1, X2). goalD(s(X1)) :- ','(s2lcA(X1, X2), listC(X2)). Clauses: s2lcA(0, []). s2lcA(s(X1), .(X2, X3)) :- s2lcA(X1, X3). listcB. listcC([]). listcC([]) :- listcB. listcC(.(X1, X2)) :- listcC(X2). Afs: goalD(x1) = goalD(x1) ---------------------------------------- (5) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: goalD_in_1: (b) s2lA_in_2: (b,f) s2lcA_in_2: (b,f) listC_in_1: (b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: GOALD_IN_G(s(X1)) -> U3_G(X1, s2lA_in_ga(X1, X2)) GOALD_IN_G(s(X1)) -> S2LA_IN_GA(X1, X2) S2LA_IN_GA(s(X1), .(X2, X3)) -> U1_GA(X1, X2, X3, s2lA_in_ga(X1, X3)) S2LA_IN_GA(s(X1), .(X2, X3)) -> S2LA_IN_GA(X1, X3) GOALD_IN_G(s(X1)) -> U4_G(X1, s2lcA_in_ga(X1, X2)) U4_G(X1, s2lcA_out_ga(X1, X2)) -> U5_G(X1, listC_in_g(X2)) U4_G(X1, s2lcA_out_ga(X1, X2)) -> LISTC_IN_G(X2) LISTC_IN_G(.(X1, X2)) -> U2_G(X1, X2, listC_in_g(X2)) LISTC_IN_G(.(X1, X2)) -> LISTC_IN_G(X2) The TRS R consists of the following rules: s2lcA_in_ga(0, []) -> s2lcA_out_ga(0, []) s2lcA_in_ga(s(X1), .(X2, X3)) -> U7_ga(X1, X2, X3, s2lcA_in_ga(X1, X3)) U7_ga(X1, X2, X3, s2lcA_out_ga(X1, X3)) -> s2lcA_out_ga(s(X1), .(X2, X3)) The argument filtering Pi contains the following mapping: s(x1) = s(x1) s2lA_in_ga(x1, x2) = s2lA_in_ga(x1) .(x1, x2) = .(x2) s2lcA_in_ga(x1, x2) = s2lcA_in_ga(x1) 0 = 0 s2lcA_out_ga(x1, x2) = s2lcA_out_ga(x1, x2) U7_ga(x1, x2, x3, x4) = U7_ga(x1, x4) listC_in_g(x1) = listC_in_g(x1) GOALD_IN_G(x1) = GOALD_IN_G(x1) U3_G(x1, x2) = U3_G(x1, x2) S2LA_IN_GA(x1, x2) = S2LA_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) U4_G(x1, x2) = U4_G(x1, x2) U5_G(x1, x2) = U5_G(x1, x2) LISTC_IN_G(x1) = LISTC_IN_G(x1) U2_G(x1, x2, x3) = U2_G(x2, x3) 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: GOALD_IN_G(s(X1)) -> U3_G(X1, s2lA_in_ga(X1, X2)) GOALD_IN_G(s(X1)) -> S2LA_IN_GA(X1, X2) S2LA_IN_GA(s(X1), .(X2, X3)) -> U1_GA(X1, X2, X3, s2lA_in_ga(X1, X3)) S2LA_IN_GA(s(X1), .(X2, X3)) -> S2LA_IN_GA(X1, X3) GOALD_IN_G(s(X1)) -> U4_G(X1, s2lcA_in_ga(X1, X2)) U4_G(X1, s2lcA_out_ga(X1, X2)) -> U5_G(X1, listC_in_g(X2)) U4_G(X1, s2lcA_out_ga(X1, X2)) -> LISTC_IN_G(X2) LISTC_IN_G(.(X1, X2)) -> U2_G(X1, X2, listC_in_g(X2)) LISTC_IN_G(.(X1, X2)) -> LISTC_IN_G(X2) The TRS R consists of the following rules: s2lcA_in_ga(0, []) -> s2lcA_out_ga(0, []) s2lcA_in_ga(s(X1), .(X2, X3)) -> U7_ga(X1, X2, X3, s2lcA_in_ga(X1, X3)) U7_ga(X1, X2, X3, s2lcA_out_ga(X1, X3)) -> s2lcA_out_ga(s(X1), .(X2, X3)) The argument filtering Pi contains the following mapping: s(x1) = s(x1) s2lA_in_ga(x1, x2) = s2lA_in_ga(x1) .(x1, x2) = .(x2) s2lcA_in_ga(x1, x2) = s2lcA_in_ga(x1) 0 = 0 s2lcA_out_ga(x1, x2) = s2lcA_out_ga(x1, x2) U7_ga(x1, x2, x3, x4) = U7_ga(x1, x4) listC_in_g(x1) = listC_in_g(x1) GOALD_IN_G(x1) = GOALD_IN_G(x1) U3_G(x1, x2) = U3_G(x1, x2) S2LA_IN_GA(x1, x2) = S2LA_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x4) U4_G(x1, x2) = U4_G(x1, x2) U5_G(x1, x2) = U5_G(x1, x2) LISTC_IN_G(x1) = LISTC_IN_G(x1) U2_G(x1, x2, x3) = U2_G(x2, x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 7 less nodes. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: LISTC_IN_G(.(X1, X2)) -> LISTC_IN_G(X2) The TRS R consists of the following rules: s2lcA_in_ga(0, []) -> s2lcA_out_ga(0, []) s2lcA_in_ga(s(X1), .(X2, X3)) -> U7_ga(X1, X2, X3, s2lcA_in_ga(X1, X3)) U7_ga(X1, X2, X3, s2lcA_out_ga(X1, X3)) -> s2lcA_out_ga(s(X1), .(X2, X3)) The argument filtering Pi contains the following mapping: s(x1) = s(x1) .(x1, x2) = .(x2) s2lcA_in_ga(x1, x2) = s2lcA_in_ga(x1) 0 = 0 s2lcA_out_ga(x1, x2) = s2lcA_out_ga(x1, x2) U7_ga(x1, x2, x3, x4) = U7_ga(x1, x4) LISTC_IN_G(x1) = LISTC_IN_G(x1) 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: LISTC_IN_G(.(X1, X2)) -> LISTC_IN_G(X2) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) LISTC_IN_G(x1) = LISTC_IN_G(x1) 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: LISTC_IN_G(.(X2)) -> LISTC_IN_G(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: *LISTC_IN_G(.(X2)) -> LISTC_IN_G(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: S2LA_IN_GA(s(X1), .(X2, X3)) -> S2LA_IN_GA(X1, X3) The TRS R consists of the following rules: s2lcA_in_ga(0, []) -> s2lcA_out_ga(0, []) s2lcA_in_ga(s(X1), .(X2, X3)) -> U7_ga(X1, X2, X3, s2lcA_in_ga(X1, X3)) U7_ga(X1, X2, X3, s2lcA_out_ga(X1, X3)) -> s2lcA_out_ga(s(X1), .(X2, X3)) The argument filtering Pi contains the following mapping: s(x1) = s(x1) .(x1, x2) = .(x2) s2lcA_in_ga(x1, x2) = s2lcA_in_ga(x1) 0 = 0 s2lcA_out_ga(x1, x2) = s2lcA_out_ga(x1, x2) U7_ga(x1, x2, x3, x4) = U7_ga(x1, x4) S2LA_IN_GA(x1, x2) = S2LA_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (18) Obligation: Pi DP problem: The TRS P consists of the following rules: S2LA_IN_GA(s(X1), .(X2, X3)) -> S2LA_IN_GA(X1, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) .(x1, x2) = .(x2) S2LA_IN_GA(x1, x2) = S2LA_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (19) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: S2LA_IN_GA(s(X1)) -> S2LA_IN_GA(X1) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (21) 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: *S2LA_IN_GA(s(X1)) -> S2LA_IN_GA(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (22) YES