/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern h(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 4 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES ---------------------------------------- (0) Obligation: Clauses: f(c(s(X), Y)) :- f(c(X, s(Y))). g(c(X, s(Y))) :- g(c(s(X), Y)). h(X) :- ','(f(X), g(X)). Query: h(g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 17, "program": { "directives": [], "clauses": [ [ "(f (c (s X) Y))", "(f (c X (s Y)))" ], [ "(g (c X (s Y)))", "(g (c (s X) Y))" ], [ "(h X)", "(',' (f X) (g X))" ] ] }, "graph": { "nodes": { "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(h T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": 2, "scope": 1, "term": "(h T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "type": "Nodes", "132": { "goal": [{ "clause": -1, "scope": -1, "term": "(f (c T8 (s T9)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [], "exprvars": [] } }, "143": { "goal": [{ "clause": 1, "scope": 4, "term": "(g (c (s T8) T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [], "exprvars": [] } }, "122": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (f T3) (g T3))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "133": { "goal": [{ "clause": -1, "scope": -1, "term": "(g (c (s T8) T9))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [], "exprvars": [] } }, "144": { "goal": [{ "clause": -1, "scope": -1, "term": "(g (c (s (s T28)) T29))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T28", "T29" ], "free": [], "exprvars": [] } }, "123": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (f T3) (g T3))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "134": { "goal": [{ "clause": 0, "scope": 3, "term": "(f (c T8 (s T9)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [], "exprvars": [] } }, "145": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "124": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (f (c T8 (s T9))) (g (c (s T8) T9)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [], "exprvars": [] } }, "135": { "goal": [{ "clause": -1, "scope": -1, "term": "(f (c T18 (s (s T19))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [], "exprvars": [] } }, "125": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "136": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 17, "to": 18, "label": "CASE" }, { "from": 18, "to": 122, "label": "ONLY EVAL with clause\nh(X2) :- ','(f(X2), g(X2)).\nand substitutionT1 -> T3,\nX2 -> T3" }, { "from": 122, "to": 123, "label": "CASE" }, { "from": 123, "to": 124, "label": "EVAL with clause\nf(c(s(X7), X8)) :- f(c(X7, s(X8))).\nand substitutionX7 -> T8,\nX8 -> T9,\nT3 -> c(s(T8), T9)" }, { "from": 123, "to": 125, "label": "EVAL-BACKTRACK" }, { "from": 124, "to": 132, "label": "SPLIT 1" }, { "from": 124, "to": 133, "label": "SPLIT 2\nnew knowledge:\nT8 is ground\nT9 is ground" }, { "from": 132, "to": 134, "label": "CASE" }, { "from": 133, "to": 143, "label": "CASE" }, { "from": 134, "to": 135, "label": "EVAL with clause\nf(c(s(X17), X18)) :- f(c(X17, s(X18))).\nand substitutionX17 -> T18,\nT8 -> s(T18),\nT9 -> T19,\nX18 -> s(T19)" }, { "from": 134, "to": 136, "label": "EVAL-BACKTRACK" }, { "from": 135, "to": 132, "label": "INSTANCE with matching:\nT8 -> T18\nT9 -> s(T19)" }, { "from": 143, "to": 144, "label": "EVAL with clause\ng(c(X27, s(X28))) :- g(c(s(X27), X28)).\nand substitutionT8 -> T28,\nX27 -> s(T28),\nX28 -> T29,\nT9 -> s(T29)" }, { "from": 143, "to": 145, "label": "EVAL-BACKTRACK" }, { "from": 144, "to": 133, "label": "INSTANCE with matching:\nT8 -> s(T28)\nT9 -> T29" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: fA(s(X1), X2) :- fA(X1, s(X2)). gB(X1, s(X2)) :- gB(s(X1), X2). hC(c(s(X1), X2)) :- fA(X1, X2). hC(c(s(X1), X2)) :- ','(fcA(X1, X2), gB(X1, X2)). Clauses: fcA(s(X1), X2) :- fcA(X1, s(X2)). gcB(X1, s(X2)) :- gcB(s(X1), X2). Afs: hC(x1) = hC(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: hC_in_1: (b) fA_in_2: (b,b) fcA_in_2: (b,b) gB_in_2: (b,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: HC_IN_G(c(s(X1), X2)) -> U3_G(X1, X2, fA_in_gg(X1, X2)) HC_IN_G(c(s(X1), X2)) -> FA_IN_GG(X1, X2) FA_IN_GG(s(X1), X2) -> U1_GG(X1, X2, fA_in_gg(X1, s(X2))) FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) HC_IN_G(c(s(X1), X2)) -> U4_G(X1, X2, fcA_in_gg(X1, X2)) U4_G(X1, X2, fcA_out_gg(X1, X2)) -> U5_G(X1, X2, gB_in_gg(X1, X2)) U4_G(X1, X2, fcA_out_gg(X1, X2)) -> GB_IN_GG(X1, X2) GB_IN_GG(X1, s(X2)) -> U2_GG(X1, X2, gB_in_gg(s(X1), X2)) GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) The TRS R consists of the following rules: fcA_in_gg(s(X1), X2) -> U7_gg(X1, X2, fcA_in_gg(X1, s(X2))) U7_gg(X1, X2, fcA_out_gg(X1, s(X2))) -> fcA_out_gg(s(X1), X2) Pi is empty. 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: HC_IN_G(c(s(X1), X2)) -> U3_G(X1, X2, fA_in_gg(X1, X2)) HC_IN_G(c(s(X1), X2)) -> FA_IN_GG(X1, X2) FA_IN_GG(s(X1), X2) -> U1_GG(X1, X2, fA_in_gg(X1, s(X2))) FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) HC_IN_G(c(s(X1), X2)) -> U4_G(X1, X2, fcA_in_gg(X1, X2)) U4_G(X1, X2, fcA_out_gg(X1, X2)) -> U5_G(X1, X2, gB_in_gg(X1, X2)) U4_G(X1, X2, fcA_out_gg(X1, X2)) -> GB_IN_GG(X1, X2) GB_IN_GG(X1, s(X2)) -> U2_GG(X1, X2, gB_in_gg(s(X1), X2)) GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) The TRS R consists of the following rules: fcA_in_gg(s(X1), X2) -> U7_gg(X1, X2, fcA_in_gg(X1, s(X2))) U7_gg(X1, X2, fcA_out_gg(X1, s(X2))) -> fcA_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 7 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) The TRS R consists of the following rules: fcA_in_gg(s(X1), X2) -> U7_gg(X1, X2, fcA_in_gg(X1, s(X2))) U7_gg(X1, X2, fcA_out_gg(X1, s(X2))) -> fcA_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (12) 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: *GB_IN_GG(X1, s(X2)) -> GB_IN_GG(s(X1), X2) The graph contains the following edges 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) The TRS R consists of the following rules: fcA_in_gg(s(X1), X2) -> U7_gg(X1, X2, fcA_in_gg(X1, s(X2))) U7_gg(X1, X2, fcA_out_gg(X1, s(X2))) -> fcA_out_gg(s(X1), X2) Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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: *FA_IN_GG(s(X1), X2) -> FA_IN_GG(X1, s(X2)) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES