3.23/1.70 YES 3.23/1.72 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 3.23/1.72 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.23/1.72 3.23/1.72 3.23/1.72 Left Termination of the query pattern 3.23/1.72 3.23/1.72 p(g,a) 3.23/1.72 3.23/1.72 w.r.t. the given Prolog program could successfully be proven: 3.23/1.72 3.23/1.72 (0) Prolog 3.23/1.72 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 3.23/1.72 (2) TRIPLES 3.23/1.72 (3) TPisEmptyProof [EQUIVALENT, 0 ms] 3.23/1.72 (4) YES 3.23/1.72 3.23/1.72 3.23/1.72 ---------------------------------------- 3.23/1.72 3.23/1.72 (0) 3.23/1.72 Obligation: 3.23/1.72 Clauses: 3.23/1.72 3.23/1.72 p(X, g(X)). 3.23/1.72 p(X, f(X)) :- p(X, g(Y)). 3.23/1.72 3.23/1.72 3.23/1.72 Query: p(g,a) 3.23/1.72 ---------------------------------------- 3.23/1.72 3.23/1.72 (1) PrologToDTProblemTransformerProof (SOUND) 3.23/1.72 Built DT problem from termination graph DT10. 3.23/1.72 3.23/1.72 { 3.23/1.72 "root": 1, 3.23/1.72 "program": { 3.23/1.72 "directives": [], 3.23/1.72 "clauses": [ 3.23/1.72 [ 3.23/1.72 "(p X (g X))", 3.23/1.72 null 3.23/1.72 ], 3.23/1.72 [ 3.23/1.72 "(p X (f X))", 3.23/1.72 "(p X (g Y))" 3.23/1.72 ] 3.23/1.72 ] 3.23/1.72 }, 3.23/1.72 "graph": { 3.23/1.72 "nodes": { 3.23/1.72 "11": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": 1, 3.23/1.72 "scope": 1, 3.23/1.72 "term": "(p T4 T2)" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T4"], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "88": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": 1, 3.23/1.72 "scope": 2, 3.23/1.72 "term": "(p T6 (g X5))" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T6"], 3.23/1.72 "free": ["X5"], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "99": { 3.23/1.72 "goal": [], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": [], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "89": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": -1, 3.23/1.72 "scope": -1, 3.23/1.72 "term": "(true)" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": [], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "type": "Nodes", 3.23/1.72 "1": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": -1, 3.23/1.72 "scope": -1, 3.23/1.72 "term": "(p T1 T2)" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T1"], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "4": { 3.23/1.72 "goal": [ 3.23/1.72 { 3.23/1.72 "clause": 0, 3.23/1.72 "scope": 1, 3.23/1.72 "term": "(p T1 T2)" 3.23/1.72 }, 3.23/1.72 { 3.23/1.72 "clause": 1, 3.23/1.72 "scope": 1, 3.23/1.72 "term": "(p T1 T2)" 3.23/1.72 } 3.23/1.72 ], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T1"], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "7": { 3.23/1.72 "goal": [ 3.23/1.72 { 3.23/1.72 "clause": -1, 3.23/1.72 "scope": -1, 3.23/1.72 "term": "(true)" 3.23/1.72 }, 3.23/1.72 { 3.23/1.72 "clause": 1, 3.23/1.72 "scope": 1, 3.23/1.72 "term": "(p T4 T2)" 3.23/1.72 } 3.23/1.72 ], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T4"], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "90": { 3.23/1.72 "goal": [], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": [], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "91": { 3.23/1.72 "goal": [], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": [], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "92": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": -1, 3.23/1.72 "scope": -1, 3.23/1.72 "term": "(p T14 (g X14))" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [[ 3.23/1.72 "(p T14 T2)", 3.23/1.72 "(p X2 (g X2))" 3.23/1.72 ]], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T14"], 3.23/1.72 "free": [ 3.23/1.72 "X2", 3.23/1.72 "X14" 3.23/1.72 ], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "93": { 3.23/1.72 "goal": [], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": [], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "94": { 3.23/1.72 "goal": [ 3.23/1.72 { 3.23/1.72 "clause": 0, 3.23/1.72 "scope": 3, 3.23/1.72 "term": "(p T14 (g X14))" 3.23/1.72 }, 3.23/1.72 { 3.23/1.72 "clause": 1, 3.23/1.72 "scope": 3, 3.23/1.72 "term": "(p T14 (g X14))" 3.23/1.72 } 3.23/1.72 ], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [[ 3.23/1.72 "(p T14 T2)", 3.23/1.72 "(p X2 (g X2))" 3.23/1.72 ]], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T14"], 3.23/1.72 "free": [ 3.23/1.72 "X2", 3.23/1.72 "X14" 3.23/1.72 ], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "84": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": -1, 3.23/1.72 "scope": -1, 3.23/1.72 "term": "(p T6 (g X5))" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T6"], 3.23/1.72 "free": ["X5"], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "95": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": 0, 3.23/1.72 "scope": 3, 3.23/1.72 "term": "(p T14 (g X14))" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [[ 3.23/1.72 "(p T14 T2)", 3.23/1.72 "(p X2 (g X2))" 3.23/1.72 ]], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T14"], 3.23/1.72 "free": [ 3.23/1.72 "X2", 3.23/1.72 "X14" 3.23/1.72 ], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "85": { 3.23/1.72 "goal": [], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": [], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "96": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": 1, 3.23/1.72 "scope": 3, 3.23/1.72 "term": "(p T14 (g X14))" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [[ 3.23/1.72 "(p T14 T2)", 3.23/1.72 "(p X2 (g X2))" 3.23/1.72 ]], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T14"], 3.23/1.72 "free": [ 3.23/1.72 "X2", 3.23/1.72 "X14" 3.23/1.72 ], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "86": { 3.23/1.72 "goal": [ 3.23/1.72 { 3.23/1.72 "clause": 0, 3.23/1.72 "scope": 2, 3.23/1.72 "term": "(p T6 (g X5))" 3.23/1.72 }, 3.23/1.72 { 3.23/1.72 "clause": 1, 3.23/1.72 "scope": 2, 3.23/1.72 "term": "(p T6 (g X5))" 3.23/1.72 } 3.23/1.72 ], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T6"], 3.23/1.72 "free": ["X5"], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "97": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": -1, 3.23/1.72 "scope": -1, 3.23/1.72 "term": "(true)" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": [], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "10": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": 1, 3.23/1.72 "scope": 1, 3.23/1.72 "term": "(p T1 T2)" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [[ 3.23/1.72 "(p T1 T2)", 3.23/1.72 "(p X2 (g X2))" 3.23/1.72 ]], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T1"], 3.23/1.72 "free": ["X2"], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "87": { 3.23/1.72 "goal": [{ 3.23/1.72 "clause": 0, 3.23/1.72 "scope": 2, 3.23/1.72 "term": "(p T6 (g X5))" 3.23/1.72 }], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": ["T6"], 3.23/1.72 "free": ["X5"], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "98": { 3.23/1.72 "goal": [], 3.23/1.72 "kb": { 3.23/1.72 "nonunifying": [], 3.23/1.72 "intvars": {}, 3.23/1.72 "arithmetic": { 3.23/1.72 "type": "PlainIntegerRelationState", 3.23/1.72 "relations": [] 3.23/1.72 }, 3.23/1.72 "ground": [], 3.23/1.72 "free": [], 3.23/1.72 "exprvars": [] 3.23/1.72 } 3.23/1.72 } 3.23/1.72 }, 3.23/1.72 "edges": [ 3.23/1.72 { 3.23/1.72 "from": 1, 3.23/1.72 "to": 4, 3.23/1.72 "label": "CASE" 3.23/1.72 }, 3.23/1.72 { 3.23/1.72 "from": 4, 3.23/1.72 "to": 7, 3.23/1.72 "label": "EVAL with clause\np(X2, g(X2)).\nand substitutionT1 -> T4,\nX2 -> T4,\nT2 -> g(T4)" 3.23/1.72 }, 3.23/1.72 { 3.23/1.72 "from": 4, 3.23/1.72 "to": 10, 3.23/1.72 "label": "EVAL-BACKTRACK" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 7, 3.35/1.72 "to": 11, 3.35/1.72 "label": "SUCCESS" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 10, 3.35/1.72 "to": 92, 3.35/1.72 "label": "EVAL with clause\np(X13, f(X13)) :- p(X13, g(X14)).\nand substitutionT1 -> T14,\nX13 -> T14,\nT2 -> f(T14)" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 10, 3.35/1.72 "to": 93, 3.35/1.72 "label": "EVAL-BACKTRACK" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 11, 3.35/1.72 "to": 84, 3.35/1.72 "label": "EVAL with clause\np(X4, f(X4)) :- p(X4, g(X5)).\nand substitutionT4 -> T6,\nX4 -> T6,\nT2 -> f(T6)" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 11, 3.35/1.72 "to": 85, 3.35/1.72 "label": "EVAL-BACKTRACK" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 84, 3.35/1.72 "to": 86, 3.35/1.72 "label": "CASE" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 86, 3.35/1.72 "to": 87, 3.35/1.72 "label": "PARALLEL" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 86, 3.35/1.72 "to": 88, 3.35/1.72 "label": "PARALLEL" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 87, 3.35/1.72 "to": 89, 3.35/1.72 "label": "ONLY EVAL with clause\np(X10, g(X10)).\nand substitutionT6 -> T11,\nX10 -> T11,\nX5 -> T11" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 88, 3.35/1.72 "to": 91, 3.35/1.72 "label": "BACKTRACK\nfor clause: p(X, f(X)) :- p(X, g(Y))because of non-unification" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 89, 3.35/1.72 "to": 90, 3.35/1.72 "label": "SUCCESS" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 92, 3.35/1.72 "to": 94, 3.35/1.72 "label": "CASE" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 94, 3.35/1.72 "to": 95, 3.35/1.72 "label": "PARALLEL" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 94, 3.35/1.72 "to": 96, 3.35/1.72 "label": "PARALLEL" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 95, 3.35/1.72 "to": 97, 3.35/1.72 "label": "ONLY EVAL with clause\np(X19, g(X19)).\nand substitutionT14 -> T19,\nX19 -> T19,\nX14 -> T19" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 96, 3.35/1.72 "to": 99, 3.35/1.72 "label": "BACKTRACK\nfor clause: p(X, f(X)) :- p(X, g(Y))because of non-unification" 3.35/1.72 }, 3.35/1.72 { 3.35/1.72 "from": 97, 3.35/1.72 "to": 98, 3.35/1.72 "label": "SUCCESS" 3.35/1.72 } 3.35/1.72 ], 3.35/1.72 "type": "Graph" 3.35/1.72 } 3.35/1.72 } 3.35/1.72 3.35/1.72 ---------------------------------------- 3.35/1.72 3.35/1.72 (2) 3.35/1.72 Obligation: 3.35/1.72 Triples: 3.35/1.72 3.35/1.72 3.35/1.72 Clauses: 3.35/1.72 3.35/1.72 3.35/1.72 Afs: 3.35/1.72 3.35/1.72 3.35/1.72 ---------------------------------------- 3.35/1.72 3.35/1.72 (3) TPisEmptyProof (EQUIVALENT) 3.35/1.72 There are no more dependency triples. Hence, the dependency triple problem trivially terminates. 3.35/1.72 ---------------------------------------- 3.35/1.72 3.35/1.72 (4) 3.35/1.72 YES 3.37/1.75 EOF