This book gives a comprehensive overview of central themes of finite model theory – expressive power, descriptive complexity, and zero-one laws – together with selected applications relating to database theory and artificial intelligence, especially constraint databases and constraint satisfaction problems. The final chapter provides a concise modern introduction to modal logic, emphasizing the continuity in spirit and technique with finite model theory. This underlying spirit involves the use of various fragments of and hierarchies within first-order, second-order, fixed-point, and infinitary logics (...) to gain insight into phenomena in complexity theory and combinatorics. The book emphasizes the use of combinatorial games, such as extensions and refinements of the Ehrenfeucht-Fraissé pebble game, as a powerful way to analyze the expressive power of such logics, and illustrates how deep notions from model theory and combinatorics, such as o-minimality and treewidth, arise naturally in the application of finite model theory to database theory and AI. Students of logic and computer science will find here the tools necessary to embark on research into finite model theory, and all readers will experience the excitement of a vibrant area of the application of logic to computer science. (shrink)

Many known tools for proving expressibility bounds for first-order logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of (...) the easiest tools for proving expressibility bounds. These results apply beyond the first-order case. We use them to derive expressibility bounds for first-order logic with unary quantifiers and counting. We also characterize the notions of locality on structures of small degree. (shrink)

Locality notions in logic say that the truth value of a formula can be determined locally, by looking at the isomorphism type of a small neighbourhood of its free variables. Such notions have proved to be useful in many applications. They all, however, refer to isomorphisms of neighbourhoods, which most local logics cannot test. A stronger notion of locality says that the truth value of a formula is determined by what the logic itself can say about that small neighbourhood. Since (...) the expressiveness of many logics can be characterized by games, one can also say that the truth value of a formula is determined by the type, with respect to a game, of that small neighbourhood. Such game-based notions of locality can often be applied when traditional isomorphism-based notions of locality cannot.Our goal is to study game-based notions of locality. We work with an abstract view of games that subsumes games for many logics. We look at three, progressively more complicated locality notions. The easiest requires only very mild conditions on the game and works for most logics of interest. The other notions, based on Hanf’s and Gaifman’s theorems, require more restrictions. We state those restrictions and give examples of logics that satisfy and fail the respective game-based notions of locality. (shrink)

Mitochondrial replacement therapy requires oocytes of women whose mitochondrial DNA will be transmitted to resultant children. These techniques are scientifically, ethically and socially controversial; it is likely that some women who donate their oocytes for general in vitro fertilisation usage would nevertheless oppose their genetic material being used in MRT. The possibility of oocytes being used in MRT is therefore relevant to oocyte donation and should be included in the consent process when applicable. In present circumstances, specific consent should be (...) obtained. However, once MRT becomes more routine, such consent could be incorporated into the general consent process for oocyte donation. The reported lack of proper consent for MRT from the oocyte donor in the first baby born via the technique is an ethical failing and should be corrected in any future practice of MRT. (shrink)

A significant proportion of conservationists' work is directed towards efforts to save disappearing species. This relies upon the belief that species extinction is undesirable. When justifications are offered for this belief, they very often rest upon the assumption that extinction brought about by humans is different in kind from other forms of extinction. This paper examines this assumption and reveals that there is indeed good reason to suppose current anthropogenic extinctions to be different in kind from extinctions brought about at (...) other times or by other factors. Having considered – and rejected – quantity and rate of extinction as useful distinguishing factors, four alternative arguments are offered, each identifying a way in which anthropogenic extinction is significantly different from other forms of extinction, even mass extinction: (1) Humans are a different kind of natural cause from other causes of extinction; (2) Extinctions brought about by humans are uniquely persistent; (3) Anthropogenic extinctions are effectively random whereas past mass extinctions are rule-bound; (4) The impact of the current anthropogenic extinction event differs from the impact of other extinction events of the past, such that future recovery may not follow past patterns. Together, these four arguments suggest that the present-day extinction event brought about by humans may be unprecedented and that we cannot clearly extrapolate from past to present recovery from extinctions. Although insufficient as justification for the claim that present-day extinctions are undesirable, the arguments provide some ammunition for conservationists' conviction that species extinction – in which humans play an accelerating role – ought to be prevented. (shrink)

This volume presents new texts of Cicero's dialogues on political philosophy, De Re Publica and De Legibus, together with corrected versions of the editor's previously published editions of Cato Maior de Senectute and Laelius de Amicitia. The texts are based on a full reconsideration of the manuscript evidence and are presented in a clear and readable form.