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)

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)

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)

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)