Author name cluster

Jonathan Stillman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

AAAI Conference 1992 Conference Paper

The Complexity of Propositional Default Logics

Jonathan Stillman

We characterize the complexity of several typical problems in propositional default logics. In particular, we examine the complexity of extension membership, extension existence, and extension entailment problems. We show that the extension existence problem is X; complete, even for semi-normal theories, and that the extension membership and entailment problems are X; complete and II; complete respectively, even when restricted to normal default theories. These results contribute to our understanding of the computational relationship between propositional default logics and other formalisms for nonmonotonic reasoning, e. g. , autoepistemic logic and McDermott and Doyle’ s NML, as well as their relationship to problems outside the realm of nonmonotonic reasoning.

PDF Details

TCS Journal 1991 Journal Article

Semi-unification

Deepak Kapur
David Musser
Paliath Narendran
Jonathan Stillman

Semi-unification is a generalization fo both matching and ordinary unification: for a given pair of terms s and t, two substitution ρ and σ are sought such that ρ(σ(s))=σ(t). Semi-unifiability can be used as a check for non-termination of a rewrite rule, but constructing a correct semi- unification algorithm has been an elusive goal; for example, an algorithm given by Purdom in his RTA-87 paper was incorrect. This paper presents a decision procedure for semi-unification based on techniques semilar to those used in the Knuth-Bendix completion procedure. When its substitutions ρ and σ are easily extracted. Though exponential in its computing time, the decision procedure can be improved to a polynomial-time algorithm, as will be shown.

Details DOI

AAAI Conference 1990 Conference Paper

It’s Not My Default: The Complexity of Membership Problems in Restricted Propositional Default Logics

Jonathan Stillman

We investigate the computational complexity of membership problems in a number of propositional default logics. We introduce a hierarchy of classes of propositional default rules that extends that described in [Kautz and Selman 19891, and characterize the complexity of membership problems in these classes under various simplifying assumptions about the underlying propositional theory. Our work significantly extends both that presented in [Kautz and Selman 19891 and in [Stillman 199Oal.

PDF Details

UAI Conference 1989 Conference Paper

Uncertainty and Incompleteness: Breaking the Symmetry of Defeasible Reasoning

Piero P. Bonissone
David A. Cyrluk
James W. Goodwin
Jonathan Stillman

Two major difficulties in using default logics are their intractability and the problem of selecting among multiple extensions. We propose an approach to these problems based on integrating nommonotonic reasoning with plausible reasoning based on triangular norms. A previously proposed system for reasoning with uncertainty (RUM) performs uncertain monotonic inferences on an acyclic graph. We have extended RUM to allow nommonotonic inferences and cycles within nonmonotonic rules. By restricting the size and complexity of the nommonotonic cycles we can still perform efficient inferences. Uncertainty measures provide a basis for deciding among multiple defaults. Different algorithms and heuristics for finding the optimal defaults are discussed.

Details