Guided by an analogy between the logic of truth and the logic of a rationally choosing agent, I propose for the latter a principle of acyclicity, which blocks paradoxical self-referring reasoning. Certain decision-theoretic paradoxes are used to illustrate what can happen when acyclicity is violated. The principle, however, is argued for directly on grounds of coherence. Among its consequences are certain decision-theoretic rules, as well as a guiding line for setting Bayesian prior probabilities. From this perspective I discuss in the last two sections Prisoner's Dilemma and Newcomb's Paradox.

Datalogis the language of logic programs without function symbols.It is used as a database query language.If it is possible to eliminate recursion from a Datalog program F', then t' is said to be bounded.It is shown that the problem of deciding whether a given Datalog program is bounded is undecidable, even for linear programs (i.e., programs in which each rule contains at most one occurrence of a recursive predicate).It is then shown that every semantic property of Datalog programs is undecidable if it is stable, is strongly nontrivial, and contains An earlier version of this work appeared under the same title in the Proceedings of the 2nd IEEE Symposium on Logic i~z Computer Science (Ithaca, N.Y.).

The problem of replaying computations of nondeterministic concurrent programs arises in contexts such as debugging and recovery. We investigate the problem for an abstract model of concurrency, which generalizes dataflow networks, processors with shared variables, and logic programming models of concurrency. We say that nondeterminism is visible if the state is determined, up to some (appropriately defined) notion of equivalence, by the external behavior. We show that if nondeterminism is visible then replay is achievable using a one-step lookahead sequential simulation algorithm. If the program has an additional monotonicity property called stability then recovery is possible without simulating the original computation, by restarting the program from a certain easily constructed state. Also, for stable programs with visible nondeterminism, a process composed of identical parallel processes has the same external behavior as each of its components. Hence high crash-failure res...

The authors develop a resolution logic that is based on direct proofs rather than on proofs by refutations. The deductive system studied has clauses as its formulas and resolution as the sole inference rule. They analyze this deductive system using a novel representation of resolution proofs, called resolution graphs, and obtain a general completeness theorem: a clause is a logical consequence of a set of clauses if and only if it is either tautological or subsumed by a clause derivable from that set. In a previous paper (proc. 16th ACM Symp. on Principles of Prog. Lang., pp.134-42, 1989), the authors developed a model-theoretic compositional semantics for logic programs and investigated the fully abstract equivalences induced by various notions of composition. They continue that study here using the proof theory of resolution logic. This proof theory gives rise to various semantics for logic programs that reflect more operational details than does the model-theoretic semantics.>

We propose a framework for discussing fully abstract compositional semantics, which exposes the interrelations between the choices of observables, compositions, and meanings. Every choice of observables and compositions determines a unique fully abstract equivalence. A semantics is fully abstract if it induces this equivalence.

Datalog is the language of logic programs without function symbols. It is used as a database query language. If it is possible to eliminate recursion from a Datalog program Π, then Π is said to be bounded. It is known that the problem of deciding whether a given Datalog program is bounded is undecidable, even for binary programs. We show here that boundedness is decidable for monadic programs, i.e., programs where the recursive predicates are monadic (the non-recursive predicates can have arbitrary arity). Underlying our results are new tools for the optimization of Datalog programs based on automata theory and logic. In particular, one of the tools we develop is a theory of two-way alternating tree automata. We also use our techniques to show that containment for monadic programs is decidable.

The basic concept underlying probability theory and statistics is a function assigning numerical values (probabilities) to events. An “event” in this context is any conceivable state of affairs including the so-called “empty event”—an a priori impossible state. Informally, events are described in everyday language (e.g. “by playing this strategy I shall win $1000 before going broke”). But in the current mathematical framework (first proposed by Kolmogoroff [Ko 1]) they are identified with subsets of some all-inclusive set Q. The family of all events constitutes a field, or σ-field, and the logical connectives ‘and’, ‘or’ and ‘not’ are translated into the set-theoretical operations of intersection, union and complementation. The points of Q can be regarded as possible worlds and an event as the set of all worlds in which it takes place. The concept of a field of sets is wide enough to accommodate all cases and to allow for a general abstract foundation of the theory. On the other hand it does not reflect distinctions that arise out of the linguistic structure which goes into the description of our events. Since events are always described in some language they can be indentified with the sentences that describe them and the probability function can be regarded as an assignment of values to sentences. The extensive accumulated knowledge concerning formal languages makes such a project feasible. The study of probability functions defined over the sentences of a rich enough formal language yields interesting insights in more than one direction. Our present approach is not an alternative to the accepted Kolmogoroff axiomatics. In fact, given some formal language L, we can consider a rich enough set, say Q, of models for L (called also in this work “worlds”) and we can associate with every sentence the set of all worlds in Q in which the sentence is true. Thus our probabilities can be considered also as measures over some field of sets. But the introduction of the language adds mathematical structure and makes for distinctions expressing basic intuitions that cannot be otherwise expressed. As an example we mention here the concept of a random sequence or, more generally, a random world, or a world which is typical to a certain probability distribution.