3.15/1.56 YES 3.15/1.57 proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl 3.15/1.57 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.15/1.57 3.15/1.57 3.15/1.57 Left Termination of the query pattern 3.15/1.57 3.15/1.57 f(a,a,g) 3.15/1.57 3.15/1.57 w.r.t. the given Prolog program could successfully be proven: 3.15/1.57 3.15/1.57 (0) Prolog 3.15/1.57 (1) PrologToIRSwTTransformerProof [SOUND, 0 ms] 3.15/1.57 (2) TRUE 3.15/1.57 3.15/1.57 3.15/1.57 ---------------------------------------- 3.15/1.57 3.15/1.57 (0) 3.15/1.57 Obligation: 3.15/1.57 Clauses: 3.15/1.57 3.15/1.57 f(0, 1, X) :- f(X, X, X). 3.15/1.57 3.15/1.57 3.15/1.57 Query: f(a,a,g) 3.15/1.57 ---------------------------------------- 3.15/1.57 3.15/1.57 (1) PrologToIRSwTTransformerProof (SOUND) 3.15/1.57 Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert 3.15/1.57 3.15/1.57 { 3.15/1.57 "root": 8, 3.15/1.57 "program": { 3.15/1.57 "directives": [], 3.15/1.57 "clauses": [[ 3.15/1.57 "(f (0) (1) X)", 3.15/1.57 "(f X X X)" 3.15/1.57 ]] 3.15/1.57 }, 3.15/1.57 "graph": { 3.15/1.57 "nodes": { 3.15/1.57 "44": { 3.15/1.57 "goal": [], 3.15/1.57 "kb": { 3.15/1.57 "nonunifying": [], 3.15/1.57 "intvars": {}, 3.15/1.57 "arithmetic": { 3.15/1.57 "type": "PlainIntegerRelationState", 3.15/1.57 "relations": [] 3.15/1.57 }, 3.15/1.57 "ground": [], 3.15/1.57 "free": [], 3.15/1.57 "exprvars": [] 3.15/1.57 } 3.15/1.57 }, 3.15/1.57 "25": { 3.15/1.57 "goal": [{ 3.15/1.57 "clause": 0, 3.15/1.57 "scope": 1, 3.15/1.57 "term": "(f T1 T2 T3)" 3.15/1.57 }], 3.15/1.57 "kb": { 3.15/1.57 "nonunifying": [], 3.15/1.57 "intvars": {}, 3.15/1.57 "arithmetic": { 3.15/1.57 "type": "PlainIntegerRelationState", 3.15/1.57 "relations": [] 3.15/1.57 }, 3.15/1.57 "ground": ["T3"], 3.15/1.57 "free": [], 3.15/1.57 "exprvars": [] 3.15/1.57 } 3.15/1.57 }, 3.15/1.57 "8": { 3.15/1.57 "goal": [{ 3.15/1.57 "clause": -1, 3.15/1.57 "scope": -1, 3.15/1.57 "term": "(f T1 T2 T3)" 3.15/1.57 }], 3.15/1.57 "kb": { 3.15/1.57 "nonunifying": [], 3.15/1.57 "intvars": {}, 3.15/1.57 "arithmetic": { 3.15/1.57 "type": "PlainIntegerRelationState", 3.15/1.57 "relations": [] 3.15/1.57 }, 3.15/1.57 "ground": ["T3"], 3.15/1.57 "free": [], 3.15/1.57 "exprvars": [] 3.15/1.57 } 3.15/1.57 }, 3.15/1.57 "61": { 3.15/1.57 "goal": [{ 3.15/1.57 "clause": 0, 3.15/1.57 "scope": 2, 3.15/1.57 "term": "(f T6 T6 T6)" 3.15/1.57 }], 3.15/1.57 "kb": { 3.15/1.57 "nonunifying": [], 3.15/1.57 "intvars": {}, 3.15/1.57 "arithmetic": { 3.15/1.57 "type": "PlainIntegerRelationState", 3.15/1.57 "relations": [] 3.15/1.57 }, 3.15/1.57 "ground": ["T6"], 3.15/1.57 "free": [], 3.15/1.57 "exprvars": [] 3.15/1.57 } 3.15/1.57 }, 3.15/1.57 "type": "Nodes", 3.15/1.57 "62": { 3.15/1.57 "goal": [], 3.15/1.57 "kb": { 3.15/1.57 "nonunifying": [], 3.15/1.57 "intvars": {}, 3.15/1.57 "arithmetic": { 3.15/1.57 "type": "PlainIntegerRelationState", 3.15/1.57 "relations": [] 3.15/1.57 }, 3.15/1.57 "ground": [], 3.15/1.57 "free": [], 3.15/1.57 "exprvars": [] 3.15/1.57 } 3.15/1.57 }, 3.15/1.57 "41": { 3.15/1.57 "goal": [{ 3.15/1.57 "clause": -1, 3.15/1.57 "scope": -1, 3.15/1.57 "term": "(f T6 T6 T6)" 3.15/1.57 }], 3.15/1.57 "kb": { 3.15/1.57 "nonunifying": [], 3.15/1.57 "intvars": {}, 3.15/1.57 "arithmetic": { 3.15/1.57 "type": "PlainIntegerRelationState", 3.15/1.57 "relations": [] 3.15/1.57 }, 3.15/1.57 "ground": ["T6"], 3.15/1.57 "free": [], 3.15/1.57 "exprvars": [] 3.15/1.57 } 3.15/1.57 } 3.15/1.57 }, 3.15/1.57 "edges": [ 3.15/1.57 { 3.15/1.57 "from": 8, 3.15/1.57 "to": 25, 3.15/1.58 "label": "CASE" 3.15/1.58 }, 3.15/1.58 { 3.15/1.58 "from": 25, 3.15/1.58 "to": 41, 3.15/1.58 "label": "EVAL with clause\nf(0, 1, X3) :- f(X3, X3, X3).\nand substitutionT1 -> 0,\nT2 -> 1,\nT3 -> T6,\nX3 -> T6" 3.15/1.58 }, 3.15/1.58 { 3.15/1.58 "from": 25, 3.15/1.58 "to": 44, 3.15/1.58 "label": "EVAL-BACKTRACK" 3.15/1.58 }, 3.15/1.58 { 3.15/1.58 "from": 41, 3.15/1.58 "to": 61, 3.15/1.58 "label": "CASE" 3.15/1.58 }, 3.15/1.58 { 3.15/1.58 "from": 61, 3.15/1.58 "to": 62, 3.15/1.58 "label": "BACKTRACK\nfor clause: f(0, 1, X) :- f(X, X, X)because of non-unification" 3.15/1.58 } 3.15/1.58 ], 3.15/1.58 "type": "Graph" 3.15/1.58 } 3.15/1.58 } 3.15/1.58 3.15/1.58 ---------------------------------------- 3.15/1.58 3.15/1.58 (2) 3.15/1.58 TRUE 3.15/1.62 EOF