Fundamenta Informaticae - Volume 17, issue 1-2

Article Type: Other

DOI: 10.3233/FI-1992-171-201

Citation: Fundamenta Informaticae, vol. 17, no. 1-2, pp. i-vii, 1992

Authors: Truszczyński, Miroslaw

Article Type: Editorial

DOI: 10.3233/FI-1992-171-202

Citation: Fundamenta Informaticae, vol. 17, no. 1-2, pp. 1-3, 1992

Authors: Boutilier, Craig

Article Type: Research Article

Abstract: A drawback of existing epistemic logics is their inability to deal with entrenchment of beliefs. All beliefs have equal status; none can be held more firmly than others. We present a bimodal logic that generalizes Levesque’s reconstruction of autoepistemic logic. In our system standard epistemic concepts can be represented, including the notion of only knowing, but elements of a belief set may be more or less entrenched. This has important implications for the distinction between epistemic defaults and subjunctive (and normative) defaults, both of which are representable in our system.

DOI: 10.3233/FI-1992-171-203

Citation: Fundamenta Informaticae, vol. 17, no. 1-2, pp. 5-29, 1992

Authors: Eiter, Thomas | Gottlob, Georg

Article Type: Research Article

Abstract: We investigate the complexity of autoepistemic reasoning with parsimonious and moderately grounded expansions. A stable expansion of an autoepistemic set of premises is parsimonious if its objective (i.e. nonmodal) part does not contain the objective part of any other stable expansion. We prove that deciding whether a formula φ belongs to at least one parsimonious stable expansion of a finite base set A is complete for Σ 3 P , while deciding containment in all parsimonious stable expansions is complete for ∏ 3 P . …Similar results are derived for autoepistemic reasoning with moderately grounded expansions. In particular, we show that deciding whether a formula φ belongs to some moderately grounded expansion of a finite base set A is Σ 3 P -complete, and that deciding whether φ belongs to all moderately grounded expansions is ∏ 3 P -complete. These results suggest that reasoning with parsimonious stable expansions and moderately grounded expansions is strictly harder than reasoning in Moore’s standard version of autoepistemic logic. We also address the complexity of reasoning if the set A is in a normalized form, and derive completeness results for this case. Show more

DOI: 10.3233/FI-1992-171-204

Citation: Fundamenta Informaticae, vol. 17, no. 1-2, pp. 31-53, 1992

Authors: Fitting, Melvin

Article Type: Research Article

Abstract: Suppose there are several experts, with some dominating others (expert A dominates expert B if B says something is true whenever A says it is). Suppose, further, that each of the experts has his or her own view of what is possible – in other words each of the experts has their own Kripke model in mind (subject, of course, to the dominance relation that may hold between experts). How will they assign truth values to sentences in a common modal language, and on what sentences will they agree? This problem can be reformulated as one …about many-valued Kripke models, allowing many-valued accessibility relations. This is a natural generalization of conventional Kripke models that has only recently been looked at. The equivalence between the many-valued version and the multiple expert one will be formally established. Finally we will axiomatize many-valued modal logics, and sketch a proof of completeness. Show more

DOI: 10.3233/FI-1992-171-205

Citation: Fundamenta Informaticae, vol. 17, no. 1-2, pp. 55-73, 1992

Authors: Lakemeyer, Gerhard

Article Type: Research Article

Abstract: Agents with perfect introspection may have incomplete beliefs about the world, but they possess complete knowledge about their own beliefs. This fact suggests that the beliefs of introspective agents should be completely determined by their objective beliefs, that is, those beliefs that are only about the domain in question and not about other beliefs. Introspection and logical reasoning alone should suffice to reconstruct all other beliefs from the objective ones. While this property has been shown to hold for propositional belief logics, there have so far only been negative results in the case of first-order belief logics with quantifying-in. …In this paper we present a logic of belier with quantifying-in, where the beliefs of a perfectly introspective agent are indeed uniquely determined by the objective beliefs. The result is obtained by weakening the notion of belief of an existing logic that does not have this property. Show more

DOI: 10.3233/FI-1992-171-206

Citation: Fundamenta Informaticae, vol. 17, no. 1-2, pp. 75-98, 1992

Authors: Marek, V. Wiktor | Truszczynski, Miroslaw

Article Type: Research Article

Abstract: Investigations of default logic have been so far mostly concerned with the notion of an extension of a default theory. It turns out, however, that default logic is much richer. Namely, there are other natural classes of objects that might be associated with default reasoning. We study two such classes of objects with emphasis on their relations with modal nonmonotonic formalisms. First, we introduce the concept of a weak extension and study its properties. It has long been suspected that there are close connections between default and autoepistemic logics. The notion of weak extension allows us to precisely describe …the relationship between these two formalisms. In particular, we show that default logic with weak extensions is essentially equivalent to autoepistemic logic, that is, nonmonotonic logic KD45. In the paper we also study the notion of a set of formulas closed under a default theory. These objects are shown to correspond to stable theories and to modal logic S5. In particular, we show that skeptical reasoning with sets closed under default theories is closely related with provability in S5. As an application of our results we determine the complexity of reasoning with weak extensions and sets closed under default theories. Show more

DOI: 10.3233/FI-1992-171-207

Citation: Fundamenta Informaticae, vol. 17, no. 1-2, pp. 99-116, 1992

Authors: Niemelä, Ilkka N.F.

Article Type: Research Article

Abstract: The decidability and computational complexity of autoepistemic reasoning is investigated in a general setting where the autoepistemic logic CLae built on top of a given classical logic CL is studied. Correct autoepistemic conclusions from a set of premises are defined in terms of expansions of the premises. Three classes of expansions are studied: Moore style stable expansions, enumeration based expansions, and L-hierarchic expansions. A simple finitary characterization for each type of expansions in CLae is developed. Using the characterizations conditions ensuring that a set of premises has at least one or exactly one stable expansion can be stated …and an upper bound for the number of stable expansions of a set of premises can be given. With the aid of the finitary characterizations results on decidability and complexity of autoepistemic reasoning are obtained. E.g., it is shown that autoepistemic reasoning based on each of the three types of expansions is decidable if the monotonic consequence relation given by the underlying classical logic is decidable. In the propositional case decision problems related to the three classes of expansions are shown to be complete problems with respect to the second level of the polynomial time hierarchy. This implies that propositional autoepistemic reasoning is strictly harder than classical propositional reasoning unless the polynomial time hierarchy collapses. Show more

DOI: 10.3233/FI-1992-171-208

Citation: Fundamenta Informaticae, vol. 17, no. 1-2, pp. 117-155, 1992

Authors: Schwarz, Grigori

Article Type: Research Article

Abstract: We propose a new variant of autoepistemic logic which, intuitively, corresponds to understanding a belief operator L as “is known”, in contrast to the interpretation of L as “is believed” in Moore’s autoepistemic logic. Formal properties of the new logic and relationship to Moore’s logic are studied in detail.

DOI: 10.3233/FI-1992-171-209

Citation: Fundamenta Informaticae, vol. 17, no. 1-2, pp. 157-173, 1992