/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 add(a,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, 9 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: add(X, 0, Y) :- ','(!, eq(X, Y)). add(X, Y, s(Z)) :- ','(p(Y, P), add(X, P, Z)). p(0, 0). p(s(X), X). eq(X, X). Query: add(a,g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 3, "program": { "directives": [], "clauses": [ [ "(add X (0) Y)", "(',' (!) (eq X Y))" ], [ "(add X Y (s Z))", "(',' (p Y P) (add X P Z))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "34": { "goal": [{ "clause": 4, "scope": 2, "term": "(eq T8 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "35": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "36": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [{ "clause": 3, "scope": 3, "term": "(',' (p T17 X14) (add T19 X14 T20))" }], "kb": { "nonunifying": [[ "(add T1 T17 T3)", "(add X3 (0) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [ "X3", "X4", "X14" ], "exprvars": [] } }, "37": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "38": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T17 X14) (add T19 X14 T20))" }], "kb": { "nonunifying": [[ "(add T1 T17 T3)", "(add X3 (0) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [ "X3", "X4", "X14" ], "exprvars": [] } }, "39": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(add T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(add T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(add T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (eq T8 T9))" }, { "clause": 1, "scope": 1, "term": "(add T1 (0) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 1, "scope": 1, "term": "(add T1 T2 T3)" }], "kb": { "nonunifying": [[ "(add T1 T2 T3)", "(add X3 (0) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [ "X3", "X4" ], "exprvars": [] } }, "8": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T8 T9)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "94": { "goal": [{ "clause": -1, "scope": -1, "term": "(add T19 T23 T20)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T23"], "free": [], "exprvars": [] } }, "95": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "42": { "goal": [ { "clause": 2, "scope": 3, "term": "(',' (p T17 X14) (add T19 X14 T20))" }, { "clause": 3, "scope": 3, "term": "(',' (p T17 X14) (add T19 X14 T20))" } ], "kb": { "nonunifying": [[ "(add T1 T17 T3)", "(add X3 (0) X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T17"], "free": [ "X3", "X4", "X14" ], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 4, "label": "CASE" }, { "from": 4, "to": 5, "label": "EVAL with clause\nadd(X3, 0, X4) :- ','(!_1, eq(X3, X4)).\nand substitutionT1 -> T8,\nX3 -> T8,\nT2 -> 0,\nT3 -> T9,\nX4 -> T9,\nT6 -> T8,\nT7 -> T9" }, { "from": 4, "to": 6, "label": "EVAL-BACKTRACK" }, { "from": 5, "to": 8, "label": "CUT" }, { "from": 6, "to": 38, "label": "EVAL with clause\nadd(X11, X12, s(X13)) :- ','(p(X12, X14), add(X11, X14, X13)).\nand substitutionT1 -> T19,\nX11 -> T19,\nT2 -> T17,\nX12 -> T17,\nX13 -> T20,\nT3 -> s(T20),\nT16 -> T19,\nT18 -> T20" }, { "from": 6, "to": 39, "label": "EVAL-BACKTRACK" }, { "from": 8, "to": 34, "label": "CASE" }, { "from": 34, "to": 35, "label": "EVAL with clause\neq(X7, X7).\nand substitutionT8 -> T12,\nX7 -> T12,\nT9 -> T12" }, { "from": 34, "to": 36, "label": "EVAL-BACKTRACK" }, { "from": 35, "to": 37, "label": "SUCCESS" }, { "from": 38, "to": 42, "label": "CASE" }, { "from": 42, "to": 47, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (add(T1, T17, T3), add(X3, 0, X4))" }, { "from": 47, "to": 94, "label": "EVAL with clause\np(s(X17), X17).\nand substitutionX17 -> T23,\nT17 -> s(T23),\nX14 -> T23" }, { "from": 47, "to": 95, "label": "EVAL-BACKTRACK" }, { "from": 94, "to": 3, "label": "INSTANCE with matching:\nT1 -> T19\nT2 -> T23\nT3 -> T20" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: addA(X1, s(X2), s(X3)) :- addA(X1, X2, X3). Clauses: addcA(X1, 0, X1). addcA(X1, s(X2), s(X3)) :- addcA(X1, X2, X3). Afs: addA(x1, x2, x3) = addA(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: addA_in_3: (f,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: ADDA_IN_AGA(X1, s(X2), s(X3)) -> U1_AGA(X1, X2, X3, addA_in_aga(X1, X2, X3)) ADDA_IN_AGA(X1, s(X2), s(X3)) -> ADDA_IN_AGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: addA_in_aga(x1, x2, x3) = addA_in_aga(x2) s(x1) = s(x1) ADDA_IN_AGA(x1, x2, x3) = ADDA_IN_AGA(x2) U1_AGA(x1, x2, x3, x4) = U1_AGA(x2, x4) 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: ADDA_IN_AGA(X1, s(X2), s(X3)) -> U1_AGA(X1, X2, X3, addA_in_aga(X1, X2, X3)) ADDA_IN_AGA(X1, s(X2), s(X3)) -> ADDA_IN_AGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: addA_in_aga(x1, x2, x3) = addA_in_aga(x2) s(x1) = s(x1) ADDA_IN_AGA(x1, x2, x3) = ADDA_IN_AGA(x2) U1_AGA(x1, x2, x3, x4) = U1_AGA(x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: ADDA_IN_AGA(X1, s(X2), s(X3)) -> ADDA_IN_AGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) ADDA_IN_AGA(x1, x2, x3) = ADDA_IN_AGA(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: ADDA_IN_AGA(s(X2)) -> ADDA_IN_AGA(X2) 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: *ADDA_IN_AGA(s(X2)) -> ADDA_IN_AGA(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (10) YES