3.50/1.61 YES 3.50/1.63 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 3.50/1.63 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.50/1.63 3.50/1.63 3.50/1.63 Left Termination of the query pattern 3.50/1.63 3.50/1.63 plus(g,a,a) 3.50/1.63 3.50/1.63 w.r.t. the given Prolog program could successfully be proven: 3.50/1.63 3.50/1.63 (0) Prolog 3.50/1.63 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 3.50/1.63 (2) TRIPLES 3.50/1.63 (3) TriplesToPiDPProof [SOUND, 0 ms] 3.50/1.63 (4) PiDP 3.50/1.63 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 3.50/1.63 (6) PiDP 3.50/1.63 (7) PiDPToQDPProof [SOUND, 0 ms] 3.50/1.63 (8) QDP 3.50/1.63 (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] 3.50/1.63 (10) YES 3.50/1.63 3.50/1.63 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (0) 3.50/1.63 Obligation: 3.50/1.63 Clauses: 3.50/1.63 3.50/1.63 p(s(X), X). 3.50/1.63 plus(0, Y, Y). 3.50/1.63 plus(s(X), Y, s(Z)) :- ','(p(s(X), U), plus(U, Y, Z)). 3.50/1.63 3.50/1.63 3.50/1.63 Query: plus(g,a,a) 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (1) PrologToDTProblemTransformerProof (SOUND) 3.50/1.63 Built DT problem from termination graph DT10. 3.50/1.63 3.50/1.63 { 3.50/1.63 "root": 61, 3.50/1.63 "program": { 3.50/1.63 "directives": [], 3.50/1.63 "clauses": [ 3.50/1.63 [ 3.50/1.63 "(p (s X) X)", 3.50/1.63 null 3.50/1.63 ], 3.50/1.63 [ 3.50/1.63 "(plus (0) Y Y)", 3.50/1.63 null 3.50/1.63 ], 3.50/1.63 [ 3.50/1.63 "(plus (s X) Y (s Z))", 3.50/1.63 "(',' (p (s X) U) (plus U Y Z))" 3.50/1.63 ] 3.50/1.63 ] 3.50/1.63 }, 3.50/1.63 "graph": { 3.50/1.63 "nodes": { 3.50/1.63 "79": { 3.50/1.63 "goal": [ 3.50/1.63 { 3.50/1.63 "clause": -1, 3.50/1.63 "scope": -1, 3.50/1.63 "term": "(true)" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "clause": 2, 3.50/1.63 "scope": 1, 3.50/1.63 "term": "(plus (0) T2 T3)" 3.50/1.63 } 3.50/1.63 ], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": [], 3.50/1.63 "free": [], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "139": { 3.50/1.63 "goal": [{ 3.50/1.63 "clause": -1, 3.50/1.63 "scope": -1, 3.50/1.63 "term": "(',' (p (s T9) X12) (plus X12 T12 T13))" 3.50/1.63 }], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": ["T9"], 3.50/1.63 "free": ["X12"], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "80": { 3.50/1.63 "goal": [{ 3.50/1.63 "clause": 2, 3.50/1.63 "scope": 1, 3.50/1.63 "term": "(plus T1 T2 T3)" 3.50/1.63 }], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [[ 3.50/1.63 "(plus T1 T2 T3)", 3.50/1.63 "(plus (0) X2 X2)" 3.50/1.63 ]], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": ["T1"], 3.50/1.63 "free": ["X2"], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "81": { 3.50/1.63 "goal": [{ 3.50/1.63 "clause": 2, 3.50/1.63 "scope": 1, 3.50/1.63 "term": "(plus (0) T2 T3)" 3.50/1.63 }], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": [], 3.50/1.63 "free": [], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "82": { 3.50/1.63 "goal": [], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": [], 3.50/1.63 "free": [], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "61": { 3.50/1.63 "goal": [{ 3.50/1.63 "clause": -1, 3.50/1.63 "scope": -1, 3.50/1.63 "term": "(plus T1 T2 T3)" 3.50/1.63 }], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": ["T1"], 3.50/1.63 "free": [], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "type": "Nodes", 3.50/1.63 "62": { 3.50/1.63 "goal": [ 3.50/1.63 { 3.50/1.63 "clause": 1, 3.50/1.63 "scope": 1, 3.50/1.63 "term": "(plus T1 T2 T3)" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "clause": 2, 3.50/1.63 "scope": 1, 3.50/1.63 "term": "(plus T1 T2 T3)" 3.50/1.63 } 3.50/1.63 ], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": ["T1"], 3.50/1.63 "free": [], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "140": { 3.50/1.63 "goal": [], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": [], 3.50/1.63 "free": [], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "141": { 3.50/1.63 "goal": [{ 3.50/1.63 "clause": 0, 3.50/1.63 "scope": 2, 3.50/1.63 "term": "(',' (p (s T9) X12) (plus X12 T12 T13))" 3.50/1.63 }], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": ["T9"], 3.50/1.63 "free": ["X12"], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "142": { 3.50/1.63 "goal": [{ 3.50/1.63 "clause": -1, 3.50/1.63 "scope": -1, 3.50/1.63 "term": "(plus T18 T12 T13)" 3.50/1.63 }], 3.50/1.63 "kb": { 3.50/1.63 "nonunifying": [], 3.50/1.63 "intvars": {}, 3.50/1.63 "arithmetic": { 3.50/1.63 "type": "PlainIntegerRelationState", 3.50/1.63 "relations": [] 3.50/1.63 }, 3.50/1.63 "ground": ["T18"], 3.50/1.63 "free": [], 3.50/1.63 "exprvars": [] 3.50/1.63 } 3.50/1.63 } 3.50/1.63 }, 3.50/1.63 "edges": [ 3.50/1.63 { 3.50/1.63 "from": 61, 3.50/1.63 "to": 62, 3.50/1.63 "label": "CASE" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "from": 62, 3.50/1.63 "to": 79, 3.50/1.63 "label": "EVAL with clause\nplus(0, X2, X2).\nand substitutionT1 -> 0,\nT2 -> T5,\nX2 -> T5,\nT3 -> T5" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "from": 62, 3.50/1.63 "to": 80, 3.50/1.63 "label": "EVAL-BACKTRACK" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "from": 79, 3.50/1.63 "to": 81, 3.50/1.63 "label": "SUCCESS" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "from": 80, 3.50/1.63 "to": 139, 3.50/1.63 "label": "EVAL with clause\nplus(s(X9), X10, s(X11)) :- ','(p(s(X9), X12), plus(X12, X10, X11)).\nand substitutionX9 -> T9,\nT1 -> s(T9),\nT2 -> T12,\nX10 -> T12,\nX11 -> T13,\nT3 -> s(T13),\nT10 -> T12,\nT11 -> T13" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "from": 80, 3.50/1.63 "to": 140, 3.50/1.63 "label": "EVAL-BACKTRACK" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "from": 81, 3.50/1.63 "to": 82, 3.50/1.63 "label": "BACKTRACK\nfor clause: plus(s(X), Y, s(Z)) :- ','(p(s(X), U), plus(U, Y, Z))because of non-unification" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "from": 139, 3.50/1.63 "to": 141, 3.50/1.63 "label": "CASE" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "from": 141, 3.50/1.63 "to": 142, 3.50/1.63 "label": "ONLY EVAL with clause\np(s(X17), X17).\nand substitutionT9 -> T18,\nX17 -> T18,\nX12 -> T18" 3.50/1.63 }, 3.50/1.63 { 3.50/1.63 "from": 142, 3.50/1.63 "to": 61, 3.50/1.63 "label": "INSTANCE with matching:\nT1 -> T18\nT2 -> T12\nT3 -> T13" 3.50/1.63 } 3.50/1.63 ], 3.50/1.63 "type": "Graph" 3.50/1.63 } 3.50/1.63 } 3.50/1.63 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (2) 3.50/1.63 Obligation: 3.50/1.63 Triples: 3.50/1.63 3.50/1.63 plusA(s(X1), X2, s(X3)) :- plusA(X1, X2, X3). 3.50/1.63 3.50/1.63 Clauses: 3.50/1.63 3.50/1.63 pluscA(0, X1, X1). 3.50/1.63 pluscA(s(X1), X2, s(X3)) :- pluscA(X1, X2, X3). 3.50/1.63 3.50/1.63 Afs: 3.50/1.63 3.50/1.63 plusA(x1, x2, x3) = plusA(x1) 3.50/1.63 3.50/1.63 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (3) TriplesToPiDPProof (SOUND) 3.50/1.63 We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: 3.50/1.63 3.50/1.63 plusA_in_3: (b,f,f) 3.50/1.63 3.50/1.63 Transforming TRIPLES into the following Term Rewriting System: 3.50/1.63 3.50/1.63 Pi DP problem: 3.50/1.63 The TRS P consists of the following rules: 3.50/1.63 3.50/1.63 PLUSA_IN_GAA(s(X1), X2, s(X3)) -> U1_GAA(X1, X2, X3, plusA_in_gaa(X1, X2, X3)) 3.50/1.63 PLUSA_IN_GAA(s(X1), X2, s(X3)) -> PLUSA_IN_GAA(X1, X2, X3) 3.50/1.63 3.50/1.63 R is empty. 3.50/1.63 The argument filtering Pi contains the following mapping: 3.50/1.63 plusA_in_gaa(x1, x2, x3) = plusA_in_gaa(x1) 3.50/1.63 3.50/1.63 s(x1) = s(x1) 3.50/1.63 3.50/1.63 PLUSA_IN_GAA(x1, x2, x3) = PLUSA_IN_GAA(x1) 3.50/1.63 3.50/1.63 U1_GAA(x1, x2, x3, x4) = U1_GAA(x1, x4) 3.50/1.63 3.50/1.63 3.50/1.63 We have to consider all (P,R,Pi)-chains 3.50/1.63 3.50/1.63 3.50/1.63 Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES 3.50/1.63 3.50/1.63 3.50/1.63 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (4) 3.50/1.63 Obligation: 3.50/1.63 Pi DP problem: 3.50/1.63 The TRS P consists of the following rules: 3.50/1.63 3.50/1.63 PLUSA_IN_GAA(s(X1), X2, s(X3)) -> U1_GAA(X1, X2, X3, plusA_in_gaa(X1, X2, X3)) 3.50/1.63 PLUSA_IN_GAA(s(X1), X2, s(X3)) -> PLUSA_IN_GAA(X1, X2, X3) 3.50/1.63 3.50/1.63 R is empty. 3.50/1.63 The argument filtering Pi contains the following mapping: 3.50/1.63 plusA_in_gaa(x1, x2, x3) = plusA_in_gaa(x1) 3.50/1.63 3.50/1.63 s(x1) = s(x1) 3.50/1.63 3.50/1.63 PLUSA_IN_GAA(x1, x2, x3) = PLUSA_IN_GAA(x1) 3.50/1.63 3.50/1.63 U1_GAA(x1, x2, x3, x4) = U1_GAA(x1, x4) 3.50/1.63 3.50/1.63 3.50/1.63 We have to consider all (P,R,Pi)-chains 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (5) DependencyGraphProof (EQUIVALENT) 3.50/1.63 The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (6) 3.50/1.63 Obligation: 3.50/1.63 Pi DP problem: 3.50/1.63 The TRS P consists of the following rules: 3.50/1.63 3.50/1.63 PLUSA_IN_GAA(s(X1), X2, s(X3)) -> PLUSA_IN_GAA(X1, X2, X3) 3.50/1.63 3.50/1.63 R is empty. 3.50/1.63 The argument filtering Pi contains the following mapping: 3.50/1.63 s(x1) = s(x1) 3.50/1.63 3.50/1.63 PLUSA_IN_GAA(x1, x2, x3) = PLUSA_IN_GAA(x1) 3.50/1.63 3.50/1.63 3.50/1.63 We have to consider all (P,R,Pi)-chains 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (7) PiDPToQDPProof (SOUND) 3.50/1.63 Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (8) 3.50/1.63 Obligation: 3.50/1.63 Q DP problem: 3.50/1.63 The TRS P consists of the following rules: 3.50/1.63 3.50/1.63 PLUSA_IN_GAA(s(X1)) -> PLUSA_IN_GAA(X1) 3.50/1.63 3.50/1.63 R is empty. 3.50/1.63 Q is empty. 3.50/1.63 We have to consider all (P,Q,R)-chains. 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (9) QDPSizeChangeProof (EQUIVALENT) 3.50/1.63 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. 3.50/1.63 3.50/1.63 From the DPs we obtained the following set of size-change graphs: 3.50/1.63 *PLUSA_IN_GAA(s(X1)) -> PLUSA_IN_GAA(X1) 3.50/1.63 The graph contains the following edges 1 > 1 3.50/1.63 3.50/1.63 3.50/1.63 ---------------------------------------- 3.50/1.63 3.50/1.63 (10) 3.50/1.63 YES 3.74/1.67 EOF