/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern goal(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 37 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, 13 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), append(Xs, X1, X2)). append([], Y, Z) :- ','(!, eq(Y, Z)). append(X, Y, .(H, Z)) :- ','(head(X, H), ','(tail(X, T), append(T, Y, Z))). s2l(0, L) :- ','(!, eq(L, [])). s2l(X, .(X3, Xs)) :- ','(p(X, P), s2l(P, Xs)). head([], X4). head(.(H, X5), H). tail([], []). tail(.(X6, Xs), Xs). p(0, 0). p(s(X), X). eq(X, X). Query: goal(g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(goal X)", "(',' (s2l X Xs) (append Xs X1 X2))" ], [ "(append ([]) Y Z)", "(',' (!) (eq Y Z))" ], [ "(append X Y (. H Z))", "(',' (head X H) (',' (tail X T) (append T Y Z)))" ], [ "(s2l (0) L)", "(',' (!) (eq L ([])))" ], [ "(s2l X (. X3 Xs))", "(',' (p X P) (s2l P Xs))" ], [ "(head ([]) X4)", null ], [ "(head (. H X5) H)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X6 Xs) Xs)", null ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "89": { "goal": [ { "clause": 9, "scope": 6, "term": "(',' (',' (p T6 X70) (s2l X70 X72)) (append (. X71 X72) X10 X11))" }, { "clause": 10, "scope": 6, "term": "(',' (',' (p T6 X70) (s2l X70 X72)) (append (. X71 X72) X10 X11))" } ], "kb": { "nonunifying": [[ "(s2l T6 X9)", "(s2l (0) X16)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X9", "X10", "X11", "X16", "X71", "X72", "X70" ], "exprvars": [] } }, "type": "Nodes", "152": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head (. X150 T21) X152) (',' (tail (. X150 T21) X149) (append X149 X151 X153)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X150", "X151", "X152", "X153", "X149" ], "exprvars": [] } }, "110": { "goal": [{ "clause": 10, "scope": 9, "term": "(',' (p T13 X110) (s2l X110 X112))" }], "kb": { "nonunifying": [[ "(s2l T13 X72)", "(s2l (0) X86)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [ "X72", "X86", "X112", "X110" ], "exprvars": [] } }, "473": { "goal": [{ "clause": 5, "scope": 15, "term": "(',' (head T36 X236) (',' (tail T36 X234) (append X234 X235 X237)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X236", "X237", "X234" ], "exprvars": [] } }, "474": { "goal": [{ "clause": 6, "scope": 15, "term": "(',' (head T36 X236) (',' (tail T36 X234) (append X234 X235 X237)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X236", "X237", "X234" ], "exprvars": [] } }, "112": { "goal": [{ "clause": -1, "scope": -1, "term": "(s2l T16 X112)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T16"], "free": ["X112"], "exprvars": [] } }, "310": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. X171 T26) X149) (append X149 X151 X153))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X151", "X153", "X149", "X171" ], "exprvars": [] } }, "431": { "goal": [ { "clause": 1, "scope": 13, "term": "(append T31 X151 X153)" }, { "clause": 2, "scope": 13, "term": "(append T31 X151 X153)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X151", "X153" ], "exprvars": [] } }, "475": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail ([]) X234) (append X234 X235 X237))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X237", "X234" ], "exprvars": [] } }, "113": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "476": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "477": { "goal": [ { "clause": 7, "scope": 16, "term": "(',' (tail ([]) X234) (append X234 X235 X237))" }, { "clause": 8, "scope": 16, "term": "(',' (tail ([]) X234) (append X234 X235 X237))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X237", "X234" ], "exprvars": [] } }, "116": { "goal": [ { "clause": 1, "scope": 10, "term": "(append (. X71 T10) X10 X11)" }, { "clause": 2, "scope": 10, "term": "(append (. X71 T10) X10 X11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X11", "X71" ], "exprvars": [] } }, "90": { "goal": [{ "clause": 10, "scope": 6, "term": "(',' (',' (p T6 X70) (s2l X70 X72)) (append (. X71 X72) X10 X11))" }], "kb": { "nonunifying": [[ "(s2l T6 X9)", "(s2l (0) X16)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X9", "X10", "X11", "X16", "X71", "X72", "X70" ], "exprvars": [] } }, "118": { "goal": [{ "clause": 2, "scope": 10, "term": "(append (. X71 T10) X10 X11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X11", "X71" ], "exprvars": [] } }, "437": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_13) (eq X203 X204))" }, { "clause": 2, "scope": 13, "term": "(append T31 X151 X153)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X151", "X153", "X203", "X204" ], "exprvars": [] } }, "93": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (s2l T9 X72) (append (. X71 X72) X10 X11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X10", "X11", "X71", "X72" ], "exprvars": [] } }, "94": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_2) (eq X17 ([]))) (append X17 X10 X11))" }, { "clause": 4, "scope": 2, "term": "(',' (s2l (0) X9) (append X9 X10 X11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X9", "X10", "X11", "X17" ], "exprvars": [] } }, "98": { "goal": [{ "clause": -1, "scope": -1, "term": "(s2l T9 X72)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X72"], "exprvars": [] } }, "11": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (s2l T3 X9) (append X9 X10 X11))" }], "kb": { "nonunifying": [[ "(s2l T3 X9)", "(s2l (0) X16)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [ "X9", "X10", "X11", "X16" ], "exprvars": [] } }, "99": { "goal": [{ "clause": -1, "scope": -1, "term": "(append (. X71 T10) X10 X11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X11", "X71" ], "exprvars": [] } }, "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (eq X17 ([])) (append X17 X10 X11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X11", "X17" ], "exprvars": [] } }, "15": { "goal": [{ "clause": 11, "scope": 3, "term": "(',' (eq X17 ([])) (append X17 X10 X11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X11", "X17" ], "exprvars": [] } }, "16": { "goal": [{ "clause": -1, "scope": -1, "term": "(append ([]) X10 X11)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X11" ], "exprvars": [] } }, "18": { "goal": [ { "clause": 1, "scope": 4, "term": "(append ([]) X10 X11)" }, { "clause": 2, "scope": 4, "term": "(append ([]) X10 X11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X11" ], "exprvars": [] } }, "19": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_4) (eq X46 X47))" }, { "clause": 2, "scope": 4, "term": "(append ([]) X10 X11)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X10", "X11", "X46", "X47" ], "exprvars": [] } }, "440": { "goal": [{ "clause": 2, "scope": 13, "term": "(append T31 X151 X153)" }], "kb": { "nonunifying": [[ "(append T31 X151 X153)", "(append ([]) X201 X202)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X151", "X153", "X201", "X202" ], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(goal T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "442": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq X203 X204)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X203", "X204" ], "exprvars": [] } }, "445": { "goal": [{ "clause": 11, "scope": 14, "term": "(eq X203 X204)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X203", "X204" ], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(goal T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (s2l T3 X9) (append X9 X10 X11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "9": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (s2l T3 X9) (append X9 X10 X11))" }, { "clause": 4, "scope": 2, "term": "(',' (s2l T3 X9) (append X9 X10 X11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [ "X9", "X10", "X11" ], "exprvars": [] } }, "526": { "goal": [{ "clause": 7, "scope": 16, "term": "(',' (tail ([]) X234) (append X234 X235 X237))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X237", "X234" ], "exprvars": [] } }, "527": { "goal": [{ "clause": 8, "scope": 16, "term": "(',' (tail ([]) X234) (append X234 X235 X237))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X237", "X234" ], "exprvars": [] } }, "528": { "goal": [{ "clause": -1, "scope": -1, "term": "(append ([]) X235 X237)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X237" ], "exprvars": [] } }, "529": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq X46 X47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X46", "X47" ], "exprvars": [] } }, "21": { "goal": [{ "clause": 11, "scope": 5, "term": "(eq X46 X47)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X46", "X47" ], "exprvars": [] } }, "22": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "530": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T43 T44) X234) (append X234 X235 X237))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X237", "X234" ], "exprvars": [] } }, "531": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "532": { "goal": [ { "clause": 7, "scope": 17, "term": "(',' (tail (. T43 T44) X234) (append X234 X235 X237))" }, { "clause": 8, "scope": 17, "term": "(',' (tail (. T43 T44) X234) (append X234 X235 X237))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X237", "X234" ], "exprvars": [] } }, "533": { "goal": [{ "clause": 8, "scope": 17, "term": "(',' (tail (. T43 T44) X234) (append X234 X235 X237))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X237", "X234" ], "exprvars": [] } }, "457": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "534": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T52 X235 X237)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X237" ], "exprvars": [] } }, "458": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "415": { "goal": [ { "clause": 7, "scope": 12, "term": "(',' (tail (. X171 T26) X149) (append X149 X151 X153))" }, { "clause": 8, "scope": 12, "term": "(',' (tail (. X171 T26) X149) (append X149 X151 X153))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X151", "X153", "X149", "X171" ], "exprvars": [] } }, "416": { "goal": [{ "clause": 8, "scope": 12, "term": "(',' (tail (. X171 T26) X149) (append X149 X151 X153))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X151", "X153", "X149", "X171" ], "exprvars": [] } }, "462": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T36 X236) (',' (tail T36 X234) (append X234 X235 X237)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X236", "X237", "X234" ], "exprvars": [] } }, "100": { "goal": [ { "clause": 3, "scope": 7, "term": "(s2l T9 X72)" }, { "clause": 4, "scope": 7, "term": "(s2l T9 X72)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": ["X72"], "exprvars": [] } }, "101": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_7) (eq X87 ([])))" }, { "clause": 4, "scope": 7, "term": "(s2l (0) X72)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X72", "X87" ], "exprvars": [] } }, "102": { "goal": [{ "clause": 4, "scope": 7, "term": "(s2l T9 X72)" }], "kb": { "nonunifying": [[ "(s2l T9 X72)", "(s2l (0) X86)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X72", "X86" ], "exprvars": [] } }, "465": { "goal": [ { "clause": 5, "scope": 15, "term": "(',' (head T36 X236) (',' (tail T36 X234) (append X234 X235 X237)))" }, { "clause": 6, "scope": 15, "term": "(',' (head T36 X236) (',' (tail T36 X234) (append X234 X235 X237)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X235", "X236", "X237", "X234" ], "exprvars": [] } }, "103": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq X87 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X87"], "exprvars": [] } }, "104": { "goal": [{ "clause": 11, "scope": 8, "term": "(eq X87 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X87"], "exprvars": [] } }, "105": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "303": { "goal": [ { "clause": 5, "scope": 11, "term": "(',' (head (. X150 T21) X152) (',' (tail (. X150 T21) X149) (append X149 X151 X153)))" }, { "clause": 6, "scope": 11, "term": "(',' (head (. X150 T21) X152) (',' (tail (. X150 T21) X149) (append X149 X151 X153)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X150", "X151", "X152", "X153", "X149" ], "exprvars": [] } }, "424": { "goal": [{ "clause": -1, "scope": -1, "term": "(append T31 X151 X153)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X151", "X153" ], "exprvars": [] } }, "106": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "304": { "goal": [{ "clause": 6, "scope": 11, "term": "(',' (head (. X150 T21) X152) (',' (tail (. X150 T21) X149) (append X149 X151 X153)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X150", "X151", "X152", "X153", "X149" ], "exprvars": [] } }, "108": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T13 X110) (s2l X110 X112))" }], "kb": { "nonunifying": [[ "(s2l T13 X72)", "(s2l (0) X86)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [ "X72", "X86", "X112", "X110" ], "exprvars": [] } }, "109": { "goal": [ { "clause": 9, "scope": 9, "term": "(',' (p T13 X110) (s2l X110 X112))" }, { "clause": 10, "scope": 9, "term": "(',' (p T13 X110) (s2l X110 X112))" } ], "kb": { "nonunifying": [[ "(s2l T13 X72)", "(s2l (0) X86)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [ "X72", "X86", "X112", "X110" ], "exprvars": [] } }, "87": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (p T6 X70) (s2l X70 X72)) (append (. X71 X72) X10 X11))" }], "kb": { "nonunifying": [[ "(s2l T6 X9)", "(s2l (0) X16)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [ "X9", "X10", "X11", "X16", "X71", "X72", "X70" ], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 8, "label": "ONLY EVAL with clause\ngoal(X8) :- ','(s2l(X8, X9), append(X9, X10, X11)).\nand substitutionT1 -> T3,\nX8 -> T3" }, { "from": 8, "to": 9, "label": "CASE" }, { "from": 9, "to": 10, "label": "EVAL with clause\ns2l(0, X16) :- ','(!_2, eq(X16, [])).\nand substitutionT3 -> 0,\nX9 -> X17,\nX16 -> X17" }, { "from": 9, "to": 11, "label": "EVAL-BACKTRACK" }, { "from": 10, "to": 12, "label": "CUT" }, { "from": 11, "to": 87, "label": "ONLY EVAL with clause\ns2l(X67, .(X68, X69)) :- ','(p(X67, X70), s2l(X70, X69)).\nand substitutionT3 -> T6,\nX67 -> T6,\nX68 -> X71,\nX69 -> X72,\nX9 -> .(X71, X72)" }, { "from": 12, "to": 15, "label": "CASE" }, { "from": 15, "to": 16, "label": "ONLY EVAL with clause\neq(X30, X30).\nand substitutionX17 -> [],\nX30 -> [],\nX31 -> []" }, { "from": 16, "to": 18, "label": "CASE" }, { "from": 18, "to": 19, "label": "ONLY EVAL with clause\nappend([], X44, X45) :- ','(!_4, eq(X44, X45)).\nand substitutionX10 -> X46,\nX44 -> X46,\nX11 -> X47,\nX45 -> X47" }, { "from": 19, "to": 20, "label": "CUT" }, { "from": 20, "to": 21, "label": "CASE" }, { "from": 21, "to": 22, "label": "ONLY EVAL with clause\neq(X52, X52).\nand substitutionX46 -> X53,\nX52 -> X53,\nX47 -> X53" }, { "from": 22, "to": 23, "label": "SUCCESS" }, { "from": 87, "to": 89, "label": "CASE" }, { "from": 89, "to": 90, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (s2l(T6, X9), s2l(0, X16))" }, { "from": 90, "to": 93, "label": "EVAL with clause\np(s(X77), X77).\nand substitutionX77 -> T9,\nT6 -> s(T9),\nX70 -> T9" }, { "from": 90, "to": 94, "label": "EVAL-BACKTRACK" }, { "from": 93, "to": 98, "label": "SPLIT 1" }, { "from": 93, "to": 99, "label": "SPLIT 2\nnew knowledge:\nT9 is ground\nreplacements:X72 -> T10" }, { "from": 98, "to": 100, "label": "CASE" }, { "from": 99, "to": 116, "label": "CASE" }, { "from": 100, "to": 101, "label": "EVAL with clause\ns2l(0, X86) :- ','(!_7, eq(X86, [])).\nand substitutionT9 -> 0,\nX72 -> X87,\nX86 -> X87" }, { "from": 100, "to": 102, "label": "EVAL-BACKTRACK" }, { "from": 101, "to": 103, "label": "CUT" }, { "from": 102, "to": 108, "label": "ONLY EVAL with clause\ns2l(X107, .(X108, X109)) :- ','(p(X107, X110), s2l(X110, X109)).\nand substitutionT9 -> T13,\nX107 -> T13,\nX108 -> X111,\nX109 -> X112,\nX72 -> .(X111, X112)" }, { "from": 103, "to": 104, "label": "CASE" }, { "from": 104, "to": 105, "label": "ONLY EVAL with clause\neq(X92, X92).\nand substitutionX87 -> [],\nX92 -> [],\nX93 -> []" }, { "from": 105, "to": 106, "label": "SUCCESS" }, { "from": 108, "to": 109, "label": "CASE" }, { "from": 109, "to": 110, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (s2l(T13, X72), s2l(0, X86))" }, { "from": 110, "to": 112, "label": "EVAL with clause\np(s(X117), X117).\nand substitutionX117 -> T16,\nT13 -> s(T16),\nX110 -> T16" }, { "from": 110, "to": 113, "label": "EVAL-BACKTRACK" }, { "from": 112, "to": 98, "label": "INSTANCE with matching:\nT9 -> T16\nX72 -> X112" }, { "from": 116, "to": 118, "label": "BACKTRACK\nfor clause: append([], Y, Z) :- ','(!, eq(Y, Z))because of non-unification" }, { "from": 118, "to": 152, "label": "ONLY EVAL with clause\nappend(X145, X146, .(X147, X148)) :- ','(head(X145, X147), ','(tail(X145, X149), append(X149, X146, X148))).\nand substitutionX71 -> X150,\nT10 -> T21,\nX145 -> .(X150, T21),\nX10 -> X151,\nX146 -> X151,\nX147 -> X152,\nX148 -> X153,\nX11 -> .(X152, X153),\nT20 -> T21" }, { "from": 152, "to": 303, "label": "CASE" }, { "from": 303, "to": 304, "label": "BACKTRACK\nfor clause: head([], X4)because of non-unification" }, { "from": 304, "to": 310, "label": "ONLY EVAL with clause\nhead(.(X169, X170), X169).\nand substitutionX150 -> X171,\nX169 -> X171,\nT21 -> T26,\nX170 -> T26,\nX152 -> X171,\nT25 -> T26" }, { "from": 310, "to": 415, "label": "CASE" }, { "from": 415, "to": 416, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 416, "to": 424, "label": "ONLY EVAL with clause\ntail(.(X186, X187), X187).\nand substitutionX171 -> X188,\nX186 -> X188,\nT26 -> T31,\nX187 -> T31,\nX149 -> T31,\nT30 -> T31" }, { "from": 424, "to": 431, "label": "CASE" }, { "from": 431, "to": 437, "label": "EVAL with clause\nappend([], X201, X202) :- ','(!_13, eq(X201, X202)).\nand substitutionT31 -> [],\nX151 -> X203,\nX201 -> X203,\nX153 -> X204,\nX202 -> X204" }, { "from": 431, "to": 440, "label": "EVAL-BACKTRACK" }, { "from": 437, "to": 442, "label": "CUT" }, { "from": 440, "to": 462, "label": "ONLY EVAL with clause\nappend(X230, X231, .(X232, X233)) :- ','(head(X230, X232), ','(tail(X230, X234), append(X234, X231, X233))).\nand substitutionT31 -> T36,\nX230 -> T36,\nX151 -> X235,\nX231 -> X235,\nX232 -> X236,\nX233 -> X237,\nX153 -> .(X236, X237),\nT35 -> T36" }, { "from": 442, "to": 445, "label": "CASE" }, { "from": 445, "to": 457, "label": "ONLY EVAL with clause\neq(X209, X209).\nand substitutionX203 -> X210,\nX209 -> X210,\nX204 -> X210" }, { "from": 457, "to": 458, "label": "SUCCESS" }, { "from": 462, "to": 465, "label": "CASE" }, { "from": 465, "to": 473, "label": "PARALLEL" }, { "from": 465, "to": 474, "label": "PARALLEL" }, { "from": 473, "to": 475, "label": "EVAL with clause\nhead([], X250).\nand substitutionT36 -> [],\nX236 -> X251,\nX250 -> X251" }, { "from": 473, "to": 476, "label": "EVAL-BACKTRACK" }, { "from": 474, "to": 530, "label": "EVAL with clause\nhead(.(X274, X275), X274).\nand substitutionX274 -> T43,\nX275 -> T44,\nT36 -> .(T43, T44),\nX236 -> T43,\nT41 -> T43,\nT42 -> T44" }, { "from": 474, "to": 531, "label": "EVAL-BACKTRACK" }, { "from": 475, "to": 477, "label": "CASE" }, { "from": 477, "to": 526, "label": "PARALLEL" }, { "from": 477, "to": 527, "label": "PARALLEL" }, { "from": 526, "to": 528, "label": "ONLY EVAL with clause\ntail([], []).\nand substitutionX234 -> []" }, { "from": 527, "to": 529, "label": "BACKTRACK\nfor clause: tail(.(X6, Xs), Xs)because of non-unification" }, { "from": 528, "to": 16, "label": "INSTANCE with matching:\nX10 -> X235\nX11 -> X237" }, { "from": 530, "to": 532, "label": "CASE" }, { "from": 532, "to": 533, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 533, "to": 534, "label": "ONLY EVAL with clause\ntail(.(X288, X289), X289).\nand substitutionT43 -> T50,\nX288 -> T50,\nT44 -> T52,\nX289 -> T52,\nX234 -> T52,\nT51 -> T52" }, { "from": 534, "to": 424, "label": "INSTANCE with matching:\nT31 -> T52\nX151 -> X235\nX153 -> X237" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: s2lA(s(X1), .(X2, X3)) :- s2lA(X1, X3). appendC([], X1, .(X2, X3)) :- appendB(X1, X3). appendC(.(X1, X2), X3, .(X1, X4)) :- appendC(X2, X3, X4). goalD(0) :- appendB(X1, X2). goalD(s(X1)) :- s2lA(X1, X2). goalD(s(X1)) :- ','(s2lcA(X1, X2), appendC(X2, X3, X4)). Clauses: s2lcA(0, []). s2lcA(s(X1), .(X2, X3)) :- s2lcA(X1, X3). appendcB(X1, X1). appendcC([], X1, X1). appendcC([], X1, .(X2, X3)) :- appendcB(X1, X3). appendcC(.(X1, X2), X3, .(X1, X4)) :- appendcC(X2, X3, X4). 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). appendC(.(X1, X2), X3, .(X1, X4)) :- appendC(X2, X3, X4). goalD(s(X1)) :- s2lA(X1, X2). goalD(s(X1)) :- ','(s2lcA(X1, X2), appendC(X2, X3, X4)). Clauses: s2lcA(0, []). s2lcA(s(X1), .(X2, X3)) :- s2lcA(X1, X3). appendcB(X1, X1). appendcC([], X1, X1). appendcC([], X1, .(X2, X3)) :- appendcB(X1, X3). appendcC(.(X1, X2), X3, .(X1, X4)) :- appendcC(X2, X3, X4). 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) appendC_in_3: (b,f,f) 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, appendC_in_gaa(X2, X3, X4)) U4_G(X1, s2lcA_out_ga(X1, X2)) -> APPENDC_IN_GAA(X2, X3, X4) APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U2_GAA(X1, X2, X3, X4, appendC_in_gaa(X2, X3, X4)) APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4) 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) appendC_in_gaa(x1, x2, x3) = appendC_in_gaa(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) APPENDC_IN_GAA(x1, x2, x3) = APPENDC_IN_GAA(x1) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x2, x5) 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, appendC_in_gaa(X2, X3, X4)) U4_G(X1, s2lcA_out_ga(X1, X2)) -> APPENDC_IN_GAA(X2, X3, X4) APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> U2_GAA(X1, X2, X3, X4, appendC_in_gaa(X2, X3, X4)) APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4) 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) appendC_in_gaa(x1, x2, x3) = appendC_in_gaa(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) APPENDC_IN_GAA(x1, x2, x3) = APPENDC_IN_GAA(x1) U2_GAA(x1, x2, x3, x4, x5) = U2_GAA(x2, x5) 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: APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4) 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) APPENDC_IN_GAA(x1, x2, x3) = APPENDC_IN_GAA(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: APPENDC_IN_GAA(.(X1, X2), X3, .(X1, X4)) -> APPENDC_IN_GAA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x2) APPENDC_IN_GAA(x1, x2, x3) = APPENDC_IN_GAA(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: APPENDC_IN_GAA(.(X2)) -> APPENDC_IN_GAA(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: *APPENDC_IN_GAA(.(X2)) -> APPENDC_IN_GAA(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