Satisfaction systems and reductions between them are presented as an appropriate context for analyzing the satisfiability and the validity problems. The notion of reduction is generalized in order to cope with the meet-combination of logics. Reductions between satisfaction systems induce reductions between the respective satisfiability problems and (under mild conditions) also between their validity problems. Sufficient conditions are provided for relating satisfiability problems to validity problems. Reflection results for decidability in the presence of reductions are established. The validity problem in the meet-combination is proved to be decidable whenever the validity problem for the components are decidable. Several examples are discussed, namely, involving modal and intuitionistic logics, as well as the meet-combination of $\textrm {K}$ modal logic and intuitionistic logic.

Model theorists have been studying analytic functions since the late 1970s. Highlights include the seminal work of Denef and van den Dries on the theory of the p-adics with restricted analytic functions, Wilkie's proof of o-minimality of the theory of the reals with the exponential function, and the formulation of Zilber's conjecture for the complex exponential. My goal in this talk is to survey these main developments and to reflect on today's open problems, in particular for theories of valued fields.

We prove a number of elementary facts about computability in partial combinatory algebras (pca’s). We disprove a suggestion made by Kreisel about using Friedberg numberings to construct extensional pca’s. We then discuss separability and elements without total extensions. We relate this to Ershov’s notion of precompleteness, and we show that precomplete numberings are not 1–1 in general.

Invariance criteria are widely accepted as a means to demarcate the logical vocabulary of a language. In previous work, I proposed a framework of “semantic constraints” for model-theoretic consequence which does not rely on a strict distinction between logical and nonlogical terms, but rather on a range of constraints on models restricting the interpretations of terms in the language in different ways. In this paper I show how invariance criteria can be generalized so as to apply to semantic constraints on models. Some obviously unpalatable semantic constraints turn out to be invariant under isomorphisms. I shall connect the discussion to known counter-examples to invariance criteria for logical terms, and so the generalization will also shed light on the current existing debate on logicality. I analyse the failure of invariance to fulfil its role as a criterion for logicality, and argue that invariance conditions should best be thought of as merely methodological meta-constraints restricting the ways the model-theoretic apparatus should be used.

This thesis aims to develop a domain-independent system for repairing faulty Datalog-like theories by combining three existing techniques: abduction, belief revision, and conceptual change. Accordingly, the proposed system is named the ABC repair system (ABC). Given an observed assertion and a current theory, abduction adds axioms, which explain that observation by making the corresponding assertion derivable from the expanded theory. Belief revision incorporates a new piece of information which conflicts with the input theory by deleting old axioms. Conceptual change uses the reformation algorithm for blocking unwanted proofs or unblocking wanted proofs. The former two techniques change an axiom as a whole, while reformation changes the language in which the theory is written. These three techniques are complementary. But they have not previously been combined into one system. We are working on aligning these three techniques in ABC, which is capable of repairing logical theories with better result than each individual technique alone. In addition, ABC extends abduction and belief revision to operate on preconditions: the former deletes preconditions from rules, and the latter adds preconditions to rules. Datalog is used as the underlying logic of theories in this thesis, but the proposed system has the potential to be adapted to theories in other logics.

Abstract prepared by Xue Li by taking directly from the thesis.

E-mail: [email protected]