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

Authors: Skarbek, Władysław

Article Type: Research Article

Abstract: Spatial Signal OR Graphs (SSOG) are defined and specialized to fractal pattern generation (FSSOG) and cellular array pattern generation(CSSOG). It is proved that fractal patterns always stabilize after predictable transient time, while cellular pattern graphs enter in parallel mode into a stable state if the initial state is even, otherwise they enter into a cycle of length 2. If nondeterministic mode is considered then any G ∈ SSOG enters a stable state with probability one.

DOI: 10.3233/FI-1996-283410

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

Authors: Suraj, Zbigniew

Article Type: Research Article

Abstract: The main objective of machine discovery is the determination of relations between data and of data models. In the paper we describe a method for discovery of data models represented by concurrent systems from experimental tables. The basic step consists in a determination of rules which yield a decomposition of experimental data tables; the components are then used to define fragments of the global system corresponding to a table. The method has been applied to automatic data models discovery from experimental tables with Petri nets as models for concurrency.

Keywords: data mining, system decomposition, rough sets, concurrent models, laws discovery from experimental data

DOI: 10.3233/FI-1996-283411

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

Authors: Schlechta, Karl

Article Type: Research Article

Abstract: Our subject is the representation and analysis of simple first-order default statements of ordinary language, such as “normally, birds fly”. There are, among other approaches, two kinds of analysis, both semantic in style. One interprets “normally, birds fly” along the lines of “for every item x in the domain of discourse, the most normal models of “x is a bird” are models of “x flies””. This is the preferential models approach, first outlined by Bossu/Siegel and Shoham, and studied by Kraus, Lehmann, Magidor and others. The other interprets “normally, birds fly” along the lines of “there is an important subset …of the birds, all of whose elements fly”. This is the generalized quantifier approach, formulated and developed by the author. The purpose of the present paper is to show how the two approaches may usefully be combined into a single two-stage approach, and how such a combination provides an elegant account of certain problematic examples. Show more

Keywords: Nonmonotonic Logic, Defaults, Preferential Models, Generalized Quantifiers

DOI: 10.3233/FI-1996-283412

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

Authors: Winkowski, Józef

Article Type: Research Article

Abstract: Structures called concatenable weighted pomsets are introduced which can serve as models of processes of Petri nets, including nets with time features. Operations on such structures are defined which allow to combine them sequentially and in parallel. These operations correspond to natural operations on processes. They make the universe of concatenable weighted pomsets a partial algebra which appears to be a symmetric strict monoidal category. Sets of processes of timed and time Petri nets are characterized as subsets of this algebra.

Keywords: concatenable weighted pomset, symmetry, table, sequential composition, parallel composition, interchange, algebra, timed Petri net, time Petri net, process, potential timed process, actual timed process

DOI: 10.3233/FI-1996-283413

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

Authors: Wróblewski, Jakub

Article Type: Research Article

Abstract: A lot of research on genetic algorithms theory is concentrated on classical, binary case. However, there are many other types of useful genetic algorithms (GA), e.g. tree-based (genetic programming), or order-based ones. This paper shows, that many of classical results can be transferred into the order-based GAs. The analysis includes the Schema Theorem and Markov chain modelling of order-based GA.

DOI: 10.3233/FI-1996-283414

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