/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern f(g,a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 3 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [SOUND, 2 ms] (8) QDP (9) MRRProof [EQUIVALENT, 17 ms] (10) QDP (11) DependencyGraphProof [EQUIVALENT, 0 ms] (12) TRUE ---------------------------------------- (0) Obligation: Clauses: f(0, Y, Z) :- ','(!, eq(Z, 0)). f(X, Y, Z) :- ','(p(X, P), ','(f(P, Y, U), f(U, Y, Z))). p(0, 0). p(s(X), X). eq(X, X). Query: f(g,a,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(f (0) Y Z)", "(',' (!) (eq Z (0)))" ], [ "(f X Y Z)", "(',' (p X P) (',' (f P Y U) (f U Y Z)))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "22": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "44": { "goal": [{ "clause": -1, "scope": -1, "term": "(f T24 T25 T26)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T24"], "free": [], "exprvars": [] } }, "23": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (eq T8 (0)))" }, { "clause": 1, "scope": 1, "term": "(f (0) T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "24": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T15 X14) (',' (f X14 T18 X15) (f X15 T18 T19)))" }], "kb": { "nonunifying": [[ "(f T15 T2 T3)", "(f (0) X3 X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X3", "X4", "X14", "X15" ], "exprvars": [] } }, "25": { "goal": [ { "clause": 2, "scope": 3, "term": "(',' (p T15 X14) (',' (f X14 T18 X15) (f X15 T18 T19)))" }, { "clause": 3, "scope": 3, "term": "(',' (p T15 X14) (',' (f X14 T18 X15) (f X15 T18 T19)))" } ], "kb": { "nonunifying": [[ "(f T15 T2 T3)", "(f (0) X3 X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X3", "X4", "X14", "X15" ], "exprvars": [] } }, "15": { "goal": [{ "clause": 1, "scope": 1, "term": "(f T1 T2 T3)" }], "kb": { "nonunifying": [[ "(f T1 T2 T3)", "(f (0) X3 X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X3", "X4" ], "exprvars": [] } }, "16": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T8 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 4, "scope": 2, "term": "(eq T8 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(f T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(f T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(f T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": 3, "scope": 3, "term": "(',' (p T15 X14) (',' (f X14 T18 X15) (f X15 T18 T19)))" }], "kb": { "nonunifying": [[ "(f T15 T2 T3)", "(f (0) X3 X4)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T15"], "free": [ "X3", "X4", "X14", "X15" ], "exprvars": [] } }, "41": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (f T22 T18 X15) (f X15 T18 T19))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X15"], "exprvars": [] } }, "42": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "43": { "goal": [{ "clause": -1, "scope": -1, "term": "(f T22 T18 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X15"], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 13, "label": "EVAL with clause\nf(0, X3, X4) :- ','(!_1, eq(X4, 0)).\nand substitutionT1 -> 0,\nT2 -> T6,\nX3 -> T6,\nT3 -> T8,\nX4 -> T8,\nT7 -> T8" }, { "from": 6, "to": 15, "label": "EVAL-BACKTRACK" }, { "from": 13, "to": 16, "label": "CUT" }, { "from": 15, "to": 24, "label": "ONLY EVAL with clause\nf(X11, X12, X13) :- ','(p(X11, X14), ','(f(X14, X12, X15), f(X15, X12, X13))).\nand substitutionT1 -> T15,\nX11 -> T15,\nT2 -> T18,\nX12 -> T18,\nT3 -> T19,\nX13 -> T19,\nT16 -> T18,\nT17 -> T19" }, { "from": 16, "to": 17, "label": "CASE" }, { "from": 17, "to": 21, "label": "EVAL with clause\neq(X7, X7).\nand substitutionT8 -> 0,\nX7 -> 0,\nT11 -> 0" }, { "from": 17, "to": 22, "label": "EVAL-BACKTRACK" }, { "from": 21, "to": 23, "label": "SUCCESS" }, { "from": 24, "to": 25, "label": "CASE" }, { "from": 25, "to": 40, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (f(T15, T2, T3), f(0, X3, X4))" }, { "from": 40, "to": 41, "label": "EVAL with clause\np(s(X18), X18).\nand substitutionX18 -> T22,\nT15 -> s(T22),\nX14 -> T22" }, { "from": 40, "to": 42, "label": "EVAL-BACKTRACK" }, { "from": 41, "to": 43, "label": "SPLIT 1" }, { "from": 41, "to": 44, "label": "SPLIT 2\nnew knowledge:\nT22 is ground\nT24 is ground\nreplacements:X15 -> T24,\nT18 -> T25,\nT19 -> T26" }, { "from": 43, "to": 2, "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T18\nT3 -> X15" }, { "from": 44, "to": 2, "label": "INSTANCE with matching:\nT1 -> T24\nT2 -> T25\nT3 -> T26" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: fA(s(X1), X2, X3) :- fA(X1, X2, X4). fA(s(X1), X2, X3) :- ','(fcA(X1, X2, X4), fA(X4, X2, X3)). Clauses: fcA(0, X1, 0). fcA(s(X1), X2, X3) :- ','(fcA(X1, X2, X4), fcA(X4, X2, X3)). Afs: fA(x1, x2, x3) = fA(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: fA_in_3: (b,f,f) fcA_in_3: (b,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: FA_IN_GAA(s(X1), X2, X3) -> U1_GAA(X1, X2, X3, fA_in_gaa(X1, X2, X4)) FA_IN_GAA(s(X1), X2, X3) -> FA_IN_GAA(X1, X2, X4) FA_IN_GAA(s(X1), X2, X3) -> U2_GAA(X1, X2, X3, fcA_in_gaa(X1, X2, X4)) U2_GAA(X1, X2, X3, fcA_out_gaa(X1, X2, X4)) -> U3_GAA(X1, X2, X3, fA_in_gaa(X4, X2, X3)) U2_GAA(X1, X2, X3, fcA_out_gaa(X1, X2, X4)) -> FA_IN_GAA(X4, X2, X3) The TRS R consists of the following rules: fcA_in_gaa(0, X1, 0) -> fcA_out_gaa(0, X1, 0) fcA_in_gaa(s(X1), X2, X3) -> U5_gaa(X1, X2, X3, fcA_in_gaa(X1, X2, X4)) U5_gaa(X1, X2, X3, fcA_out_gaa(X1, X2, X4)) -> U6_gaa(X1, X2, X3, X4, fcA_in_gaa(X4, X2, X3)) U6_gaa(X1, X2, X3, X4, fcA_out_gaa(X4, X2, X3)) -> fcA_out_gaa(s(X1), X2, X3) The argument filtering Pi contains the following mapping: fA_in_gaa(x1, x2, x3) = fA_in_gaa(x1) s(x1) = s(x1) fcA_in_gaa(x1, x2, x3) = fcA_in_gaa(x1) 0 = 0 fcA_out_gaa(x1, x2, x3) = fcA_out_gaa(x1, x3) U5_gaa(x1, x2, x3, x4) = U5_gaa(x1, x4) U6_gaa(x1, x2, x3, x4, x5) = U6_gaa(x1, x5) FA_IN_GAA(x1, x2, x3) = FA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4) = U1_GAA(x1, x4) U2_GAA(x1, x2, x3, x4) = U2_GAA(x1, x4) U3_GAA(x1, x2, x3, x4) = U3_GAA(x1, 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: FA_IN_GAA(s(X1), X2, X3) -> U1_GAA(X1, X2, X3, fA_in_gaa(X1, X2, X4)) FA_IN_GAA(s(X1), X2, X3) -> FA_IN_GAA(X1, X2, X4) FA_IN_GAA(s(X1), X2, X3) -> U2_GAA(X1, X2, X3, fcA_in_gaa(X1, X2, X4)) U2_GAA(X1, X2, X3, fcA_out_gaa(X1, X2, X4)) -> U3_GAA(X1, X2, X3, fA_in_gaa(X4, X2, X3)) U2_GAA(X1, X2, X3, fcA_out_gaa(X1, X2, X4)) -> FA_IN_GAA(X4, X2, X3) The TRS R consists of the following rules: fcA_in_gaa(0, X1, 0) -> fcA_out_gaa(0, X1, 0) fcA_in_gaa(s(X1), X2, X3) -> U5_gaa(X1, X2, X3, fcA_in_gaa(X1, X2, X4)) U5_gaa(X1, X2, X3, fcA_out_gaa(X1, X2, X4)) -> U6_gaa(X1, X2, X3, X4, fcA_in_gaa(X4, X2, X3)) U6_gaa(X1, X2, X3, X4, fcA_out_gaa(X4, X2, X3)) -> fcA_out_gaa(s(X1), X2, X3) The argument filtering Pi contains the following mapping: fA_in_gaa(x1, x2, x3) = fA_in_gaa(x1) s(x1) = s(x1) fcA_in_gaa(x1, x2, x3) = fcA_in_gaa(x1) 0 = 0 fcA_out_gaa(x1, x2, x3) = fcA_out_gaa(x1, x3) U5_gaa(x1, x2, x3, x4) = U5_gaa(x1, x4) U6_gaa(x1, x2, x3, x4, x5) = U6_gaa(x1, x5) FA_IN_GAA(x1, x2, x3) = FA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4) = U1_GAA(x1, x4) U2_GAA(x1, x2, x3, x4) = U2_GAA(x1, x4) U3_GAA(x1, x2, x3, x4) = U3_GAA(x1, x4) 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: FA_IN_GAA(s(X1), X2, X3) -> U2_GAA(X1, X2, X3, fcA_in_gaa(X1, X2, X4)) U2_GAA(X1, X2, X3, fcA_out_gaa(X1, X2, X4)) -> FA_IN_GAA(X4, X2, X3) FA_IN_GAA(s(X1), X2, X3) -> FA_IN_GAA(X1, X2, X4) The TRS R consists of the following rules: fcA_in_gaa(0, X1, 0) -> fcA_out_gaa(0, X1, 0) fcA_in_gaa(s(X1), X2, X3) -> U5_gaa(X1, X2, X3, fcA_in_gaa(X1, X2, X4)) U5_gaa(X1, X2, X3, fcA_out_gaa(X1, X2, X4)) -> U6_gaa(X1, X2, X3, X4, fcA_in_gaa(X4, X2, X3)) U6_gaa(X1, X2, X3, X4, fcA_out_gaa(X4, X2, X3)) -> fcA_out_gaa(s(X1), X2, X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) fcA_in_gaa(x1, x2, x3) = fcA_in_gaa(x1) 0 = 0 fcA_out_gaa(x1, x2, x3) = fcA_out_gaa(x1, x3) U5_gaa(x1, x2, x3, x4) = U5_gaa(x1, x4) U6_gaa(x1, x2, x3, x4, x5) = U6_gaa(x1, x5) FA_IN_GAA(x1, x2, x3) = FA_IN_GAA(x1) U2_GAA(x1, x2, x3, x4) = U2_GAA(x1, x4) 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: FA_IN_GAA(s(X1)) -> U2_GAA(X1, fcA_in_gaa(X1)) U2_GAA(X1, fcA_out_gaa(X1, X4)) -> FA_IN_GAA(X4) FA_IN_GAA(s(X1)) -> FA_IN_GAA(X1) The TRS R consists of the following rules: fcA_in_gaa(0) -> fcA_out_gaa(0, 0) fcA_in_gaa(s(X1)) -> U5_gaa(X1, fcA_in_gaa(X1)) U5_gaa(X1, fcA_out_gaa(X1, X4)) -> U6_gaa(X1, fcA_in_gaa(X4)) U6_gaa(X1, fcA_out_gaa(X4, X3)) -> fcA_out_gaa(s(X1), X3) The set Q consists of the following terms: fcA_in_gaa(x0) U5_gaa(x0, x1) U6_gaa(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (9) 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 dependency pairs: FA_IN_GAA(s(X1)) -> U2_GAA(X1, fcA_in_gaa(X1)) FA_IN_GAA(s(X1)) -> FA_IN_GAA(X1) Strictly oriented rules of the TRS R: fcA_in_gaa(0) -> fcA_out_gaa(0, 0) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(FA_IN_GAA(x_1)) = 2*x_1 POL(U2_GAA(x_1, x_2)) = x_1 + x_2 POL(U5_gaa(x_1, x_2)) = 2 + x_1 + x_2 POL(U6_gaa(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(fcA_in_gaa(x_1)) = 1 + 2*x_1 POL(fcA_out_gaa(x_1, x_2)) = x_1 + 2*x_2 POL(s(x_1)) = 1 + 2*x_1 ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: U2_GAA(X1, fcA_out_gaa(X1, X4)) -> FA_IN_GAA(X4) The TRS R consists of the following rules: fcA_in_gaa(s(X1)) -> U5_gaa(X1, fcA_in_gaa(X1)) U5_gaa(X1, fcA_out_gaa(X1, X4)) -> U6_gaa(X1, fcA_in_gaa(X4)) U6_gaa(X1, fcA_out_gaa(X4, X3)) -> fcA_out_gaa(s(X1), X3) The set Q consists of the following terms: fcA_in_gaa(x0) U5_gaa(x0, x1) U6_gaa(x0, x1) We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (12) TRUE