5.23/2.08 YES 5.23/2.10 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 5.23/2.10 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.23/2.10 5.23/2.10 5.23/2.10 Left Termination of the query pattern 5.23/2.10 5.23/2.10 flat(g,a) 5.23/2.10 5.23/2.10 w.r.t. the given Prolog program could successfully be proven: 5.23/2.10 5.23/2.10 (0) Prolog 5.23/2.10 (1) PrologToTRSTransformerProof [SOUND, 0 ms] 5.23/2.10 (2) QTRS 5.23/2.10 (3) QTRSRRRProof [EQUIVALENT, 132 ms] 5.23/2.10 (4) QTRS 5.23/2.10 (5) RisEmptyProof [EQUIVALENT, 0 ms] 5.23/2.10 (6) YES 5.23/2.10 5.23/2.10 5.23/2.10 ---------------------------------------- 5.23/2.10 5.23/2.10 (0) 5.23/2.10 Obligation: 5.23/2.10 Clauses: 5.23/2.10 5.23/2.10 right(tree(X, XS1, XS2), XS2). 5.23/2.10 flat(niltree, nil). 5.23/2.10 flat(tree(X, niltree, XS), cons(X, YS)) :- ','(right(tree(X, niltree, XS), ZS), flat(ZS, YS)). 5.23/2.10 flat(tree(X, tree(Y, YS1, YS2), XS), ZS) :- flat(tree(Y, YS1, tree(X, YS2, XS)), ZS). 5.23/2.10 5.23/2.10 5.23/2.10 Query: flat(g,a) 5.23/2.10 ---------------------------------------- 5.23/2.10 5.23/2.10 (1) PrologToTRSTransformerProof (SOUND) 5.23/2.10 Transformed Prolog program to TRS. 5.23/2.10 5.23/2.10 { 5.23/2.10 "root": 61, 5.23/2.10 "program": { 5.23/2.10 "directives": [], 5.23/2.10 "clauses": [ 5.23/2.10 [ 5.23/2.10 "(right (tree X XS1 XS2) XS2)", 5.23/2.10 null 5.23/2.10 ], 5.23/2.10 [ 5.23/2.10 "(flat (niltree) (nil))", 5.23/2.10 null 5.23/2.10 ], 5.23/2.10 [ 5.23/2.10 "(flat (tree X (niltree) XS) (cons X YS))", 5.23/2.10 "(',' (right (tree X (niltree) XS) ZS) (flat ZS YS))" 5.23/2.10 ], 5.23/2.10 [ 5.23/2.10 "(flat (tree X (tree Y YS1 YS2) XS) ZS)", 5.23/2.10 "(flat (tree Y YS1 (tree X YS2 XS)) ZS)" 5.23/2.10 ] 5.23/2.10 ] 5.23/2.10 }, 5.23/2.10 "graph": { 5.23/2.10 "nodes": { 5.23/2.10 "type": "Nodes", 5.23/2.10 "195": { 5.23/2.10 "goal": [{ 5.23/2.10 "clause": -1, 5.23/2.10 "scope": -1, 5.23/2.10 "term": "(flat (tree T38 T39 (tree T37 T40 T41)) T43)" 5.23/2.10 }], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": [ 5.23/2.10 "T37", 5.23/2.10 "T38", 5.23/2.10 "T39", 5.23/2.10 "T40", 5.23/2.10 "T41" 5.23/2.10 ], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "196": { 5.23/2.10 "goal": [], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": [], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "101": { 5.23/2.10 "goal": [{ 5.23/2.10 "clause": -1, 5.23/2.10 "scope": -1, 5.23/2.10 "term": "(flat T24 T18)" 5.23/2.10 }], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": ["T24"], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "80": { 5.23/2.10 "goal": [{ 5.23/2.10 "clause": 1, 5.23/2.10 "scope": 1, 5.23/2.10 "term": "(flat T1 T2)" 5.23/2.10 }], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": ["T1"], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "81": { 5.23/2.10 "goal": [ 5.23/2.10 { 5.23/2.10 "clause": 2, 5.23/2.10 "scope": 1, 5.23/2.10 "term": "(flat T1 T2)" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "clause": 3, 5.23/2.10 "scope": 1, 5.23/2.10 "term": "(flat T1 T2)" 5.23/2.10 } 5.23/2.10 ], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": ["T1"], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "82": { 5.23/2.10 "goal": [{ 5.23/2.10 "clause": -1, 5.23/2.10 "scope": -1, 5.23/2.10 "term": "(true)" 5.23/2.10 }], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": [], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "61": { 5.23/2.10 "goal": [{ 5.23/2.10 "clause": -1, 5.23/2.10 "scope": -1, 5.23/2.10 "term": "(flat T1 T2)" 5.23/2.10 }], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": ["T1"], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "83": { 5.23/2.10 "goal": [], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": [], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "73": { 5.23/2.10 "goal": [ 5.23/2.10 { 5.23/2.10 "clause": 1, 5.23/2.10 "scope": 1, 5.23/2.10 "term": "(flat T1 T2)" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "clause": 2, 5.23/2.10 "scope": 1, 5.23/2.10 "term": "(flat T1 T2)" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "clause": 3, 5.23/2.10 "scope": 1, 5.23/2.10 "term": "(flat T1 T2)" 5.23/2.10 } 5.23/2.10 ], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": ["T1"], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "84": { 5.23/2.10 "goal": [], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": [], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "95": { 5.23/2.10 "goal": [{ 5.23/2.10 "clause": -1, 5.23/2.10 "scope": -1, 5.23/2.10 "term": "(',' (right (tree T15 (niltree) T16) X18) (flat X18 T18))" 5.23/2.10 }], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": [ 5.23/2.10 "T15", 5.23/2.10 "T16" 5.23/2.10 ], 5.23/2.10 "free": ["X18"], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "96": { 5.23/2.10 "goal": [], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": [], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "86": { 5.23/2.10 "goal": [{ 5.23/2.10 "clause": 2, 5.23/2.10 "scope": 1, 5.23/2.10 "term": "(flat T1 T2)" 5.23/2.10 }], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": ["T1"], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "97": { 5.23/2.10 "goal": [{ 5.23/2.10 "clause": 0, 5.23/2.10 "scope": 2, 5.23/2.10 "term": "(',' (right (tree T15 (niltree) T16) X18) (flat X18 T18))" 5.23/2.10 }], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": [ 5.23/2.10 "T15", 5.23/2.10 "T16" 5.23/2.10 ], 5.23/2.10 "free": ["X18"], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "87": { 5.23/2.10 "goal": [{ 5.23/2.10 "clause": 3, 5.23/2.10 "scope": 1, 5.23/2.10 "term": "(flat T1 T2)" 5.23/2.10 }], 5.23/2.10 "kb": { 5.23/2.10 "nonunifying": [], 5.23/2.10 "intvars": {}, 5.23/2.10 "arithmetic": { 5.23/2.10 "type": "PlainIntegerRelationState", 5.23/2.10 "relations": [] 5.23/2.10 }, 5.23/2.10 "ground": ["T1"], 5.23/2.10 "free": [], 5.23/2.10 "exprvars": [] 5.23/2.10 } 5.23/2.10 } 5.23/2.10 }, 5.23/2.10 "edges": [ 5.23/2.10 { 5.23/2.10 "from": 61, 5.23/2.10 "to": 73, 5.23/2.10 "label": "CASE" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 73, 5.23/2.10 "to": 80, 5.23/2.10 "label": "PARALLEL" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 73, 5.23/2.10 "to": 81, 5.23/2.10 "label": "PARALLEL" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 80, 5.23/2.10 "to": 82, 5.23/2.10 "label": "EVAL with clause\nflat(niltree, nil).\nand substitutionT1 -> niltree,\nT2 -> nil" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 80, 5.23/2.10 "to": 83, 5.23/2.10 "label": "EVAL-BACKTRACK" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 81, 5.23/2.10 "to": 86, 5.23/2.10 "label": "PARALLEL" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 81, 5.23/2.10 "to": 87, 5.23/2.10 "label": "PARALLEL" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 82, 5.23/2.10 "to": 84, 5.23/2.10 "label": "SUCCESS" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 86, 5.23/2.10 "to": 95, 5.23/2.10 "label": "EVAL with clause\nflat(tree(X15, niltree, X16), cons(X15, X17)) :- ','(right(tree(X15, niltree, X16), X18), flat(X18, X17)).\nand substitutionX15 -> T15,\nX16 -> T16,\nT1 -> tree(T15, niltree, T16),\nX17 -> T18,\nT2 -> cons(T15, T18),\nT17 -> T18" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 86, 5.23/2.10 "to": 96, 5.23/2.10 "label": "EVAL-BACKTRACK" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 87, 5.23/2.10 "to": 195, 5.23/2.10 "label": "EVAL with clause\nflat(tree(X40, tree(X41, X42, X43), X44), X45) :- flat(tree(X41, X42, tree(X40, X43, X44)), X45).\nand substitutionX40 -> T37,\nX41 -> T38,\nX42 -> T39,\nX43 -> T40,\nX44 -> T41,\nT1 -> tree(T37, tree(T38, T39, T40), T41),\nT2 -> T43,\nX45 -> T43,\nT42 -> T43" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 87, 5.23/2.10 "to": 196, 5.23/2.10 "label": "EVAL-BACKTRACK" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 95, 5.23/2.10 "to": 97, 5.23/2.10 "label": "CASE" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 97, 5.23/2.10 "to": 101, 5.23/2.10 "label": "ONLY EVAL with clause\nright(tree(X25, X26, X27), X27).\nand substitutionT15 -> T23,\nX25 -> T23,\nX26 -> niltree,\nT16 -> T24,\nX27 -> T24,\nX18 -> T24" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 101, 5.23/2.10 "to": 61, 5.23/2.10 "label": "INSTANCE with matching:\nT1 -> T24\nT2 -> T18" 5.23/2.10 }, 5.23/2.10 { 5.23/2.10 "from": 195, 5.23/2.10 "to": 61, 5.23/2.10 "label": "INSTANCE with matching:\nT1 -> tree(T38, T39, tree(T37, T40, T41))\nT2 -> T43" 5.23/2.10 } 5.23/2.10 ], 5.23/2.10 "type": "Graph" 5.23/2.10 } 5.23/2.10 } 5.23/2.10 5.23/2.10 ---------------------------------------- 5.23/2.10 5.23/2.10 (2) 5.23/2.10 Obligation: 5.23/2.10 Q restricted rewrite system: 5.23/2.10 The TRS R consists of the following rules: 5.23/2.10 5.23/2.10 f61_in(niltree) -> f61_out1(nil) 5.23/2.10 f61_in(tree(T23, niltree, T24)) -> U1(f61_in(T24), tree(T23, niltree, T24)) 5.23/2.10 U1(f61_out1(T18), tree(T23, niltree, T24)) -> f61_out1(cons(T23, T18)) 5.23/2.10 f61_in(tree(T37, tree(T38, T39, T40), T41)) -> U2(f61_in(tree(T38, T39, tree(T37, T40, T41))), tree(T37, tree(T38, T39, T40), T41)) 5.23/2.10 U2(f61_out1(T43), tree(T37, tree(T38, T39, T40), T41)) -> f61_out1(T43) 5.23/2.10 5.23/2.10 Q is empty. 5.23/2.10 5.23/2.10 ---------------------------------------- 5.23/2.10 5.23/2.10 (3) QTRSRRRProof (EQUIVALENT) 5.23/2.10 Used ordering: 5.23/2.10 Quasi precedence: 5.23/2.10 [f61_in_1, nil] > niltree > tree_3 5.23/2.10 [f61_in_1, nil] > [U1_2, cons_2] > f61_out1_1 5.23/2.10 [f61_in_1, nil] > U2_2 5.23/2.10 5.23/2.10 5.23/2.10 Status: 5.23/2.10 f61_in_1: [1] 5.23/2.10 niltree: multiset status 5.23/2.10 f61_out1_1: multiset status 5.23/2.10 nil: multiset status 5.23/2.10 tree_3: [2,3,1] 5.23/2.10 U1_2: multiset status 5.23/2.10 cons_2: multiset status 5.23/2.10 U2_2: multiset status 5.23/2.10 5.23/2.10 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 5.23/2.10 5.23/2.10 f61_in(niltree) -> f61_out1(nil) 5.23/2.10 f61_in(tree(T23, niltree, T24)) -> U1(f61_in(T24), tree(T23, niltree, T24)) 5.23/2.10 U1(f61_out1(T18), tree(T23, niltree, T24)) -> f61_out1(cons(T23, T18)) 5.23/2.10 f61_in(tree(T37, tree(T38, T39, T40), T41)) -> U2(f61_in(tree(T38, T39, tree(T37, T40, T41))), tree(T37, tree(T38, T39, T40), T41)) 5.23/2.10 U2(f61_out1(T43), tree(T37, tree(T38, T39, T40), T41)) -> f61_out1(T43) 5.23/2.10 5.23/2.10 5.23/2.10 5.23/2.10 5.23/2.10 ---------------------------------------- 5.23/2.10 5.23/2.10 (4) 5.23/2.10 Obligation: 5.23/2.10 Q restricted rewrite system: 5.23/2.10 R is empty. 5.23/2.10 Q is empty. 5.23/2.10 5.23/2.10 ---------------------------------------- 5.23/2.10 5.23/2.10 (5) RisEmptyProof (EQUIVALENT) 5.23/2.10 The TRS R is empty. Hence, termination is trivially proven. 5.23/2.10 ---------------------------------------- 5.23/2.10 5.23/2.10 (6) 5.23/2.10 YES 5.23/2.13 EOF