/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 select(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [SOUND, 0 ms] (8) QDP (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] (10) YES ---------------------------------------- (0) Obligation: Clauses: select(X, .(X, Xs), Xs). select(X, .(Y, Xs), .(Y, Zs)) :- select(X, Xs, Zs). Query: select(g,g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(select X (. X Xs) Xs)", null ], [ "(select X (. Y Xs) (. Y Zs))", "(select X Xs Zs)" ] ] }, "graph": { "nodes": { "89": { "goal": [ { "clause": 0, "scope": 1, "term": "(select T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(select T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "type": "Nodes", "110": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "111": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T69 T71 T73)" }], "kb": { "nonunifying": [[ "(select T69 (. T47 (. T70 T71)) T3)", "(select X3 (. X3 X4) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T47", "T69", "T70", "T71" ], "free": [ "X3", "X4" ], "exprvars": [] } }, "112": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "90": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(select T6 (. T6 T7) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "91": { "goal": [{ "clause": 1, "scope": 1, "term": "(select T1 T2 T3)" }], "kb": { "nonunifying": [[ "(select T1 T2 T3)", "(select X3 (. X3 X4) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [ "X3", "X4" ], "exprvars": [] } }, "92": { "goal": [{ "clause": 1, "scope": 1, "term": "(select T6 (. T6 T7) T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "93": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T11 T12 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T11", "T12" ], "free": [], "exprvars": [] } }, "94": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "95": { "goal": [ { "clause": 0, "scope": 2, "term": "(select T11 T12 T14)" }, { "clause": 1, "scope": 2, "term": "(select T11 T12 T14)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T11", "T12" ], "free": [], "exprvars": [] } }, "96": { "goal": [{ "clause": 0, "scope": 2, "term": "(select T11 T12 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T11", "T12" ], "free": [], "exprvars": [] } }, "97": { "goal": [{ "clause": 1, "scope": 2, "term": "(select T11 T12 T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T11", "T12" ], "free": [], "exprvars": [] } }, "98": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "99": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "100": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "101": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T33 T35 T37)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T33", "T35" ], "free": [], "exprvars": [] } }, "102": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "103": { "goal": [{ "clause": -1, "scope": -1, "term": "(select T46 T48 T50)" }], "kb": { "nonunifying": [[ "(select T46 (. T47 T48) T3)", "(select X3 (. X3 X4) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T46", "T47", "T48" ], "free": [ "X3", "X4" ], "exprvars": [] } }, "104": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "105": { "goal": [ { "clause": 0, "scope": 3, "term": "(select T46 T48 T50)" }, { "clause": 1, "scope": 3, "term": "(select T46 T48 T50)" } ], "kb": { "nonunifying": [[ "(select T46 (. T47 T48) T3)", "(select X3 (. X3 X4) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T46", "T47", "T48" ], "free": [ "X3", "X4" ], "exprvars": [] } }, "106": { "goal": [{ "clause": 0, "scope": 3, "term": "(select T46 T48 T50)" }], "kb": { "nonunifying": [[ "(select T46 (. T47 T48) T3)", "(select X3 (. X3 X4) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T46", "T47", "T48" ], "free": [ "X3", "X4" ], "exprvars": [] } }, "107": { "goal": [{ "clause": 1, "scope": 3, "term": "(select T46 T48 T50)" }], "kb": { "nonunifying": [[ "(select T46 (. T47 T48) T3)", "(select X3 (. X3 X4) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T46", "T47", "T48" ], "free": [ "X3", "X4" ], "exprvars": [] } }, "108": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "109": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 89, "label": "CASE" }, { "from": 89, "to": 90, "label": "EVAL with clause\nselect(X3, .(X3, X4), X4).\nand substitutionT1 -> T6,\nX3 -> T6,\nX4 -> T7,\nT2 -> .(T6, T7),\nT3 -> T7" }, { "from": 89, "to": 91, "label": "EVAL-BACKTRACK" }, { "from": 90, "to": 92, "label": "SUCCESS" }, { "from": 91, "to": 103, "label": "EVAL with clause\nselect(X43, .(X44, X45), .(X44, X46)) :- select(X43, X45, X46).\nand substitutionT1 -> T46,\nX43 -> T46,\nX44 -> T47,\nX45 -> T48,\nT2 -> .(T47, T48),\nX46 -> T50,\nT3 -> .(T47, T50),\nT49 -> T50" }, { "from": 91, "to": 104, "label": "EVAL-BACKTRACK" }, { "from": 92, "to": 93, "label": "EVAL with clause\nselect(X9, .(X10, X11), .(X10, X12)) :- select(X9, X11, X12).\nand substitutionT6 -> T11,\nX9 -> T11,\nX10 -> T11,\nT7 -> T12,\nX11 -> T12,\nX12 -> T14,\nT3 -> .(T11, T14),\nT13 -> T14" }, { "from": 92, "to": 94, "label": "EVAL-BACKTRACK" }, { "from": 93, "to": 95, "label": "CASE" }, { "from": 95, "to": 96, "label": "PARALLEL" }, { "from": 95, "to": 97, "label": "PARALLEL" }, { "from": 96, "to": 98, "label": "EVAL with clause\nselect(X21, .(X21, X22), X22).\nand substitutionT11 -> T23,\nX21 -> T23,\nX22 -> T24,\nT12 -> .(T23, T24),\nT14 -> T24" }, { "from": 96, "to": 99, "label": "EVAL-BACKTRACK" }, { "from": 97, "to": 101, "label": "EVAL with clause\nselect(X31, .(X32, X33), .(X32, X34)) :- select(X31, X33, X34).\nand substitutionT11 -> T33,\nX31 -> T33,\nX32 -> T34,\nX33 -> T35,\nT12 -> .(T34, T35),\nX34 -> T37,\nT14 -> .(T34, T37),\nT36 -> T37" }, { "from": 97, "to": 102, "label": "EVAL-BACKTRACK" }, { "from": 98, "to": 100, "label": "SUCCESS" }, { "from": 101, "to": 1, "label": "INSTANCE with matching:\nT1 -> T33\nT2 -> T35\nT3 -> T37" }, { "from": 103, "to": 105, "label": "CASE" }, { "from": 105, "to": 106, "label": "PARALLEL" }, { "from": 105, "to": 107, "label": "PARALLEL" }, { "from": 106, "to": 108, "label": "EVAL with clause\nselect(X55, .(X55, X56), X56).\nand substitutionT46 -> T59,\nX55 -> T59,\nX56 -> T60,\nT48 -> .(T59, T60),\nT50 -> T60" }, { "from": 106, "to": 109, "label": "EVAL-BACKTRACK" }, { "from": 107, "to": 111, "label": "EVAL with clause\nselect(X65, .(X66, X67), .(X66, X68)) :- select(X65, X67, X68).\nand substitutionT46 -> T69,\nX65 -> T69,\nX66 -> T70,\nX67 -> T71,\nT48 -> .(T70, T71),\nX68 -> T73,\nT50 -> .(T70, T73),\nT72 -> T73" }, { "from": 107, "to": 112, "label": "EVAL-BACKTRACK" }, { "from": 108, "to": 110, "label": "SUCCESS" }, { "from": 111, "to": 1, "label": "INSTANCE with matching:\nT1 -> T69\nT2 -> T71\nT3 -> T73" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: selectA(X1, .(X1, .(X2, X3)), .(X1, .(X2, X4))) :- selectA(X1, X3, X4). selectA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) :- selectA(X1, X4, X5). Clauses: selectcA(X1, .(X1, X2), X2). selectcA(X1, .(X1, .(X1, X2)), .(X1, X2)). selectcA(X1, .(X1, .(X2, X3)), .(X1, .(X2, X4))) :- selectcA(X1, X3, X4). selectcA(X1, .(X2, .(X1, X3)), .(X2, X3)). selectcA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) :- selectcA(X1, X4, X5). Afs: selectA(x1, x2, x3) = selectA(x1, x2) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: selectA_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: SELECTA_IN_GGA(X1, .(X1, .(X2, X3)), .(X1, .(X2, X4))) -> U1_GGA(X1, X2, X3, X4, selectA_in_gga(X1, X3, X4)) SELECTA_IN_GGA(X1, .(X1, .(X2, X3)), .(X1, .(X2, X4))) -> SELECTA_IN_GGA(X1, X3, X4) SELECTA_IN_GGA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> U2_GGA(X1, X2, X3, X4, X5, selectA_in_gga(X1, X4, X5)) SELECTA_IN_GGA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> SELECTA_IN_GGA(X1, X4, X5) R is empty. The argument filtering Pi contains the following mapping: selectA_in_gga(x1, x2, x3) = selectA_in_gga(x1, x2) .(x1, x2) = .(x1, x2) SELECTA_IN_GGA(x1, x2, x3) = SELECTA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x1, x2, x3, x4, x6) 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: SELECTA_IN_GGA(X1, .(X1, .(X2, X3)), .(X1, .(X2, X4))) -> U1_GGA(X1, X2, X3, X4, selectA_in_gga(X1, X3, X4)) SELECTA_IN_GGA(X1, .(X1, .(X2, X3)), .(X1, .(X2, X4))) -> SELECTA_IN_GGA(X1, X3, X4) SELECTA_IN_GGA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> U2_GGA(X1, X2, X3, X4, X5, selectA_in_gga(X1, X4, X5)) SELECTA_IN_GGA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> SELECTA_IN_GGA(X1, X4, X5) R is empty. The argument filtering Pi contains the following mapping: selectA_in_gga(x1, x2, x3) = selectA_in_gga(x1, x2) .(x1, x2) = .(x1, x2) SELECTA_IN_GGA(x1, x2, x3) = SELECTA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U2_GGA(x1, x2, x3, x4, x5, x6) = U2_GGA(x1, x2, x3, x4, x6) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 2 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: SELECTA_IN_GGA(X1, .(X2, .(X3, X4)), .(X2, .(X3, X5))) -> SELECTA_IN_GGA(X1, X4, X5) SELECTA_IN_GGA(X1, .(X1, .(X2, X3)), .(X1, .(X2, X4))) -> SELECTA_IN_GGA(X1, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) SELECTA_IN_GGA(x1, x2, x3) = SELECTA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: SELECTA_IN_GGA(X1, .(X2, .(X3, X4))) -> SELECTA_IN_GGA(X1, X4) SELECTA_IN_GGA(X1, .(X1, .(X2, X3))) -> SELECTA_IN_GGA(X1, X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (9) 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: *SELECTA_IN_GGA(X1, .(X2, .(X3, X4))) -> SELECTA_IN_GGA(X1, X4) The graph contains the following edges 1 >= 1, 2 > 2 *SELECTA_IN_GGA(X1, .(X1, .(X2, X3))) -> SELECTA_IN_GGA(X1, X3) The graph contains the following edges 1 >= 1, 2 > 1, 2 > 2 ---------------------------------------- (10) YES