โ Scribed by Christos H. Papadimitriou; Mihalis Yannakakis
No coin nor oath required. For personal study only.
We address the question of when the structure of a Datalog program with negation guarantees the existence of a fixpoint. We propose a semantics of Datalog programs with negation, which we call the tie-breaking semantics. The tie-breaking semantics can be computed in polynomial time and results in a fixpoint whenever the rule-goal graph of the program has no cycle with an odd number of negative edges. We show that, in some well-defined sense, this is the most general fixpoint semantics of negation possible; in particular, we show that if a cycle with an odd number of negative edges is present, then the logic program is not structurally total, that is, it has an alphabetic variant which has no fixpoint semantics whatsoever. Determining whether a program is total is undecidable.
๐ SIMILAR VOLUMES
It has been noted on a number of occasions that the knowledge-representation structures and processing functions provided by Sowa's theory of conceptual graphs is complementary with the semantic system developed by Ray Jackendoff. Jackendoff s system, incorporating Gruber's Thematic Relations Hypoth
We show, in the context of a simple evolutionary bargaining game, that the efficiency of bargaining behavior depends crucially on the tie-breaking rule players use. For certain tie-breaking rules, and in the limit as the number of feasible demands becomes infinite, all the surplus is wasted. Ineffic
A heuristic for 0-1 integer programming is proposed that features a specific rule for breaking ties that occur when attempting to determine a variable to set to 1 during a given iteration. It is tested on a large number of smallto moderate-sized randomly generated generalized set-packing models. Sol