Figure 1: A pr ototyp ical exa mple of a three-layer feed forward network, used by Plunkett and M archm an (1 991 ) to simulate learning the past-tense of En glish verbs. The inpu t units encode representations of the three phonemes of the present tense of the artificial words used in this simulation. Th e netwo rk is trained to produce a representation of the phonemes employed in the past tense form and the suffix (/d/, /ed/, or /t/) (...) used on regular verbs. To run the network, each input unit is assigned an activation value o f 0 or 1 , dep ending on whethe r the featu re is present or not. Eac h input unit is conne cted to each of the 30 hidden units by a we ighted conn ection and p rovid es an inp ut to each hidden unit equal to the product of the input unit's activation and the weight. Each hidd en unit's activation is then determined by summing ov er the va lues co ming fro m each inp ut unit to deter mine a netinput, and then applying a non-linear function (e.g., the logistic function 1/(1+e^netinput). Th is whole proced ure is. (shrink)

Diatoms are a species‐rich group of photosynthetic eukaryotes, with enormous ecological significance and great potential for biotechnology. During the last decade, diatoms have begun to be studied intensively using modern molecular techniques and the genomes of four diatoms have been wholly or partially sequenced. Although new insights into the biology and evolution of diatoms are accumulating rapidly due to the availability of reverse genetic tools, the full potential of these molecular biological approaches can only be fully realized if experimental control (...) of sexual crosses becomes firmly established and widely accessible to experimental biologists. Here we discuss the issue of choosing new models for diatom research, by taking into account the broader context of diatom mating systems and the place of sex in relation to the intricate cycle of cell size reduction and restitution that is characteristic of most diatoms. We illustrate the results of our efforts to select and develop experimental systems in diatoms, using species with typical life cycle attributes, which could be used as future model organisms to complement existing ones. BioEssays 30:692–702, 2008. © 2008 Wiley Periodicals, Inc. (shrink)

In the philosophy of science and epistemology literature, robustness analysis has become an umbrella term that refers to a variety of strategies. One of the main purposes of this paper is to argue that different strategies rely on different criteria for justifications. More specifically, I will claim that: i) robustness analysis differs from de-idealization even though the two concepts have often been conflated in the literature; ii) the comparison of different model frameworks requires different justifications than the comparison of models (...) that differ only for the assumption under test; iii) the replacement of specific assumptions with different ones can encounter specific difficulties in scientific practice. These claims will be supported by a case study in population ecology and a case study in geographical economics. (shrink)

This book aims to lay bare the logical foundations of tractable reasoning. It draws on Marvin Minsky's seminal work on frames, which has been highly influential in computer science and, to a lesser extent, in cognitive science. Only very few people have explored ideas about frames in logic, which is why the investigation in this book breaks new ground. The apparent intractability of dynamic, inferential reasoning is an unsolved problem in both cognitive science and logic-oriented artificial intelligence. By means of (...) a logical investigation of frames and frame concepts, Andreas devises a novel logic of tractable reasoning, called frame logic. Moreover, he devises a novel belief revision scheme, which is tractable for frame logic. These tractability results shed new light on our logical and cognitive means to carry out dynamic, inferential reasoning. Modularity remains central for tractability, and so the author sets forth a logical variant of the massive modularity hypothesis in cognitive science. (shrink)

We analyse the computational complexity of comparing informational structures. Intuitively, we study the complexity of deciding queries such as the following: Is Alice’s epistemic information strictly coarser than Bob’s? Do Alice and Bob have the same knowledge about each other’s knowledge? Is it possible to manipulate Alice in a way that she will have the same beliefs as Bob? The results show that these problems lie on both sides of the border between tractability (P) and intractability (NP-hard). In particular, (...) we investigate the impact of assuming information structures to be partition-based (rather than arbitrary relational structures) on the complexity of various problems. We focus on the tractability of concrete epistemic tasks and not on epistemic logics describing them. (shrink)

Lisciandra poses a challenge for robustness analysis as applied to economic models. She argues that substituting tractability assumptions risks altering the main mathematical structure of the model, thereby preventing the possibility of meaningfully evaluating the same model under different assumptions. In such cases RA is argued to be inapplicable. However, Lisciandra is mistaken to take the goal of RA as keeping the mathematical properties of tractability assumptions intact. Instead, RA really aims to keep the modeling component while varying (...) the corresponding mathematical formulation. Thus, her argument concerning whether the associated mathematical properties of certain assumptions can be kept intact is irrelevant to the success of RA. Furthermore, we explicate and develop Lloyd’s account of “model robustness” to provide solutions to Lisciandra’s challenges. Our solutions are, namely, error analysis and independent empirical support. We conclude that although complex economic models do face potential dangers, there are solutions and robustness analysis need not be given up.. (shrink)

According to the Best System Account of lawhood, laws of nature are theorems of the deductive systems that best balance simplicity and strength. In this paper, I advocate a different account of lawhood which is related, in spirit, to the BSA: according to my account, laws are theorems of deductive systems that best balance simplicity, strength, and also calculational tractability. I discuss two problems that the BSA faces, and I show that my account solves them. I also use my (...) account to illuminate the nomological character of special science laws. (shrink)

In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred interpretation, provides (...) evidence for these predictions. Experiment 2 was a picture verification task. The results show that the strong interpretation was in fact possible for tractable all but one-reciprocals, but not for exactly n. The last experiment manipulated monotonicity of the quantifier antecedents. (shrink)

This article discusses five propositions about managerial moral tractability -- that is, a morality that is amenable to the complexity of managers’ continual pressure to decide and act -- in their customer relations. The propositions come from the comparison of three case studies of different types of managers. To analyze the morality of managers, discursive practices of managers are studied. At the end of the article also some consideration is given to “information strategies” of managers, in relation to their (...) tractable morality. (shrink)

We overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, (...) to be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. -/- We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition. (shrink)

Much like admissibility is the key concept underlying preferred semantics, strong admissibility is the key concept underlying grounded semantics, as membership of a strongly admissible set is sufficient to show membership of the grounded extension. As such, strongly admissible sets and labellings can be used as an explanation of membership of the grounded extension, as is for instance done in some of the proof procedures for grounded semantics. In the current paper, we present two polynomial algorithms for constructing relatively small (...) strongly admissible labellings, with associated min–max numberings, for a particular argument. These labellings can be used as relatively small explanations for the argument’s membership of the grounded extension. Although our algorithms are not guaranteed to yield an absolute minimal strongly admissible labelling for the argument (as doing so would have implied an exponential complexity), our best performing algorithm yields results that are only marginally larger. Moreover, the runtime of this algorithm is an order of magnitude smaller than that of the existing approach for computing an absolute minimal strongly admissible labelling for a particular argument. As such, we believe that our algorithms can be of practical value in situations where the aim is to construct a minimal or near-minimal strongly admissible labelling in a time-efficient way. (shrink)

This article discusses five propositions about managerial moral tractability - that is, a morality that is amenable to the complexity of managers' continual pressure to decide and act - in their customer relations. The propositions come from the comparison of three case studies of different types of managers. To analyze the morality of managers, discursive practices of managers are studied. At the end of the article also some consideration is given to "information strategies" of managers, in relation to their (...) tractable morality. (shrink)

According to Church’s thesis, we can identify the intuitive concept of effective computability with such well-defined mathematical concepts as Turing computability and partial recursiveness. The almost universal acceptance of Church’s thesis among logicians and computer scientists is puzzling from some epistemological perspectives, since no formal proof is possible of a thesis that involves an informal concept such as effectiveness. Elliott Mendelson has recently argued, however, that equivalencies between intuitive notions and precise notions need not always be considered unprovable theses, and (...) that Church’s thesis should be accepted as true.I want to discuss a thesis that is nearly as important in current research in computer science as Church’s thesis. I call the newer thesis the tractability thesis, since it identifies the intuitive class of computationally tractable problems with a precise class of problems whose solutions can be computed in polynomial time. After briefly reviewing the theory of intractability, I compare the grounds for accepting the tractability thesis with the grounds for accepting Church's thesis. Intimately connected with the tractability thesis is the mathematical conjecture, whose meaning I shall shortly explain, that P≠NP. Unlike Church's thesis, this conjecture is precise enough to be capable of mathematical proof, but most computer scientists believe it even though no proof has been found. As we shall see below, understanding the grounds for acceptance of the conjecture that P≠NP has implications for general questions in the philosophy of mathematics and science, especially concerning the epistemological importance of explanatory and conceptual coherence. (shrink)

In three experiments, we investigated the computational complexity of German reciprocal sentences with different quantificational antecedents. Building upon the tractable cognition thesis (van Rooij, 2008) and its application to the verification of quantifiers (Szymanik, 2010) we predicted complexity differences among these sentences. Reciprocals with all-antecedents are expected to preferably receive a strong interpretation (Dalrymple et al., 1998), but reciprocals with proportional or numerical quantifier antecedents should be interpreted weakly. Experiment 1, where participants completed pictures according to their preferred interpretation, provides (...) evidence for these predictions. Experiment 2 was a picture verification task. The results show that the strong interpretation was in fact possible for tractable all but one-reciprocals, but not for exactly n. The last experiment manipulated monotonicity of the quantifier antecedents. (shrink)

In this paper we study the semantic data complexity of several controlled fragments of English designed for natural language front-ends to OWL (Web Ontology Language) and description logic ontology-based systems. Controlled languages are fragments of natural languages, obtained by restricting natural language syntax, vocabulary and semantics with the goal of eliminating ambiguity. Semantic complexity arises from the formal logic modelling of meaning in natural language and fragments thereof. It can be characterized as the computational complexity of the reasoning problems associated (...) to their semantic representations. Data complexity (the complexity of answering a question over an ontology, stated in terms of the data items stored therein), in particular, provides a measure of the scalability of controlled languages to ontologies, since tractable data complexity implies scalability of data access. We present maximal tractable controlled languages and minimal intractable controlled languages. (shrink)

In the study of cognitive processes, limitations on computational resources (computing time and memory space) are usually considered to be beyond the scope of a theory of competence, and to be exclusively relevant to the study of performance. Starting from considerations derived from the theory of computational complexity, in this paper I argue that there are good reasons for claiming that some aspects of resource limitations pertain to the domain of a theory of competence.

In computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can feasibly work as (...) computational models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes. (shrink)

Perception solves computationally demanding problems at lightning fast speed. It recovers sophisticated representations of the world from degraded inputs, often in a matter of milliseconds. Any theory of perception must be able to explain how this is possible; in other words, it must be able to explain perception's computational tractability. One of the few attempts to move toward such an explanation has been the information encapsulation hypothesis, which posits that perception can be fast because it keeps computational costs low (...) by forgoing access to information stored in cognition. I argue that we have no compelling reason to believe that encapsulation explains (or even contributes to an explanation of) perceptual tractability, and much reason to doubt it. This is because there exist much deeper computational challenges for perception than information access, and these threaten to make the costs of access irrelevant. If this is right, it undermines a core computational motivation for encapsulation and sends us back to the drawing board for explanations of perceptual tractability. (shrink)

Burt's critique of using polygenic scores in social science conflates the “scientific costs” of sociogenomics with “sociopolitical and ethical” concerns. Furthermore, she paradoxically enlists recent advances in controlling for environmental confounding to argue such confounding is scientifically “intractable.” Disinterested social scientists should support ongoing efforts to improve this technology rather than obstructing progress and excusing genetically confounded research.

In the future, when we compare the welfare of a being of one substrate (say, a human) with the welfare of another (say, an artificial intelligence system), we will be making an intersubstrate welfare comparison. In this paper, we argue that intersubstrate welfare comparisons are important, difficult, and potentially tractable. The world might soon contain a vast number of sentient or otherwise significant beings of different substrates, and moral agents will need to be able to compare their welfare levels. However, (...) this work will be difficult, because we lack the same kinds of commonalities across substrates that we have within them. Fortunately, we might be able to make at least some intersubstrate welfare comparisons responsibly in spite of these issues. We make the case for cautious optimism and call for more research. (shrink)

Coalitional games raise a number of important questions from the point of view of computer science, key among them being how to represent such games compactly, and how to efficiently compute solution concepts assuming such representations. Marginal contribution nets , introduced by Ieong and Shoham, are one of the simplest and most influential representation schemes for coalitional games. MC-nets are a rulebased formalism, in which rules take the form pattern → value, where “pattern ” is a Boolean condition over agents, (...) and “value ” is a numeric value. Ieong and Shoham showed that, for a class of what we will call “basic” MC-nets, where patterns are constrained to be a conjunction of literals, marginal contribution nets permit the easy computation of solution concepts such as the Shapley value. However, there are very natural classes of coalitional games that require an exponential number of such basic MC-net rules. We present read-once MC-nets, a new class of MC-nets that is provably more compact than basic MC-nets, while retaining the attractive computational properties of basic MC-nets. We show how the techniques we develop for read-once MC-nets can be applied to other domains, in particular, computing solution concepts in network flow games on series-parallel networks. (shrink)

Many compelling examples have recently been provided in which people can achieve impressive epistemic success, e.g. draw highly accurate inferences, by using simple heuristics and very little information. This is possible by taking advantage of the features of the environment. The examples suggest an easy and appealing naturalization of rationality: on the one hand, people clearly can apply simple heuristics, and on the other hand, they intuitively ought do so when this brings them high accuracy at little cost.. The ‘ought-can’ (...) principle is satisfied, and rationality is meaningfully normative. We show, however, that this naturalization program is endangered by a computational wrinkle in the adaptation process taken to be responsible for this heuristics-based (‘ecological’) rationality: for the adaptation process to guarantee even minimal rationality, it requires astronomical computational resources, making the problem intractable. We consider various plausible auxiliary assumptions in attempt to remove this obstacle, and show that they do not succeed; intractability is a robust property of adaptation. We discuss the implications of our findings for the project of naturalizing rationality. (shrink)

Different versions of moral projectivism are delineated: minimal, metaphysical, nihilistic, and noncognitivist. Minimal projectivism (the focus of this paper) is the conjunction of two subtheses: (1) that we experience morality as an objective aspect of the world and (2) that this experience has its origin in an affective attitude (e.g., an emotion) rather than in perceptual faculties. Both are empirical claims and must be tested as such. This paper does not offer ideas on any specific test procedures, but rather undertakes (...) the important preliminary task of clarifying the content of these subtheses (e.g., what is meant by "objective"? what is meant by "experience"?). Finally, attention is given to the relation between (a) acknowledging that the projectivist account might be true of a token moral judgment and (b) maintaining moral projectivism to be true as a general thesis. (shrink)

We present a rational model of consumer choice, which can also serve as a behavioral model. The central construct is λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda $$\end{document}, the marginal utility of money, derived from the consumer’s rest-of-life problem. It provides a simple criterion for choosing a consumption bundle in a separable consumption problem. We derive a robust approximation of λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda $$\end{document} and show how to incorporate liquidity constraints, (...) indivisibilities, and adaptation to a changing environment. We find connections with numerous historical and recent constructs, both behavioral and neoclassical, and draw contrasts with standard partial equilibrium analysis. The result is a better grounded, more flexible, and more intuitive description of consumer choice. (shrink)

How can we prove that some fragment of a given logic has the power to define precisely all structural properties that satisfy some characteristic semantic preservation condition? This issue is a fundamental one for classical model theory and applications in non-classical settings alike. While methods differ greatly, and while the classical methods can usually not be matched for instance in the setting of finite model theory, this note surveys some interesting commonality revolving around the use and availability of tractable representatives (...) in the relevant model classes. The construction of models in which simple invariants like partial types based on some weak fragment control all the relevant structural properties, may be seen at the heart of such questions. We highlight some constructions involving degrees of acyclicity and saturation that can be achieved in finite model constructions, and discuss their uses towards expressive completeness w.r.t. bisimulation based equivalences in hypergraphs and relational structures. The emphasis is on the combinatorial challenges in such more constructive approaches that work in non-classical settings and especially in finite model theory. One new result concerns expressive completeness w.r.t. guarded negation bisimulation, a back-and-forth equivalence involving local homomorphisms. (shrink)

:We propose to strengthen Popper’s notion of falsifiability by adding the requirement that when an observation is inconsistent with a theory, there must be a ‘short proof’ of this inconsistency. We model the concept of a short proof using tools from computational complexity, and provide some examples of economic theories that are falsifiable in the usual sense but not with this additional requirement. We consider several variants of the definition of ‘short proof’ and several assumptions about the difficulty of computation, (...) and study their different implications on the falsifiability of theories. (shrink)

Perception solves computationally demanding problems at lightning fast speed. It recovers sophisticated representations of the world from degraded inputs, often in a matter of milliseconds. Any theory of perception must be able to explain how this is possible; in other words, it must be able to explain perception’s computational tractability. One of the few attempts to move toward such an explanation is the information encapsulation hypothesis, which posits that perception can be fast because it keeps computational costs low by (...) forgoing access to information stored in cognition. I argue that we have no compelling reason to believe that encapsulation explains (or even contributes to an explanation of) perceptual tractability, and much reason to doubt it. This is because there exist much deeper computational challenges for perception than information access, and these threaten to make the costs of access irrelevant. If this is right, it undermines a core computational motivation for encapsulation and sends us back to the drawing board for explanations of perceptual tractability. (shrink)

Risk attitude is known to be a key determinant of various economic and financial choices. Behavioral studies that aim to evaluate the role of risk attitudes in contexts of this type, therefore, require tools for measuring individual risk tolerance. Recent developments in decision theory provide such tools. However, the methods available can be time consuming. As a result, some practitioners might have an incentive to prefer “fast and frugal” methods to clean but more costly methods. In this article, we focus (...) on a tractable procedure initially proposed by Holt and Laury (2002) to elicit risk attitude. We generalize this method to measure utility and risk aversion as follows. First, we allow measurement of probabilistic risk attitude through violations of expected utility due to probability weighting. Second, we use the outcome scale rather than the probability scale in the menu of choices. Third, we compare sure payoffs with lotteries instead of comparing non-degenerate lotteries. A within-subject experimental study illustrates the gains in tractability and bias minimization that can result from such an extension. (shrink)

We describe new results in parametrized complexity theory. In particular, we prove a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. We also study the parametrized complexity of analogues of PSPACE via certain natural problems concerning k-move games. Finally, we examine several aspects of the structural complexity of W [P] and related classes. For instance, we show that W[P] can be characterized in terms (...) of the DTIME ) and NP. (shrink)

Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it (...) is shown that the class FPT of tractable parameterized problems has interesting and natural internal structure. (shrink)

We study a refined framework of parameterized complexity theory where the parameter dependence of fixed-parameter tractable algorithms is not arbitrary, but restricted by a function in some family . For every family of functions, this yields a notion of -fixed-parameter tractability. If is the class of all polynomially bounded functions, then -fixed-parameter tractability coincides with polynomial time decidability and if is the class of all computable functions, -fixed-parameter tractability coincides with the standard notion of fixed-parameter tractability. (...) There are interesting choices of between these two extremes, for example the class of all singly exponential functions. In this article, we study the general theory of -fixed-parameter tractability. We introduce a generic notion of reduction and two classes -W[P] and -XP, which may be viewed as analogues of NP and EXPTIME, respectively, in the world of -fixed-parameter tractability. (shrink)

There continues to be significant confusion about the goals, scope, and nature of modelling practice in neuroeconomics. This article aims to dispel some such confusion by using one of the most recent critiques of neuroeconomic modelling as a foil. The article argues for two claims. First, currently, for at least some economic model of choice behaviour, the benefits derivable from neurally informing an economic model do not involve special tractability costs. Second, modelling in neuroeconomics is best understood within Marr’s (...) three-level of analysis framework and in light of a co-evolutionary research ideology. The first claim is established by elucidating the relationship between the tractability of a model, its descriptive accuracy, and its number of variables. The second claim relies on an explanation of what it can take to neurally inform an economic model of choice behaviour. 1 Introduction2 Neurally Informed Models of Choice: A Case Study2.1 A case study on risk-sensitive choice2.1.1 Target and modelling framework2.1.2 Research question and hypotheses2.1.3 Competitive models of risk-sensitive behaviour2.1.4 Model-based fMRI: from economics to brains and back2.2 Neurally informed modelling3 Tractability: When Does Size Matter?4 Neural Integration and the Co-evolutionary Research Ideology5 Conclusion. (shrink)

We address in this paper the problem of counting the models of a propositional theory under incremental changes to its literals. Specifcally, we show that if a propositional theory Δ is in a special form that we call smooth, deterministic, decomposable negation normal form, then for any consistent set of literals S, we can simultaneously count the models of Δ ∪ S and the models of every theory Δ ∪ T where T results from adding, removing or flipping a literal (...) in S. We present two results relating to the time and space complexity of compiling propositional theories into sd-DNNF. First, we show that if a conjunctive normal form has a bounded treewidth, then it can be compiled into an sd-DNNF in time and space which are linear in its size. Second, we show that sd-DNNF is a strictly more space efficient representation than Free Binary Decision Diagrams. Finally, we discuss some applications of the counting results to truth maintenance systems, belief revision, and model-based diagnosis. (shrink)

We address in this paper the problem of counting the models of a propositional theory under incremental changes to its literals. Specifcally, we show that if a propositional theory Δ is in a special form that we call smooth, deterministic, decomposable negation normal form (sd-DNNF), then for any consistent set of literals S, we can simultaneously count (in time linear in the size of Δ) the models of Δ ∪ S and the models of every theory Δ ∪ T where (...) T results from adding, removing or flipping a literal in S. We present two results relating to the time and space complexity of compiling propositional theories into sd-DNNF. First, we show that if a conjunctive normal form (CNF) has a bounded treewidth, then it can be compiled into an sd-DNNF in time and space which are linear in its size. Second, we show that sd-DNNF is a strictly more space efficient representation than Free Binary Decision Diagrams (FBDDs). Finally, we discuss some applications of the counting results to truth maintenance systems, belief revision, and model-based diagnosis. (shrink)

Social norms – rules governing which behaviours are deemed appropriate or inappropriate within a given community – are typically taken to be uniquely human. Recently, this position has been challenged by a number of philosophers, cognitive scientists, and ethologists, who have suggested that social norms may also be found in certain non-human animal communities. Such claims have elicited considerable scepticism from norm cognition researchers, who doubt that any non-human animals possess the psychological capacities necessary for normative cognition. However, there is (...) little agreement among these researchers about what these psychological prerequisites are. This makes empirical study of animal social norms difficult, since it is not clear what we are looking for and thus what should count as behavioural evidence for the presence (or absence) of social norms in animals. To break this impasse, we offer an approach that moves beyond contested psychological criteria for social norms. This approach is inspired by the animal culture research program, which has made a similar shift away from heavily psychological definitions of ‘culture’ and to become organized around a cluster of more empirically tractable concepts of culture. Here, we propose an analogous set of constructs built around the core notion of a normative regularity, which we define as a socially maintained pattern of behavioural conformity within a community. We suggest methods for studying potential normative regularities in wild and captive primates. We also discuss the broader scientific and philosophical implications of this research program with respect to questions of human uniqueness, animal welfare and conservation. (shrink)

In the recent literature at the interface between economics, biology and neuroscience, several authors argue that by adopting an interdisciplinary approach to the analysis of decision making, economists will be able to construct predictively and explanatorily superior models. However, most economists remain quite reluctant to import biological or neural insights into their account of choice behaviour. In this paper, I reconstruct and critique one of the main arguments by means of which economists attempt to vindicate their conservative position. Furthermore, I (...) develop an alternative defense of the thesis that economists justifiably rely on a methodologically distinctive approach to the modelling of choice behaviour. (shrink)

In the dissertation we study the complexity of generalized quantifiers in natural language. Our perspective is interdisciplinary: we combine philosophical insights with theoretical computer science, experimental cognitive science and linguistic theories. -/- In Chapter 1 we argue for identifying a part of meaning, the so-called referential meaning (model-checking), with algorithms. Moreover, we discuss the influence of computational complexity theory on cognitive tasks. We give some arguments to treat as cognitively tractable only those problems which can be computed in polynomial time. (...) Additionally, we suggest that plausible semantic theories of the everyday fragment of natural language can be formulated in the existential fragment of second-order logic. -/- In Chapter 2 we give an overview of the basic notions of generalized quantifier theory, computability theory, and descriptive complexity theory. -/- In Chapter 3 we prove that PTIME quantifiers are closed under iteration, cumulation and resumption. Next, we discuss the NP-completeness of branching quantifiers. Finally, we show that some Ramsey quantifiers define NP-complete classes of finite models while others stay in PTIME. We also give a sufficient condition for a Ramsey quantifier to be computable in polynomial time. -/- In Chapter 4 we investigate the computational complexity of polyadic lifts expressing various readings of reciprocal sentences with quantified antecedents. We show a dichotomy between these readings: the strong reciprocal reading can create NP-complete constructions, while the weak and the intermediate reciprocal readings do not. Additionally, we argue that this difference should be acknowledged in the Strong Meaning hypothesis. -/- In Chapter 5 we study the definability and complexity of the type-shifting approach to collective quantification in natural language. We show that under reasonable complexity assumptions it is not general enough to cover the semantics of all collective quantifiers in natural language. The type-shifting approach cannot lead outside second-order logic and arguably some collective quantifiers are not expressible in second-order logic. As a result, we argue that algebraic (many-sorted) formalisms dealing with collectivity are more plausible than the type-shifting approach. Moreover, we suggest that some collective quantifiers might not be realized in everyday language due to their high computational complexity. Additionally, we introduce the so-called second-order generalized quantifiers to the study of collective semantics. -/- In Chapter 6 we study the statement known as Hintikka's thesis: that the semantics of sentences like ``Most boys and most girls hate each other'' is not expressible by linear formulae and one needs to use branching quantification. We discuss possible readings of such sentences and come to the conclusion that they are expressible by linear formulae, as opposed to what Hintikka states. Next, we propose empirical evidence confirming our theoretical predictions that these sentences are sometimes interpreted by people as having the conjunctional reading. -/- In Chapter 7 we discuss a computational semantics for monadic quantifiers in natural language. We recall that it can be expressed in terms of finite-state and push-down automata. Then we present and criticize the neurological research building on this model. The discussion leads to a new experimental set-up which provides empirical evidence confirming the complexity predictions of the computational model. We show that the differences in reaction time needed for comprehension of sentences with monadic quantifiers are consistent with the complexity differences predicted by the model. -/- In Chapter 8 we discuss some general open questions and possible directions for future research, e.g., using different measures of complexity, involving game-theory and so on. -/- In general, our research explores, from different perspectives, the advantages of identifying meaning with algorithms and applying computational complexity analysis to semantic issues. It shows the fruitfulness of such an abstract computational approach for linguistics and cognitive science. (shrink)

Contemporary philosophy often chants the mantra, ‘Philosophy is continuous with science.’ Now Shepanski gives it a clear sense, by extracting from W. V. Quine’s writings an explicit normative epistemology – i.e. an explicit set of norms for theorizing – that applies to philosophy and science alike. It is recognizably a version of empiricism, yet it permits the kind of philosophical theorizing that Quine practised all his life. Indeed, it is that practice, more than any overt avowals, that justifies attributing this (...) set of norms to Quine. -/- The Quinean epistemology is supported by a metaphilosophy that judges epistemologies by the tenability of their consequences. Shepanski explores the Quinean epistemology’s consequences for inductive and abductive inference, for mathematical entities, for science and for common sense. Moreover, he finds that it continues to be fruitful, as illustrated by a case study in which Quinean methods lead to a new formal treatment of the propositional attitudes. Finally, there is critical discussion of popular alternative views, including foundationalism, the centrality of knowledge, and Quine’s own epistemological naturalism. -/- By focusing on Quine’s normative epistemology, Shepanski illuminates a part of Quine’s thought that has hitherto been insufficiently discussed, and provides a tractable starting point for readers who are new to Quine. Most importantly, he isolates the part of Quine’s thought that has the greatest potential impact outside epistemology, outside philosophy of language, and even outside philosophy. (shrink)