Logic has pride of place in mathematics and its 20th century offshoot, computer science. Modern symbolic logic was developed, in part, as a way to provide a formal framework for mathematics: Frege, Peano, Whitehead and Russell, as well as Hilbert developed systems of logic to formalize mathematics. These systems were meant to serve either as themselves foundational, or at least as formal analogs of mathematical reasoning amenable to mathematical study, e.g., in Hilbert’s consistency program. Similar efforts continue, but have been (...) expanded by the development of sophisticated methods to study the properties of such systems using proof and model theory. In parallel with this evolution of logical formalisms as tools for articulating mathematical theories (broadly speaking), much progress has been made in the quest for a mechanization of logical inference and the investigation of its theoretical limits, culminating recently in the development of new foundational frameworks for mathematics with sophisticated computer-assisted proof systems. In addition, logical formalisms developed by logicians in mathematical and philosophical contexts have proved immensely useful in describing theories and systems of interest to computer scientists, and to some degree, vice versa. Three examples of the influence of logic in computer science are automated reasoning, computer verification, and type systems for programming languages. (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)

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 describe approximation algorithms for MAX SAT with performance ratios arbitrarily close to 1, in particular, when performance ratios exceed the limits of polynomial-time approximation. Namely, given a polynomial-time α-approximation algorithm , we construct an -approximation algorithm . The algorithm runs in time of the order ck, where k is the number of clauses in the input formula and c is a constant depending on α. Thus we estimate the cost of improving a performance ratio. Similar constructions for MAX 2SAT (...) and MAX 3SAT are also described. Taking known algorithms as , we obtain particular upper bounds on the running time of. (shrink)

Semantic networks were developed in cognitive science and artificial intelligence studies as graphical knowledge representation and inference tools emulating human thought processes. Formal analysis of the representation and inference capabilities of the networks modeled them as subsets of standard first-order logic (FOL), restricted in the operations allowed in order to ensure the tractability that seemed to characterize human reasoning capabilities. The graphical network representations were modeled as providing a visual language for the logic. Sub-sets of FOL targeted on knowledge representation (...) came to be called description logics, and research on these logics has focused on issues of tractability of subsets with differing representation capabilities, and on the implementation of practical inference systems achieving the best possible performance. Semantic network research has kept pace with these developments, providing visual languages for knowledge entry, editing, and presenting the results of inference, that translate unambiguously to the underlying description logics. This paper discusses the design issues for such semantic network formalisms, and illustrates them through detailed examples of significant generic knowledge structures analyzed in the literature, including determinables, contrast sets, genus/differentiae, taxonomies, faceted taxonomies, cluster concepts, family resemblances, graded concepts, frames, definitions, rules, rules with exceptions, essence and state assertions, opposites and contraries, relevance, and so on. Such examples provide important test material for any visual language formalism for logic. (shrink)

We show that Smullyan's analytic tableaux cannot p-simulate the truth-tables. We identify the cause of this computational breakdown and relate it to an underlying semantic difficulty which is common to the whole tradition originating in Gentzen's sequent calculus, namely the dissonance between cut-free proofs and the Principle of Bivalence. Finally we discuss some ways in which this principle can be built into a tableau-like method without affecting its analytic nature.

Research on computational models of scientific discovery investigates both the induction of descriptive laws and the construction of explanatory models. Although the work in law discovery centers on knowledge‐lean approaches to searching a problem space, research on deeper modeling tasks emphasizes the pivotal role of domain knowledge. As an example, our own research on inductive process modeling uses information about candidate processes to explain why variables change over time. However, our experience with IPM, an artificial intelligence system that implements this (...) approach, suggests that process knowledge is insufficient to avoid consideration of implausible models. To this end, the discovery system needs additional knowledge that constrains the model structures. We report on an extended system, SC‐IPM, that uses such information to reduce its search through the space of candidates and to produce models that human scientists find more plausible. We also argue that although people carry out less extensive search than SC‐IPM, they rely on the same forms of knowledge—processes and constraints—when constructing explanatory models. (shrink)

Contemporary epistemological and cognitive studies, as well as recent trends in computer science and game theory have revealed an increasingly important and intimate relationship between Information, Interaction, and Agency. Agents perform actions based on the available information and in the presence of other interacting agents. From this perspective Information, Interaction, and Agency neatly ties together classical themes like rationality, decision-making and belief revision with games, strategies and learning in a multi-agent setting. Unified by the central notions Information, Interaction, and Agency, (...) the essays in this volume provide refreshing methodological perspectives on belief revision, dynamic epistemic logic, von Neumann games, and evolutionary game theory; all of which in turn are central approaches to understanding our own rationality and that of other agents. (shrink)