Fundamenta Informaticae - Volume 28, issue 3-4

Authors: Marek, Wiktor | Polkowski, Lech | Skowron, Andrzej

Article Type: Other

DOI: 10.3233/FI-1996-283415

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. i-i, 1996

Authors: Banerjee, Mohua | Chakraborty, Mihir K.

Article Type: Research Article

Abstract: While studying rough equality within the framework of the modal system S5 , an algebraic structure called rough algebra [1], came up. Its features were abstracted to yield a topological quasi-Boolean algebra (tqBa). In this paper, it is observed that rough algebra is more structured than a tqBa. Thus, enriching the tqBa with additional axioms, two more structures, viz. pre-rough algebra and rough algebra, are denned. Representation theorems of these algebras are also obtained. Further, the corresponding logical systems ℒ1 ℒ2 are proposed and eventually, ℒ2 is proved to be sound and complete with respect to a …rough set semantics. Show more

Keywords: Rough set theory, Algebraic logic, Modal system S 5

DOI: 10.3233/FI-1996-283401

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. 211-221, 1996

Authors: Bochman, Alexander

Article Type: Research Article

Abstract: In this paper we develop a logical framework for normal logic programs, called default consequence relations. We give a representation of major semantics for logic programs in this formalism and study the question what logics are adequate for the latter. It is shown that, in general, default consequence relations based on three-valued inference are appropriate for these semantics, though different semantics admit different kinds of inference.

DOI: 10.3233/FI-1996-283402

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. 223-245, 1996

Authors: Ho, Nguyen Cat

Article Type: Research Article

Abstract: In this paper we shall introduce a notion of formal knowledge base consisting of statements associated with linguistic truth degrees and a set of inference rules handling this kind of statements. A deductive reasoning method based on these inference rules will be examined. The logical foundation of this method is linguistic valued logic based on extended hedge algebras and, based on this basis, the consistency of the knowledge base will be considered.

DOI: 10.3233/FI-1996-283403

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. 247-259, 1996

Authors: Doherty, Patrick | Łukaszewicz, Witold | Szałas, Andrzej

Article Type: Research Article

Abstract: Circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic and commonsense reasoning, but difficult to apply in practice due to the use of second-order formulas. One proposal for dealing with the computational problems is to identify classes of first-order formulas whose circumscription can be shown to be equivalent to a first-order formula. In previous work, we presented an algorithm which reduces certain classes of second-order circumscription axioms to logically equivalent first-order formulas. The basis for the algorithm is an elimination lemma due to Ackermann. In this paper, we capitalize on the use of a generalization of Ackermann's …Lemma in order to deal with a subclass of universal formulas called semi-Horn formulas. Our results subsume previous results by Kolaitis and Papadimitriou regarding a characterization of circumscribed definite logic programs which are first-order expressible. The method for distinguishing which formulas are reducible is based on a boundedness criterion. The approach we use is to first reduce a circumscribed semi-Horn formula to a fixpoint formula which is reducible if the formula is bounded, otherwise not. In addition to a number of other extensions, we also present a fixpoint calculus which is shown to be sound and complete for bounded fixpoint formulas. Show more

DOI: 10.3233/FI-1996-283404

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. 261-271, 1996

Authors: Green, John | Horne, Neil | Orłowska, Ewa | Siemens, Paul

Article Type: Research Article

Abstract: The purpose of this paper is to define and investigate document retrieval strategies based on rough sets. A subject classification index is modelled by means of a family of set-theoretic information systems. The family induces a power set hierarchy built from the set of keywords. In the paper, the task of information retrieval in response to a query that refers to several levels of that hierarchy is defined. Retrieval strategies are proposed and discussed. The strategies are, roughly speaking, based on various types of similarity between sets of keywords included in a query and in a document. It is not …necessarily required that the document matches the query; we allow for approximate matching. Measures of relevance of documents to a query are proposed for the given strategies. Show more

DOI: 10.3233/FI-1996-283405

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. 273-296, 1996

Authors: Grigoriev, Dima | Karpinski, Marek | Odlyzko, Andrew M.

Article Type: Research Article

Abstract: We prove for the first time an existence of the short (polynomial size) proofs for nondivisibility of two sparse polynomials (putting thus this problem is the class NP) under the Extended Riemann Hypothesis. The divisibility problem is closely related to the problem of rational interpolation. Its computational complexity was studied in [5], [4], and [6]. We prove also, somewhat surprisingly, the problem of deciding whether a rational function given by a black box equals to a polynomial belong to the parallel class NC (see, e. g., [KR 90]), provided we know the degree of its sparse representation.

DOI: 10.3233/FI-1996-283406

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. 297-301, 1996

Authors: Gomolińska, Anna

Article Type: Research Article

Abstract: The logic of acceptance and rejection (AEL2) is a nonmonotonic formalism in the spirit of Moore's autoepistemic logic (AEL). AEL2 is to represent knowledge of an ideal rational agent who makes decisions about pieces of information. The case of uncertainty of the agent is considered as well. Therefore the agent's choices are: acceptance, rejection, and the lack of decision. AEL is treated as the nonmonotonic KD45 modal logic. AEL2 may be formalized in a similar way. In the paper the problem of an appropriate semantics for the modal formalization of AEL2 is discussed.

Keywords: autoepistemic logic, nonmonotonic modal logics

DOI: 10.3233/FI-1996-283407

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. 303-313, 1996

Authors: Păun, Gheorghe | Polkowski, Lech | Skowron, Andrzej

Article Type: Research Article

Abstract: In a parallel communicating grammar system, several grammars work together, synchronously, on their own sentential forms, and communicate on request. No restriction is imposed usually about the communicated strings. We consider here two types of restrictions, as models of the negotiation process in multi-agent systems: (1) conditions formulated on the transmitted strings, and (2) conditions formulated on the resulting string in the receiving components. These conditions are expressed in terms of regular languages, whose elements the mentioned strings should be. Moreover, we allow that the communicated string is a part (any one, a prefix, a maximal, a minimal one, etc.) …of the string of the communicating component. We investigate these variants from the point of view of the generative capacity of the corresponding parallel communicating grammar systems. Show more

DOI: 10.3233/FI-1996-283408

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. 315-330, 1996

Authors: Radev, Slavian

Article Type: Research Article

Abstract: Argumentation systems are useful instruments for decision support when the arguments are changed dynamically in dependence of the users and the situation. In argumentation systems different strategies are used when the system prepares the argumentation for a given situation and/or user. These strategies correspond to some many valued logics and some of these strategies have fuzzy and rough interpretations. Many information systems have interpretation in different argumentation systems. For the lower and upper approximations there are equivalent argumentation strategies that correspond to the well known logical systems. Moreover when a practical system chooses the arguments for the user it needs …more compact argumentation then the list of all procedures it uses. Then the argumentation system finds arguments with the same persuade power as its argumentation. Show more

Keywords: information systems, argumentation systems, decision support systems, rough sets, many-valued logics, proofs, deduction, induction, analogy

DOI: 10.3233/FI-1996-283409

Citation: Fundamenta Informaticae, vol. 28, no. 3-4, pp. 331-346, 1996