3.30/1.71 YES 3.63/1.74 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 3.63/1.74 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.63/1.74 3.63/1.74 3.63/1.74 Left Termination of the query pattern 3.63/1.74 3.63/1.74 fold(g,g,a) 3.63/1.74 3.63/1.74 w.r.t. the given Prolog program could successfully be proven: 3.63/1.74 3.63/1.74 (0) Prolog 3.63/1.74 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 3.63/1.74 (2) TRIPLES 3.63/1.74 (3) TriplesToPiDPProof [SOUND, 0 ms] 3.63/1.74 (4) PiDP 3.63/1.74 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 3.63/1.74 (6) TRUE 3.63/1.74 3.63/1.74 3.63/1.74 ---------------------------------------- 3.63/1.74 3.63/1.74 (0) 3.63/1.74 Obligation: 3.63/1.74 Clauses: 3.63/1.74 3.63/1.74 fold(X, .(Y, Ys), Z) :- ','(myop(X, Y, V), fold(V, Ys, Z)). 3.63/1.74 fold(X, [], X). 3.63/1.74 myop(a, b, c). 3.63/1.74 3.63/1.74 3.63/1.74 Query: fold(g,g,a) 3.63/1.74 ---------------------------------------- 3.63/1.74 3.63/1.74 (1) PrologToDTProblemTransformerProof (SOUND) 3.63/1.74 Built DT problem from termination graph DT10. 3.63/1.74 3.63/1.74 { 3.63/1.74 "root": 70, 3.63/1.74 "program": { 3.63/1.74 "directives": [], 3.63/1.74 "clauses": [ 3.63/1.74 [ 3.63/1.74 "(fold X (. Y Ys) Z)", 3.63/1.74 "(',' (myop X Y V) (fold V Ys Z))" 3.63/1.74 ], 3.63/1.74 [ 3.63/1.74 "(fold X ([]) X)", 3.63/1.74 null 3.63/1.74 ], 3.63/1.74 [ 3.63/1.74 "(myop (a) (b) (c))", 3.63/1.74 null 3.63/1.74 ] 3.63/1.74 ] 3.63/1.74 }, 3.63/1.74 "graph": { 3.63/1.74 "nodes": { 3.63/1.74 "170": { 3.63/1.74 "goal": [], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "171": { 3.63/1.74 "goal": [], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "type": "Nodes", 3.63/1.74 "143": { 3.63/1.74 "goal": [ 3.63/1.74 { 3.63/1.74 "clause": -1, 3.63/1.74 "scope": -1, 3.63/1.74 "term": "(',' (myop T8 T9 X9) (fold X9 T10 T12))" 3.63/1.74 }, 3.63/1.74 { 3.63/1.74 "clause": 1, 3.63/1.74 "scope": 1, 3.63/1.74 "term": "(fold T8 (. T9 T10) T3)" 3.63/1.74 } 3.63/1.74 ], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [ 3.63/1.74 "T8", 3.63/1.74 "T9", 3.63/1.74 "T10" 3.63/1.74 ], 3.63/1.74 "free": ["X9"], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "144": { 3.63/1.74 "goal": [{ 3.63/1.74 "clause": 1, 3.63/1.74 "scope": 1, 3.63/1.74 "term": "(fold T1 T2 T3)" 3.63/1.74 }], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [[ 3.63/1.74 "(fold T1 T2 T3)", 3.63/1.74 "(fold X5 (. X6 X7) X8)" 3.63/1.74 ]], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [ 3.63/1.74 "T1", 3.63/1.74 "T2" 3.63/1.74 ], 3.63/1.74 "free": [ 3.63/1.74 "X5", 3.63/1.74 "X6", 3.63/1.74 "X7", 3.63/1.74 "X8" 3.63/1.74 ], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "145": { 3.63/1.74 "goal": [ 3.63/1.74 { 3.63/1.74 "clause": 2, 3.63/1.74 "scope": 2, 3.63/1.74 "term": "(',' (myop T8 T9 X9) (fold X9 T10 T12))" 3.63/1.74 }, 3.63/1.74 { 3.63/1.74 "clause": -1, 3.63/1.74 "scope": 2, 3.63/1.74 "term": null 3.63/1.74 }, 3.63/1.74 { 3.63/1.74 "clause": 1, 3.63/1.74 "scope": 1, 3.63/1.74 "term": "(fold T8 (. T9 T10) T3)" 3.63/1.74 } 3.63/1.74 ], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [ 3.63/1.74 "T8", 3.63/1.74 "T9", 3.63/1.74 "T10" 3.63/1.74 ], 3.63/1.74 "free": ["X9"], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "167": { 3.63/1.74 "goal": [{ 3.63/1.74 "clause": 1, 3.63/1.74 "scope": 1, 3.63/1.74 "term": "(fold T8 (. T9 T10) T3)" 3.63/1.74 }], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [ 3.63/1.74 "T8", 3.63/1.74 "T9", 3.63/1.74 "T10" 3.63/1.74 ], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "146": { 3.63/1.74 "goal": [{ 3.63/1.74 "clause": 2, 3.63/1.74 "scope": 2, 3.63/1.74 "term": "(',' (myop T8 T9 X9) (fold X9 T10 T12))" 3.63/1.74 }], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [ 3.63/1.74 "T8", 3.63/1.74 "T9", 3.63/1.74 "T10" 3.63/1.74 ], 3.63/1.74 "free": ["X9"], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "168": { 3.63/1.74 "goal": [], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "147": { 3.63/1.74 "goal": [ 3.63/1.74 { 3.63/1.74 "clause": -1, 3.63/1.74 "scope": 2, 3.63/1.74 "term": null 3.63/1.74 }, 3.63/1.74 { 3.63/1.74 "clause": 1, 3.63/1.74 "scope": 1, 3.63/1.74 "term": "(fold T8 (. T9 T10) T3)" 3.63/1.74 } 3.63/1.74 ], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [ 3.63/1.74 "T8", 3.63/1.74 "T9", 3.63/1.74 "T10" 3.63/1.74 ], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "169": { 3.63/1.74 "goal": [{ 3.63/1.74 "clause": -1, 3.63/1.74 "scope": -1, 3.63/1.74 "term": "(true)" 3.63/1.74 }], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "148": { 3.63/1.74 "goal": [{ 3.63/1.74 "clause": -1, 3.63/1.74 "scope": -1, 3.63/1.74 "term": "(fold (c) T10 T12)" 3.63/1.74 }], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": ["T10"], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "149": { 3.63/1.74 "goal": [], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "70": { 3.63/1.74 "goal": [{ 3.63/1.74 "clause": -1, 3.63/1.74 "scope": -1, 3.63/1.74 "term": "(fold T1 T2 T3)" 3.63/1.74 }], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [ 3.63/1.74 "T1", 3.63/1.74 "T2" 3.63/1.74 ], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "71": { 3.63/1.74 "goal": [ 3.63/1.74 { 3.63/1.74 "clause": 0, 3.63/1.74 "scope": 1, 3.63/1.74 "term": "(fold T1 T2 T3)" 3.63/1.74 }, 3.63/1.74 { 3.63/1.74 "clause": 1, 3.63/1.74 "scope": 1, 3.63/1.74 "term": "(fold T1 T2 T3)" 3.63/1.74 } 3.63/1.74 ], 3.63/1.74 "kb": { 3.63/1.74 "nonunifying": [], 3.63/1.74 "intvars": {}, 3.63/1.74 "arithmetic": { 3.63/1.74 "type": "PlainIntegerRelationState", 3.63/1.74 "relations": [] 3.63/1.74 }, 3.63/1.74 "ground": [ 3.63/1.74 "T1", 3.63/1.74 "T2" 3.63/1.74 ], 3.63/1.74 "free": [], 3.63/1.74 "exprvars": [] 3.63/1.74 } 3.63/1.74 } 3.63/1.74 }, 3.63/1.74 "edges": [ 3.63/1.74 { 3.63/1.74 "from": 70, 3.63/1.74 "to": 71, 3.63/1.74 "label": "CASE" 3.63/1.74 }, 3.63/1.74 { 3.63/1.74 "from": 71, 3.63/1.74 "to": 143, 3.63/1.74 "label": "EVAL with clause\nfold(X5, .(X6, X7), X8) :- ','(myop(X5, X6, X9), fold(X9, X7, X8)).\nand substitutionT1 -> T8,\nX5 -> T8,\nX6 -> T9,\nX7 -> T10,\nT2 -> .(T9, T10),\nT3 -> T12,\nX8 -> T12,\nT11 -> T12" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 71, 3.63/1.75 "to": 144, 3.63/1.75 "label": "EVAL-BACKTRACK" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 143, 3.63/1.75 "to": 145, 3.63/1.75 "label": "CASE" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 144, 3.63/1.75 "to": 169, 3.63/1.75 "label": "EVAL with clause\nfold(X17, [], X17).\nand substitutionT1 -> T18,\nX17 -> T18,\nT2 -> [],\nT3 -> T18" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 144, 3.63/1.75 "to": 170, 3.63/1.75 "label": "EVAL-BACKTRACK" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 145, 3.63/1.75 "to": 146, 3.63/1.75 "label": "PARALLEL" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 145, 3.63/1.75 "to": 147, 3.63/1.75 "label": "PARALLEL" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 146, 3.63/1.75 "to": 148, 3.63/1.75 "label": "EVAL with clause\nmyop(a, b, c).\nand substitutionT8 -> a,\nT9 -> b,\nX9 -> c" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 146, 3.63/1.75 "to": 149, 3.63/1.75 "label": "EVAL-BACKTRACK" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 147, 3.63/1.75 "to": 167, 3.63/1.75 "label": "FAILURE" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 148, 3.63/1.75 "to": 70, 3.63/1.75 "label": "INSTANCE with matching:\nT1 -> c\nT2 -> T10\nT3 -> T12" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 167, 3.63/1.75 "to": 168, 3.63/1.75 "label": "BACKTRACK\nfor clause: fold(X, [], X)because of non-unification" 3.63/1.75 }, 3.63/1.75 { 3.63/1.75 "from": 169, 3.63/1.75 "to": 171, 3.63/1.75 "label": "SUCCESS" 3.63/1.75 } 3.63/1.75 ], 3.63/1.75 "type": "Graph" 3.63/1.75 } 3.63/1.75 } 3.63/1.75 3.63/1.75 ---------------------------------------- 3.63/1.75 3.63/1.75 (2) 3.63/1.75 Obligation: 3.63/1.75 Triples: 3.63/1.75 3.63/1.75 foldA(a, .(b, X1), X2) :- foldA(c, X1, X2). 3.63/1.75 3.63/1.75 Clauses: 3.63/1.75 3.63/1.75 foldcA(a, .(b, X1), X2) :- foldcA(c, X1, X2). 3.63/1.75 foldcA(X1, [], X1). 3.63/1.75 3.63/1.75 Afs: 3.63/1.75 3.63/1.75 foldA(x1, x2, x3) = foldA(x1, x2) 3.63/1.75 3.63/1.75 3.63/1.75 ---------------------------------------- 3.63/1.75 3.63/1.75 (3) TriplesToPiDPProof (SOUND) 3.63/1.75 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 3.63/1.75 3.63/1.75 foldA_in_3: (b,b,f) 3.63/1.75 3.63/1.75 Transforming TRIPLES into the following Term Rewriting System: 3.63/1.75 3.63/1.75 Pi DP problem: 3.63/1.75 The TRS P consists of the following rules: 3.63/1.75 3.63/1.75 FOLDA_IN_GGA(a, .(b, X1), X2) -> U1_GGA(X1, X2, foldA_in_gga(c, X1, X2)) 3.63/1.75 FOLDA_IN_GGA(a, .(b, X1), X2) -> FOLDA_IN_GGA(c, X1, X2) 3.63/1.75 3.63/1.75 R is empty. 3.63/1.75 The argument filtering Pi contains the following mapping: 3.63/1.75 foldA_in_gga(x1, x2, x3) = foldA_in_gga(x1, x2) 3.63/1.75 3.63/1.75 a = a 3.63/1.75 3.63/1.75 .(x1, x2) = .(x1, x2) 3.63/1.75 3.63/1.75 b = b 3.63/1.75 3.63/1.75 c = c 3.63/1.75 3.63/1.75 FOLDA_IN_GGA(x1, x2, x3) = FOLDA_IN_GGA(x1, x2) 3.63/1.75 3.63/1.75 U1_GGA(x1, x2, x3) = U1_GGA(x1, x3) 3.63/1.75 3.63/1.75 3.63/1.75 We have to consider all (P,R,Pi)-chains 3.63/1.75 3.63/1.75 3.63/1.75 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 3.63/1.75 3.63/1.75 3.63/1.75 3.63/1.75 ---------------------------------------- 3.63/1.75 3.63/1.75 (4) 3.63/1.75 Obligation: 3.63/1.75 Pi DP problem: 3.63/1.75 The TRS P consists of the following rules: 3.63/1.75 3.63/1.75 FOLDA_IN_GGA(a, .(b, X1), X2) -> U1_GGA(X1, X2, foldA_in_gga(c, X1, X2)) 3.63/1.75 FOLDA_IN_GGA(a, .(b, X1), X2) -> FOLDA_IN_GGA(c, X1, X2) 3.63/1.75 3.63/1.75 R is empty. 3.63/1.75 The argument filtering Pi contains the following mapping: 3.63/1.75 foldA_in_gga(x1, x2, x3) = foldA_in_gga(x1, x2) 3.63/1.75 3.63/1.75 a = a 3.63/1.75 3.63/1.75 .(x1, x2) = .(x1, x2) 3.63/1.75 3.63/1.75 b = b 3.63/1.75 3.63/1.75 c = c 3.63/1.75 3.63/1.75 FOLDA_IN_GGA(x1, x2, x3) = FOLDA_IN_GGA(x1, x2) 3.63/1.75 3.63/1.75 U1_GGA(x1, x2, x3) = U1_GGA(x1, x3) 3.63/1.75 3.63/1.75 3.63/1.75 We have to consider all (P,R,Pi)-chains 3.63/1.75 ---------------------------------------- 3.63/1.75 3.63/1.75 (5) DependencyGraphProof (EQUIVALENT) 3.63/1.75 The approximation of the Dependency Graph [LOPSTR] contains 0 SCCs with 2 less nodes. 3.63/1.75 ---------------------------------------- 3.63/1.75 3.63/1.75 (6) 3.63/1.75 TRUE 3.63/1.78 EOF