/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 ordered(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 62 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) PiDPToQDPProof [EQUIVALENT, 0 ms] (23) QDP (24) MRRProof [EQUIVALENT, 0 ms] (25) QDP (26) DependencyGraphProof [EQUIVALENT, 0 ms] (27) TRUE ---------------------------------------- (0) Obligation: Clauses: ordered([]) :- !. ordered(.(X1, [])) :- !. ordered(Xs) :- ','(head(Xs, X), ','(tail(Xs, Ys), ','(head(Ys, Y), ','(tail(Ys, Zs), ','(less(X, s(Y)), ordered(.(Y, Zs))))))). head([], X2). head(.(X, X3), X). tail([], []). tail(.(X4, Xs), Xs). less(0, Y) :- ','(!, eq(Y, s(X5))). less(X, Y) :- ','(p(X, Px), ','(p(Y, Py), less(Px, Py))). p(0, 0). p(s(X), X). eq(X, X). Query: ordered(g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(ordered ([]))", "(!)" ], [ "(ordered (. X1 ([])))", "(!)" ], [ "(ordered Xs)", "(',' (head Xs X) (',' (tail Xs Ys) (',' (head Ys Y) (',' (tail Ys Zs) (',' (less X (s Y)) (ordered (. Y Zs)))))))" ], [ "(head ([]) X2)", null ], [ "(head (. X X3) X)", null ], [ "(tail ([]) ([]))", null ], [ "(tail (. X4 Xs) Xs)", null ], [ "(less (0) Y)", "(',' (!) (eq Y (s X5)))" ], [ "(less X Y)", "(',' (p X Px) (',' (p Y Py) (less Px Py)))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "44": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T22 T23) X13) (',' (less T16 (s T22)) (ordered (. T22 X13))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T22", "T23" ], "free": ["X13"], "exprvars": [] } }, "45": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "46": { "goal": [ { "clause": 5, "scope": 5, "term": "(',' (tail (. T22 T23) X13) (',' (less T16 (s T22)) (ordered (. T22 X13))))" }, { "clause": 6, "scope": 5, "term": "(',' (tail (. T22 T23) X13) (',' (less T16 (s T22)) (ordered (. T22 X13))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T22", "T23" ], "free": ["X13"], "exprvars": [] } }, "47": { "goal": [{ "clause": 6, "scope": 5, "term": "(',' (tail (. T22 T23) X13) (',' (less T16 (s T22)) (ordered (. T22 X13))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T22", "T23" ], "free": ["X13"], "exprvars": [] } }, "type": "Nodes", "354": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T68 X116) (less T71 X116))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T68", "T71" ], "free": ["X116"], "exprvars": [] } }, "357": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "359": { "goal": [ { "clause": 9, "scope": 13, "term": "(',' (p T68 X116) (less T71 X116))" }, { "clause": 10, "scope": 13, "term": "(',' (p T68 X116) (less T71 X116))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T68", "T71" ], "free": ["X116"], "exprvars": [] } }, "97": { "goal": [ { "clause": 7, "scope": 6, "term": "(less T16 (s T30))" }, { "clause": 8, "scope": 6, "term": "(less T16 (s T30))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T30" ], "free": [], "exprvars": [] } }, "54": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (less T16 (s T30)) (ordered (. T30 T31)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T30", "T31" ], "free": [], "exprvars": [] } }, "361": { "goal": [{ "clause": 9, "scope": 13, "term": "(',' (p T68 X116) (less T71 X116))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T68", "T71" ], "free": ["X116"], "exprvars": [] } }, "362": { "goal": [{ "clause": 10, "scope": 13, "term": "(',' (p T68 X116) (less T71 X116))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T68", "T71" ], "free": ["X116"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "123": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T44 X78) (',' (p (s T45) X79) (less X78 X79)))" }], "kb": { "nonunifying": [[ "(less T44 (s T45))", "(less (0) X62)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X62", "X78", "X79" ], "exprvars": [] } }, "3": { "goal": [ { "clause": 0, "scope": 1, "term": "(ordered T1)" }, { "clause": 1, "scope": 1, "term": "(ordered T1)" }, { "clause": 2, "scope": 1, "term": "(ordered T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "124": { "goal": [ { "clause": 9, "scope": 8, "term": "(',' (p T44 X78) (',' (p (s T45) X79) (less X78 X79)))" }, { "clause": 10, "scope": 8, "term": "(',' (p T44 X78) (',' (p (s T45) X79) (less X78 X79)))" } ], "kb": { "nonunifying": [[ "(less T44 (s T45))", "(less (0) X62)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X62", "X78", "X79" ], "exprvars": [] } }, "125": { "goal": [{ "clause": 10, "scope": 8, "term": "(',' (p T44 X78) (',' (p (s T45) X79) (less X78 X79)))" }], "kb": { "nonunifying": [[ "(less T44 (s T45))", "(less (0) X62)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T44", "T45" ], "free": [ "X62", "X78", "X79" ], "exprvars": [] } }, "126": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (s T45) X79) (less T48 X79))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T48" ], "free": ["X79"], "exprvars": [] } }, "368": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T71 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": [], "exprvars": [] } }, "127": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "369": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "128": { "goal": [ { "clause": 9, "scope": 9, "term": "(',' (p (s T45) X79) (less T48 X79))" }, { "clause": 10, "scope": 9, "term": "(',' (p (s T45) X79) (less T48 X79))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T48" ], "free": ["X79"], "exprvars": [] } }, "129": { "goal": [{ "clause": 10, "scope": 9, "term": "(',' (p (s T45) X79) (less T48 X79))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T48" ], "free": ["X79"], "exprvars": [] } }, "20": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 1, "scope": 1, "term": "(ordered ([]))" }, { "clause": 2, "scope": 1, "term": "(ordered ([]))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "goal": [ { "clause": 1, "scope": 1, "term": "(ordered T1)" }, { "clause": 2, "scope": 1, "term": "(ordered T1)" } ], "kb": { "nonunifying": [[ "(ordered T1)", "(ordered ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "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": [] } }, "26": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_1)" }, { "clause": 2, "scope": 1, "term": "(ordered (. T3 ([])))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "28": { "goal": [{ "clause": 2, "scope": 1, "term": "(ordered T1)" }], "kb": { "nonunifying": [ [ "(ordered T1)", "(ordered ([]))" ], [ "(ordered T1)", "(ordered (. X7 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": ["X7"], "exprvars": [] } }, "29": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "134": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T48 T52)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T48", "T52" ], "free": [], "exprvars": [] } }, "332": { "goal": [{ "clause": 8, "scope": 10, "term": "(less T48 T52)" }], "kb": { "nonunifying": [[ "(less T48 T52)", "(less (0) X99)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T48", "T52" ], "free": ["X99"], "exprvars": [] } }, "334": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T56 (s X100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T56"], "free": ["X100"], "exprvars": [] } }, "335": { "goal": [{ "clause": 11, "scope": 11, "term": "(eq T56 (s X100))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T56"], "free": ["X100"], "exprvars": [] } }, "338": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "339": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "72": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T16 (s T30))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T30" ], "free": [], "exprvars": [] } }, "73": { "goal": [{ "clause": -1, "scope": -1, "term": "(ordered (. T30 T31))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T30", "T31" ], "free": [], "exprvars": [] } }, "30": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T5 X10) (',' (tail T5 X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less X10 (s X12)) (ordered (. X12 X13)))))))" }], "kb": { "nonunifying": [ [ "(ordered T5)", "(ordered ([]))" ], [ "(ordered T5)", "(ordered (. X7 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X10", "X11", "X12", "X13" ], "exprvars": [] } }, "33": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (head T5 X10) (',' (tail T5 X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less X10 (s X12)) (ordered (. X12 X13)))))))" }, { "clause": 4, "scope": 2, "term": "(',' (head T5 X10) (',' (tail T5 X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less X10 (s X12)) (ordered (. X12 X13)))))))" } ], "kb": { "nonunifying": [ [ "(ordered T5)", "(ordered ([]))" ], [ "(ordered T5)", "(ordered (. X7 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X10", "X11", "X12", "X13" ], "exprvars": [] } }, "35": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (head T5 X10) (',' (tail T5 X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less X10 (s X12)) (ordered (. X12 X13)))))))" }], "kb": { "nonunifying": [ [ "(ordered T5)", "(ordered ([]))" ], [ "(ordered T5)", "(ordered (. X7 ([])))" ] ], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [ "X7", "X10", "X11", "X12", "X13" ], "exprvars": [] } }, "37": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (tail (. T10 T11) X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less T10 (s X12)) (ordered (. X12 X13))))))" }], "kb": { "nonunifying": [[ "(ordered (. T10 T11))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X7", "X11", "X12", "X13" ], "exprvars": [] } }, "38": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [ { "clause": 5, "scope": 3, "term": "(',' (tail (. T10 T11) X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less T10 (s X12)) (ordered (. X12 X13))))))" }, { "clause": 6, "scope": 3, "term": "(',' (tail (. T10 T11) X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less T10 (s X12)) (ordered (. X12 X13))))))" } ], "kb": { "nonunifying": [[ "(ordered (. T10 T11))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X7", "X11", "X12", "X13" ], "exprvars": [] } }, "184": { "goal": [ { "clause": 7, "scope": 10, "term": "(less T48 T52)" }, { "clause": 8, "scope": 10, "term": "(less T48 T52)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T48", "T52" ], "free": [], "exprvars": [] } }, "340": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "102": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_6) (eq (s T36) (s X63)))" }, { "clause": 8, "scope": 6, "term": "(less (0) (s T36))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": ["X63"], "exprvars": [] } }, "103": { "goal": [{ "clause": 8, "scope": 6, "term": "(less T16 (s T30))" }], "kb": { "nonunifying": [[ "(less T16 (s T30))", "(less (0) X62)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T30" ], "free": ["X62"], "exprvars": [] } }, "104": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq (s T36) (s X63))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": ["X63"], "exprvars": [] } }, "225": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_10) (eq T56 (s X100)))" }, { "clause": 8, "scope": 10, "term": "(less (0) T56)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T56"], "free": ["X100"], "exprvars": [] } }, "346": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T67 X115) (',' (p T68 X116) (less X115 X116)))" }], "kb": { "nonunifying": [[ "(less T67 T68)", "(less (0) X99)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T67", "T68" ], "free": [ "X99", "X115", "X116" ], "exprvars": [] } }, "467": { "goal": [{ "clause": -1, "scope": -1, "term": "(less T71 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T71", "T74" ], "free": [], "exprvars": [] } }, "105": { "goal": [{ "clause": 11, "scope": 7, "term": "(eq (s T36) (s X63))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": ["X63"], "exprvars": [] } }, "347": { "goal": [ { "clause": 9, "scope": 12, "term": "(',' (p T67 X115) (',' (p T68 X116) (less X115 X116)))" }, { "clause": 10, "scope": 12, "term": "(',' (p T67 X115) (',' (p T68 X116) (less X115 X116)))" } ], "kb": { "nonunifying": [[ "(less T67 T68)", "(less (0) X99)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T67", "T68" ], "free": [ "X99", "X115", "X116" ], "exprvars": [] } }, "469": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "107": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "349": { "goal": [{ "clause": 10, "scope": 12, "term": "(',' (p T67 X115) (',' (p T68 X116) (less X115 X116)))" }], "kb": { "nonunifying": [[ "(less T67 T68)", "(less (0) X99)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T67", "T68" ], "free": [ "X99", "X115", "X116" ], "exprvars": [] } }, "108": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": 6, "scope": 3, "term": "(',' (tail (. T10 T11) X11) (',' (head X11 X12) (',' (tail X11 X13) (',' (less T10 (s X12)) (ordered (. X12 X13))))))" }], "kb": { "nonunifying": [[ "(ordered (. T10 T11))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T10", "T11" ], "free": [ "X7", "X11", "X12", "X13" ], "exprvars": [] } }, "41": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (head T17 X12) (',' (tail T17 X13) (',' (less T16 (s X12)) (ordered (. X12 X13)))))" }], "kb": { "nonunifying": [[ "(ordered (. T16 T17))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17" ], "free": [ "X7", "X12", "X13" ], "exprvars": [] } }, "42": { "goal": [ { "clause": 3, "scope": 4, "term": "(',' (head T17 X12) (',' (tail T17 X13) (',' (less T16 (s X12)) (ordered (. X12 X13)))))" }, { "clause": 4, "scope": 4, "term": "(',' (head T17 X12) (',' (tail T17 X13) (',' (less T16 (s X12)) (ordered (. X12 X13)))))" } ], "kb": { "nonunifying": [[ "(ordered (. T16 T17))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17" ], "free": [ "X7", "X12", "X13" ], "exprvars": [] } }, "43": { "goal": [{ "clause": 4, "scope": 4, "term": "(',' (head T17 X12) (',' (tail T17 X13) (',' (less T16 (s X12)) (ordered (. X12 X13)))))" }], "kb": { "nonunifying": [[ "(ordered (. T16 T17))", "(ordered (. X7 ([])))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17" ], "free": [ "X7", "X12", "X13" ], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 3, "label": "CASE" }, { "from": 3, "to": 20, "label": "EVAL with clause\nordered([]) :- !_1.\nand substitutionT1 -> []" }, { "from": 3, "to": 21, "label": "EVAL-BACKTRACK" }, { "from": 20, "to": 22, "label": "CUT" }, { "from": 21, "to": 26, "label": "EVAL with clause\nordered(.(X7, [])) :- !_1.\nand substitutionX7 -> T3,\nT1 -> .(T3, [])" }, { "from": 21, "to": 28, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 23, "label": "SUCCESS" }, { "from": 26, "to": 29, "label": "CUT" }, { "from": 28, "to": 31, "label": "ONLY EVAL with clause\nordered(X9) :- ','(head(X9, X10), ','(tail(X9, X11), ','(head(X11, X12), ','(tail(X11, X13), ','(less(X10, s(X12)), ordered(.(X12, X13))))))).\nand substitutionT1 -> T5,\nX9 -> T5" }, { "from": 29, "to": 30, "label": "SUCCESS" }, { "from": 31, "to": 33, "label": "CASE" }, { "from": 33, "to": 35, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (ordered(T5), ordered([]))" }, { "from": 35, "to": 37, "label": "EVAL with clause\nhead(.(X20, X21), X20).\nand substitutionX20 -> T10,\nX21 -> T11,\nT5 -> .(T10, T11),\nX10 -> T10" }, { "from": 35, "to": 38, "label": "EVAL-BACKTRACK" }, { "from": 37, "to": 39, "label": "CASE" }, { "from": 39, "to": 40, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 40, "to": 41, "label": "ONLY EVAL with clause\ntail(.(X32, X33), X33).\nand substitutionT10 -> T16,\nX32 -> T16,\nT11 -> T17,\nX33 -> T17,\nX11 -> T17" }, { "from": 41, "to": 42, "label": "CASE" }, { "from": 42, "to": 43, "label": "BACKTRACK\nfor clause: head([], X2)\nwith clash: (ordered(.(T16, T17)), ordered(.(X7, [])))" }, { "from": 43, "to": 44, "label": "EVAL with clause\nhead(.(X43, X44), X43).\nand substitutionX43 -> T22,\nX44 -> T23,\nT17 -> .(T22, T23),\nX12 -> T22" }, { "from": 43, "to": 45, "label": "EVAL-BACKTRACK" }, { "from": 44, "to": 46, "label": "CASE" }, { "from": 46, "to": 47, "label": "BACKTRACK\nfor clause: tail([], [])because of non-unification" }, { "from": 47, "to": 54, "label": "ONLY EVAL with clause\ntail(.(X53, X54), X54).\nand substitutionT22 -> T30,\nX53 -> T30,\nT23 -> T31,\nX54 -> T31,\nX13 -> T31" }, { "from": 54, "to": 72, "label": "SPLIT 1" }, { "from": 54, "to": 73, "label": "SPLIT 2\nnew knowledge:\nT16 is ground\nT30 is ground" }, { "from": 72, "to": 97, "label": "CASE" }, { "from": 73, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(T30, T31)" }, { "from": 97, "to": 102, "label": "EVAL with clause\nless(0, X62) :- ','(!_6, eq(X62, s(X63))).\nand substitutionT16 -> 0,\nT30 -> T36,\nX62 -> s(T36)" }, { "from": 97, "to": 103, "label": "EVAL-BACKTRACK" }, { "from": 102, "to": 104, "label": "CUT" }, { "from": 103, "to": 123, "label": "ONLY EVAL with clause\nless(X76, X77) :- ','(p(X76, X78), ','(p(X77, X79), less(X78, X79))).\nand substitutionT16 -> T44,\nX76 -> T44,\nT30 -> T45,\nX77 -> s(T45)" }, { "from": 104, "to": 105, "label": "CASE" }, { "from": 105, "to": 107, "label": "ONLY EVAL with clause\neq(X66, X66).\nand substitutionT36 -> T39,\nX66 -> s(T39),\nX63 -> T39" }, { "from": 107, "to": 108, "label": "SUCCESS" }, { "from": 123, "to": 124, "label": "CASE" }, { "from": 124, "to": 125, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (less(T44, s(T45)), less(0, X62))" }, { "from": 125, "to": 126, "label": "EVAL with clause\np(s(X85), X85).\nand substitutionX85 -> T48,\nT44 -> s(T48),\nX78 -> T48" }, { "from": 125, "to": 127, "label": "EVAL-BACKTRACK" }, { "from": 126, "to": 128, "label": "CASE" }, { "from": 128, "to": 129, "label": "BACKTRACK\nfor clause: p(0, 0)because of non-unification" }, { "from": 129, "to": 134, "label": "ONLY EVAL with clause\np(s(X93), X93).\nand substitutionT45 -> T52,\nX93 -> T52,\nX79 -> T52" }, { "from": 134, "to": 184, "label": "CASE" }, { "from": 184, "to": 225, "label": "EVAL with clause\nless(0, X99) :- ','(!_10, eq(X99, s(X100))).\nand substitutionT48 -> 0,\nT52 -> T56,\nX99 -> T56" }, { "from": 184, "to": 332, "label": "EVAL-BACKTRACK" }, { "from": 225, "to": 334, "label": "CUT" }, { "from": 332, "to": 346, "label": "ONLY EVAL with clause\nless(X113, X114) :- ','(p(X113, X115), ','(p(X114, X116), less(X115, X116))).\nand substitutionT48 -> T67,\nX113 -> T67,\nT52 -> T68,\nX114 -> T68" }, { "from": 334, "to": 335, "label": "CASE" }, { "from": 335, "to": 338, "label": "EVAL with clause\neq(X103, X103).\nand substitutionT56 -> s(T62),\nX103 -> s(T62),\nX100 -> T62,\nT61 -> s(T62)" }, { "from": 335, "to": 339, "label": "EVAL-BACKTRACK" }, { "from": 338, "to": 340, "label": "SUCCESS" }, { "from": 346, "to": 347, "label": "CASE" }, { "from": 347, "to": 349, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (less(T67, T68), less(0, X99))" }, { "from": 349, "to": 354, "label": "EVAL with clause\np(s(X122), X122).\nand substitutionX122 -> T71,\nT67 -> s(T71),\nX115 -> T71" }, { "from": 349, "to": 357, "label": "EVAL-BACKTRACK" }, { "from": 354, "to": 359, "label": "CASE" }, { "from": 359, "to": 361, "label": "PARALLEL" }, { "from": 359, "to": 362, "label": "PARALLEL" }, { "from": 361, "to": 368, "label": "EVAL with clause\np(0, 0).\nand substitutionT68 -> 0,\nX116 -> 0" }, { "from": 361, "to": 369, "label": "EVAL-BACKTRACK" }, { "from": 362, "to": 467, "label": "EVAL with clause\np(s(X130), X130).\nand substitutionX130 -> T74,\nT68 -> s(T74),\nX116 -> T74" }, { "from": 362, "to": 469, "label": "EVAL-BACKTRACK" }, { "from": 368, "to": 134, "label": "INSTANCE with matching:\nT48 -> T71\nT52 -> 0" }, { "from": 467, "to": 134, "label": "INSTANCE with matching:\nT48 -> T71\nT52 -> T74" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: lessC(s(X1), 0) :- lessC(X1, 0). lessC(s(X1), s(X2)) :- lessC(X1, X2). orderedA(.(s(X1), .(X2, X3))) :- lessC(X1, X2). orderedA(.(X1, .(X2, X3))) :- ','(lesscB(X1, X2), orderedA(.(X2, X3))). Clauses: orderedcA([]). orderedcA(.(X1, [])). orderedcA(.(X1, .(X2, X3))) :- ','(lesscB(X1, X2), orderedcA(.(X2, X3))). lesscC(0, s(X1)). lesscC(s(X1), 0) :- lesscC(X1, 0). lesscC(s(X1), s(X2)) :- lesscC(X1, X2). lesscB(0, X1). lesscB(s(X1), X2) :- lesscC(X1, X2). Afs: orderedA(x1) = orderedA(x1) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: orderedA_in_1: (b) lessC_in_2: (b,b) lesscB_in_2: (b,b) lesscC_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: ORDEREDA_IN_G(.(s(X1), .(X2, X3))) -> U3_G(X1, X2, X3, lessC_in_gg(X1, X2)) ORDEREDA_IN_G(.(s(X1), .(X2, X3))) -> LESSC_IN_GG(X1, X2) LESSC_IN_GG(s(X1), 0) -> U1_GG(X1, lessC_in_gg(X1, 0)) LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) LESSC_IN_GG(s(X1), s(X2)) -> U2_GG(X1, X2, lessC_in_gg(X1, X2)) LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) ORDEREDA_IN_G(.(X1, .(X2, X3))) -> U4_G(X1, X2, X3, lesscB_in_gg(X1, X2)) U4_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> U5_G(X1, X2, X3, orderedA_in_g(.(X2, X3))) U4_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> ORDEREDA_IN_G(.(X2, X3)) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U11_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(s(X1), 0) -> U9_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U10_gg(X1, X2, lesscC_in_gg(X1, X2)) U10_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U9_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U11_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: ORDEREDA_IN_G(.(s(X1), .(X2, X3))) -> U3_G(X1, X2, X3, lessC_in_gg(X1, X2)) ORDEREDA_IN_G(.(s(X1), .(X2, X3))) -> LESSC_IN_GG(X1, X2) LESSC_IN_GG(s(X1), 0) -> U1_GG(X1, lessC_in_gg(X1, 0)) LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) LESSC_IN_GG(s(X1), s(X2)) -> U2_GG(X1, X2, lessC_in_gg(X1, X2)) LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) ORDEREDA_IN_G(.(X1, .(X2, X3))) -> U4_G(X1, X2, X3, lesscB_in_gg(X1, X2)) U4_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> U5_G(X1, X2, X3, orderedA_in_g(.(X2, X3))) U4_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> ORDEREDA_IN_G(.(X2, X3)) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U11_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(s(X1), 0) -> U9_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U10_gg(X1, X2, lesscC_in_gg(X1, X2)) U10_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U9_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U11_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 3 SCCs with 5 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U11_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(s(X1), 0) -> U9_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U10_gg(X1, X2, lesscC_in_gg(X1, X2)) U10_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U9_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U11_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) 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: *LESSC_IN_GG(s(X1), 0) -> LESSC_IN_GG(X1, 0) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U11_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(s(X1), 0) -> U9_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U10_gg(X1, X2, lesscC_in_gg(X1, X2)) U10_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U9_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U11_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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: *LESSC_IN_GG(s(X1), s(X2)) -> LESSC_IN_GG(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: ORDEREDA_IN_G(.(X1, .(X2, X3))) -> U4_G(X1, X2, X3, lesscB_in_gg(X1, X2)) U4_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> ORDEREDA_IN_G(.(X2, X3)) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U11_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(s(X1), 0) -> U9_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U10_gg(X1, X2, lesscC_in_gg(X1, X2)) U10_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U9_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U11_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: ORDEREDA_IN_G(.(X1, .(X2, X3))) -> U4_G(X1, X2, X3, lesscB_in_gg(X1, X2)) U4_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> ORDEREDA_IN_G(.(X2, X3)) The TRS R consists of the following rules: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscB_in_gg(s(X1), X2) -> U11_gg(X1, X2, lesscC_in_gg(X1, X2)) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(s(X1), 0) -> U9_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U10_gg(X1, X2, lesscC_in_gg(X1, X2)) U10_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U9_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) U11_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) The set Q consists of the following terms: lesscB_in_gg(x0, x1) lesscC_in_gg(x0, x1) U10_gg(x0, x1, x2) U9_gg(x0, x1) U11_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (24) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: lesscB_in_gg(0, X1) -> lesscB_out_gg(0, X1) lesscC_in_gg(0, s(X1)) -> lesscC_out_gg(0, s(X1)) lesscC_in_gg(s(X1), 0) -> U9_gg(X1, lesscC_in_gg(X1, 0)) lesscC_in_gg(s(X1), s(X2)) -> U10_gg(X1, X2, lesscC_in_gg(X1, X2)) U11_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscB_out_gg(s(X1), X2) Used ordering: Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = 2*x_1 + x_2 POL(0) = 2 POL(ORDEREDA_IN_G(x_1)) = 2*x_1 POL(U10_gg(x_1, x_2, x_3)) = 2 + x_1 + x_2 + x_3 POL(U11_gg(x_1, x_2, x_3)) = 2 + 2*x_1 + x_2 + x_3 POL(U4_G(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_2 + 2*x_3 + x_4 POL(U9_gg(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(lesscB_in_gg(x_1, x_2)) = 2*x_1 + 2*x_2 POL(lesscB_out_gg(x_1, x_2)) = x_1 + 2*x_2 POL(lesscC_in_gg(x_1, x_2)) = 2*x_1 + x_2 POL(lesscC_out_gg(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = 1 + 2*x_1 ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: ORDEREDA_IN_G(.(X1, .(X2, X3))) -> U4_G(X1, X2, X3, lesscB_in_gg(X1, X2)) U4_G(X1, X2, X3, lesscB_out_gg(X1, X2)) -> ORDEREDA_IN_G(.(X2, X3)) The TRS R consists of the following rules: lesscB_in_gg(s(X1), X2) -> U11_gg(X1, X2, lesscC_in_gg(X1, X2)) U10_gg(X1, X2, lesscC_out_gg(X1, X2)) -> lesscC_out_gg(s(X1), s(X2)) U9_gg(X1, lesscC_out_gg(X1, 0)) -> lesscC_out_gg(s(X1), 0) The set Q consists of the following terms: lesscB_in_gg(x0, x1) lesscC_in_gg(x0, x1) U10_gg(x0, x1, x2) U9_gg(x0, x1) U11_gg(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (27) TRUE