3.44/1.73 YES 3.44/1.74 proof of /export/starexec/sandbox/benchmark/theBenchmark.pl 3.44/1.74 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.44/1.74 3.44/1.74 3.44/1.74 Left Termination of the query pattern 3.44/1.74 3.44/1.74 map(a) 3.44/1.74 3.44/1.74 w.r.t. the given Prolog program could successfully be proven: 3.44/1.74 3.44/1.74 (0) Prolog 3.44/1.74 (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] 3.44/1.74 (2) TRIPLES 3.44/1.74 (3) TPisEmptyProof [EQUIVALENT, 0 ms] 3.44/1.74 (4) YES 3.44/1.74 3.44/1.74 3.44/1.74 ---------------------------------------- 3.44/1.74 3.44/1.74 (0) 3.44/1.74 Obligation: 3.44/1.74 Clauses: 3.44/1.74 3.44/1.74 color_map([], X1). 3.44/1.74 color_map(.(Region, Regions), Colors) :- ','(color_region(Region, Colors), color_map(Regions, Colors)). 3.44/1.74 color_region(region(X2, Color, Neighbors), Colors) :- ','(select(Color, Colors, Colors1), subset(Neighbors, Colors1)). 3.44/1.74 select(X, .(X, Xs), Xs). 3.44/1.74 select(X, .(Y, Xs), .(Y, Zs)) :- select(X, Xs, Zs). 3.44/1.74 subset([], X3). 3.44/1.74 subset(.(X, Xs), Ys) :- ','(member(X, Ys), subset(Xs, Ys)). 3.44/1.74 member(X, .(X, X4)). 3.44/1.74 member(X, .(X5, Xs)) :- member(X, Xs). 3.44/1.74 map(.(region(belize, Belize, .(Guatemala, [])), .(region(guatemala, Guatemala, .(Belize, .(El_Salvador, .(Honduras, [])))), .(region(el_salvador, El_Salvador, .(Guatemala, .(Honduras, []))), .(region(honduras, Honduras, .(Guatemala, .(El_Salvador, .(Nicaragua, [])))), .(region(nicaragua, Nicaragua, .(Honduras, .(Costa_rica, []))), .(region(costa_rica, Costa_rica, .(Nicaragua, .(Panama, []))), .(region(panama, Panama, .(Costa_rica, [])), [])))))))). 3.44/1.74 query :- ','(map(X), color_map(X, .(red, .(blue, .(green, []))))). 3.44/1.74 3.44/1.74 3.44/1.74 Query: map(a) 3.44/1.74 ---------------------------------------- 3.44/1.74 3.44/1.74 (1) PrologToDTProblemTransformerProof (SOUND) 3.44/1.74 Built DT problem from termination graph DT10. 3.44/1.74 3.44/1.74 { 3.44/1.74 "root": 3, 3.44/1.74 "program": { 3.44/1.74 "directives": [], 3.44/1.74 "clauses": [ 3.44/1.74 [ 3.44/1.74 "(color_map ([]) X1)", 3.44/1.74 null 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(color_map (. Region Regions) Colors)", 3.44/1.74 "(',' (color_region Region Colors) (color_map Regions Colors))" 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(color_region (region X2 Color Neighbors) Colors)", 3.44/1.74 "(',' (select Color Colors Colors1) (subset Neighbors Colors1))" 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(select X (. X Xs) Xs)", 3.44/1.74 null 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(select X (. Y Xs) (. Y Zs))", 3.44/1.74 "(select X Xs Zs)" 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(subset ([]) X3)", 3.44/1.74 null 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(subset (. X Xs) Ys)", 3.44/1.74 "(',' (member X Ys) (subset Xs Ys))" 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(member X (. X X4))", 3.44/1.74 null 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(member X (. X5 Xs))", 3.44/1.74 "(member X Xs)" 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(map (. (region (belize) Belize (. Guatemala ([]))) (. (region (guatemala) Guatemala (. Belize (. El_Salvador (. Honduras ([]))))) (. (region (el_salvador) El_Salvador (. Guatemala (. Honduras ([])))) (. (region (honduras) Honduras (. Guatemala (. El_Salvador (. Nicaragua ([]))))) (. (region (nicaragua) Nicaragua (. Honduras (. Costa_rica ([])))) (. (region (costa_rica) Costa_rica (. Nicaragua (. Panama ([])))) (. (region (panama) Panama (. Costa_rica ([]))) ([])))))))))", 3.44/1.74 null 3.44/1.74 ], 3.44/1.74 [ 3.44/1.74 "(query)", 3.44/1.74 "(',' (map X) (color_map X (. (red) (. (blue) (. (green) ([]))))))" 3.44/1.74 ] 3.44/1.74 ] 3.44/1.74 }, 3.44/1.74 "graph": { 3.44/1.74 "nodes": { 3.44/1.74 "24": { 3.44/1.74 "goal": [{ 3.44/1.74 "clause": 9, 3.44/1.74 "scope": 1, 3.44/1.74 "term": "(map T1)" 3.44/1.74 }], 3.44/1.74 "kb": { 3.44/1.74 "nonunifying": [], 3.44/1.74 "intvars": {}, 3.44/1.74 "arithmetic": { 3.44/1.74 "type": "PlainIntegerRelationState", 3.44/1.74 "relations": [] 3.44/1.74 }, 3.44/1.74 "ground": [], 3.44/1.74 "free": [], 3.44/1.74 "exprvars": [] 3.44/1.74 } 3.44/1.74 }, 3.44/1.74 "3": { 3.44/1.74 "goal": [{ 3.44/1.74 "clause": -1, 3.44/1.74 "scope": -1, 3.44/1.74 "term": "(map T1)" 3.44/1.74 }], 3.44/1.74 "kb": { 3.44/1.74 "nonunifying": [], 3.44/1.74 "intvars": {}, 3.44/1.74 "arithmetic": { 3.44/1.74 "type": "PlainIntegerRelationState", 3.44/1.74 "relations": [] 3.44/1.74 }, 3.44/1.74 "ground": [], 3.44/1.74 "free": [], 3.44/1.74 "exprvars": [] 3.44/1.74 } 3.44/1.74 }, 3.44/1.74 "type": "Nodes", 3.44/1.74 "51": { 3.44/1.74 "goal": [{ 3.44/1.74 "clause": -1, 3.44/1.74 "scope": -1, 3.44/1.74 "term": "(true)" 3.44/1.74 }], 3.44/1.74 "kb": { 3.44/1.74 "nonunifying": [], 3.44/1.74 "intvars": {}, 3.44/1.74 "arithmetic": { 3.44/1.74 "type": "PlainIntegerRelationState", 3.44/1.74 "relations": [] 3.44/1.74 }, 3.44/1.74 "ground": [], 3.44/1.74 "free": [], 3.44/1.74 "exprvars": [] 3.44/1.74 } 3.44/1.74 }, 3.44/1.74 "52": { 3.44/1.74 "goal": [], 3.44/1.74 "kb": { 3.44/1.74 "nonunifying": [], 3.44/1.74 "intvars": {}, 3.44/1.74 "arithmetic": { 3.44/1.74 "type": "PlainIntegerRelationState", 3.44/1.74 "relations": [] 3.44/1.74 }, 3.44/1.74 "ground": [], 3.44/1.74 "free": [], 3.44/1.74 "exprvars": [] 3.44/1.74 } 3.44/1.74 }, 3.44/1.74 "53": { 3.44/1.74 "goal": [], 3.44/1.74 "kb": { 3.44/1.74 "nonunifying": [], 3.44/1.74 "intvars": {}, 3.44/1.74 "arithmetic": { 3.44/1.74 "type": "PlainIntegerRelationState", 3.44/1.74 "relations": [] 3.44/1.74 }, 3.44/1.74 "ground": [], 3.44/1.74 "free": [], 3.44/1.74 "exprvars": [] 3.44/1.74 } 3.44/1.74 } 3.44/1.74 }, 3.44/1.74 "edges": [ 3.44/1.74 { 3.44/1.74 "from": 3, 3.44/1.74 "to": 24, 3.44/1.74 "label": "CASE" 3.44/1.74 }, 3.44/1.74 { 3.44/1.74 "from": 24, 3.44/1.74 "to": 51, 3.44/1.74 "label": "EVAL with clause\nmap(.(region(belize, X13, .(X14, [])), .(region(guatemala, X14, .(X13, .(X15, .(X16, [])))), .(region(el_salvador, X15, .(X14, .(X16, []))), .(region(honduras, X16, .(X14, .(X15, .(X17, [])))), .(region(nicaragua, X17, .(X16, .(X18, []))), .(region(costa_rica, X18, .(X17, .(X19, []))), .(region(panama, X19, .(X18, [])), [])))))))).\nand substitutionX13 -> T9,\nX14 -> T10,\nX15 -> T11,\nX16 -> T12,\nX17 -> T13,\nX18 -> T14,\nX19 -> T15,\nT1 -> .(region(belize, T9, .(T10, [])), .(region(guatemala, T10, .(T9, .(T11, .(T12, [])))), .(region(el_salvador, T11, .(T10, .(T12, []))), .(region(honduras, T12, .(T10, .(T11, .(T13, [])))), .(region(nicaragua, T13, .(T12, .(T14, []))), .(region(costa_rica, T14, .(T13, .(T15, []))), .(region(panama, T15, .(T14, [])), [])))))))" 3.44/1.74 }, 3.44/1.74 { 3.44/1.74 "from": 24, 3.44/1.74 "to": 52, 3.44/1.74 "label": "EVAL-BACKTRACK" 3.44/1.74 }, 3.44/1.74 { 3.44/1.74 "from": 51, 3.44/1.74 "to": 53, 3.44/1.74 "label": "SUCCESS" 3.44/1.74 } 3.44/1.74 ], 3.44/1.74 "type": "Graph" 3.44/1.74 } 3.44/1.74 } 3.44/1.74 3.44/1.74 ---------------------------------------- 3.44/1.74 3.44/1.74 (2) 3.44/1.74 Obligation: 3.44/1.74 Triples: 3.44/1.74 3.44/1.74 3.44/1.74 Clauses: 3.44/1.74 3.44/1.74 3.44/1.74 Afs: 3.44/1.74 3.44/1.74 3.44/1.74 ---------------------------------------- 3.44/1.74 3.44/1.74 (3) TPisEmptyProof (EQUIVALENT) 3.44/1.74 There are no more dependency triples. Hence, the dependency triple problem trivially terminates. 3.44/1.74 ---------------------------------------- 3.44/1.74 3.44/1.74 (4) 3.44/1.74 YES 3.65/1.77 EOF