YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern app(a,a,g) 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: app([], X, X). app(.(X, Xs), Ys, .(X, Zs)) :- app(Xs, Ys, Zs). Query: app(a,a,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(app ([]) X X)", null ], [ "(app (. X Xs) Ys (. X Zs))", "(app Xs Ys Zs)" ] ] }, "graph": { "nodes": { "type": "Nodes", "110": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "111": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T64 T65 T63)" }], "kb": { "nonunifying": [[ "(app T1 T2 (. T41 (. T60 T63)))", "(app ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T60", "T63" ], "free": ["X2"], "exprvars": [] } }, "112": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "94": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T45 T46 T44)" }], "kb": { "nonunifying": [[ "(app T1 T2 (. T41 T44))", "(app ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T44" ], "free": ["X2"], "exprvars": [] } }, "95": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "goal": [{ "clause": 0, "scope": 2, "term": "(app T14 T15 T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "32": { "goal": [{ "clause": 1, "scope": 2, "term": "(app T14 T15 T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "98": { "goal": [ { "clause": 0, "scope": 3, "term": "(app T45 T46 T44)" }, { "clause": 1, "scope": 3, "term": "(app T45 T46 T44)" } ], "kb": { "nonunifying": [[ "(app T1 T2 (. T41 T44))", "(app ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T44" ], "free": ["X2"], "exprvars": [] } }, "11": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(app T1 T2 T5)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "33": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [{ "clause": 1, "scope": 1, "term": "(app T1 T2 T3)" }], "kb": { "nonunifying": [[ "(app T1 T2 T3)", "(app ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": ["X2"], "exprvars": [] } }, "34": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": 1, "scope": 1, "term": "(app T1 T2 T5)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T5"], "free": [], "exprvars": [] } }, "35": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T14 T15 T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "36": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T33 T34 T32)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T32"], "free": [], "exprvars": [] } }, "15": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "16": { "goal": [ { "clause": 0, "scope": 2, "term": "(app T14 T15 T13)" }, { "clause": 1, "scope": 2, "term": "(app T14 T15 T13)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": [], "exprvars": [] } }, "39": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(app T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "103": { "goal": [{ "clause": 0, "scope": 3, "term": "(app T45 T46 T44)" }], "kb": { "nonunifying": [[ "(app T1 T2 (. T41 T44))", "(app ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T44" ], "free": ["X2"], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(app T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(app T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "105": { "goal": [{ "clause": 1, "scope": 3, "term": "(app T45 T46 T44)" }], "kb": { "nonunifying": [[ "(app T1 T2 (. T41 T44))", "(app ([]) X2 X2)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T41", "T44" ], "free": ["X2"], "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": 2, "to": 6, "label": "CASE" }, { "from": 6, "to": 11, "label": "EVAL with clause\napp([], X2, X2).\nand substitutionT1 -> [],\nT2 -> T5,\nX2 -> T5,\nT3 -> T5" }, { "from": 6, "to": 12, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 13, "label": "SUCCESS" }, { "from": 12, "to": 94, "label": "EVAL with clause\napp(.(X34, X35), X36, .(X34, X37)) :- app(X35, X36, X37).\nand substitutionX34 -> T41,\nX35 -> T45,\nT1 -> .(T41, T45),\nT2 -> T46,\nX36 -> T46,\nX37 -> T44,\nT3 -> .(T41, T44),\nT42 -> T45,\nT43 -> T46" }, { "from": 12, "to": 95, "label": "EVAL-BACKTRACK" }, { "from": 13, "to": 14, "label": "EVAL with clause\napp(.(X7, X8), X9, .(X7, X10)) :- app(X8, X9, X10).\nand substitutionX7 -> T10,\nX8 -> T14,\nT1 -> .(T10, T14),\nT2 -> T15,\nX9 -> T15,\nX10 -> T13,\nT5 -> .(T10, T13),\nT11 -> T14,\nT12 -> T15" }, { "from": 13, "to": 15, "label": "EVAL-BACKTRACK" }, { "from": 14, "to": 16, "label": "CASE" }, { "from": 16, "to": 31, "label": "PARALLEL" }, { "from": 16, "to": 32, "label": "PARALLEL" }, { "from": 31, "to": 33, "label": "EVAL with clause\napp([], X15, X15).\nand substitutionT14 -> [],\nT15 -> T20,\nX15 -> T20,\nT13 -> T20" }, { "from": 31, "to": 34, "label": "EVAL-BACKTRACK" }, { "from": 32, "to": 36, "label": "EVAL with clause\napp(.(X24, X25), X26, .(X24, X27)) :- app(X25, X26, X27).\nand substitutionX24 -> T29,\nX25 -> T33,\nT14 -> .(T29, T33),\nT15 -> T34,\nX26 -> T34,\nX27 -> T32,\nT13 -> .(T29, T32),\nT30 -> T33,\nT31 -> T34" }, { "from": 32, "to": 39, "label": "EVAL-BACKTRACK" }, { "from": 33, "to": 35, "label": "SUCCESS" }, { "from": 36, "to": 2, "label": "INSTANCE with matching:\nT1 -> T33\nT2 -> T34\nT3 -> T32" }, { "from": 94, "to": 98, "label": "CASE" }, { "from": 98, "to": 103, "label": "PARALLEL" }, { "from": 98, "to": 105, "label": "PARALLEL" }, { "from": 103, "to": 108, "label": "EVAL with clause\napp([], X42, X42).\nand substitutionT45 -> [],\nT46 -> T51,\nX42 -> T51,\nT44 -> T51" }, { "from": 103, "to": 109, "label": "EVAL-BACKTRACK" }, { "from": 105, "to": 111, "label": "EVAL with clause\napp(.(X51, X52), X53, .(X51, X54)) :- app(X52, X53, X54).\nand substitutionX51 -> T60,\nX52 -> T64,\nT45 -> .(T60, T64),\nT46 -> T65,\nX53 -> T65,\nX54 -> T63,\nT44 -> .(T60, T63),\nT61 -> T64,\nT62 -> T65" }, { "from": 105, "to": 112, "label": "EVAL-BACKTRACK" }, { "from": 108, "to": 110, "label": "SUCCESS" }, { "from": 111, "to": 2, "label": "INSTANCE with matching:\nT1 -> T64\nT2 -> T65\nT3 -> T63" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: appA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) :- appA(X3, X4, X5). appA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) :- appA(X3, X4, X5). Clauses: appcA([], X1, X1). appcA(.(X1, []), X2, .(X1, X2)). appcA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) :- appcA(X3, X4, X5). appcA(.(X1, []), X2, .(X1, X2)). appcA(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) :- appcA(X3, X4, X5). Afs: appA(x1, x2, x3) = appA(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: appA_in_3: (f,f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: APPA_IN_AAG(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> U1_AAG(X1, X2, X3, X4, X5, appA_in_aag(X3, X4, X5)) APPA_IN_AAG(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> APPA_IN_AAG(X3, X4, X5) R is empty. The argument filtering Pi contains the following mapping: appA_in_aag(x1, x2, x3) = appA_in_aag(x3) .(x1, x2) = .(x1, x2) APPA_IN_AAG(x1, x2, x3) = APPA_IN_AAG(x3) U1_AAG(x1, x2, x3, x4, x5, x6) = U1_AAG(x1, x2, x5, 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: APPA_IN_AAG(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> U1_AAG(X1, X2, X3, X4, X5, appA_in_aag(X3, X4, X5)) APPA_IN_AAG(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> APPA_IN_AAG(X3, X4, X5) R is empty. The argument filtering Pi contains the following mapping: appA_in_aag(x1, x2, x3) = appA_in_aag(x3) .(x1, x2) = .(x1, x2) APPA_IN_AAG(x1, x2, x3) = APPA_IN_AAG(x3) U1_AAG(x1, x2, x3, x4, x5, x6) = U1_AAG(x1, x2, x5, x6) 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: APPA_IN_AAG(.(X1, .(X2, X3)), X4, .(X1, .(X2, X5))) -> APPA_IN_AAG(X3, X4, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) APPA_IN_AAG(x1, x2, x3) = APPA_IN_AAG(x3) 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: APPA_IN_AAG(.(X1, .(X2, X5))) -> APPA_IN_AAG(X5) 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: *APPA_IN_AAG(.(X1, .(X2, X5))) -> APPA_IN_AAG(X5) The graph contains the following edges 1 > 1 ---------------------------------------- (10) YES