/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 app3_b(g,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) UsableRulesProof [EQUIVALENT, 0 ms] (8) PiDP (9) PiDPToQDPProof [SOUND, 0 ms] (10) QDP (11) QDPSizeChangeProof [EQUIVALENT, 0 ms] (12) YES ---------------------------------------- (0) Obligation: Clauses: app3_a(Xs, Ys, Zs, Us) :- ','(app(Xs, Ys, Vs), app(Vs, Zs, Us)). app3_b(Xs, Ys, Zs, Us) :- ','(app(Ys, Zs, Vs), app(Xs, Vs, Us)). app([], Ys, Ys). app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). Query: app3_b(g,g,g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(app3_a Xs Ys Zs Us)", "(',' (app Xs Ys Vs) (app Vs Zs Us))" ], [ "(app3_b Xs Ys Zs Us)", "(',' (app Ys Zs Vs) (app Xs Vs Us))" ], [ "(app ([]) Ys Ys)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "99": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "24": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T9 T18 T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T18" ], "free": [], "exprvars": [] } }, "25": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "26": { "goal": [ { "clause": 2, "scope": 3, "term": "(app T9 T18 T13)" }, { "clause": 3, "scope": 3, "term": "(app T9 T18 T13)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T18" ], "free": [], "exprvars": [] } }, "16": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (app T10 T11 X9) (app T9 X9 T13))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10", "T11" ], "free": ["X9"], "exprvars": [] } }, "27": { "goal": [{ "clause": 2, "scope": 3, "term": "(app T9 T18 T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T18" ], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (app T10 T11 X9) (app T9 X9 T13))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10", "T11" ], "free": ["X9"], "exprvars": [] } }, "28": { "goal": [{ "clause": 3, "scope": 3, "term": "(app T9 T18 T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T18" ], "free": [], "exprvars": [] } }, "29": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "151": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T48 T49 X50) (app T9 (. T47 X50) T13))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T47", "T48", "T49" ], "free": ["X50"], "exprvars": [] } }, "152": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "153": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T48 T49 X50)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T48", "T49" ], "free": ["X50"], "exprvars": [] } }, "154": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T9 (. T47 T52) T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T47", "T52" ], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(app3_b T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": 1, "scope": 1, "term": "(app3_b T1 T2 T3 T4)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (app T10 T11 X9) (app T9 X9 T13))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10", "T11" ], "free": ["X9"], "exprvars": [] } }, "92": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T35 T36 T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T35", "T36" ], "free": [], "exprvars": [] } }, "30": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (app T10 T11 X9) (app T9 X9 T13))" }, { "clause": 3, "scope": 2, "term": "(',' (app T10 T11 X9) (app T9 X9 T13))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10", "T11" ], "free": ["X9"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 9, "label": "ONLY EVAL with clause\napp3_b(X5, X6, X7, X8) :- ','(app(X6, X7, X9), app(X5, X9, X8)).\nand substitutionT1 -> T9,\nX5 -> T9,\nT2 -> T10,\nX6 -> T10,\nT3 -> T11,\nX7 -> T11,\nT4 -> T13,\nX8 -> T13,\nT12 -> T13" }, { "from": 9, "to": 10, "label": "CASE" }, { "from": 10, "to": 16, "label": "PARALLEL" }, { "from": 10, "to": 17, "label": "PARALLEL" }, { "from": 16, "to": 24, "label": "EVAL with clause\napp([], X14, X14).\nand substitutionT10 -> [],\nT11 -> T18,\nX14 -> T18,\nX9 -> T18" }, { "from": 16, "to": 25, "label": "EVAL-BACKTRACK" }, { "from": 17, "to": 151, "label": "EVAL with clause\napp(.(X46, X47), X48, .(X46, X49)) :- app(X47, X48, X49).\nand substitutionX46 -> T47,\nX47 -> T48,\nT10 -> .(T47, T48),\nT11 -> T49,\nX48 -> T49,\nX49 -> X50,\nX9 -> .(T47, X50)" }, { "from": 17, "to": 152, "label": "EVAL-BACKTRACK" }, { "from": 24, "to": 26, "label": "CASE" }, { "from": 26, "to": 27, "label": "PARALLEL" }, { "from": 26, "to": 28, "label": "PARALLEL" }, { "from": 27, "to": 29, "label": "EVAL with clause\napp([], X21, X21).\nand substitutionT9 -> [],\nT18 -> T25,\nX21 -> T25,\nT13 -> T25" }, { "from": 27, "to": 30, "label": "EVAL-BACKTRACK" }, { "from": 28, "to": 92, "label": "EVAL with clause\napp(.(X30, X31), X32, .(X30, X33)) :- app(X31, X32, X33).\nand substitutionX30 -> T34,\nX31 -> T35,\nT9 -> .(T34, T35),\nT18 -> T36,\nX32 -> T36,\nX33 -> T38,\nT13 -> .(T34, T38),\nT37 -> T38" }, { "from": 28, "to": 99, "label": "EVAL-BACKTRACK" }, { "from": 29, "to": 31, "label": "SUCCESS" }, { "from": 92, "to": 24, "label": "INSTANCE with matching:\nT9 -> T35\nT18 -> T36\nT13 -> T38" }, { "from": 151, "to": 153, "label": "SPLIT 1" }, { "from": 151, "to": 154, "label": "SPLIT 2\nnew knowledge:\nT48 is ground\nT49 is ground\nT52 is ground\nreplacements:X50 -> T52" }, { "from": 153, "to": 24, "label": "INSTANCE with matching:\nT9 -> T48\nT18 -> T49\nT13 -> X50" }, { "from": 154, "to": 24, "label": "INSTANCE with matching:\nT18 -> .(T47, T52)" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: appA(.(X1, X2), X3, .(X1, X4)) :- appA(X2, X3, X4). app3_bB(X1, [], X2, X3) :- appA(X1, X2, X3). app3_bB(X1, .(X2, X3), X4, X5) :- appA(X3, X4, X6). app3_bB(X1, .(X2, X3), X4, X5) :- ','(appcA(X3, X4, X6), appA(X1, .(X2, X6), X5)). Clauses: appcA([], X1, X1). appcA(.(X1, X2), X3, .(X1, X4)) :- appcA(X2, X3, X4). Afs: app3_bB(x1, x2, x3, x4) = app3_bB(x1, x2, x3) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: app3_bB_in_4: (b,b,b,f) appA_in_3: (b,b,f) appcA_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: APP3_BB_IN_GGGA(X1, [], X2, X3) -> U2_GGGA(X1, X2, X3, appA_in_gga(X1, X2, X3)) APP3_BB_IN_GGGA(X1, [], X2, X3) -> APPA_IN_GGA(X1, X2, X3) APPA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U1_GGA(X1, X2, X3, X4, appA_in_gga(X2, X3, X4)) APPA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GGA(X2, X3, X4) APP3_BB_IN_GGGA(X1, .(X2, X3), X4, X5) -> U3_GGGA(X1, X2, X3, X4, X5, appA_in_gga(X3, X4, X6)) APP3_BB_IN_GGGA(X1, .(X2, X3), X4, X5) -> APPA_IN_GGA(X3, X4, X6) APP3_BB_IN_GGGA(X1, .(X2, X3), X4, X5) -> U4_GGGA(X1, X2, X3, X4, X5, appcA_in_gga(X3, X4, X6)) U4_GGGA(X1, X2, X3, X4, X5, appcA_out_gga(X3, X4, X6)) -> U5_GGGA(X1, X2, X3, X4, X5, appA_in_gga(X1, .(X2, X6), X5)) U4_GGGA(X1, X2, X3, X4, X5, appcA_out_gga(X3, X4, X6)) -> APPA_IN_GGA(X1, .(X2, X6), X5) The TRS R consists of the following rules: appcA_in_gga([], X1, X1) -> appcA_out_gga([], X1, X1) appcA_in_gga(.(X1, X2), X3, .(X1, X4)) -> U7_gga(X1, X2, X3, X4, appcA_in_gga(X2, X3, X4)) U7_gga(X1, X2, X3, X4, appcA_out_gga(X2, X3, X4)) -> appcA_out_gga(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: [] = [] appA_in_gga(x1, x2, x3) = appA_in_gga(x1, x2) .(x1, x2) = .(x1, x2) appcA_in_gga(x1, x2, x3) = appcA_in_gga(x1, x2) appcA_out_gga(x1, x2, x3) = appcA_out_gga(x1, x2, x3) U7_gga(x1, x2, x3, x4, x5) = U7_gga(x1, x2, x3, x5) APP3_BB_IN_GGGA(x1, x2, x3, x4) = APP3_BB_IN_GGGA(x1, x2, x3) U2_GGGA(x1, x2, x3, x4) = U2_GGGA(x1, x2, x4) APPA_IN_GGA(x1, x2, x3) = APPA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U3_GGGA(x1, x2, x3, x4, x5, x6) = U3_GGGA(x1, x2, x3, x4, x6) U4_GGGA(x1, x2, x3, x4, x5, x6) = U4_GGGA(x1, x2, x3, x4, x6) U5_GGGA(x1, x2, x3, x4, x5, x6) = U5_GGGA(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: APP3_BB_IN_GGGA(X1, [], X2, X3) -> U2_GGGA(X1, X2, X3, appA_in_gga(X1, X2, X3)) APP3_BB_IN_GGGA(X1, [], X2, X3) -> APPA_IN_GGA(X1, X2, X3) APPA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> U1_GGA(X1, X2, X3, X4, appA_in_gga(X2, X3, X4)) APPA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GGA(X2, X3, X4) APP3_BB_IN_GGGA(X1, .(X2, X3), X4, X5) -> U3_GGGA(X1, X2, X3, X4, X5, appA_in_gga(X3, X4, X6)) APP3_BB_IN_GGGA(X1, .(X2, X3), X4, X5) -> APPA_IN_GGA(X3, X4, X6) APP3_BB_IN_GGGA(X1, .(X2, X3), X4, X5) -> U4_GGGA(X1, X2, X3, X4, X5, appcA_in_gga(X3, X4, X6)) U4_GGGA(X1, X2, X3, X4, X5, appcA_out_gga(X3, X4, X6)) -> U5_GGGA(X1, X2, X3, X4, X5, appA_in_gga(X1, .(X2, X6), X5)) U4_GGGA(X1, X2, X3, X4, X5, appcA_out_gga(X3, X4, X6)) -> APPA_IN_GGA(X1, .(X2, X6), X5) The TRS R consists of the following rules: appcA_in_gga([], X1, X1) -> appcA_out_gga([], X1, X1) appcA_in_gga(.(X1, X2), X3, .(X1, X4)) -> U7_gga(X1, X2, X3, X4, appcA_in_gga(X2, X3, X4)) U7_gga(X1, X2, X3, X4, appcA_out_gga(X2, X3, X4)) -> appcA_out_gga(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: [] = [] appA_in_gga(x1, x2, x3) = appA_in_gga(x1, x2) .(x1, x2) = .(x1, x2) appcA_in_gga(x1, x2, x3) = appcA_in_gga(x1, x2) appcA_out_gga(x1, x2, x3) = appcA_out_gga(x1, x2, x3) U7_gga(x1, x2, x3, x4, x5) = U7_gga(x1, x2, x3, x5) APP3_BB_IN_GGGA(x1, x2, x3, x4) = APP3_BB_IN_GGGA(x1, x2, x3) U2_GGGA(x1, x2, x3, x4) = U2_GGGA(x1, x2, x4) APPA_IN_GGA(x1, x2, x3) = APPA_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4, x5) = U1_GGA(x1, x2, x3, x5) U3_GGGA(x1, x2, x3, x4, x5, x6) = U3_GGGA(x1, x2, x3, x4, x6) U4_GGGA(x1, x2, x3, x4, x5, x6) = U4_GGGA(x1, x2, x3, x4, x6) U5_GGGA(x1, x2, x3, x4, x5, x6) = U5_GGGA(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 8 less nodes. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: APPA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GGA(X2, X3, X4) The TRS R consists of the following rules: appcA_in_gga([], X1, X1) -> appcA_out_gga([], X1, X1) appcA_in_gga(.(X1, X2), X3, .(X1, X4)) -> U7_gga(X1, X2, X3, X4, appcA_in_gga(X2, X3, X4)) U7_gga(X1, X2, X3, X4, appcA_out_gga(X2, X3, X4)) -> appcA_out_gga(.(X1, X2), X3, .(X1, X4)) The argument filtering Pi contains the following mapping: [] = [] .(x1, x2) = .(x1, x2) appcA_in_gga(x1, x2, x3) = appcA_in_gga(x1, x2) appcA_out_gga(x1, x2, x3) = appcA_out_gga(x1, x2, x3) U7_gga(x1, x2, x3, x4, x5) = U7_gga(x1, x2, x3, x5) APPA_IN_GGA(x1, x2, x3) = APPA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (8) Obligation: Pi DP problem: The TRS P consists of the following rules: APPA_IN_GGA(.(X1, X2), X3, .(X1, X4)) -> APPA_IN_GGA(X2, X3, X4) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPA_IN_GGA(x1, x2, x3) = APPA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (9) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: APPA_IN_GGA(.(X1, X2), X3) -> APPA_IN_GGA(X2, X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (11) 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: *APPA_IN_GGA(.(X1, X2), X3) -> APPA_IN_GGA(X2, X3) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (12) YES