/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern p(a) w.r.t. the given Prolog program could not be shown: (0) Prolog (1) CutEliminatorProof [SOUND, 0 ms] (2) Prolog (3) PrologToTRSTransformerProof [SOUND, 0 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 11 ms] (6) QTRS (7) Overlay + Local Confluence [EQUIVALENT, 0 ms] (8) QTRS (9) DependencyPairsProof [EQUIVALENT, 0 ms] (10) QDP (11) UsableRulesProof [EQUIVALENT, 0 ms] (12) QDP (13) QReductionProof [EQUIVALENT, 0 ms] (14) QDP (15) NonTerminationLoopProof [COMPLETE, 0 ms] (16) NO (17) PrologToDTProblemTransformerProof [SOUND, 0 ms] (18) TRIPLES (19) TriplesToPiDPProof [SOUND, 0 ms] (20) PiDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) PiDP (23) PiDPToQDPProof [SOUND, 0 ms] (24) QDP (25) NonTerminationLoopProof [COMPLETE, 0 ms] (26) NO ---------------------------------------- (0) Obligation: Clauses: p(X) :- ','(no(letter(X)), q(X)). q(x) :- p(X1). letter(x). no(X) :- ','(X, ','(!, failure(a))). no(X2). failure(b). Query: p(a) ---------------------------------------- (1) CutEliminatorProof (SOUND) Eliminated all cuts by simply ignoring them[PROLOG]. ---------------------------------------- (2) Obligation: Clauses: p(X) :- ','(no(letter(X)), q(X)). q(x) :- p(X1). letter(x). no(X) :- ','(X, failure(a)). no(X2). failure(b). Query: p(a) ---------------------------------------- (3) PrologToTRSTransformerProof (SOUND) Transformed Prolog program to TRS. { "root": 3, "program": { "directives": [], "clauses": [ [ "(p X)", "(',' (no (letter X)) (q X))" ], [ "(q (x))", "(p X1)" ], [ "(letter (x))", null ], [ "(no X)", "(',' X (',' (!) (failure (a))))" ], [ "(no X2)", null ], [ "(failure (b))", null ] ] }, "graph": { "nodes": { "44": { "goal": [{ "clause": -1, "scope": -1, "term": "(q T16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "23": { "goal": [ { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T6)) (q T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "16": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (letter T11)) (',' (!_2) (failure (a)))) (q T11))" }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T6)) (q T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (q (x)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "49": { "goal": [{ "clause": 1, "scope": 6, "term": "(q T16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "39": { "goal": [{ "clause": 5, "scope": 5, "term": "(',' (failure (a)) (q (x)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "18": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (letter T11) (',' (',' (!_2) (failure (a))) (q T11)))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T6)) (q T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [ { "clause": 2, "scope": 4, "term": "(',' (letter T11) (',' (',' (!_2) (failure (a))) (q T11)))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T6)) (q T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (letter T6)) (q T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "50": { "goal": [{ "clause": -1, "scope": -1, "term": "(p X18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X18"], "exprvars": [] } }, "51": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "41": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "42": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T6)) (q T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "10": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (no (letter T6)) (q T6))" }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T6)) (q T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_2) (failure (a))) (q (x)))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T6)) (q T6))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "43": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (no (letter T6)) (q T6))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 6, "label": "CASE" }, { "from": 6, "to": 8, "label": "ONLY EVAL with clause\np(X6) :- ','(no(letter(X6)), q(X6)).\nand substitutionT1 -> T6,\nX6 -> T6,\nT5 -> T6" }, { "from": 8, "to": 10, "label": "CASE" }, { "from": 10, "to": 16, "label": "ONLY EVAL with clause\nno(X10) :- ','(call(X10), ','(!_2, failure(a))).\nand substitutionT6 -> T11,\nX10 -> letter(T11),\nT10 -> T11" }, { "from": 16, "to": 18, "label": "CALL" }, { "from": 18, "to": 19, "label": "CASE" }, { "from": 19, "to": 21, "label": "EVAL with clause\nletter(x).\nand substitutionT11 -> x" }, { "from": 19, "to": 23, "label": "EVAL-BACKTRACK" }, { "from": 21, "to": 27, "label": "CUT" }, { "from": 23, "to": 42, "label": "FAILURE" }, { "from": 27, "to": 39, "label": "CASE" }, { "from": 39, "to": 41, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 42, "to": 43, "label": "FAILURE" }, { "from": 43, "to": 44, "label": "ONLY EVAL with clause\nno(X15).\nand substitutionT6 -> T16,\nX15 -> letter(T16),\nT15 -> T16" }, { "from": 44, "to": 49, "label": "CASE" }, { "from": 49, "to": 50, "label": "EVAL with clause\nq(x) :- p(X18).\nand substitutionT16 -> x" }, { "from": 49, "to": 51, "label": "EVAL-BACKTRACK" }, { "from": 50, "to": 3, "label": "INSTANCE with matching:\nT1 -> X18" } ], "type": "Graph" } } ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f3_in -> U1(f3_in) U1(f3_out1(X18)) -> f3_out1(x) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(U1(x_1)) = 2*x_1 POL(f3_in) = 0 POL(f3_out1(x_1)) = 1 + 2*x_1 POL(x) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U1(f3_out1(X18)) -> f3_out1(x) ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f3_in -> U1(f3_in) Q is empty. ---------------------------------------- (7) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (8) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: f3_in -> U1(f3_in) The set Q consists of the following terms: f3_in ---------------------------------------- (9) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: F3_IN -> F3_IN The TRS R consists of the following rules: f3_in -> U1(f3_in) The set Q consists of the following terms: f3_in We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: F3_IN -> F3_IN R is empty. The set Q consists of the following terms: f3_in We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f3_in ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: F3_IN -> F3_IN R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = F3_IN evaluates to t =F3_IN Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from F3_IN to F3_IN. ---------------------------------------- (16) NO ---------------------------------------- (17) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(p X)", "(',' (no (letter X)) (q X))" ], [ "(q (x))", "(p X1)" ], [ "(letter (x))", null ], [ "(no X)", "(',' X (',' (!) (failure (a))))" ], [ "(no X2)", null ], [ "(failure (b))", null ] ] }, "graph": { "nodes": { "33": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (no (letter T4)) (q T4))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (call (letter T9)) (',' (!_2) (failure (a)))) (q T9))" }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T4)) (q T4))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "46": { "goal": [{ "clause": 1, "scope": 6, "term": "(q T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (letter T9) (',' (',' (!_2) (failure (a))) (q T9)))" }, { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T4)) (q T4))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "25": { "goal": [ { "clause": 2, "scope": 4, "term": "(',' (letter T9) (',' (',' (!_2) (failure (a))) (q T9)))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T4)) (q T4))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "47": { "goal": [{ "clause": -1, "scope": -1, "term": "(p X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X15"], "exprvars": [] } }, "26": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (',' (!_2) (failure (a))) (q (x)))" }, { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T4)) (q T4))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "48": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [ { "clause": -1, "scope": 4, "term": null }, { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T4)) (q T4))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "29": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (failure (a)) (q (x)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "4": { "goal": [{ "clause": 0, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (no (letter T4)) (q T4))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "9": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (no (letter T4)) (q T4))" }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T4)) (q T4))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "40": { "goal": [{ "clause": -1, "scope": -1, "term": "(q T14)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "30": { "goal": [{ "clause": 5, "scope": 5, "term": "(',' (failure (a)) (q (x)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "32": { "goal": [ { "clause": -1, "scope": 3, "term": null }, { "clause": 4, "scope": 2, "term": "(',' (no (letter T4)) (q T4))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 7, "label": "ONLY EVAL with clause\np(X4) :- ','(no(letter(X4)), q(X4)).\nand substitutionT1 -> T4,\nX4 -> T4,\nT3 -> T4" }, { "from": 7, "to": 9, "label": "CASE" }, { "from": 9, "to": 12, "label": "ONLY EVAL with clause\nno(X7) :- ','(call(X7), ','(!_2, failure(a))).\nand substitutionT4 -> T9,\nX7 -> letter(T9),\nT8 -> T9" }, { "from": 12, "to": 14, "label": "CALL" }, { "from": 14, "to": 25, "label": "CASE" }, { "from": 25, "to": 26, "label": "EVAL with clause\nletter(x).\nand substitutionT9 -> x" }, { "from": 25, "to": 28, "label": "EVAL-BACKTRACK" }, { "from": 26, "to": 29, "label": "CUT" }, { "from": 28, "to": 32, "label": "FAILURE" }, { "from": 29, "to": 30, "label": "CASE" }, { "from": 30, "to": 31, "label": "BACKTRACK\nfor clause: failure(b)because of non-unification" }, { "from": 32, "to": 33, "label": "FAILURE" }, { "from": 33, "to": 40, "label": "ONLY EVAL with clause\nno(X12).\nand substitutionT4 -> T14,\nX12 -> letter(T14),\nT13 -> T14" }, { "from": 40, "to": 46, "label": "CASE" }, { "from": 46, "to": 47, "label": "EVAL with clause\nq(x) :- p(X15).\nand substitutionT14 -> x" }, { "from": 46, "to": 48, "label": "EVAL-BACKTRACK" }, { "from": 47, "to": 2, "label": "INSTANCE with matching:\nT1 -> X15" } ], "type": "Graph" } } ---------------------------------------- (18) Obligation: Triples: pA(x) :- pA(X1). Clauses: pcA(x) :- pcA(X1). Afs: pA(x1) = pA ---------------------------------------- (19) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: pA_in_1: (f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: PA_IN_A(x) -> U1_A(pA_in_a(X1)) PA_IN_A(x) -> PA_IN_A(X1) R is empty. The argument filtering Pi contains the following mapping: pA_in_a(x1) = pA_in_a x = x PA_IN_A(x1) = PA_IN_A U1_A(x1) = U1_A(x1) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (20) Obligation: Pi DP problem: The TRS P consists of the following rules: PA_IN_A(x) -> U1_A(pA_in_a(X1)) PA_IN_A(x) -> PA_IN_A(X1) R is empty. The argument filtering Pi contains the following mapping: pA_in_a(x1) = pA_in_a x = x PA_IN_A(x1) = PA_IN_A U1_A(x1) = U1_A(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. ---------------------------------------- (22) Obligation: Pi DP problem: The TRS P consists of the following rules: PA_IN_A(x) -> PA_IN_A(X1) R is empty. The argument filtering Pi contains the following mapping: x = x PA_IN_A(x1) = PA_IN_A We have to consider all (P,R,Pi)-chains ---------------------------------------- (23) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: PA_IN_A -> PA_IN_A R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (25) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = PA_IN_A evaluates to t =PA_IN_A Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [ ] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from PA_IN_A to PA_IN_A. ---------------------------------------- (26) NO