/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 group3(g,a,a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 80 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 [SOUND, 4 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) PiDPToQDPProof [SOUND, 0 ms] (16) QDP (17) QDPOrderProof [EQUIVALENT, 35 ms] (18) QDP (19) PisEmptyProof [EQUIVALENT, 0 ms] (20) YES ---------------------------------------- (0) Obligation: Clauses: group3(G, G1, G2, G3) :- ','(selectN(2, G, G1), ','(subtract(G, G1, R1), ','(selectN(3, R1, G2), ','(subtract(R1, G2, R2), ','(selectN(4, R2, G3), subtract(R2, G3, [])))))). selectN(0, X1, []) :- !. selectN(N, L, .(X, S)) :- ','(>(N, 0), ','(el(X, L, R), ','(is(N1, -(N, 1)), selectN(N1, R, S)))). el(X, .(X, L), L). el(X, .(X2, L), R) :- el(X, L, R). Query: group3(g,a,a,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(group3 G G1 G2 G3)", "(',' (selectN (2) G G1) (',' (subtract G G1 R1) (',' (selectN (3) R1 G2) (',' (subtract R1 G2 R2) (',' (selectN (4) R2 G3) (subtract R2 G3 ([])))))))" ], [ "(selectN (0) X1 ([]))", "(!)" ], [ "(selectN N L (. X S))", "(',' (> N (0)) (',' (el X L R) (',' (is N1 (- N (1))) (selectN N1 R S))))" ], [ "(el X (. X L) L)", null ], [ "(el X (. X2 L) R)", "(el X L R)" ] ] }, "graph": { "nodes": { "44": { "goal": [{ "clause": -1, "scope": -1, "term": "(el T61 T60 X62)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" } ] }, "ground": ["T60"], "free": ["X62"], "exprvars": [] } }, "45": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (el T25 T22 X28) (',' (is X29 (- (2) (1))) (selectN X29 X28 T26))) (',' (subtract T22 (. T25 T26) X11) (',' (selectN (3) X11 T27) (',' (subtract X11 T27 X12) (',' (selectN (4) X12 T28) (subtract X12 T28 ([])))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }] }, "ground": ["T22"], "free": [ "X11", "X12", "X28", "X29" ], "exprvars": [] } }, "3100": { "goal": [{ "clause": -1, "scope": -1, "term": "(selectN T124 T93 T94)" }], "kb": { "nonunifying": [[ "(selectN T83 T84 T95)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T124", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T83", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [ "T84", "T83", "T93", "T124" ], "free": [ "X71", "X87" ], "exprvars": [ "T83", "T124" ] } }, "type": "Nodes", "892": { "goal": [{ "clause": 2, "scope": 4, "term": "(selectN T66 T33 T34)" }], "kb": { "nonunifying": [[ "(selectN T66 T33 T34)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [ "T33", "T66" ], "free": ["X71"], "exprvars": ["T66"] } }, "894": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": ["T66"] } }, "895": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": ["T66"] } }, "3037": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T83", "T66" ] } }, "3036": { "goal": [{ "clause": -1, "scope": -1, "term": "(el T119 T118 X120)" }], "kb": { "nonunifying": [[ "(selectN T83 (. T117 T118) T34)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T83", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T83", "T117", "T118" ], "free": [ "X71", "X120" ], "exprvars": [ "T83", "T66" ] } }, "911": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T83 (0)) (',' (el T87 T84 X86) (',' (is X87 (- T83 (1))) (selectN X87 X86 T88))))" }], "kb": { "nonunifying": [[ "(selectN T83 T84 T34)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T83", "T84" ], "free": [ "X71", "X86", "X87" ], "exprvars": [ "T83", "T66" ] } }, "914": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": ["T66"] } }, "30": { "goal": [{ "clause": -1, "scope": -1, "term": "(el T25 T22 X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }] }, "ground": ["T22"], "free": ["X28"], "exprvars": [] } }, "31": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (is X29 (- (2) (1))) (selectN X29 T33 T34)) (',' (subtract T22 (. T35 T34) X11) (',' (selectN (3) X11 T36) (',' (subtract X11 T36 X12) (',' (selectN (4) X12 T37) (subtract X12 T37 ([])))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T22", "T35", "T33" ], "free": [ "X11", "X12", "X29" ], "exprvars": [] } }, "10": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (selectN (2) T9 T13) (',' (subtract T9 T13 X11) (',' (selectN (3) X11 T14) (',' (subtract X11 T14 X12) (',' (selectN (4) X12 T15) (subtract X12 T15 ([])))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X11", "X12" ], "exprvars": [] } }, "33": { "goal": [ { "clause": 3, "scope": 3, "term": "(el T25 T22 X28)" }, { "clause": 4, "scope": 3, "term": "(el T25 T22 X28)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }] }, "ground": ["T22"], "free": ["X28"], "exprvars": [] } }, "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (> (2) (0)) (',' (el T25 T22 X28) (',' (is X29 (- (2) (1))) (selectN X29 X28 T26)))) (',' (subtract T22 (. T25 T26) X11) (',' (selectN (3) X11 T27) (',' (subtract X11 T27 X12) (',' (selectN (4) X12 T28) (subtract X12 T28 ([])))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": [ "X11", "X12", "X28", "X29" ], "exprvars": [] } }, "13": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "36": { "goal": [{ "clause": 3, "scope": 3, "term": "(el T25 T22 X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }] }, "ground": ["T22"], "free": ["X28"], "exprvars": [] } }, "37": { "goal": [{ "clause": 4, "scope": 3, "term": "(el T25 T22 X28)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }] }, "ground": ["T22"], "free": ["X28"], "exprvars": [] } }, "39": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [] } }, "3035": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T83", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T83", "T66" ] } }, "3034": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T83", "T66" ] } }, "3033": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T83", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T83", "T66" ] } }, "3099": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3030": { "goal": [{ "clause": 4, "scope": 5, "term": "(el T87 T84 X86)" }], "kb": { "nonunifying": [[ "(selectN T83 T84 T34)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T84", "T83" ], "free": [ "X71", "X86" ], "exprvars": [ "T83", "T66" ] } }, "3109": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(group3 T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "542": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (selectN T66 T33 T34) (',' (subtract T22 (. T35 T34) X11) (',' (selectN (3) X11 T36) (',' (subtract X11 T36 X12) (',' (selectN (4) X12 T37) (subtract X12 T37 ([])))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [ "T35", "T22", "T33", "T66" ], "free": [ "X11", "X12", "X29" ], "exprvars": ["T66"] } }, "2435": { "goal": [], "kb": { "nonunifying": [[ "(selectN T83 T84 T34)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": ">=" } ] }, "ground": [ "T84", "T83" ], "free": [ "X71", "X86", "X87" ], "exprvars": [ "T83", "T66" ] } }, "2457": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X87 (- T83 (1))) (selectN X87 T93 T94))" }], "kb": { "nonunifying": [[ "(selectN T83 T84 T95)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T84", "T83", "T93" ], "free": [ "X71", "X87" ], "exprvars": [] } }, "3029": { "goal": [{ "clause": 3, "scope": 5, "term": "(el T87 T84 X86)" }], "kb": { "nonunifying": [[ "(selectN T83 T84 T34)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T84", "T83" ], "free": [ "X71", "X86" ], "exprvars": [ "T83", "T66" ] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(group3 T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "543": { "goal": [{ "clause": -1, "scope": -1, "term": "(selectN T66 T33 T34)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [ "T33", "T66" ], "free": [], "exprvars": ["T66"] } }, "3028": { "goal": [ { "clause": 3, "scope": 5, "term": "(el T87 T84 X86)" }, { "clause": 4, "scope": 5, "term": "(el T87 T84 X86)" } ], "kb": { "nonunifying": [[ "(selectN T83 T84 T34)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T84", "T83" ], "free": [ "X71", "X86" ], "exprvars": [ "T83", "T66" ] } }, "544": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (subtract T22 (. T35 T68) X11) (',' (selectN (3) X11 T69) (',' (subtract X11 T69 X12) (',' (selectN (4) X12 T70) (subtract X12 T70 ([]))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T22", "T68" ], "free": [ "X11", "X12" ], "exprvars": [] } }, "545": { "goal": [ { "clause": 1, "scope": 4, "term": "(selectN T66 T33 T34)" }, { "clause": 2, "scope": 4, "term": "(selectN T66 T33 T34)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [ "T33", "T66" ], "free": [], "exprvars": ["T66"] } }, "2432": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (el T87 T84 X86) (',' (is X87 (- T83 (1))) (selectN X87 X86 T88)))" }], "kb": { "nonunifying": [[ "(selectN T83 T84 T34)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T84", "T83" ], "free": [ "X71", "X86", "X87" ], "exprvars": [ "T83", "T66" ] } }, "2454": { "goal": [{ "clause": -1, "scope": -1, "term": "(el T87 T84 X86)" }], "kb": { "nonunifying": [[ "(selectN T83 T84 T34)", "(selectN (0) X71 ([]))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T83", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T84", "T83" ], "free": [ "X71", "X86" ], "exprvars": [ "T83", "T66" ] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (selectN (2) T9 T13) (',' (subtract T9 T13 X11) (',' (selectN (3) X11 T14) (',' (subtract X11 T14 X12) (',' (selectN (4) X12 T15) (subtract X12 T15 ([])))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X11", "X12" ], "exprvars": [] } }, "8": { "goal": [ { "clause": 1, "scope": 2, "term": "(',' (selectN (2) T9 T13) (',' (subtract T9 T13 X11) (',' (selectN (3) X11 T14) (',' (subtract X11 T14 X12) (',' (selectN (4) X12 T15) (subtract X12 T15 ([])))))))" }, { "clause": 2, "scope": 2, "term": "(',' (selectN (2) T9 T13) (',' (subtract T9 T13 X11) (',' (selectN (3) X11 T14) (',' (subtract X11 T14 X12) (',' (selectN (4) X12 T15) (subtract X12 T15 ([])))))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [ "X11", "X12" ], "exprvars": [] } }, "889": { "goal": [ { "clause": -1, "scope": -1, "term": "(!_4)" }, { "clause": 2, "scope": 4, "term": "(selectN (0) T74 T34)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T66", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": ["T74"], "free": [], "exprvars": ["T66"] } }, "40": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }] }, "ground": [], "free": [], "exprvars": [] } }, "42": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" }, { "lhs": { "type": "PlainIntegerConstant", "value": "2" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "2" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 7, "label": "ONLY EVAL with clause\ngroup3(X7, X8, X9, X10) :- ','(selectN(2, X7, X8), ','(subtract(X7, X8, X11), ','(selectN(3, X11, X9), ','(subtract(X11, X9, X12), ','(selectN(4, X12, X10), subtract(X12, X10, [])))))).\nand substitutionT1 -> T9,\nX7 -> T9,\nT2 -> T13,\nX8 -> T13,\nT3 -> T14,\nX9 -> T14,\nT4 -> T15,\nX10 -> T15,\nT10 -> T13,\nT11 -> T14,\nT12 -> T15" }, { "from": 7, "to": 8, "label": "CASE" }, { "from": 8, "to": 10, "label": "BACKTRACK\nfor clause: selectN(0, X1, []) :- !because of non-unification" }, { "from": 10, "to": 12, "label": "EVAL with clause\nselectN(X24, X25, .(X26, X27)) :- ','(>(X24, 0), ','(el(X26, X25, X28), ','(is(X29, -(X24, 1)), selectN(X29, X28, X27)))).\nand substitutionX24 -> 2,\nT9 -> T22,\nX25 -> T22,\nX26 -> T25,\nX27 -> T26,\nT13 -> .(T25, T26),\nT23 -> T25,\nT24 -> T26,\nT14 -> T27,\nT15 -> T28" }, { "from": 10, "to": 13, "label": "EVAL-BACKTRACK" }, { "from": 12, "to": 27, "label": "ARITHCOMP SUCCESS" }, { "from": 27, "to": 30, "label": "SPLIT 1" }, { "from": 27, "to": 31, "label": "SPLIT 2\nnew knowledge:\nT35 is ground\nT22 is ground\nT33 is ground\nreplacements:X28 -> T33,\nT26 -> T34,\nT25 -> T35,\nT27 -> T36,\nT28 -> T37" }, { "from": 30, "to": 33, "label": "CASE" }, { "from": 31, "to": 542, "label": "\nX29 -> T66" }, { "from": 33, "to": 36, "label": "PARALLEL" }, { "from": 33, "to": 37, "label": "PARALLEL" }, { "from": 36, "to": 39, "label": "EVAL with clause\nel(X46, .(X46, X47), X47).\nand substitutionT25 -> T50,\nX46 -> T50,\nX47 -> T51,\nT22 -> .(T50, T51),\nX28 -> T51" }, { "from": 36, "to": 40, "label": "EVAL-BACKTRACK" }, { "from": 37, "to": 44, "label": "EVAL with clause\nel(X58, .(X59, X60), X61) :- el(X58, X60, X61).\nand substitutionT25 -> T61,\nX58 -> T61,\nX59 -> T59,\nX60 -> T60,\nT22 -> .(T59, T60),\nX28 -> X62,\nX61 -> X62,\nT58 -> T61" }, { "from": 37, "to": 45, "label": "EVAL-BACKTRACK" }, { "from": 39, "to": 42, "label": "SUCCESS" }, { "from": 44, "to": 30, "label": "INSTANCE with matching:\nT25 -> T61\nT22 -> T60\nX28 -> X62" }, { "from": 542, "to": 543, "label": "SPLIT 1" }, { "from": 542, "to": 544, "label": "SPLIT 2\nnew knowledge:\nT66 is ground\nT33 is ground\nT68 is ground\nreplacements:T34 -> T68,\nT36 -> T69,\nT37 -> T70" }, { "from": 543, "to": 545, "label": "CASE" }, { "from": 544, "to": 3109, "label": "UNDEFINED ERROR" }, { "from": 545, "to": 889, "label": "EVAL with clause\nselectN(0, X71, []) :- !_4.\nand substitutionT66 -> 0,\nT33 -> T74,\nX71 -> T74,\nT34 -> []" }, { "from": 545, "to": 892, "label": "EVAL-BACKTRACK" }, { "from": 889, "to": 894, "label": "CUT" }, { "from": 892, "to": 911, "label": "EVAL with clause\nselectN(X82, X83, .(X84, X85)) :- ','(>(X82, 0), ','(el(X84, X83, X86), ','(is(X87, -(X82, 1)), selectN(X87, X86, X85)))).\nand substitutionT66 -> T83,\nX82 -> T83,\nT33 -> T84,\nX83 -> T84,\nX84 -> T87,\nX85 -> T88,\nT34 -> .(T87, T88),\nT85 -> T87,\nT86 -> T88" }, { "from": 892, "to": 914, "label": "EVAL-BACKTRACK" }, { "from": 894, "to": 895, "label": "SUCCESS" }, { "from": 911, "to": 2432, "label": "ARITHCOMP SUCCESS" }, { "from": 911, "to": 2435, "label": "ARITHCOMP FAIL" }, { "from": 2432, "to": 2454, "label": "SPLIT 1" }, { "from": 2432, "to": 2457, "label": "SPLIT 2\nnew knowledge:\nT87 is ground\nT84 is ground\nT93 is ground\nreplacements:X86 -> T93,\nT88 -> T94,\nT34 -> T95" }, { "from": 2454, "to": 3028, "label": "CASE" }, { "from": 2457, "to": 3099, "label": "IS ERROR" }, { "from": 2457, "to": 3100, "label": "\nX87 -> T124" }, { "from": 3028, "to": 3029, "label": "PARALLEL" }, { "from": 3028, "to": 3030, "label": "PARALLEL" }, { "from": 3029, "to": 3033, "label": "EVAL with clause\nel(X104, .(X104, X105), X105).\nand substitutionT87 -> T108,\nX104 -> T108,\nX105 -> T109,\nT84 -> .(T108, T109),\nX86 -> T109" }, { "from": 3029, "to": 3034, "label": "EVAL-BACKTRACK" }, { "from": 3030, "to": 3036, "label": "EVAL with clause\nel(X116, .(X117, X118), X119) :- el(X116, X118, X119).\nand substitutionT87 -> T119,\nX116 -> T119,\nX117 -> T117,\nX118 -> T118,\nT84 -> .(T117, T118),\nX86 -> X120,\nX119 -> X120,\nT116 -> T119" }, { "from": 3030, "to": 3037, "label": "EVAL-BACKTRACK" }, { "from": 3033, "to": 3035, "label": "SUCCESS" }, { "from": 3036, "to": 30, "label": "INSTANCE with matching:\nT25 -> T119\nT22 -> T118\nX28 -> X120" }, { "from": 3100, "to": 543, "label": "INSTANCE with matching:\nT66 -> T124\nT33 -> T93\nT34 -> T94" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: elA(X1, .(X2, X3), X4) :- elA(X1, X3, X4). selectNB(X1, .(X2, X3), .(X4, X5)) :- elA(X4, X3, X6). selectNB(X1, X2, .(X3, X4)) :- ','(elcC(X3, X2, X5), selectNB(X6, X5, X4)). group3D(X1, .(X2, X3), X4, X5) :- elA(X2, X1, X6). group3D(X1, .(X2, X3), X4, X5) :- ','(elcA(X2, X1, X6), selectNB(X7, X6, X3)). Clauses: elcA(X1, .(X1, X2), X2). elcA(X1, .(X2, X3), X4) :- elcA(X1, X3, X4). selectNcB(0, X1, []). selectNcB(X1, X2, .(X3, X4)) :- ','(elcC(X3, X2, X5), selectNcB(X6, X5, X4)). elcC(X1, .(X1, X2), X2). elcC(X1, .(X2, X3), X4) :- elcA(X1, X3, X4). Afs: group3D(x1, x2, x3, x4) = group3D(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: group3D_in_4: (b,f,f,f) elA_in_3: (f,b,f) elcA_in_3: (f,b,f) selectNB_in_3: (f,b,f) elcC_in_3: (f,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: GROUP3D_IN_GAAA(X1, .(X2, X3), X4, X5) -> U5_GAAA(X1, X2, X3, X4, X5, elA_in_aga(X2, X1, X6)) GROUP3D_IN_GAAA(X1, .(X2, X3), X4, X5) -> ELA_IN_AGA(X2, X1, X6) ELA_IN_AGA(X1, .(X2, X3), X4) -> U1_AGA(X1, X2, X3, X4, elA_in_aga(X1, X3, X4)) ELA_IN_AGA(X1, .(X2, X3), X4) -> ELA_IN_AGA(X1, X3, X4) GROUP3D_IN_GAAA(X1, .(X2, X3), X4, X5) -> U6_GAAA(X1, X2, X3, X4, X5, elcA_in_aga(X2, X1, X6)) U6_GAAA(X1, X2, X3, X4, X5, elcA_out_aga(X2, X1, X6)) -> U7_GAAA(X1, X2, X3, X4, X5, selectNB_in_aga(X7, X6, X3)) U6_GAAA(X1, X2, X3, X4, X5, elcA_out_aga(X2, X1, X6)) -> SELECTNB_IN_AGA(X7, X6, X3) SELECTNB_IN_AGA(X1, .(X2, X3), .(X4, X5)) -> U2_AGA(X1, X2, X3, X4, X5, elA_in_aga(X4, X3, X6)) SELECTNB_IN_AGA(X1, .(X2, X3), .(X4, X5)) -> ELA_IN_AGA(X4, X3, X6) SELECTNB_IN_AGA(X1, X2, .(X3, X4)) -> U3_AGA(X1, X2, X3, X4, elcC_in_aga(X3, X2, X5)) U3_AGA(X1, X2, X3, X4, elcC_out_aga(X3, X2, X5)) -> U4_AGA(X1, X2, X3, X4, selectNB_in_aga(X6, X5, X4)) U3_AGA(X1, X2, X3, X4, elcC_out_aga(X3, X2, X5)) -> SELECTNB_IN_AGA(X6, X5, X4) The TRS R consists of the following rules: elcA_in_aga(X1, .(X1, X2), X2) -> elcA_out_aga(X1, .(X1, X2), X2) elcA_in_aga(X1, .(X2, X3), X4) -> U9_aga(X1, X2, X3, X4, elcA_in_aga(X1, X3, X4)) U9_aga(X1, X2, X3, X4, elcA_out_aga(X1, X3, X4)) -> elcA_out_aga(X1, .(X2, X3), X4) elcC_in_aga(X1, .(X1, X2), X2) -> elcC_out_aga(X1, .(X1, X2), X2) elcC_in_aga(X1, .(X2, X3), X4) -> U12_aga(X1, X2, X3, X4, elcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, elcA_out_aga(X1, X3, X4)) -> elcC_out_aga(X1, .(X2, X3), X4) The argument filtering Pi contains the following mapping: elA_in_aga(x1, x2, x3) = elA_in_aga(x2) .(x1, x2) = .(x1, x2) elcA_in_aga(x1, x2, x3) = elcA_in_aga(x2) elcA_out_aga(x1, x2, x3) = elcA_out_aga(x1, x2, x3) U9_aga(x1, x2, x3, x4, x5) = U9_aga(x2, x3, x5) selectNB_in_aga(x1, x2, x3) = selectNB_in_aga(x2) elcC_in_aga(x1, x2, x3) = elcC_in_aga(x2) elcC_out_aga(x1, x2, x3) = elcC_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) GROUP3D_IN_GAAA(x1, x2, x3, x4) = GROUP3D_IN_GAAA(x1) U5_GAAA(x1, x2, x3, x4, x5, x6) = U5_GAAA(x1, x6) ELA_IN_AGA(x1, x2, x3) = ELA_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x2, x3, x5) U6_GAAA(x1, x2, x3, x4, x5, x6) = U6_GAAA(x1, x6) U7_GAAA(x1, x2, x3, x4, x5, x6) = U7_GAAA(x1, x6) SELECTNB_IN_AGA(x1, x2, x3) = SELECTNB_IN_AGA(x2) U2_AGA(x1, x2, x3, x4, x5, x6) = U2_AGA(x2, x3, x6) U3_AGA(x1, x2, x3, x4, x5) = U3_AGA(x2, x5) U4_AGA(x1, x2, x3, x4, x5) = U4_AGA(x2, x5) 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: GROUP3D_IN_GAAA(X1, .(X2, X3), X4, X5) -> U5_GAAA(X1, X2, X3, X4, X5, elA_in_aga(X2, X1, X6)) GROUP3D_IN_GAAA(X1, .(X2, X3), X4, X5) -> ELA_IN_AGA(X2, X1, X6) ELA_IN_AGA(X1, .(X2, X3), X4) -> U1_AGA(X1, X2, X3, X4, elA_in_aga(X1, X3, X4)) ELA_IN_AGA(X1, .(X2, X3), X4) -> ELA_IN_AGA(X1, X3, X4) GROUP3D_IN_GAAA(X1, .(X2, X3), X4, X5) -> U6_GAAA(X1, X2, X3, X4, X5, elcA_in_aga(X2, X1, X6)) U6_GAAA(X1, X2, X3, X4, X5, elcA_out_aga(X2, X1, X6)) -> U7_GAAA(X1, X2, X3, X4, X5, selectNB_in_aga(X7, X6, X3)) U6_GAAA(X1, X2, X3, X4, X5, elcA_out_aga(X2, X1, X6)) -> SELECTNB_IN_AGA(X7, X6, X3) SELECTNB_IN_AGA(X1, .(X2, X3), .(X4, X5)) -> U2_AGA(X1, X2, X3, X4, X5, elA_in_aga(X4, X3, X6)) SELECTNB_IN_AGA(X1, .(X2, X3), .(X4, X5)) -> ELA_IN_AGA(X4, X3, X6) SELECTNB_IN_AGA(X1, X2, .(X3, X4)) -> U3_AGA(X1, X2, X3, X4, elcC_in_aga(X3, X2, X5)) U3_AGA(X1, X2, X3, X4, elcC_out_aga(X3, X2, X5)) -> U4_AGA(X1, X2, X3, X4, selectNB_in_aga(X6, X5, X4)) U3_AGA(X1, X2, X3, X4, elcC_out_aga(X3, X2, X5)) -> SELECTNB_IN_AGA(X6, X5, X4) The TRS R consists of the following rules: elcA_in_aga(X1, .(X1, X2), X2) -> elcA_out_aga(X1, .(X1, X2), X2) elcA_in_aga(X1, .(X2, X3), X4) -> U9_aga(X1, X2, X3, X4, elcA_in_aga(X1, X3, X4)) U9_aga(X1, X2, X3, X4, elcA_out_aga(X1, X3, X4)) -> elcA_out_aga(X1, .(X2, X3), X4) elcC_in_aga(X1, .(X1, X2), X2) -> elcC_out_aga(X1, .(X1, X2), X2) elcC_in_aga(X1, .(X2, X3), X4) -> U12_aga(X1, X2, X3, X4, elcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, elcA_out_aga(X1, X3, X4)) -> elcC_out_aga(X1, .(X2, X3), X4) The argument filtering Pi contains the following mapping: elA_in_aga(x1, x2, x3) = elA_in_aga(x2) .(x1, x2) = .(x1, x2) elcA_in_aga(x1, x2, x3) = elcA_in_aga(x2) elcA_out_aga(x1, x2, x3) = elcA_out_aga(x1, x2, x3) U9_aga(x1, x2, x3, x4, x5) = U9_aga(x2, x3, x5) selectNB_in_aga(x1, x2, x3) = selectNB_in_aga(x2) elcC_in_aga(x1, x2, x3) = elcC_in_aga(x2) elcC_out_aga(x1, x2, x3) = elcC_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) GROUP3D_IN_GAAA(x1, x2, x3, x4) = GROUP3D_IN_GAAA(x1) U5_GAAA(x1, x2, x3, x4, x5, x6) = U5_GAAA(x1, x6) ELA_IN_AGA(x1, x2, x3) = ELA_IN_AGA(x2) U1_AGA(x1, x2, x3, x4, x5) = U1_AGA(x2, x3, x5) U6_GAAA(x1, x2, x3, x4, x5, x6) = U6_GAAA(x1, x6) U7_GAAA(x1, x2, x3, x4, x5, x6) = U7_GAAA(x1, x6) SELECTNB_IN_AGA(x1, x2, x3) = SELECTNB_IN_AGA(x2) U2_AGA(x1, x2, x3, x4, x5, x6) = U2_AGA(x2, x3, x6) U3_AGA(x1, x2, x3, x4, x5) = U3_AGA(x2, x5) U4_AGA(x1, x2, x3, x4, x5) = U4_AGA(x2, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 9 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: ELA_IN_AGA(X1, .(X2, X3), X4) -> ELA_IN_AGA(X1, X3, X4) The TRS R consists of the following rules: elcA_in_aga(X1, .(X1, X2), X2) -> elcA_out_aga(X1, .(X1, X2), X2) elcA_in_aga(X1, .(X2, X3), X4) -> U9_aga(X1, X2, X3, X4, elcA_in_aga(X1, X3, X4)) U9_aga(X1, X2, X3, X4, elcA_out_aga(X1, X3, X4)) -> elcA_out_aga(X1, .(X2, X3), X4) elcC_in_aga(X1, .(X1, X2), X2) -> elcC_out_aga(X1, .(X1, X2), X2) elcC_in_aga(X1, .(X2, X3), X4) -> U12_aga(X1, X2, X3, X4, elcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, elcA_out_aga(X1, X3, X4)) -> elcC_out_aga(X1, .(X2, X3), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) elcA_in_aga(x1, x2, x3) = elcA_in_aga(x2) elcA_out_aga(x1, x2, x3) = elcA_out_aga(x1, x2, x3) U9_aga(x1, x2, x3, x4, x5) = U9_aga(x2, x3, x5) elcC_in_aga(x1, x2, x3) = elcC_in_aga(x2) elcC_out_aga(x1, x2, x3) = elcC_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) ELA_IN_AGA(x1, x2, x3) = ELA_IN_AGA(x2) 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: ELA_IN_AGA(X1, .(X2, X3), X4) -> ELA_IN_AGA(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) ELA_IN_AGA(x1, x2, x3) = ELA_IN_AGA(x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) 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: ELA_IN_AGA(.(X2, X3)) -> ELA_IN_AGA(X3) 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: *ELA_IN_AGA(.(X2, X3)) -> ELA_IN_AGA(X3) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: SELECTNB_IN_AGA(X1, X2, .(X3, X4)) -> U3_AGA(X1, X2, X3, X4, elcC_in_aga(X3, X2, X5)) U3_AGA(X1, X2, X3, X4, elcC_out_aga(X3, X2, X5)) -> SELECTNB_IN_AGA(X6, X5, X4) The TRS R consists of the following rules: elcA_in_aga(X1, .(X1, X2), X2) -> elcA_out_aga(X1, .(X1, X2), X2) elcA_in_aga(X1, .(X2, X3), X4) -> U9_aga(X1, X2, X3, X4, elcA_in_aga(X1, X3, X4)) U9_aga(X1, X2, X3, X4, elcA_out_aga(X1, X3, X4)) -> elcA_out_aga(X1, .(X2, X3), X4) elcC_in_aga(X1, .(X1, X2), X2) -> elcC_out_aga(X1, .(X1, X2), X2) elcC_in_aga(X1, .(X2, X3), X4) -> U12_aga(X1, X2, X3, X4, elcA_in_aga(X1, X3, X4)) U12_aga(X1, X2, X3, X4, elcA_out_aga(X1, X3, X4)) -> elcC_out_aga(X1, .(X2, X3), X4) The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) elcA_in_aga(x1, x2, x3) = elcA_in_aga(x2) elcA_out_aga(x1, x2, x3) = elcA_out_aga(x1, x2, x3) U9_aga(x1, x2, x3, x4, x5) = U9_aga(x2, x3, x5) elcC_in_aga(x1, x2, x3) = elcC_in_aga(x2) elcC_out_aga(x1, x2, x3) = elcC_out_aga(x1, x2, x3) U12_aga(x1, x2, x3, x4, x5) = U12_aga(x2, x3, x5) SELECTNB_IN_AGA(x1, x2, x3) = SELECTNB_IN_AGA(x2) U3_AGA(x1, x2, x3, x4, x5) = U3_AGA(x2, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: SELECTNB_IN_AGA(X2) -> U3_AGA(X2, elcC_in_aga(X2)) U3_AGA(X2, elcC_out_aga(X3, X2, X5)) -> SELECTNB_IN_AGA(X5) The TRS R consists of the following rules: elcA_in_aga(.(X1, X2)) -> elcA_out_aga(X1, .(X1, X2), X2) elcA_in_aga(.(X2, X3)) -> U9_aga(X2, X3, elcA_in_aga(X3)) U9_aga(X2, X3, elcA_out_aga(X1, X3, X4)) -> elcA_out_aga(X1, .(X2, X3), X4) elcC_in_aga(.(X1, X2)) -> elcC_out_aga(X1, .(X1, X2), X2) elcC_in_aga(.(X2, X3)) -> U12_aga(X2, X3, elcA_in_aga(X3)) U12_aga(X2, X3, elcA_out_aga(X1, X3, X4)) -> elcC_out_aga(X1, .(X2, X3), X4) The set Q consists of the following terms: elcA_in_aga(x0) U9_aga(x0, x1, x2) elcC_in_aga(x0) U12_aga(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (17) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. SELECTNB_IN_AGA(X2) -> U3_AGA(X2, elcC_in_aga(X2)) U3_AGA(X2, elcC_out_aga(X3, X2, X5)) -> SELECTNB_IN_AGA(X5) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( U3_AGA_2(x_1, x_2) ) = max{0, 2x_2 - 2} POL( elcC_in_aga_1(x_1) ) = x_1 + 1 POL( ._2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( elcC_out_aga_3(x_1, ..., x_3) ) = x_3 + 2 POL( U12_aga_3(x_1, ..., x_3) ) = 2x_1 + x_3 + 2 POL( elcA_in_aga_1(x_1) ) = 2x_1 + 1 POL( elcA_out_aga_3(x_1, ..., x_3) ) = x_3 POL( U9_aga_3(x_1, ..., x_3) ) = x_3 + 2 POL( SELECTNB_IN_AGA_1(x_1) ) = 2x_1 + 1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: elcC_in_aga(.(X1, X2)) -> elcC_out_aga(X1, .(X1, X2), X2) elcC_in_aga(.(X2, X3)) -> U12_aga(X2, X3, elcA_in_aga(X3)) elcA_in_aga(.(X1, X2)) -> elcA_out_aga(X1, .(X1, X2), X2) elcA_in_aga(.(X2, X3)) -> U9_aga(X2, X3, elcA_in_aga(X3)) U12_aga(X2, X3, elcA_out_aga(X1, X3, X4)) -> elcC_out_aga(X1, .(X2, X3), X4) U9_aga(X2, X3, elcA_out_aga(X1, X3, X4)) -> elcA_out_aga(X1, .(X2, X3), X4) ---------------------------------------- (18) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: elcA_in_aga(.(X1, X2)) -> elcA_out_aga(X1, .(X1, X2), X2) elcA_in_aga(.(X2, X3)) -> U9_aga(X2, X3, elcA_in_aga(X3)) U9_aga(X2, X3, elcA_out_aga(X1, X3, X4)) -> elcA_out_aga(X1, .(X2, X3), X4) elcC_in_aga(.(X1, X2)) -> elcC_out_aga(X1, .(X1, X2), X2) elcC_in_aga(.(X2, X3)) -> U12_aga(X2, X3, elcA_in_aga(X3)) U12_aga(X2, X3, elcA_out_aga(X1, X3, X4)) -> elcC_out_aga(X1, .(X2, X3), X4) The set Q consists of the following terms: elcA_in_aga(x0) U9_aga(x0, x1, x2) elcC_in_aga(x0) U12_aga(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (20) YES