/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,a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 37 ms] (2) AND (3) IRSwT (4) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (5) TRUE (6) IRSwT (7) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (8) TRUE (9) IRSwT (10) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (11) TRUE (12) IRSwT (13) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (14) IRSwT (15) IntTRSCompressionProof [EQUIVALENT, 5 ms] (16) IRSwT (17) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (18) IRSwT (19) IRSwTTerminationDigraphProof [EQUIVALENT, 6 ms] (20) IRSwT (21) TempFilterProof [SOUND, 3 ms] (22) IRSwT (23) IRSwTToQDPProof [SOUND, 1 ms] (24) QDP (25) QDPSizeChangeProof [EQUIVALENT, 0 ms] (26) YES ---------------------------------------- (0) Obligation: Clauses: goal(A, B, C) :- ','(s2l(A, D), applast(D, B, C)). applast(L, X, Last) :- ','(app(L, .(X, []), LX), last(Last, LX)). last(X, .(X, [])) :- !. last(X, Y) :- ','(tail(Y, T), last(X, T)). app([], Y, Z) :- ','(!, eq(Y, Z)). app(X, Y, .(H, Z)) :- ','(head(X, H), ','(tail(X, T), app(T, Y, Z))). s2l(0, L) :- ','(!, eq(L, [])). s2l(X, .(X1, Xs)) :- ','(p(X, P), s2l(P, Xs)). head([], X2). head(.(X, X3), X). tail([], []). tail(.(X4, Xs), Xs). p(0, 0). p(s(X), X). eq(X, X). Query: goal(g,a,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(goal A B C)", "(',' (s2l A D) (applast D B C))" ], [ "(applast L X Last)", "(',' (app L (. X ([])) LX) (last Last LX))" ], [ "(last X (. X ([])))", "(!)" ], [ "(last X Y)", "(',' (tail Y T) (last X T))" ], [ "(app ([]) Y Z)", "(',' (!) (eq Y Z))" ], [ "(app X Y (. H Z))", "(',' (head X H) (',' (tail X T) (app T Y Z)))" ], [ "(s2l (0) L)", "(',' (!) (eq L ([])))" ], [ "(s2l X (. X1 Xs))", "(',' (p X P) (s2l P Xs))" ], [ "(head ([]) X2)", null ], [ "(head (. X X3) X)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X4 Xs) Xs)", null ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "type": "Nodes", "590": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T40 (. T41 ([])) X77)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X77"], "exprvars": [] } }, "591": { "goal": [{ "clause": -1, "scope": -1, "term": "(last T45 T44)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "592": { "goal": [ { "clause": 4, "scope": 6, "term": "(app T40 (. T41 ([])) X77)" }, { "clause": 5, "scope": 6, "term": "(app T40 (. T41 ([])) X77)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X77"], "exprvars": [] } }, "791": { "goal": [{ "clause": -1, "scope": -1, "term": "(last T136 T137)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "551": { "goal": [{ "clause": -1, "scope": -1, "term": "(s2l T23 X52)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T23"], "free": ["X52"], "exprvars": [] } }, "793": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "552": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "753": { "goal": [ { "clause": 2, "scope": 13, "term": "(last T45 T44)" }, { "clause": 3, "scope": 13, "term": "(last T45 T44)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "710": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail ([]) X116) (app X116 (. T66 ([])) X118))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X118", "X116" ], "exprvars": [] } }, "711": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "755": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_13)" }, { "clause": 3, "scope": 13, "term": "(last T45 T44)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "756": { "goal": [{ "clause": 3, "scope": 13, "term": "(last T45 T44)" }], "kb": { "nonunifying": [[ "(last T45 T44)", "(last X182 (. X182 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X182"], "exprvars": [] } }, "757": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "318": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (s2l T12 X17) (applast X17 T15 T16))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": ["X17"], "exprvars": [] } }, "714": { "goal": [ { "clause": 10, "scope": 9, "term": "(',' (tail ([]) X116) (app X116 (. T66 ([])) X118))" }, { "clause": 11, "scope": 9, "term": "(',' (tail ([]) X116) (app X116 (. T66 ([])) X118))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X118", "X116" ], "exprvars": [] } }, "758": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "319": { "goal": [{ "clause": -1, "scope": -1, "term": "(s2l T12 X17)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": ["X17"], "exprvars": [] } }, "715": { "goal": [{ "clause": 10, "scope": 9, "term": "(',' (tail ([]) X116) (app X116 (. T66 ([])) X118))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X118", "X116" ], "exprvars": [] } }, "716": { "goal": [{ "clause": 11, "scope": 9, "term": "(',' (tail ([]) X116) (app X116 (. T66 ([])) X118))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X118", "X116" ], "exprvars": [] } }, "717": { "goal": [{ "clause": -1, "scope": -1, "term": "(app ([]) (. T66 ([])) X118)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X118"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(goal T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "321": { "goal": [{ "clause": -1, "scope": -1, "term": "(applast T17 T15 T16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "762": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail T114 X191) (last T115 X191))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X191"], "exprvars": [] } }, "720": { "goal": [ { "clause": 4, "scope": 10, "term": "(app ([]) (. T66 ([])) X118)" }, { "clause": 5, "scope": 10, "term": "(app ([]) (. T66 ([])) X118)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X118"], "exprvars": [] } }, "325": { "goal": [ { "clause": 6, "scope": 2, "term": "(s2l T12 X17)" }, { "clause": 7, "scope": 2, "term": "(s2l T12 X17)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": ["X17"], "exprvars": [] } }, "326": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_2) (eq X27 ([])))" }, { "clause": 7, "scope": 2, "term": "(s2l (0) X17)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X17", "X27" ], "exprvars": [] } }, "327": { "goal": [{ "clause": 7, "scope": 2, "term": "(s2l T12 X17)" }], "kb": { "nonunifying": [[ "(s2l T12 X17)", "(s2l (0) X26)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": [ "X17", "X26" ], "exprvars": [] } }, "328": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq X27 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X27"], "exprvars": [] } }, "603": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_6) (eq (. T50 ([])) X92))" }, { "clause": 5, "scope": 6, "term": "(app T40 (. T41 ([])) X77)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X77", "X92" ], "exprvars": [] } }, "724": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_10) (eq (. T75 ([])) X152))" }, { "clause": 5, "scope": 10, "term": "(app ([]) (. T66 ([])) X118)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X118", "X152" ], "exprvars": [] } }, "604": { "goal": [{ "clause": 5, "scope": 6, "term": "(app T40 (. T41 ([])) X77)" }], "kb": { "nonunifying": [[ "(app T40 (. T41 ([])) X77)", "(app ([]) X90 X91)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X77", "X90", "X91" ], "exprvars": [] } }, "725": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq (. T75 ([])) X152)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X152"], "exprvars": [] } }, "605": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq (. T50 ([])) X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X92"], "exprvars": [] } }, "726": { "goal": [{ "clause": 14, "scope": 11, "term": "(eq (. T75 ([])) X152)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X152"], "exprvars": [] } }, "62": { "goal": [{ "clause": 0, "scope": 1, "term": "(goal T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "606": { "goal": [{ "clause": 14, "scope": 7, "term": "(eq (. T50 ([])) X92)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X92"], "exprvars": [] } }, "331": { "goal": [{ "clause": 14, "scope": 3, "term": "(eq X27 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X27"], "exprvars": [] } }, "771": { "goal": [ { "clause": 10, "scope": 14, "term": "(',' (tail T114 X191) (last T115 X191))" }, { "clause": 11, "scope": 14, "term": "(',' (tail T114 X191) (last T115 X191))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X191"], "exprvars": [] } }, "772": { "goal": [{ "clause": 10, "scope": 14, "term": "(',' (tail T114 X191) (last T115 X191))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X191"], "exprvars": [] } }, "333": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "773": { "goal": [{ "clause": 11, "scope": 14, "term": "(',' (tail T114 X191) (last T115 X191))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X191"], "exprvars": [] } }, "334": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "774": { "goal": [{ "clause": -1, "scope": -1, "term": "(last T117 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "775": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "579": { "goal": [{ "clause": 1, "scope": 5, "term": "(applast T17 T15 T16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "733": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "777": { "goal": [ { "clause": 2, "scope": 15, "term": "(last T117 ([]))" }, { "clause": 3, "scope": 15, "term": "(last T117 ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "734": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "614": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "735": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "779": { "goal": [{ "clause": 3, "scope": 15, "term": "(last T117 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "615": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "781": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail ([]) X203) (last T125 X203))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X203"], "exprvars": [] } }, "782": { "goal": [ { "clause": 10, "scope": 16, "term": "(',' (tail ([]) X203) (last T125 X203))" }, { "clause": 11, "scope": 16, "term": "(',' (tail ([]) X203) (last T125 X203))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X203"], "exprvars": [] } }, "740": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T85 T86) X116) (app X116 (. T87 ([])) X118))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X118", "X116" ], "exprvars": [] } }, "784": { "goal": [{ "clause": 10, "scope": 16, "term": "(',' (tail ([]) X203) (last T125 X203))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X203"], "exprvars": [] } }, "785": { "goal": [{ "clause": 11, "scope": 16, "term": "(',' (tail ([]) X203) (last T125 X203))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X203"], "exprvars": [] } }, "544": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T20 X50) (s2l X50 X52))" }], "kb": { "nonunifying": [[ "(s2l T20 X17)", "(s2l (0) X26)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T20"], "free": [ "X17", "X26", "X52", "X50" ], "exprvars": [] } }, "742": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "786": { "goal": [{ "clause": -1, "scope": -1, "term": "(last T125 ([]))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "589": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T40 (. T41 ([])) X77) (last T42 X77))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X77"], "exprvars": [] } }, "744": { "goal": [ { "clause": 10, "scope": 12, "term": "(',' (tail (. T85 T86) X116) (app X116 (. T87 ([])) X118))" }, { "clause": 11, "scope": 12, "term": "(',' (tail (. T85 T86) X116) (app X116 (. T87 ([])) X118))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X118", "X116" ], "exprvars": [] } }, "788": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "547": { "goal": [ { "clause": 12, "scope": 4, "term": "(',' (p T20 X50) (s2l X50 X52))" }, { "clause": 13, "scope": 4, "term": "(',' (p T20 X50) (s2l X50 X52))" } ], "kb": { "nonunifying": [[ "(s2l T20 X17)", "(s2l (0) X26)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T20"], "free": [ "X17", "X26", "X52", "X50" ], "exprvars": [] } }, "701": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T63 X117) (',' (tail T63 X116) (app X116 (. T64 ([])) X118)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X117", "X118", "X116" ], "exprvars": [] } }, "745": { "goal": [{ "clause": 11, "scope": 12, "term": "(',' (tail (. T85 T86) X116) (app X116 (. T87 ([])) X118))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X118", "X116" ], "exprvars": [] } }, "548": { "goal": [{ "clause": 13, "scope": 4, "term": "(',' (p T20 X50) (s2l X50 X52))" }], "kb": { "nonunifying": [[ "(s2l T20 X17)", "(s2l (0) X26)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T20"], "free": [ "X17", "X26", "X52", "X50" ], "exprvars": [] } }, "703": { "goal": [ { "clause": 8, "scope": 8, "term": "(',' (head T63 X117) (',' (tail T63 X116) (app X116 (. T64 ([])) X118)))" }, { "clause": 9, "scope": 8, "term": "(',' (head T63 X117) (',' (tail T63 X116) (app X116 (. T64 ([])) X118)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X117", "X118", "X116" ], "exprvars": [] } }, "704": { "goal": [{ "clause": 8, "scope": 8, "term": "(',' (head T63 X117) (',' (tail T63 X116) (app X116 (. T64 ([])) X118)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X117", "X118", "X116" ], "exprvars": [] } }, "748": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T98 (. T99 ([])) X118)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X118"], "exprvars": [] } }, "706": { "goal": [{ "clause": 9, "scope": 8, "term": "(',' (head T63 X117) (',' (tail T63 X116) (app X116 (. T64 ([])) X118)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [ "X117", "X118", "X116" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 62, "label": "CASE" }, { "from": 62, "to": 318, "label": "ONLY EVAL with clause\ngoal(X14, X15, X16) :- ','(s2l(X14, X17), applast(X17, X15, X16)).\nand substitutionT1 -> T12,\nX14 -> T12,\nT2 -> T15,\nX15 -> T15,\nT3 -> T16,\nX16 -> T16,\nT13 -> T15,\nT14 -> T16" }, { "from": 318, "to": 319, "label": "SPLIT 1" }, { "from": 318, "to": 321, "label": "SPLIT 2\nnew knowledge:\nT12 is ground\nreplacements:X17 -> T17" }, { "from": 319, "to": 325, "label": "CASE" }, { "from": 321, "to": 579, "label": "CASE" }, { "from": 325, "to": 326, "label": "EVAL with clause\ns2l(0, X26) :- ','(!_2, eq(X26, [])).\nand substitutionT12 -> 0,\nX17 -> X27,\nX26 -> X27" }, { "from": 325, "to": 327, "label": "EVAL-BACKTRACK" }, { "from": 326, "to": 328, "label": "CUT" }, { "from": 327, "to": 544, "label": "ONLY EVAL with clause\ns2l(X47, .(X48, X49)) :- ','(p(X47, X50), s2l(X50, X49)).\nand substitutionT12 -> T20,\nX47 -> T20,\nX48 -> X51,\nX49 -> X52,\nX17 -> .(X51, X52)" }, { "from": 328, "to": 331, "label": "CASE" }, { "from": 331, "to": 333, "label": "ONLY EVAL with clause\neq(X32, X32).\nand substitutionX27 -> [],\nX32 -> [],\nX33 -> []" }, { "from": 333, "to": 334, "label": "SUCCESS" }, { "from": 544, "to": 547, "label": "CASE" }, { "from": 547, "to": 548, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (s2l(T20, X17), s2l(0, X26))" }, { "from": 548, "to": 551, "label": "EVAL with clause\np(s(X57), X57).\nand substitutionX57 -> T23,\nT20 -> s(T23),\nX50 -> T23" }, { "from": 548, "to": 552, "label": "EVAL-BACKTRACK" }, { "from": 551, "to": 319, "label": "INSTANCE with matching:\nT12 -> T23\nX17 -> X52" }, { "from": 579, "to": 589, "label": "ONLY EVAL with clause\napplast(X74, X75, X76) :- ','(app(X74, .(X75, []), X77), last(X76, X77)).\nand substitutionT17 -> T40,\nX74 -> T40,\nT15 -> T41,\nX75 -> T41,\nT16 -> T42,\nX76 -> T42,\nT37 -> T40,\nT38 -> T41,\nT39 -> T42" }, { "from": 589, "to": 590, "label": "SPLIT 1" }, { "from": 589, "to": 591, "label": "SPLIT 2\nreplacements:X77 -> T44,\nT42 -> T45" }, { "from": 590, "to": 592, "label": "CASE" }, { "from": 591, "to": 753, "label": "CASE" }, { "from": 592, "to": 603, "label": "EVAL with clause\napp([], X90, X91) :- ','(!_6, eq(X90, X91)).\nand substitutionT40 -> [],\nT41 -> T50,\nX90 -> .(T50, []),\nX77 -> X92,\nX91 -> X92,\nT49 -> T50" }, { "from": 592, "to": 604, "label": "EVAL-BACKTRACK" }, { "from": 603, "to": 605, "label": "CUT" }, { "from": 604, "to": 701, "label": "ONLY EVAL with clause\napp(X112, X113, .(X114, X115)) :- ','(head(X112, X114), ','(tail(X112, X116), app(X116, X113, X115))).\nand substitutionT40 -> T63,\nX112 -> T63,\nT41 -> T64,\nX113 -> .(T64, []),\nX114 -> X117,\nX115 -> X118,\nX77 -> .(X117, X118),\nT61 -> T63,\nT62 -> T64" }, { "from": 605, "to": 606, "label": "CASE" }, { "from": 606, "to": 614, "label": "ONLY EVAL with clause\neq(X95, X95).\nand substitutionT50 -> T53,\nX95 -> .(T53, []),\nX92 -> .(T53, [])" }, { "from": 614, "to": 615, "label": "SUCCESS" }, { "from": 701, "to": 703, "label": "CASE" }, { "from": 703, "to": 704, "label": "PARALLEL" }, { "from": 703, "to": 706, "label": "PARALLEL" }, { "from": 704, "to": 710, "label": "EVAL with clause\nhead([], X130).\nand substitutionT63 -> [],\nX117 -> X131,\nX130 -> X131,\nT64 -> T66" }, { "from": 704, "to": 711, "label": "EVAL-BACKTRACK" }, { "from": 706, "to": 740, "label": "EVAL with clause\nhead(.(X162, X163), X162).\nand substitutionX162 -> T85,\nX163 -> T86,\nT63 -> .(T85, T86),\nX117 -> T85,\nT83 -> T85,\nT84 -> T86,\nT64 -> T87" }, { "from": 706, "to": 742, "label": "EVAL-BACKTRACK" }, { "from": 710, "to": 714, "label": "CASE" }, { "from": 714, "to": 715, "label": "PARALLEL" }, { "from": 714, "to": 716, "label": "PARALLEL" }, { "from": 715, "to": 717, "label": "ONLY EVAL with clause\ntail([], []).\nand substitutionX116 -> []" }, { "from": 716, "to": 735, "label": "BACKTRACK\nfor clause: tail(.(X4, Xs), Xs)because of non-unification" }, { "from": 717, "to": 720, "label": "CASE" }, { "from": 720, "to": 724, "label": "ONLY EVAL with clause\napp([], X150, X151) :- ','(!_10, eq(X150, X151)).\nand substitutionT66 -> T75,\nX150 -> .(T75, []),\nX118 -> X152,\nX151 -> X152,\nT74 -> T75" }, { "from": 724, "to": 725, "label": "CUT" }, { "from": 725, "to": 726, "label": "CASE" }, { "from": 726, "to": 733, "label": "ONLY EVAL with clause\neq(X155, X155).\nand substitutionT75 -> T78,\nX155 -> .(T78, []),\nX152 -> .(T78, [])" }, { "from": 733, "to": 734, "label": "SUCCESS" }, { "from": 740, "to": 744, "label": "CASE" }, { "from": 744, "to": 745, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 745, "to": 748, "label": "ONLY EVAL with clause\ntail(.(X174, X175), X175).\nand substitutionT85 -> T96,\nX174 -> T96,\nT86 -> T98,\nX175 -> T98,\nX116 -> T98,\nT97 -> T98,\nT87 -> T99" }, { "from": 748, "to": 590, "label": "INSTANCE with matching:\nT40 -> T98\nT41 -> T99\nX77 -> X118" }, { "from": 753, "to": 755, "label": "EVAL with clause\nlast(X182, .(X182, [])) :- !_13.\nand substitutionT45 -> T104,\nX182 -> T104,\nT44 -> .(T104, [])" }, { "from": 753, "to": 756, "label": "EVAL-BACKTRACK" }, { "from": 755, "to": 757, "label": "CUT" }, { "from": 756, "to": 762, "label": "ONLY EVAL with clause\nlast(X189, X190) :- ','(tail(X190, X191), last(X189, X191)).\nand substitutionT45 -> T115,\nX189 -> T115,\nT44 -> T114,\nX190 -> T114,\nT113 -> T114,\nT112 -> T115" }, { "from": 757, "to": 758, "label": "SUCCESS" }, { "from": 762, "to": 771, "label": "CASE" }, { "from": 771, "to": 772, "label": "PARALLEL" }, { "from": 771, "to": 773, "label": "PARALLEL" }, { "from": 772, "to": 774, "label": "EVAL with clause\ntail([], []).\nand substitutionT114 -> [],\nX191 -> [],\nT115 -> T117" }, { "from": 772, "to": 775, "label": "EVAL-BACKTRACK" }, { "from": 773, "to": 791, "label": "EVAL with clause\ntail(.(X214, X215), X215).\nand substitutionX214 -> T134,\nX215 -> T137,\nT114 -> .(T134, T137),\nX191 -> T137,\nT115 -> T136,\nT135 -> T137" }, { "from": 773, "to": 793, "label": "EVAL-BACKTRACK" }, { "from": 774, "to": 777, "label": "CASE" }, { "from": 777, "to": 779, "label": "BACKTRACK\nfor clause: last(X, .(X, [])) :- !because of non-unification" }, { "from": 779, "to": 781, "label": "ONLY EVAL with clause\nlast(X201, X202) :- ','(tail(X202, X203), last(X201, X203)).\nand substitutionT117 -> T125,\nX201 -> T125,\nX202 -> [],\nT124 -> T125" }, { "from": 781, "to": 782, "label": "CASE" }, { "from": 782, "to": 784, "label": "PARALLEL" }, { "from": 782, "to": 785, "label": "PARALLEL" }, { "from": 784, "to": 786, "label": "ONLY EVAL with clause\ntail([], []).\nand substitutionX203 -> []" }, { "from": 785, "to": 788, "label": "BACKTRACK\nfor clause: tail(.(X4, Xs), Xs)because of non-unification" }, { "from": 786, "to": 774, "label": "INSTANCE with matching:\nT117 -> T125" }, { "from": 791, "to": 591, "label": "INSTANCE with matching:\nT45 -> T136\nT44 -> T137" } ], "type": "Graph" } } ---------------------------------------- (2) Complex Obligation (AND) ---------------------------------------- (3) Obligation: Rules: f777_in -> f779_in :|: TRUE f779_out -> f777_out :|: TRUE f786_in -> f774_in :|: TRUE f774_out -> f786_out :|: TRUE f777_out -> f774_out :|: TRUE f774_in -> f777_in :|: TRUE f786_out -> f784_out :|: TRUE f784_in -> f786_in :|: TRUE f784_out -> f782_out :|: TRUE f785_out -> f782_out :|: TRUE f782_in -> f785_in :|: TRUE f782_in -> f784_in :|: TRUE f781_in -> f782_in :|: TRUE f782_out -> f781_out :|: TRUE f781_out -> f779_out :|: TRUE f779_in -> f781_in :|: TRUE f1_in(T1) -> f62_in(T1) :|: TRUE f62_out(x) -> f1_out(x) :|: TRUE f318_out(T12) -> f62_out(T12) :|: TRUE f62_in(x1) -> f318_in(x1) :|: TRUE f321_out -> f318_out(x2) :|: TRUE f319_out(x3) -> f321_in :|: TRUE f318_in(x4) -> f319_in(x4) :|: TRUE f579_out -> f321_out :|: TRUE f321_in -> f579_in :|: TRUE f579_in -> f589_in :|: TRUE f589_out -> f579_out :|: TRUE f589_in -> f590_in :|: TRUE f590_out -> f591_in :|: TRUE f591_out -> f589_out :|: TRUE f591_in -> f753_in :|: TRUE f753_out -> f591_out :|: TRUE f753_in -> f756_in :|: TRUE f755_out -> f753_out :|: TRUE f753_in -> f755_in :|: TRUE f756_out -> f753_out :|: TRUE f756_in -> f762_in :|: TRUE f762_out -> f756_out :|: TRUE f771_out -> f762_out :|: TRUE f762_in -> f771_in :|: TRUE f771_in -> f773_in :|: TRUE f772_out -> f771_out :|: TRUE f771_in -> f772_in :|: TRUE f773_out -> f771_out :|: TRUE f772_in -> f774_in :|: TRUE f774_out -> f772_out :|: TRUE f775_out -> f772_out :|: TRUE f772_in -> f775_in :|: TRUE Start term: f1_in(T1) ---------------------------------------- (4) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (5) TRUE ---------------------------------------- (6) Obligation: Rules: f591_out -> f791_out :|: TRUE f791_in -> f591_in :|: TRUE f791_out -> f773_out :|: TRUE f773_in -> f793_in :|: TRUE f793_out -> f773_out :|: TRUE f773_in -> f791_in :|: TRUE f753_in -> f756_in :|: TRUE f755_out -> f753_out :|: TRUE f753_in -> f755_in :|: TRUE f756_out -> f753_out :|: TRUE f771_in -> f773_in :|: TRUE f772_out -> f771_out :|: TRUE f771_in -> f772_in :|: TRUE f773_out -> f771_out :|: TRUE f591_in -> f753_in :|: TRUE f753_out -> f591_out :|: TRUE f756_in -> f762_in :|: TRUE f762_out -> f756_out :|: TRUE f771_out -> f762_out :|: TRUE f762_in -> f771_in :|: TRUE f1_in(T1) -> f62_in(T1) :|: TRUE f62_out(x) -> f1_out(x) :|: TRUE f318_out(T12) -> f62_out(T12) :|: TRUE f62_in(x1) -> f318_in(x1) :|: TRUE f321_out -> f318_out(x2) :|: TRUE f319_out(x3) -> f321_in :|: TRUE f318_in(x4) -> f319_in(x4) :|: TRUE f579_out -> f321_out :|: TRUE f321_in -> f579_in :|: TRUE f579_in -> f589_in :|: TRUE f589_out -> f579_out :|: TRUE f589_in -> f590_in :|: TRUE f590_out -> f591_in :|: TRUE f591_out -> f589_out :|: TRUE Start term: f1_in(T1) ---------------------------------------- (7) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (8) TRUE ---------------------------------------- (9) Obligation: Rules: f745_in -> f748_in :|: TRUE f748_out -> f745_out :|: TRUE f703_in -> f706_in :|: TRUE f703_in -> f704_in :|: TRUE f704_out -> f703_out :|: TRUE f706_out -> f703_out :|: TRUE f745_out -> f744_out :|: TRUE f744_in -> f745_in :|: TRUE f592_in -> f604_in :|: TRUE f603_out -> f592_out :|: TRUE f592_in -> f603_in :|: TRUE f604_out -> f592_out :|: TRUE f740_in -> f744_in :|: TRUE f744_out -> f740_out :|: TRUE f748_in -> f590_in :|: TRUE f590_out -> f748_out :|: TRUE f703_out -> f701_out :|: TRUE f701_in -> f703_in :|: TRUE f701_out -> f604_out :|: TRUE f604_in -> f701_in :|: TRUE f706_in -> f740_in :|: TRUE f742_out -> f706_out :|: TRUE f740_out -> f706_out :|: TRUE f706_in -> f742_in :|: TRUE f590_in -> f592_in :|: TRUE f592_out -> f590_out :|: TRUE f1_in(T1) -> f62_in(T1) :|: TRUE f62_out(x) -> f1_out(x) :|: TRUE f318_out(T12) -> f62_out(T12) :|: TRUE f62_in(x1) -> f318_in(x1) :|: TRUE f321_out -> f318_out(x2) :|: TRUE f319_out(x3) -> f321_in :|: TRUE f318_in(x4) -> f319_in(x4) :|: TRUE f579_out -> f321_out :|: TRUE f321_in -> f579_in :|: TRUE f579_in -> f589_in :|: TRUE f589_out -> f579_out :|: TRUE f589_in -> f590_in :|: TRUE f590_out -> f591_in :|: TRUE f591_out -> f589_out :|: TRUE Start term: f1_in(T1) ---------------------------------------- (10) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (11) TRUE ---------------------------------------- (12) Obligation: Rules: f325_in(T12) -> f327_in(T12) :|: TRUE f327_out(x) -> f325_out(x) :|: TRUE f325_in(0) -> f326_in :|: TRUE f326_out -> f325_out(0) :|: TRUE f327_in(T20) -> f544_in(T20) :|: TRUE f544_out(x1) -> f327_out(x1) :|: TRUE f544_in(x2) -> f547_in(x2) :|: TRUE f547_out(x3) -> f544_out(x3) :|: TRUE f552_out -> f548_out(x4) :|: TRUE f551_out(T23) -> f548_out(s(T23)) :|: TRUE f548_in(x5) -> f552_in :|: TRUE f548_in(s(x6)) -> f551_in(x6) :|: TRUE f325_out(x7) -> f319_out(x7) :|: TRUE f319_in(x8) -> f325_in(x8) :|: TRUE f548_out(x9) -> f547_out(x9) :|: TRUE f547_in(x10) -> f548_in(x10) :|: TRUE f319_out(x11) -> f551_out(x11) :|: TRUE f551_in(x12) -> f319_in(x12) :|: TRUE f1_in(T1) -> f62_in(T1) :|: TRUE f62_out(x13) -> f1_out(x13) :|: TRUE f318_out(x14) -> f62_out(x14) :|: TRUE f62_in(x15) -> f318_in(x15) :|: TRUE f321_out -> f318_out(x16) :|: TRUE f319_out(x17) -> f321_in :|: TRUE f318_in(x18) -> f319_in(x18) :|: TRUE Start term: f1_in(T1) ---------------------------------------- (13) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f325_in(T12) -> f327_in(T12) :|: TRUE f327_in(T20) -> f544_in(T20) :|: TRUE f544_in(x2) -> f547_in(x2) :|: TRUE f548_in(s(x6)) -> f551_in(x6) :|: TRUE f319_in(x8) -> f325_in(x8) :|: TRUE f547_in(x10) -> f548_in(x10) :|: TRUE f551_in(x12) -> f319_in(x12) :|: TRUE ---------------------------------------- (14) Obligation: Rules: f325_in(T12) -> f327_in(T12) :|: TRUE f327_in(T20) -> f544_in(T20) :|: TRUE f544_in(x2) -> f547_in(x2) :|: TRUE f548_in(s(x6)) -> f551_in(x6) :|: TRUE f319_in(x8) -> f325_in(x8) :|: TRUE f547_in(x10) -> f548_in(x10) :|: TRUE f551_in(x12) -> f319_in(x12) :|: TRUE ---------------------------------------- (15) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (16) Obligation: Rules: f319_in(s(x6:0)) -> f319_in(x6:0) :|: TRUE ---------------------------------------- (17) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (18) Obligation: Rules: f319_in(s(x6:0)) -> f319_in(x6:0) :|: TRUE ---------------------------------------- (19) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f319_in(s(x6:0)) -> f319_in(x6:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (20) Obligation: Termination digraph: Nodes: (1) f319_in(s(x6:0)) -> f319_in(x6:0) :|: TRUE Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (21) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f319_in(VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (22) Obligation: Rules: f319_in(s(x6:0)) -> f319_in(x6:0) ---------------------------------------- (23) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: f319_in(s(x6:0)) -> f319_in(x6:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (25) 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: *f319_in(s(x6:0)) -> f319_in(x6:0) The graph contains the following edges 1 > 1 ---------------------------------------- (26) YES