The model-checking problem for a logic L on a class C of structures asks whether a given L-sentence holds in a given structure in C. In this paper, we give super-exponential lower bounds for fixed-parameter tractable model-checking problems for first-order and monadic second-order logic. We show that unless PTIME=NP, the model-checking problem for monadic second-order logic on finite words is not solvable in time f·p, for any elementary function f and any polynomial p. Here k denotes the size of the (...) input sentence and n the size of the input word. We establish a number of similar lower bounds for the model-checking problem for first-order logic, for example, on the class of all trees. (shrink)
Originally published in 1941, this book contains the French text of Jean-Jacques Rousseau's 1755 treatise Discours sur l'origine et les fondements de l'inégalité parmi les hommes, in which he examines the artificial origins of human social structures designed to keep one group elevated above another. The preface by F. C. Green provides the historical context for Rousseau's essay and explains its influence on the authors of the French Revolution. This book will be of value to anyone with an interest in (...) French history or political philosophy. (shrink)
In this book, Professor Simu? demonstrates how Baur came to understand Christian theology as a Gnostic philosophy of religion under the influence of Böhme's unorthodox esoteric theosophy and Hegel's modern religious philosophy.
We will show that there is a strong form of emergence in cell biology. Beginning with C.D. Broad's classic discussion of emergence, we distinguish two conditions sufficient for emergence. Emergence in biology must be compatible with the thought that all explanations of systemic properties are mechanistic explanations and with their sufficiency. Explanations of systemic properties are always in terms of the properties of the parts within the system. Nonetheless, systemic properties can still be emergent. If the properties of the components (...) within the system cannot be predicted, even in principle, from the behavior of the system's parts within simpler wholes then there also will be systemic properties which cannot be predicted, even in principle, on basis of the behavior of these parts. We show in an explicit case study drawn from molecular cell physiology that biochemical networks display this kind of emergence, even though they deploy only mechanistic explanations. This illustrates emergence and its place in nature. (shrink)